[LLVMdev] proof of concept for a loop fusion pass

[Hal Finkel]

----- Original Message -----
> From: "Adam Nemet" <anemet at apple.com>
> To: "Ramshankar Ramanarayanan" <Ramshankar.Ramanarayanan at amd.com>
> Cc: llvmdev at cs.uiuc.edu
> Sent: Saturday, January 17, 2015 12:20:55 AM
> Subject: Re: [LLVMdev] proof of concept for a loop fusion pass
> 
> 
> On Jan 15, 2015, at 4:22 PM, Ramanarayanan, Ramshankar <
> Ramshankar.Ramanarayanan at amd.com > wrote:
> 
> 
> Hi,
> 
> 
> We are proposing a loop fusion pass that tries to proactive fuse
> loops across function call boundaries and arbitrary control flow.
> 
> 
> http://reviews.llvm.org/D7008

This link contains the Clang patch. Did you intend to post the LLVM patch as well?

> 
> 
> With this pass, we get 103 loop fusions in SPECCPU INT 2006
> 462.libquantum with rate performance improving close to 2.5X in x86
> (results from AMD A10-6700).
> 
> 
> I took some liberties in patching up some of the code in
> ScalarEvolution/DependenceAnalysis/GlobalsModRef/Clang options/ and
> also adjusted the IPO/LTO pass managers. I would need to do a better
> job there but I would like to put this out as WIP for high level
> reviews. At this time standard loop fusion test cases may not work
> (cases where control dep are same or loops are truly adjacent etc).
> I would be doing that as well.
> 
> 
> Appreciate suggestions and other help.
> 
> 
> The pass initially attempts to inline calls which have loops in them.
> Following inlining, a separate scalar "main" pass tries to fuse
> loops. It is not necessary for loops to be adjacent or have the same
> control dependence. Specifically a control dependence closure is
> computed and loops that share a control dep closure prefix are taken
> as candidates for fusion, in case there are no other loops in a
> certain path between them. A loop graph is built with edges between
> loops which share the control dependence closure prefix. A recursive
> application of fusion follows on the graph from "bottom-up".
> 
> 
> During fusion, program slices are taken based on the control flow
> closures of the two loops being fused. Example: Suppose two loops A
> and B are going to be fused. They share the same control dependence
> prefix, but their suffices vary. The suffices are used to duplicate
> Control flow paths that pass through both loops. Specifically paths
> from the first block in the control-dep closure suffix of the first
> loop, through the first loop's exit and following into the suffix of
> the second loop through the second loop's exit on to the common
> post-dominator of either loop's exit. The number of paths grows
> exponentially. At this time some heuristics are used when exploring
> for paths. Using profile based heuristics is a better idea.

On this last point, would it be possible to encode your static heuristics as improvements to our static branch probability heuristics, and then naturally adapt to profile-based branch probabilities when those are available?

> 
> Hi Ramshankar,
> 
> 
> 
> 
> 
> This is interesting, indeed. Thanks for soliciting input.
> 
> 
> My main comment has to do with the fact that in order to get this
> gain you need many pieces to work together. My suggestion is to
> proceed in steps and develop it incrementally on trunk.

I second this. We definitely should have loop fusion in LLVM, and incremental in-trunk development is the best way to make that happen.

> 
> 
> For example it would be good to first add a simple loop fusion pass
> that only merges adjacent loops and then build it up from there. Can
> you break down your approach into smaller, incremental steps like
> this? What would these steps be?
> 
> 
> My other comment is about the choice of DependenceAnalysis framework.
> No pass currently uses this framework and I am not sure how complete
> the implementation is

DependenceAnalysis has known issues -- as I recall, the way it pulls apart GEP indices without verifying the boundary conditions is not really sound, but this could be replaced by our delinearization functionality now (what Polly is using) -- and if this work provides the impetus for cleaning that up, so much the better. That having been said, care is required. DependenceAnalysis is definitely more powerful than the vectorizer's dependence analysis, and conceptually cleaner. However, using what the vectorizer uses should provide a conservatively-correct base.

> and whether it has adequate test coverage.

DependenceAnalysis's test coverage actually isn't bad, at least for loop bodies in traditional form.

> This was my main reason for reusing the dependence analysis from the
> LoopVectorizer. Have you considered the same?

Finally, it might be a good idea to discuss the overall optimization plan for fuseable loops. One possibility that I had discussed with Chandler a couple of months ago was: aggressively fuse early, expose optimization opportunities, and then split late (after vectorization) based on target-specific modeling (accounting for register pressure, hardware prefetching resources, etc.). There are obviously also other possible approaches, and I'd like to know what you think would be an optimal strategy.

Thanks again,
Hal

> 
> 
> Adam
> 
> 
> 
> 
> 
> 
> 
> 
> 
> Also function unswitching helps by cleaning up control flow.
> 
> 
> Example:
> if (a & b) {
> if (a & c) {
> if (t & 0xF) {
> for (i=0; i < size; i++) {
> if (A[i] & d) {
> A[i] |= (1 << t);
> }
> }
> }
> }
> }
> 
> 
> if (b & d) {
> if (a & d) {
> if (t & 0xA) {
> for (i=0; i < size; i++) {
> if (A[i] & d) {
> A[i] |= (1 << t);
> }
> }
> }
> }
> }
> 
> 
> After fusion we will have:
> 
> 
> if (a&b && a&c && t&0xF && b&d && a&d t&0xA) {
> for (i=0; i < size; i++) {
> if (A[i] & d) {
> A[i] |= (1 << t);
> }
> if (A[i] & d) {
> A[i] |= (1 << t);
> }
> }
> } else {
> // original code
> if (a & b) {
> if (a & c) {
> if (t & 0xF) {
> for (i=0; i < size; i++) {
> if (A[i] & d) {
> A[i] |= (1 << t);
> }
> }
> }
> }
> }
> 
> 
> if (b & d) {
> if (a & d) {
> if (t & 0xA) {
> for (i=0; i < size; i++) {
> if (A[i] & d) {
> A[i] |= (1 << t);
> }
> }
> }
> }
> }
> }
> 
> 
> Thanks,
> Ramshankar _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
> 
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
> 

-- 
Hal Finkel
Assistant Computational Scientist
Leadership Computing Facility
Argonne National Laboratory