+/// getEdgeValue - This method attempts to infer more complex
+LVILatticeVal LVIQuery::getEdgeValue(BasicBlock *BBFrom, BasicBlock *BBTo) {
+ // TODO: Handle more complex conditionals. If (v == 0 || v2 < 1) is false, we
+ // know that v != 0.
+ if (BranchInst *BI = dyn_cast<BranchInst>(BBFrom->getTerminator())) {
+ // If this is a conditional branch and only one successor goes to BBTo, then
+ // we maybe able to infer something from the condition.
+ if (BI->isConditional() &&
+ BI->getSuccessor(0) != BI->getSuccessor(1)) {
+ bool isTrueDest = BI->getSuccessor(0) == BBTo;
+ assert(BI->getSuccessor(!isTrueDest) == BBTo &&
+ "BBTo isn't a successor of BBFrom");
+
+ // If V is the condition of the branch itself, then we know exactly what
+ // it is.
+ if (BI->getCondition() == Val)
+ return LVILatticeVal::get(ConstantInt::get(
+ Type::getInt1Ty(Val->getContext()), isTrueDest));
+
+ // If the condition of the branch is an equality comparison, we may be
+ // able to infer the value.
+ ICmpInst *ICI = dyn_cast<ICmpInst>(BI->getCondition());
+ if (ICI && ICI->getOperand(0) == Val &&
+ isa<Constant>(ICI->getOperand(1))) {
+ if (ICI->isEquality()) {
+ // We know that V has the RHS constant if this is a true SETEQ or
+ // false SETNE.
+ if (isTrueDest == (ICI->getPredicate() == ICmpInst::ICMP_EQ))
+ return LVILatticeVal::get(cast<Constant>(ICI->getOperand(1)));
+ return LVILatticeVal::getNot(cast<Constant>(ICI->getOperand(1)));
+ }
+
+ if (ConstantInt *CI = dyn_cast<ConstantInt>(ICI->getOperand(1))) {
+ // Calculate the range of values that would satisfy the comparison.
+ ConstantRange CmpRange(CI->getValue(), CI->getValue()+1);
+ ConstantRange TrueValues =
+ ConstantRange::makeICmpRegion(ICI->getPredicate(), CmpRange);
+
+ // If we're interested in the false dest, invert the condition.
+ if (!isTrueDest) TrueValues = TrueValues.inverse();
+
+ // Figure out the possible values of the query BEFORE this branch.
+ LVILatticeVal InBlock = getBlockValue(BBFrom);
+ if (!InBlock.isConstantRange())
+ return LVILatticeVal::getRange(TrueValues);
+
+ // Find all potential values that satisfy both the input and output
+ // conditions.
+ ConstantRange PossibleValues =
+ TrueValues.intersectWith(InBlock.getConstantRange());
+
+ return LVILatticeVal::getRange(PossibleValues);
+ }
+ }
+ }
+ }
+
+ // If the edge was formed by a switch on the value, then we may know exactly
+ // what it is.
+ if (SwitchInst *SI = dyn_cast<SwitchInst>(BBFrom->getTerminator())) {
+ if (SI->getCondition() == Val) {
+ // We don't know anything in the default case.
+ if (SI->getDefaultDest() == BBTo) {
+ LVILatticeVal Result;
+ Result.markOverdefined();
+ return Result;
+ }
+
+ // We only know something if there is exactly one value that goes from
+ // BBFrom to BBTo.
+ unsigned NumEdges = 0;
+ ConstantInt *EdgeVal = 0;
+ for (unsigned i = 1, e = SI->getNumSuccessors(); i != e; ++i) {
+ if (SI->getSuccessor(i) != BBTo) continue;
+ if (NumEdges++) break;
+ EdgeVal = SI->getCaseValue(i);
+ }
+ assert(EdgeVal && "Missing successor?");
+ if (NumEdges == 1)
+ return LVILatticeVal::get(EdgeVal);
+ }
+ }
+
+ // Otherwise see if the value is known in the block.
+ return getBlockValue(BBFrom);
+}
+
+
+//===----------------------------------------------------------------------===//
+// LazyValueInfoCache Impl
+//===----------------------------------------------------------------------===//
+
+LVILatticeVal LazyValueInfoCache::getValueInBlock(Value *V, BasicBlock *BB) {
+ // If already a constant, there is nothing to compute.
+ if (Constant *VC = dyn_cast<Constant>(V))
+ return LVILatticeVal::get(VC);
+
+ DEBUG(dbgs() << "LVI Getting block end value " << *V << " at '"
+ << BB->getName() << "'\n");
+
+ LVILatticeVal Result = LVIQuery(V, *this,
+ ValueCache[LVIValueHandle(V, this)],
+ OverDefinedCache).getBlockValue(BB);
+
+ DEBUG(dbgs() << " Result = " << Result << "\n");
+ return Result;
+}
+
+LVILatticeVal LazyValueInfoCache::
+getValueOnEdge(Value *V, BasicBlock *FromBB, BasicBlock *ToBB) {
+ // If already a constant, there is nothing to compute.