Cost and Benefit Allocation for moving the expression above the conditional.

[Richard Biener]

On Sun, Sep 6, 2015 at 2:46 PM, Ajit Kumar Agarwal
<ajit.kumar.agarwal@xilinx.com> wrote:
> All:
>
> The cost and benefit associated for moving a given expression above conditional  are the important factors for the performance boost.
>
> Considering the above, the cost and benefit calculation can be derived based on below.
>
> For a given conditional entry point 'n', the benefit path 'p'  are the sub paths that passes through 'n' and available and anticipatable at the conditional
> Entry n.
>
> For a given conditional entry point 'n', the cost path 'p' are the sub paths that passes through 'n' and are unavailable and un-anticipatable at the
> Conditional entry n.
>
> Thus the Benefit =  summation of the frequency of all the benefit paths as given above.
> Cost = Summation of the frequency of all the cost paths as given above.
>
> Thus the movement of expression above the conditional can be enabled if the Benefit > Cost as calculated above.
>
> The derivation above can be extended to Loop Invariant code motion.
>
> The above benefit and the cost derivation can be extended to the following based on number of DEFs and use.
>
> Benefit = Summation of the frequency of all the benefit paths + summation of (number  of defs * latency of store instruction)  of all benefit paths
> +summation of ( number of uses * latency of load instruction ) of all benefit paths +  -  Summation of  ( Number of moves * latency of move instructions)
> Of all benefit paths.
>
> Cost =  Benefit = Summation of the frequency of all the cost paths + summation of (number  of defs * latency of store instruction)  of all cost paths
> +summation of ( number of uses * latency of load instruction ) of all cost paths    -  Summation of  ( Number of moves * latency of move instructions)
> Of all cost paths
>
> The movement of the expressions above the condition and can be extended  to LICM if the benefit is greater than cost.
>
> The above is feasible and quite efficient for the cost and Benefit allocation for control flow code motion. This  above cost  somewhat equivalent to
> Cost of the Live range priority and  selection of coloring the live ranges based on priority.

PRE kind-of considers this "locally" for each insert location, but the
data-flow driven solution doesn't know the "path" an
expression was coming from so I don't see how we could implement this
more "global" scheme.

Richard.

>
> Thanks & Regards
> Ajit