[SCEV] Apply conditions involving constants first in applyLoopGuards.

[fhahn]

Summary

In some cases the order conditions are applied in can pessimize results.
In general, applying conditions with constant operands should lead to
better results. I think ideally we would apply conditions with operands
that are not involved in any other condition first, but processing
conditions with constants should be a good start.

Alternatively we could re-write all collected expressions after
collecting them. But that's likely more expensive.

Depends on D126460.

Fixes #55645.

[nikic]

llvm/lib/Analysis/ScalarEvolution.cpp

14565

I don't understand this comparison function. If A is constant and B is not, this returns that A is smaller than B. If B is constant and A is not then ... this also returns that A is smaller than B?

[fhahn]

Thanks for taking a look! Unfortunately this only worked by accident and I missed that there aren't any tests with the conditions in reverse order.

I think the real issue here is that we need to apply the conditions that constraint the value range first and the rewriting as multiple last.

[fhahn]

Update sort order to apply conditions that constraint ranges using max/min (predicates != EQ & != NE).

This ensures we rewrite conditons involving URem checks last, which can lead to better results.

[alonkom]

llvm/lib/Analysis/ScalarEvolution.cpp

14554

Even with this sorting won't we lose information about the min/max values of the value?
For example if we know (tc > 0) and (tc % 8 == 0) and we process (tc % 8 == 0) last, AFAIU the SCEV expression will be overridden to (tc / 8) * 8 and we'll lose the fact that the trip count is also positive.

[nikic]

llvm/lib/Analysis/ScalarEvolution.cpp

14563

There may be range comparisons using eq/ne as well, with != 0 probably being the only important one. Possibly we should not be collecting Terms but already classified conditions (i.e. either known factor or known range limit)?

[mkazantsev]

llvm/lib/Analysis/ScalarEvolution.cpp

14560

Use isRelational

[mkazantsev]

Marking as "request changes" just to reduce my list. Feel free to update when the comments are addressed!

llvm/test/Analysis/ScalarEvolution/trip-multiple-guard-info.ll

107

Precommit test?

llvm/lib/Analysis/ScalarEvolution.cpp

const BranchInst *LoopEntryPredicate =
         dyn_cast<BranchInst>(Pair.first->getTerminator());
     if (!LoopEntryPredicate || LoopEntryPredicate->isUnconditional())
       continue;
 
     Terms.emplace_back(LoopEntryPredicate->getCondition(),
                        LoopEntryPredicate->getSuccessor(0) == Pair.second);
   }
 
