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
  55     /// notconstant - This LLVM value is known to not have the specified value.
  56     notconstant,
  57
  58     /// overdefined - This instruction is not known to be constant, and we know
  59     /// it has a value.
  60     overdefined
  61   };
  62
  63   /// Val: This stores the current lattice value along with the Constant* for
  64   /// the constant if this is a 'constant' or 'notconstant' value.
  65   PointerIntPair<Constant *, 2, LatticeValueTy> Val;
  66
  67 public:
  68   LVILatticeVal() : Val(0, undefined) {}
  69
  70   static LVILatticeVal get(Constant *C) {
  71     LVILatticeVal Res;
  72     Res.markConstant(C);
  73     return Res;
  74   }
  75   static LVILatticeVal getNot(Constant *C) {
  76     LVILatticeVal Res;
  77     Res.markNotConstant(C);
  78     return Res;
  79   }
  80
  81   bool isUndefined() const   { return Val.getInt() == undefined; }
  82   bool isConstant() const    { return Val.getInt() == constant; }
  83   bool isNotConstant() const { return Val.getInt() == notconstant; }
  84   bool isOverdefined() const { return Val.getInt() == overdefined; }
  85
  86   Constant *getConstant() const {
  87     assert(isConstant() && "Cannot get the constant of a non-constant!");
  88     return Val.getPointer();
  89   }
  90
  91   Constant *getNotConstant() const {
  92     assert(isNotConstant() && "Cannot get the constant of a non-notconstant!");
  93     return Val.getPointer();
  94   }
  95
  96   /// markOverdefined - Return true if this is a change in status.
  97   bool markOverdefined() {
  98     if (isOverdefined())
  99       return false;
 100     Val.setInt(overdefined);
 101     return true;
 102   }
 103
 104   /// markConstant - Return true if this is a change in status.
 105   bool markConstant(Constant *V) {
 106     if (isConstant()) {
 107       assert(getConstant() == V && "Marking constant with different value");
 108       return false;
 109     }
 110
 111     assert(isUndefined());
 112     Val.setInt(constant);
 113     assert(V && "Marking constant with NULL");
 114     Val.setPointer(V);
 115     return true;
 116   }
 117
 118   /// markNotConstant - Return true if this is a change in status.
 119   bool markNotConstant(Constant *V) {
 120     if (isNotConstant()) {
 121       assert(getNotConstant() == V && "Marking !constant with different value");
 122       return false;
 123     }
 124
 125     if (isConstant())
 126       assert(getConstant() != V && "Marking not constant with different value");
 127     else
 128       assert(isUndefined());
 129
 130     Val.setInt(notconstant);
 131     assert(V && "Marking constant with NULL");
 132     Val.setPointer(V);
 133     return true;
 134   }
 135
 136   /// mergeIn - Merge the specified lattice value into this one, updating this
 137   /// one and returning true if anything changed.
 138   bool mergeIn(const LVILatticeVal &RHS) {
 139     if (RHS.isUndefined() || isOverdefined()) return false;
 140     if (RHS.isOverdefined()) return markOverdefined();
 141
 142     if (RHS.isNotConstant()) {
 143       if (isNotConstant()) {
 144         if (getNotConstant() != RHS.getNotConstant())
 145           return markOverdefined();
 146         return false;
 147       }
 148       if (isConstant() && getConstant() != RHS.getNotConstant())
 149         return markOverdefined();
 150       return markNotConstant(RHS.getNotConstant());
 151     }
 152
 153     // RHS must be a constant, we must be undef or constant.
 154     if (isConstant() && getConstant() != RHS.getConstant())
 155       return markOverdefined();
 156     return markConstant(RHS.getConstant());
 157   }
 158
 159 };
 160
 161 } // end anonymous namespace.
 162
 163 namespace llvm {
 164 raw_ostream &operator<<(raw_ostream &OS, const LVILatticeVal &Val) {
 165   if (Val.isUndefined())
 166     return OS << "undefined";
 167   if (Val.isOverdefined())
 168     return OS << "overdefined";
 169
 170   if (Val.isNotConstant())
 171     return OS << "notconstant<" << *Val.getNotConstant() << '>';
 172   return OS << "constant<" << *Val.getConstant() << '>';
 173 }
 174 }
 175
 176 //===----------------------------------------------------------------------===//
 177 //                            LazyValueInfo Impl
 178 //===----------------------------------------------------------------------===//
 179
 180 bool LazyValueInfo::runOnFunction(Function &F) {
 181   TD = getAnalysisIfAvailable<TargetData>();
 182   // Fully lazy.
 183   return false;
 184 }
 185
 186 void LazyValueInfo::releaseMemory() {
 187   // No caching yet.
 188 }
 189
 190 static LVILatticeVal GetValueInBlock(Value *V, BasicBlock *BB,
 191                                      DenseMap<BasicBlock*, LVILatticeVal> &);
 192
 193 static LVILatticeVal GetValueOnEdge(Value *V, BasicBlock *BBFrom,
 194                                     BasicBlock *BBTo,
 195                               DenseMap<BasicBlock*, LVILatticeVal> &BlockVals) {
 196   // FIXME: Pull edge logic out of jump threading.
 197
 198
 199   if (BranchInst *BI = dyn_cast<BranchInst>(BBFrom->getTerminator())) {
 200     // If this is a conditional branch and only one successor goes to BBTo, then
 201     // we maybe able to infer something from the condition.
 202     if (BI->isConditional() &&
 203         BI->getSuccessor(0) != BI->getSuccessor(1)) {
 204       bool isTrueDest = BI->getSuccessor(0) == BBTo;
 205       assert(BI->getSuccessor(!isTrueDest) == BBTo &&
 206              "BBTo isn't a successor of BBFrom");
 207
 208       // If V is the condition of the branch itself, then we know exactly what
 209       // it is.
 210       if (BI->getCondition() == V)
 211         return LVILatticeVal::get(ConstantInt::get(
 212                                  Type::getInt1Ty(V->getContext()), isTrueDest));
 213
 214       // If the condition of the branch is an equality comparison, we may be
 215       // able to infer the value.
 216       if (ICmpInst *ICI = dyn_cast<ICmpInst>(BI->getCondition()))
 217         if (ICI->isEquality() && ICI->getOperand(0) == V &&
 218             isa<Constant>(ICI->getOperand(1))) {
 219           // We know that V has the RHS constant if this is a true SETEQ or
 220           // false SETNE.
 221           if (isTrueDest == (ICI->getPredicate() == ICmpInst::ICMP_EQ))
 222             return LVILatticeVal::get(cast<Constant>(ICI->getOperand(1)));
 223           return LVILatticeVal::getNot(cast<Constant>(ICI->getOperand(1)));
 224         }
 225     }
 226   }
 227
 228   // TODO: Info from switch.
 229
 230
 231   // Otherwise see if the value is known in the block.
 232   return GetValueInBlock(V, BBFrom, BlockVals);
 233 }
 234
 235 static LVILatticeVal GetValueInBlock(Value *V, BasicBlock *BB,
 236                               DenseMap<BasicBlock*, LVILatticeVal> &BlockVals) {
 237   // See if we already have a value for this block.
 238   LVILatticeVal &BBLV = BlockVals[BB];
 239
 240   // If we've already computed this block's value, return it.
 241   if (!BBLV.isUndefined())
 242     return BBLV;
 243
 244   // Otherwise, this is the first time we're seeing this block.  Reset the
 245   // lattice value to overdefined, so that cycles will terminate and be
 246   // conservatively correct.
 247   BBLV.markOverdefined();
 248
 249   LVILatticeVal Result;  // Start Undefined.
 250
 251   // If V is live in to BB, see if our predecessors know anything about it.
 252   Instruction *BBI = dyn_cast<Instruction>(V);
 253   if (BBI == 0 || BBI->getParent() != BB) {
 254     unsigned NumPreds = 0;
 255
 256     // Loop over all of our predecessors, merging what we know from them into
 257     // result.
 258     for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) {
 259       Result.mergeIn(GetValueOnEdge(V, *PI, BB, BlockVals));
 260
 261       // If we hit overdefined, exit early.  The BlockVals entry is already set
 262       // to overdefined.
 263       if (Result.isOverdefined())
 264         return Result;
 265       ++NumPreds;
 266     }
 267
 268     // If this is the entry block, we must be asking about an argument.  The
 269     // value is overdefined.
 270     if (NumPreds == 0 && BB == &BB->getParent()->front()) {
 271       assert(isa<Argument>(V) && "Unknown live-in to the entry block");
 272       Result.markOverdefined();
 273       return Result;
 274     }
 275
 276     // Return the merged value, which is more precise than 'overdefined'.
 277     assert(!Result.isOverdefined());
 278     return BlockVals[BB] = Result;
 279   }
 280
 281   // If this value is defined by an instruction in this block, we have to
 282   // process it here somehow or return overdefined.
 283   if (PHINode *PN = dyn_cast<PHINode>(BBI)) {
 284     (void)PN;
 285     // TODO: PHI Translation in preds.
 286   } else {
 287
 288   }
 289
 290   Result.markOverdefined();
 291   return BlockVals[BB] = Result;
 292 }
 293
 294
 295 Constant *LazyValueInfo::getConstant(Value *V, BasicBlock *BB) {
 296   // If already a constant, return it.
 297   if (Constant *VC = dyn_cast<Constant>(V))
 298     return VC;
 299
 300   DenseMap<BasicBlock*, LVILatticeVal> BlockValues;
 301
 302   DEBUG(errs() << "Getting value " << *V << " at end of block '"
 303                << BB->getName() << "'\n");
 304   LVILatticeVal Result = GetValueInBlock(V, BB, BlockValues);
 305
 306   DEBUG(errs() << "  Result = " << Result << "\n");
 307
 308   if (Result.isConstant())
 309     return Result.getConstant();
 310   return 0;
 311 }
 312
 313 /// getConstantOnEdge - Determine whether the specified value is known to be a
 314 /// constant on the specified edge.  Return null if not.
 315 Constant *LazyValueInfo::getConstantOnEdge(Value *V, BasicBlock *FromBB,
 316                                            BasicBlock *ToBB) {
 317   // If already a constant, return it.
 318   if (Constant *VC = dyn_cast<Constant>(V))
 319     return VC;
 320
 321   DenseMap<BasicBlock*, LVILatticeVal> BlockValues;
 322
 323   DEBUG(errs() << "Getting value " << *V << " on edge from '"
 324                << FromBB->getName() << "' to '" << ToBB->getName() << "'\n");
 325   LVILatticeVal Result = GetValueOnEdge(V, FromBB, ToBB, BlockValues);
 326
 327   DEBUG(errs() << "  Result = " << Result << "\n");
 328
 329   if (Result.isConstant())
 330     return Result.getConstant();
 331   return 0;
 332 }
 333
 334 /// getPredicateOnEdge - Determine whether the specified value comparison
 335 /// with a constant is known to be true or false on the specified CFG edge.
 336 /// Pred is a CmpInst predicate.
 337 LazyValueInfo::Tristate
 338 LazyValueInfo::getPredicateOnEdge(unsigned Pred, Value *V, Constant *C,
 339                                   BasicBlock *FromBB, BasicBlock *ToBB) {
 340   LVILatticeVal Result;
 341
 342   // If already a constant, we can use constant folding.
 343   if (Constant *VC = dyn_cast<Constant>(V)) {
 344     Result = LVILatticeVal::get(VC);
 345   } else {
 346     DenseMap<BasicBlock*, LVILatticeVal> BlockValues;
 347
 348     DEBUG(errs() << "Getting value " << *V << " on edge from '"
 349           << FromBB->getName() << "' to '" << ToBB->getName() << "'\n");
 350     Result = GetValueOnEdge(V, FromBB, ToBB, BlockValues);
 351     DEBUG(errs() << "  Result = " << Result << "\n");
 352   }
 353
 354   // If we know the value is a constant, evaluate the conditional.
 355   Constant *Res = 0;
 356   if (Result.isConstant()) {
 357     Res = ConstantFoldCompareInstOperands(Pred, Result.getConstant(), C, TD);
 358     if (ConstantInt *ResCI = dyn_cast_or_null<ConstantInt>(Res))
 359       return ResCI->isZero() ? False : True;
 360   } else if (Result.isNotConstant()) {
 361     // If this is an equality comparison, we can try to fold it knowing that
 362     // "V != C1".
 363     if (Pred == ICmpInst::ICMP_EQ) {
 364       // !C1 == C -> false iff C1 == C.
 365       Res = ConstantFoldCompareInstOperands(ICmpInst::ICMP_NE,
 366                                             Result.getNotConstant(), C, TD);
 367       if (Res->isNullValue())
 368         return False;
 369     } else if (Pred == ICmpInst::ICMP_NE) {
 370       // !C1 != C -> true iff C1 == C.
 371       Res = ConstantFoldCompareInstOperands(ICmpInst::ICMP_EQ,
 372                                             Result.getNotConstant(), C, TD);
 373       if (Res->isNullValue())
 374         return True;
 375     }
 376   }
 377
 378   return Unknown;
 379 }
 380
 381