[JumpThreading] Process range comparisions with non-local cmp instructions

[kachkov98]

Summary

Use getPredicateOnEdge method if value is a non-local compare-with-a-constant instruction,
that can give more precise results than getConstantOnEdge.

[kachkov98]

test-suite results:

Metric: jump-threading.NumThreads

Program                                                                                                           jump-threading.NumThreads                    
                                                                                                                  baseline                  jumpthreading diff 
                                                test-suite :: MultiSource/Benchmarks/MallocBench/cfrac/cfrac.test   14.00                     19.00       35.7%
                                              test-suite :: MultiSource/Benchmarks/Rodinia/backprop/backprop.test    3.00                      4.00       33.3%
                                             test-suite :: SingleSource/Benchmarks/Adobe-C++/functionobjects.test   20.00                     22.00       10.0%
                                         test-suite :: MultiSource/Benchmarks/Prolangs-C/assembler/assembler.test   26.00                     28.00        7.7%
                                                      test-suite :: MultiSource/Applications/obsequi/Obsequi.test   39.00                     42.00        7.7%
                                                  test-suite :: MultiSource/Benchmarks/FreeBench/pifft/pifft.test   43.00                     45.00        4.7%
                                       test-suite :: MultiSource/Applications/ALAC/encode/alacconvert-encode.test   24.00                     25.00        4.2%
                                       test-suite :: MultiSource/Applications/ALAC/decode/alacconvert-decode.test   24.00                     25.00        4.2%
                                           test-suite :: MultiSource/Benchmarks/Prolangs-C/unix-tbl/unix-tbl.test   51.00                     53.00        3.9%
                                                     test-suite :: MultiSource/Applications/JM/lencod/lencod.test  704.00                    726.00        3.1%
                                           test-suite :: MultiSource/Benchmarks/Prolangs-C/football/football.test   89.00                     91.00        2.2%
                                                   test-suite :: MultiSource/Benchmarks/mafft/pairlocalalign.test  326.00                    333.00        2.1%
                                                     test-suite :: MultiSource/Applications/JM/ldecod/ldecod.test  345.00                    352.00        2.0%
                                                 test-suite :: MultiSource/Benchmarks/Prolangs-C/agrep/agrep.test   52.00                     53.00        1.9%
                                                        test-suite :: MultiSource/Applications/treecc/treecc.test   56.00                     57.00        1.8%
                                                            test-suite :: MultiSource/Benchmarks/PAQ8p/paq8p.test  112.00                    114.00        1.8%
                                          test-suite :: MultiSource/Benchmarks/MallocBench/espresso/espresso.test  117.00                    119.00        1.7%
                                                      test-suite :: MultiSource/Applications/ClamAV/clamscan.test 1365.00                   1384.00        1.4%
                                                  test-suite :: MultiSource/Applications/lambda-0.1.3/lambda.test   74.00                     75.00        1.4%
                                          test-suite :: MultiSource/Benchmarks/DOE-ProxyApps-C++/CLAMR/CLAMR.test  746.00                    755.00        1.2%
                                                      test-suite :: MultiSource/Applications/sqlite3/sqlite3.test 1518.00                   1534.00        1.1%
                                    test-suite :: MultiSource/Benchmarks/MiBench/office-ispell/office-ispell.test  110.00                    111.00        0.9%
                                                              test-suite :: MultiSource/Applications/lua/lua.test  229.00                    231.00        0.9%
                                    test-suite :: MultiSource/Benchmarks/MiBench/consumer-jpeg/consumer-jpeg.test  126.00                    127.00        0.8%
                                          test-suite :: MultiSource/Benchmarks/mediabench/jpeg/jpeg-6a/cjpeg.test  137.00                    138.00        0.7%
                                                      test-suite :: MultiSource/Benchmarks/MallocBench/gs/gs.test  288.00                    290.00        0.7%
                                                          test-suite :: MultiSource/Applications/SPASS/SPASS.test 1205.00                   1212.00        0.6%
                                   test-suite :: MultiSource/Benchmarks/Prolangs-C/TimberWolfMC/timberwolfmc.test  211.00                    212.00        0.5%
                                                        test-suite :: MultiSource/Applications/oggenc/oggenc.test  324.00                    325.00        0.3%
                                                          test-suite :: MultiSource/Benchmarks/Bullet/bullet.test  554.00                    555.00        0.2%
                                                    test-suite :: MultiSource/Benchmarks/7zip/7zip-benchmark.test 1731.00                   1734.00        0.2%

