Index: llvm/include/llvm/Analysis/IRSimilarityIdentifier.h =================================================================== --- llvm/include/llvm/Analysis/IRSimilarityIdentifier.h +++ llvm/include/llvm/Analysis/IRSimilarityIdentifier.h @@ -150,6 +150,9 @@ void setBranchSuccessors(DenseMap &BasicBlockToInteger); + void + setPHIPredecessors(DenseMap &BasicBlockToInteger); + /// Hashes \p Value based on its opcode, types, and operand types. /// Two IRInstructionData instances produce the same hash when they perform /// the same operation. @@ -411,7 +414,7 @@ return Illegal; } // TODO: Determine a scheme to resolve when the labels are similar enough. - InstrType visitPHINode(PHINode &PN) { return Illegal; } + InstrType visitPHINode(PHINode &PN) { return Legal; } // TODO: Handle allocas. InstrType visitAllocaInst(AllocaInst &AI) { return Illegal; } // We exclude variable argument instructions since variable arguments Index: llvm/lib/Analysis/IRSimilarityIdentifier.cpp =================================================================== --- llvm/lib/Analysis/IRSimilarityIdentifier.cpp +++ llvm/lib/Analysis/IRSimilarityIdentifier.cpp @@ -77,6 +77,31 @@ } } +void IRInstructionData::setPHIPredecessors( + DenseMap &BasicBlockToInteger) { + assert(isa(Inst) && "Instruction must be phi node"); + + PHINode *PN = cast(Inst); + DenseMap::iterator BBNumIt; + + BBNumIt = BasicBlockToInteger.find(PN->getParent()); + assert(BBNumIt != BasicBlockToInteger.end() && + "Could not find location for BasicBlock!"); + + int CurrentBlockNumber = static_cast(BBNumIt->second); + + for (unsigned Idx = 0; Idx < PN->getNumIncomingValues(); Idx++) { + BasicBlock *Incoming = PN->getIncomingBlock(Idx); + BBNumIt = BasicBlockToInteger.find(Incoming); + assert(BBNumIt != BasicBlockToInteger.end() && + "Could not find number for BasicBlock!"); + int OtherBlockNumber = static_cast(BBNumIt->second); + + int Relative = OtherBlockNumber - CurrentBlockNumber; + RelativeBlockLocations.push_back(Relative); + } +} + CmpInst::Predicate IRInstructionData::predicateForConsistency(CmpInst *CI) { switch (CI->getPredicate()) { case CmpInst::FCMP_OGT: @@ -236,6 +261,9 @@ if (isa(*It)) ID->setBranchSuccessors(BasicBlockToInteger); + if (isa(*It)) + ID->setPHIPredecessors(BasicBlockToInteger); + // Add to the instruction list bool WasInserted; DenseMap::iterator Index: llvm/test/Transforms/IROutliner/phi-nodes-non-constant.ll =================================================================== --- /dev/null +++ llvm/test/Transforms/IROutliner/phi-nodes-non-constant.ll @@ -0,0 +1,85 @@ +; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --include-generated-funcs +; RUN: opt -S -verify -iroutliner -ir-outlining-no-cost < %s | FileCheck %s + +; Show that we do not extract phi nodes as it would require extra label and +; control flow checking. + +define void @function1(i32* %a, i32* %b) { +entry: + %0 = alloca i32, align 4 + %c = load i32, i32* %0, align 4 + br label %test1 +test1: + %e = load i32, i32* %0, align 4 + br label %first +test: + %d = load i32, i32* %0, align 4 + br label %first +first: + %1 = phi i32 [ %c, %test ], [ %e, %test1 ] + store i32 2, i32* %a, align 4 + store i32 3, i32* %b, align 4 + ret void +} + +define void @function2(i32* %a, i32* %b) { +entry: + %0 = alloca i32, align 4 + %c = load i32, i32* %0, align 4 + br label %test1 +test1: + %e = load i32, i32* %0, align 4 + br label %first +test: + %d = load i32, i32* %0, align 4 + br label %first +first: + %1 = phi i32 [ %c, %test ], [ %e, %test1 ] + store i32 2, i32* %a, align 4 + store i32 3, i32* %b, align 4 + ret void +} +; CHECK-LABEL: @function1( +; CHECK-NEXT: entry: +; CHECK-NEXT: [[TMP0:%.*]] = alloca i32, align 4 +; CHECK-NEXT: [[C:%.*]] = load i32, i32* [[TMP0]], align 4 +; CHECK-NEXT: br label [[TEST1:%.*]] +; CHECK: test1: +; CHECK-NEXT: [[E:%.*]] = load i32, i32* [[TMP0]], align 4 +; CHECK-NEXT: br label [[FIRST:%.*]] +; CHECK: test: +; CHECK-NEXT: [[D:%.*]] = load i32, i32* [[TMP0]], align 4 +; CHECK-NEXT: br label [[FIRST]] +; CHECK: first: +; CHECK-NEXT: [[TMP1:%.*]] = phi i32 [ [[C]], [[TEST:%.*]] ], [ [[E]], [[TEST1]] ] +; CHECK-NEXT: call void @outlined_ir_func_0(i32* [[A:%.*]], i32* [[B:%.*]]) +; CHECK-NEXT: ret void +; +; +; CHECK-LABEL: @function2( +; CHECK-NEXT: entry: +; CHECK-NEXT: [[TMP0:%.*]] = alloca i32, align 4 +; CHECK-NEXT: [[C:%.*]] = load i32, i32* [[TMP0]], align 4 +; CHECK-NEXT: br label [[TEST1:%.*]] +; CHECK: test1: +; CHECK-NEXT: [[E:%.*]] = load i32, i32* [[TMP0]], align 4 +; CHECK-NEXT: br label [[FIRST:%.*]] +; CHECK: test: +; CHECK-NEXT: [[D:%.*]] = load i32, i32* [[TMP0]], align 4 +; CHECK-NEXT: br label [[FIRST]] +; CHECK: first: +; CHECK-NEXT: [[TMP1:%.*]] = phi i32 [ [[C]], [[TEST:%.*]] ], [ [[E]], [[TEST1]] ] +; CHECK-NEXT: call void @outlined_ir_func_0(i32* [[A:%.*]], i32* [[B:%.*]]) +; CHECK-NEXT: ret void +; +; +; CHECK: define internal void @outlined_ir_func_0( +; CHECK-NEXT: newFuncRoot: +; CHECK-NEXT: br label [[FIRST_TO_OUTLINE:%.*]] +; CHECK: first_after_outline.exitStub: +; CHECK-NEXT: ret void +; CHECK: first_to_outline: +; CHECK-NEXT: store i32 2, i32* [[TMP0:%.*]], align 4 +; CHECK-NEXT: store i32 3, i32* [[TMP1:%.*]], align 4 +; CHECK-NEXT: br label [[FIRST_AFTER_OUTLINE_EXITSTUB:%.*]] +; Index: llvm/test/Transforms/IROutliner/phi-nodes-simple.ll =================================================================== --- /dev/null +++ llvm/test/Transforms/IROutliner/phi-nodes-simple.ll @@ -0,0 +1,60 @@ +; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --include-generated-funcs +; RUN: opt -S -verify -iroutliner -ir-outlining-no-cost < %s | FileCheck %s + +; Show that we do not extract phi nodes as it would require extra label and +; control flow checking. + +define void @function1(i32* %a, i32* %b) { +entry: + br label %test +test: + br label %first +first: + %0 = phi i32 [ 0, %test ] + store i32 2, i32* %a, align 4 + store i32 3, i32* %b, align 4 + ret void +} + +define void @function2(i32* %a, i32* %b) { +entry: + br label %test +test: + br label %first +first: + %0 = phi i32 [ 0, %test ] + store i32 2, i32* %a, align 4 + store i32 3, i32* %b, align 4 + ret void +} +; CHECK-LABEL: @function1( +; CHECK-NEXT: entry: +; CHECK-NEXT: br label [[TEST:%.*]] +; CHECK: test: +; CHECK-NEXT: br label [[FIRST:%.*]] +; CHECK: first: +; CHECK-NEXT: call void @outlined_ir_func_0(i32* [[A:%.*]], i32* [[B:%.*]]) +; CHECK-NEXT: ret void +; +; +; CHECK-LABEL: @function2( +; CHECK-NEXT: entry: +; CHECK-NEXT: br label [[TEST:%.*]] +; CHECK: test: +; CHECK-NEXT: br label [[FIRST:%.*]] +; CHECK: first: +; CHECK-NEXT: call void @outlined_ir_func_0(i32* [[A:%.*]], i32* [[B:%.*]]) +; CHECK-NEXT: ret void +; +; +; CHECK: define internal void @outlined_ir_func_0( +; CHECK-NEXT: newFuncRoot: +; CHECK-NEXT: br label [[FIRST_TO_OUTLINE:%.*]] +; CHECK: first_after_outline.exitStub: +; CHECK-NEXT: ret void +; CHECK: first_to_outline: +; CHECK-NEXT: [[TMP2:%.*]] = phi i32 [ 0, [[NEWFUNCROOT:%.*]] ] +; CHECK-NEXT: store i32 2, i32* [[TMP0:%.*]], align 4 +; CHECK-NEXT: store i32 3, i32* [[TMP1:%.*]], align 4 +; CHECK-NEXT: br label [[FIRST_AFTER_OUTLINE_EXITSTUB:%.*]] +; Index: llvm/unittests/Analysis/IRSimilarityIdentifierTest.cpp =================================================================== --- llvm/unittests/Analysis/IRSimilarityIdentifierTest.cpp +++ llvm/unittests/Analysis/IRSimilarityIdentifierTest.cpp @@ -755,26 +755,13 @@ ASSERT_TRUE(UnsignedVec[1] < UnsignedVec[2]); } -// In most cases, the illegal instructions we are collecting don't require any -// sort of setup. In these cases, we can just only have illegal instructions, -// and the mapper will create 0 length vectors, and we can check that. - -// In cases where we have legal instructions needed to set up the illegal -// instruction, to check illegal instructions are assigned unsigned integers -// from the maximum value decreasing to 0, it will be greater than a legal -// instruction that comes after. So to check that we have an illegal -// instruction, we place a legal instruction after an illegal instruction, and -// check that the illegal unsigned integer is greater than the unsigned integer -// of the legal instruction. - -// Checks that a PHINode is mapped to be illegal since there is extra checking -// needed to ensure that a branch in one region is bin an isomorphic -// location in a different region. +// Checks that a PHINode is mapped to be legal. TEST(IRInstructionMapper, PhiIllegal) { StringRef ModuleString = R"( define i32 @f(i32 %a, i32 %b) { bb0: %0 = phi i1 [ 0, %bb0 ], [ %0, %bb1 ] + %1 = add i32 %a, %b ret i32 0 bb1: ret i32 1 @@ -788,12 +775,25 @@ SpecificBumpPtrAllocator InstDataAllocator; SpecificBumpPtrAllocator IDLAllocator; IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator); + Mapper.initializeForBBs(*M); getVectors(*M, Mapper, InstrList, UnsignedVec); ASSERT_EQ(InstrList.size(), UnsignedVec.size()); - ASSERT_EQ(UnsignedVec.size(), static_cast(0)); + ASSERT_EQ(UnsignedVec.size(), static_cast(3)); } +// In most cases, the illegal instructions we are collecting don't require any +// sort of setup. In these cases, we can just only have illegal instructions, +// and the mapper will create 0 length vectors, and we can check that. + +// In cases where we have legal instructions needed to set up the illegal +// instruction, to check illegal instructions are assigned unsigned integers +// from the maximum value decreasing to 0, it will be greater than a legal +// instruction that comes after. So to check that we have an illegal +// instruction, we place a legal instruction after an illegal instruction, and +// check that the illegal unsigned integer is greater than the unsigned integer +// of the legal instruction. + // Checks that an alloca instruction is mapped to be illegal. TEST(IRInstructionMapper, AllocaIllegal) { StringRef ModuleString = R"( @@ -2289,6 +2289,111 @@ ASSERT_TRUE(longSimCandCompare(InstrList, true, 3, 0, 6)); } +// Checks that the same structure is recognized between two candidates, +// when the phi predecessor are other blocks inside the same region, +// the relative distance between the blocks must be the same. +TEST(IRSimilarityCandidate, SamePHIStructureInternal) { + StringRef ModuleString = R"( + define i32 @f(i32 %a, i32 %b) { + bb0: + br label %bb2 + bb1: + br label %bb2 + bb2: + %0 = phi i32 [ %a, %bb0 ], [ %b, %bb1 ] + %1 = add i32 %b, %a + %2 = add i32 %a, %b + ret i32 0 + } + + define i32 @f2(i32 %a, i32 %b) { + bb0: + br label %bb2 + bb1: + br label %bb2 + bb2: + %0 = phi i32 [ %a, %bb0 ], [ %b, %bb1 ] + %1 = add i32 %b, %a + %2 = add i32 %a, %b + ret i32 0 + })"; + LLVMContext Context; + std::unique_ptr M = makeLLVMModule(Context, ModuleString); + + std::vector InstrList; + std::vector UnsignedVec; + + SpecificBumpPtrAllocator InstDataAllocator; + SpecificBumpPtrAllocator IDLAllocator; + IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator); + Mapper.InstClassifier.EnableBranches = true; + Mapper.initializeForBBs(*M); + getVectors(*M, Mapper, InstrList, UnsignedVec); + + // Check to make sure that we have a long enough region. + ASSERT_EQ(InstrList.size(), static_cast(11)); + // Check that the instructions were added correctly to both vectors. + ASSERT_TRUE(InstrList.size() == UnsignedVec.size()); + + for (unsigned i : UnsignedVec) + errs() << i << " "; + errs() << "\n"; + ASSERT_TRUE(longSimCandCompare(InstrList, true, 4, 0, 6)); +} + +// Checks that the different structure is recognized between two candidates, +// when the phi predecessor are other blocks inside the same region, +// the relative distance between the blocks must be the same. +TEST(IRSimilarityCandidate, DifferentPHIStructureInternal) { + StringRef ModuleString = R"( + define i32 @f(i32 %a, i32 %b) { + bb0: + br label %bb2 + bb1: + br label %bb2 + bb3: + br label %bb2 + bb2: + %0 = phi i32 [ %a, %bb0 ], [ %b, %bb1 ] + %1 = add i32 %b, %a + %2 = add i32 %a, %b + ret i32 0 + } + + define i32 @f2(i32 %a, i32 %b) { + bb0: + br label %bb2 + bb1: + br label %bb2 + bb3: + br label %bb2 + bb2: + %0 = phi i32 [ %a, %bb0 ], [ %b, %bb3 ] + %1 = add i32 %b, %a + %2 = add i32 %a, %b + ret i32 0 + })"; + LLVMContext Context; + std::unique_ptr M = makeLLVMModule(Context, ModuleString); + + std::vector InstrList; + std::vector UnsignedVec; + + SpecificBumpPtrAllocator InstDataAllocator; + SpecificBumpPtrAllocator IDLAllocator; + IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator); + Mapper.InstClassifier.EnableBranches = true; + Mapper.initializeForBBs(*M); + getVectors(*M, Mapper, InstrList, UnsignedVec); + + // Check to make sure that we have a long enough region. + ASSERT_EQ(InstrList.size(), static_cast(13)); + // Check that the instructions were added correctly to both vectors. + ASSERT_TRUE(InstrList.size() == UnsignedVec.size()); + + ASSERT_FALSE(longSimCandCompare(InstrList, true, 5, 0, 7)); +} + // Checks that two sets of identical instructions are found to be the same. // Both sequences of adds have the same operand ordering, and the same // instructions, making them strcturally equivalent.