From d281ed2d03654b9cdb290a2d7c73dfe7b826e554 Mon Sep 17 00:00:00 2001
From: Dan Gohman <gohman@apple.com>
Date: Fri, 18 Dec 2009 02:09:29 +0000
Subject: [PATCH] Preserve NSW information in more places.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@91656 91177308-0d34-0410-b5e6-96231b3b80d8
---
 include/llvm/Analysis/ScalarEvolution.h |  2 +-
 lib/Analysis/ScalarEvolution.cpp        | 27 +++++++++++++++++--------
 2 files changed, 20 insertions(+), 9 deletions(-)

diff --git a/include/llvm/Analysis/ScalarEvolution.h b/include/llvm/Analysis/ScalarEvolution.h
index 4aa3dfa55ce..6f57c741fe5 100644
--- a/include/llvm/Analysis/ScalarEvolution.h
+++ b/include/llvm/Analysis/ScalarEvolution.h
@@ -243,7 +243,7 @@ namespace llvm {
 
     /// createNodeForGEP - Provide the special handling we need to analyze GEP
     /// SCEVs.
-    const SCEV *createNodeForGEP(Operator *GEP);
+    const SCEV *createNodeForGEP(GEPOperator *GEP);
 
     /// computeSCEVAtScope - Implementation code for getSCEVAtScope; called
     /// at most once for each SCEV+Loop pair.
diff --git a/lib/Analysis/ScalarEvolution.cpp b/lib/Analysis/ScalarEvolution.cpp
index babfc858dd5..551c25f07c3 100644
--- a/lib/Analysis/ScalarEvolution.cpp
+++ b/lib/Analysis/ScalarEvolution.cpp
@@ -1460,7 +1460,9 @@ const SCEV *ScalarEvolution::getAddExpr(SmallVectorImpl<const SCEV *> &Ops,
                                            AddRec->op_end());
       AddRecOps[0] = getAddExpr(LIOps);
 
-      const SCEV *NewRec = getAddRecExpr(AddRecOps, AddRec->getLoop());
+      const SCEV *NewRec = getAddRecExpr(AddRecOps, AddRec->getLoop(),
+                                         AddRec->hasNoUnsignedWrap() && HasNUW,
+                                         AddRec->hasNoSignedWrap() && HasNSW);
       // If all of the other operands were loop invariant, we are done.
       if (Ops.size() == 1) return NewRec;
 
@@ -1636,7 +1638,9 @@ const SCEV *ScalarEvolution::getMulExpr(SmallVectorImpl<const SCEV *> &Ops,
         }
       }
 
-      const SCEV *NewRec = getAddRecExpr(NewOps, AddRec->getLoop());
+      const SCEV *NewRec = getAddRecExpr(NewOps, AddRec->getLoop(),
+                                         AddRec->hasNoUnsignedWrap() && HasNUW,
+                                         AddRec->hasNoSignedWrap() && HasNSW);
 
       // If all of the other operands were loop invariant, we are done.
       if (Ops.size() == 1) return NewRec;
@@ -2592,8 +2596,9 @@ const SCEV *ScalarEvolution::createNodeForPHI(PHINode *PN) {
 /// createNodeForGEP - Expand GEP instructions into add and multiply
 /// operations. This allows them to be analyzed by regular SCEV code.
 ///
-const SCEV *ScalarEvolution::createNodeForGEP(Operator *GEP) {
+const SCEV *ScalarEvolution::createNodeForGEP(GEPOperator *GEP) {
 
+  bool InBounds = GEP->isInBounds();
   const Type *IntPtrTy = getEffectiveSCEVType(GEP->getType());
   Value *Base = GEP->getOperand(0);
   // Don't attempt to analyze GEPs over unsized objects.
@@ -2610,18 +2615,24 @@ const SCEV *ScalarEvolution::createNodeForGEP(Operator *GEP) {
       // For a struct, add the member offset.
       unsigned FieldNo = cast<ConstantInt>(Index)->getZExtValue();
       TotalOffset = getAddExpr(TotalOffset,
-                               getFieldOffsetExpr(STy, FieldNo));
+                               getFieldOffsetExpr(STy, FieldNo),
+                               /*HasNUW=*/false, /*HasNSW=*/InBounds);
     } else {
       // For an array, add the element offset, explicitly scaled.
       const SCEV *LocalOffset = getSCEV(Index);
       if (!isa<PointerType>(LocalOffset->getType()))
         // Getelementptr indicies are signed.
         LocalOffset = getTruncateOrSignExtend(LocalOffset, IntPtrTy);
-      LocalOffset = getMulExpr(LocalOffset, getAllocSizeExpr(*GTI));
-      TotalOffset = getAddExpr(TotalOffset, LocalOffset);
+      // Lower "inbounds" GEPs to NSW arithmetic.
+      bool HasNSW = GEP->isInBounds();
+      LocalOffset = getMulExpr(LocalOffset, getAllocSizeExpr(*GTI),
+                               /*HasNUW=*/false, /*HasNSW=*/InBounds);
+      TotalOffset = getAddExpr(TotalOffset, LocalOffset,
+                               /*HasNUW=*/false, /*HasNSW=*/InBounds);
     }
   }
-  return getAddExpr(getSCEV(Base), TotalOffset);
+  return getAddExpr(getSCEV(Base), TotalOffset,
+                    /*HasNUW=*/false, /*HasNSW=*/InBounds);
 }
 
 /// GetMinTrailingZeros - Determine the minimum number of zero bits that S is
@@ -3130,7 +3141,7 @@ const SCEV *ScalarEvolution::createSCEV(Value *V) {
     // expressions we handle are GEPs and address literals.
 
   case Instruction::GetElementPtr:
-    return createNodeForGEP(U);
+    return createNodeForGEP(cast<GEPOperator>(U));
 
   case Instruction::PHI:
     return createNodeForPHI(cast<PHINode>(U));
-- 
2.34.1