[LVI/CVP] Teach LVI about range metadata

[reames]

Summary

Somewhat shockingly for an analysis pass which is computing constant ranges, LVI did not understand the ranges provided by range metadata.

As part of this change, I included a change to CVP primarily because doing so made it much easier to write small self contained test cases. CVP was previously only handling the non-local operand case, but given that LVI can sometimes figure out information about instructions standalone, I don't see any reason to restrict this.

Note that this patch continues a somewhat bad practice in LVI. In many cases, we know facts about values, and separate context sensitive facts about values. LVI makes no effort to distinguish and will frequently cache the same value fact repeatedly for different contexts. I would like to change this, but that's a large enough change that I want it to go in separately with clear documentation of what's changing. Other examples of this include the non-null handling, and arguments.

As a meta comment: the entire motivation of this change was being able to write smaller (aka reasonable sized) test cases for a future patch teaching LVI about select instructions.

[reames]

If folks are uncomfortable with the CVP change, I could restructure it
to only try to simplify icmps feeding return instructions. That should
trigger far less often, still be useable for writing tests, and get most
of the actual performance benefit. I'll probably stick with the current
change if no one objects; just throwing out the alternative for discussion.

Philip

[reames]

ping! I'd really like to get this in so that I can build on it.

[• chenli]

lib/Analysis/LazyValueInfo.cpp

502 ↗

