X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FAnalysis%2FScalarEvolutionNormalization.cpp;h=b238fe43cc608a2b302f7d8b54fa555ee60e79d7;hb=12af22e8cc217827cf4f118b0f5e4ebbda9925ae;hp=c66ecd6e872794942b5f032d96b246a7a4e9dbd0;hpb=7f1653a7aee0c30adfa948ad5bdbf12c7cc1e519;p=oota-llvm.git

diff --git a/lib/Analysis/ScalarEvolutionNormalization.cpp b/lib/Analysis/ScalarEvolutionNormalization.cpp
index c66ecd6e872..b238fe43cc6 100644
--- a/lib/Analysis/ScalarEvolutionNormalization.cpp
+++ b/lib/Analysis/ScalarEvolutionNormalization.cpp
@@ -12,7 +12,7 @@
 //
 //===----------------------------------------------------------------------===//
 
-#include "llvm/Analysis/Dominators.h"
+#include "llvm/IR/Dominators.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
 #include "llvm/Analysis/ScalarEvolutionNormalization.h"
@@ -113,14 +113,24 @@ TransformImpl(const SCEV *S, Instruction *User, Value *OperandValToReplace) {
     // Transform each operand.
     for (SCEVNAryExpr::op_iterator I = AR->op_begin(), E = AR->op_end();
          I != E; ++I) {
-      Operands.push_back(TransformSubExpr(*I, LUser, 0));
+      Operands.push_back(TransformSubExpr(*I, LUser, nullptr));
     }
     // Conservatively use AnyWrap until/unless we need FlagNW.
     const SCEV *Result = SE.getAddRecExpr(Operands, L, SCEV::FlagAnyWrap);
     switch (Kind) {
-    default: llvm_unreachable("Unexpected transform name!");
     case NormalizeAutodetect:
-      if (IVUseShouldUsePostIncValue(User, OperandValToReplace, L, &DT)) {
+      // Normalize this SCEV by subtracting the expression for the final step.
+      // We only allow affine AddRecs to be normalized, otherwise we would not
+      // be able to correctly denormalize.
+      // e.g. {1,+,3,+,2} == {-2,+,1,+,2} + {3,+,2}
+      // Normalized form:   {-2,+,1,+,2}
+      // Denormalized form: {1,+,3,+,2}
+      //
+      // However, denormalization would use a different step expression than
+      // normalization (see getPostIncExpr), generating the wrong final
+      // expression: {-2,+,1,+,2} + {1,+,2} => {-1,+,3,+,2}
+      if (AR->isAffine() &&
+          IVUseShouldUsePostIncValue(User, OperandValToReplace, L, &DT)) {
         const SCEV *TransformedStep =
           TransformSubExpr(AR->getStepRecurrence(SE),
                            User, OperandValToReplace);
@@ -137,6 +147,20 @@ TransformImpl(const SCEV *S, Instruction *User, Value *OperandValToReplace) {
 #endif
       break;
     case Normalize:
+      // We want to normalize step expression, because otherwise we might not be
+      // able to denormalize to the original expression.
+      //
+      // Here is an example what will happen if we don't normalize step:
+      //  ORIGINAL ISE:
+      //    {(100 /u {1,+,1}<%bb16>),+,(100 /u {1,+,1}<%bb16>)}<%bb25>
+      //  NORMALIZED ISE:
+      //    {((-1 * (100 /u {1,+,1}<%bb16>)) + (100 /u {0,+,1}<%bb16>)),+,
+      //     (100 /u {0,+,1}<%bb16>)}<%bb25>
+      //  DENORMALIZED BACK ISE:
+      //    {((2 * (100 /u {1,+,1}<%bb16>)) + (-1 * (100 /u {2,+,1}<%bb16>))),+,
+      //     (100 /u {1,+,1}<%bb16>)}<%bb25>
+      //  Note that the initial value changes after normalization +
+      //  denormalization, which isn't correct.
       if (Loops.count(L)) {
         const SCEV *TransformedStep =
           TransformSubExpr(AR->getStepRecurrence(SE),
@@ -150,8 +174,14 @@ TransformImpl(const SCEV *S, Instruction *User, Value *OperandValToReplace) {
 #endif
       break;
     case Denormalize:
-      if (Loops.count(L))
-        Result = cast<SCEVAddRecExpr>(Result)->getPostIncExpr(SE);
+      // Here we want to normalize step expressions for the same reasons, as
+      // stated above.
+      if (Loops.count(L)) {
+        const SCEV *TransformedStep =
+          TransformSubExpr(AR->getStepRecurrence(SE),
+                           User, OperandValToReplace);
+        Result = SE.getAddExpr(Result, TransformedStep);
+      }
       break;
     }
     return Result;
@@ -191,7 +221,6 @@ TransformImpl(const SCEV *S, Instruction *User, Value *OperandValToReplace) {
   }
 
   llvm_unreachable("Unexpected SCEV kind!");
-  return 0;
 }
 
 /// Manage recursive transformation across an expression DAG. Revisiting
@@ -212,7 +241,7 @@ TransformSubExpr(const SCEV *S, Instruction *User, Value *OperandValToReplace) {
 }
 
 /// Top level driver for transforming an expression DAG into its requested
-/// post-inc form (either "Normalized" or "Denormalized".
+/// post-inc form (either "Normalized" or "Denormalized").
 const SCEV *llvm::TransformForPostIncUse(TransformKind Kind,
                                          const SCEV *S,
                                          Instruction *User,