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

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

On 7/31/13 4:30 PM, Tobias Grosser wrote:
> 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
I'm pretty sure Open64's LNO is able to revert LICM-ed loop back to what
to was.

>
> 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
>
>
>

On 7/31/13 4:47 PM, Shuxin Yang wrote:
>
> On 7/31/13 4:30 PM, Tobias Grosser wrote:
>> 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
>
> I'm pretty sure Open64's LNO is able to revert LICM-ed loop back to
> what to was.
Recall little bit more, it must be done in forwarding pass.
>
>
>>
>> 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
>>
>>
>>
>

On 7/31/2013 6:30 PM, Tobias Grosser wrote:
>
> 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.
The way I was thinking about it is that LICM could be optionally added 
to the preparation steps, something like requiring loop-closed SSA form 
for certain transformations.

-K

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

Now I see a strong value for running LICM earlier -- to brutally expose 
LNO's stupidity:-)

On 7/31/13 6:39 PM, Krzysztof Parzyszek wrote:
> On 7/31/2013 6:30 PM, Tobias Grosser wrote:
>>
>> 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.
>
> The way I was thinking about it is that LICM could be optionally added 
> to the preparation steps, something like requiring loop-closed SSA 
> form for certain transformations.
>
> -K
>