diff --git a/llvm/lib/Transforms/Utils/SimplifyCFG.cpp b/llvm/lib/Transforms/Utils/SimplifyCFG.cpp --- a/llvm/lib/Transforms/Utils/SimplifyCFG.cpp +++ b/llvm/lib/Transforms/Utils/SimplifyCFG.cpp @@ -2078,8 +2078,97 @@ SmallPtrSet InstructionsToSink; DenseMap> PHIOperands; LockstepReverseIterator LRI(UnconditionalPreds); - while (LRI.isValid() && - canSinkInstructions(*LRI, PHIOperands)) { + + // Code generation will be less efficient because of losing opportunity + // to generate offset addressing if phi is created based on + // elements of same array. + auto ProfitableToCreatePHINode = [&](LockstepReverseIterator &LRI) { + bool HasPHIOperands = false; + bool ContainsDifferentGEPs = false; + const Value *PossibleBasePointerValue = nullptr; + const GetElementPtrInst *PreviousGEPInstr = nullptr; + SmallVector ConstantIndicesNumber; + SmallVector PreviousConstantIndices; + SmallVector CurrentConstantIndices; + unsigned GEPInstructionsNumber = 0; + for (auto *Instruction : *LRI) { + for (auto *V : PHIOperands[Instruction]) { + HasPHIOperands = true; + Value *CurrentValue = V; + + if (auto *GEPInstruction = dyn_cast(V)) { + CurrentValue = GEPInstruction->getPointerOperand(); + + // Check that all GEPs are different and contain constant values. + unsigned Index = 1; + unsigned ConstantIndices = 0; + CurrentConstantIndices = + SmallVector(GEPInstruction->getNumIndices(), false); + for (auto IndexOperator = GEPInstruction->idx_begin(); + IndexOperator != GEPInstruction->idx_end(); + IndexOperator++, Index++) { + auto ConstantIndexValue = + dyn_cast(IndexOperator->get()); + if (ConstantIndexValue) { + ConstantIndices++; + CurrentConstantIndices[Index - 1] = true; + } + GEPInstructionsNumber++; + if (!ContainsDifferentGEPs && PreviousGEPInstr != nullptr) { + if (GEPInstruction->getNumIndices() != + PreviousGEPInstr->getNumIndices()) { + ContainsDifferentGEPs = true; + } else { + // Check constants. + const Value *IndexFromPreviousGEP = + PreviousGEPInstr->getOperand(Index); + if (IndexFromPreviousGEP != IndexOperator->get()) { + if (CurrentConstantIndices[Index - 1] && + PreviousConstantIndices[Index - 1]) { + ContainsDifferentGEPs |= + ConstantIndexValue->getValue() != + cast(IndexFromPreviousGEP)->getValue(); + } else { + ContainsDifferentGEPs = true; + } + } + } + } + } + if (PreviousGEPInstr == nullptr) { + PreviousGEPInstr = GEPInstruction; + } + if (!ContainsDifferentGEPs) { + PreviousConstantIndices = CurrentConstantIndices; + } + ConstantIndicesNumber.push_back(ConstantIndices); + } + + if (PossibleBasePointerValue == nullptr) { + PossibleBasePointerValue = CurrentValue; + } else if (CurrentValue != PossibleBasePointerValue) { + return true; + } + } + } + if (!HasPHIOperands || + (!ContainsDifferentGEPs && GEPInstructionsNumber > 1)) { + return true; + } + size_t GEPWithConstantIndicesNumber = + count_if(ConstantIndicesNumber, [](int i) { return i > 0; }); + if (GEPWithConstantIndicesNumber < ConstantIndicesNumber.size() / 2) { + return true; + } + LLVM_DEBUG(dbgs() << "SINK: PHI node for elements of same entity " + << *PossibleBasePointerValue << " was found\n"); + return false; + }; + + while (LRI.isValid() && canSinkInstructions(*LRI, PHIOperands)) { + if (!ProfitableToCreatePHINode(LRI)) { + return false; + } LLVM_DEBUG(dbgs() << "SINK: instruction can be sunk: " << *(*LRI)[0] << "\n"); InstructionsToSink.insert((*LRI).begin(), (*LRI).end()); diff --git a/llvm/test/Transforms/SimplifyCFG/X86/sink-common-code.ll b/llvm/test/Transforms/SimplifyCFG/X86/sink-common-code.ll --- a/llvm/test/Transforms/SimplifyCFG/X86/sink-common-code.ll +++ b/llvm/test/Transforms/SimplifyCFG/X86/sink-common-code.ll @@ -296,17 +296,17 @@ %struct.anon = type { i32, i32 } ; The GEP indexes a struct type so cannot have a variable last index. -define i32 @test10(i1 zeroext %flag, i32 %x, i32* %y, %struct.anon* %s) { +define i32 @test10(i1 zeroext %flag, i32 %x, i32* %y, %struct.anon* %s, %struct.anon* %s1) { ; CHECK-LABEL: @test10( ; CHECK-NEXT: entry: ; CHECK-NEXT: br i1 [[FLAG:%.*]], label [[IF_THEN:%.*]], label [[IF_ELSE:%.*]] ; CHECK: if.then: ; CHECK-NEXT: [[DUMMY:%.*]] = add i32 [[X:%.*]], 5 -; CHECK-NEXT: [[GEPA:%.*]] = getelementptr inbounds [[STRUCT_ANON:%.*]], %struct.anon* [[S:%.*]], i32 0, i32 0 +; CHECK-NEXT: [[GEPA:%.*]] = getelementptr inbounds [[STRUCT_ANON:%.*]], %struct.anon* {{%.*}}, i32 0, i32 0 ; CHECK-NEXT: br label [[IF_END:%.*]] ; CHECK: if.else: ; CHECK-NEXT: [[DUMMY1:%.*]] = add i32 [[X]], 6 -; CHECK-NEXT: [[GEPB:%.*]] = getelementptr inbounds [[STRUCT_ANON]], %struct.anon* [[S]], i32 0, i32 1 +; CHECK-NEXT: [[GEPB:%.*]] = getelementptr inbounds [[STRUCT_ANON]], %struct.anon* {{%.*}}, i32 0, i32 1 ; CHECK-NEXT: br label [[IF_END]] ; CHECK: if.end: ; CHECK-NEXT: [[GEPB_SINK:%.*]] = phi i32* [ [[GEPB]], [[IF_ELSE]] ], [ [[GEPA]], [[IF_THEN]] ] @@ -324,7 +324,7 @@ if.else: %dummy1 = add i32 %x, 6 - %gepb = getelementptr inbounds %struct.anon, %struct.anon* %s, i32 0, i32 1 + %gepb = getelementptr inbounds %struct.anon, %struct.anon* %s1, i32 0, i32 1 store volatile i32 %x, i32* %gepb br label %if.end @@ -519,17 +519,17 @@ ; The load should be commoned. -define i32 @test15(i1 zeroext %flag, i32 %w, i32 %x, i32 %y, %struct.anon* %s) { +define i32 @test15(i1 zeroext %flag, i32 %w, i32 %x, i32 %y, %struct.anon* %s, %struct.anon* %s1) { ; CHECK-LABEL: @test15( ; CHECK-NEXT: entry: ; CHECK-NEXT: br i1 [[FLAG:%.*]], label [[IF_THEN:%.*]], label [[IF_ELSE:%.*]] ; CHECK: if.then: ; CHECK-NEXT: [[DUMMY:%.*]] = add i32 [[X:%.*]], 1 -; CHECK-NEXT: [[GEPA:%.*]] = getelementptr inbounds [[STRUCT_ANON:%.*]], %struct.anon* [[S:%.*]], i32 0, i32 0 +; CHECK-NEXT: [[GEPA:%.*]] = getelementptr inbounds [[STRUCT_ANON:%.*]], %struct.anon* {{%.*}}, i32 0, i32 0 ; CHECK-NEXT: br label [[IF_END:%.*]] ; CHECK: if.else: ; CHECK-NEXT: [[DUMMY2:%.*]] = add i32 [[X]], 4 -; CHECK-NEXT: [[GEPB:%.*]] = getelementptr inbounds [[STRUCT_ANON]], %struct.anon* [[S]], i32 0, i32 1 +; CHECK-NEXT: [[GEPB:%.*]] = getelementptr inbounds [[STRUCT_ANON]], %struct.anon* {{%.*}}, i32 0, i32 1 ; CHECK-NEXT: br label [[IF_END]] ; CHECK: if.end: ; CHECK-NEXT: [[GEPB_SINK:%.*]] = phi i32* [ [[GEPB]], [[IF_ELSE]] ], [ [[GEPA]], [[IF_THEN]] ] @@ -552,7 +552,7 @@ if.else: %dummy2 = add i32 %x, 4 - %gepb = getelementptr inbounds %struct.anon, %struct.anon* %s, i32 0, i32 1 + %gepb = getelementptr inbounds %struct.anon, %struct.anon* %s1, i32 0, i32 1 %sv2 = load i32, i32* %gepb %ext2 = zext i32 %sv2 to i64 %cmp2 = icmp eq i64 %ext2, 57 diff --git a/llvm/test/Transforms/SimplifyCFG/phi-with-geps-sink.ll b/llvm/test/Transforms/SimplifyCFG/phi-with-geps-sink.ll new file mode 100644 --- /dev/null +++ b/llvm/test/Transforms/SimplifyCFG/phi-with-geps-sink.ll @@ -0,0 +1,151 @@ +; NOTE: Assertions have been autogenerated by utils/update_test_checks.py +; RUN: opt < %s -simplifycfg -simplifycfg-require-and-preserve-domtree=1 -sink-common-insts -S | FileCheck %s +; RUN: opt < %s -passes='simplifycfg' -S | FileCheck %s + +%struct.anon = type { i32, i32 } + +; PHI node that consists of GEPs of same base only. +define i32 @test1(i1 %flag, i32 %x, %struct.anon* %s) { +; CHECK-LABEL: @test1( +; CHECK-NEXT: entry: +; CHECK-NEXT: br i1 [[FLAG:%.*]], label [[IF_THEN:%.*]], label [[IF_ELSE:%.*]] +; CHECK: if.then: +; CHECK-NEXT: [[DUMMY:%.*]] = add i32 [[X:%.*]], 5 +; CHECK-NEXT: [[GEPA:%.*]] = getelementptr inbounds [[STRUCT_ANON:%.*]], %struct.anon* [[S:%.*]], i32 0, i32 0 +; CHECK-NEXT: store i32 [[X]], i32* [[GEPA]], align 4 +; CHECK-NEXT: br label [[IF_END:%.*]] +; CHECK: if.else: +; CHECK-NEXT: [[DUMMY1:%.*]] = add i32 [[X]], 6 +; CHECK-NEXT: [[GEPB:%.*]] = getelementptr inbounds [[STRUCT_ANON]], %struct.anon* [[S]], i32 0, i32 1 +; CHECK-NEXT: store i32 [[X]], i32* [[GEPB]], align 4 +; CHECK-NEXT: br label [[IF_END]] +; CHECK: if.end: +; CHECK-NEXT: ret i32 1 +; +entry: + br i1 %flag, label %if.then, label %if.else + +if.then: + %dummy = add i32 %x, 5 + %gepa = getelementptr inbounds %struct.anon, %struct.anon* %s, i32 0, i32 0 + store i32 %x, i32* %gepa + br label %if.end + +if.else: + %dummy1 = add i32 %x, 6 + %gepb = getelementptr inbounds %struct.anon, %struct.anon* %s, i32 0, i32 1 + store i32 %x, i32* %gepb + br label %if.end + +if.end: + ret i32 1 +} + +; PHI node that consists of GEP and its base entity. +define i32 @test2(i1 %flag, i32* %array, i32 %x) { +; CHECK-LABEL: @test2( +; CHECK-NEXT: entry: +; CHECK-NEXT: br i1 [[FLAG:%.*]], label [[IF_THEN:%.*]], label [[IF_ELSE:%.*]] +; CHECK: if.then: +; CHECK-NEXT: [[DUMMY:%.*]] = add i32 [[X:%.*]], 5 +; CHECK-NEXT: store i32 [[X]], i32* [[ARRAY:%.*]], align 4 +; CHECK-NEXT: br label [[IF_END:%.*]] +; CHECK: if.else: +; CHECK-NEXT: [[DUMMY1:%.*]] = add i32 [[X]], 6 +; CHECK-NEXT: [[ARRAYIDX:%.*]] = getelementptr inbounds i32, i32* [[ARRAY]], i64 1 +; CHECK-NEXT: store i32 [[X]], i32* [[ARRAYIDX]], align 4 +; CHECK-NEXT: br label [[IF_END]] +; CHECK: if.end: +; CHECK-NEXT: ret i32 1 +; + +entry: + br i1 %flag, label %if.then, label %if.else + +if.then: + %dummy = add i32 %x, 5 + store i32 %x, i32* %array + br label %if.end + +if.else: + %dummy1 = add i32 %x, 6 + %arrayidx = getelementptr inbounds i32, i32* %array, i64 1 + store i32 %x, i32* %arrayidx + br label %if.end + +if.end: + ret i32 1 +} + +; PHI node that consists of GEPs of different base. +define i32 @test3(i1 %flag, i32 %x, %struct.anon* %s, %struct.anon* %s1) { +; CHECK-LABEL: @test3( +; CHECK-NEXT: entry: +; CHECK-NEXT: br i1 [[FLAG:%.*]], label [[IF_THEN:%.*]], label [[IF_ELSE:%.*]] +; CHECK: if.then: +; CHECK-NEXT: [[DUMMY:%.*]] = add i32 [[X:%.*]], 5 +; CHECK-NEXT: [[GEPA:%.*]] = getelementptr inbounds [[STRUCT_ANON:%.*]], %struct.anon* [[S:%.*]], i32 0, i32 0 +; CHECK-NEXT: br label [[IF_END:%.*]] +; CHECK: if.else: +; CHECK-NEXT: [[DUMMY1:%.*]] = add i32 [[X]], 6 +; CHECK-NEXT: [[GEPB:%.*]] = getelementptr inbounds [[STRUCT_ANON]], %struct.anon* [[S1:%.*]], i32 0, i32 1 +; CHECK-NEXT: br label [[IF_END]] +; CHECK: if.end: +; CHECK-NEXT: [[GEPB_SINK:%.*]] = phi i32* [ [[GEPB]], [[IF_ELSE]] ], [ [[GEPA]], [[IF_THEN]] ] +; CHECK-NEXT: store i32 [[X]], i32* [[GEPB_SINK]], align 4 +; CHECK-NEXT: ret i32 1 +; +entry: + br i1 %flag, label %if.then, label %if.else + +if.then: + %dummy = add i32 %x, 5 + %gepa = getelementptr inbounds %struct.anon, %struct.anon* %s, i32 0, i32 0 + store i32 %x, i32* %gepa + br label %if.end + +if.else: + %dummy1 = add i32 %x, 6 + %gepb = getelementptr inbounds %struct.anon, %struct.anon* %s1, i32 0, i32 1 + store i32 %x, i32* %gepb + br label %if.end + +if.end: + ret i32 1 +} + +; PHI node that consists of not GEPs only. +define i32 @test4(i1 %flag, i32* %array, i32 %x, %struct.anon* %s) { +; CHECK-LABEL: @test4( +; CHECK-NEXT: entry: +; CHECK-NEXT: br i1 [[FLAG:%.*]], label [[IF_THEN:%.*]], label [[IF_ELSE:%.*]] +; CHECK: if.then: +; CHECK-NEXT: [[DUMMY:%.*]] = add i32 [[X:%.*]], 5 +; CHECK-NEXT: br label [[IF_END:%.*]] +; CHECK: if.else: +; CHECK-NEXT: [[DUMMY1:%.*]] = add i32 [[X]], 6 +; CHECK-NEXT: [[GEPA:%.*]] = getelementptr inbounds [[STRUCT_ANON:%.*]], %struct.anon* [[S:%.*]], i32 0, i32 0 +; CHECK-NEXT: br label [[IF_END]] +; CHECK: if.end: +; CHECK-NEXT: [[GEPA_SINK:%.*]] = phi i32* [ [[GEPA]], [[IF_ELSE]] ], [ [[ARRAY:%.*]], [[IF_THEN]] ] +; CHECK-NEXT: store i32 [[X]], i32* [[GEPA_SINK]], align 4 +; CHECK-NEXT: ret i32 1 +; + +entry: + br i1 %flag, label %if.then, label %if.else + +if.then: + %dummy = add i32 %x, 5 + store i32 %x, i32* %array + br label %if.end + +if.else: + %dummy1 = add i32 %x, 6 + %gepa = getelementptr inbounds %struct.anon, %struct.anon* %s, i32 0, i32 0 + store i32 %x, i32* %gepa + br label %if.end + +if.end: + ret i32 1 +}