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             isa<ConstantExpr>(getNotConstant()) ||
 146             isa<ConstantExpr>(RHS.getNotConstant()))
 147           return markOverdefined();
 148         return false;
 149       }
 150       if (isConstant()) {
 151         if (getConstant() == RHS.getNotConstant() ||
 152             isa<ConstantExpr>(RHS.getNotConstant()) ||
 153             isa<ConstantExpr>(getConstant()))
 154           return markOverdefined();
 155         return markNotConstant(RHS.getNotConstant());
 156       }
 157
 158       assert(isUndefined() && "Unexpected lattice");
 159       return markNotConstant(RHS.getNotConstant());
 160     }
 161
 162     // RHS must be a constant, we must be undef, constant, or notconstant.
 163     if (isUndefined())
 164       return markConstant(RHS.getConstant());
 165
 166     if (isConstant()) {
 167       if (getConstant() != RHS.getConstant())
 168         return markOverdefined();
 169       return false;
 170     }
 171
 172     // If we are known "!=4" and RHS is "==5", stay at "!=4".
 173     if (getNotConstant() == RHS.getConstant() ||
 174         isa<ConstantExpr>(getNotConstant()) ||
 175         isa<ConstantExpr>(RHS.getConstant()))
 176       return markOverdefined();
 177     return false;
 178   }
 179
 180 };
 181
 182 } // end anonymous namespace.
 183
 184 namespace llvm {
 185 raw_ostream &operator<<(raw_ostream &OS, const LVILatticeVal &Val) {
 186   if (Val.isUndefined())
 187     return OS << "undefined";
 188   if (Val.isOverdefined())
 189     return OS << "overdefined";
 190
 191   if (Val.isNotConstant())
 192     return OS << "notconstant<" << *Val.getNotConstant() << '>';
 193   return OS << "constant<" << *Val.getConstant() << '>';
 194 }
 195 }
 196
 197 //===----------------------------------------------------------------------===//
 198 //                          LazyValueInfoCache Decl
 199 //===----------------------------------------------------------------------===//
 200
 201 namespace {
 202   /// LazyValueInfoCache - This is the cache kept by LazyValueInfo which
 203   /// maintains information about queries across the clients' queries.
 204   class LazyValueInfoCache {
 205   public:
 206     /// BlockCacheEntryTy - This is a computed lattice value at the end of the
 207     /// specified basic block for a Value* that depends on context.
 208     typedef std::pair<BasicBlock*, LVILatticeVal> BlockCacheEntryTy;
 209
 210     /// ValueCacheEntryTy - This is all of the cached block information for
 211     /// exactly one Value*.  The entries are sorted by the BasicBlock* of the
 212     /// entries, allowing us to do a lookup with a binary search.
 213     typedef std::vector<BlockCacheEntryTy> ValueCacheEntryTy;
 214
 215   private:
 216     /// ValueCache - This is all of the cached information for all values,
 217     /// mapped from Value* to key information.
 218     DenseMap<Value*, ValueCacheEntryTy> ValueCache;
 219   public:
 220
 221     /// getValueInBlock - This is the query interface to determine the lattice
 222     /// value for the specified Value* at the end of the specified block.
 223     LVILatticeVal getValueInBlock(Value *V, BasicBlock *BB);
 224
 225     /// getValueOnEdge - This is the query interface to determine the lattice
 226     /// value for the specified Value* that is true on the specified edge.
 227     LVILatticeVal getValueOnEdge(Value *V, BasicBlock *FromBB,BasicBlock *ToBB);
 228   };
 229 } // end anonymous namespace
 230
 231 //===----------------------------------------------------------------------===//
 232 //                              LVIQuery Impl
 233 //===----------------------------------------------------------------------===//
 234
 235 namespace {
 236   /// LVIQuery - This is a transient object that exists while a query is
 237   /// being performed.
 238   class LVIQuery {
 239     typedef LazyValueInfoCache::BlockCacheEntryTy BlockCacheEntryTy;
 240     typedef LazyValueInfoCache::ValueCacheEntryTy ValueCacheEntryTy;
 241
 242     /// This is the current value being queried.
 243     Value *Val;
 244
 245     /// This is all of the cached information about this value.
 246     ValueCacheEntryTy &Cache;
 247
 248     /// BlockVals Temporary Cache used while processing a query.
 249     DenseMap<BasicBlock*, LVILatticeVal> BlockVals;
 250
 251   public:
 252
 253     LVIQuery(Value *V, ValueCacheEntryTy &VC) : Val(V), Cache(VC) {
 254     }
 255
 256     LVILatticeVal getBlockValue(BasicBlock *BB);
 257
 258     LVILatticeVal getEdgeValue(BasicBlock *FromBB, BasicBlock *ToBB);
 259   };
 260 } // end anonymous namespace
 261
 262
 263 LVILatticeVal LVIQuery::getBlockValue(BasicBlock *BB) {
 264   // See if we already have a value for this block.
 265   LVILatticeVal &BBLV = BlockVals[BB];
 266
 267   // If we've already computed this block's value, return it.
 268   if (!BBLV.isUndefined())
 269     return BBLV;
 270
 271   // Otherwise, this is the first time we're seeing this block.  Reset the
 272   // lattice value to overdefined, so that cycles will terminate and be
 273   // conservatively correct.
 274   BBLV.markOverdefined();
 275
 276   // If V is live into BB, see if our predecessors know anything about it.
 277   Instruction *BBI = dyn_cast<Instruction>(Val);
 278   if (BBI == 0 || BBI->getParent() != BB) {
 279     LVILatticeVal Result;  // Start Undefined.
 280     unsigned NumPreds = 0;
 281
 282     // Loop over all of our predecessors, merging what we know from them into
 283     // result.
 284     for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) {
 285       Result.mergeIn(getEdgeValue(*PI, BB));
 286
 287       // If we hit overdefined, exit early.  The BlockVals entry is already set
 288       // to overdefined.
 289       if (Result.isOverdefined())
 290         return Result;
 291       ++NumPreds;
 292     }
 293
 294     // If this is the entry block, we must be asking about an argument.  The
 295     // value is overdefined.
 296     if (NumPreds == 0 && BB == &BB->getParent()->front()) {
 297       assert(isa<Argument>(Val) && "Unknown live-in to the entry block");
 298       Result.markOverdefined();
 299       return Result;
 300     }
 301
 302     // Return the merged value, which is more precise than 'overdefined'.
 303     assert(!Result.isOverdefined());
 304     return BlockVals[BB] = Result;
 305   }
 306
 307   // If this value is defined by an instruction in this block, we have to
 308   // process it here somehow or return overdefined.
 309   if (PHINode *PN = dyn_cast<PHINode>(BBI)) {
 310     (void)PN;
 311     // TODO: PHI Translation in preds.
 312   } else {
 313
 314   }
 315
 316   LVILatticeVal Result;
 317   Result.markOverdefined();
 318   return BlockVals[BB] = Result;
 319 }
 320
 321
 322 /// getEdgeValue - This method
 323 LVILatticeVal LVIQuery::getEdgeValue(BasicBlock *BBFrom, BasicBlock *BBTo) {
 324   if (BranchInst *BI = dyn_cast<BranchInst>(BBFrom->getTerminator())) {
 325     // If this is a conditional branch and only one successor goes to BBTo, then
 326     // we maybe able to infer something from the condition.
 327     if (BI->isConditional() &&
 328         BI->getSuccessor(0) != BI->getSuccessor(1)) {
 329       bool isTrueDest = BI->getSuccessor(0) == BBTo;
 330       assert(BI->getSuccessor(!isTrueDest) == BBTo &&
 331              "BBTo isn't a successor of BBFrom");
 332
 333       // If V is the condition of the branch itself, then we know exactly what
 334       // it is.
 335       if (BI->getCondition() == Val)
 336         return LVILatticeVal::get(ConstantInt::get(
 337                                Type::getInt1Ty(Val->getContext()), isTrueDest));
 338
 339       // If the condition of the branch is an equality comparison, we may be
 340       // able to infer the value.
 341       if (ICmpInst *ICI = dyn_cast<ICmpInst>(BI->getCondition()))
 342         if (ICI->isEquality() && ICI->getOperand(0) == Val &&
 343             isa<Constant>(ICI->getOperand(1))) {
 344           // We know that V has the RHS constant if this is a true SETEQ or
 345           // false SETNE.
 346           if (isTrueDest == (ICI->getPredicate() == ICmpInst::ICMP_EQ))
 347             return LVILatticeVal::get(cast<Constant>(ICI->getOperand(1)));
 348           return LVILatticeVal::getNot(cast<Constant>(ICI->getOperand(1)));
 349         }
 350     }
 351   }
 352
 353   // TODO: Info from switch.
 354
 355   // TODO: Handle more complex conditionals.  If (v == 0 || v2 < 1) is false, we
 356   // know that v != 0.
 357
 358   // Otherwise see if the value is known in the block.
 359   return getBlockValue(BBFrom);
 360 }
 361
 362
 363 //===----------------------------------------------------------------------===//
 364 //                         LazyValueInfoCache Impl
 365 //===----------------------------------------------------------------------===//
 366
 367 LVILatticeVal LazyValueInfoCache::getValueInBlock(Value *V, BasicBlock *BB) {
 368   // If already a constant, there is nothing to compute.
 369   if (Constant *VC = dyn_cast<Constant>(V))
 370     return LVILatticeVal::get(VC);
 371
 372   DEBUG(errs() << "Getting value " << *V << " at end of block '"
 373         << BB->getName() << "'\n");
 374
 375   LVILatticeVal Result = LVIQuery(V, ValueCache[V]).getBlockValue(BB);
 376
 377   DEBUG(errs() << "  Result = " << Result << "\n");
 378   return Result;
 379 }
 380
 381 LVILatticeVal LazyValueInfoCache::
 382 getValueOnEdge(Value *V, BasicBlock *FromBB, BasicBlock *ToBB) {
 383   // If already a constant, there is nothing to compute.
 384   if (Constant *VC = dyn_cast<Constant>(V))
 385     return LVILatticeVal::get(VC);
 386
 387   DEBUG(errs() << "Getting value " << *V << " on edge from '"
 388         << FromBB->getName() << "' to '" << ToBB->getName() << "'\n");
 389   LVILatticeVal Result =
 390     LVIQuery(V, ValueCache[V]).getEdgeValue(FromBB, ToBB);
 391
 392   DEBUG(errs() << "  Result = " << Result << "\n");
 393
 394   return Result;
 395 }
 396
 397 //===----------------------------------------------------------------------===//
 398 //                            LazyValueInfo Impl
 399 //===----------------------------------------------------------------------===//
 400
 401 bool LazyValueInfo::runOnFunction(Function &F) {
 402   TD = getAnalysisIfAvailable<TargetData>();
 403   // Fully lazy.
 404   return false;
 405 }
 406
 407 /// getCache - This lazily constructs the LazyValueInfoCache.
 408 static LazyValueInfoCache &getCache(void *&PImpl) {
 409   if (!PImpl)
 410     PImpl = new LazyValueInfoCache();
 411   return *static_cast<LazyValueInfoCache*>(PImpl);
 412 }
 413
 414 void LazyValueInfo::releaseMemory() {
 415   // If the cache was allocated, free it.
 416   if (PImpl) {
 417     delete &getCache(PImpl);
 418     PImpl = 0;
 419   }
 420 }
 421
 422 Constant *LazyValueInfo::getConstant(Value *V, BasicBlock *BB) {
 423   LVILatticeVal Result = getCache(PImpl).getValueInBlock(V, BB);
 424
 425   if (Result.isConstant())
 426     return Result.getConstant();
 427   return 0;
 428 }
 429
 430 /// getConstantOnEdge - Determine whether the specified value is known to be a
 431 /// constant on the specified edge.  Return null if not.
 432 Constant *LazyValueInfo::getConstantOnEdge(Value *V, BasicBlock *FromBB,
 433                                            BasicBlock *ToBB) {
 434   LVILatticeVal Result = getCache(PImpl).getValueOnEdge(V, FromBB, ToBB);
 435
 436   if (Result.isConstant())
 437     return Result.getConstant();
 438   return 0;
 439 }
 440
 441 /// getPredicateOnEdge - Determine whether the specified value comparison
 442 /// with a constant is known to be true or false on the specified CFG edge.
 443 /// Pred is a CmpInst predicate.
 444 LazyValueInfo::Tristate
 445 LazyValueInfo::getPredicateOnEdge(unsigned Pred, Value *V, Constant *C,
 446                                   BasicBlock *FromBB, BasicBlock *ToBB) {
 447   LVILatticeVal Result = getCache(PImpl).getValueOnEdge(V, FromBB, ToBB);
 448
 449   // If we know the value is a constant, evaluate the conditional.
 450   Constant *Res = 0;
 451   if (Result.isConstant()) {
 452     Res = ConstantFoldCompareInstOperands(Pred, Result.getConstant(), C, TD);
 453     if (ConstantInt *ResCI = dyn_cast_or_null<ConstantInt>(Res))
 454       return ResCI->isZero() ? False : True;
 455     return Unknown;
 456   }
 457
 458   if (Result.isNotConstant()) {
 459     // If this is an equality comparison, we can try to fold it knowing that
 460     // "V != C1".
 461     if (Pred == ICmpInst::ICMP_EQ) {
 462       // !C1 == C -> false iff C1 == C.
 463       Res = ConstantFoldCompareInstOperands(ICmpInst::ICMP_NE,
 464                                             Result.getNotConstant(), C, TD);
 465       if (Res->isNullValue())
 466         return False;
 467     } else if (Pred == ICmpInst::ICMP_NE) {
 468       // !C1 != C -> true iff C1 == C.
 469       Res = ConstantFoldCompareInstOperands(ICmpInst::ICMP_EQ,
 470                                             Result.getNotConstant(), C, TD);
 471       if (Res->isNullValue())
 472         return True;
 473     }
 474     return Unknown;
 475   }
 476
 477   return Unknown;
 478 }
 479
 480