[llvm-dev] Loop identification

[Krzysztof Parzyszek via llvm-dev]

On 1/13/2017 11:25 AM, Mehdi Amini wrote:
> This seems quite contradictory with what I was constantly told about the goal of inst-combine, i.e. it is supposed to canonicalize the IR to make it easier for further passes to recognize patterns.

Chris has described the "canonical form" as one that has been "maximally 
strength-reduced". The problem with this is that it is very vague:
- Whether you can simplify something further often depends on how 
complex the simplification code can become.  Also, the equivalency 
problem is provably unsolvable, so there isn't a hard stop at which it 
can reliably determine that "this is the final form".
- It doesn't tell the consumers what really they should expect to see in 
the reduced code, and what should be folded/simplified. Sure, you can 
read the combiner source, but that may change in the next commit.

I've seen the same problem with SimpilfyCFG a few years back. It would 
go bonkers trying to simplify branches, and as a result it would create 
some degenerate loop nest out of a single loop with a simple conditional 
"continue" statement in it. We've had to add some code to throttle it 
back or otherwise the outcome was just too complex to analyze without 
writing a loop nest optimizer. (I don't know what it's like now, I 
haven't looked at it lately).

We have the same thing yet again in the DAG combiner, where the rules 
are listed in the comments, instead of being listed in the 
documentation. People write selection patterns that need to match the 
actual DAGs, and knowing what form the code will take would certainly be 
of help.


A canonicalizer should, above all, make the code look predictable 
instead of trying hard to make it optimal, and that's not something that 
I have confidence in at the moment.

-Krzysztof


-- 
Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, 
hosted by The Linux Foundation