This is an archive of the discontinued LLVM Phabricator instance.

[LICM] Don't duplicate instructions just because they're free
ClosedPublic

Authored by nikic on Apr 25 2023, 2:06 AM.

Details

Summary

D37076 makes LICM duplicate instructions into exit blocks if the instruction is free. For GEPs, the motivation appears to be that this allows the GEP to be folded into addressing modes, while non-foldable users outside the loop might prevent this. TBH I don't think LICM is the place to do this (why doesn't CGP apply this heuristic itself?) but at least I understand the motivation.

However, the transform is also applied to all other "free" instructions, which are just that (removed during lowering and not "folded" in some way). For such instruction, this transform seems somewhere between useless, counter-productive (undoing CSE/GVN) and actively incorrect. For example, this transform can duplicate freeze instructions, which is illegal.

This patch limits the transform to just foldable GEPs, though we might want to drop it from LICM entirely as a followup.

This is a small compile-time improvement, because querying TTI cost model for every single instruction is expensive: http://llvm-compile-time-tracker.com/compare.php?from=057b5f1f3573ddceb04d9eb6fb9973358d53fece&to=1211bdf470f784888b8bef867e1e613539998e9b&stat=instructions:u

Diff Detail

Event Timeline

nikic created this revision.Apr 25 2023, 2:06 AM
Herald added a project: Restricted Project. · View Herald TranscriptApr 25 2023, 2:06 AM
nikic requested review of this revision.Apr 25 2023, 2:06 AM
Herald added a project: Restricted Project. · View Herald TranscriptApr 25 2023, 2:06 AM
mkazantsev added inline comments.Apr 25 2023, 4:35 AM
llvm/lib/Transforms/Scalar/LICM.cpp
1379

This function has a very clear semantics of checking cost, and I don't think that legality concerns should be taken into account here. The legality check seems missing here:

// Check to see if we can sink this instruction to the exit blocks
// of the loop.  We can do this if the all users of the instruction are
// outside of the loop.  In this case, it doesn't even matter if the
// operands of the instruction are loop invariant.
//
bool FreeInLoop = false;
bool LoopNestMode = OutermostLoop != nullptr;
if (!I.mayHaveSideEffects() &&
    isNotUsedOrFreeInLoop(I, LoopNestMode ? OutermostLoop : CurLoop,
                          SafetyInfo, TTI, FreeInLoop, LoopNestMode) &&
    canSinkOrHoistInst(I, AA, DT, CurLoop, MSSAU, true, Flags, ORE)) {
  if (sink(I, LI, DT, CurLoop, SafetyInfo, MSSAU, ORE)) {
    if (!FreeInLoop) {
      ++II;
      salvageDebugInfo(I);
      eraseInstruction(I, *SafetyInfo, MSSAU);
    }
    Changed = true;
  }
}

There should be check on legality of duplication somewhere around here.

I also agree that we should possibly consider dropping this transform at all.

nikic added inline comments.Apr 25 2023, 5:06 AM
llvm/lib/Transforms/Scalar/LICM.cpp
1379

This is intended as a change of the cost model (i.e. don't do it for anything but GEP), which also fixes the legality issue by dint of this always being legal for GEPs and it not handling anything else anymore.

We don't have a generic way to check legality of this transform, as far as I know.

nikic updated this revision to Diff 517086.Apr 26 2023, 1:02 AM

Rename Free -> Foldable to make the name match the new implementation.

mkazantsev accepted this revision.Apr 28 2023, 4:59 AM

LG, thanks!

This revision is now accepted and ready to land.Apr 28 2023, 4:59 AM
This revision was landed with ongoing or failed builds.Apr 28 2023, 5:31 AM
This revision was automatically updated to reflect the committed changes.