[LLVMdev] Detecting reduction operations

[Scott Ricketts]

> Hi Scott,
>
> Do you mean loop carried dependencies?  There is some initial work on
> dependence analysis, but it is still pretty young.  We also have support for
> dependence between memory operations that are not loop aware.
>
> -Chris

I think the dependence analysis will have to be loop aware. For example:

bb:
        %indvar = phi i64 [ 0, %bb.nph ], [ %indvar.next, %bb ]
        %sum = phi i32 [ 0, %bb.nph ], [ %3, %bb ]
        %1 = getelementptr i32* %X, i64 %indvar
        %2 = load i32* %1, align 4
        %3 = add i32 %2, %sum
        %indvar.next = add i64 %indvar, 1
        %exitcond = icmp eq i64 %indvar.next, %tmp.
        br i1 %exitcond, label %bb2, label %bb

I would like to recognize that there is circular dependence (true and
anti-) between %3 and %sum and that the only operations that form this
dependence are associative+commutative (e.g. addition). In this
example, we can see that by just looking at the operands of the %sum
and %3 instructions. But things get more challenging when we toss in,
say, a constant scalar multiply into each iteration. Then the
dependencies have an intermediate operations between them:

bb:
        %indvar = phi i64 [ 0, %bb.nph ], [ %indvar.next, %bb ]
        %sum = phi i32 [ 0, %bb.nph ], [ %3, %bb ]
        %1 = getelementptr i32* %X, i64 %indvar
        %2 = load i32* %1, align 4
        %3 = mul i32 %2, 4
%3 = add i32 %2, %sum
        %indvar.next = add i64 %indvar, 1
        %exitcond = icmp eq i64 %indvar.next, %tmp.
        br i1 %exitcond, label %bb2, label %bb

1) %3 has a true dependency on %sum (this is trivial by just looking
at the operands of the add inst)
2) %sum has an anti