[LLVMdev] Detecting reduction operations

[Chris Lattner]

On Oct 12, 2009, at 5:17 PM, Scott Ricketts wrote:

>> 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:

Okay, so the short answer is that we don't have what you need out of  
the box.

The longer answer is that there are two completely different types of  
loop dependences: memory dependences (load/store dependencies) and SSA  
value dependences like you're talking about here.

If you want to detect simple reductions like this, just walk the SSA  
graph starting from the PHIs in the loop header.  The code should look  
very similar to how LoopInfo identifies the canonical induction  
variable for a loop, it should not be difficult to write.

-Chris

>
> 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
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev