[LVI] Introduce an intersect operation on lattice values

[reames]

Summary

LVI has several separate sources of facts - edge local conditions, recursive queries, assumes, and control independent value facts - which all apply to the same value at the same location. The existing implementation was very conservative about exploiting all of these facts at once.

This change introduces an "intersect" function specifically to abstract the action of picking a good set of facts from all of the separate facts given. At the moment, this function is relatively simple (i.e. mostly just reuses the bits which were already there), but even the minor additions reveal the inherent power. For example, JumpThreading is now capable of doing an inductive proof that a particular value is always positive and removing a half range check.

I'm currently only using the new intersect function in one place. If folks are happy with the direction of the work, I plan on making a series of small changes without review to replace mergeIn with intersect at all the appropriate places.

[sanjoy]

Two nitpicky comments inline.

lib/Analysis/LazyValueInfo.cpp

1104

Why not return A.isConstantRange() ? A : B?

1123

This looks a little misleading. If the return value of getEdgeValueLocal truly does not matter, I'd prefer the more idiomatic (void)getEdgeValueLocal(...)

[reames]

lib/Analysis/LazyValueInfo.cpp

1104

Unless I'm misreading something, your replacement would be incorrect. Specifically, I'm returning here if either A or B is NOT a constant range.

1123

I was planning on fixing this in a follow on NFC change by making the function return void. Happy to tweak as suggested though.

[reames]

Fix Sanjoy's comment.

[sanjoy]

lib/Analysis/LazyValueInfo.cpp

1104

I was suggesting putting the return inside the if -- the rule I was suggesting was that if one of the values is not a ConstantRange and the other one isn't then return the one that is a constantrange. However, after re-reading the code it looks like you'll enter the if only with either two nonconstant s or one nonconstant and one constantrange. With that in mind, I'm not sure if my suggestion is actually useful -- both a constantrange and nonconstant are equally "good" I think.

1123

Fixing as a follow on change is fine.

[nlewycky]

lib/Analysis/LazyValueInfo.cpp

357

Remove extra space after 'dbgs'

1076–1080

Optional: You could return a single definition of the constant 'undef'?

1082–1092

I think that if it's undefined, that means that "there exists no definition for this value", and that's stronger than all other possibilities. I think if it's proven to be undefined by any means, you should return undefined.

1094–1095

Optional: Well, you can still rank constants. ConstantExpr is worse than ConstantInt is worse than Undef.

(Actually, there's something even more interesting here which is that constant A must equal constant B, which might be something nobody else has figured out yet. GVN would like to know.)

1137–1138

One dot or three, never two.

[reames]

lib/Analysis/LazyValueInfo.cpp

1076–1080

I'm really trying to avoid changing fundamentals of the lattice with this change. If you think this is a valuable enhancement given discussion below, let me know and I'll consider a future patch.

1082–1092

I think the interpretation you're giving is a reasonable one, but it's not clear to me that's what is currently implemented in LVI. I can't find a counter example, so I'm willing to do this, but would you mind if I submitted this change as is, then followed with a separate change to invert the handling for undefined and clarify the comments? I'd like to isolate any breakage into an easy to revert patch. I also think the diff will be fairly large without adding much value in understandability to the current patch.

1094–1095

While interesting, this would be a fundamental change to the nature of the lattice. We'd effectively be increasing it's height by the number of constant types. Without a clear motivating example, I'd rather not go here.

1137–1138

Will fix.

[reames]

Updated patch w/Nick's comments -- the key point I was confused about is that the previous code implicitly treated the result on the edge as overdefined without ever explicitly making it so. Adding that explicit step and then updating the intersect logic makes things far more clear.

[nlewycky]

lib/Analysis/LazyValueInfo.cpp

357

Please fix the extra space after 'dbgs'

1055–1058

Optional: I'd reorder this test first on the grounds that it should be much more likely.

1090

A period at the end please.

1105–1107

If using Undefined here doesn't work today, please file a PR and link to that PR from here. It has to be a bug, right?

test/Transforms/CorrelatedValuePropagation/conflict.ll

3–4

Can you check anything positive about the results, that we did or didn't fold away branches or comparisons maybe?

test/Transforms/JumpThreading/induction.ll

3

Extra newline.

14

Could you add a CHECK line which shows that this happened? The presence of a branch to the backedge isn't entirely clear.

[reames]

Update per Nick's comments.

[nlewycky]

Spiffy!

lib/Analysis/LazyValueInfo.cpp

class LazyValueInfoCache {
     DenseSet<std::pair<BasicBlock*, Value*> > BlockValueSet;
 
     /// Push BV onto BlockValueStack unless it's already in there.
     /// Returns true on success.
     bool pushBlockValue(const std::pair<BasicBlock *, Value *> &BV) {
       if (!BlockValueSet.insert(BV).second)
         return false;  // It's already in the stack.
 
+      DEBUG(dbgs() << "PUSH: " << *BV.second << " in " << BV.first->getName()
+                   << "\n");
       BlockValueStack.push(BV);
       return true;
     }
 
     AssumptionCache *AC;  ///< A pointer to the cache of @llvm.assume calls.
     const DataLayout &DL; ///< A mandatory DataLayout
     DominatorTree *DT;    ///< An optional DT pointer.
 
while (!BlockValueStack.empty()) {
     assert(BlockValueSet.count(e) && "Stack value should be in BlockValueSet!");
 
     if (solveBlockValue(e.second, e.first)) {
       // The work item was completely processed.
       assert(BlockValueStack.top() == e && "Nothing should have been pushed!");
       assert(hasCachedValueInfo(e.second, e.first) &&
              "Result should be in cache!");
 
+      DEBUG(dbgs() << "POP " << *e.second << " in " << e.first->getName()
+                   << " = " << lookup(e.second)[e.first] << "\n");
+
       BlockValueStack.pop();
       BlockValueSet.erase(e);
     } else {
       // More work needs to be done before revisiting.
       assert(BlockValueStack.top() != e && "Stack should have been pushed!");
     }
   }
 }
for (SwitchInst::CaseIt i : SI->cases()) {
         EdgesVals = EdgesVals.unionWith(EdgeVal);
     }
     Result = LVILatticeVal::getRange(EdgesVals);
     return true;
   }
   return false;
 }
 
