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:
/// 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))) {
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;
}
}
+ // 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;
/// 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.
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) {
// 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.
// Analyze the base pointer next.
V = GEPOp->getOperand(0);
- }
+ } while (--MaxLookup);
+
+ // If the chain of expressions is too deep, just return early.
+ return V;
}