[LLVMdev] GraphTraits and non-pointer graph nodes

[Daniel Berlin]

Our graph traits (but not the iterators) seem dependent on having
graphs made up of node that are pointers.

It requires the child iterators return pointers, etc.

(things like depth_first_iterator do not in fact care.  It just
defaults to smallptrset instead of smallset, and so is written for
pointers. )
This has two issues:

1. I have a trivially copiable pair that i want to treat as a graph
(actual use case is sane :P).  I don't want to have to allocate them.

This is std::pair<MemoryAccess *, AliasAnalysis::Location>.

TL; DR
As one walks up the def-use graph for memoryssa, and hits a phi node,
the pointer in the location needs to be translated through any phi
nodes that are in the block, for each predecessor it is going to
follow.

It's not enough to just hack around it - during any walk, it is
possible to go through the same block/accesses multiple times with
different memory locations, so the visited sets of the graph iterators
need to be able to be pairs, since it's really "did i visit this
memory access with this location, not 'did i visit this memory
access'.

I want to be able to use the normal graph iterators, rather than write
my own walks (for obvious reasons)

2. This seems to be the reason that we ended up with API
inconsistencies like pred/succ iterator that never return references.

IE

given

for (auto B : A Function)
B is a BasicBlock &


for (auto S: Successors(a BB))
S is a BasicBlock *.

(if succ_begin/succ_end returned references, they would not work in
the graphtraits API)


But i'd like to allow graphs that are made up of non-pointers.

This should in actually not be a huge change, i hope :)

But before i attempt it, wanted to know if anyone had any thoughts,
objections, etc.