+/// Returns true if this lattice value represents at most one possible value.
+/// This is as precise as any lattice value can get while still representing
+/// reachable code.
+static bool hasSingleValue(LVILatticeVal Val) {
+  if (Val.isConstantRange() &&
+      Val.getConstantRange().isSingleElement())
+    // Integer constants are single element ranges
+    return true;
+  if (Val.isConstant())
+    // Non integer constants
+    return true;
+  return false;
+}
+
+/// Combine two sets of facts about the same value into a single set of
+/// facts.  Note that this method is not suitable for merging facts along
+/// different paths in a CFG; that's what the mergeIn function is for.  This
+/// is for merging facts gathered about the same value at the same location
+/// through two independent means.
+/// Notes:
+/// * This method does not promise to return the most precise possible lattice
+///   value implied by A and B.  It is allowed to return any lattice element
+///   which is at least as strong as *either* A or B (unless our facts
+///   conflict, see below).  
+/// * Due to unreachable code, the intersection of two lattice values could be
+///   contradictory.  If this happens, we return some valid lattice value so as
+///   not confuse the rest of LVI.  Ideally, we'd always return Undefined, but
+///   we do not make this guarantee.  TODO: This would be a useful enhancement.
+static LVILatticeVal intersect(LVILatticeVal A, LVILatticeVal B) {
+  // Undefined is the strongest state.  It means the value is known to be along
+  // an unreachable path.
+  if (A.isUndefined())
+    return A;
+  if (B.isUndefined())
+    return B;
+
+  // If we gave up for one, but got a useable fact from the other, use it.
+  if (A.isOverdefined())
+    return B;
+  if (B.isOverdefined())
+    return A;
+
+  // Can't get any more precise than constants.
+  if (hasSingleValue(A))
+    return A;
+  if (hasSingleValue(B))
+    return B;
+
+  // Could be either constant range or not constant here.
+  if (!A.isConstantRange() || !B.isConstantRange()) {
+    // TODO: Arbitrary choice, could be improved
+    return A;
+  }
+
+  // Intersect two constant ranges
+  ConstantRange Range =
+    A.getConstantRange().intersectWith(B.getConstantRange());
+  // Note: An empty range is implicitly converted to overdefined internally.
+  // TODO: We could instead use Undefined here since we've proven a conflict
+  // and thus know this path must be unreachable. 
+  return LVILatticeVal::getRange(Range);
+}
+
 /// \brief Compute the value of Val on the edge BBFrom -> BBTo or the value at
 /// the basic block if the edge does not constrain Val.
 bool LazyValueInfoCache::getEdgeValue(Value *Val, BasicBlock *BBFrom,
                                       BasicBlock *BBTo, LVILatticeVal &Result,
                                       Instruction *CxtI) {
   // If already a constant, there is nothing to compute.
   if (Constant *VC = dyn_cast<Constant>(Val)) {
     Result = LVILatticeVal::get(VC);
     return true;
   }
 
-  if (getEdgeValueLocal(Val, BBFrom, BBTo, Result)) {
-    if (!Result.isConstantRange() ||
-        Result.getConstantRange().getSingleElement())
-      return true;
+  LVILatticeVal LocalResult;
+  if (!getEdgeValueLocal(Val, BBFrom, BBTo, LocalResult))
+    // If we couldn't constrain the value on the edge, LocalResult doesn't
+    // provide any information.
+    LocalResult.markOverdefined();
+  
+  if (hasSingleValue(LocalResult)) {
+    // Can't get any more precise here
+    Result = LocalResult;
+  }
 
-    // FIXME: this check should be moved to the beginning of the function when
-    // LVI better supports recursive values. Even for the single value case, we
-    // can intersect to detect dead code (an empty range).
-    if (!hasBlockValue(Val, BBFrom)) {
-      if (pushBlockValue(std::make_pair(BBFrom, Val)))
-        return false;
-      Result.markOverdefined();
-      return true;
-    }
+    // No new information.
+    Result = LocalResult;
 
-    // Try to intersect ranges of the BB and the constraint on the edge.
-    LVILatticeVal InBlock = getBlockValue(Val, BBFrom);
-    mergeAssumeBlockValueConstantRange(Val, InBlock, BBFrom->getTerminator());
-    // See note on the use of the CxtI with mergeAssumeBlockValueConstantRange,
-    // and caching, below.
-    mergeAssumeBlockValueConstantRange(Val, InBlock, CxtI);
-    if (!InBlock.isConstantRange())
-      return true;
-
-    ConstantRange Range =
-      Result.getConstantRange().intersectWith(InBlock.getConstantRange());
-    Result = LVILatticeVal::getRange(Range);
-    return true;
-  }
-
-  if (!hasBlockValue(Val, BBFrom)) {
-    if (pushBlockValue(std::make_pair(BBFrom, Val)))
-      return false;
-    Result.markOverdefined();
-    return true;
-  }
-
-  // If we couldn't compute the value on the edge, use the value from the BB.
-  Result = getBlockValue(Val, BBFrom);
-  mergeAssumeBlockValueConstantRange(Val, Result, BBFrom->getTerminator());
   // We can use the context instruction (generically the ultimate instruction
   // the calling pass is trying to simplify) here, even though the result of
   // this function is generally cached when called from the solve* functions
   // (and that cached result might be used with queries using a different
   // context instruction), because when this function is called from the solve*
   // functions, the context instruction is not provided. When called from
   // LazyValueInfoCache::getValueOnEdge, the context instruction is provided,
   // but then the result is not cached.
-  mergeAssumeBlockValueConstantRange(Val, Result, CxtI);
+  mergeAssumeBlockValueConstantRange(Val, InBlock, CxtI);
+
+  Result = intersect(LocalResult, InBlock);
   return true;
 }
 
 LVILatticeVal LazyValueInfoCache::getValueInBlock(Value *V, BasicBlock *BB,
                                                   Instruction *CxtI) {
   DEBUG(dbgs() << "LVI Getting block end value " << *V << " at '"
         << BB->getName() << "'\n");
 

test/Transforms/CorrelatedValuePropagation/conflict.ll

+; RUN: opt -correlated-propagation -S < %s | FileCheck %s
+; Checks that we don't crash on conflicting facts about a value 
+; (i.e. unreachable code)
+
+; Test that we can handle conflict edge facts
+define i8 @test(i8 %a) {
+; CHECK-LABEL: @test
+  %cmp1 = icmp eq i8 %a, 5
+  br i1 %cmp1, label %next, label %exit
+next:
+  %cmp2 = icmp eq i8 %a, 3
+; CHECK: br i1 false, label %dead, label %exit
+  br i1 %cmp2, label %dead, label %exit
+dead:
+; CHECK-LABEL: dead:
+; CHECK: ret i8 5
+; NOTE: undef, or 3 would be equal valid
+  ret i8 %a
+exit:
+  ret i8 0
+}
+
+declare void @llvm.assume(i1)
+
+; Test that we can handle conflicting assume vs edge facts
+define i8 @test2(i8 %a) {
+; CHECK-LABEL: @test2
+  %cmp1 = icmp eq i8 %a, 5
+  call void @llvm.assume(i1 %cmp1)
+  %cmp2 = icmp eq i8 %a, 3
+; CHECK: br i1 false, label %dead, label %exit
+  br i1 %cmp2, label %dead, label %exit
+dead:
+  ret i8 %a
+exit:
+  ret i8 0
+}
+
+define i8 @test3(i8 %a) {
+; CHECK-LABEL: @test3
+  %cmp1 = icmp eq i8 %a, 5
+  br i1 %cmp1, label %dead, label %exit
+dead:
+  %cmp2 = icmp eq i8 %a, 3
+; CHECK: call void @llvm.assume(i1 false)
+  call void @llvm.assume(i1 %cmp2)
+  ret i8 %a
+exit:
+  ret i8 0
+}

test/Transforms/JumpThreading/induction.ll

+; RUN: opt -S -jump-threading < %s | FileCheck %s
+
+define i8 @test(i32 %a, i32 %length) {
+; CHECK-LABEL: @test
+entry:
+; CHECK: br label %backedge
+  br label %loop
+
+loop:
+; CHECK-LABEL: backedge:
+; CHECK: phi i32
+; CHECK: br i1 %cont, label %backedge, label %exit
+  %iv = phi i32 [0, %entry], [%iv.next, %backedge]
+  ;; We can use an inductive argument to prove %iv is always positive
+  %cnd = icmp sge i32 %iv, 0
+  br i1 %cnd, label %backedge, label %exit
+
+backedge:
+  %iv.next = add nsw i32 %iv, 1
+  %cont = icmp slt i32 %iv.next, 400
+  br i1 %cont, label %loop, label %exit
+exit:
+  ret i8 0
+}
+