Compute instruction depths through the current trace.

Assuming infinite issue width, compute the earliest each instruction in
the trace can issue, when considering the latency of data dependencies.

Compute instruction depths through the current trace.

Assuming infinite issue width, compute the earliest each instruction in
the trace can issue, when considering the latency of data dependencies.
The issue cycle is record as a 'depth' from the beginning of the trace.

This is half the computation required to find the length of the critical
path through the trace. Heights are next.

llvm-svn: 161074

show more ...

Rename CT -> MTM. MachineTraceMetrics is abbreviated MTM.

llvm-svn: 161072

Avoid looking at stale data in verifyAnalysis().

llvm-svn: 161004

Allow traces to enter nested loops.

This lets traces include the final iteration of a nested loop above the
center block, and the first iteration of a nested loop below the center
block.

We still d

Allow traces to enter nested loops.

This lets traces include the final iteration of a nested loop above the
center block, and the first iteration of a nested loop below the center
block.

We still don't allow traces to contain backedges, and traces are
truncated where they would leave a loop, as seen from the center block.

llvm-svn: 161003

show more ...

Assert that all trace candidate blocks have been visited by the PO.

When computing a trace, all the candidates for pred/succ must have been
visited. Filter out back-edges first, though. The PO trave

Assert that all trace candidate blocks have been visited by the PO.

When computing a trace, all the candidates for pred/succ must have been
visited. Filter out back-edges first, though. The PO traversal ignores
them.

Thanks to Andy for spotting this in review.

llvm-svn: 160995

show more ...

Hook into PassManager's analysis verification.

By overriding Pass::verifyAnalysis(), the pass contents will be verified
by the pass manager.

llvm-svn: 160994

Add MachineInstr::isTransient().

This is a cleaned up version of the isFree() function in
MachineTraceMetrics.cpp.

Transient instructions are very unlikely to produce any code in the
final output.

Add MachineInstr::isTransient().

This is a cleaned up version of the isFree() function in
MachineTraceMetrics.cpp.

Transient instructions are very unlikely to produce any code in the
final output. Either because they get eliminated by RegisterCoalescing,
or because they are pseudo-instructions like labels and debug values.

llvm-svn: 160977

show more ...

Add MachineTraceMetrics::verify().

This function verifies the consistency of cached data in the
MachineTraceMetrics analysis.

llvm-svn: 160976

Verify that the CFG hasn't changed during invalidate().

The MachineTraceMetrics analysis must be invalidated before modifying
the CFG. This will catch some of the violations of that rule.

llvm-svn:

Verify that the CFG hasn't changed during invalidate().

The MachineTraceMetrics analysis must be invalidated before modifying
the CFG. This will catch some of the violations of that rule.

llvm-svn: 160969

show more ...

Add more debug output to MachineTraceMetrics.

llvm-svn: 160905

Keep track of the head and tail of the trace through each block.

This makes it possible to quickly detect blocks that are outside the
trace.

llvm-svn: 160904

Use an otherwise unused variable.

llvm-svn: 160798

Start scaffolding for a MachineTraceMetrics analysis pass.

This is still a work in progress.

Out-of-order CPUs usually execute instructions from multiple basic
blocks simultaneously, so it is neces

Start scaffolding for a MachineTraceMetrics analysis pass.

This is still a work in progress.

Out-of-order CPUs usually execute instructions from multiple basic
blocks simultaneously, so it is necessary to look at longer traces when
estimating the performance effects of code transformations.

The MachineTraceMetrics analysis will pick a typical trace through a
given basic block and provide performance metrics for the trace. Metrics
will include:

- Instruction count through the trace.
- Issue count per functional unit.
- Critical path length, and per-instruction 'slack'.

These metrics can be used to determine the performance limiting factor
when executing the trace, and how it will be affected by a code
transformation.

Initially, this will be used by the early if-conversion pass.

llvm-svn: 160796

show more ...