comparison lib/Transforms/Utils/FunctionComparator.cpp @ 148:63bd29f05246

merged
author Shinji KONO <kono@ie.u-ryukyu.ac.jp>
date Wed, 14 Aug 2019 19:46:37 +0900 (2019-08-14)
parents c4cc77a799c9 c2174574ed3a
children
comparison
equal deleted inserted replaced
146:3fc4d5c3e21e 148:63bd29f05246
1 //===- FunctionComparator.h - Function Comparator -------------------------===// 1 //===- FunctionComparator.h - Function Comparator -------------------------===//
2 // 2 //
3 // The LLVM Compiler Infrastructure 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // 4 // See https://llvm.org/LICENSE.txt for license information.
5 // This file is distributed under the University of Illinois Open Source 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 // License. See LICENSE.TXT for details.
7 // 6 //
8 //===----------------------------------------------------------------------===// 7 //===----------------------------------------------------------------------===//
9 // 8 //
10 // This file implements the FunctionComparator and GlobalNumberState classes 9 // This file implements the FunctionComparator and GlobalNumberState classes
11 // which are used by the MergeFunctions pass for comparing functions. 10 // which are used by the MergeFunctions pass for comparing functions.
16 #include "llvm/ADT/APFloat.h" 15 #include "llvm/ADT/APFloat.h"
17 #include "llvm/ADT/APInt.h" 16 #include "llvm/ADT/APInt.h"
18 #include "llvm/ADT/ArrayRef.h" 17 #include "llvm/ADT/ArrayRef.h"
19 #include "llvm/ADT/Hashing.h" 18 #include "llvm/ADT/Hashing.h"
20 #include "llvm/ADT/SmallPtrSet.h" 19 #include "llvm/ADT/SmallPtrSet.h"
21 #include "llvm/ADT/SmallSet.h"
22 #include "llvm/ADT/SmallVector.h" 20 #include "llvm/ADT/SmallVector.h"
23 #include "llvm/IR/Attributes.h" 21 #include "llvm/IR/Attributes.h"
24 #include "llvm/IR/BasicBlock.h" 22 #include "llvm/IR/BasicBlock.h"
25 #include "llvm/IR/CallSite.h" 23 #include "llvm/IR/CallSite.h"
26 #include "llvm/IR/Constant.h" 24 #include "llvm/IR/Constant.h"
113 AttributeSet::iterator LI = LAS.begin(), LE = LAS.end(); 111 AttributeSet::iterator LI = LAS.begin(), LE = LAS.end();
114 AttributeSet::iterator RI = RAS.begin(), RE = RAS.end(); 112 AttributeSet::iterator RI = RAS.begin(), RE = RAS.end();
115 for (; LI != LE && RI != RE; ++LI, ++RI) { 113 for (; LI != LE && RI != RE; ++LI, ++RI) {
116 Attribute LA = *LI; 114 Attribute LA = *LI;
117 Attribute RA = *RI; 115 Attribute RA = *RI;
116 if (LA.isTypeAttribute() && RA.isTypeAttribute()) {
117 if (LA.getKindAsEnum() != RA.getKindAsEnum())
118 return cmpNumbers(LA.getKindAsEnum(), RA.getKindAsEnum());
119
120 Type *TyL = LA.getValueAsType();
121 Type *TyR = RA.getValueAsType();
122 if (TyL && TyR)
123 return cmpTypes(TyL, TyR);
124
125 // Two pointers, at least one null, so the comparison result is
126 // independent of the value of a real pointer.
127 return cmpNumbers((uint64_t)TyL, (uint64_t)TyR);
128 }
118 if (LA < RA) 129 if (LA < RA)
119 return -1; 130 return -1;
120 if (RA < LA) 131 if (RA < LA)
121 return 1; 132 return 1;
122 } 133 }
375 // context of their respective functions. 386 // context of their respective functions.
376 return cmpValues(LBA->getBasicBlock(), RBA->getBasicBlock()); 387 return cmpValues(LBA->getBasicBlock(), RBA->getBasicBlock());
377 } 388 }
378 } 389 }
379 default: // Unknown constant, abort. 390 default: // Unknown constant, abort.
380 DEBUG(dbgs() << "Looking at valueID " << L->getValueID() << "\n"); 391 LLVM_DEBUG(dbgs() << "Looking at valueID " << L->getValueID() << "\n");
381 llvm_unreachable("Constant ValueID not recognized."); 392 llvm_unreachable("Constant ValueID not recognized.");
382 return -1; 393 return -1;
383 } 394 }
384 } 395 }
385 396
409 return Res; 420 return Res;
410 421
411 switch (TyL->getTypeID()) { 422 switch (TyL->getTypeID()) {
412 default: 423 default:
413 llvm_unreachable("Unknown type!"); 424 llvm_unreachable("Unknown type!");
414 // Fall through in Release mode.
415 LLVM_FALLTHROUGH;
416 case Type::IntegerTyID: 425 case Type::IntegerTyID:
417 return cmpNumbers(cast<IntegerType>(TyL)->getBitWidth(), 426 return cmpNumbers(cast<IntegerType>(TyL)->getBitWidth(),
418 cast<IntegerType>(TyR)->getBitWidth()); 427 cast<IntegerType>(TyR)->getBitWidth());
419 // TyL == TyR would have returned true earlier, because types are uniqued. 428 // TyL == TyR would have returned true earlier, because types are uniqued.
420 case Type::VoidTyID: 429 case Type::VoidTyID:
561 return cmpNumbers(SI->getSyncScopeID(), 570 return cmpNumbers(SI->getSyncScopeID(),
562 cast<StoreInst>(R)->getSyncScopeID()); 571 cast<StoreInst>(R)->getSyncScopeID());
563 } 572 }
564 if (const CmpInst *CI = dyn_cast<CmpInst>(L)) 573 if (const CmpInst *CI = dyn_cast<CmpInst>(L))
565 return cmpNumbers(CI->getPredicate(), cast<CmpInst>(R)->getPredicate()); 574 return cmpNumbers(CI->getPredicate(), cast<CmpInst>(R)->getPredicate());
566 if (const CallInst *CI = dyn_cast<CallInst>(L)) { 575 if (auto CSL = CallSite(const_cast<Instruction *>(L))) {
567 if (int Res = cmpNumbers(CI->getCallingConv(), 576 auto CSR = CallSite(const_cast<Instruction *>(R));
568 cast<CallInst>(R)->getCallingConv())) 577 if (int Res = cmpNumbers(CSL.getCallingConv(), CSR.getCallingConv()))
569 return Res; 578 return Res;
570 if (int Res = 579 if (int Res = cmpAttrs(CSL.getAttributes(), CSR.getAttributes()))
571 cmpAttrs(CI->getAttributes(), cast<CallInst>(R)->getAttributes())) 580 return Res;
572 return Res; 581 if (int Res = cmpOperandBundlesSchema(L, R))
573 if (int Res = cmpOperandBundlesSchema(CI, R)) 582 return Res;
574 return Res; 583 if (const CallInst *CI = dyn_cast<CallInst>(L))
575 return cmpRangeMetadata( 584 if (int Res = cmpNumbers(CI->getTailCallKind(),
576 CI->getMetadata(LLVMContext::MD_range), 585 cast<CallInst>(R)->getTailCallKind()))
577 cast<CallInst>(R)->getMetadata(LLVMContext::MD_range)); 586 return Res;
578 } 587 return cmpRangeMetadata(L->getMetadata(LLVMContext::MD_range),
579 if (const InvokeInst *II = dyn_cast<InvokeInst>(L)) { 588 R->getMetadata(LLVMContext::MD_range));
580 if (int Res = cmpNumbers(II->getCallingConv(),
581 cast<InvokeInst>(R)->getCallingConv()))
582 return Res;
583 if (int Res =
584 cmpAttrs(II->getAttributes(), cast<InvokeInst>(R)->getAttributes()))
585 return Res;
586 if (int Res = cmpOperandBundlesSchema(II, R))
587 return Res;
588 return cmpRangeMetadata(
589 II->getMetadata(LLVMContext::MD_range),
590 cast<InvokeInst>(R)->getMetadata(LLVMContext::MD_range));
591 } 589 }
592 if (const InsertValueInst *IVI = dyn_cast<InsertValueInst>(L)) { 590 if (const InsertValueInst *IVI = dyn_cast<InsertValueInst>(L)) {
593 ArrayRef<unsigned> LIndices = IVI->getIndices(); 591 ArrayRef<unsigned> LIndices = IVI->getIndices();
594 ArrayRef<unsigned> RIndices = cast<InsertValueInst>(R)->getIndices(); 592 ArrayRef<unsigned> RIndices = cast<InsertValueInst>(R)->getIndices();
595 if (int Res = cmpNumbers(LIndices.size(), RIndices.size())) 593 if (int Res = cmpNumbers(LIndices.size(), RIndices.size()))
711 return Res; 709 return Res;
712 if (int Res = cmpNumbers(L->isAlignStack(), R->isAlignStack())) 710 if (int Res = cmpNumbers(L->isAlignStack(), R->isAlignStack()))
713 return Res; 711 return Res;
714 if (int Res = cmpNumbers(L->getDialect(), R->getDialect())) 712 if (int Res = cmpNumbers(L->getDialect(), R->getDialect()))
715 return Res; 713 return Res;
716 llvm_unreachable("InlineAsm blocks were not uniqued."); 714 assert(L->getFunctionType() != R->getFunctionType());
717 return 0; 715 return 0;
718 } 716 }
719 717
720 /// Compare two values used by the two functions under pair-wise comparison. If 718 /// Compare two values used by the two functions under pair-wise comparison. If
721 /// this is the first time the values are seen, they're added to the mapping so 719 /// this is the first time the values are seen, they're added to the mapping so
869 return Res; 867 return Res;
870 868
871 if (int Res = cmpBasicBlocks(BBL, BBR)) 869 if (int Res = cmpBasicBlocks(BBL, BBR))
872 return Res; 870 return Res;
873 871
874 const TerminatorInst *TermL = BBL->getTerminator(); 872 const Instruction *TermL = BBL->getTerminator();
875 const TerminatorInst *TermR = BBR->getTerminator(); 873 const Instruction *TermR = BBR->getTerminator();
876 874
877 assert(TermL->getNumSuccessors() == TermR->getNumSuccessors()); 875 assert(TermL->getNumSuccessors() == TermR->getNumSuccessors());
878 for (unsigned i = 0, e = TermL->getNumSuccessors(); i != e; ++i) { 876 for (unsigned i = 0, e = TermL->getNumSuccessors(); i != e; ++i) {
879 if (!VisitedBBs.insert(TermL->getSuccessor(i)).second) 877 if (!VisitedBBs.insert(TermL->getSuccessor(i)).second)
880 continue; 878 continue;
926 HashAccumulator64 H; 924 HashAccumulator64 H;
927 H.add(F.isVarArg()); 925 H.add(F.isVarArg());
928 H.add(F.arg_size()); 926 H.add(F.arg_size());
929 927
930 SmallVector<const BasicBlock *, 8> BBs; 928 SmallVector<const BasicBlock *, 8> BBs;
931 SmallSet<const BasicBlock *, 16> VisitedBBs; 929 SmallPtrSet<const BasicBlock *, 16> VisitedBBs;
932 930
933 // Walk the blocks in the same order as FunctionComparator::cmpBasicBlocks(), 931 // Walk the blocks in the same order as FunctionComparator::cmpBasicBlocks(),
934 // accumulating the hash of the function "structure." (BB and opcode sequence) 932 // accumulating the hash of the function "structure." (BB and opcode sequence)
935 BBs.push_back(&F.getEntryBlock()); 933 BBs.push_back(&F.getEntryBlock());
936 VisitedBBs.insert(BBs[0]); 934 VisitedBBs.insert(BBs[0]);
940 // opcodes into BBs wouldn't affect the hash, only the order of the opcodes 938 // opcodes into BBs wouldn't affect the hash, only the order of the opcodes
941 H.add(45798); 939 H.add(45798);
942 for (auto &Inst : *BB) { 940 for (auto &Inst : *BB) {
943 H.add(Inst.getOpcode()); 941 H.add(Inst.getOpcode());
944 } 942 }
945 const TerminatorInst *Term = BB->getTerminator(); 943 const Instruction *Term = BB->getTerminator();
946 for (unsigned i = 0, e = Term->getNumSuccessors(); i != e; ++i) { 944 for (unsigned i = 0, e = Term->getNumSuccessors(); i != e; ++i) {
947 if (!VisitedBBs.insert(Term->getSuccessor(i)).second) 945 if (!VisitedBBs.insert(Term->getSuccessor(i)).second)
948 continue; 946 continue;
949 BBs.push_back(Term->getSuccessor(i)); 947 BBs.push_back(Term->getSuccessor(i));
950 } 948 }