Canonicalize nested AddRecs in by nesting them in order of loop depth.

llvm-svn: 54545

1 files changed, 13 insertions, 0 deletions

diff --git a/llvm/lib/Analysis/ScalarEvolution.cpp b/llvm/lib/Analysis/ScalarEvolution.cpp
index 84e02e47a0c..00a4475e28e 100644
--- a/llvm/lib/Analysis/ScalarEvolution.cpp
+++ b/llvm/lib/Analysis/ScalarEvolution.cpp
@@ -1158,6 +1158,19 @@ SCEVHandle ScalarEvolution::getAddRecExpr(std::vector<SCEVHandle> &Operands,
     return getAddRecExpr(Operands, L);             // { X,+,0 }  -->  X
   }
 
+  // Canonicalize nested AddRecs in by nesting them in order of loop depth.
+  if (SCEVAddRecExpr *NestedAR = dyn_cast<SCEVAddRecExpr>(Operands[0])) {
+    const Loop* NestedLoop = NestedAR->getLoop();
+    if (L->getLoopDepth() < NestedLoop->getLoopDepth()) {
+      std::vector<SCEVHandle> NestedOperands(NestedAR->op_begin(),
+                                             NestedAR->op_end());
+      SCEVHandle NestedARHandle(NestedAR);
+      Operands[0] = NestedAR->getStart();
+      NestedOperands[0] = getAddRecExpr(Operands, L);
+      return getAddRecExpr(NestedOperands, NestedLoop);
+    }
+  }
+
   SCEVAddRecExpr *&Result =
     (*SCEVAddRecExprs)[std::make_pair(L, std::vector<SCEV*>(Operands.begin(),
                                                             Operands.end()))];