This is the mail archive of the
gcc@gcc.gnu.org
mailing list for the GCC project.
Cost and Benefit Allocation for moving the expression above the conditional.
- From: Ajit Kumar Agarwal <ajit dot kumar dot agarwal at xilinx dot com>
- To: Jeff Law <law at redhat dot com>, "vmakarov at redhat dot com" <vmakarov at redhat dot com>, Richard Biener <richard dot guenther at gmail dot com>, "gcc at gcc dot gnu dot org" <gcc at gcc dot gnu dot org>
- Cc: Vinod Kathail <vinodk at xilinx dot com>, Shail Aditya Gupta <shailadi at xilinx dot com>, Vidhumouli Hunsigida <vidhum at xilinx dot com>, "Nagaraju Mekala" <nmekala at xilinx dot com>
- Date: Sun, 6 Sep 2015 12:46:25 +0000
- Subject: Cost and Benefit Allocation for moving the expression above the conditional.
- Authentication-results: sourceware.org; auth=none
- Authentication-results: spf=pass (sender IP is 149.199.60.100) smtp.mailfrom=xilinx.com; gmail.com; dkim=none (message not signed) header.d=none;gmail.com; dmarc=bestguesspass action=none header.from=xilinx.com;
- Spamdiagnosticmetadata: NSPM
- Spamdiagnosticoutput: 1:23
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.
Thanks & Regards
Ajit