Page MenuHomePhabricator

Loop Fusion Pass
Needs ReviewPublic

Authored by tvvikram on Feb 18 2016, 9:16 AM.

Details

Summary

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.

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.

Thank you

Vikram TV
CompilerTree Technologies

Diff Detail

Event Timeline

tvvikram updated this revision to Diff 48340.Feb 18 2016, 9:16 AM
tvvikram retitled this revision from to Loop Fusion Pass.
tvvikram updated this object.
thanm added a subscriber: thanm.Feb 19 2016, 6:09 PM

Vikram,

I remember you mentioning this patch on llvm-dev a while ago, and I believe Adam had given you some preliminary feedback. I'm wondering what your status on this is. Thanks!

Vikram,

I remember you mentioning this patch on llvm-dev a while ago, and I believe Adam had given you some preliminary feedback. I'm wondering what your status on this is. Thanks!

This patch is not in the immediate task list as compiler efficiency is not too important for us at this point. But I am willing to work on this patch sometime next month.

(Sorry for replying very late! Somehow gmail filtered this thread to spam! And I noticed it just now).

suyog added a subscriber: suyog.Jun 13 2016, 2:08 AM

This patch is not in the immediate task list as compiler efficiency is not too important for us at this point. But I am willing to work on this patch sometime next month.

Thanks for the update. I'd be happy to help out with anything, so please let me know if I can assist.

hxy9243 added a subscriber: hxy9243.Aug 8 2016, 2:13 PM

Vikram, are you still interested in working on this?

pacxx added a subscriber: pacxx.Mar 14 2017, 3:13 AM
pacxx removed a subscriber: pacxx.Mar 14 2017, 5:38 AM
pacxx added a subscriber: pacxx.

Sorry for necroposting - what is the status of the patch? @tvvikram