Be more careful when transforming | to +. Patch from Wojciech Matyjewicz.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@44248 91177308-0d34-0410-b5e6-96231b3b80d8

diff --git a/lib/Analysis/ScalarEvolution.cpp b/lib/Analysis/ScalarEvolution.cpp
index 6e506174cfb1563d206dc19463b7586f0fa781a5..e7bb9ab80c205a0c70a6b36be0caac0630f5eee2 100644 (file)
--- a/lib/Analysis/ScalarEvolution.cpp
+++ b/lib/Analysis/ScalarEvolution.cpp
@@ -1484,25 +1484,27 @@ SCEVHandle ScalarEvolutionsImpl::createSCEV(Value *V) {
     case Instruction::SDiv:
       return SE.getSDivExpr(getSCEV(I->getOperand(0)),
                             getSCEV(I->getOperand(1)));
-      break;
-
     case Instruction::Sub:
       return SE.getMinusSCEV(getSCEV(I->getOperand(0)),
                              getSCEV(I->getOperand(1)));
     case Instruction::Or:
       // If the RHS of the Or is a constant, we may have something like:
-      // X*4+1 which got turned into X*4|1.  Handle this as an add so loop
+      // X*4+1 which got turned into X*4|1.  Handle this as an Add so loop
       // optimizations will transparently handle this case.
+      //
+      // In order for this transformation to be safe, the LHS must be of the
+      // form X*(2^n) and the Or constant must be less than 2^n.
+
       if (ConstantInt *CI = dyn_cast<ConstantInt>(I->getOperand(1))) {
         SCEVHandle LHS = getSCEV(I->getOperand(0));
         APInt CommonFact(GetConstantFactor(LHS));
         assert(!CommonFact.isMinValue() &&
                "Common factor should at least be 1!");
-        if (CommonFact.ugt(CI->getValue())) {
-          // If the LHS is a multiple that is larger than the RHS, use +.
+        const APInt &CIVal = CI->getValue();
+        if (CommonFact.countTrailingZeros() >=
+            (CIVal.getBitWidth() - CIVal.countLeadingZeros()))
           return SE.getAddExpr(LHS,
                                getSCEV(I->getOperand(1)));
-        }
       }
       break;
     case Instruction::Xor:

diff --git a/test/Analysis/ScalarEvolution/2007-11-18-OrInstruction.ll b/test/Analysis/ScalarEvolution/2007-11-18-OrInstruction.ll
new file mode 100644 (file)
index 0000000..830a402
--- /dev/null
+++ b/test/Analysis/ScalarEvolution/2007-11-18-OrInstruction.ll
@@ -0,0 +1,18 @@
+; RUN: llvm-as < %s | opt -analyze -scalar-evolution 2>&1 | grep -e '-->  %b'
+; PR1810
+
+define void @fun() {
+entry:
+        br label %header
+header:
+        %i = phi i32 [ 1, %entry ], [ %i.next, %body ]
+        %cond = icmp eq i32 %i, 10
+        br i1 %cond, label %exit, label %body
+body:
+        %a = mul i32 %i, 5
+        %b = or i32 %a, 1
+        %i.next = add i32 %i, 1
+        br label %header
+exit:        
+        ret void
+}