[llvm-dev] Implement Loop Fusion Pass

[Vikram TV via llvm-dev]

On Fri, Feb 19, 2016 at 10:46 PM, Vikram TV <vikram.tarikere at gmail.com>
wrote:

> Hi,
>
> Thanks for the reply. Few thoughts inlined.
>
> On Fri, Feb 19, 2016 at 8:00 AM, Adam Nemet <anemet at apple.com> wrote:
>
>> Hi Vikram,
>>
>> On Feb 18, 2016, at 9:21 AM, Vikram TV via llvm-dev <
>> llvm-dev at lists.llvm.org> wrote:
>>
>> Hi all,
>>
>> I have created a patch (up for review at: http://reviews.llvm.org/D17386)
>> that does Loop Fusion implementation.
>>
>> Approach:
>> Legality: Currently it can fuse two adjacent loops whose iteration spaces
>> are same and are at same depth.
>>
>> Dependence legality: Currently, dependence legality cannot be checked
>> across loops. Hence the loops are cloned along a versioned path,
>> unconditionally fused along that path and then the dependence legality is
>> checked on the fused loop keeping the instructions from original loops in
>> context. Fusion is illegal if there is a backward dependence between memory
>> accesses whose source was in first loop and sink was in second loop.
>> Currently, LoopAccessAnalysis is used to check dependence legality.
>>
>>
>> Thanks for writing up the design here.
>>
>> I think we have a pretty strong policy against creating temporary
>> instructions and here you actually create an entire loop just to check
>> legality.
>>
> I didn't understand the consequences here. A subsequent DCE pass or
> explicit removal in this case is taking care of the temporaries. Any
> pointers in this regard would be helpful.
>
>>
>> It would probably be a better design to add the capability of adding two
>> LAI objects together.  This would effectively simulate the fusion on the
>> analysis side so you could query the legality from that.
>>
> I am not sure how the underlying analysis like SCEV would behave in this
> case. As per my understanding, it queries for a particular loop while we
> have populated accesses from two different loops. But assuming that it
> works, we would lose the ability to try/test using DependenceAnalysis in
> future. Currently, it is very easy to replace LoopAccessAnalysis with
> DependenceAnalysis.
>
>>
>> Specifically, you could check if you have backward dependences between
>> instructions in L2 to instructions in L1 which would be illegal.
>>
>> As a side effect you’d also get the total set of memchecks which you
>> could filter to only include checks where the participating pointers come
>> from different loops.  (This is quite similar to LoopDistribution.)
>>
> I am happy to add a routine in a subsequent patch that filter the checks.
>
Just to clarify, I meant to filter the runtime checks which is currently
not done in the patch.

>
>> Also I don’t think it should be too hard to teach LVer to be able to
>> version two consecutive loops (or arbitrary CFG?).
>>
> I think yes. Instead of Loop Versioning deciding to version, code can be
> factored out so that it versions unconditionally "also" as requested by the
> pass that uses it.
>
>>
>> Let me know what you think,
>> Adam
>>
>>
>> A basic diagram below tries to explain the approach taken to test
>> dependence legality on two adjacent loops (L1 and L2).
>>
>>     L1PH        (PH: Preheader)
>>     |
>>     L1
>>     |
>>     CB (L1Exit/L2PH: ConnectingBlock (CB) )
>>     |
>>     L2
>>     |
>>     L2Exit
>>
>> is versioned as:
>>
>>     BooleanBB
>>           /\
>>  L1PH  L1PH.clone
>>          |     |
>>       L1    L1.clone
>>          |     |
>>       CB    CB.clone
>>          |     |
>>       L2    L2.clone
>>           \  /
>>        L2Exit
>>
>> And fused as:
>>
>>   BooleanBB
>>           /\
>>  L1PH  FusedPH
>>          |  |
>>       L1  L1Blocks
>>          |  |              \
>>      CB  L2Blocks |
>>          |  |             |/
>>       L2  |
>>          \ /
>>    CommonExit
>>
>> Profitability: Yet to be added.
>>
>> Further, based on legality and profitability success, the fused loop is
>> either retained or removed. If runtime checks are necessary, both original
>> and fused loops are retained; otherwise the original loops are removed.
>>
>> Currently, I have scheduled the fusion pass after distribution pass. Such
>> a schedule negates the effect of the other pass, but given that the
>> distribution (and fusion) pass is experimental and off by default, I felt
>> it was okay to schedule that way till a global profitability is implemented.
>>
>> Please share your feedback about the design and implementation.
>>
>> Thank you
>> --
>>
>> Good time...
>> Vikram TV
>> CompilerTree Technologies
>> Mysore, Karnataka, INDIA
>> _______________________________________________
>> LLVM Developers mailing list
>> llvm-dev at lists.llvm.org
>> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>>
>>
>>
>
>
> --
>
> Good time...
> Vikram TV
> CompilerTree Technologies
> Mysore, Karnataka, INDIA
>



-- 

Good time...
Vikram TV
CompilerTree Technologies
Mysore, Karnataka, INDIA
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20160222/c287ffc8/attachment.html>