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