llvm dev - Jul 2013 - [LLVMdev] IR Passes and TargetTransformInfo: Straw Man

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

On 7/29/2013 6:28 PM, Andrew Trick wrote:
>
> 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.
Optimizations like LICM, and unswitching can potentially damage perfect 
nesting of loops.  For example, consider this nest:

   for (i) {
     for (j) {
       ... = A[i];
     }
   }

The load of A[i] is invariant in the j-loop (assuming no aliased 
stores), and even if it was not invariant, the address computation code 
is.  A pass of LICM could then generate something like this:

   for (i) {
     t = A[i];
     for (j) {
       ... = t;
     }
   }

This is no longer a perfect nest, and a variety of loop nest 
optimizations will no longer be applicable.  In general, nest 
optimizations have a greater potential for improving code performance 
than scalar optimizations, and should be given priority over them.  In 
most cases (excluding loop interchange, for example), the LICM 
opportunity will remain, and can be taken care of later.


An example of where the target-dependent factors come into the picture 
before the target-specific stage (target-specific optimizations, 
lowering, etc.), may be loop distribution.  The example below does not 
belong to the nest optimizations, but the generic target-independent 
scalar optimizations will still apply after this transformation.
Say that we have a loop that performs several computations, some of 
which may be amenable to more aggressive optimizations:

   for (i) {
     v = 1.0/(1.0 + A[i]*A[i]);
     B[i] = (1.0 - B[i])*v
   }

Suppose that we have a hardware that can perform very fast FMA 
operations (possibly vectorized).  We could transform the loop into

   for (i) {
     t = 1.0 + A[i]*A[i];
     v = 1.0/t;
     B[i] = (1.0 - B[i])*v;
   }

And then expand t into an array, and distribute the loop:

   for (i) {
     t[i] = 1.0 + A[i]*A[i];
   }
   for (i) {
     v = 1.0/t[i];
     B[i] = (1.0 - B[i])*v;
   }

The first loop may then be unrolled and vectorized, while the second one 
may simply be left alone.

This may be difficult to address in a target-independent way (via a 
generic TTI interface), since we are trying to identify a specific 
pattern that, for the specific hardware, may be worth extracting out of 
a more complex loop.  In addition to that, for this example to make 
sense, the vectorization passes would have to run afterwards, which 
would then put a bound on how late this transformation could be done.

I guess the approach of being able to extend/modify what the PMB 
creates, that you mention below, would address this problem.

> 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.
Yes, I agree.  My major concern is that we need to be careful that we 
don't accidentally make things harder for ourselves.  I very much agree 
with the canonicalization approach, and loop nests can take a bit of 
preparation (even including loop distribution).  At the same time, there 
are other optimizations that will destroy the canonical structures (of 
loops, loop nests, etc.), that also need to take place at some point. 
There should be a place in the optimization sequence, where the 
"destructive" optimizations have not yet taken place, and where the 
"constructive" (canonical) passes can be executed.  The farther down
the
optimization stream we push the "destructive" ones, the more
flexibility
we will have as to what types of transformations can be done that 
require the code to be in a canonical form.

> 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.
All of these approaches would work (even concurrently).  I think (3) 
could potentially be the future goal.

> 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.
Actually, in this case my concern was the interleaving of the 
target-dependent code with target-independent code (if we were to do all 
idiom recognition in the same pass), or code duplication (if the 
target-independent and target-dependent passes were to be separate). 
The more I think about it, the more I favor the "separate" approach, 
since the target-specific idioms may be very different for different 
targets, and there doesn't seem to be much that can be handled in a 
common code (hence not a lot of actual duplication would happen).

-Krzysztof


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

On 7/30/13 7:35 AM, Krzysztof Parzyszek wrote:
> On 7/29/2013 6:28 PM, Andrew Trick wrote:
>>
>> 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.
>
> Optimizations like LICM, and unswitching can potentially damage 
> perfect nesting of loops.  For example, consider this nest:
>
>   for (i) {
>     for (j) {
>       ... = A[i];
>     }
>   }
>
> The load of A[i] is invariant in the j-loop (assuming no aliased 
> stores), and even if it was not invariant, the address computation 
> code is.  A pass of LICM could then generate something like this:
>
>   for (i) {
>     t = A[i];
>     for (j) {
>       ... = t;
>     }
>   }
>
> This is no longer a perfect nest, and a variety of loop nest 
> optimizations will no longer be applicable.  In general, nest 
> optimizations have a greater potential for improving code performance 
> than scalar optimizations, and should be given priority over them.  In 
> most cases (excluding loop interchange, for example), the LICM 
> opportunity will remain, and can be taken care of later.
>
Yes, LICM will make perfect nesting become imperfect. When I define 
pre-ipo pass, I also take this into account as well.
I think for a while, and are not able to figure out any strong reason 
for running or not running LICM in pre-ipo pass,
or other compilation phase before LNO.

   The pro for running LICM early is that it may move big redundant 
stuff out of loop nest. You never know
how big it is.  In case you are lucky , you can move lot of stuff out of
loop, the loop may become much smaller and hence enable lots of 
downstream optimizations. This sound
to be a big win for control-intensive programs where Loop-nest-opt 
normally is a big, expensive no-op.

   The con side is that, as you said, the nest is not perfect any more. 
