Remove isPod() from DenseMapInfo, splitting it out to its own

[oota-llvm.git] / lib / Analysis / ValueTracking.cpp

diff --git a/lib/Analysis/ValueTracking.cpp b/lib/Analysis/ValueTracking.cpp
index 5439bbff269e6047aec4037d74866bb2d93e7cf8..22c6e3b6f121145c7579d87186e6072106b4bc23 100644 (file)
--- a/lib/Analysis/ValueTracking.cpp
+++ b/lib/Analysis/ValueTracking.cpp
@@ -659,7 +659,7 @@ unsigned llvm::ComputeNumSignBits(Value *V, const TargetData *TD,
   switch (Operator::getOpcode(V)) {
   default: break;
   case Instruction::SExt:
-    Tmp = TyBits-cast<IntegerType>(U->getOperand(0)->getType())->getBitWidth();
+    Tmp = TyBits - U->getOperand(0)->getType()->getScalarSizeInBits();
     return ComputeNumSignBits(U->getOperand(0), TD, Depth+1) + Tmp;
     
   case Instruction::AShr:
@@ -950,11 +950,20 @@ bool llvm::CannotBeNegativeZero(const Value *V, unsigned Depth) {
 
 
 /// GetLinearExpression - Analyze the specified value as a linear expression:
-/// "A*V + B".  Return the scale and offset values as APInts and return V as a
-/// Value*.  The incoming Value is known to be a scalar integer.
+/// "A*V + B", where A and B are constant integers.  Return the scale and offset
+/// values as APInts and return V as a Value*.  The incoming Value is known to
+/// have IntegerType.  Note that this looks through extends, so the high bits
+/// may not be represented in the result.
 static Value *GetLinearExpression(Value *V, APInt &Scale, APInt &Offset,
-                                  const TargetData *TD) {
+                                  const TargetData *TD, unsigned Depth) {
   assert(isa<IntegerType>(V->getType()) && "Not an integer value");
+
+  // Limit our recursion depth.
+  if (Depth == 6) {
+    Scale = 1;
+    Offset = 0;
+    return V;
+  }
   
   if (BinaryOperator *BOp = dyn_cast<BinaryOperator>(V)) {
     if (ConstantInt *RHSC = dyn_cast<ConstantInt>(BOp->getOperand(1))) {
@@ -967,16 +976,16 @@ static Value *GetLinearExpression(Value *V, APInt &Scale, APInt &Offset,
           break;
         // FALL THROUGH.
       case Instruction::Add:
-        V = GetLinearExpression(BOp->getOperand(0), Scale, Offset, TD);
+        V = GetLinearExpression(BOp->getOperand(0), Scale, Offset, TD, Depth+1);
         Offset += RHSC->getValue();
         return V;
       case Instruction::Mul:
-        V = GetLinearExpression(BOp->getOperand(0), Scale, Offset, TD);
+        V = GetLinearExpression(BOp->getOperand(0), Scale, Offset, TD, Depth+1);
         Offset *= RHSC->getValue();
         Scale *= RHSC->getValue();
         return V;
       case Instruction::Shl:
-        V = GetLinearExpression(BOp->getOperand(0), Scale, Offset, TD);
+        V = GetLinearExpression(BOp->getOperand(0), Scale, Offset, TD, Depth+1);
         Offset <<= RHSC->getValue().getLimitedValue();
         Scale <<= RHSC->getValue().getLimitedValue();
         return V;
@@ -984,6 +993,20 @@ static Value *GetLinearExpression(Value *V, APInt &Scale, APInt &Offset,
     }
   }
   
+  // Since clients don't care about the high bits of the value, just scales and
+  // offsets, we can look through extensions.
+  if (isa<SExtInst>(V) || isa<ZExtInst>(V)) {
+    Value *CastOp = cast<CastInst>(V)->getOperand(0);
+    unsigned OldWidth = Scale.getBitWidth();
+    unsigned SmallWidth = CastOp->getType()->getPrimitiveSizeInBits();
+    Scale.trunc(SmallWidth);
+    Offset.trunc(SmallWidth);
+    Value *Result = GetLinearExpression(CastOp, Scale, Offset, TD, Depth+1);
+    Scale.zext(OldWidth);
+    Offset.zext(OldWidth);
+    return Result;
+  }
+  
   Scale = 1;
   Offset = 0;
   return V;
@@ -993,6 +1016,11 @@ static Value *GetLinearExpression(Value *V, APInt &Scale, APInt &Offset,
 /// into a base pointer with a constant offset and a number of scaled symbolic
 /// offsets.
 ///
+/// The scaled symbolic offsets (represented by pairs of a Value* and a scale in
+/// the VarIndices vector) are Value*'s that are known to be scaled by the
+/// specified amount, but which may have other unrepresented high bits. As such,
+/// the gep cannot necessarily be reconstructed from its decomposed form.
+///
 /// When TargetData is around, this function is capable of analyzing everything
 /// that Value::getUnderlyingObject() can look through.  When not, it just looks
 /// through pointer casts.
@@ -1000,9 +1028,11 @@ static Value *GetLinearExpression(Value *V, APInt &Scale, APInt &Offset,
 const Value *llvm::DecomposeGEPExpression(const Value *V, int64_t &BaseOffs,
                  SmallVectorImpl<std::pair<const Value*, int64_t> > &VarIndices,
                                           const TargetData *TD) {
-  // FIXME: Should limit depth like getUnderlyingObject?
+  // Limit recursion depth to limit compile time in crazy cases.
+  unsigned MaxLookup = 6;
+  
   BaseOffs = 0;
-  while (1) {
+  do {
     // See if this is a bitcast or GEP.
     const Operator *Op = dyn_cast<Operator>(V);
     if (Op == 0) {
@@ -1067,7 +1097,7 @@ const Value *llvm::DecomposeGEPExpression(const Value *V, int64_t &BaseOffs,
       // Use GetLinearExpression to decompose the index into a C1*V+C2 form.
       unsigned Width = cast<IntegerType>(Index->getType())->getBitWidth();
       APInt IndexScale(Width, 0), IndexOffset(Width, 0);
-      Index = GetLinearExpression(Index, IndexScale, IndexOffset, TD);
+      Index = GetLinearExpression(Index, IndexScale, IndexOffset, TD, 0);
       
       // The GEP index scale ("Scale") scales C1*V+C2, yielding (C1*V+C2)*Scale.
       // This gives us an aggregate computation of (C1*Scale)*V + C2*Scale.
@@ -1100,7 +1130,10 @@ const Value *llvm::DecomposeGEPExpression(const Value *V, int64_t &BaseOffs,
     
     // Analyze the base pointer next.
     V = GEPOp->getOperand(0);
-  }
+  } while (--MaxLookup);
+  
+  // If the chain of expressions is too deep, just return early.
+  return V;
 }