diff --git a/lib/Analysis/ScalarEvolution.cpp b/lib/Analysis/ScalarEvolution.cpp
index 240126e..358d591 100644
--- a/lib/Analysis/ScalarEvolution.cpp
+++ b/lib/Analysis/ScalarEvolution.cpp
@@ -1552,9 +1552,11 @@
                                              AddRec->op_end());
       AddRecOps[0] = getAddExpr(LIOps);
 
-      // It's tempting to propagate NUW/NSW flags here, but nuw/nsw addition
-      // is not associative so this isn't necessarily safe.
-      const SCEV *NewRec = getAddRecExpr(AddRecOps, AddRecLoop);
+      // Build the new addrec. Propagate the NUW and NSW flags if both the
+      // outer add and the inner addrec are guaranteed to have no overflow.
+      const SCEV *NewRec = getAddRecExpr(AddRecOps, AddRecLoop,
+                                         HasNUW && AddRec->hasNoUnsignedWrap(),
+                                         HasNSW && AddRec->hasNoSignedWrap());
 
       // If all of the other operands were loop invariant, we are done.
       if (Ops.size() == 1) return NewRec;
@@ -1754,11 +1756,11 @@
       for (unsigned i = 0, e = AddRec->getNumOperands(); i != e; ++i)
         NewOps.push_back(getMulExpr(Scale, AddRec->getOperand(i)));
 
-      // It's tempting to propagate the NSW flag here, but nsw multiplication
-      // is not associative so this isn't necessarily safe.
+      // Build the new addrec. Propagate the NUW and NSW flags if both the
+      // outer mul and the inner addrec are guaranteed to have no overflow.
       const SCEV *NewRec = getAddRecExpr(NewOps, AddRec->getLoop(),
                                          HasNUW && AddRec->hasNoUnsignedWrap(),
-                                         /*HasNSW=*/false);
+                                         HasNSW && AddRec->hasNoSignedWrap());
 
       // If all of the other operands were loop invariant, we are done.
       if (Ops.size() == 1) return NewRec;
@@ -2758,15 +2760,49 @@
   return getUnknown(PN);
 }
 
+/// UseFlag - When creating an operator with operands L and R based on an
+/// LLVM IR instruction in basic block BB where the instruction has
+/// nsw, nuw, or inbounds, test whether the corresponding flag can be
+/// set for the resulting SCEV.
+static bool
+UseFlag(bool Flag, const SCEV *L, const SCEV *R, const Value *Inst) {
+  // If the flag is not set, don't use it. This is included here to reduce
+  // clutter in the callers.
+  if (!Flag)
+    return false;
+
+  // Determine the block which contains the instruction with the flag.
+  const Instruction *I = dyn_cast<Instruction>(Inst);
+  if (!I)
+    return false;
+  const BasicBlock *BB = I->getParent();
+
+  // Handle an easy case: test if exactly one of the operands is an addrec
+  // and that the instruction is trivially control-equivalent to the addrec's
+  // loop's header.
+  if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(L)) {
+    if (!isa<SCEVAddRecExpr>(R) &&
+        AR->getLoop()->getHeader() == BB)
+      return true;
+  } else if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(R)) {
+    if (AR->getLoop()->getHeader() == BB)
+      return true;
+  }
+
+  return false;
+}
+
 /// createNodeForGEP - Expand GEP instructions into add and multiply
 /// operations. This allows them to be analyzed by regular SCEV code.
 ///
 const SCEV *ScalarEvolution::createNodeForGEP(GEPOperator *GEP) {
 
-  // Don't transfer the inbounds flag from the GEP instruction to the
-  // Add expression, because the Instruction may be guarded by control
-  // flow and the no-overflow bits may not be valid for the expression in
-  // any context.
+  // Don't blindly transfer the inbounds flag from the GEP instruction to the
+  // Add expression, because the Instruction may be guarded by control flow
+  // and the no-overflow bits may not be valid for the expression in any
+  // context. However, in the special case where the GEP is in the loop header,
+  // we know it's trivially control-equivalent to any addrecs for that loop.
+  bool InBounds = GEP->isInBounds();
 
   const Type *IntPtrTy = getEffectiveSCEVType(GEP->getType());
   Value *Base = GEP->getOperand(0);
@@ -2783,23 +2819,49 @@
     if (const StructType *STy = dyn_cast<StructType>(*GTI++)) {
       // For a struct, add the member offset.
       unsigned FieldNo = cast<ConstantInt>(Index)->getZExtValue();
-      TotalOffset = getAddExpr(TotalOffset,
-                               getOffsetOfExpr(STy, FieldNo),
-                               /*HasNUW=*/false, /*HasNSW=*/false);
+      const SCEV *FieldOffset = getOffsetOfExpr(STy, FieldNo);
+
+      // Test if the GEP has the inbounds keyword and is control-equivalent
+      // to the addrec.
+      bool HasNUW = UseFlag(InBounds, TotalOffset, FieldOffset, GEP);
+
+      // Add the field offset to the running total offset.
+      TotalOffset = getAddExpr(TotalOffset, FieldOffset,
+                               HasNUW, /*HasNSW=*/false);
     } else {
       // For an array, add the element offset, explicitly scaled.
-      const SCEV *LocalOffset = getSCEV(Index);
+      const SCEV *ElementSize = getSizeOfExpr(*GTI);
+      const SCEV *IndexS = getSCEV(Index);
       // Getelementptr indices are signed.
-      LocalOffset = getTruncateOrSignExtend(LocalOffset, IntPtrTy);
-      // Lower "inbounds" GEPs to NSW arithmetic.
-      LocalOffset = getMulExpr(LocalOffset, getSizeOfExpr(*GTI),
-                               /*HasNUW=*/false, /*HasNSW=*/false);
+      IndexS = getTruncateOrSignExtend(IndexS, IntPtrTy);
+
+      // Test if the GEP has the inbounds keyword and is control-equivalent
+      // to the addrec.
+      bool HasNUW = UseFlag(InBounds, IndexS, ElementSize, GEP);
+
+      // Multiply the index by the element size to compute the element offset.
+      const SCEV *LocalOffset = getMulExpr(IndexS, ElementSize,
+                                           HasNUW, /*HasNSW=*/false);
+
+      // Test if the GEP has the inbounds keyword and is control-equivalent
+      // to the addrec.
+      HasNUW = UseFlag(InBounds, TotalOffset, LocalOffset, GEP);
+
+      // Add the element offset to the running total offset.
       TotalOffset = getAddExpr(TotalOffset, LocalOffset,
-                               /*HasNUW=*/false, /*HasNSW=*/false);
+                               HasNUW, /*HasNSW=*/false);
     }
   }
