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/
