[LLVMdev] IR Passes and TargetTransformInfo: Straw Man

[Shuxin Yang]

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