[SCEV][NFC] Check NoWrap flags before lexicographical comparison of SCEVs

[mkazantsev]

Summary

Lexicographical comparison of SCEV trees is potentially expensive for big
expression trees. We can define ordering between them for AddRecs and
N-ary operations by SCEV NoWrap flags to make non-equality check
cheaper.

This change does not prevent grouping eqivalent SCEVs together and is
not supposed to have any meaningful impact on behavior of any transforms.

[sanjoy]

lgtm

[rtereshin]

llvm/trunk/lib/Analysis/ScalarEvolution.cpp

699 ↗

(On Diff #125704)

Hi everyone,

Unfortunately, wrapping flags are not a part of SCEV's identity (they do not participate in computing a hash value or in equality comparisons) and in fact they could be assigned after the fact w/o rebuilding a SCEV.

At least, last time I checked it was that way. Grep for const_cast's to see quite a few of example, AFAIR all for AddRec's.

So, if 2 expressions get built in 2 slightly different ways: one with flags set in the beginning, the other with the flags attached later on, we may end up with 2 expressions which are exactly the same but have their operands swapped in one of the commutative N-ary expressions, and at least one of them will have "sorted by complexity" invariant broken.

2 identical SCEV's won't compare equal by pointer comparison as they are supposed to.

I didn't verify this with an experiment yet, please correct me if I'm wrong.

Thanks,
Roman

[mkazantsev]

llvm/trunk/lib/Analysis/ScalarEvolution.cpp

699 ↗

(On Diff #125704)

I think you are right, and it's a good reason to revert this patch. Please do so with checking in a test where it shows up. Good catch!

[rtereshin]

llvm/trunk/lib/Analysis/ScalarEvolution.cpp

699 ↗

(On Diff #125704)

Done as requested.

The revert is currently a part of https://reviews.llvm.org/D51014 aiming to gain back the compile time improvements, I will update the diff so it does not include the revert a bit later.

Also, I wasn't able to actually see any compile time regression with the revert yet as I'm not sure what to benchmark exactly. One benchmark I'm trying builds very large SCEVs and spends the absolute majority of the time doing getSCEV, and that benchmark show near-noise difference in time spent in compareSCEVComplexity as well as in getSCEV between TOT with and without the revert.

lib/Analysis/ScalarEvolution.cpp

if (LLoop != RLoop) {
       return -1;
     }
 
     // Addrec complexity grows with operand count.
     unsigned LNumOps = LA->getNumOperands(), RNumOps = RA->getNumOperands();
     if (LNumOps != RNumOps)
       return (int)LNumOps - (int)RNumOps;
 
+    // Compare NoWrap flags.
+    if (LA->getNoWrapFlags() != RA->getNoWrapFlags())
+      return (int)LA->getNoWrapFlags() - (int)RA->getNoWrapFlags();
+
     // Lexicographically compare.
     for (unsigned i = 0; i != LNumOps; ++i) {
       int X = CompareSCEVComplexity(EqCacheSCEV, LI, LA->getOperand(i),
                                     RA->getOperand(i), DT,  Depth + 1);
       if (X != 0)
         return X;
     }
     EqCacheSCEV.unionSets(LHS, RHS);
     return 0;
   }
 
   case scAddExpr:
   case scMulExpr:
   case scSMaxExpr:
   case scUMaxExpr: {
     const SCEVNAryExpr *LC = cast<SCEVNAryExpr>(LHS);
     const SCEVNAryExpr *RC = cast<SCEVNAryExpr>(RHS);
 
     // Lexicographically compare n-ary expressions.
     unsigned LNumOps = LC->getNumOperands(), RNumOps = RC->getNumOperands();
     if (LNumOps != RNumOps)
       return (int)LNumOps - (int)RNumOps;
 
+    // Compare NoWrap flags.
+    if (LC->getNoWrapFlags() != RC->getNoWrapFlags())
+      return (int)LC->getNoWrapFlags() - (int)RC->getNoWrapFlags();
+
     for (unsigned i = 0; i != LNumOps; ++i) {
       int X = CompareSCEVComplexity(EqCacheSCEV, LI, LC->getOperand(i),
                                     RC->getOperand(i), DT, Depth + 1);
       if (X != 0)
         return X;
     }
     EqCacheSCEV.unionSets(LHS, RHS);
     return 0;