Re: Strahler numbers

"BGB / cr88192" <cr88192@hotmail.com> writes:




> these strategies I would think would seem to have limited applicability,
> namely, they would only generally directly apply in situations where:
> the compiler is dealing with full expressions in lower levels of the
> compiler (like, the thing has not switched to RPN or TAC or similar before
> this point);


RPN is no problem -- the Horton-Strahler number is the minimal number
of stack elements needed to compute an RPN expression if you are
allowed to swap the children of a node (let the child with the highest
Horton-Strahler number be the first operand). And the stack code can
easily be transformed into register code. It is also easy to extend
to ternary or higher arity operations. The main limitation is that
you need an expression tree -- the algorithm doesn't work on DAGs, nor
in the presence of side effects.


> the specific types or operations may cost additional registers (say, a
> certain operation on a certain type is not directly applicable to a given
> CPU, and simulating this operation requires several additional temporary
> registers).


True, but this adds only a constant number of extra registers.


> another limitation could be on architectures where the number of registers
> is particularly limited, and most non-trivial operations will not fit in the
> CPU registers anyways.


It is easy enough to add a "spill" mechanism: The Horton-Strahler number
is the minimum number of temporary storage locations needed to compute
the tree. It doesn't matter if these are registers, stack entries or
memory locations.


> although, many of these issues likely could be addressed, I am not certain
> if this has much direct applicability to many/most compiler designs (where
> the AST is long dead by the time one gets to the codegen).


One way to use the technique is to re-arrange expression trees before
code generation. You do not need at this point to assign actual
registers, just re-arrange the tree so it needs a minimal number of
locations. Later (after value numbering, code generation and so on),
you can use graph colouring (or whatever you prefer) to do the actual
register allocation including precoloured nodes, spill and so on. You
are not guaranteed optimal allocation, but re-arranging the expression
trees will reduce register pressure.


Torben

Return to the comp.compilers page.
Search the comp.compilers archives again.