-  return getAddExpr(getSCEV(Base), TotalOffset,
-                    /*HasNUW=*/false, /*HasNSW=*/false);
+
+  // Get the SCEV for the GEP base.
+  const SCEV *BaseS = getSCEV(Base);
+
+  // Test if the GEP has the inbounds keyword and is control-equivalent
+  // to the addrec.
+  bool HasNUW = UseFlag(InBounds, BaseS, TotalOffset, GEP);
+
+  // Add the total offset from all the GEP indices to the base.
+  return getAddExpr(BaseS, TotalOffset, HasNUW, /*HasNSW=*/false);
 }
 
 /// GetMinTrailingZeros - Determine the minimum number of zero bits that S is
@@ -3191,18 +3253,30 @@
 
   Operator *U = cast<Operator>(V);
   switch (Opcode) {
-  case Instruction::Add:
+  case Instruction::Add: {
+    const SCEV *LHS = getSCEV(U->getOperand(0));
+    const SCEV *RHS = getSCEV(U->getOperand(1));
+
     // Don't transfer the NSW and NUW bits from the Add instruction to the
-    // Add expression, because the Instruction may be guarded by control
-    // flow and the no-overflow bits may not be valid for the expression in
-    // any context.
-    return getAddExpr(getSCEV(U->getOperand(0)),
-                      getSCEV(U->getOperand(1)));
-  case Instruction::Mul:
+    // Add expression unless we can prove that it's safe.
+    AddOperator *Add = cast<AddOperator>(U);
+    bool HasNUW = UseFlag(Add->hasNoUnsignedWrap(), LHS, RHS, Add);
+    bool HasNSW = UseFlag(Add->hasNoSignedWrap(), LHS, RHS, Add);
+
+    return getAddExpr(LHS, RHS, HasNUW, HasNSW);
+  }
+  case Instruction::Mul: {
+    const SCEV *LHS = getSCEV(U->getOperand(0));
+    const SCEV *RHS = getSCEV(U->getOperand(1));
+
     // Don't transfer the NSW and NUW bits from the Mul instruction to the
-    // Mul expression, as with Add.
-    return getMulExpr(getSCEV(U->getOperand(0)),
-                      getSCEV(U->getOperand(1)));
+    // Mul expression unless we can prove that it's safe.
+    MulOperator *Mul = cast<MulOperator>(U);
+    bool HasNUW = UseFlag(Mul->hasNoUnsignedWrap(), LHS, RHS, Mul);
+    bool HasNSW = UseFlag(Mul->hasNoSignedWrap(), LHS, RHS, Mul);
+
+    return getMulExpr(LHS, RHS, HasNUW, HasNSW);
+  }
   case Instruction::UDiv:
     return getUDivExpr(getSCEV(U->getOperand(0)),
                        getSCEV(U->getOperand(1)));