Patch to improve register elimination

Jeffrey A Law
Sun Feb 28 18:15:00 GMT 1999

  In message < 199902040523.AAA05726@jwlab.FEITH.COM >you write:
  > This patch improves register elimination by realizing that it doesn't
  > matter when the offset for a register can't be determined at the beginning
  > of the last basic block if the register isn't mentioned in the block and
  > there are no jumps to previous blocks.
  > ChangeLog:
  > Wed Feb  3 13:06:06 EST 1999  John Wehle  (
  > 	* reload1.c (set_label_offsets): Don't disable the elimination
  > 	when the offsets don't agree at a CODE_LABEL if it's the last
  > 	basic block, the register isn't mentioned, and there are no jumps
  > 	to previous blocks.
Consider if the last block does not initially have a reference to the frame
pointer.  So we initially don't care about the differing offsets involing
the frame pointer.

But later we end up eliminating some other eliminable register (arg pointer
for example) to be a frame pointer reference. 

Will your code handle that correctly?


This could be made more effective using dataflow analysis to propagate this
info around the cfg.

ie, if at any given code label no paths starting with that code label can
lead to a use of of the eliminable register, then the given code label does
not matter for register elimination purposes.

That's a pretty easy backwards dataflow problem to solve.

First we compute every block which uses the register requiring elimination.

Then we compute the global in/out properties

xout[block] = intersect of xin for each of block's successors
xin[block] = xout[block] - used_elim_register[block]
xout[EXIT] would be all ones

ie, if all the paths leading out of a block do not care about elimination
ofsets, then we do not care about elimination offsets at the end of the given

if we do not care about the elimination offsets at the end of the block, and
nowhere in the block do we use the eliminable register, then also do not care
about elimination offsets at the start of the given block.

Computing the local property (what eliminable registers are used by each block)
is straightforward.  The propagation code would look something like this:

  while (changed)
      changed = 0;
      /* We scan the blocks in the reverse order to speed up
         the convergence.  */
      for (bb = n_basic_blocks - 1; bb >= 0; bb--)
          if (bb != n_basic_blocks - 1)
            sbitmap_intersect_of_successors (xout[bb], xin, bb, s_succs);
          changed |= sbitmap_difference (xin[bb], xout[bb], local[bb]);

Interested in trying to do a more global version of this algorithm?

My only concern is chains of eliminations.  Consider if the last block
initially does not use the frame pointer, then due to elimination of some
other eliminable register (like the arg pointer, or return address pointer)
we end up with a frame pointer reference. 


More information about the Gcc-patches mailing list