Index: llvm/lib/Transforms/Scalar/LoopBoundSplit.cpp =================================================================== --- llvm/lib/Transforms/Scalar/LoopBoundSplit.cpp +++ llvm/lib/Transforms/Scalar/LoopBoundSplit.cpp @@ -40,10 +40,12 @@ ICmpInst::Predicate Pred; /// AddRec llvm value Value *AddRecValue; + /// Non PHI AddRec llvm value + Value *NonPHIAddRecValue; /// Bound llvm value Value *BoundValue; /// AddRec SCEV - const SCEV *AddRecSCEV; + const SCEVAddRecExpr *AddRecSCEV; /// Bound SCEV const SCEV *BoundSCEV; @@ -55,19 +57,31 @@ } // namespace static void analyzeICmp(ScalarEvolution &SE, ICmpInst *ICmp, - ConditionInfo &Cond) { + ConditionInfo &Cond, const Loop &L) { Cond.ICmp = ICmp; if (match(ICmp, m_ICmp(Cond.Pred, m_Value(Cond.AddRecValue), m_Value(Cond.BoundValue)))) { - Cond.AddRecSCEV = SE.getSCEV(Cond.AddRecValue); - Cond.BoundSCEV = SE.getSCEV(Cond.BoundValue); + const SCEV *AddRecSCEV = SE.getSCEV(Cond.AddRecValue); + const SCEV *BoundSCEV = SE.getSCEV(Cond.BoundValue); + const SCEVAddRecExpr *LHSAddRecSCEV = dyn_cast(AddRecSCEV); + const SCEVAddRecExpr *RHSAddRecSCEV = dyn_cast(BoundSCEV); // Locate AddRec in LHSSCEV and Bound in RHSSCEV. - if (isa(Cond.BoundSCEV) && - !isa(Cond.AddRecSCEV)) { + if (!LHSAddRecSCEV && RHSAddRecSCEV) { std::swap(Cond.AddRecValue, Cond.BoundValue); - std::swap(Cond.AddRecSCEV, Cond.BoundSCEV); + std::swap(AddRecSCEV, BoundSCEV); Cond.Pred = ICmpInst::getSwappedPredicate(Cond.Pred); } + + Cond.AddRecSCEV = dyn_cast(AddRecSCEV); + Cond.BoundSCEV = BoundSCEV; + Cond.NonPHIAddRecValue = Cond.AddRecValue; + + // If the Cond.AddRecValue is PHI node, update Cond.NonPHIAddRecValue with + // value from backedge. + if (Cond.AddRecSCEV && isa(Cond.AddRecValue)) { + PHINode *PN = cast(Cond.AddRecValue); + Cond.NonPHIAddRecValue = PN->getIncomingValueForBlock(L.getLoopLatch()); + } } } @@ -119,21 +133,20 @@ static bool hasProcessableCondition(const Loop &L, ScalarEvolution &SE, ICmpInst *ICmp, ConditionInfo &Cond, bool IsExitCond) { - analyzeICmp(SE, ICmp, Cond); + analyzeICmp(SE, ICmp, Cond, L); // The BoundSCEV should be evaluated at loop entry. if (!SE.isAvailableAtLoopEntry(Cond.BoundSCEV, &L)) return false; - const SCEVAddRecExpr *AddRecSCEV = dyn_cast(Cond.AddRecSCEV); // Allowed AddRec as induction variable. - if (!AddRecSCEV) + if (!Cond.AddRecSCEV) return false; - if (!AddRecSCEV->isAffine()) + if (!Cond.AddRecSCEV->isAffine()) return false; - const SCEV *StepRecSCEV = AddRecSCEV->getStepRecurrence(SE); + const SCEV *StepRecSCEV = Cond.AddRecSCEV->getStepRecurrence(SE); // Allowed constant step. if (!isa(StepRecSCEV)) return false; @@ -268,10 +281,9 @@ // After transformation, we assume the split condition of the pre-loop is // always true. In order to guarantee it, we need to check the start value // of the split cond AddRec satisfies the split condition. - const SCEV *SplitAddRecStartSCEV = - cast(SplitCandidateCond.AddRecSCEV)->getStart(); - if (!SE.isKnownPredicate(SplitCandidateCond.Pred, SplitAddRecStartSCEV, - SplitCandidateCond.BoundSCEV)) + if (!SE.isLoopEntryGuardedByCond(&L, SplitCandidateCond.Pred, + SplitCandidateCond.AddRecSCEV->getStart(), + SplitCandidateCond.BoundSCEV)) continue; SplitCandidateCond.BI = BI; @@ -378,18 +390,27 @@ // Replace exiting bound value of pre-loop NewBound. ExitingCond.ICmp->setOperand(1, NewBoundValue); - // Replace IV's start value of post-loop by NewBound. + // Update phi nodes in header of post-loop. for (PHINode &PN : L.getHeader()->phis()) { // Find PHI with exiting condition from pre-loop. - if (SE.isSCEVable(PN.getType()) && isa(SE.getSCEV(&PN))) { - for (Value *Op : PN.incoming_values()) { - if (Op == ExitingCond.AddRecValue) { - // Find cloned PHI for post-loop. - PHINode *PostLoopPN = cast(VMap[&PN]); - PostLoopPN->setIncomingValueForBlock(PostLoopPreHeader, - NewBoundValue); - } - } + if (ExitingCond.NonPHIAddRecValue == + PN.getIncomingValueForBlock(L.getLoopLatch())) { + // Find cloned PHI for post-loop. + PHINode *PostLoopPN = cast(VMap[&PN]); + // Update post-loop PHI's incoming value from preheader with + // NewBoundValue. + PostLoopPN->setIncomingValueForBlock(PostLoopPreHeader, NewBoundValue); + } else if (SE.isSCEVable(PN.getType()) && + isa(SE.getSCEV(&PN))) { + // Update phi which is not related to exit condition but its expression is + // AddRecExpr. The incoming value from preheader should be `original + // incoming value + NewBoundValue` and it should be in preheader. + Value *OrgIncomingValue = + PN.getIncomingValueForBlock(L.getLoopPreheader()); + Value *NewIncomingValue = + Builder.CreateAdd(OrgIncomingValue, NewBoundValue); + PHINode *PostLoopPN = cast(VMap[&PN]); + PostLoopPN->setIncomingValueForBlock(PostLoopPreHeader, NewIncomingValue); } } Index: llvm/test/Transforms/LoopBoundSplit/bug-loop-bound-split-phi-in-exit-block.ll =================================================================== --- llvm/test/Transforms/LoopBoundSplit/bug-loop-bound-split-phi-in-exit-block.ll +++ llvm/test/Transforms/LoopBoundSplit/bug-loop-bound-split-phi-in-exit-block.ll @@ -31,7 +31,7 @@ ; CHECK: for.body.split.preheader: ; CHECK-NEXT: br label [[FOR_BODY_SPLIT:%.*]] ; CHECK: for.body.split: -; CHECK-NEXT: [[I_SPLIT:%.*]] = phi i16 [ [[ADD_SPLIT:%.*]], [[COND_END_SPLIT:%.*]] ], [ 0, [[FOR_BODY_SPLIT_PREHEADER]] ] +; CHECK-NEXT: [[I_SPLIT:%.*]] = phi i16 [ [[ADD_SPLIT:%.*]], [[COND_END_SPLIT:%.*]] ], [ 3, [[FOR_BODY_SPLIT_PREHEADER]] ] ; CHECK-NEXT: [[CMP1_SPLIT:%.*]] = icmp ult i16 [[I_SPLIT]], 3 ; CHECK-NEXT: br i1 false, label [[COND_TRUE_SPLIT:%.*]], label [[COND_FALSE_SPLIT:%.*]] ; CHECK: cond.false.split: Index: llvm/test/Transforms/LoopBoundSplit/bug51866.ll =================================================================== --- /dev/null +++ llvm/test/Transforms/LoopBoundSplit/bug51866.ll @@ -0,0 +1,99 @@ +; NOTE: Assertions have been autogenerated by utils/update_test_checks.py +; RUN: opt -passes=loop-bound-split -S < %s | FileCheck %s + +@B = external global [10 x i16], align 1 + +define void @test() { +; CHECK-LABEL: @test( +; CHECK-NEXT: entry: +; CHECK-NEXT: br label [[ENTRY_SPLIT:%.*]] +; CHECK: entry.split: +; CHECK-NEXT: br label [[FOR_COND:%.*]] +; CHECK: for.cond: +; CHECK-NEXT: [[I_0:%.*]] = phi i16 [ 0, [[ENTRY_SPLIT]] ], [ [[INC_0:%.*]], [[FOR_INC:%.*]] ] +; CHECK-NEXT: [[I_1:%.*]] = phi i16 [ 10, [[ENTRY_SPLIT]] ], [ [[INC_0]], [[FOR_INC]] ] +; CHECK-NEXT: [[I_2:%.*]] = phi i16 [ 10, [[ENTRY_SPLIT]] ], [ [[INC_2:%.*]], [[FOR_INC]] ] +; CHECK-NEXT: [[EXITCOND_NOT:%.*]] = icmp eq i16 [[I_0]], 5 +; CHECK-NEXT: br i1 [[EXITCOND_NOT]], label [[ENTRY_SPLIT_SPLIT:%.*]], label [[FOR_BODY:%.*]] +; CHECK: for.body: +; CHECK-NEXT: [[CMP1:%.*]] = icmp ult i16 [[I_0]], 5 +; CHECK-NEXT: [[ARRAYIDX:%.*]] = getelementptr inbounds [10 x i16], [10 x i16]* @B, i16 0, i16 [[I_0]] +; CHECK-NEXT: [[TMP0:%.*]] = load i16, i16* [[ARRAYIDX]], align 1 +; CHECK-NEXT: br i1 true, label [[IF_THEN:%.*]], label [[IF_ELSE:%.*]] +; CHECK: if.then: +; CHECK-NEXT: call void @foo(i16 [[TMP0]]) +; CHECK-NEXT: br label [[FOR_INC]] +; CHECK: if.else: +; CHECK-NEXT: call void @bar(i16 [[TMP0]]) +; CHECK-NEXT: br label [[FOR_INC]] +; CHECK: for.inc: +; CHECK-NEXT: [[INC_0]] = add nuw nsw i16 [[I_0]], 1 +; CHECK-NEXT: [[INC_2]] = add nuw nsw i16 [[I_2]], 1 +; CHECK-NEXT: br label [[FOR_COND]] +; CHECK: entry.split.split: +; CHECK-NEXT: [[I_0_LCSSA:%.*]] = phi i16 [ [[I_0]], [[FOR_COND]] ] +; CHECK-NEXT: [[TMP1:%.*]] = icmp ne i16 [[I_0_LCSSA]], 10 +; CHECK-NEXT: br i1 [[TMP1]], label [[FOR_COND_SPLIT_PREHEADER:%.*]], label [[FOR_END:%.*]] +; CHECK: for.cond.split.preheader: +; CHECK-NEXT: br label [[FOR_COND_SPLIT:%.*]] +; CHECK: for.cond.split: +; CHECK-NEXT: [[I_0_SPLIT:%.*]] = phi i16 [ [[INC_0_SPLIT:%.*]], [[FOR_INC_SPLIT:%.*]] ], [ 5, [[FOR_COND_SPLIT_PREHEADER]] ] +; CHECK-NEXT: [[I_1_SPLIT:%.*]] = phi i16 [ [[INC_0_SPLIT]], [[FOR_INC_SPLIT]] ], [ 5, [[FOR_COND_SPLIT_PREHEADER]] ] +; CHECK-NEXT: [[I_2_SPLIT:%.*]] = phi i16 [ [[INC_2_SPLIT:%.*]], [[FOR_INC_SPLIT]] ], [ 15, [[FOR_COND_SPLIT_PREHEADER]] ] +; CHECK-NEXT: [[EXITCOND_NOT_SPLIT:%.*]] = icmp eq i16 [[I_0_SPLIT]], 10 +; CHECK-NEXT: br i1 [[EXITCOND_NOT_SPLIT]], label [[FOR_END_LOOPEXIT:%.*]], label [[FOR_BODY_SPLIT:%.*]] +; CHECK: for.body.split: +; CHECK-NEXT: [[CMP1_SPLIT:%.*]] = icmp ult i16 [[I_0_SPLIT]], 5 +; CHECK-NEXT: [[ARRAYIDX_SPLIT:%.*]] = getelementptr inbounds [10 x i16], [10 x i16]* @B, i16 0, i16 [[I_0_SPLIT]] +; CHECK-NEXT: [[TMP2:%.*]] = load i16, i16* [[ARRAYIDX_SPLIT]], align 1 +; CHECK-NEXT: br i1 false, label [[IF_THEN_SPLIT:%.*]], label [[IF_ELSE_SPLIT:%.*]] +; CHECK: if.else.split: +; CHECK-NEXT: call void @bar(i16 [[TMP2]]) +; CHECK-NEXT: br label [[FOR_INC_SPLIT]] +; CHECK: if.then.split: +; CHECK-NEXT: call void @foo(i16 [[TMP2]]) +; CHECK-NEXT: br label [[FOR_INC_SPLIT]] +; CHECK: for.inc.split: +; CHECK-NEXT: [[INC_0_SPLIT]] = add nuw nsw i16 [[I_0_SPLIT]], 1 +; CHECK-NEXT: [[INC_2_SPLIT]] = add nuw nsw i16 [[I_2_SPLIT]], 1 +; CHECK-NEXT: br label [[FOR_COND_SPLIT]] +; CHECK: for.end.loopexit: +; CHECK-NEXT: br label [[FOR_END]] +; CHECK: for.end: +; CHECK-NEXT: ret void +; +entry: + br label %for.cond + +for.cond: ; preds = %for.inc, %entry + %i.0 = phi i16 [ 0, %entry ], [ %inc.0, %for.inc ] + %i.1 = phi i16 [ 10, %entry ], [ %inc.0, %for.inc ] + %i.2 = phi i16 [ 10, %entry ], [ %inc.2, %for.inc ] + %exitcond.not = icmp eq i16 %i.0, 10 + br i1 %exitcond.not, label %for.end, label %for.body + +for.body: ; preds = %for.cond + %cmp1 = icmp ult i16 %i.0, 5 + %arrayidx = getelementptr inbounds [10 x i16], [10 x i16]* @B, i16 0, i16 %i.0 + %0 = load i16, i16* %arrayidx, align 1 + br i1 %cmp1, label %if.then, label %if.else + +if.then: ; preds = %for.body + call void @foo(i16 %0) + br label %for.inc + +if.else: ; preds = %for.body + call void @bar(i16 %0) + br label %for.inc + +for.inc: ; preds = %if.else, %if.then + %inc.0 = add nuw nsw i16 %i.0, 1 + %inc.2 = add nuw nsw i16 %i.2, 1 + br label %for.cond + +for.end: ; preds = %for.cond + ret void +} + +declare void @foo(i16) +declare void @bar(i16)