[JumpThreading] Teach jump threading how to analyze (and (cmp A, C1), (cmp A, C2)) after InstCombine has turned it into (cmp (add A, C3), C4)

[craig.topper]

Summary

Currently JumpThreading can use LazyValueInfo to analyze an 'and' or 'or' of compare if the compare is fed by a livein of a basic block. This can be used to to prove the condition can't be met for some predecessor and the jump from that predecessor can be moved to the false path of the condition.

But if the compare is something that InstCombine turns into an add and a single compare, it can't be analyzed because the livein is now an input to the add and not the compare.

This patch adds a new getPredicateOnEdgeAfterAdd entry point to LazyValueInfo that allows for an adjustment to be made to the livein's range before doing the compare predicate check. JumpThreading is then taught to use this entry point if it can see that there is an add of a livein with a constant that is used by a compare.

I'm not sure this is the right division of labor between the two passes so I'm open to other opinions on where the line should be.

[reames]

Can you give a test case without the instcombine processing? (i.e. I'd like to see what jump-threading is actually encountering) At least on first glance, this looks like something LVI should just be able to analyse without any special casing in jump threading.

[craig.topper]

Change test case to be the output after InstCombine.

[craig.topper]

@reames where you able to take a look at this?

[reames]

Ok, I finally got a chance to look at this, sorry for the long delay.

I see the problem you're trying to solve, but I think this patch goes about it the wrong way. I don't think you need any special handling per se, this is a case that JumpThreading::ComputeValueKnownInPredeccessors should handle for you. We should be able to figure out that the %0 icmp expression is known the be false if the "if.then, if.end" edge is executed. In fact, the handling for recursion on icmps and binary operators appears to already be there, so I'm not quite sure why it's not working today. I think this likely comes down to some small bug in either CVKInP or in the jump-threading logic itself.

[craig.topper]

The problem is that LVI knows the value on the edge is within a specific ConstantRange, but the method we call in LVI is getConstantOnEdge which can't return a range.

[reames]

Ok, my previous comment was wrong. This isn't something the existing infrastructure can handle because CVKInP reasons only about constants and we need to forward propagate constant ranges here to discharge the icmp. That's what I'd missed on the first look.

I think there's a couple of reasonable ways to implement this:

1. ask for the constant range of each input to the add, then forward propagate using the ConstantRange accessors. Doing this specifically for add directly in CVKInP doesn't seem too ugly.
2. restructure CVKInP to work in terms of constant ranges. If we'd directly returned the CRs from the inputs, and unwound the recursion in CVKInP applying the forward propagation rules (i.e. the add), then we'd handle not just this case, but many others. (CVKInPred essentially does this today for constants using the constant expressions.)
3. we could sink the result of (2) directly into LVI - this is close to what you're doing currently, but substantially more general.
4. In an alternate approach, we could backwards propagate a predicate (think weakest precondition style) to the beginning of the block, then ask LVI to discharge that predicate for each incoming value. (Clarification: LVI already does something similar to this inside getPredicateAt. We don't current handle the case within a single block, but potentially could. If we did, we should really separate this into it's own analysis layered on top of LVI.)

(1-3) and (4) have slightly different power. Doing (2) is probably the most straight forward extension of the existing logic, but we already have some reasoning ala (4) in LVI itself. Either approach seems reasonable and I could be convinced we should do either. I'd lean towards forward propagation of constant ranges just because that'd probably be easier to write and reason about.

[reames]

In D33262#768289, @craig.topper wrote:

The problem is that LVI knows the value on the edge is within a specific ConstantRange, but the method we call in LVI is getConstantOnEdge which can't return a range.

Our comments interwove here. :) I think I came to the same conclusion you did right?

[Farhana]

It seems to me that the improvement is done in the wrong place which is JumpThreading and made the change-set very specific. In my opinion, it does not have to be specific to JumpThreading. It can be a very general improvement of LVI using your new utilities.

