[LLVMdev] How to gather data dependences

[Preston Briggs]

Valmico <valmico88 at gmail.com> wrote:
> I'm currently trying to develop new LLVM Pass that will generate
> simple data dependencies graph. For now I'm trying to get familiar
> with DependenceAnalysis.
> My general idea is to traverse each function (runOnFunction)
> top to bottom Instruction by Instruction, using DA.depends( I, I2, ...)
> on every Instructions combination in function to check if they are
> dependent on any others.
>
> Problem is that almost all (if not all) Instructions seems to be dependent
> on others even if they write/read to/from different memory cells.
> Also I'm getting Dependence (confused) object, not the FullDependence,
> should i try to dynamically cast it to FullDependence, or is there a way
> to determine which Dependence instance i got other way?
>
> Please help, I'm not an C++ nor LLVM programmer, but PHP-developer,
> however i need it done asap. If you can help just a little, give me a
hint,
> i'll be very, very thankful for ANY support.
>
> Best Regards
> Valmico

Hi,

The DependenceAnalysis pass isn't reliable yet; it has several errors that
need to be corrected. These manifest by the analysis claiming there's no
dependence when one in fact exists.

Your proposed scheme of testing every pair of instructions is
asymptotically expensive, requiring O(n^2) tests, where each test is
already fairly expensive. I describe (or start to describe) a better
approach here<https://sites.google.com/site/parallelizationforllvm/building-the-dependence-graph>
.

In the meantime, you should be getting better results than you report.
You'll want to use several other passes in conjunction with DA. Try
something like

opt -basicaa -mem2reg -simplifycfg -loop-simplify -loop-rotate -simplifycfg
-instcombine -indvars -da


Also, a confused dependences mean that the analysis wasn't able to prove
anything; a FullDependence means the analysis was able to prove some facts,
though it wasn't actually able to disprove the dependence. It's not
reasonable to cast a Dependence to a FullDependence.

Preston
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20130808/4d30fe92/attachment.html>