TLDR: We should add a representation for icmp to SCEV’s expression language. In the near term, this will simplify predication and predicate evaluation. In the longer term, we can consider whether we want to analyze arbitrary icmp instructions.
Today, SCEV does not represent arbitrary comparisons. We have a bunch of code for reasoning about comparisons, but the selection of these comparisons is entirely outside of SCEV’s core logic. (Mostly in IndVarSimplify, some in various other places.) The two exceptions to this that live in SCEV itself are a) comparisons controlling exiting edges, and b) conditions used by selects.
⚙ D119558 [SCEV] Add SCEVCompareExpr node proposes introducing a new SCEV expression node for representing an arbitrary comparison. This email is basically a summary of why I think this is a good idea.
Simplifying and Generalizing PredicatedScalarEvolution
Once we have a generalized SCEVCompareExpr, we can rewrite the SCEVPredicate hierarchy into a simple wrapper around an i1 SCEV expression. This should let us delete all most all the code that deals with SCEVPredicates. A first step towards this objective is up for review here: ⚙ D119631 [SCEV] Replace SCEVComparePredicate with a wrapped SCEV expression.
Additionally, having SCEVPredicate be a simple wrapper around a SCEV expression enables generalized predicates. Right now, SCEVPredicate can only represent not(and(wrappredicate…, icmppredicate…)). We have cases even today where LoopVersioning needs more complicated predicates (and thus duplicates logic to avoid using SCEVPredicate), and we’ve had this come up recently on the loop optimization working group as well.
Let me stop and address an obvious alternative here. We could simply extend the SCEVPredicate hierarchy with additional boolean expression nodes. I’ve looked at this - it was actually my first idea here - and ended up deciding this was not a good direction to go in for a couple of reasons:
- SCEVPredicate is currently a bit of a mess implementation wise. As an example, SCEVUnionPredicate is - despite being a subclass of a FoldingSetNode - only stack allocateable. I have a local patch which addresses this, but it ends up basically being a complete rewrite of the SCEVPredicate code.
- If we were to extend the hierarchy, we’d end up duplicating a bunch of logic (expander, simplification, implication, etc…). This makes the code harder to maintain, harder to test, and reduces the expected quality of implementation.
- We already have in SCEV itself a way to represent a generalized boolean expression (except the raw compare). We use umin for AND, umax for OR, 1 - X for NOT. We can argue about whether this is the best possible representation, but the key point is we already have it, it’s reasonable well tested, and we already have a good chunk of the simplification rules and expansion implemented.
Simplifying Predicate Logic
Today, SCEV has a whole family of routines for reasoning about and attempting to optimize comparisons. (See isKnownPredicate, getLoopInvariant*, isImpliedCond, and many of their users.)
I believe it makes sense to move much of this logic inside SCEVCompareExpr::get. Not all of it - for instance, the forking analysis performed during isKnownPredicateViaSplitting probably makes sense to leave where it is. The result of this move will be both a) more consistency in the simplification tactics we apply and b) probably the ability to replace some icmp specific transforms with generic code (e.g. getInvariantCond can be removed since generic code will now handle.)
The obvious alternative is just to have a common routine for canonicalizing compare operands (e.g. pred, lhs, rhs). This is sort of what SimplifyICmpOperands does today. There’s two basic reasons why I believe having a SCEVCompareExpr is the better answers here:
- Not all of the simplifications make sense expressed in terms of the operands of a compare. For instance, cmp eq a, a should simplify to “true”, not another icmp. As another example, icmp ne zext i1 %a, zext i1 %b should simplify to %a xor %b, not another icmp. (This later case is an example that we don’t implement today.)
- In SCEV, we have an idiomatic pattern for expressing such simplify on construction patterns; the use of an SCEVXExpr::get routine. Finding another way to spell it, just to avoid a SCEVCompareExpr seems forced to me.
I’ll note that there’s potentially a compile time benefit to canonicalizing conditions once before analyzing them, but that’s speculative enough that we should not consider that a justification for the proposal. I really doubt we’ll get slower, but faster may or may not happen.
Recognizing Compares in IR
The least obviously worthwhile application is extending getSCEV to generate SCEVCompareExpr nodes for icmps seen in the original IR. We clearly want a mode to do this for testing at the least, but enabling this by default seems questionable to me at this time.
It would let us reframe the computeExitLimitFromX code in terms of reasoning about SCEV expressions instead of IR, but I don’t know that’s a meaningful win code structure wise and I haven’t yet found cases where this gets us meaningfully better results.
I don’t currently have examples to strongly motivate spending the compile time to construct a SCEV for all icmp instructions. With that in mind, I currently propose adding the SCEVCompareExpr, but not extending getSCEV to directly use them. This is slightly different than saying we’d never see them in SCEV expressions. If a compare is a simpler way to represent some other expressible structure, we could chose to canonicalize towards a compare. However, I don’t have any candidates for that today, and each should be subject to it’s own review.
As a final point, gather data on whether extend getSCEV makes sense is much easier if we already have the node in tree, and have extended the various simplification rules in individual reviews. 
In Conclusion
I’ve laid out a couple of applications of a proposed SCEVCompareExpr. To me, the code clarity we get from having the node, and the potential canonicalization benefits during predicate analysis seem worthwhile. Not an obvious slam dunk, but worthwhile.
I think this at a minimum clears the bar of being a reasonable thing to attempt. We may try it, and later decide we want to back away and take a different direction, but I think it’s entirely reasonable to try it in tree with the expectation that we’ll reevaluate based on practical experience gathered over weeks and months.
Thoughts?