[LLVMdev] IR Passes and TargetTransformInfo: Straw Man

[Shuxin Yang]

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