This is an archive of the discontinued LLVM Phabricator instance.

MachineCombiner: use height in improvesCriticialPathLen()
AbandonedPublic

Authored by artagnon on May 16 2023, 5:59 AM.

Details

Summary

improvesCriticialPathLen() currently has an early-exit on
CombinerObjective::MustReduceDepth introduced in 766589ef (add
'MustReduceDepth' as an objective/cost-metric for the MachineCombiner),
by only considering transforms that would reduce the root depth.
However, the patch was introduced because MachineCombiner's use of
MachineTraceMetrics was incomplete, as noted in the Phabricator
discussion. This patch attempts to make better use of
MachineTraceMetrics in MachineCombiner, by also computing instruction
heights, and asserting that the critical path length = depth + slack +
height. We then unify the cost model in improvesCriticalPathLen(), since
there are only two essential differences between the MustReduceDepth
case and the other case: the MustReduceDepth case doesn't want to
consider slack, and wants to be more conservative with respect to the
cost comparison.

Diff Detail

Event Timeline

artagnon created this revision.May 16 2023, 5:59 AM
Herald added a project: Restricted Project. · View Herald TranscriptMay 16 2023, 5:59 AM
artagnon requested review of this revision.May 16 2023, 5:59 AM

This patch gives us improvements on standard benchmarks like Embench.

A couple of things to note:

  • I need some help with the height calculation, as it is wrong in some places.
  • I've only updated the RISC-V tests. Will update tests for other architectures, once the patch is closer to final form.
shiva0217 added inline comments.
llvm/lib/CodeGen/MachineCombiner.cpp
265

Should it go through all users as following?

for (MachineInstr &UseInstr : MRI->use_instructions(MO.getReg())) {

Theoretically, NewRootHeight and OldRootHeight should be equal.
Does it make sense to remove the Heights calculations?

llvm/lib/CodeGen/MachineCombiner.cpp
269

In MachineTraceMetrics::Ensemble::computeInstrHeights function, Loop header PHI heights are all 0.

It seems it could be addressed by defining.

unsigned
MachineTraceMetrics::Trace::getPHIHeight(const MachineInstr &PHI) const{
  // Loop header PHI heights are all 0.
  return TBI.Succ ? getInstrCycles(PHI).Height : 0;
}
artagnon abandoned this revision.May 17 2023, 3:28 AM

Theoretically, NewRootHeight and OldRootHeight should be equal.

You're absolutely right; I'll try to explain the improvements I'm seeing, and re-think this patch.