[LLVMdev] DSGraph implementation status update

[Chris Lattner]

Hi all DSGraph users...

This is a note to let you know that I just checked in a rather large
change to the data structure graph representation.  Here are the bonuses
of the new representation:

1. Only the DSNode interface changed, mostly in implementation details, so
   hopefully client code shouldn't be effected.  As a metric, nothing had
   to change in BottomUp or TopDownClosure.cpp for the new representation.
   The biggest change is that the getLink(...) methods now return a
   reference to a DSNodeHandle instead of a pointer.
2. The new representation is much smaller and less computationally
   intensive to update, meaning that the datastructure analysis itself
   should be much faster.
3. The new representation is *much* simpler to *understand*.  The
   immediate effect of this is that the construction and maintenance
   algorithms are much less likely to be buggy.
4. The *code* to implement the new representation is shorter and easier to
   understand.
5. Speaking of bugs, all known bugs in the old representation are now
   dead.  All of the Olden suite and at least 181.mcf are successfully
   datastructuranalysisifiable.  Others probably work as well.
6. The graphs, as printed by dot, are a heckofalot easier to read and
   interpret.
7. Now that the representation is finalized, I can finish writing the
   representation section of the paper, which means that it should be
   available sooner rather than later.

Here is the drawback:

1. The representation is less powerful.  There are cases, at least in
   theory, that the old representation would have handled better (assuming
   that all of the bugs would have been fixed).

In practice, I haven't seen any of the cases actually happen where the
other algorithm would work better, so I think the trade-offs are worth it.

For the details of the new DSNode representation, I'll refer you to the
source for now, it has lots of comments:

http://llvm.cs.uiuc.edu/doxygen/DSNode_8h-source.html
http://llvm.cs.uiuc.edu/doxygen/classDSNode.html

... eventually the paper will be the reference.

So now that the DSNode representation is basically frozen (haven't I said
this before?), there is still stuff to do:

1. A new "Globals" graph will be added, which will optimize some
   situations due to programs that use lots of global variables, or call
   lots of external functions.  This shouldn't fundementally change the
   interface at all.
2. The heuristics can be improved slightly, improving the quality of the
   generated graphs.  Basically, right now if something happens that
   cannot be represented in the graph, the node in question is collapsed,
   losing all field sensitivity.  Because some "features" are not
   implemented yet, this happens in a couple cases where it shouldn't.  In
   particular, the following programs graphs will improve:

 Olden-tsp, Olden-vornoni - Struct padding is causing problems
 181.mcf - The lack of a "realloc" function is causing problems
 Olden-health - Level raise is not doing it's job on this benchmark,
                fouling up ds analysis.  I have a hack to fix this.

So, baring those benchmarks, everything seems to be in order.  Right now
dsanalysis prints out warning messages when various "collapsing"  cases
happen, but they can be ignored (the safe, but conservative, thing is
happening).  At some point in the future, I'll DEBUG() them. If you have
any problems with the new code, if it dumps core or asserts out, PLEASE
let me know.

-Chris

-- 
http://llvm.cs.uiuc.edu/
http://www.nondot.org/~sabre/Projects/