+  // Sort conditions so that conditions that tighten ranges of values come last.
+  // This allows processing them first in the loop below, which can lead to more
+  // effective expression rewriting.
+  stable_sort(Terms, [this](const std::pair<Value *, bool> &A,
+                            const std::pair<Value *, bool> &B) {
+    auto *CmpA = dyn_cast<ICmpInst>(A.first);
+    auto *CmpB = dyn_cast<ICmpInst>(B.first);
+    if (!CmpA || !CmpB)
+      return false;
+    bool IsRangeA = CmpA->getPredicate() != CmpInst::ICMP_NE &&
+                    CmpA->getPredicate() != CmpInst::ICMP_EQ;
+    bool IsRangeB = CmpB->getPredicate() != CmpInst::ICMP_NE &&
+                    CmpB->getPredicate() != CmpInst::ICMP_EQ;
+    return IsRangeA < IsRangeB;
+  });
+
   // Now apply the information from the collected conditions to RewriteMap.
   // Conditions are processed in reverse order, so the earliest conditions is
   // processed first. This ensures the SCEVs with the shortest dependency chains
   // are constructed first.
   DenseMap<const SCEV *, const SCEV *> RewriteMap;
   for (auto &E : reverse(Terms)) {
     bool EnterIfTrue = E.second;
     SmallVector<Value *, 8> Worklist;

llvm/test/Analysis/ScalarEvolution/trip-multiple-guard-info.ll

 }
 
 
 define void @test_trip_multiple_4_ugt_5(i32 %num) {
 ; CHECK-LABEL: @test_trip_multiple_4_ugt_5
 ; CHECK:       Loop %for.body: backedge-taken count is (-1 + %num)
 ; CHECK-NEXT:  Loop %for.body: max backedge-taken count is -2
 ; CHECK-NEXT:  Loop %for.body: Predicated backedge-taken count is (-1 + %num)
-; CHECK:       Loop %for.body: Trip multiple is 2
+; CHECK:       Loop %for.body: Trip multiple is 4
 ;
 entry:
   %u = urem i32 %num, 4
   %cmp = icmp eq i32 %u, 0
   tail call void @llvm.assume(i1 %cmp)
   %cmp.1 = icmp ugt i32 %num, 5
   tail call void @llvm.assume(i1 %cmp.1)
   br label %for.body
 
 for.body:
   %i.010 = phi i32 [ 0, %entry ], [ %inc, %for.body ]
   %inc = add nuw nsw i32 %i.010, 1
   %cmp2 = icmp ult i32 %inc, %num
   br i1 %cmp2, label %for.body, label %exit
 
 exit:
   ret void
 }
 
 define void @test_trip_multiple_4_sgt_5(i32 %num) {
 ; CHECK-LABEL: @test_trip_multiple_4_sgt_5
 ; CHECK:       Loop %for.body: backedge-taken count is (-1 + %num)
 ; CHECK-NEXT:  Loop %for.body: max backedge-taken count is 2147483646
 ; CHECK-NEXT:  Loop %for.body: Predicated backedge-taken count is (-1 + %num)
-; CHECK:       Loop %for.body: Trip multiple is 2
+; CHECK:       Loop %for.body: Trip multiple is 4
 ;
 entry:
   %u = urem i32 %num, 4
   %cmp = icmp eq i32 %u, 0
   tail call void @llvm.assume(i1 %cmp)
   %cmp.1 = icmp sgt i32 %num, 5
   tail call void @llvm.assume(i1 %cmp.1)
   br label %for.body
 
 for.body:
   %i.010 = phi i32 [ 0, %entry ], [ %inc, %for.body ]
   %inc = add nuw nsw i32 %i.010, 1
   %cmp2 = icmp slt i32 %inc, %num
   br i1 %cmp2, label %for.body, label %exit
 
 exit:
   ret void
 }
 
 define void @test_trip_multiple_4_uge_5(i32 %num) {
 ; CHECK-LABEL: @test_trip_multiple_4_uge_5
 ; CHECK:       Loop %for.body: backedge-taken count is (-1 + %num)
 ; CHECK-NEXT:  Loop %for.body: max backedge-taken count is -2
 ; CHECK-NEXT:  Loop %for.body: Predicated backedge-taken count is (-1 + %num)
-; CHECK:       Loop %for.body: Trip multiple is 1
+; CHECK:       Loop %for.body: Trip multiple is 4
 ;
 entry:
   %u = urem i32 %num, 4
   %cmp = icmp eq i32 %u, 0
   tail call void @llvm.assume(i1 %cmp)
   %cmp.1 = icmp uge i32 %num, 5
   tail call void @llvm.assume(i1 %cmp.1)
   br label %for.body
 
 for.body:
   %i.010 = phi i32 [ 0, %entry ], [ %inc, %for.body ]
   %inc = add nuw nsw i32 %i.010, 1
   %cmp2 = icmp ult i32 %inc, %num
   br i1 %cmp2, label %for.body, label %exit
 
 exit:
   ret void
 }
 
+define void @test_trip_multiple_4_uge_5_order_swapped(i32 %num) {
+; CHECK-LABEL: @test_trip_multiple_4_uge_5_order_swapped
+; CHECK:       Loop %for.body: backedge-taken count is (-1 + %num)
+; CHECK-NEXT:  Loop %for.body: max backedge-taken count is -2
+; CHECK-NEXT:  Loop %for.body: Predicated backedge-taken count is (-1 + %num)
+; CHECK:       Loop %for.body: Trip multiple is 4
+;
+entry:
+  %u = urem i32 %num, 4
+  %cmp = icmp eq i32 %u, 0
+  %cmp.1 = icmp uge i32 %num, 5
+  tail call void @llvm.assume(i1 %cmp.1)
+  tail call void @llvm.assume(i1 %cmp)
+  br label %for.body
+
+for.body:
+  %i.010 = phi i32 [ 0, %entry ], [ %inc, %for.body ]
+  %inc = add nuw nsw i32 %i.010, 1
+  %cmp2 = icmp ult i32 %inc, %num
+  br i1 %cmp2, label %for.body, label %exit
+
+exit:
+  ret void
+}
+
 define void @test_trip_multiple_4_sge_5(i32 %num) {
 ; CHECK-LABEL: @test_trip_multiple_4_sge_5
 ; CHECK:       Loop %for.body: backedge-taken count is (-1 + %num)
 ; CHECK-NEXT:  Loop %for.body: max backedge-taken count is 2147483646
 ; CHECK-NEXT:  Loop %for.body: Predicated backedge-taken count is (-1 + %num)
-; CHECK:       Loop %for.body: Trip multiple is 1
+; CHECK:       Loop %for.body: Trip multiple is 4
 ;
 entry:
   %u = urem i32 %num, 4
   %cmp = icmp eq i32 %u, 0
   tail call void @llvm.assume(i1 %cmp)
   %cmp.1 = icmp sge i32 %num, 5
   tail call void @llvm.assume(i1 %cmp.1)
   br label %for.body