From da2b817d1ae73d014539e4e47675d8be3e47c81d Mon Sep 17 00:00:00 2001 From: Sanjoy Das Date: Thu, 8 Oct 2015 18:28:36 +0000 Subject: [PATCH] [SCEV] Pick backedge values for phi nodes correctly Summary: `getConstantEvolutionLoopExitValue` and `ComputeExitCountExhaustively` assumed all phi nodes in the loop header have the same order of incoming values. This is not correct, and this commit changes `getConstantEvolutionLoopExitValue` and `ComputeExitCountExhaustively` to lookup the backedge value of a phi node using the loop's latch block. Unfortunately, there is still some code duplication `getConstantEvolutionLoopExitValue` and `ComputeExitCountExhaustively`. At some point in the future we should extract out a helper class / method that can evolve constant evolution phi nodes across iterations. Fixes 25060. Thanks to Mattias Eriksson for the spot-on analysis! Depends on D13457. Reviewers: atrick, hfinkel Subscribers: materi, llvm-commits Differential Revision: http://reviews.llvm.org/D13458 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@249712 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Analysis/ScalarEvolution.cpp | 43 +++++++++++++++++------ test/Transforms/IndVarSimplify/pr25060.ll | 37 +++++++++++++++++++ 2 files changed, 70 insertions(+), 10 deletions(-) create mode 100644 test/Transforms/IndVarSimplify/pr25060.ll diff --git a/lib/Analysis/ScalarEvolution.cpp b/lib/Analysis/ScalarEvolution.cpp index 05c1c6980cb..c9f7a48cf79 100644 --- a/lib/Analysis/ScalarEvolution.cpp +++ b/lib/Analysis/ScalarEvolution.cpp @@ -5742,22 +5742,36 @@ ScalarEvolution::getConstantEvolutionLoopExitValue(PHINode *PN, BasicBlock *Header = L->getHeader(); assert(PN->getParent() == Header && "Can't evaluate PHI not in loop header!"); - // Since the loop is canonicalized, the PHI node must have two entries. One + BasicBlock *Latch = L->getLoopLatch(); + if (!Latch) + return nullptr; + + // Since the loop has one latch, the PHI node must have two entries. One // entry must be a constant (coming in from outside of the loop), and the // second must be derived from the same PHI. - bool SecondIsBackedge = L->contains(PN->getIncomingBlock(1)); + + BasicBlock *NonLatch = Latch == PN->getIncomingBlock(0) + ? PN->getIncomingBlock(1) + : PN->getIncomingBlock(0); + + assert(PN->getNumIncomingValues() == 2 && "Follows from having one latch!"); + + // Note: not all PHI nodes in the same block have to have their incoming + // values in the same order, so we use the basic block to look up the incoming + // value, not an index. + for (auto &I : *Header) { PHINode *PHI = dyn_cast(&I); if (!PHI) break; auto *StartCST = - dyn_cast(PHI->getIncomingValue(!SecondIsBackedge)); + dyn_cast(PHI->getIncomingValueForBlock(NonLatch)); if (!StartCST) continue; CurrentIterVals[PHI] = StartCST; } if (!CurrentIterVals.count(PN)) return RetVal = nullptr; - Value *BEValue = PN->getIncomingValue(SecondIsBackedge); + Value *BEValue = PN->getIncomingValueForBlock(Latch); // Execute the loop symbolically to determine the exit value. if (BEs.getActiveBits() >= 32) @@ -5796,7 +5810,7 @@ ScalarEvolution::getConstantEvolutionLoopExitValue(PHINode *PN, PHINode *PHI = I.first; Constant *&NextPHI = NextIterVals[PHI]; if (!NextPHI) { // Not already computed. - Value *BEValue = PHI->getIncomingValue(SecondIsBackedge); + Value *BEValue = PHI->getIncomingValueForBlock(Latch); NextPHI = EvaluateExpression(BEValue, L, CurrentIterVals, DL, &TLI); } if (NextPHI != I.second) @@ -5831,15 +5845,24 @@ const SCEV *ScalarEvolution::ComputeExitCountExhaustively(const Loop *L, BasicBlock *Header = L->getHeader(); assert(PN->getParent() == Header && "Can't evaluate PHI not in loop header!"); - // One entry must be a constant (coming in from outside of the loop), and the - // second must be derived from the same PHI. - bool SecondIsBackedge = L->contains(PN->getIncomingBlock(1)); + BasicBlock *Latch = L->getLoopLatch(); + assert(Latch && "Should follow from NumIncomingValues == 2!"); + + // NonLatch is the preheader, or something equivalent. + BasicBlock *NonLatch = Latch == PN->getIncomingBlock(0) + ? PN->getIncomingBlock(1) + : PN->getIncomingBlock(0); + + // Note: not all PHI nodes in the same block have to have their incoming + // values in the same order, so we use the basic block to look up the incoming + // value, not an index. + for (auto &I : *Header) { PHINode *PHI = dyn_cast(&I); if (!PHI) break; auto *StartCST = - dyn_cast(PHI->getIncomingValue(!SecondIsBackedge)); + dyn_cast(PHI->getIncomingValueForBlock(NonLatch)); if (!StartCST) continue; CurrentIterVals[PHI] = StartCST; } @@ -5879,7 +5902,7 @@ const SCEV *ScalarEvolution::ComputeExitCountExhaustively(const Loop *L, Constant *&NextPHI = NextIterVals[PHI]; if (NextPHI) continue; // Already computed! - Value *BEValue = PHI->getIncomingValue(SecondIsBackedge); + Value *BEValue = PHI->getIncomingValueForBlock(Latch); NextPHI = EvaluateExpression(BEValue, L, CurrentIterVals, DL, &TLI); } CurrentIterVals.swap(NextIterVals); diff --git a/test/Transforms/IndVarSimplify/pr25060.ll b/test/Transforms/IndVarSimplify/pr25060.ll new file mode 100644 index 00000000000..25863fff2d3 --- /dev/null +++ b/test/Transforms/IndVarSimplify/pr25060.ll @@ -0,0 +1,37 @@ +; RUN: opt -S -indvars < %s | FileCheck %s + +define i16 @fn1() { +; CHECK-LABEL: @fn1( +entry: + br label %bb1 + +bb1: + %i = phi i16 [ 0, %entry ], [ 1, %bb1 ] + %storemerge = phi i16 [ %storemerge2, %bb1 ], [ 0, %entry ] + %storemerge2 = phi i16 [ 10, %entry ], [ 200, %bb1 ] + %tmp10 = icmp eq i16 %i, 1 + br i1 %tmp10, label %bb5, label %bb1 + +bb5: + %storemerge.lcssa = phi i16 [ %storemerge, %bb1 ] +; CHECK: ret i16 10 + ret i16 %storemerge.lcssa +} + +define i16 @fn2() { +; CHECK-LABEL: @fn2( +entry: + br label %bb1 + +bb1: + %canary = phi i16 [ 0, %entry ], [ %canary.inc, %bb1 ] + %i = phi i16 [ 0, %entry ], [ %storemerge, %bb1 ] + %storemerge = phi i16 [ 0, %bb1 ], [ 10, %entry ] + %canary.inc = add i16 %canary, 1 + %_tmp10 = icmp eq i16 %i, 10 + br i1 %_tmp10, label %bb5, label %bb1 + +bb5: +; CHECK: ret i16 1 + ret i16 %canary +} -- 2.34.1