diff --git a/llvm/lib/Transforms/InstCombine/InstCombineInternal.h b/llvm/lib/Transforms/InstCombine/InstCombineInternal.h --- a/llvm/lib/Transforms/InstCombine/InstCombineInternal.h +++ b/llvm/lib/Transforms/InstCombine/InstCombineInternal.h @@ -643,6 +643,7 @@ Instruction *foldPHIArgLoadIntoPHI(PHINode &PN); Instruction *foldPHIArgZextsIntoPHI(PHINode &PN); Instruction *foldPHIArgIntToPtrToPHI(PHINode &PN); + Instruction *foldPHIArgGEPWithConsts(PHINode &PN); /// If an integer typed PHI has only one use which is an IntToPtr operation, /// replace the PHI with an existing pointer typed PHI if it exists. Otherwise diff --git a/llvm/lib/Transforms/InstCombine/InstCombinePHI.cpp b/llvm/lib/Transforms/InstCombine/InstCombinePHI.cpp --- a/llvm/lib/Transforms/InstCombine/InstCombinePHI.cpp +++ b/llvm/lib/Transforms/InstCombine/InstCombinePHI.cpp @@ -40,15 +40,22 @@ /// as input. The debug location of the single operation will be the merged /// locations of the original PHI node arguments. void InstCombinerImpl::PHIArgMergedDebugLoc(Instruction *Inst, PHINode &PN) { - auto *FirstInst = cast(PN.getIncomingValue(0)); - Inst->setDebugLoc(FirstInst->getDebugLoc()); + Instruction *CurrentInst = nullptr; + unsigned Index; + for (Index = 0; Index < PN.getNumIncomingValues() && !CurrentInst; Index++) { + CurrentInst = dyn_cast(PN.getIncomingValue(Index)); + } + assert(CurrentInst && "PHI Node is expected to have at least one instruction " + "as incoming value"); + Inst->setDebugLoc(CurrentInst->getDebugLoc()); // We do not expect a CallInst here, otherwise, N-way merging of DebugLoc // will be inefficient. assert(!isa(Inst)); - for (Value *V : drop_begin(PN.incoming_values())) { - auto *I = cast(V); - Inst->applyMergedLocation(Inst->getDebugLoc(), I->getDebugLoc()); + for (Value *V : drop_begin(PN.incoming_values(), Index)) { + if (auto *I = dyn_cast(V)) { + Inst->applyMergedLocation(Inst->getDebugLoc(), I->getDebugLoc()); + } } } @@ -604,6 +611,151 @@ return NewGEP; } +Instruction *InstCombinerImpl::foldPHIArgGEPWithConsts(PHINode &PN) { + bool AllInBounds = true; + Value *PossibleBasePointerValue = nullptr; + SmallVector CurrentConstantIndices; + SmallVector, 4> ConstantIndices; + const GetElementPtrInst *PreviousGEPInstr = nullptr; + unsigned InstrNumber = 0; + bool HasDifferentGEPs = false; + + // Check that all users are load source or store destination. + // This modification is worth to do if it can be later transformed + // in addressing by constant offset. + // In other cases it can only cause inefficient register usage. + for (auto User : PN.users()) { + if (isa(User)) { + // Check that PHI is used as destination operand. + if (User->getOperand(0) == &PN) { + return nullptr; + } + } else if (!isa(User)) { + return nullptr; + } + } + + auto AddZeroConstants = [&PreviousGEPInstr, &ConstantIndices]() { + SmallVector ZeroConstants; + for (Value *Operand : PreviousGEPInstr->indices()) { + ZeroConstants.push_back(ConstantInt::get(Operand->getType(), 0)); + } + ConstantIndices.push_back(ZeroConstants); + }; + + for (Value *Incoming : PN.incoming_values()) { + Value *CurrentValue = Incoming; + + if (auto *GEPInstruction = dyn_cast(Incoming)) { + // Don't try to modify structure as far as PHI nodes as arg is prohibited. + if (GEPInstruction->getSourceElementType()->isStructTy()) { + return nullptr; + } + if (PreviousGEPInstr) { + if (GEPInstruction->getNumIndices() != + PreviousGEPInstr->getNumIndices() || + GEPInstruction->getResultElementType() != + PreviousGEPInstr->getResultElementType()) { + return nullptr; + } + } + + CurrentValue = GEPInstruction->getPointerOperand(); + AllInBounds &= GEPInstruction->isInBounds(); + + // Collect all constant indices from GEP instructions + // and check that GEP instructions differ. + unsigned Index = 1; + bool DiffersFromPrevious = false; + CurrentConstantIndices = + SmallVector(GEPInstruction->getNumIndices()); + for (auto IndexOperator = GEPInstruction->idx_begin(); + IndexOperator != GEPInstruction->idx_end(); + IndexOperator++, Index++) { + + DiffersFromPrevious |= + PreviousGEPInstr && GEPInstruction->getOperand(Index) != + PreviousGEPInstr->getOperand(Index); + + if (auto ConstantIndexValue = + dyn_cast(IndexOperator->get())) { + // Different type can be caused by previous optimization of GEP + // instruction. + if (PreviousGEPInstr && + ConstantIndexValue->getType() != + PreviousGEPInstr->getOperand(Index)->getType()) { + return nullptr; + } + CurrentConstantIndices[Index - 1] = ConstantIndexValue; + } else { + return nullptr; + } + } + + HasDifferentGEPs |= DiffersFromPrevious; + + if (PreviousGEPInstr == nullptr) { + PreviousGEPInstr = GEPInstruction; + } + + // First element in PHI wasn't GEP value, so need to create zero indices. + if (PossibleBasePointerValue != nullptr && ConstantIndices.empty()) { + for (unsigned I = 0; I < InstrNumber; I++) { + AddZeroConstants(); + } + HasDifferentGEPs = true; + } + ConstantIndices.push_back(CurrentConstantIndices); + } else { + if (PreviousGEPInstr != nullptr) { + AddZeroConstants(); + HasDifferentGEPs = true; + } + } + + if (PossibleBasePointerValue == nullptr) { + PossibleBasePointerValue = CurrentValue; + } else if (CurrentValue != PossibleBasePointerValue) { + return nullptr; + } + InstrNumber++; + } + + if (ConstantIndices.empty() || !HasDifferentGEPs) { + return nullptr; + } + + unsigned PHINumber = ConstantIndices[0].size(); + unsigned IncomingNumber = ConstantIndices.size(); + + // It's worth to simplify if we don't create too many new instructions + if (PN.getNumOperands() <= PHINumber + 1) { + return nullptr; + } + // Create new PHI nodes. + SmallVector NewPHINodes; + for (unsigned PHIIndex = 0; PHIIndex < PHINumber; PHIIndex++) { + PHINode *NewPN = + PHINode::Create(ConstantIndices[0][PHIIndex]->getType(), IncomingNumber, + PN.getName() + ".pn" + itostr(PHIIndex)); + NewPHINodes.push_back(NewPN); + InsertNewInstBefore(NewPN, PN); + for (unsigned GEPIndex = 0; GEPIndex < IncomingNumber; GEPIndex++) { + NewPN->addIncoming(ConstantIndices[GEPIndex][PHIIndex], + PN.getIncomingBlock(GEPIndex)); + } + } + + GetElementPtrInst *NewGEP = GetElementPtrInst::Create( + PreviousGEPInstr->getSourceElementType(), PossibleBasePointerValue, + makeArrayRef(NewPHINodes)); + if (AllInBounds) + NewGEP->setIsInBounds(); + PHIArgMergedDebugLoc(NewGEP, PN); + + return NewGEP; +} + /// Return true if we know that it is safe to sink the load out of the block /// that defines it. This means that it must be obvious the value of the load is /// not changed from the point of the load to the end of the block it is in. @@ -1389,6 +1541,10 @@ if (Instruction *Result = foldPHIArgOpIntoPHI(PN)) return Result; + if (Instruction *Result = foldPHIArgGEPWithConsts(PN)) { + return Result; + } + // If the incoming values are pointer casts of the same original value, // replace the phi with a single cast iff we can insert a non-PHI instruction. if (PN.getType()->isPointerTy() && diff --git a/llvm/test/Transforms/InstCombine/phi-with-geps.ll b/llvm/test/Transforms/InstCombine/phi-with-geps.ll --- a/llvm/test/Transforms/InstCombine/phi-with-geps.ll +++ b/llvm/test/Transforms/InstCombine/phi-with-geps.ll @@ -1,6 +1,8 @@ ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py ; RUN: opt -instcombine -S < %s | FileCheck %s +; convert phi[ gep (x, const), gep (x, const1) ---> gep (x, phi[const, const1]) + %struct.anon = type { i32, i32, i32 } ; PHI node that consists of GEPs of same base only. @@ -8,16 +10,14 @@ ; CHECK-LABEL: @test1( ; CHECK-NEXT: br i1 [[FLAG:%.*]], label [[IF:%.*]], label [[ELSE:%.*]] ; CHECK: if: -; CHECK-NEXT: [[GEP1:%.*]] = getelementptr inbounds i64, i64* [[ARRAY:%.*]], i64 1 ; CHECK-NEXT: br i1 [[FLAG]], label [[IF1:%.*]], label [[JOIN:%.*]] ; CHECK: else: -; CHECK-NEXT: [[GEP2:%.*]] = getelementptr inbounds i64, i64* [[ARRAY]], i64 2 ; CHECK-NEXT: br label [[JOIN]] ; CHECK: if1: -; CHECK-NEXT: [[GEP3:%.*]] = getelementptr inbounds i64, i64* [[ARRAY]], i64 3 ; CHECK-NEXT: br label [[JOIN]] ; CHECK: join: -; CHECK-NEXT: [[PHI:%.*]] = phi i64* [ [[GEP1]], [[IF]] ], [ [[GEP2]], [[ELSE]] ], [ [[GEP3]], [[IF1]] ] +; CHECK-NEXT: [[PHI_PN0:%.*]] = phi i64 [ 1, [[IF]] ], [ 2, [[ELSE]] ], [ 3, [[IF1]] ] +; CHECK-NEXT: [[PHI:%.*]] = getelementptr inbounds i64, i64* [[ARRAY:%.*]], i64 [[PHI_PN0]] ; CHECK-NEXT: store i64 2, i64* [[PHI]], align 4 ; CHECK-NEXT: ret i32 1 ; @@ -46,15 +46,14 @@ ; CHECK-LABEL: @test2( ; CHECK-NEXT: br i1 [[FLAG:%.*]], label [[IF:%.*]], label [[ELSE:%.*]] ; CHECK: if: -; CHECK-NEXT: [[GEP1:%.*]] = getelementptr inbounds i64, i64* [[ARRAY:%.*]], i64 1 ; CHECK-NEXT: br i1 [[FLAG]], label [[IF1:%.*]], label [[JOIN:%.*]] ; CHECK: else: -; CHECK-NEXT: [[GEP2:%.*]] = getelementptr inbounds i64, i64* [[ARRAY]], i64 2 ; CHECK-NEXT: br label [[JOIN]] ; CHECK: if1: ; CHECK-NEXT: br label [[JOIN]] ; CHECK: join: -; CHECK-NEXT: [[PHI:%.*]] = phi i64* [ [[GEP1]], [[IF]] ], [ [[GEP2]], [[ELSE]] ], [ [[ARRAY]], [[IF1]] ] +; CHECK-NEXT: [[PHI_PN0:%.*]] = phi i64 [ 1, [[IF]] ], [ 2, [[ELSE]] ], [ 0, [[IF1]] ] +; CHECK-NEXT: [[PHI:%.*]] = getelementptr inbounds i64, i64* [[ARRAY:%.*]], i64 [[PHI_PN0]] ; CHECK-NEXT: store i64 3, i64* [[PHI]], align 4 ; CHECK-NEXT: ret i32 1 ; @@ -82,19 +81,17 @@ ; CHECK-LABEL: @test3( ; CHECK-NEXT: br i1 [[FLAG:%.*]], label [[IF:%.*]], label [[ELSE:%.*]] ; CHECK: if: -; CHECK-NEXT: [[GEP1:%.*]] = getelementptr inbounds [50 x i32], [50 x i32]* [[ARRAY2:%.*]], i64 0, i64 0 ; CHECK-NEXT: br i1 [[FLAG]], label [[IF1:%.*]], label [[JOIN:%.*]] ; CHECK: else: -; CHECK-NEXT: [[GEP2:%.*]] = getelementptr inbounds [50 x i32], [50 x i32]* [[ARRAY2]], i64 2, i64 3 ; CHECK-NEXT: br i1 [[FLAG]], label [[IF2:%.*]], label [[JOIN]] ; CHECK: if1: -; CHECK-NEXT: [[GEP3:%.*]] = getelementptr inbounds [50 x i32], [50 x i32]* [[ARRAY2]], i64 3, i64 2 ; CHECK-NEXT: br label [[JOIN]] ; CHECK: if2: -; CHECK-NEXT: [[GEP4:%.*]] = getelementptr inbounds [50 x i32], [50 x i32]* [[ARRAY2]], i64 1, i64 1 ; CHECK-NEXT: br label [[JOIN]] ; CHECK: join: -; CHECK-NEXT: [[PHI:%.*]] = phi i32* [ [[GEP1]], [[IF]] ], [ [[GEP2]], [[ELSE]] ], [ [[GEP3]], [[IF1]] ], [ [[GEP4]], [[IF2]] ] +; CHECK-NEXT: [[PHI_PN0:%.*]] = phi i64 [ 0, [[IF]] ], [ 2, [[ELSE]] ], [ 3, [[IF1]] ], [ 1, [[IF2]] ] +; CHECK-NEXT: [[PHI_PN1:%.*]] = phi i64 [ 0, [[IF]] ], [ 3, [[ELSE]] ], [ 2, [[IF1]] ], [ 1, [[IF2]] ] +; CHECK-NEXT: [[PHI:%.*]] = getelementptr inbounds [50 x i32], [50 x i32]* [[ARRAY2:%.*]], i64 [[PHI_PN0]], i64 [[PHI_PN1]] ; CHECK-NEXT: store i32 1, i32* [[PHI]], align 4 ; CHECK-NEXT: ret i32 1 ; @@ -122,6 +119,7 @@ ret i32 1 } +; Negative test ; GEP with structure define i32 @test4(i1 %flag, i32 %x, %struct.anon* %s) { ; CHECK-LABEL: @test4( @@ -171,6 +169,7 @@ ret i32 1 } +; Negative test. ; PHI not only with GEPS. define i32 @test5(i1 %flag, i64* %array, i64* %x) { ; CHECK-LABEL: @test5( @@ -207,6 +206,7 @@ ret i32 1 } +; Negative test ; PHI node that consists of GEPs with different base. define i32 @test6(i1 %flag, i64* %array, i64* %array1) { ; CHECK-LABEL: @test6( @@ -245,6 +245,7 @@ ret i32 1 } +; Negative test ; PHI node that consists of GEPs with non-constant value. define i32 @test7(i1 %flag, i64* %array, i64 %x) { ; CHECK-LABEL: @test7( @@ -283,6 +284,7 @@ ret i32 1 } +; Negative test ; Not enough elements in PHI node. define i32 @test8(i1 %flag, i64* %array) { ; CHECK-LABEL: @test8(