lib/Analysis/LazyValueInfo.cpp

   1 //===- LazyValueInfo.cpp - Value constraint analysis ----------------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file defines the interface for lazy computation of value constraint
  11 // information.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #include "llvm/Analysis/LazyValueInfo.h"
  16 #include "llvm/Constants.h"
  17 #include "llvm/Instructions.h"
  18 #include "llvm/Analysis/ConstantFolding.h"
  19 #include "llvm/Target/TargetData.h"
  20 #include "llvm/Support/CFG.h"
  21 #include "llvm/Support/raw_ostream.h"
  22 #include "llvm/ADT/DenseMap.h"
  23 #include "llvm/ADT/PointerIntPair.h"
  24 using namespace llvm;
  25
  26 char LazyValueInfo::ID = 0;
  27 static RegisterPass<LazyValueInfo>
  28 X("lazy-value-info", "Lazy Value Information Analysis", false, true);
  29
  30 namespace llvm {
  31   FunctionPass *createLazyValueInfoPass() { return new LazyValueInfo(); }
  32 }
  33
  34
  35 //===----------------------------------------------------------------------===//
  36 //                               LVILatticeVal
  37 //===----------------------------------------------------------------------===//
  38
  39 /// LVILatticeVal - This is the information tracked by LazyValueInfo for each
  40 /// value.
  41 ///
  42 /// FIXME: This is basically just for bringup, this can be made a lot more rich
  43 /// in the future.
  44 ///
  45 namespace {
  46 class LVILatticeVal {
  47   enum LatticeValueTy {
  48     /// undefined - This LLVM Value has no known value yet.
  49     undefined,
  50     /// constant - This LLVM Value has a specific constant value.
  51     constant,
  52     /// overdefined - This instruction is not known to be constant, and we know
  53     /// it has a value.
  54     overdefined
  55   };
  56
  57   /// Val: This stores the current lattice value along with the Constant* for
  58   /// the constant if this is a 'constant' value.
  59   PointerIntPair<Constant *, 2, LatticeValueTy> Val;
  60
  61 public:
  62   LVILatticeVal() : Val(0, undefined) {}
  63
  64   static LVILatticeVal get(Constant *C) {
  65     LVILatticeVal Res;
  66     Res.markConstant(C);
  67     return Res;
  68   }
  69
  70   bool isUndefined() const   { return Val.getInt() == undefined; }
  71   bool isConstant() const    { return Val.getInt() == constant; }
  72   bool isOverdefined() const { return Val.getInt() == overdefined; }
  73
  74   Constant *getConstant() const {
  75     assert(isConstant() && "Cannot get the constant of a non-constant!");
  76     return Val.getPointer();
  77   }
  78
  79   /// getConstantInt - If this is a constant with a ConstantInt value, return it
  80   /// otherwise return null.
  81   ConstantInt *getConstantInt() const {
  82     if (isConstant())
  83       return dyn_cast<ConstantInt>(getConstant());
  84     return 0;
  85   }
  86
  87   /// markOverdefined - Return true if this is a change in status.
  88   bool markOverdefined() {
  89     if (isOverdefined())
  90       return false;
  91     Val.setInt(overdefined);
  92     return true;
  93   }
  94
  95   /// markConstant - Return true if this is a change in status.
  96   bool markConstant(Constant *V) {
  97     if (isConstant()) {
  98       assert(getConstant() == V && "Marking constant with different value");
  99       return false;
 100     }
 101
 102     assert(isUndefined());
 103     Val.setInt(constant);
 104     assert(V && "Marking constant with NULL");
 105     Val.setPointer(V);
 106     return true;
 107   }
 108
 109   /// mergeIn - Merge the specified lattice value into this one, updating this
 110   /// one and returning true if anything changed.
 111   bool mergeIn(const LVILatticeVal &RHS) {
 112     if (RHS.isUndefined() || isOverdefined()) return false;
 113     if (RHS.isOverdefined()) return markOverdefined();
 114
 115     // RHS must be a constant, we must be undef or constant.
 116     if (isConstant() && getConstant() != RHS.getConstant())
 117       return markOverdefined();
 118     return markConstant(RHS.getConstant());
 119   }
 120
 121 };
 122
 123 } // end anonymous namespace.
 124
 125 namespace llvm {
 126 raw_ostream &operator<<(raw_ostream &OS, const LVILatticeVal &Val) {
 127   if (Val.isUndefined())
 128     return OS << "undefined";
 129   if (Val.isOverdefined())
 130     return OS << "overdefined";
 131   return OS << "constant<" << *Val.getConstant() << '>';
 132 }
 133 }
 134
 135 //===----------------------------------------------------------------------===//
 136 //                            LazyValueInfo Impl
 137 //===----------------------------------------------------------------------===//
 138
 139 bool LazyValueInfo::runOnFunction(Function &F) {
 140   TD = getAnalysisIfAvailable<TargetData>();
 141   // Fully lazy.
 142   return false;
 143 }
 144
 145 void LazyValueInfo::releaseMemory() {
 146   // No caching yet.
 147 }
 148
 149 static LVILatticeVal GetValueInBlock(Value *V, BasicBlock *BB,
 150                                      DenseMap<BasicBlock*, LVILatticeVal> &);
 151
 152 static LVILatticeVal GetValueOnEdge(Value *V, BasicBlock *BBFrom,
 153                                     BasicBlock *BBTo,
 154                               DenseMap<BasicBlock*, LVILatticeVal> &BlockVals) {
 155   // FIXME: Pull edge logic out of jump threading.
 156
 157
 158   if (BranchInst *BI = dyn_cast<BranchInst>(BBFrom->getTerminator())) {
 159     // If this is a conditional branch and only one successor goes to BBTo, then
 160     // we maybe able to infer something from the condition.
 161     if (BI->isConditional() &&
 162         BI->getSuccessor(0) != BI->getSuccessor(1)) {
 163       bool isTrueDest = BI->getSuccessor(0) == BBTo;
 164       assert(BI->getSuccessor(!isTrueDest) == BBTo &&
 165              "BBTo isn't a successor of BBFrom");
 166
 167       // If V is the condition of the branch itself, then we know exactly what
 168       // it is.
 169       if (BI->getCondition() == V)
 170         return LVILatticeVal::get(ConstantInt::get(
 171                                  Type::getInt1Ty(V->getContext()), isTrueDest));
 172
 173       // If the condition of the branch is an equality comparison, we may be
 174       // able to infer the value.
 175       if (ICmpInst *ICI = dyn_cast<ICmpInst>(BI->getCondition()))
 176         if (ICI->isEquality() && ICI->getOperand(0) == V &&
 177             isa<Constant>(ICI->getOperand(1))) {
 178           // We know that V has the RHS constant if this is a true SETEQ or
 179           // false SETNE.
 180           if (isTrueDest == (ICI->getPredicate() == ICmpInst::ICMP_EQ))
 181             return LVILatticeVal::get(cast<Constant>(ICI->getOperand(1)));
 182         }
 183     }
 184   }
 185
 186   // TODO: Info from switch.
 187
 188
 189   // Otherwise see if the value is known in the block.
 190   return GetValueInBlock(V, BBFrom, BlockVals);
 191 }
 192
 193 static LVILatticeVal GetValueInBlock(Value *V, BasicBlock *BB,
 194                               DenseMap<BasicBlock*, LVILatticeVal> &BlockVals) {
 195   // See if we already have a value for this block.
 196   LVILatticeVal &BBLV = BlockVals[BB];
 197
 198   // If we've already computed this block's value, return it.
 199   if (!BBLV.isUndefined())
 200     return BBLV;
 201
 202   // Otherwise, this is the first time we're seeing this block.  Reset the
 203   // lattice value to overdefined, so that cycles will terminate and be
 204   // conservatively correct.
 205   BBLV.markOverdefined();
 206
 207   LVILatticeVal Result;  // Start Undefined.
 208
 209   // If V is live in to BB, see if our predecessors know anything about it.
 210   Instruction *BBI = dyn_cast<Instruction>(V);
 211   if (BBI == 0 || BBI->getParent() != BB) {
 212     unsigned NumPreds = 0;
 213
 214     // Loop over all of our predecessors, merging what we know from them into
 215     // result.
 216     for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) {
 217       Result.mergeIn(GetValueOnEdge(V, *PI, BB, BlockVals));
 218
 219       // If we hit overdefined, exit early.  The BlockVals entry is already set
 220       // to overdefined.
 221       if (Result.isOverdefined())
 222         return Result;
 223       ++NumPreds;
 224     }
 225
 226     // If this is the entry block, we must be asking about an argument.  The
 227     // value is overdefined.
 228     if (NumPreds == 0 && BB == &BB->getParent()->front()) {
 229       assert(isa<Argument>(V) && "Unknown live-in to the entry block");
 230       Result.markOverdefined();
 231       return Result;
 232     }
 233
 234     // Return the merged value, which is more precise than 'overdefined'.
 235     assert(!Result.isOverdefined());
 236     return BlockVals[BB] = Result;
 237   }
 238
 239   // If this value is defined by an instruction in this block, we have to
 240   // process it here somehow or return overdefined.
 241   if (PHINode *PN = dyn_cast<PHINode>(BBI)) {
 242     (void)PN;
 243     // TODO: PHI Translation in preds.
 244   } else {
 245
 246   }
 247
 248   Result.markOverdefined();
 249   return BlockVals[BB] = Result;
 250 }
 251
 252
 253 Constant *LazyValueInfo::getConstant(Value *V, BasicBlock *BB) {
 254   // If already a constant, return it.
 255   if (Constant *VC = dyn_cast<Constant>(V))
 256     return VC;
 257
 258   DenseMap<BasicBlock*, LVILatticeVal> BlockValues;
 259
 260   errs() << "Getting value " << *V << " at end of block '"
 261          << BB->getName() << "'\n";
 262   LVILatticeVal Result = GetValueInBlock(V, BB, BlockValues);
 263
 264   errs() << "  Result = " << Result << "\n";
 265
 266   if (Result.isConstant())
 267     return Result.getConstant();
 268   return 0;
 269 }
 270
 271 /// isEqual - Determine whether the specified value is known to be equal or
 272 /// not-equal to the specified constant at the end of the specified block.
 273 LazyValueInfo::Tristate
 274 LazyValueInfo::isEqual(Value *V, Constant *C, BasicBlock *BB) {
 275   // If already a constant, we can use constant folding.
 276   if (Constant *VC = dyn_cast<Constant>(V)) {
 277     // Ignore FP for now.  TODO, consider what form of equality we want.
 278     if (C->getType()->isFPOrFPVector())
 279       return Unknown;
 280
 281     Constant *Res = ConstantFoldCompareInstOperands(ICmpInst::ICMP_EQ, VC,C,TD);
 282     if (ConstantInt *ResCI = dyn_cast<ConstantInt>(Res))
 283       return ResCI->isZero() ? No : Yes;
 284   }
 285
 286   // Not a very good implementation.
 287   return Unknown;
 288 }
 289
 290