1 //===- IRSimilarityIdentifier.h - Find similarity in a module --------------==// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // \file 10 // Interface file for the IRSimilarityIdentifier for identifying similarities in 11 // IR including the IRInstructionMapper, which maps an Instruction to unsigned 12 // integers. 13 // 14 // Two sequences of instructions are called "similar" if they perform the same 15 // series of operations for all inputs. 16 // 17 // \code 18 // %1 = add i32 %a, 10 19 // %2 = add i32 %a, %1 20 // %3 = icmp slt icmp %1, %2 21 // \endcode 22 // 23 // and 24 // 25 // \code 26 // %1 = add i32 11, %a 27 // %2 = sub i32 %a, %1 28 // %3 = icmp sgt icmp %2, %1 29 // \endcode 30 // 31 // ultimately have the same result, even if the inputs, and structure are 32 // slightly different. 33 // 34 // For instructions, we do not worry about operands that do not have fixed 35 // semantic meaning to the program. We consider the opcode that the instruction 36 // has, the types, parameters, and extra information such as the function name, 37 // or comparison predicate. These are used to create a hash to map instructions 38 // to integers to be used in similarity matching in sequences of instructions 39 // 40 // Terminology: 41 // An IRSimilarityCandidate is a region of IRInstructionData (wrapped 42 // Instructions), usually used to denote a region of similarity has been found. 43 // 44 // A SimilarityGroup is a set of IRSimilarityCandidates that are structurally 45 // similar to one another. 46 // 47 //===----------------------------------------------------------------------===// 48 49 #ifndef LLVM_ANALYSIS_IRSIMILARITYIDENTIFIER_H 50 #define LLVM_ANALYSIS_IRSIMILARITYIDENTIFIER_H 51 52 #include "llvm/IR/InstVisitor.h" 53 #include "llvm/IR/Instructions.h" 54 #include "llvm/IR/PassManager.h" 55 #include "llvm/Pass.h" 56 #include "llvm/Support/Allocator.h" 57 58 namespace llvm { 59 class Module; 60 61 namespace IRSimilarity { 62 63 struct IRInstructionDataList; 64 65 /// This represents what is and is not supported when finding similarity in 66 /// Instructions. 67 /// 68 /// Legal Instructions are considered when looking at similarity between 69 /// Instructions. 70 /// 71 /// Illegal Instructions cannot be considered when looking for similarity 72 /// between Instructions. They act as boundaries between similarity regions. 73 /// 74 /// Invisible Instructions are skipped over during analysis. 75 // TODO: Shared with MachineOutliner 76 enum InstrType { Legal, Illegal, Invisible }; 77 78 /// This provides the utilities for hashing an Instruction to an unsigned 79 /// integer. Two IRInstructionDatas produce the same hash value when their 80 /// underlying Instructions perform the same operation (even if they don't have 81 /// the same input operands.) 82 /// As a more concrete example, consider the following: 83 /// 84 /// \code 85 /// %add1 = add i32 %a, %b 86 /// %add2 = add i32 %c, %d 87 /// %add3 = add i64 %e, %f 88 /// \endcode 89 /// 90 // Then the IRInstructionData wrappers for these Instructions may be hashed like 91 /// so: 92 /// 93 /// \code 94 /// ; These two adds have the same types and operand types, so they hash to the 95 /// ; same number. 96 /// %add1 = add i32 %a, %b ; Hash: 1 97 /// %add2 = add i32 %c, %d ; Hash: 1 98 /// ; This add produces an i64. This differentiates it from %add1 and %add2. So, 99 /// ; it hashes to a different number. 100 /// %add3 = add i64 %e, %f; Hash: 2 101 /// \endcode 102 /// 103 /// 104 /// This hashing scheme will be used to represent the program as a very long 105 /// string. This string can then be placed in a data structure which can be used 106 /// for similarity queries. 107 /// 108 /// TODO: Handle types of Instructions which can be equal even with different 109 /// operands. (E.g. comparisons with swapped predicates.) 110 /// TODO: Handle CallInsts, which are only checked for function type 111 /// by \ref isSameOperationAs. 112 /// TODO: Handle GetElementPtrInsts, as some of the operands have to be the 113 /// exact same, and some do not. 114 struct IRInstructionData 115 : ilist_node<IRInstructionData, ilist_sentinel_tracking<true>> { 116 117 /// The source Instruction that is being wrapped. 118 Instruction *Inst = nullptr; 119 /// The values of the operands in the Instruction. 120 SmallVector<Value *, 4> OperVals; 121 /// The legality of the wrapped instruction. This is informed by InstrType, 122 /// and is used when checking when two instructions are considered similar. 123 /// If either instruction is not legal, the instructions are automatically not 124 /// considered similar. 125 bool Legal = false; 126 127 /// This is only relevant if we are wrapping a CmpInst where we needed to 128 /// change the predicate of a compare instruction from a greater than form 129 /// to a less than form. It is None otherwise. 130 Optional<CmpInst::Predicate> RevisedPredicate; 131 132 /// This is only relevant if we are wrapping a CallInst. If we are requiring 133 /// that the function calls have matching names as well as types, and the 134 /// call is not an indirect call, this will hold the name of the function. If 135 /// it is an indirect string, it will be the empty string. However, if this 136 /// requirement is not in place it will be the empty string regardless of the 137 /// function call type. The value held here is used to create the hash of the 138 /// instruction, and check to make sure two instructions are close to one 139 /// another. 140 Optional<std::string> CalleeName; 141 142 /// This structure holds the distances of how far "ahead of" or "behind" the 143 /// target blocks of a branch, or the incoming blocks of a phi nodes are. 144 /// If the value is negative, it means that the block was registered before 145 /// the block of this instruction in terms of blocks in the function. 146 /// Code Example: 147 /// \code 148 /// block_1: 149 /// br i1 %0, label %block_2, label %block_3 150 /// block_2: 151 /// br i1 %1, label %block_1, label %block_2 152 /// block_3: 153 /// br i1 %2, label %block_2, label %block_1 154 /// ; Replacing the labels with relative values, this becomes: 155 /// block_1: 156 /// br i1 %0, distance 1, distance 2 157 /// block_2: 158 /// br i1 %1, distance -1, distance 0 159 /// block_3: 160 /// br i1 %2, distance -1, distance -2 161 /// \endcode 162 /// Taking block_2 as our example, block_1 is "behind" block_2, and block_2 is 163 /// "ahead" of block_2. 164 SmallVector<int, 4> RelativeBlockLocations; 165 166 /// Gather the information that is difficult to gather for an Instruction, or 167 /// is changed. i.e. the operands of an Instruction and the Types of those 168 /// operands. This extra information allows for similarity matching to make 169 /// assertions that allow for more flexibility when checking for whether an 170 /// Instruction performs the same operation. 171 IRInstructionData(Instruction &I, bool Legality, IRInstructionDataList &IDL); 172 IRInstructionData(IRInstructionDataList &IDL); 173 174 /// Fills data stuctures for IRInstructionData when it is constructed from a 175 // reference or a pointer. 176 void initializeInstruction(); 177 178 /// Get the predicate that the compare instruction is using for hashing the 179 /// instruction. the IRInstructionData must be wrapping a CmpInst. 180 CmpInst::Predicate getPredicate() const; 181 182 /// Get the callee name that the call instruction is using for hashing the 183 /// instruction. The IRInstructionData must be wrapping a CallInst. 184 StringRef getCalleeName() const; 185 186 /// A function that swaps the predicates to their less than form if they are 187 /// in a greater than form. Otherwise, the predicate is unchanged. 188 /// 189 /// \param CI - The comparison operation to find a consistent preidcate for. 190 /// \return the consistent comparison predicate. 191 static CmpInst::Predicate predicateForConsistency(CmpInst *CI); 192 193 /// For an IRInstructionData containing a branch, finds the 194 /// relative distances from the source basic block to the target by taking 195 /// the difference of the number assigned to the current basic block and the 196 /// target basic block of the branch. 197 /// 198 /// \param BasicBlockToInteger - The mapping of basic blocks to their location 199 /// in the module. 200 void 201 setBranchSuccessors(DenseMap<BasicBlock *, unsigned> &BasicBlockToInteger); 202 203 /// For an IRInstructionData containing a CallInst, set the function name 204 /// appropriately. This will be an empty string if it is an indirect call, 205 /// or we are not matching by name of the called function. It will be the 206 /// name of the function if \p MatchByName is true and it is not an indirect 207 /// call. We may decide not to match by name in order to expand the 208 /// size of the regions we can match. If a function name has the same type 209 /// signature, but the different name, the region of code is still almost the 210 /// same. Since function names can be treated as constants, the name itself 211 /// could be extrapolated away. However, matching by name provides a 212 /// specificity and more "identical" code than not matching by name. 213 /// 214 /// \param MatchByName - A flag to mark whether we are using the called 215 /// function name as a differentiating parameter. 216 void setCalleeName(bool MatchByName = true); 217 218 /// For an IRInstructionData containing a PHINode, finds the 219 /// relative distances from the incoming basic block to the current block by 220 /// taking the difference of the number assigned to the current basic block 221 /// and the incoming basic block of the branch. 222 /// 223 /// \param BasicBlockToInteger - The mapping of basic blocks to their location 224 /// in the module. 225 void 226 setPHIPredecessors(DenseMap<BasicBlock *, unsigned> &BasicBlockToInteger); 227 228 /// Hashes \p Value based on its opcode, types, and operand types. 229 /// Two IRInstructionData instances produce the same hash when they perform 230 /// the same operation. 231 /// 232 /// As a simple example, consider the following instructions. 233 /// 234 /// \code 235 /// %add1 = add i32 %x1, %y1 236 /// %add2 = add i32 %x2, %y2 237 /// 238 /// %sub = sub i32 %x1, %y1 239 /// 240 /// %add_i64 = add i64 %x2, %y2 241 /// \endcode 242 /// 243 /// Because the first two adds operate the same types, and are performing the 244 /// same action, they will be hashed to the same value. 245 /// 246 /// However, the subtraction instruction is not the same as an addition, and 247 /// will be hashed to a different value. 248 /// 249 /// Finally, the last add has a different type compared to the first two add 250 /// instructions, so it will also be hashed to a different value that any of 251 /// the previous instructions. 252 /// 253 /// \param [in] ID - The IRInstructionData instance to be hashed. 254 /// \returns A hash_value of the IRInstructionData. 255 friend hash_code hash_value(const IRInstructionData &ID) { 256 SmallVector<Type *, 4> OperTypes; 257 for (Value *V : ID.OperVals) 258 OperTypes.push_back(V->getType()); 259 260 if (isa<CmpInst>(ID.Inst)) 261 return llvm::hash_combine( 262 llvm::hash_value(ID.Inst->getOpcode()), 263 llvm::hash_value(ID.Inst->getType()), 264 llvm::hash_value(ID.getPredicate()), 265 llvm::hash_combine_range(OperTypes.begin(), OperTypes.end())); 266 267 if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(ID.Inst)) { 268 // To hash intrinsics, we use the opcode, and types like the other 269 // instructions, but also, the Intrinsic ID, and the Name of the 270 // intrinsic. 271 Intrinsic::ID IntrinsicID = II->getIntrinsicID(); 272 return llvm::hash_combine( 273 llvm::hash_value(ID.Inst->getOpcode()), 274 llvm::hash_value(ID.Inst->getType()), llvm::hash_value(IntrinsicID), 275 llvm::hash_value(*ID.CalleeName), 276 llvm::hash_combine_range(OperTypes.begin(), OperTypes.end())); 277 } 278 279 if (isa<CallInst>(ID.Inst)) { 280 std::string FunctionName = *ID.CalleeName; 281 return llvm::hash_combine( 282 llvm::hash_value(ID.Inst->getOpcode()), 283 llvm::hash_value(ID.Inst->getType()), 284 llvm::hash_value(ID.Inst->getType()), llvm::hash_value(FunctionName), 285 llvm::hash_combine_range(OperTypes.begin(), OperTypes.end())); 286 } 287 288 return llvm::hash_combine( 289 llvm::hash_value(ID.Inst->getOpcode()), 290 llvm::hash_value(ID.Inst->getType()), 291 llvm::hash_combine_range(OperTypes.begin(), OperTypes.end())); 292 } 293 294 IRInstructionDataList *IDL = nullptr; 295 }; 296 297 struct IRInstructionDataList 298 : simple_ilist<IRInstructionData, ilist_sentinel_tracking<true>> {}; 299 300 /// Compare one IRInstructionData class to another IRInstructionData class for 301 /// whether they are performing a the same operation, and can mapped to the 302 /// same value. For regular instructions if the hash value is the same, then 303 /// they will also be close. 304 /// 305 /// \param A - The first IRInstructionData class to compare 306 /// \param B - The second IRInstructionData class to compare 307 /// \returns true if \p A and \p B are similar enough to be mapped to the same 308 /// value. 309 bool isClose(const IRInstructionData &A, const IRInstructionData &B); 310 311 struct IRInstructionDataTraits : DenseMapInfo<IRInstructionData *> { 312 static inline IRInstructionData *getEmptyKey() { return nullptr; } 313 static inline IRInstructionData *getTombstoneKey() { 314 return reinterpret_cast<IRInstructionData *>(-1); 315 } 316 317 static unsigned getHashValue(const IRInstructionData *E) { 318 using llvm::hash_value; 319 assert(E && "IRInstructionData is a nullptr?"); 320 return hash_value(*E); 321 } 322 323 static bool isEqual(const IRInstructionData *LHS, 324 const IRInstructionData *RHS) { 325 if (RHS == getEmptyKey() || RHS == getTombstoneKey() || 326 LHS == getEmptyKey() || LHS == getTombstoneKey()) 327 return LHS == RHS; 328 329 assert(LHS && RHS && "nullptr should have been caught by getEmptyKey?"); 330 return isClose(*LHS, *RHS); 331 } 332 }; 333 334 /// Helper struct for converting the Instructions in a Module into a vector of 335 /// unsigned integers. This vector of unsigned integers can be thought of as a 336 /// "numeric string". This numeric string can then be queried by, for example, 337 /// data structures that find repeated substrings. 338 /// 339 /// This hashing is done per BasicBlock in the module. To hash Instructions 340 /// based off of their operations, each Instruction is wrapped in an 341 /// IRInstructionData struct. The unsigned integer for an IRInstructionData 342 /// depends on: 343 /// - The hash provided by the IRInstructionData. 344 /// - Which member of InstrType the IRInstructionData is classified as. 345 // See InstrType for more details on the possible classifications, and how they 346 // manifest in the numeric string. 347 /// 348 /// The numeric string for an individual BasicBlock is terminated by an unique 349 /// unsigned integer. This prevents data structures which rely on repetition 350 /// from matching across BasicBlocks. (For example, the SuffixTree.) 351 /// As a concrete example, if we have the following two BasicBlocks: 352 /// \code 353 /// bb0: 354 /// %add1 = add i32 %a, %b 355 /// %add2 = add i32 %c, %d 356 /// %add3 = add i64 %e, %f 357 /// bb1: 358 /// %sub = sub i32 %c, %d 359 /// \endcode 360 /// We may hash the Instructions like this (via IRInstructionData): 361 /// \code 362 /// bb0: 363 /// %add1 = add i32 %a, %b ; Hash: 1 364 /// %add2 = add i32 %c, %d; Hash: 1 365 /// %add3 = add i64 %e, %f; Hash: 2 366 /// bb1: 367 /// %sub = sub i32 %c, %d; Hash: 3 368 /// %add4 = add i32 %c, %d ; Hash: 1 369 /// \endcode 370 /// And produce a "numeric string representation" like so: 371 /// 1, 1, 2, unique_integer_1, 3, 1, unique_integer_2 372 /// 373 /// TODO: This is very similar to the MachineOutliner, and should be 374 /// consolidated into the same interface. 375 struct IRInstructionMapper { 376 /// The starting illegal instruction number to map to. 377 /// 378 /// Set to -3 for compatibility with DenseMapInfo<unsigned>. 379 unsigned IllegalInstrNumber = static_cast<unsigned>(-3); 380 381 /// The next available integer to assign to a legal Instruction to. 382 unsigned LegalInstrNumber = 0; 383 384 /// Correspondence from IRInstructionData to unsigned integers. 385 DenseMap<IRInstructionData *, unsigned, IRInstructionDataTraits> 386 InstructionIntegerMap; 387 388 /// A mapping for a basic block in a module to its assigned number/location 389 /// in the module. 390 DenseMap<BasicBlock *, unsigned> BasicBlockToInteger; 391 392 /// Set if we added an illegal number in the previous step. 393 /// Since each illegal number is unique, we only need one of them between 394 /// each range of legal numbers. This lets us make sure we don't add more 395 /// than one illegal number per range. 396 bool AddedIllegalLastTime = false; 397 398 /// Marks whether we found a illegal instruction in the previous step. 399 bool CanCombineWithPrevInstr = false; 400 401 /// Marks whether we have found a set of instructions that is long enough 402 /// to be considered for similarity. 403 bool HaveLegalRange = false; 404 405 /// Marks whether we should use exact function names, as well as types to 406 /// find similarity between calls. 407 bool EnableMatchCallsByName = false; 408 409 /// This allocator pointer is in charge of holding on to the IRInstructionData 410 /// so it is not deallocated until whatever external tool is using it is done 411 /// with the information. 412 SpecificBumpPtrAllocator<IRInstructionData> *InstDataAllocator = nullptr; 413 414 /// This allocator pointer is in charge of creating the IRInstructionDataList 415 /// so it is not deallocated until whatever external tool is using it is done 416 /// with the information. 417 SpecificBumpPtrAllocator<IRInstructionDataList> *IDLAllocator = nullptr; 418 419 /// Get an allocated IRInstructionData struct using the InstDataAllocator. 420 /// 421 /// \param I - The Instruction to wrap with IRInstructionData. 422 /// \param Legality - A boolean value that is true if the instruction is to 423 /// be considered for similarity, and false if not. 424 /// \param IDL - The InstructionDataList that the IRInstructionData is 425 /// inserted into. 426 /// \returns An allocated IRInstructionData struct. 427 IRInstructionData *allocateIRInstructionData(Instruction &I, bool Legality, 428 IRInstructionDataList &IDL); 429 430 /// Get an empty allocated IRInstructionData struct using the 431 /// InstDataAllocator. 432 /// 433 /// \param IDL - The InstructionDataList that the IRInstructionData is 434 /// inserted into. 435 /// \returns An allocated IRInstructionData struct. 436 IRInstructionData *allocateIRInstructionData(IRInstructionDataList &IDL); 437 438 /// Get an allocated IRInstructionDataList object using the IDLAllocator. 439 /// 440 /// \returns An allocated IRInstructionDataList object. 441 IRInstructionDataList *allocateIRInstructionDataList(); 442 443 IRInstructionDataList *IDL = nullptr; 444 445 /// Assigns values to all the basic blocks in function \p F starting from 446 /// integer \p BBNumber. 447 /// 448 /// \param F - The function containing the basic blocks to assign numbers to. 449 /// \param BBNumber - The number to start from. 450 void initializeForBBs(Function &F, unsigned &BBNumber) { 451 for (BasicBlock &BB : F) 452 BasicBlockToInteger.insert(std::make_pair(&BB, BBNumber++)); 453 } 454 455 /// Assigns values to all the basic blocks in Module \p M. 456 /// \param M - The module containing the basic blocks to assign numbers to. 457 void initializeForBBs(Module &M) { 458 unsigned BBNumber = 0; 459 for (Function &F : M) 460 initializeForBBs(F, BBNumber); 461 } 462 463 /// Maps the Instructions in a BasicBlock \p BB to legal or illegal integers 464 /// determined by \p InstrType. Two Instructions are mapped to the same value 465 /// if they are close as defined by the InstructionData class above. 466 /// 467 /// \param [in] BB - The BasicBlock to be mapped to integers. 468 /// \param [in,out] InstrList - Vector of IRInstructionData to append to. 469 /// \param [in,out] IntegerMapping - Vector of unsigned integers to append to. 470 void convertToUnsignedVec(BasicBlock &BB, 471 std::vector<IRInstructionData *> &InstrList, 472 std::vector<unsigned> &IntegerMapping); 473 474 /// Maps an Instruction to a legal integer. 475 /// 476 /// \param [in] It - The Instruction to be mapped to an integer. 477 /// \param [in,out] IntegerMappingForBB - Vector of unsigned integers to 478 /// append to. 479 /// \param [in,out] InstrListForBB - Vector of InstructionData to append to. 480 /// \returns The integer \p It was mapped to. 481 unsigned mapToLegalUnsigned(BasicBlock::iterator &It, 482 std::vector<unsigned> &IntegerMappingForBB, 483 std::vector<IRInstructionData *> &InstrListForBB); 484 485 /// Maps an Instruction to an illegal integer. 486 /// 487 /// \param [in] It - The \p Instruction to be mapped to an integer. 488 /// \param [in,out] IntegerMappingForBB - Vector of unsigned integers to 489 /// append to. 490 /// \param [in,out] InstrListForBB - Vector of IRInstructionData to append to. 491 /// \param End - true if creating a dummy IRInstructionData at the end of a 492 /// basic block. 493 /// \returns The integer \p It was mapped to. 494 unsigned mapToIllegalUnsigned( 495 BasicBlock::iterator &It, std::vector<unsigned> &IntegerMappingForBB, 496 std::vector<IRInstructionData *> &InstrListForBB, bool End = false); 497 498 IRInstructionMapper(SpecificBumpPtrAllocator<IRInstructionData> *IDA, 499 SpecificBumpPtrAllocator<IRInstructionDataList> *IDLA) 500 : InstDataAllocator(IDA), IDLAllocator(IDLA) { 501 // Make sure that the implementation of DenseMapInfo<unsigned> hasn't 502 // changed. 503 assert(DenseMapInfo<unsigned>::getEmptyKey() == static_cast<unsigned>(-1) && 504 "DenseMapInfo<unsigned>'s empty key isn't -1!"); 505 assert(DenseMapInfo<unsigned>::getTombstoneKey() == 506 static_cast<unsigned>(-2) && 507 "DenseMapInfo<unsigned>'s tombstone key isn't -2!"); 508 509 IDL = new (IDLAllocator->Allocate()) 510 IRInstructionDataList(); 511 } 512 513 /// Custom InstVisitor to classify different instructions for whether it can 514 /// be analyzed for similarity. 515 struct InstructionClassification 516 : public InstVisitor<InstructionClassification, InstrType> { 517 InstructionClassification() = default; 518 519 // TODO: Determine a scheme to resolve when the label is similar enough. 520 InstrType visitBranchInst(BranchInst &BI) { 521 if (EnableBranches) 522 return Legal; 523 return Illegal; 524 } 525 InstrType visitPHINode(PHINode &PN) { 526 if (EnableBranches) 527 return Legal; 528 return Illegal; 529 } 530 // TODO: Handle allocas. 531 InstrType visitAllocaInst(AllocaInst &AI) { return Illegal; } 532 // We exclude variable argument instructions since variable arguments 533 // requires extra checking of the argument list. 534 InstrType visitVAArgInst(VAArgInst &VI) { return Illegal; } 535 // We exclude all exception handling cases since they are so context 536 // dependent. 537 InstrType visitLandingPadInst(LandingPadInst &LPI) { return Illegal; } 538 InstrType visitFuncletPadInst(FuncletPadInst &FPI) { return Illegal; } 539 // DebugInfo should be included in the regions, but should not be 540 // analyzed for similarity as it has no bearing on the outcome of the 541 // program. 542 InstrType visitDbgInfoIntrinsic(DbgInfoIntrinsic &DII) { return Invisible; } 543 InstrType visitIntrinsicInst(IntrinsicInst &II) { 544 // These are disabled due to complications in the CodeExtractor when 545 // outlining these instructions. For instance, It is unclear what we 546 // should do when moving only the start or end lifetime instruction into 547 // an outlined function. Also, assume-like intrinsics could be removed 548 // from the region, removing arguments, causing discrepencies in the 549 // number of inputs between different regions. 550 if (II.isAssumeLikeIntrinsic()) 551 return Illegal; 552 return EnableIntrinsics ? Legal : Illegal; 553 } 554 // We only allow call instructions where the function has a name and 555 // is not an indirect call. 556 InstrType visitCallInst(CallInst &CI) { 557 Function *F = CI.getCalledFunction(); 558 bool IsIndirectCall = CI.isIndirectCall(); 559 if (IsIndirectCall && !EnableIndirectCalls) 560 return Illegal; 561 if (!F && !IsIndirectCall) 562 return Illegal; 563 // Functions marked with the swifttailcc and tailcc calling conventions 564 // require special handling when outlining musttail functions. The 565 // calling convention must be passed down to the outlined function as 566 // well. Further, there is special handling for musttail calls as well, 567 // requiring a return call directly after. For now, the outliner does not 568 // support this, so we do not handle matching this case either. 569 if ((CI.getCallingConv() == CallingConv::SwiftTail || 570 CI.getCallingConv() == CallingConv::Tail) && 571 !EnableMustTailCalls) 572 return Illegal; 573 if (CI.isMustTailCall() && !EnableMustTailCalls) 574 return Illegal; 575 return Legal; 576 } 577 // TODO: We do not current handle similarity that changes the control flow. 578 InstrType visitInvokeInst(InvokeInst &II) { return Illegal; } 579 // TODO: We do not current handle similarity that changes the control flow. 580 InstrType visitCallBrInst(CallBrInst &CBI) { return Illegal; } 581 // TODO: Handle interblock similarity. 582 InstrType visitTerminator(Instruction &I) { return Illegal; } 583 InstrType visitInstruction(Instruction &I) { return Legal; } 584 585 // The flag variable that lets the classifier know whether we should 586 // allow branches to be checked for similarity. 587 bool EnableBranches = false; 588 589 // The flag variable that lets the classifier know whether we should 590 // allow indirect calls to be considered legal instructions. 591 bool EnableIndirectCalls = false; 592 593 // Flag that lets the classifier know whether we should allow intrinsics to 594 // be checked for similarity. 595 bool EnableIntrinsics = false; 596 597 // Flag that lets the classifier know whether we should allow tail calls to 598 // be checked for similarity. 599 bool EnableMustTailCalls = false; 600 }; 601 602 /// Maps an Instruction to a member of InstrType. 603 InstructionClassification InstClassifier; 604 }; 605 606 /// This is a class that wraps a range of IRInstructionData from one point to 607 /// another in the vector of IRInstructionData, which is a region of the 608 /// program. It is also responsible for defining the structure within this 609 /// region of instructions. 610 /// 611 /// The structure of a region is defined through a value numbering system 612 /// assigned to each unique value in a region at the creation of the 613 /// IRSimilarityCandidate. 614 /// 615 /// For example, for each Instruction we add a mapping for each new 616 /// value seen in that Instruction. 617 /// IR: Mapping Added: 618 /// %add1 = add i32 %a, c1 %add1 -> 3, %a -> 1, c1 -> 2 619 /// %add2 = add i32 %a, %1 %add2 -> 4 620 /// %add3 = add i32 c2, c1 %add3 -> 6, c2 -> 5 621 /// 622 /// We can compare IRSimilarityCandidates against one another. 623 /// The \ref isSimilar function compares each IRInstructionData against one 624 /// another and if we have the same sequences of IRInstructionData that would 625 /// create the same hash, we have similar IRSimilarityCandidates. 626 /// 627 /// We can also compare the structure of IRSimilarityCandidates. If we can 628 /// create a mapping of registers in the region contained by one 629 /// IRSimilarityCandidate to the region contained by different 630 /// IRSimilarityCandidate, they can be considered structurally similar. 631 /// 632 /// IRSimilarityCandidate1: IRSimilarityCandidate2: 633 /// %add1 = add i32 %a, %b %add1 = add i32 %d, %e 634 /// %add2 = add i32 %a, %c %add2 = add i32 %d, %f 635 /// %add3 = add i32 c1, c2 %add3 = add i32 c3, c4 636 /// 637 /// Can have the following mapping from candidate to candidate of: 638 /// %a -> %d, %b -> %e, %c -> %f, c1 -> c3, c2 -> c4 639 /// and can be considered similar. 640 /// 641 /// IRSimilarityCandidate1: IRSimilarityCandidate2: 642 /// %add1 = add i32 %a, %b %add1 = add i32 %d, c4 643 /// %add2 = add i32 %a, %c %add2 = add i32 %d, %f 644 /// %add3 = add i32 c1, c2 %add3 = add i32 c3, c4 645 /// 646 /// We cannot create the same mapping since the use of c4 is not used in the 647 /// same way as %b or c2. 648 class IRSimilarityCandidate { 649 private: 650 /// The start index of this IRSimilarityCandidate in the instruction list. 651 unsigned StartIdx = 0; 652 653 /// The number of instructions in this IRSimilarityCandidate. 654 unsigned Len = 0; 655 656 /// The first instruction in this IRSimilarityCandidate. 657 IRInstructionData *FirstInst = nullptr; 658 659 /// The last instruction in this IRSimilarityCandidate. 660 IRInstructionData *LastInst = nullptr; 661 662 /// Global Value Numbering structures 663 /// @{ 664 /// Stores the mapping of the value to the number assigned to it in the 665 /// IRSimilarityCandidate. 666 DenseMap<Value *, unsigned> ValueToNumber; 667 /// Stores the mapping of the number to the value assigned this number. 668 DenseMap<unsigned, Value *> NumberToValue; 669 /// Stores the mapping of a value's number to canonical numbering in the 670 /// candidate's respective similarity group. 671 DenseMap<unsigned, unsigned> NumberToCanonNum; 672 /// Stores the mapping of canonical number in the candidate's respective 673 /// similarity group to a value number. 674 DenseMap<unsigned, unsigned> CanonNumToNumber; 675 /// @} 676 677 public: 678 /// \param StartIdx - The starting location of the region. 679 /// \param Len - The length of the region. 680 /// \param FirstInstIt - The starting IRInstructionData of the region. 681 /// \param LastInstIt - The ending IRInstructionData of the region. 682 IRSimilarityCandidate(unsigned StartIdx, unsigned Len, 683 IRInstructionData *FirstInstIt, 684 IRInstructionData *LastInstIt); 685 686 /// \param A - The first IRInstructionCandidate to compare. 687 /// \param B - The second IRInstructionCandidate to compare. 688 /// \returns True when every IRInstructionData in \p A is similar to every 689 /// IRInstructionData in \p B. 690 static bool isSimilar(const IRSimilarityCandidate &A, 691 const IRSimilarityCandidate &B); 692 693 /// \param [in] A - The first IRInstructionCandidate to compare. 694 /// \param [in] B - The second IRInstructionCandidate to compare. 695 /// \returns True when every IRInstructionData in \p A is structurally similar 696 /// to \p B. 697 static bool compareStructure(const IRSimilarityCandidate &A, 698 const IRSimilarityCandidate &B); 699 700 /// \param [in] A - The first IRInstructionCandidate to compare. 701 /// \param [in] B - The second IRInstructionCandidate to compare. 702 /// \param [in,out] ValueNumberMappingA - A mapping of value numbers from 703 /// candidate \p A to candidate \B. 704 /// \param [in,out] ValueNumberMappingB - A mapping of value numbers from 705 /// candidate \p B to candidate \A. 706 /// \returns True when every IRInstructionData in \p A is structurally similar 707 /// to \p B. 708 static bool 709 compareStructure(const IRSimilarityCandidate &A, 710 const IRSimilarityCandidate &B, 711 DenseMap<unsigned, DenseSet<unsigned>> &ValueNumberMappingA, 712 DenseMap<unsigned, DenseSet<unsigned>> &ValueNumberMappingB); 713 714 struct OperandMapping { 715 /// The IRSimilarityCandidate that holds the instruction the OperVals were 716 /// pulled from. 717 const IRSimilarityCandidate &IRSC; 718 719 /// The operand values to be analyzed. 720 ArrayRef<Value *> &OperVals; 721 722 /// The current mapping of global value numbers from one IRSimilarityCandidate 723 /// to another IRSimilarityCandidate. 724 DenseMap<unsigned, DenseSet<unsigned>> &ValueNumberMapping; 725 }; 726 727 /// A helper struct to hold the candidate, for a branch instruction, the 728 /// relative location of a label, and the label itself. This is mostly to 729 /// group the values together before passing them as a bundle to a function. 730 struct RelativeLocMapping { 731 /// The IRSimilarityCandidate that holds the instruction the relative 732 /// location was pulled from. 733 const IRSimilarityCandidate &IRSC; 734 735 /// The relative location to be analyzed. 736 int RelativeLocation; 737 738 /// The corresponding value. 739 Value *OperVal; 740 }; 741 742 /// Compare the operands in \p A and \p B and check that the current mapping 743 /// of global value numbers from \p A to \p B and \p B to \A is consistent. 744 /// 745 /// \param A - The first IRInstructionCandidate, operand values, and current 746 /// operand mappings to compare. 747 /// \param B - The second IRInstructionCandidate, operand values, and current 748 /// operand mappings to compare. 749 /// \returns true if the IRSimilarityCandidates operands are compatible. 750 static bool compareNonCommutativeOperandMapping(OperandMapping A, 751 OperandMapping B); 752 753 /// Compare the operands in \p A and \p B and check that the current mapping 754 /// of global value numbers from \p A to \p B and \p B to \A is consistent 755 /// given that the operands are commutative. 756 /// 757 /// \param A - The first IRInstructionCandidate, operand values, and current 758 /// operand mappings to compare. 759 /// \param B - The second IRInstructionCandidate, operand values, and current 760 /// operand mappings to compare. 761 /// \returns true if the IRSimilarityCandidates operands are compatible. 762 static bool compareCommutativeOperandMapping(OperandMapping A, 763 OperandMapping B); 764 765 /// Compare the relative locations in \p A and \p B and check that the 766 /// distances match if both locations are contained in the region, and that 767 /// the branches both point outside the region if they do not. 768 /// Example Region: 769 /// \code 770 /// entry: 771 /// br i1 %0, label %block_1, label %block_3 772 /// block_0: 773 /// br i1 %0, label %block_1, label %block_2 774 /// block_1: 775 /// br i1 %0, label %block_2, label %block_3 776 /// block_2: 777 /// br i1 %1, label %block_1, label %block_4 778 /// block_3: 779 /// br i1 %2, label %block_2, label %block_5 780 /// \endcode 781 /// If we compare the branches in block_0 and block_1 the relative values are 782 /// 1 and 2 for both, so we consider this a match. 783 /// 784 /// If we compare the branches in entry and block_0 the relative values are 785 /// 2 and 3, and 1 and 2 respectively. Since these are not the same we do not 786 /// consider them a match. 787 /// 788 /// If we compare the branches in block_1 and block_2 the relative values are 789 /// 1 and 2, and -1 and None respectively. As a result we do not consider 790 /// these to be the same 791 /// 792 /// If we compare the branches in block_2 and block_3 the relative values are 793 /// -1 and None for both. We do consider these to be a match. 794 /// 795 /// \param A - The first IRInstructionCandidate, relative location value, 796 /// and incoming block. 797 /// \param B - The second IRInstructionCandidate, relative location value, 798 /// and incoming block. 799 /// \returns true if the relative locations match. 800 static bool checkRelativeLocations(RelativeLocMapping A, 801 RelativeLocMapping B); 802 803 /// Create a mapping from the value numbering to a different separate set of 804 /// numbers. This will serve as a guide for relating one candidate to another. 805 /// The canonical number gives use the ability identify which global value 806 /// number in one candidate relates to the global value number in the other. 807 /// 808 /// \param [in, out] CurrCand - The IRSimilarityCandidate to create a 809 /// canonical numbering for. 810 static void createCanonicalMappingFor(IRSimilarityCandidate &CurrCand); 811 812 /// Create a mapping for the value numbering of the calling 813 /// IRSimilarityCandidate, to a different separate set of numbers, based on 814 /// the canonical ordering in \p SourceCand. These are defined based on the 815 /// found mappings in \p ToSourceMapping and \p FromSourceMapping. Both of 816 /// these relationships should have the same information, just in opposite 817 /// directions. 818 /// 819 /// \param [in, out] SourceCand - The IRSimilarityCandidate to create a 820 /// canonical numbering from. 821 /// \param ToSourceMapping - The mapping of value numbers from this candidate 822 /// to \p SourceCand. 823 /// \param FromSourceMapping - The mapping of value numbers from \p SoureCand 824 /// to this candidate. 825 void createCanonicalRelationFrom( 826 IRSimilarityCandidate &SourceCand, 827 DenseMap<unsigned, DenseSet<unsigned>> &ToSourceMapping, 828 DenseMap<unsigned, DenseSet<unsigned>> &FromSourceMapping); 829 830 /// \param [in,out] BBSet - The set to track the basic blocks. 831 void getBasicBlocks(DenseSet<BasicBlock *> &BBSet) const { 832 for (IRInstructionData &ID : *this) { 833 BasicBlock *BB = ID.Inst->getParent(); 834 BBSet.insert(BB); 835 } 836 } 837 838 /// \param [in,out] BBSet - The set to track the basic blocks. 839 /// \param [in,out] BBList - A list in order of use to track the basic blocks. 840 void getBasicBlocks(DenseSet<BasicBlock *> &BBSet, 841 SmallVector<BasicBlock *> &BBList) const { 842 for (IRInstructionData &ID : *this) { 843 BasicBlock *BB = ID.Inst->getParent(); 844 if (BBSet.insert(BB).second) 845 BBList.push_back(BB); 846 } 847 } 848 849 /// Compare the start and end indices of the two IRSimilarityCandidates for 850 /// whether they overlap. If the start instruction of one 851 /// IRSimilarityCandidate is less than the end instruction of the other, and 852 /// the start instruction of one is greater than the start instruction of the 853 /// other, they overlap. 854 /// 855 /// \returns true if the IRSimilarityCandidates do not have overlapping 856 /// instructions. 857 static bool overlap(const IRSimilarityCandidate &A, 858 const IRSimilarityCandidate &B); 859 860 /// \returns the number of instructions in this Candidate. 861 unsigned getLength() const { return Len; } 862 863 /// \returns the start index of this IRSimilarityCandidate. 864 unsigned getStartIdx() const { return StartIdx; } 865 866 /// \returns the end index of this IRSimilarityCandidate. 867 unsigned getEndIdx() const { return StartIdx + Len - 1; } 868 869 /// \returns The first IRInstructionData. 870 IRInstructionData *front() const { return FirstInst; } 871 /// \returns The last IRInstructionData. 872 IRInstructionData *back() const { return LastInst; } 873 874 /// \returns The first Instruction. 875 Instruction *frontInstruction() { return FirstInst->Inst; } 876 /// \returns The last Instruction 877 Instruction *backInstruction() { return LastInst->Inst; } 878 879 /// \returns The BasicBlock the IRSimilarityCandidate starts in. 880 BasicBlock *getStartBB() { return FirstInst->Inst->getParent(); } 881 /// \returns The BasicBlock the IRSimilarityCandidate ends in. 882 BasicBlock *getEndBB() { return LastInst->Inst->getParent(); } 883 884 /// \returns The Function that the IRSimilarityCandidate is located in. 885 Function *getFunction() { return getStartBB()->getParent(); } 886 887 /// Finds the positive number associated with \p V if it has been mapped. 888 /// \param [in] V - the Value to find. 889 /// \returns The positive number corresponding to the value. 890 /// \returns None if not present. 891 Optional<unsigned> getGVN(Value *V) { 892 assert(V != nullptr && "Value is a nullptr?"); 893 DenseMap<Value *, unsigned>::iterator VNIt = ValueToNumber.find(V); 894 if (VNIt == ValueToNumber.end()) 895 return None; 896 return VNIt->second; 897 } 898 899 /// Finds the Value associate with \p Num if it exists. 900 /// \param [in] Num - the number to find. 901 /// \returns The Value associated with the number. 902 /// \returns None if not present. 903 Optional<Value *> fromGVN(unsigned Num) { 904 DenseMap<unsigned, Value *>::iterator VNIt = NumberToValue.find(Num); 905 if (VNIt == NumberToValue.end()) 906 return None; 907 assert(VNIt->second != nullptr && "Found value is a nullptr!"); 908 return VNIt->second; 909 } 910 911 /// Find the canonical number from the global value number \p N stored in the 912 /// candidate. 913 /// 914 /// \param N - The global value number to find the canonical number for. 915 /// \returns An optional containing the value, and None if it could not be 916 /// found. 917 Optional<unsigned> getCanonicalNum(unsigned N) { 918 DenseMap<unsigned, unsigned>::iterator NCIt = NumberToCanonNum.find(N); 919 if (NCIt == NumberToCanonNum.end()) 920 return None; 921 return NCIt->second; 922 } 923 924 /// Find the global value number from the canonical number \p N stored in the 925 /// candidate. 926 /// 927 /// \param N - The canonical number to find the global vlaue number for. 928 /// \returns An optional containing the value, and None if it could not be 929 /// found. 930 Optional<unsigned> fromCanonicalNum(unsigned N) { 931 DenseMap<unsigned, unsigned>::iterator CNIt = CanonNumToNumber.find(N); 932 if (CNIt == CanonNumToNumber.end()) 933 return None; 934 return CNIt->second; 935 } 936 937 /// \param RHS -The IRSimilarityCandidate to compare against 938 /// \returns true if the IRSimilarityCandidate is occurs after the 939 /// IRSimilarityCandidate in the program. 940 bool operator<(const IRSimilarityCandidate &RHS) const { 941 return getStartIdx() > RHS.getStartIdx(); 942 } 943 944 using iterator = IRInstructionDataList::iterator; 945 iterator begin() const { return iterator(front()); } 946 iterator end() const { return std::next(iterator(back())); } 947 }; 948 949 typedef DenseMap<IRSimilarityCandidate *, 950 DenseMap<unsigned, DenseSet<unsigned>>> 951 CandidateGVNMapping; 952 typedef std::vector<IRSimilarityCandidate> SimilarityGroup; 953 typedef std::vector<SimilarityGroup> SimilarityGroupList; 954 955 /// This class puts all the pieces of the IRInstructionData, 956 /// IRInstructionMapper, IRSimilarityCandidate together. 957 /// 958 /// It first feeds the Module or vector of Modules into the IRInstructionMapper, 959 /// and puts all the mapped instructions into a single long list of 960 /// IRInstructionData. 961 /// 962 /// The list of unsigned integers is given to the Suffix Tree or similar data 963 /// structure to find repeated subsequences. We construct an 964 /// IRSimilarityCandidate for each instance of the subsequence. We compare them 965 /// against one another since These repeated subsequences can have different 966 /// structure. For each different kind of structure found, we create a 967 /// similarity group. 968 /// 969 /// If we had four IRSimilarityCandidates A, B, C, and D where A, B and D are 970 /// structurally similar to one another, while C is different we would have two 971 /// SimilarityGroups: 972 /// 973 /// SimilarityGroup 1: SimilarityGroup 2 974 /// A, B, D C 975 /// 976 /// A list of the different similarity groups is then returned after 977 /// analyzing the module. 978 class IRSimilarityIdentifier { 979 public: 980 IRSimilarityIdentifier(bool MatchBranches = true, 981 bool MatchIndirectCalls = true, 982 bool MatchCallsWithName = false, 983 bool MatchIntrinsics = true, 984 bool MatchMustTailCalls = true) 985 : Mapper(&InstDataAllocator, &InstDataListAllocator), 986 EnableBranches(MatchBranches), EnableIndirectCalls(MatchIndirectCalls), 987 EnableMatchingCallsByName(MatchCallsWithName), 988 EnableIntrinsics(MatchIntrinsics), 989 EnableMustTailCalls(MatchMustTailCalls) {} 990 991 private: 992 /// Map the instructions in the module to unsigned integers, using mapping 993 /// already present in the Mapper if possible. 994 /// 995 /// \param [in] M Module - To map to integers. 996 /// \param [in,out] InstrList - The vector to append IRInstructionData to. 997 /// \param [in,out] IntegerMapping - The vector to append integers to. 998 void populateMapper(Module &M, std::vector<IRInstructionData *> &InstrList, 999 std::vector<unsigned> &IntegerMapping); 1000 1001 /// Map the instructions in the modules vector to unsigned integers, using 1002 /// mapping already present in the mapper if possible. 1003 /// 1004 /// \param [in] Modules - The list of modules to use to populate the mapper 1005 /// \param [in,out] InstrList - The vector to append IRInstructionData to. 1006 /// \param [in,out] IntegerMapping - The vector to append integers to. 1007 void populateMapper(ArrayRef<std::unique_ptr<Module>> &Modules, 1008 std::vector<IRInstructionData *> &InstrList, 1009 std::vector<unsigned> &IntegerMapping); 1010 1011 /// Find the similarity candidates in \p InstrList and corresponding 1012 /// \p UnsignedVec 1013 /// 1014 /// \param [in,out] InstrList - The vector to append IRInstructionData to. 1015 /// \param [in,out] IntegerMapping - The vector to append integers to. 1016 /// candidates found in the program. 1017 void findCandidates(std::vector<IRInstructionData *> &InstrList, 1018 std::vector<unsigned> &IntegerMapping); 1019 1020 public: 1021 // Find the IRSimilarityCandidates in the \p Modules and group by structural 1022 // similarity in a SimilarityGroup, each group is returned in a 1023 // SimilarityGroupList. 1024 // 1025 // \param [in] Modules - the modules to analyze. 1026 // \returns The groups of similarity ranges found in the modules. 1027 SimilarityGroupList & 1028 findSimilarity(ArrayRef<std::unique_ptr<Module>> Modules); 1029 1030 // Find the IRSimilarityCandidates in the given Module grouped by structural 1031 // similarity in a SimilarityGroup, contained inside a SimilarityGroupList. 1032 // 1033 // \param [in] M - the module to analyze. 1034 // \returns The groups of similarity ranges found in the module. 1035 SimilarityGroupList &findSimilarity(Module &M); 1036 1037 // Clears \ref SimilarityCandidates if it is already filled by a previous run. 1038 void resetSimilarityCandidates() { 1039 // If we've already analyzed a Module or set of Modules, so we must clear 1040 // the SimilarityCandidates to make sure we do not have only old values 1041 // hanging around. 1042 if (SimilarityCandidates) 1043 SimilarityCandidates->clear(); 1044 else 1045 SimilarityCandidates = SimilarityGroupList(); 1046 } 1047 1048 // \returns The groups of similarity ranges found in the most recently passed 1049 // set of modules. 1050 Optional<SimilarityGroupList> &getSimilarity() { 1051 return SimilarityCandidates; 1052 } 1053 1054 private: 1055 /// The allocator for IRInstructionData. 1056 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator; 1057 1058 /// The allocator for IRInstructionDataLists. 1059 SpecificBumpPtrAllocator<IRInstructionDataList> InstDataListAllocator; 1060 1061 /// Map Instructions to unsigned integers and wraps the Instruction in an 1062 /// instance of IRInstructionData. 1063 IRInstructionMapper Mapper; 1064 1065 /// The flag variable that marks whether we should check branches for 1066 /// similarity, or only look within basic blocks. 1067 bool EnableBranches = true; 1068 1069 /// The flag variable that marks whether we allow indirect calls to be checked 1070 /// for similarity, or exclude them as a legal instruction. 1071 bool EnableIndirectCalls = true; 1072 1073 /// The flag variable that marks whether we allow calls to be marked as 1074 /// similar if they do not have the same name, only the same calling 1075 /// convention, attributes and type signature. 1076 bool EnableMatchingCallsByName = true; 1077 1078 /// The flag variable that marks whether we should check intrinsics for 1079 /// similarity. 1080 bool EnableIntrinsics = true; 1081 1082 // The flag variable that marks whether we should allow tailcalls 1083 // to be checked for similarity. 1084 bool EnableMustTailCalls = false; 1085 1086 /// The SimilarityGroups found with the most recent run of \ref 1087 /// findSimilarity. None if there is no recent run. 1088 Optional<SimilarityGroupList> SimilarityCandidates; 1089 }; 1090 1091 } // end namespace IRSimilarity 1092 1093 /// An analysis pass based on legacy pass manager that runs and returns 1094 /// IRSimilarityIdentifier run on the Module. 1095 class IRSimilarityIdentifierWrapperPass : public ModulePass { 1096 std::unique_ptr<IRSimilarity::IRSimilarityIdentifier> IRSI; 1097 1098 public: 1099 static char ID; 1100 IRSimilarityIdentifierWrapperPass(); 1101 1102 IRSimilarity::IRSimilarityIdentifier &getIRSI() { return *IRSI; } 1103 const IRSimilarity::IRSimilarityIdentifier &getIRSI() const { return *IRSI; } 1104 1105 bool doInitialization(Module &M) override; 1106 bool doFinalization(Module &M) override; 1107 bool runOnModule(Module &M) override; 1108 void getAnalysisUsage(AnalysisUsage &AU) const override { 1109 AU.setPreservesAll(); 1110 } 1111 }; 1112 1113 /// An analysis pass that runs and returns the IRSimilarityIdentifier run on the 1114 /// Module. 1115 class IRSimilarityAnalysis : public AnalysisInfoMixin<IRSimilarityAnalysis> { 1116 public: 1117 typedef IRSimilarity::IRSimilarityIdentifier Result; 1118 1119 Result run(Module &M, ModuleAnalysisManager &); 1120 1121 private: 1122 friend AnalysisInfoMixin<IRSimilarityAnalysis>; 1123 static AnalysisKey Key; 1124 }; 1125 1126 /// Printer pass that uses \c IRSimilarityAnalysis. 1127 class IRSimilarityAnalysisPrinterPass 1128 : public PassInfoMixin<IRSimilarityAnalysisPrinterPass> { 1129 raw_ostream &OS; 1130 1131 public: 1132 explicit IRSimilarityAnalysisPrinterPass(raw_ostream &OS) : OS(OS) {} 1133 PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM); 1134 }; 1135 1136 } // end namespace llvm 1137 1138 #endif // LLVM_ANALYSIS_IRSIMILARITYIDENTIFIER_H 1139