PATCH: Lengauer/Tarjan version of dominator computing

Michael Matz
Fri Oct 6 07:34:00 GMT 2000


On Thu, 5 Oct 2000, Richard Henderson wrote:

> On Thu, Oct 05, 2000 at 04:46:20PM +0200, Michael Matz wrote:
> > /* Type of Basic Block aka. TBB */
> > #define TBB unsigned int
> I'd prefer to use a proper typedef instead of the preprocessor.
> That way the debugger knows about the thing.

Ok, I myself don't remember anymore, why I used a #define ;-)

> > struct dom_info
> > {
> >   /* The parent of a node in the DFS tree.  */
> >   TBB *dfs_parent;
> I see a large number of arrays indexed by basic block number.
> Are you aware of the `aux' field on the basic block structure?

Yep. I didn't want to use it, because of the following reasons:
 * the algorithm does not work with basic block numbers, but with dfs
   number. If I would use the aux field, this would need an additional
   indirection on many places. (The thing does not deal with basic blocks
   _at all_, only with abstract nodes).
 * Most of these arrays, are indexed by TBB, and also contain TBB's. If I
   would use aux, constructs like key[path_min[set_chain[v]]] would be
   considerably more complex and slower.
 * The algorithm often only uses a part of the array (e.g. set_size and
   set_child are not used very often). If they would be interspersed with
   the other fields it would only dirty the cache for no good.

> Not a requirement, but I personally prefer to associate data
> with a block by actually attaching it to the block instead of
> indexing into an external array.

We have different views on the structure. I my pov a block does _not_ know
about its neighbors or any structure, besides it's own stuff (e.g. number
of instruction, whatever). The collection of all blocks, and its structure
is an entity on its own. Basically I shouldn't have to look _into_ a box,
if I want to carry it from one room to another (if I'm strong enough ;)  
Because e.g. the semidominator depends on the outer environment of a
block, this info should not be in the block.

There is also a difference between working phase and use phase, so
arguably this can be relaxed, if something is a final read-only result
(like the immediate dominator) to be used outside of the result-finding
itself: when it's clear, that the box is not going to be moved anymore,
then I could write the final room number on it, to ease access to it.

> The reorder_block_def struct in bb-reorder.c is an example of this.

Yes, and I'm not too sure about it, as it is working information. And at
least scope, next and index are more about structural things, than about
the BB itself (besides that for each BB there is that information, which
is not the right reason to put it into the BB).

> Not indexing into an array would also let you not remap the
> block numbers for entry and exit from ENTRY_BLOCK/EXIT_BLOCK,
> which would be fractionally clearer.

Hmm, yes, but I would have to map between dfs number and BB-index each
time. Better do the other thing, but only one time ;-)


More information about the Gcc-patches mailing list