[nikic]

LGTM

[kachkov98]

Thank you @nikic! I don't have commit access, could you please submit it?

[nikic]

Sure, could you please share Name <email> to use for the commit?

[kachkov98]

In D131956#3766304, @nikic wrote:

Sure, could you please share Name <email> to use for the commit?

Sergey Kachkov [e-mail]

llvm/lib/Transforms/Scalar/JumpThreading.cpp

if (Constant *KC = getKnownConstant(V, Preference)) {
     return !Result.empty();
   }
 
   // If V is a non-instruction value, or an instruction in a different block,
   // then it can't be derived from a PHI.
   Instruction *I = dyn_cast<Instruction>(V);
   if (!I || I->getParent() != BB) {
 
-    // Okay, if this is a live-in value, see if it has a known value at the end
-    // of any of our predecessors.
-    //
-    // FIXME: This should be an edge property, not a block end property.
-    /// TODO: Per PR2563, we could infer value range information about a
-    /// predecessor based on its terminator.
-    //
-    // FIXME: change this to use the more-rich 'getPredicateOnEdge' method if
-    // "I" is a non-local compare-with-a-constant instruction.  This would be
-    // able to handle value inequalities better, for example if the compare is
-    // "X < 4" and "X < 3" is known true but "X < 4" itself is not available.
-    // Perhaps getConstantOnEdge should be smart enough to do this?
+    // Okay, if this is a live-in value, see if it has a known value at the any
+    // edge from our predecessors.
     for (BasicBlock *P : predecessors(BB)) {
+      using namespace PatternMatch;
       // If the value is known by LazyValueInfo to be a constant in a
       // predecessor, use that information to try to thread this block.
       Constant *PredCst = LVI->getConstantOnEdge(V, P, BB, CxtI);
+      // If I is a non-local compare-with-constant instruction, use more-rich
+      // 'getPredicateOnEdge' method. This would be able to handle value
+      // inequalities better, for example if the compare is "X < 4" and "X < 3"
+      // is known true but "X < 4" itself is not available.
+      CmpInst::Predicate Pred;
+      Value *Val;
+      Constant *Cst;
+      if (!PredCst && match(V, m_Cmp(Pred, m_Value(Val), m_Constant(Cst)))) {
+        auto Res = LVI->getPredicateOnEdge(Pred, Val, Cst, P, BB, CxtI);
+        if (Res != LazyValueInfo::Unknown)
+          PredCst = ConstantInt::getBool(V->getContext(), Res);
+      }
       if (Constant *KC = getKnownConstant(PredCst, Preference))
         Result.emplace_back(KC, P);
     }
 
     return !Result.empty();
   }
 
   /// If I is a PHI node, then we know the incoming values for any constants.

llvm/test/Transforms/JumpThreading/range-compare.ll

 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
+; (case with non-local comparisions).
+define void @test4(i32 %x) {
+; CHECK-LABEL: @test4(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[CMP1:%.*]] = icmp slt i32 [[X:%.*]], 9
+; CHECK-NEXT:    [[X_OFF:%.*]] = add i32 [[X]], -3
+; CHECK-NEXT:    [[CMP2:%.*]] = icmp ult i32 [[X_OFF]], 5
+; CHECK-NEXT:    br i1 [[CMP1]], label [[IF_END:%.*]], label [[IF_END4:%.*]]
+; CHECK:       if.end:
+; CHECK-NEXT:    call void (...) @bar()
+; CHECK-NEXT:    br i1 [[CMP2]], 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:
+  %cmp1 = icmp slt i32 %x, 9
+  %x.off = add i32 %x, -3
+  %cmp2 = icmp ult i32 %x.off, 5
+  br i1 %cmp1, label %if.then, label %if.end
+
+if.then:                                          ; preds = %entry
+  call void (...) @bar()
+  br label %if.end
+
+if.end:                                           ; preds = %if.then, %entry
+  br i1 %cmp2, 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
+}
+