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 //                            LazyValueInfo Impl
 199 //===----------------------------------------------------------------------===//
 200
 201 bool LazyValueInfo::runOnFunction(Function &F) {
 202   TD = getAnalysisIfAvailable<TargetData>();
 203   // Fully lazy.
 204   return false;
 205 }
 206
 207 void LazyValueInfo::releaseMemory() {
 208   // No caching yet.
 209 }
 210
 211 static LVILatticeVal GetValueInBlock(Value *V, BasicBlock *BB,
 212                                      DenseMap<BasicBlock*, LVILatticeVal> &);
 213
 214 static LVILatticeVal GetValueOnEdge(Value *V, BasicBlock *BBFrom,
 215                                     BasicBlock *BBTo,
 216                               DenseMap<BasicBlock*, LVILatticeVal> &BlockVals) {
 217   // FIXME: Pull edge logic out of jump threading.
 218
 219
 220   if (BranchInst *BI = dyn_cast<BranchInst>(BBFrom->getTerminator())) {
 221     // If this is a conditional branch and only one successor goes to BBTo, then
 222     // we maybe able to infer something from the condition.
 223     if (BI->isConditional() &&
 224         BI->getSuccessor(0) != BI->getSuccessor(1)) {
 225       bool isTrueDest = BI->getSuccessor(0) == BBTo;
 226       assert(BI->getSuccessor(!isTrueDest) == BBTo &&
 227              "BBTo isn't a successor of BBFrom");
 228
 229       // If V is the condition of the branch itself, then we know exactly what
 230       // it is.
 231       if (BI->getCondition() == V)
 232         return LVILatticeVal::get(ConstantInt::get(
 233                                  Type::getInt1Ty(V->getContext()), isTrueDest));
 234
 235       // If the condition of the branch is an equality comparison, we may be
 236       // able to infer the value.
 237       if (ICmpInst *ICI = dyn_cast<ICmpInst>(BI->getCondition()))
 238         if (ICI->isEquality() && ICI->getOperand(0) == V &&
 239             isa<Constant>(ICI->getOperand(1))) {
 240           // We know that V has the RHS constant if this is a true SETEQ or
 241           // false SETNE.
 242           if (isTrueDest == (ICI->getPredicate() == ICmpInst::ICMP_EQ))
 243             return LVILatticeVal::get(cast<Constant>(ICI->getOperand(1)));
 244           return LVILatticeVal::getNot(cast<Constant>(ICI->getOperand(1)));
 245         }
 246     }
 247   }
 248
 249   // TODO: Info from switch.
 250
 251
 252   // Otherwise see if the value is known in the block.
 253   return GetValueInBlock(V, BBFrom, BlockVals);
 254 }
 255
 256 static LVILatticeVal GetValueInBlock(Value *V, BasicBlock *BB,
 257                               DenseMap<BasicBlock*, LVILatticeVal> &BlockVals) {
 258   // See if we already have a value for this block.
 259   LVILatticeVal &BBLV = BlockVals[BB];
 260
 261   // If we've already computed this block's value, return it.
 262   if (!BBLV.isUndefined())
 263     return BBLV;
 264
 265   // Otherwise, this is the first time we're seeing this block.  Reset the
 266   // lattice value to overdefined, so that cycles will terminate and be
 267   // conservatively correct.
 268   BBLV.markOverdefined();
 269
 270   LVILatticeVal Result;  // Start Undefined.
 271
 272   // If V is live in to BB, see if our predecessors know anything about it.
 273   Instruction *BBI = dyn_cast<Instruction>(V);
 274   if (BBI == 0 || BBI->getParent() != BB) {
 275     unsigned NumPreds = 0;
 276
 277     // Loop over all of our predecessors, merging what we know from them into
 278     // result.
 279     for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) {
 280       Result.mergeIn(GetValueOnEdge(V, *PI, BB, BlockVals));
 281
 282       // If we hit overdefined, exit early.  The BlockVals entry is already set
 283       // to overdefined.
 284       if (Result.isOverdefined())
 285         return Result;
 286       ++NumPreds;
 287     }
 288
 289     // If this is the entry block, we must be asking about an argument.  The
 290     // value is overdefined.
 291     if (NumPreds == 0 && BB == &BB->getParent()->front()) {
 292       assert(isa<Argument>(V) && "Unknown live-in to the entry block");
 293       Result.markOverdefined();
 294       return Result;
 295     }
 296
 297     // Return the merged value, which is more precise than 'overdefined'.
 298     assert(!Result.isOverdefined());
 299     return BlockVals[BB] = Result;
 300   }
 301
 302   // If this value is defined by an instruction in this block, we have to
 303   // process it here somehow or return overdefined.
 304   if (PHINode *PN = dyn_cast<PHINode>(BBI)) {
 305     (void)PN;
 306     // TODO: PHI Translation in preds.
 307   } else {
 308
 309   }
 310
 311   Result.markOverdefined();
 312   return BlockVals[BB] = Result;
 313 }
 314
 315
 316 Constant *LazyValueInfo::getConstant(Value *V, BasicBlock *BB) {
 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 << " at end of block '"
 324                << BB->getName() << "'\n");
 325   LVILatticeVal Result = GetValueInBlock(V, BB, BlockValues);
 326
 327   DEBUG(errs() << "  Result = " << Result << "\n");
 328
 329   if (Result.isConstant())
 330     return Result.getConstant();
 331   return 0;
 332 }
 333
 334 /// getConstantOnEdge - Determine whether the specified value is known to be a
 335 /// constant on the specified edge.  Return null if not.
 336 Constant *LazyValueInfo::getConstantOnEdge(Value *V, BasicBlock *FromBB,
 337                                            BasicBlock *ToBB) {
 338   // If already a constant, return it.
 339   if (Constant *VC = dyn_cast<Constant>(V))
 340     return VC;
 341
 342   DenseMap<BasicBlock*, LVILatticeVal> BlockValues;
 343
 344   DEBUG(errs() << "Getting value " << *V << " on edge from '"
 345                << FromBB->getName() << "' to '" << ToBB->getName() << "'\n");
 346   LVILatticeVal Result = GetValueOnEdge(V, FromBB, ToBB, BlockValues);
 347
 348   DEBUG(errs() << "  Result = " << Result << "\n");
 349
 350   if (Result.isConstant())
 351     return Result.getConstant();
 352   return 0;
 353 }
 354
 355 /// getPredicateOnEdge - Determine whether the specified value comparison
 356 /// with a constant is known to be true or false on the specified CFG edge.
 357 /// Pred is a CmpInst predicate.
 358 LazyValueInfo::Tristate
 359 LazyValueInfo::getPredicateOnEdge(unsigned Pred, Value *V, Constant *C,
 360                                   BasicBlock *FromBB, BasicBlock *ToBB) {
 361   LVILatticeVal Result;
 362
 363   // If already a constant, we can use constant folding.
 364   if (Constant *VC = dyn_cast<Constant>(V)) {
 365     Result = LVILatticeVal::get(VC);
 366   } else {
 367     DenseMap<BasicBlock*, LVILatticeVal> BlockValues;
 368
 369     DEBUG(errs() << "Getting value " << *V << " on edge from '"
 370           << FromBB->getName() << "' to '" << ToBB->getName() << "'\n");
 371     Result = GetValueOnEdge(V, FromBB, ToBB, BlockValues);
 372     DEBUG(errs() << "  Result = " << Result << "\n");
 373   }
 374
 375   // If we know the value is a constant, evaluate the conditional.
 376   Constant *Res = 0;
 377   if (Result.isConstant()) {
 378     Res = ConstantFoldCompareInstOperands(Pred, Result.getConstant(), C, TD);
 379     if (ConstantInt *ResCI = dyn_cast_or_null<ConstantInt>(Res))
 380       return ResCI->isZero() ? False : True;
 381   } else if (Result.isNotConstant()) {
 382     // If this is an equality comparison, we can try to fold it knowing that
 383     // "V != C1".
 384     if (Pred == ICmpInst::ICMP_EQ) {
 385       // !C1 == C -> false iff C1 == C.
 386       Res = ConstantFoldCompareInstOperands(ICmpInst::ICMP_NE,
 387                                             Result.getNotConstant(), C, TD);
 388       if (Res->isNullValue())
 389         return False;
 390     } else if (Pred == ICmpInst::ICMP_NE) {
 391       // !C1 != C -> true iff C1 == C.
 392       Res = ConstantFoldCompareInstOperands(ICmpInst::ICMP_EQ,
 393                                             Result.getNotConstant(), C, TD);
 394       if (Res->isNullValue())
 395         return True;
 396     }
 397   }
 398
 399   return Unknown;
 400 }
 401
 402