Basically, we can have the following:

• getPredicateOnEdge() does not require a value to be live-in but later functions do. So, I would think we can easily extend getPredicateOnEdge() to handle any kind of values/Range and do the forward substitution in getPredicateOnEdge() . Basically, the new code you have in JumpThreading that is processing a local value and computing the non-local value can be placed inside getPredicateOnEdge(). We can also handle all binary operators.

• Then allow any kind of values from ComputeValueKnownInPredecessors() being queried in getPredicateOnEdge()

[craig.topper]

@reames For 1. were you envisioning detecting the add at the time we're visiting the compare similar to what I do now? Or were you envisioning propagating the add result as we unwind CVKInP after visiting the directly. The latter I think would require us to make CVKInP work in ConstantRanges like suggestion 2. For the former I think I'd also have to replicate some of the compare handling from LVI to calculate the result for the range from the add?

For 2, I think our range solving capabilities are considerably weaker than our ConstantExpr handling so I think we'd still need to rely on ConstantExpr when we have single element ranges?

@Farhana for your suggestion of moving the logic into getPredicateOnEdge. We'd have to decide how far back to make getPredicateOnEdge search for a livein. One instruction? Multiple instructions? We'd also still need some check in jump threading to know whether we are looking at a livein or whether we should recurse into CVKInP like we do today. So we'd have to try getPredicateOnEdge and if it fails, recurse into CVKInP only if we aren't looking at a livein.

[reames]

In D33262#774151, @craig.topper wrote:

@reames For 1. were you envisioning detecting the add at the time we're visiting the compare similar to what I do now? Or were you envisioning propagating the add result as we unwind CVKInP after visiting the directly. The latter I think would require us to make CVKInP work in ConstantRanges like suggestion 2. For the former I think I'd also have to replicate some of the compare handling from LVI to calculate the result for the range from the add?

I was picturing roughly the following:

1. Pattern match add leading to compare (as done today)
2. Ask LVI for constant range representing each input to the add
3. Forward propagate those CRs using CR functions.
4. Expose the compare handling you mention as a helper function and use it.

For 2, I think our range solving capabilities are considerably weaker than our ConstantExpr handling so I think we'd still need to rely on ConstantExpr when we have single element ranges?

This sounds like a reasonable implementation technique for ConstantRange when dealing with single element ranges, but the interface to caller code shouldn't reflect that. :)

[craig.topper]

Implement by asking LVI for a ConstantRange for the add on the edge and propagate forward in JumpThreading.

I tried Farhana's suggestion of moving logic into getPredicateOnEdge, but I had some trouble with PHINode's on single basic block loops. It became difficult to know what the caller was trying to ask to know if we should look back for an instruction. I think this was also compounded by the fact that we use getPredicateOnEdge for select conditions and maybe other things that aren't real compare instructions.

[craig.topper]

Lost the test case in the previous patch.

[craig.topper]

Ping

[reames]

LGTM w/minor changes applied, no further review needed.

Very nice.

lib/Transforms/Scalar/JumpThreading.cpp

638

This would probably be clearer with either a matcher or a helper lambda.

[chandlerc]

Sorry for the drive by review, but I noticed one cleanup below and I have to ask: why is there no test case here? That seems kinda bad. I feel like there should be tests for folding to true, folding to false, and some negative testing that things which *shouldn't* be threaded here aren't....

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

647–649 ↗

