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

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 10:19 AM, Shuxin Yang <shuxin.llvm at gmail.com>
wrote:
>  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.
FWIW, I completely agree with this.  The canonical form should be that loop
invariants are hoisted.  Optimizations should not depend on perfect loops.  This
concept really only makes sense for Source/AST level transformations anyway,
which don't apply at the LLVM IR level.

-Chris

On 7/30/2013 11:44 PM, Chris Lattner wrote:
>
> The canonical form should be that loop invariants are hoisted.
The canonical form should not depend on the knowledge as to what is 
invariant and what isn't.  It has more to do with preserving certain 
"common" properties of a loop, such as header, preheader, latch
branch, etc.

> Optimizations should not depend on perfect loops.
What do you mean by "perfect loops"?  I was talking about perfect
nests.

-K

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

On 07/30/2013 09:44 PM, Chris Lattner wrote:
>
> On Jul 30, 2013, at 10:19 AM, Shuxin Yang <shuxin.llvm at gmail.com>
wrote:
>
>>   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.
>
> FWIW, I completely agree with this.  The canonical form should be that loop
invariants are hoisted.  Optimizations should not depend on perfect loops.  This
concept really only makes sense for Source/AST level transformations anyway,
which don't apply at the LLVM IR level.
Some comments from an LNO such as Polly. In general, Polly and probably 
many modern loop nest optimizers do not care that much about perfectly 
or imperfectly nested loop nests. Transformations work either way.

LICM is problematic due to another reason. LICM introduces new memory 
dependences. Here a simple example

Normal loop:

for i
    for j
      sum[i] += A[i][j]

LICM loop:

for i
    s = sum[i]
    for j
      s += A[i][j]
    sum[i] = s


Calculating precise dependences for the second loop yields a lot more 
dependences that prevent possible transformations. A LNO can always 
remove those LICM introduced dependences by expanding memory, but full 
memory expansion is impractical. Deriving the right amount of memory 
expansion (e.g. the one that just reverts the LICM) is a difficult 
problem. From a LNO perspective first deriving possible 
transformations, then transforming the loop and as a last step applying 
LICM seems to be the better option.

Having said that, if there are compelling reasons outside of LNO to keep 
the LICM in the canonicalization pass, I can see us following Andrews 
suggestion to disable LICM in case a LNO is run and having the LNO 
schedule an additional set of cleanup passes later on.

Cheers,
Tobias