[llvm-dev] Making loop guards part of canonical loop structure
David Greene via llvm-dev
llvm-dev at lists.llvm.org
Wed May 29 07:04:10 PDT 2019
This seems like potentially a good thing. There have been cases where
I've wanted to know the guard associated with the loop.
Loop versioning can create many guards, including guards nested within
other guards. I don't know how/if we want to capture that level of
complexity, but it was the first question that popped into my mind.
Kit Barton via llvm-dev <llvm-dev at lists.llvm.org> writes:
> Hi all,
> TL;DR: Should the loop guard branch be part of the canonical loop structure?
> While working on the next set of improvements to loop fusion, we discovered that
> loop rotation will put a guard around a loop if it cannot prove the loop will
> execute at least once, as seen in the following (simplified) example:
> br i1 %cmp1, label %for.body.lr.ph, label %for.cond.cleanup
> for.body.lr.ph: ; preds = %entry
> br label %for.body
> for.body: ; preds = %for.body.lr.ph, %for.inc
> br label %for.inc
> for.inc: ; preds = %for.body
> br i1 %cmp, label %for.body, label %for.cond.for.cond.cleanup_crit_edge
> for.cond.for.cond.cleanup_crit_edge: ; preds = %for.inc
> br label %for.cond.cleanup
> for.cond.cleanup: ; preds = %for.cond.for.cond.cleanup_crit_edge, %entry
> br label %for.end
> for.end: ; preds = %for.cond.cleanup
> ret void
> However, for loops that can be proven to execute at least once, there is no
> This creates complications for several loop optimizations because they need to
> handle both guarded loops and non-guarded loops. For example, the current loop
> fusion pass needs to check whether two loops are control flow equivalent before
> fusing them (i.e., if the first loop executes, the second loop is guaranteed to
> execute). This is currently done by checking that the preheader of the first
> loop dominates the preheader of the second loop, and the preheader of the second
> loop post-dominates the preheader of the first loop. When one (or both) of the
> loops have a guard, then this check no longer works. If the loop guard was part
> of the canonical form, then this check could be done using the loop guard,
> instead of the preheader.
> Similarly, when checking for perfect loop nests, a loop guard around the inner
> loop will make the nest appear imperfect. However, if the guard is considered to
> be part of the inner loop, it is easier to prove a perfect nest.
> Both of these examples have alternative ways to deal with the loop guards, if
> they are present. However, I would like to have the discussion regarding making
> guards part of the canonical loop structure. If people are supportive of this,
> we can start doing the work to implement the guards and start modify loop
> optimizations to deal with them appropriately. However, if this is not the
> direction we want to go, we can deal with the guards in the specific
> optimizations where they are relevant.
> Proposed Solution:
> Ensure that all loops in canonical form have a guard branch that dominates the
> preheader. If such a guard branch does not exist, a trivial guard will be
> I have not looked at the implementation of this
> extensively yet because I wanted feedback on this direction first. However, my
> initial thought is to modify LoopSimplify to add the concept of a loop guard,
> and provide similar guarantees that it currently provides for preheaders and exit
> blocks. Specifically, if a guard block is not found, one is created and inserted
> immediately before the loop preheader to guarantee a structure similar to the
> one in the example above. Note that as with the preheader and exit blocks, it is
> possible that subsequent passes (e.g., SimplifyCFG) may remove these blocks thus
> taking it out of canonical form. However, this is an existing situation that
> loop optimizations already deal with.
> Any comments/feedback are greatly appreciated.
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
More information about the llvm-dev