[LVI] Improve select handling to use condition

[reames]

Summary

This patches teaches LVI to recognize clamp idioms (e.g. select(a > 5, a, 5) will always produce something greater than 5.

The tests end up being somewhat simplistic because trying to exercise the case I actually care about (a loop with a range check on a clamped secondary induction variable) ends up tripping across a couple of other imprecisions in the analysis. Ah, the joys of LVI...

[sanjoy]

I thought I had LGTM'ed this earlier. Sorry for the delay!

lib/Analysis/LazyValueInfo.cpp

919

From is repeated in the name?

lib/Analysis/LazyValueInfo.cpp

bool LazyValueInfoCache::solveBlockValueSelect(LVILatticeVal &BBLV,
   LVILatticeVal FalseVal = getBlockValue(SI->getFalseValue(), BB);
   // If we hit overdefined, don't ask more queries.  We want to avoid poisoning
   // extra slots in the table if we can.
   if (FalseVal.isOverdefined()) {
     BBLV.markOverdefined();
     return true;
   }
 
+  // Can we constrain the facts about the true and false values by using the
+  // condition itself?  This shows up with idioms like e.g. select(a > 5, a, 5).
+  // TODO: We could potentially refine an overdefined true value above.
+  if (auto *ICI = dyn_cast<ICmpInst>(SI->getCondition())) {
+    LVILatticeVal TrueValTaken, FalseValTaken;
+    if (!getValueFromFromCondition(SI->getTrueValue(), ICI,
+                                   TrueValTaken, true))
+      TrueValTaken.markOverdefined();
+    if (!getValueFromFromCondition(SI->getFalseValue(), ICI,
+                                   FalseValTaken, false))
+      FalseValTaken.markOverdefined();
+
+    TrueVal = intersect(TrueVal, TrueValTaken);
+    FalseVal = intersect(FalseVal, FalseValTaken);
+  }
+
+  // TODO: handle idioms like min & max where we can use a more precise merge
+  // when our inputs are constant ranges.
+  
   LVILatticeVal Result;  // Start Undefined.
   Result.mergeIn(TrueVal, DL);
   Result.mergeIn(FalseVal, DL);
   BBLV = Result;
   return true;
 }
 
 bool LazyValueInfoCache::solveBlockValueConstantRange(LVILatticeVal &BBLV,

test/Transforms/CorrelatedValuePropagation/select.ll

; CHECK: ret i1 %res
   %res = fcmp oeq double %min, 300.0
   ret i1 %res
 
 exit:
 ; CHECK-LABEL: exit:
 ; CHECK: ret i1 true
   ret i1 true
 }
+
+;; Using the condition to clamp the result
+;; 
+
+define i1 @test5(i32* %p, i1 %unknown) {
+; CHECK-LABEL: @test5
+  %pval = load i32, i32* %p
+  %cmp1 = icmp slt i32 %pval, 255
+  br i1 %cmp1, label %next, label %exit
+
+next:
+  %cond = icmp sgt i32 %pval, 0
+  %min = select i1 %cond, i32 %pval, i32 5
+  ;; TODO: This pointless branch shouldn't be neccessary
+  br label %next2
+next2:
+; CHECK-LABEL: next2:
+; CHECK: ret i1 false
+  %res = icmp eq i32 %min, -1
+  ret i1 %res
+
+exit:
+; CHECK-LABEL: exit:
+; CHECK: ret i1 true
+  ret i1 true
+}
+
+define i1 @test6(i32* %p, i1 %unknown) {
+; CHECK-LABEL: @test6
+  %pval = load i32, i32* %p
+  %cmp1 = icmp ult i32 %pval, 255
+  br i1 %cmp1, label %next, label %exit
+
+next:
+  %cond = icmp ne i32 %pval, 254
+  %sel = select i1 %cond, i32 %pval, i32 1
+  ;; TODO: This pointless branch shouldn't be neccessary
+  br label %next2
+next2:
+; CHECK-LABEL: next2:
+; CHECK: ret i1 true
+  %res = icmp slt i32 %sel, 254
+  ret i1 %res
+
+exit:
+; CHECK-LABEL: exit:
+; CHECK: ret i1 true
+  ret i1 true
+}