A new gimple pass (LRS: live range shrinking) to reduce register pressure

Steven Bosscher stevenb.gcc@gmail.com
Thu Jan 1 17:02:00 GMT 2009

Xinliang David Li wrote:
> * An iterative data flow analysis (live use references). The result
> of the analysis is used to estimate the register pressure as well
> as the impact (cost/benefit) of code motions on the register pressure.
> The data flow result can be easily updated under various transformations.
> * An upward code motion pass to shrink live ranges
> * A downward code motion pass to perform subtree scheduling (to reduce
> overlapping live ranges). Multiple use trees are also scheduled downward
> if profitable
> * A forward data flow analysis to compute reaching virtual defs -- the
> result of this analysis is used for legality check for downward motion
> of statements with virtual uses
> * An expression tree reassociation pass to enable more opportunities
> for overlapping live range reduction (this is complementary to the
> existing reassociation pass, but with a different objective).

Are all these analyses/transformations interdependent?

Is there a reason for not just adding the reassociation
transformations to tree-ssa-reassoc.c?

> +sbitmap_a_and_not_b (sbitmap dst, const_sbitmap a, const_sbitmap b)

See sbitmap_difference().

> @@ -1095,4 +1155,3 @@ sbitmap_popcount (const_sbitmap a, unsig
>      }
>    return count;
>  }
> -

Redundant white space change.

> +	  "reg-pressure-min-bb",
> +          "The parmater to control the behavior of the lrs shrinking"
> +          "phase",
> +          80, 1, 10000)

The description is not very useful (for all 3 params). You should also
add documentation for the new params in doc/invoke.texi.

> Index: passes.c
> ===================================================================
> --- passes.c	(revision 142954)
> +++ passes.c	(working copy)
> @@ -674,6 +674,7 @@ init_optimization_passes (void)
>        NEXT_PASS (pass_cse_reciprocals);
>        NEXT_PASS (pass_convert_to_rsqrt);
>        NEXT_PASS (pass_reassoc);
> +      NEXT_PASS (pass_lrs);
>        NEXT_PASS (pass_vrp);
>        NEXT_PASS (pass_dominator);
>        /* The only const/copy propagation opportunities left after

If you run the pass here, you still have tracer and forwprop (and some
more) running after live range shrinking.  With profile-guided
optimization, tracer restructures the CFG completely, so this would
change the live ranges completely too. Therefore I'd run this pass
after tracer. And forwprop propagates SSA names, maybe extending live
ranges, so you probably want to run it after the last fwprop too.

In fact, I would expect you want to run this as the last pass, maybe
even after uncprop.

> +/* The function returns the unique id of the gimple STMT.  */
> +
> +static inline int
> +get_stmt_idx_in_region (gimple stmt)
> +{
> +  return gimple_uid (stmt);
> +}

Don't know what else to say then wtf.

> +is_gimple_assign_rhs_reassociable (enum tree_code rhs_code,

ISTR we have similar checks in tree-ssa-reassoc.c.  Maybe move the
function there and export it (unless you can move all the reassoc code
to that file, of course - that'd be the preferred solution ;-)

I don't see the relation between all the functions in the new
tree-ssa-lrs.c file.  You probably want to group functions and add
some overviews for the different phases/passes that you implement.
Bonus if you can split things per-pass into separate files...

How does this new pass (do these new passes?) impact compile time performance?


More information about the Gcc-patches mailing list