<div dir="ltr">Hi all,<div><br></div><div>I have created a patch (up for review at: <a href="http://reviews.llvm.org/D17386">http://reviews.llvm.org/D17386</a>) that does Loop Fusion implementation.</div><div><br></div><div>Approach:</div><div>Legality: Currently it can fuse two adjacent loops whose iteration spaces are same and are at same depth. <br></div><div><br></div><div>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.</div><div>Currently, LoopAccessAnalysis is used to check dependence legality.</div><div><br></div><div>A basic diagram below tries to explain the approach taken to test dependence legality on two adjacent loops (L1 and L2).</div><div><br></div><div><div>    L1PH        (PH: Preheader)</div><div>    |               </div><div>    L1              </div><div>    |               </div><div>    CB (L1Exit/L2PH: ConnectingBlock (CB) )</div><div>    |               </div><div>    L2              </div><div>    |               </div><div>    L2Exit</div></div><div><br></div><div>is versioned as:</div><div><br></div><div><div>    BooleanBB      </div><div>          /\          </div><div> L1PH  L1PH.clone</div><div>         |     |         </div><div>      L1    L1.clone  </div><div>         |     |         </div><div>      CB    CB.clone  </div><div>         |     |         </div><div>      L2    L2.clone  </div><div>          \  /          </div><div>       L2Exit</div></div><div><br></div><div>And fused as:</div><div><div><br></div><div>  BooleanBB      </div><div>          /\</div><div> L1PH  FusedPH</div><div>         |  |</div><div>      L1  L1Blocks</div><div>         |  |              \</div><div>     CB  L2Blocks |</div><div>         |  |             |/</div><div>      L2  |</div><div>         \ /</div><div>   CommonExit</div></div><div><br></div><div>Profitability: Yet to be added.</div><div><br></div><div>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.</div><div><br></div><div>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.</div><div><br></div><div>Please share your feedback about the design and implementation.</div><div><br></div><div>Thank you</div><div>-- <br></div><div><div class="gmail_signature"><div dir="ltr"><div><div dir="ltr"><div><br></div><div>Good time...</div><div>Vikram TV</div><div>CompilerTree Technologies</div><div>Mysore, Karnataka, INDIA</div></div></div></div></div>
</div></div>