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

On 7/31/2013 12:20 PM, Chris Lattner wrote:
> On Jul 31, 2013, at 6:53 AM, Krzysztof Parzyszek
> <kparzysz at codeaurora.org <mailto:kparzysz at
codeaurora.org>> wrote:
>> 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.
>
> Canonicalization of the IR is not about guarantees, it is about what
> assumptions passes can make and what form they have to tolerate.
Then the transformations that need to assume that invariants were 
hoisted could be run after LICM.  Since loops are defined in terms of 
regions (back-edges), what makes sense is a canonical form that 
normalizes the structure into a common form.  Whether the invariants are 
hoisted or not doesn't need to be a part of that.

>>> Optimizations should not depend on perfect loops.
>>
>> What do you mean by "perfect loops"?  I was talking about
perfect nests.
>
> I'm talking about perfect loop nests, as in the classical fortran loop
> transformation sense.
Most nest optimizations only apply to perfect nests.  Each such 
optimization could try to "fix" the nest for its own purposes, but it 
would be a lot of duplicated effort.

Whatever c-n does, it should not be getting in the way.

-K

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

>> I'm talking about perfect loop nests, as in the classical fortran
loop
>> transformation sense.
>
> Most nest optimizations only apply to perfect nests.  Each such 
> optimization could try to "fix" the nest for its own purposes,
but it
> would be a lot of duplicated effort.
If each L.N.O pass have to fix by itself, I would say this LNO component 
is pretty lame.
IMHO, It is natural to run a preparation pass to shape the loop nests 
into a shape such that following
LNO optimizers feel comfortable to kick in.  Such preparation/fix pass 
should include getting rid
of imperfect part, fusion, fission on individual nests or the 
neighboring nests, at appropriate nest level.

In theory, you are always possible to get rid of imperfect part by 
tugging them into the loop with
a condition like "if "iv == 1st iteration", or if possible you
can
distribute the imperfect part.
I don't think the imperfect part created by LICM need such expensive 
transformation; you just
place them back to appropriate loop.  In this sense, LICM should be 
become the culprit for disabling
some optimizers.

You might argue  running LICM early will miss the opportunities created 
by permutation. True.
But, now that permutation has detailed dep-test result, it clearly 
understand which mem-access
is invariant w.r.t which nest loop, why not move them to right place. It 
is trivial for such optimizers,
but it seems to be quite hard for following scalar optimizer, unless it 
can afford running expensive
dependence test again.

IMHO, I don't see strong disadvantage run LICM either before or after LNO.

On 7/31/2013 1:02 PM, Shuxin Yang wrote:
>
> You might argue  running LICM early will miss the opportunities created
> by permutation. True.
> But, now that permutation has detailed dep-test result, it clearly
> understand which mem-access
> is invariant w.r.t which nest loop, why not move them to right place.
Because the next nest optimization would have to deal with it again.  As 
long as we are working on high-level structures, like loop nests, the 
details (such as invariance of some expression) should not concern us. 
That would be a job for a subsequent, lower-level pass (e.g. working on 
a single loop at a time).

-K

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