(On Diff #103691)

You can remove all of the isa<Instruction> and cast<Intsruction> dance by using m_Instruction in the pattern match and making AddLHS an Instruction*.

[craig.topper]

I had a test. Maybe I forgot to git add it when I turned in. I'll check.

[craig.topper]

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

647–649 ↗

(On Diff #103691)

AddLHS isn't always an instruction. It might be a livein to the block including an argument to the function and we need to handle that.

[craig.topper]

Test case committed in r306416

include/llvm/Analysis/LazyValueInfo.h

public:
   /// on integer-typed Values.
   ConstantRange getConstantRange(Value *V, BasicBlock *BB, Instruction *CxtI = nullptr);
 
   /// Determine whether the specified value is known to be a
   /// constant on the specified edge.  Return null if not.
   Constant *getConstantOnEdge(Value *V, BasicBlock *FromBB, BasicBlock *ToBB,
                               Instruction *CxtI = nullptr);
 
+  /// Return the ConstantRage constraint that is known to hold for the
+  /// specified value on the specified edge. This may be only be called
+  /// on integer-typed Values.
+  ConstantRange getConstantRangeOnEdge(Value *V, BasicBlock *FromBB,
+                                       BasicBlock *ToBB,
+                                       Instruction *CxtI = nullptr);
+
   /// Inform the analysis cache that we have threaded an edge from
   /// PredBB to OldSucc to be from PredBB to NewSucc instead.
   void threadEdge(BasicBlock *PredBB, BasicBlock *OldSucc, BasicBlock *NewSucc);
 
   /// Inform the analysis cache that we have erased a block.
   void eraseBlock(BasicBlock *BB);
 
   /// Print the \LazyValueInfo Analysis.

lib/Analysis/LazyValueInfo.cpp

Constant *LazyValueInfo::getConstantOnEdge(Value *V, BasicBlock *FromBB,
   if (Result.isConstantRange()) {
     const ConstantRange &CR = Result.getConstantRange();
     if (const APInt *SingleVal = CR.getSingleElement())
       return ConstantInt::get(V->getContext(), *SingleVal);
   }
   return nullptr;
 }
 
+ConstantRange LazyValueInfo::getConstantRangeOnEdge(Value *V,
+                                                    BasicBlock *FromBB,
+                                                    BasicBlock *ToBB,
+                                                    Instruction *CxtI) {
+  unsigned Width = V->getType()->getIntegerBitWidth();
+  const DataLayout &DL = FromBB->getModule()->getDataLayout();
+  LVILatticeVal Result =
+      getImpl(PImpl, AC, &DL, DT).getValueOnEdge(V, FromBB, ToBB, CxtI);
+
+  if (Result.isUndefined())
+    return ConstantRange(Width, /*isFullSet=*/false);
+  if (Result.isConstantRange())
+    return Result.getConstantRange();
+  // We represent ConstantInt constants as constant ranges but other kinds
+  // of integer constants, i.e. ConstantExpr will be tagged as constants
+  assert(!(Result.isConstant() && isa<ConstantInt>(Result.getConstant())) &&
+         "ConstantInt value must be represented as constantrange");
+  return ConstantRange(Width, /*isFullSet=*/true);
+}
+
 static LazyValueInfo::Tristate getPredicateResult(unsigned Pred, Constant *C,
                                                   LVILatticeVal &Result,
                                                   const DataLayout &DL,
                                                   TargetLibraryInfo *TLI) {
 
   // If we know the value is a constant, evaluate the conditional.
   Constant *Res = nullptr;
   if (Result.isConstant()) {

lib/Transforms/Scalar/JumpThreading.cpp

 #include "llvm/Analysis/BlockFrequencyInfoImpl.h"
 #include "llvm/Analysis/CFG.h"
 #include "llvm/Analysis/ConstantFolding.h"
 #include "llvm/Analysis/GlobalsModRef.h"
 #include "llvm/Analysis/InstructionSimplify.h"
 #include "llvm/Analysis/Loads.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/ValueTracking.h"
+#include "llvm/IR/ConstantRange.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/LLVMContext.h"
 #include "llvm/IR/MDBuilder.h"
 #include "llvm/IR/Metadata.h"
 #include "llvm/IR/PatternMatch.h"
 #include "llvm/Pass.h"
 #include "llvm/Support/CommandLine.h"
if (isa<Constant>(Cmp->getOperand(1)) && !Cmp->getType()->isVectorTy()) {
 
           Constant *ResC = ConstantInt::get(Cmp->getType(), Res);
           Result.push_back(std::make_pair(ResC, P));
         }
 
         return !Result.empty();
       }
 
+      // InstCombine can fold some forms of constant range checks into
+      // (icmp (add (x, C1)), C2). See if we have we have such a thing with
+      // x as a live-in.
+      Instruction *CmpIn = cast<Instruction>(Cmp->getOperand(0));
+      if (isa<ConstantInt>(CmpConst) &&
+          CmpIn->getOpcode() == Instruction::Add) {
+        if (!isa<Instruction>(CmpIn->getOperand(0)) ||
+            cast<Instruction>(CmpIn->getOperand(0))->getParent() != BB) {
+          if (auto *AddC = dyn_cast<ConstantInt>(CmpIn->getOperand(1))) {
+            for (BasicBlock *P : predecessors(BB)) {
+              // If the value is known by LazyValueInfo to be a ConstantRange in
+              // a predecessor, use that information to try to thread this
+              // block.
+              ConstantRange CR = LVI->getConstantRangeOnEdge(
+                  CmpIn->getOperand(0), P, BB, CxtI ? CxtI : CmpIn);
+              // Propagate the range through the addition.
+              CR = CR.add(ConstantRange(AddC->getValue()));
+
+              // Get the range where the compare returns true.
+              ConstantRange CmpRange = ConstantRange::makeExactICmpRegion(
+                  Cmp->getPredicate(), cast<ConstantInt>(CmpConst)->getValue());
+
+              Constant *ResC;
+              if (CmpRange.contains(CR))
+                ResC = ConstantInt::getTrue(Cmp->getType());
+              else if (CmpRange.inverse().contains(CR))
+                ResC = ConstantInt::getFalse(Cmp->getType());
+              else
+                continue;
+
+              Result.push_back(std::make_pair(ResC, P));
+            }
+
+            return !Result.empty();
+          }
+        }
+      }
+
       // Try to find a constant value for the LHS of a comparison,
       // and evaluate it statically if we can.
       PredValueInfoTy LHSVals;
       ComputeValueKnownInPredecessors(I->getOperand(0), BB, LHSVals,
                                       WantInteger, CxtI);
 
       for (const auto &LHSVal : LHSVals) {
         Constant *V = LHSVal.first;

test/Transforms/JumpThreading/range-compare.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+;RUN: opt < %s -jump-threading -S | FileCheck %s
+
+
+declare void @bar(...)
+declare void @baz(...)
+
+; Make sure we thread the end of the bar block to the end of the function.
+define void @test1(i32 %x) {
+; CHECK-LABEL: @test1(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[CMP:%.*]] = icmp sgt i32 [[X:%.*]], 9
+; CHECK-NEXT:    br i1 [[CMP]], label [[IF_END_THREAD:%.*]], label [[IF_END:%.*]]
+; CHECK:       if.end.thread:
+; CHECK-NEXT:    call void (...) @bar()
+; CHECK-NEXT:    br label [[IF_END4:%.*]]
+; CHECK:       if.end:
+; CHECK-NEXT:    [[X_OFF:%.*]] = add i32 [[X]], -3
+; CHECK-NEXT:    [[TMP0:%.*]] = icmp ult i32 [[X_OFF]], 5
+; CHECK-NEXT:    br i1 [[TMP0]], label [[IF_THEN3:%.*]], label [[IF_END4]]
+; CHECK:       if.then3:
+; CHECK-NEXT:    call void (...) @baz()
+; CHECK-NEXT:    br label [[IF_END4]]
+; CHECK:       if.end4:
+; CHECK-NEXT:    ret void
+;
+entry:
+  %cmp = icmp sgt i32 %x, 9
+  br i1 %cmp, label %if.then, label %if.end
+
+if.then:                                          ; preds = %entry
+  call void (...) @bar()
+  br label %if.end
+
+if.end:                                           ; preds = %if.then, %entry
+  %x.off = add i32 %x, -3
+  %0 = icmp ult i32 %x.off, 5
+  br i1 %0, label %if.then3, label %if.end4
+
+if.then3:                                         ; preds = %if.end
+  call void (...) @baz()
+  br label %if.end4
+
+if.end4:                                          ; preds = %if.then3, %if.end
+  ret void
+}
+
+; Make sure we thread the false side of the first if to the end of the function.
+define void @test2(i32 %x) {
+; CHECK-LABEL: @test2(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[X:%.*]], 9
+; CHECK-NEXT:    br i1 [[CMP]], label [[IF_END:%.*]], label [[IF_END4:%.*]]
+; CHECK:       if.end:
+; CHECK-NEXT:    call void (...) @bar()
+; CHECK-NEXT:    [[X_OFF:%.*]] = add i32 [[X]], -3
+; CHECK-NEXT:    [[TMP0:%.*]] = icmp ult i32 [[X_OFF]], 5
+; CHECK-NEXT:    br i1 [[TMP0]], label [[IF_THEN3:%.*]], label [[IF_END4]]
+; CHECK:       if.then3:
+; CHECK-NEXT:    call void (...) @baz()
+; CHECK-NEXT:    br label [[IF_END4]]
+; CHECK:       if.end4:
+; CHECK-NEXT:    ret void
+;
+entry:
+  %cmp = icmp slt i32 %x, 9
+  br i1 %cmp, label %if.then, label %if.end
+
+if.then:                                          ; preds = %entry
+  call void (...) @bar()
+  br label %if.end
+
+if.end:                                           ; preds = %if.then, %entry
+  %x.off = add i32 %x, -3
+  %0 = icmp ult i32 %x.off, 5
+  br i1 %0, label %if.then3, label %if.end4
+
+if.then3:                                         ; preds = %if.end
+  call void (...) @baz()
+  br label %if.end4
+
+if.end4:                                          ; preds = %if.then3, %if.end
+  ret void
+}
+
+; Negative test to make sure we don't thread when the ranges overlap.
+define void @test3(i32 %x) {
+; CHECK-LABEL: @test3(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[CMP:%.*]] = icmp sgt i32 [[X:%.*]], 6
+; CHECK-NEXT:    br i1 [[CMP]], label [[IF_THEN:%.*]], label [[IF_END:%.*]]
+; CHECK:       if.then:
+; CHECK-NEXT:    call void (...) @bar()
+; CHECK-NEXT:    br label [[IF_END]]
+; CHECK:       if.end:
+; CHECK-NEXT:    [[X_OFF:%.*]] = add i32 [[X]], -3
+; CHECK-NEXT:    [[TMP0:%.*]] = icmp ult i32 [[X_OFF]], 5
+; CHECK-NEXT:    br i1 [[TMP0]], label [[IF_THEN3:%.*]], label [[IF_END4:%.*]]
+; CHECK:       if.then3:
+; CHECK-NEXT:    call void (...) @baz()
+; CHECK-NEXT:    br label [[IF_END4]]
+; CHECK:       if.end4:
+; CHECK-NEXT:    ret void
+;
+entry:
+  %cmp = icmp sgt i32 %x, 6
+  br i1 %cmp, label %if.then, label %if.end
+
+if.then:                                          ; preds = %entry
+  call void (...) @bar()
+  br label %if.end
+
+if.end:                                           ; preds = %if.then, %entry
+  %x.off = add i32 %x, -3
+  %0 = icmp ult i32 %x.off, 5
+  br i1 %0, label %if.then3, label %if.end4
+
+if.then3:                                         ; preds = %if.end
+  call void (...) @baz()
+  br label %if.end4
+
+if.end4:                                          ; preds = %if.then3, %if.end
+  ret void
+}
+