[LLVMdev] IR Passes and TargetTransformInfo: Straw Man

[Andrew Trick]

On Jul 29, 2013, at 9:05 AM, Krzysztof Parzyszek <kparzysz at codeaurora.org> wrote:

> On 7/16/2013 11:38 PM, Andrew Trick wrote:
>> Since introducing the new TargetTransformInfo analysis, there has been some confusion over the role of target heuristics in IR passes. A few patches have led to interesting discussions.
>> 
>> To centralize the discussion, until we get some documentation and better APIs in place, let me throw out an oversimplified Straw Man for a new pass pipline. It serves two purposes: (1) an overdue reorganization of the pass pipeline (2) a formalization of the role of TargetTransformInfo.
>> 
>> ---
>> Canonicalization passes are designed to normalize the IR in order to expose opportunities to subsequent machine independent passes. This simplifies writing machine independent optimizations and improves the quality of the compiler.
>> 
>> An important property of these passes is that they are repeatable. The may be invoked multiple times after inlining and should converge to a canonical form. They should not destructively transform the IR in a way that defeats subsequent analysis.
>> 
>> Canonicalization passes can make use of data layout and are affected by ABI, but are otherwise target independent. Adding target specific hooks to these passes can defeat the purpose of canonical IR.
>> 
>> IR Canonicalization Pipeline:
>> 
>> Function Passes {
>>   SimplifyCFG
>>   SROA-1
>>   EarlyCSE
>> }
>> Call-Graph SCC Passes {
>>   Inline
>>   Function Passes {
>>     EarlyCSE
>>     SimplifyCFG
>>     InstCombine
>>     Early Loop Opts {
>>       LoopSimplify
>>       Rotate (when obvious)
>>       Full-Unroll (when obvious)
>>     }
>>     SROA-2
>>     InstCombine
>>     GVN
>>     Reassociate
>>     Generic Loop Opts {
>>       LICM (Rotate on-demand)
>>       Unswitch
>>     }
>>     SCCP
>>     InstCombine
>>     JumpThreading
>>     CorrelatedValuePropagation
>>     AggressiveDCE
>>   }
>> }
>> 
> 
> I'm a bit late to this, but the examples of the "generic loop opts" above are really better left until later.  They have a potential to obscure the code and make other loop optimizations harder. Specifically, there has to be a place where loop nest optimizations can be done (such as loop interchange or unroll-and-jam).  There is also array expansion and loop distribution, which can be highly target-dependent in terms of their applicability.  I don't know if TTI could provide enough details to account for all circumstances that would motivate such transformations, but assuming that it could, there still needs to be a room left for it in the design.

You mean that LICM and Unswitching should be left for later? For the purpose of exposing scalar optimizations, I'm not sure I agree with that but I'd be interested in examples.

I think you're only worried about the impact on loop nest optimizations. Admittedly I'm not making much concessesion for that, because I think of loop nest optimization as a different tool that will probably want fairly substantial changes to the pass pipeline anyway. Here's a few of ways it might work:

(1) Loop nest optimizer extends the standard PMB by plugging in its own passes prior to Generic Loop Opts in addition to loading TTI. The loop nest optimizer's passes are free to query TTI:

(2) Loop nest optimizer suppresses generic loop opts through a PMB flag (assuming they are too disruptive). It registers its own loop passes with the Target Loop Opts. It registers instances of generic loop opts to now run after loop nest optimization, and registers new instances of scalar opts to rerun after Target Loop Opts if needed.

(3) If the loop nest optimizer were part of llvm core libs, then we could have a completely separate passmanager builder for it.

> On a different, but related note---one thing I've asked recently was about the "proper" solution for recognizing target specific loop idioms.  On Hexagon, we have a builtin functions that handle certain specific loop patterns.  In order to separate the target-dependent code from the target-independent, we would basically have to replicate the loop idiom recognition in our own target-specific pass.  Not only that, but it would have to run before the loops may be subjected to other optimizations that could obfuscate the opportunity.  To solve this, I was thinking about having target-specific hooks in the idiom recognition code, that could transform a given loop in the target's own way.  Still, that would imply target-specific transformations running before the "official" lowering code.

We may be able to run loop idiom recognition as part of Target Loop Opts. If that misses too many optimizations, then targets can add a second instance of loop-idiom in the target loop opts. Target's can also add extra instances of scalar opts passes in the lowering pipeline, if needed, to cleanup. The lowering pass order should be completely configurable.

Are you afraid that LICM and unswitching will obfuscate the loops to the point that you can’t recognize the idiom? The current pass pipeline would have the same problem.

-Andy