(On Diff #36820)

Do we actually need to check the Opcode? For instructions those cannot have range metadata, getMetadata(LLVMContext::MD_range) will just return a nullptr. If range metadata is extended for other instructions in the future, this switch statement has to be updated as well. I think it might be better to just get rid of the switch.

[sanjoy]

Minor inline comment inline. I don't really know LVI, so I'll have to read some code before I can review this properly.

lib/Analysis/LazyValueInfo.cpp

507 ↗

(On Diff #36820)

I've seen this logic repeated in several places now. I think it's time to refactor out a ConstantRange getRangeFromMetadata() helper function.

However, I think its fine to check this in as is, and then extract out the helper.

[reames]

lib/Analysis/LazyValueInfo.cpp

502 ↗

(On Diff #36820)

I could go either way on this. The verifier currently enforces these three, but there's no reason the code here needs to. What do others think?

507 ↗

(On Diff #36820)

Completely agreed. Will do as a separate follow on change.

[sanjoy]

lgtm modulo minor nits inline

lib/Analysis/LazyValueInfo.cpp

507 ↗

(On Diff #36820)

I ended up doing this today: http://reviews.llvm.org/rL251180 so you should be able to change this to just use getConstantRangeFromMetadata.

573 ↗

(On Diff #36820)

By "should be" do you mean at some point in the future? Because AFAICT today mergeIn will do a union.

If you do mean "at some point in the future", please make that obvious, perhaps by changing this to a TODO or a FIXME.

llvm/trunk/lib/Analysis/LazyValueInfo.cpp

 #include "llvm/Analysis/ValueTracking.h"
 #include "llvm/IR/CFG.h"
 #include "llvm/IR/ConstantRange.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/IntrinsicInst.h"
+#include "llvm/IR/LLVMContext.h"
 #include "llvm/IR/PatternMatch.h"
 #include "llvm/IR/ValueHandle.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
 #include <map>
 #include <stack>
 using namespace llvm;
 using namespace PatternMatch;
LVILatticeVal LazyValueInfoCache::getBlockValue(Value *Val, BasicBlock *BB) {
   // If already a constant, there is nothing to compute.
   if (Constant *VC = dyn_cast<Constant>(Val))
     return LVILatticeVal::get(VC);
 
   SeenBlocks.insert(BB);
   return lookup(Val)[BB];
 }
 
+static LVILatticeVal getFromRangeMetadata(Instruction *BBI) {
+  switch (BBI->getOpcode()) {
+  default: break;
+  case Instruction::Load:
+  case Instruction::Call:
+  case Instruction::Invoke:
+    if (MDNode *Ranges = BBI->getMetadata(LLVMContext::MD_range)) 
+      if (auto *IType = dyn_cast<IntegerType>(BBI->getType())) {
+        ConstantRange Result = getConstantRangeFromMetadata(*Ranges);
+        return LVILatticeVal::getRange(Result);
+      }
+    break;
+  };
+  // Nothing known - Note that we do not want overdefined here.  We may know
+  // something else about the value and not having range metadata shouldn't
+  // cause us to throw away those facts.
+  return LVILatticeVal();
+}
+
 bool LazyValueInfoCache::solveBlockValue(Value *Val, BasicBlock *BB) {
   if (isa<Constant>(Val))
     return true;
 
   if (lookup(Val).count(BB)) {
     // If we have a cached value, use that.
     DEBUG(dbgs() << "  reuse BB '" << BB->getName()
                  << "' val=" << lookup(Val)[BB] << '\n');
bool LazyValueInfoCache::solveBlockValue(Value *Val, BasicBlock *BB) {
   // If this value is a nonnull pointer, record it's range and bailout.
   PointerType *PT = dyn_cast<PointerType>(BBI->getType());
   if (PT && isKnownNonNull(BBI)) {
     Res = LVILatticeVal::getNot(ConstantPointerNull::get(PT));
     insertResult(Val, BB, Res);
     return true;
   }
 
+  // If this is an instruction which supports range metadata, return the
+  // implied range.  TODO: This should be an intersection, not a union.
+  Res.mergeIn(getFromRangeMetadata(BBI), DL);
+
   // We can only analyze the definitions of certain classes of instructions
   // (integral binops and casts at the moment), so bail if this isn't one.
   LVILatticeVal Result;
   if ((!isa<BinaryOperator>(BBI) && !isa<CastInst>(BBI)) ||
      !BBI->getType()->isIntegerTy()) {
     DEBUG(dbgs() << " compute BB '" << BB->getName()
                  << "' - overdefined because inst def found.\n");
     Res.markOverdefined();
LVILatticeVal LazyValueInfoCache::getValueInBlock(Value *V, BasicBlock *BB,
   return Result;
 }
 
 LVILatticeVal LazyValueInfoCache::getValueAt(Value *V, Instruction *CxtI) {
   DEBUG(dbgs() << "LVI Getting value " << *V << " at '"
         << CxtI->getName() << "'\n");
 
   LVILatticeVal Result;
+  if (auto *I = dyn_cast<Instruction>(V))
+    Result = getFromRangeMetadata(I);
   mergeAssumeBlockValueConstantRange(V, Result, CxtI);
 
   DEBUG(dbgs() << "  Result = " << Result << "\n");
   return Result;
 }
 
 LVILatticeVal LazyValueInfoCache::
 getValueOnEdge(Value *V, BasicBlock *FromBB, BasicBlock *ToBB,

llvm/trunk/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp

bool CorrelatedValuePropagation::processMemAccess(Instruction *I) {
   Constant *C = LVI->getConstant(Pointer, I->getParent(), I);
   if (!C) return false;
 
   ++NumMemAccess;
   I->replaceUsesOfWith(Pointer, C);
   return true;
 }
 
-/// processCmp - If the value of this comparison could be determined locally,
-/// constant propagation would already have figured it out.  Instead, walk
-/// the predecessors and statically evaluate the comparison based on information
-/// available on that edge.  If a given static evaluation is true on ALL
-/// incoming edges, then it's true universally and we can simplify the compare.
+/// processCmp - See if LazyValueInfo's ability to exploit edge conditions,
+/// or range information is sufficient to prove this comparison.  Even for
+/// local conditions, this can sometimes prove conditions instcombine can't by
+/// exploiting range information.
 bool CorrelatedValuePropagation::processCmp(CmpInst *C) {
   Value *Op0 = C->getOperand(0);
-  if (isa<Instruction>(Op0) &&
-      cast<Instruction>(Op0)->getParent() == C->getParent())
-    return false;
-
   Constant *Op1 = dyn_cast<Constant>(C->getOperand(1));
   if (!Op1) return false;
 
-  pred_iterator PI = pred_begin(C->getParent()), PE = pred_end(C->getParent());
-  if (PI == PE) return false;
-
-  LazyValueInfo::Tristate Result = LVI->getPredicateOnEdge(C->getPredicate(),
-                                    C->getOperand(0), Op1, *PI,
-                                    C->getParent(), C);
+  LazyValueInfo::Tristate Result =
+    LVI->getPredicateAt(C->getPredicate(), Op0, Op1, C);
   if (Result == LazyValueInfo::Unknown) return false;
 
-  ++PI;
-  while (PI != PE) {
-    LazyValueInfo::Tristate Res = LVI->getPredicateOnEdge(C->getPredicate(),
-                                    C->getOperand(0), Op1, *PI,
-                                    C->getParent(), C);
-    if (Res != Result) return false;
-    ++PI;
-  }
-
   ++NumCmps;
-
   if (Result == LazyValueInfo::True)
     C->replaceAllUsesWith(ConstantInt::getTrue(C->getContext()));
   else
     C->replaceAllUsesWith(ConstantInt::getFalse(C->getContext()));
-
   C->eraseFromParent();
 
   return true;
 }
 
 /// processSwitch - Simplify a switch instruction by removing cases which can
 /// never fire.  If the uselessness of a case could be determined locally then
 /// constant propagation would already have figured it out.  Instead, walk the

llvm/trunk/test/Transforms/CorrelatedValuePropagation/range.ll

  %cmp7 = icmp eq i32 %c, 7
  %cmp8 = icmp eq i32 %c, 8
 ; CHECK: %or = or i1 %cmp5, false
  %or = or i1 %cmp5, %cmp6
 ; CHECK: %or2 = or i1 false, %cmp8
  %or2 = or i1 %cmp7, %cmp8
  ret i1 false
 }
+
+define i1 @test8(i64* %p) {
+; CHECK-LABEL: @test8
+; CHECK: ret i1 false
+  %a = load i64, i64* %p, !range !{i64 4, i64 255}
+  %res = icmp eq i64 %a, 0
+  ret i1 %res
+}
+
+define i1 @test9(i64* %p) {
+; CHECK-LABEL: @test9
+; CHECK: ret i1 true
+  %a = load i64, i64* %p, !range !{i64 0, i64 1}
+  %res = icmp eq i64 %a, 0
+  ret i1 %res
+}
+
+define i1 @test10(i64* %p) {
+; CHECK-LABEL: @test10
+; CHECK: ret i1 false
+  %a = load i64, i64* %p, !range !{i64 4, i64 8, i64 15, i64 20}
+  %res = icmp eq i64 %a, 0
+  ret i1 %res
+}