However, I would argue LNO optimizations
should be able to tackle the cases when imperfect part is simple enough 
(say, no call, no control etc).
(FYI, Open64's LNO is able to tackle imperfect nesting so long as 
imperfect part is simple).  Or you just reverse
the LICM, that dosen't sound hard.

   Similar argument for unswitching, you  can run fusion to reverse the 
unswitching, and you certainly need
this opt to transform input nest into appropriate form.

   While this sound bit lame for those HPC thinking folks,  the majority 
care the performance of control intensive
programs. The design have to make the later happy:-)

On Jul 30, 2013, at 7:35 AM, Krzysztof Parzyszek <kparzysz at
codeaurora.org> wrote:
> On 7/29/2013 6:28 PM, Andrew Trick wrote:
>> 
>> 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.
> 
> Optimizations like LICM, and unswitching can potentially damage perfect
nesting of loops.  For example, consider this nest:
> 
>  for (i) {
>    for (j) {
>      ... = A[i];
>    }
>  }
> 
> The load of A[i] is invariant in the j-loop (assuming no aliased stores),
and even if it was not invariant, the address computation code is.  A pass of
LICM could then generate something like this:
> 
>  for (i) {
>    t = A[i];
>    for (j) {
>      ... = t;
>    }
>  }
> 
> This is no longer a perfect nest, and a variety of loop nest optimizations
will no longer be applicable.  In general, nest optimizations have a greater
potential for improving code performance than scalar optimizations, and should
be given priority over them.  In most cases (excluding loop interchange, for
example), the LICM opportunity will remain, and can be taken care of later.
> 
> 
> An example of where the target-dependent factors come into the picture
before the target-specific stage (target-specific optimizations, lowering,
etc.), may be loop distribution.  The example below does not belong to the nest
optimizations, but the generic target-independent scalar optimizations will
still apply after this transformation.
> Say that we have a loop that performs several computations, some of which
may be amenable to more aggressive optimizations:
> 
>  for (i) {
>    v = 1.0/(1.0 + A[i]*A[i]);
>    B[i] = (1.0 - B[i])*v
>  }
> 
> Suppose that we have a hardware that can perform very fast FMA operations
(possibly vectorized).  We could transform the loop into
> 
>  for (i) {
>    t = 1.0 + A[i]*A[i];
>    v = 1.0/t;
>    B[i] = (1.0 - B[i])*v;
>  }
> 
> And then expand t into an array, and distribute the loop:
> 
>  for (i) {
>    t[i] = 1.0 + A[i]*A[i];
>  }
>  for (i) {
>    v = 1.0/t[i];
>    B[i] = (1.0 - B[i])*v;
>  }
> 
> The first loop may then be unrolled and vectorized, while the second one
may simply be left alone.
> 
> This may be difficult to address in a target-independent way (via a generic
TTI interface), since we are trying to identify a specific pattern that, for the
specific hardware, may be worth extracting out of a more complex loop.  In
addition to that, for this example to make sense, the vectorization passes would
have to run afterwards, which would then put a bound on how late this
transformation could be done.
> 
> I guess the approach of being able to extend/modify what the PMB creates,
that you mention below, would address this problem.
> 
> 
>> 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.
> 
> Yes, I agree.  My major concern is that we need to be careful that we
don't accidentally make things harder for ourselves.  I very much agree with
the canonicalization approach, and loop nests can take a bit of preparation
(even including loop distribution).  At the same time, there are other
optimizations that will destroy the canonical structures (of loops, loop nests,
etc.), that also need to take place at some point. There should be a place in
the optimization sequence, where the "destructive" optimizations have
not yet taken place, and where the "constructive" (canonical) passes
can be executed.  The farther down the optimization stream we push the
"destructive" ones, the more flexibility we will have as to what types
of transformations can be done that require the code to be in a canonical form.
Thanks Krysztof. I appreciate your input and examples. It’s difficult to balance
things like Unswitching and LICM that clearly need to run early to expose scalar
opts, but in some sense are destructive. I agree with Shuxin’s analysis that
these transformations can be reversed if the effort is made. Those developing
experimental LNO tools can use any of the mechanisms described below to work
around it.
>> 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.
> 
> All of these approaches would work (even concurrently).  I think (3) could
potentially be the future goal.
> 
> 
>> 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.
> 
> Actually, in this case my concern was the interleaving of the
target-dependent code with target-independent code (if we were to do all idiom
recognition in the same pass), or code duplication (if the target-independent
and target-dependent passes were to be separate). The more I think about it, the
more I favor the "separate" approach, since the target-specific idioms
may be very different for different targets, and there doesn't seem to be
much that can be handled in a common code (hence not a lot of actual duplication
would happen).

I think we may want to run some generic loop idiom recognition early
(MemCpy/MemSet) because it may aid subsequent analysis. Shuxin described this as
a kind of “IR promotion” which is a good way to look at it.

However, targets do want to plugin custom idioms and I think those can run
later, separately.

To deal with pass ordering problems introduced by target-specific opts, targets
should be able to rerun generic passes if it’s worth the compile time. There are
a couple things we should improve to make this more practical:

- The generic, canonicalization passes should be able to run in a mode that
limits transformations to those that are locally profitable. We don’t want to
canonicalize late and defeat earlier optimizations.
- We should expose more generic optimizations as utilities that can run
on-demand for a given block or loop (GVN, LICM).

-Andy