Is an instruction on the critical path? (was: auto predicating branches)

anton@mips.complang.tuwien.ac.at (Anton Ertl) writes:

So the hardware should take predictability of a condition and the
availability of the condition into consideration for if-conversion.

Another criterion would be whether one of the potentially
if-converted instructions is on the critical data-dependency path.  If
none of them are, additional latency (if any) from if-conversion may
be less of an issue.  OTOH, it may also mean that the code is
resource-limited rather than dependency-limited, and that one should
avoid if-conversion in order to avoid additional resource consumption
(and of course prediction accuracy also plays into these
considerations).

This made me think how one could determine whether an instruction is
on the critical path.  If an instruction X is committed, and the only
instructions later in the reorder buffer are data-flow successors of
X, then X is obviously on the critical path.  An instruction Y that
delivers the last input that releases X from the scheduler into the
functional unit is also on the critical path; this is transitive, and
several results may arrive in the same cycle.

Marking X as a critical instruction is relatively easy, although one
might also count how many times of all dynamic instances of the
instruction were critical.  Marking the critical data-flow
predecessors is harder, especially across several levels (not to
mention all levels); one way is to do it over time: when an
instruction V delivers a dependency that releases an instruction W
from the scheduler that is already marked as critical, V is marked as
critical as well.

The same instruction may be on the critical path in one execution, but
not in another execution, due to cache hits, or differences in control
flow.  The approach outlined above only works correctly if W is always
on the critical path.  V should probably only marked as critical if
the number of critical executions of W relative to the overall
executions of W is high.

Showing the critical path through performance counters might help
programmers improve the performance of their programs.

- anton
--
'Anyone trying for "industrial quality" ISA should avoid undefined behavior.'
  Mitch Alsup, <c17fcd89-f024-40e7-a594-88a85ac10d20o@googlegroups.com>