[LLVMdev] dominance frontiers

[Preston Briggs]

On Fri, Jan 6, 2012 at 5:08 PM, Chris Lattner <clattner at apple.com> wrote:
> [many interesting things, together with contributions from Daniel Berlin and Cameron Zwarich]

Thanks.

>> We're aiming to do a number of loop xforms, including parallelization,
>> loop fusion, distribution, rewriting of reductions and recurrences,
>> etc.  The usual approach is to build a dependence graph connecting all
>> the memory references in a routine, then examine the graph looking for
>> connected components and such.  Building the graph incrementally, on
>> demand, seems wasteful since we'll want the entire graph. Similarly,
>> since we're going to build the entire dependence graph, building a
>> complete set of FUD chains is also useful since we'll use the entire
>> thing.
>
> I don't have extensive experience with those loop transformations,
> so my perspective is limited.  However, each of them seem to want
> to know very different kind of relations - e.g.  some want cross loop
> iteration dependencies, some want within iteration dependences,
> some care about forward and others care about anti-dependences, etc.
> You'd really want to compute all of this?

Today, yes.  Later, when I understand more, perhaps I'll be able to
get by with less.

> Further, many loop transformations have to immediately give up:
> for example, it might not be possible to vectorize a loop that contains
> a call to an unknown function, or a loop that does pointer chasing.
> Why burn compile time speculatively computing a bunch of information for these loops?

Because xforms of larger scope may be able to take advantage.
Drawing on your examples, a loop containing a call can sometimes be distributed
into several loops, some of which can be vectorized.  A loop that does pointer
chasing might be contained in another loop that can be parallelized.

I don't imagine such things will be useful to everybody,
but they're useful to us and we're happy to use an extra flag and pay
the extra compile time.
After all, it's so much better than having to restructure the code by hand.

Preston