[LLVMdev] How to gather data dependences

[Preston Briggs]

The dependence analyzer helps with array references in loops.
The example you show,

int nonLoopDep( int A, int B, int C ) {
    A = B + C;
    B = A / C;
    return B;
}


has no loops and no array refs, so dependence analysis won't help.
But that's ok, because these cases (scalar references) are particularly
simple and well understood by the rest of the compiler.

Unfortunately, there's more for you to learn and I don't really know
all the answers (in LLVM terms). LLVM converts everything to SSA form
(static single assignment), making it easy to chase from the use of a
variable
to its definitions.

If we put your example in a file called z.c
and compile it like this,

clang -O -S -emit-llvm z.c


we'll get a file z.s with the IL after optimization:

define i32 @nonLoopDep(i32 %A, i32 %B, i32 %C) #0 {
entry:
  %add = add nsw i32 %C, %B
  %div = sdiv i32 %add, %C
  ret i32 %div
}


Note that each name (%A, %B, %C, %add, and %div) has exactly
one definition but may have multiple uses (e.g., %C).
If you zip through the code and record the location of each definition,
then whenever you see a use, you can immediately see where it was defined.

Note that the procedure entrance serves as a definition point for the
parameters %A, %B, and %C.
Note also that your original variable B had 2 distinct definitions, and the
compiler has
recognized this and given one of them a new name, %div.

It's a little more complicated when multiple definitions can reach a single
use.
For example, if we compile this code

int dumb( int A, int B, int C ) {
  if (A == B)
    A = C + 5;
  else
    A = C / 5;
  return A + B;
}


we get

define i32 @dumb(i32 %A, i32 %B, i32 %C) #0 {
entry:
  %cmp = icmp eq i32 %A, %B
  br i1 %cmp, label %if.then, label %if.else

if.then:                                          ; preds = %entry
  %add = add nsw i32 %C, 5
  br label %if.end

if.else:                                          ; preds = %entry
  %div = sdiv i32 %C, 5
  br label %if.end

if.end:                                           ; preds = %if.else,
%if.then
  %A.addr.0 = phi i32 [ %add, %if.then ], [ %div, %if.else ]
  %add1 = add nsw i32 %A.addr.0, %B
  ret i32 %add1
}


Note that 2 different definitions of A reach the use of A after the if
statement.
In the LLVM IR, this situation is handled with a phi statement.
So what was originally A has become %A, %add, %div, and %A.addr.0
where the last is defined by a phi serving to join two of the names.

It's not actually very complicated to use; if you play with a few more
examples
(be sure to try some loops) and trace out all the use-def connections,
I think it'll become clear.

Preston







On Fri, Aug 23, 2013 at 11:53 AM, Valmico <valmico88 at gmail.com> wrote:

> Hello, thanks to your advices now my pass is on good way (i hope), but
> i've faced one problem that i cannot solve by myself:
> Running all these passes (-basicaa -mem2reg -simplifycfg -loop-simplify
> -loop-rotate -simplifycfg -instcombine -indvars -da) helped a lot, but now
> i'm unable to find dependencies that are outside of the loop. f.eg. code
> like this returns no dependencies (and no store/load instruction at all).
>
> int nonLoopDep( int A, int B, int C ) {
>     A = B + C;
>     B = A / C;
>     return B;
> }
>
> I've figured out that removing -mem2reg and -instcombine helps a little
> but it reports more dependencies than it should and also it messes up
> looking for dependencies inside loops completly.
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20130904/6e2fd538/attachment.html>