[X86] Add new pass `X86FixupInstTuning` for fixing up machine-instruction selection.

[goldstein.w.n]

Summary

There are a variety of cases where we want more control over the exact
instruction emitted. This commit creates a new pass to fixup
instructions after the DAG has been lowered. The pass is only meant to
replace instructions that are guranteed to be interchangable, not to
do analysis for special cases.

Handling these instruction changes in in X86ISelLowering of
X86ISelDAGToDAG isn't ideal, as its liable to either break existing
patterns that expected a certain instruction or generate infinite
loops.

Currently, only vpermilps -> vshufps/vshufd is implemented, but
more cases can be added.

[RKSimon]

Please can you split off the patch adding the free domain switch tuning flags? Its been something we've been missing from combineX86ShuffleChain for some time and should be addressed first.

llvm/lib/Target/X86/X86.td

533 ↗

(On Diff #496616)

Maybe rename to TuningNoDomainDelay/TuningNoDomainDelayShuffle - bypass could mean many things.....

1005 ↗

(On Diff #496616)

Bonnell has no domain penalty either (and REALLY likes the shorted instruction encodings).

[goldstein.w.n]

Split off domain flags

[goldstein.w.n]

In D143787#4120193, @RKSimon wrote:

Please can you split off the patch adding the free domain switch tuning flags? Its been something we've been missing from combineX86ShuffleChain for some time and should be addressed first.

Done, see D143859

[RKSimon]

I think this should be controlled by a tuning flag tbh, or even better we do this in a later pass and not in dag/isel

[goldstein.w.n]

In D143787#4122814, @RKSimon wrote:

I think this should be controlled by a tuning flag tbh, or even better we do this in a later pass and not in dag/isel

Where would you suggest putting it?

Also what is the case for the seperate tuning flag? AFAICT its just better code size and equal or better perf so seems
like clear universal win.

[goldstein.w.n]

Rebase

[RKSimon]

We have a number of cases where a specific instruction is faster on one target than another, or there's no domain switch cost and we can use smaller variants, etc.

This comes to mind as well: https://github.com/llvm/llvm-project/issues/43458

We can use tuning flags, but for many cases its just confusing and matching what our scheduler models already tell us. Plus we end up with many permutations of DAG / isel that don't always work well together, or cause infinite loops etc.

My idea was for a small pass similar to FixupLEA/FixBWI that we can drive from a mixture of the subtarget tuning flags and the scheduler model to decide between various equivalent instruction options based on cost estimates. Shuffle ops give themselves to this the most, but theres probably others we might consider as well.

Replacing a single instruction for another is trivial - it might be feasible to replace a single instruction for multiple instructions as well (HADD/HSUB expansion, Funnel Shifts, etc.).

[goldstein.w.n]

In D143787#4128462, @RKSimon wrote:

We have a number of cases where a specific instruction is faster on one target than another, or there's no domain switch cost and we can use smaller variants, etc.

This comes to mind as well: https://github.com/llvm/llvm-project/issues/43458

We can use tuning flags, but for many cases its just confusing and matching what our scheduler models already tell us. Plus we end up with many permutations of DAG / isel that don't always work well together, or cause infinite loops etc.

My idea was for a small pass similar to FixupLEA/FixBWI that we can drive from a mixture of the subtarget tuning flags and the scheduler model to decide between various equivalent instruction options based on cost estimates. Shuffle ops give themselves to this the most, but theres probably others we might consider as well.

Replacing a single instruction for another is trivial - it might be feasible to replace a single instruction for multiple instructions as well (HADD/HSUB expansion, Funnel Shifts, etc.).

I see, that makes sense. I'll take a stab at that.

[goldstein.w.n]

Move logic to a new pass

[goldstein.w.n]

In D143787#4128462, @RKSimon wrote:

We have a number of cases where a specific instruction is faster on one target than another, or there's no domain switch cost and we can use smaller variants, etc.

This comes to mind as well: https://github.com/llvm/llvm-project/issues/43458

We can use tuning flags, but for many cases its just confusing and matching what our scheduler models already tell us. Plus we end up with many permutations of DAG / isel that don't always work well together, or cause infinite loops etc.

My idea was for a small pass similar to FixupLEA/FixBWI that we can drive from a mixture of the subtarget tuning flags and the scheduler model to decide between various equivalent instruction options based on cost estimates. Shuffle ops give themselves to this the most, but theres probably others we might consider as well.

Replacing a single instruction for another is trivial - it might be feasible to replace a single instruction for multiple instructions as well (HADD/HSUB expansion, Funnel Shifts, etc.).

Done, only added vpermilps -> vshufps/vshufd at the moment, but other replacements should be doable.

[pengfei]

llvm/lib/Target/X86/X86FixupISel.cpp

27 ↗

(On Diff #497899)

We often use all lower case latters.

69 ↗

(On Diff #497899)

Lambda function name should starts with upper latter.

75 ↗

(On Diff #497899)

ditto.

86 ↗

(On Diff #497899)

Better to use processVPERMILPSri/processVPERMILPSmi

llvm/test/CodeGen/X86/opt-pipeline.ll

205

Is the pass too far away from ISel?

[goldstein.w.n]

llvm/test/CodeGen/X86/opt-pipeline.ll

205

I think we want it to run quite after all other instruction transformations.

The important ones are register allocation (so we convert vpermlipsri -> vshufpsrri at a spill) and domainfixup (so we have the correct instructions).

[goldstein.w.n]

Fix style

[goldstein.w.n]

Fixed the nits.

[craig.topper]

llvm/lib/Target/X86/X86FixupISel.cpp

1 ↗

(On Diff #497899)

Referring to ISel and running the pass so far from instruction selection is perhaps misleading.

[pengfei]

llvm/lib/Target/X86/X86FixupISel.cpp

1 ↗

(On Diff #497899)

I have the same concern, if it is required for vpermli*, maybe just name it FixupVpermli.

[RKSimon]

llvm/lib/Target/X86/X86FixupISel.cpp

1 ↗

(On Diff #497899)

The hope is to add other instruction combos in the future - given we're trying to fixup for a mixture of tuning/scheduler - maybe X86FixupTuning.cpp ?

12 ↗

(On Diff #497908)

What do you mean by analysis? I'm hoping we can use scheduler models in the future to drive some transforms here.

68 ↗

(On Diff #497908)

Comments explaining the exact purpose of these transforms would be useful.

69 ↗

(On Diff #497908)

(style) use bool instead of auto

[goldstein.w.n]

llvm/lib/Target/X86/X86FixupISel.cpp

12 ↗

(On Diff #497908)

I mean something like transforming vpermq ymm <-> vshufd ymm should not be put in this file, as its not always valid (requires analyzing the mask to see if no lane crosses and repeated / mask is only in pairs of 2). OTOH vpermilps <-> vshufd are always interchangable. I'll make the logic more clear.

[RKSimon]

llvm/lib/Target/X86/X86FixupISel.cpp

12 ↗

(On Diff #497908)

Agreed, anything involving valuetracking etc. shouldn't be done this late.

However, I don't see any problem with replacing instructions based on immediates that are part of the instruction - we already do this for load folding, commutation, domain switching etc.

[goldstein.w.n]

llvm/lib/Target/X86/X86FixupISel.cpp

1 ↗

(On Diff #497899)

Renamed to X86FixupInstTuning.cpp (though FixupTuning was a bit generic about what exactly is being tuned).

12 ↗

(On Diff #497908)

Agreed, anything involving valuetracking etc. shouldn't be done this late.

However, I don't see any problem with replacing instructions based on immediates that are part of the instruction - we already do this for load folding, commutation, domain switching etc.

Its not inherently wrong, but my feeling is that belongs in X86ISelLowering/X86ISelDAGToDAG/td. I think it would work for a few instructions, but it seems like the kind of thing that will explode the complexity of the file over time (even the shuffle logic with in X86ISelLowering is extremely complex/convoluted with the clean APIs the DAG has). I think that kind of complexity on a file operation on machine instr will be bug-prone. Generally, we *could* do it here, but I don't think we *should*.

[goldstein.w.n]

Fix some nits, rename

[goldstein.w.n]

Support for tput/code size decisions.
handle unpck/movhlps

[goldstein.w.n]

Rebase

[goldstein.w.n]

Rebase

[RKSimon]

Probably better for this first patch to add the pass and the inital vpermilps -> vshufps/vshufd fold, the scheduler based unpckpd fold can be added in a followup

llvm/lib/Target/X86/X86FixupInstTuning.cpp

85

It'd be better to return Optional<double> instead of 0.0 for failed matches (and return nullopt here)

[goldstein.w.n]

Remove unpckpd -> shufps and the target sched info stuff

[goldstein.w.n]

In D143787#4144121, @RKSimon wrote:

Probably better for this first patch to add the pass and the inital vpermilps -> vshufps/vshufd fold, the scheduler based unpckpd fold can be added in a followup

Done, version with sched info + unpck transform as at: D144570

llvm/lib/Target/X86/X86FixupInstTuning.cpp

85

Done in new version: D144570

[goldstein.w.n]

Rebase

[RKSimon]

LGTM with a few minors - thank you for working on this!

llvm/lib/Target/X86/X86FixupInstTuning.cpp

20

VPERMILPS xmm?

95

Maybe add a TODO for always changing for Os/Oz builds?

101

Are you intending to support the predicated variants as well? Maybe add a TODO?

[goldstein.w.n]

llvm/lib/Target/X86/X86FixupInstTuning.cpp

101

What do you mean? For VPERMILPS all variants are supported I believe.

[goldstein.w.n]

Add some todos

[RKSimon]

llvm/lib/Target/X86/X86FixupInstTuning.cpp

101

X86::VPERMILPSZrikz etc.

[e-kud]

LGTM. I second that masked versions should be handled as well. I thought they have TP equal to perms but I've double checked and it seems that masked shuffles have TP=0.5 comparing to perms.

[goldstein.w.n]

llvm/lib/Target/X86/X86FixupInstTuning.cpp

101

Oh sure, Ill add a todo for now and make a new patch for predicate version later today.

[goldstein.w.n]

Add TODO for masked predicates

[goldstein.w.n]

In D143787#4150522, @e-kud wrote:

LGTM. I second that masked versions should be handled as well. I thought they have TP equal to perms but I've double checked and it seems that masked shuffles have TP=0.5 comparing to perms.

@RKSimon added masked predicates at D144763

[RKSimon]

someting I just noticed - please can you ensure you have AVX1 test coverage for the VPERMILPSmi/VPERMILPSYmi cases - we can't fold the VPERMILPSYmi case to the VPSHUDYmi which requires AVX2

llvm/lib/Target/X86/X86FixupInstTuning.cpp

116

VPSHUFDYmi? I think this needs a AVX2 check as well

118

VPSHUFDmi

[goldstein.w.n]

llvm/lib/Target/X86/X86FixupInstTuning.cpp

116

Good catch. Do you know the API for checking if an instruction is supported on the target? Or will it need to be manually done case by case?

[goldstein.w.n]

In D143787#4151630, @RKSimon wrote:

someting I just noticed - please can you ensure you have AVX1 test coverage for the VPERMILPSmi/VPERMILPSYmi cases - we can't fold the VPERMILPSYmi case to the VPSHUDYmi which requires AVX2

I'll add tests similar to what we have for .unpckpd

[goldstein.w.n]

Add missing AVX2 check and fix ymm/xmm subsitutions

[goldstein.w.n]

llvm/lib/Target/X86/X86FixupInstTuning.cpp

116

VPSHUFDYmi? I think this needs a AVX2 check as well

Done, did just a manual check here, but if you know an API for querying if an opcode is supported that would probably be better going forward.
Added tests for the permilps transforms here: D144779 and the AVX2 requirement is tested.

[pengfei]

I don't think there exists such an API. We don't record such information for each instruction.

[goldstein.w.n]

Rebase

[RKSimon]

In D143787#4152348, @pengfei wrote:

I don't think there exists such an API. We don't record such information for each instruction.

By this point we've lost that info - its embedded in the isel tables but not much else - so you'll have to do it manually for the AVX1/AVX2 cases

[RKSimon]

LGTM

[goldstein.w.n]

Rebase

[goldstein.w.n]

Rebase

[goldstein.w.n]

Rebase (after D144832, no dep on D143786)

llvm/lib/Target/X86/X86FixupInstTuning.cpp

+//===-- X86FixupInstTunings.cpp - replace instructions -----------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// This file does a tuning pass replacing slower machine instructions
+// with faster ones. We do this here, as opposed to during normal ISel, as
+// attempting to get the "right" instruction can break patterns. This pass
+// is not meant search for special cases where an instruction can be transformed
+// to another, it is only meant to do transformations where the old instruction
+// is always replacable with the new instructions. For example:
+//
+//      `vpermq ymm` -> `vshufd ymm`
+//          -- BAD, not always valid (lane cross/non-repeated mask)
+//
+//      `vpermilps ymm` -> `vshufd ymm`
+//          -- GOOD, always replaceable
+//
+//===----------------------------------------------------------------------===//
+
+#include "X86.h"
+#include "X86InstrInfo.h"
+#include "X86Subtarget.h"
+#include "llvm/ADT/Statistic.h"
+#include "llvm/CodeGen/MachineFunctionPass.h"
+#include "llvm/CodeGen/MachineInstrBuilder.h"
+#include "llvm/CodeGen/MachineRegisterInfo.h"
+
+using namespace llvm;
+
+#define DEBUG_TYPE "x86-fixup-inst-tuning"
+
+STATISTIC(NumInstChanges, "Number of instructions changes");
+
+namespace {
+class X86FixupInstTuningPass : public MachineFunctionPass {
+public:
+  static char ID;
+
+  X86FixupInstTuningPass() : MachineFunctionPass(ID) {}
+
+  StringRef getPassName() const override { return "X86 Fixup Inst Tuning"; }
+
+  bool runOnMachineFunction(MachineFunction &MF) override;
+  bool processInstruction(MachineFunction &MF, MachineBasicBlock &MBB,
+                          MachineBasicBlock::iterator &I);
+
+  // This pass runs after regalloc and doesn't support VReg operands.
+  MachineFunctionProperties getRequiredProperties() const override {
+    return MachineFunctionProperties().set(
+        MachineFunctionProperties::Property::NoVRegs);
+  }
+
+private:
+  const X86InstrInfo *TII = nullptr;
+  const X86Subtarget *ST = nullptr;
+};
+} // end anonymous namespace
+
+char X86FixupInstTuningPass::ID = 0;
+
+INITIALIZE_PASS(X86FixupInstTuningPass, DEBUG_TYPE, DEBUG_TYPE, false, false)
+
+FunctionPass *llvm::createX86FixupInstTuning() {
+  return new X86FixupInstTuningPass();
+}
+
+bool X86FixupInstTuningPass::processInstruction(
+    MachineFunction &MF, MachineBasicBlock &MBB,
+    MachineBasicBlock::iterator &I) {
+  MachineInstr &MI = *I;
+  unsigned Opc = MI.getOpcode();
+  unsigned NumOperands = MI.getDesc().getNumOperands();
+
+  // `vpermilps r, i` -> `vshufps r, r, i`
+  // `vshufps` is always as fast or faster than `vpermilps` and takes 1 less
+  // byte of code size.
+  auto ProcessVPERMILPSri = [&](unsigned NewOpc) -> bool {
+    unsigned MaskImm = MI.getOperand(NumOperands - 1).getImm();
+    MI.removeOperand(NumOperands - 1);
+    MI.addOperand(MI.getOperand(1));
+    MI.setDesc(TII->get(NewOpc));
+    MI.addOperand(MachineOperand::CreateImm(MaskImm));
+    return true;
+  };
+
+  // `vpermilps m, i` -> `vpshufd m, i` iff no domain delay penalty on shuffles.
+  // `vpshufd` is always as fast or faster than `vpermilps` and takes 1 less
+  // byte of code size.
+  auto ProcessVPERMILPSmi = [&](unsigned NewOpc) -> bool {
+    // TODO: Might be work adding bypass delay if -Os/-Oz is enabled as
+    // `vpshufd` saves a byte of code size.
+    if (!ST->hasNoDomainDelayShuffle())
+      return false;
+    MI.setDesc(TII->get(NewOpc));
+    return true;
+  };
+
+  // TODO: Add masked predicate execution variants.
+  switch (Opc) {
+  case X86::VPERMILPSri:
+    return ProcessVPERMILPSri(X86::VSHUFPSrri);
+  case X86::VPERMILPSYri:
+    return ProcessVPERMILPSri(X86::VSHUFPSYrri);
+  case X86::VPERMILPSZ128ri:
+    return ProcessVPERMILPSri(X86::VSHUFPSZ128rri);
+  case X86::VPERMILPSZ256ri:
+    return ProcessVPERMILPSri(X86::VSHUFPSZ256rri);
+  case X86::VPERMILPSZri:
+    return ProcessVPERMILPSri(X86::VSHUFPSZrri);
+  case X86::VPERMILPSmi:
+    return ProcessVPERMILPSmi(X86::VPSHUFDmi);
+  case X86::VPERMILPSYmi:
+    // TODO: See if there is a more generic way we can test if the replacement
+    // instruction is supported.
+    return ST->hasAVX2() ? ProcessVPERMILPSmi(X86::VPSHUFDYmi) : false;
+  case X86::VPERMILPSZ128mi:
+    return ProcessVPERMILPSmi(X86::VPSHUFDZ128mi);
+  case X86::VPERMILPSZ256mi:
+    return ProcessVPERMILPSmi(X86::VPSHUFDZ256mi);
+  case X86::VPERMILPSZmi:
+    return ProcessVPERMILPSmi(X86::VPSHUFDZmi);
+  default:
+    return false;
+  }
+}
+
+bool X86FixupInstTuningPass::runOnMachineFunction(MachineFunction &MF) {
+  LLVM_DEBUG(dbgs() << "Start X86FixupInstTuning\n";);
+  bool Changed = false;
+  ST = &MF.getSubtarget<X86Subtarget>();
+  TII = ST->getInstrInfo();
+  for (MachineBasicBlock &MBB : MF) {
+    for (MachineBasicBlock::iterator I = MBB.begin(); I != MBB.end(); ++I) {
+      if (processInstruction(MF, MBB, I)) {
+        ++NumInstChanges;
+        Changed = true;
+      }
+    }
+  }
+  LLVM_DEBUG(dbgs() << "End X86FixupInstTuning\n";);
+  return Changed;
+}

llvm/test/CodeGen/X86/opt-pipeline.ll

 ; CHECK-NEXT:       X86 vzeroupper inserter
 ; CHECK-NEXT:       MachineDominator Tree Construction
 ; CHECK-NEXT:       Machine Natural Loop Construction
 ; CHECK-NEXT:       Lazy Machine Block Frequency Analysis
 ; CHECK-NEXT:       X86 Byte/Word Instruction Fixup
 ; CHECK-NEXT:       Lazy Machine Block Frequency Analysis
 ; CHECK-NEXT:       X86 Atom pad short functions
 ; CHECK-NEXT:       X86 LEA Fixup
+; CHECK-NEXT:       X86 Fixup Inst Tuning
 ; CHECK-NEXT:       Compressing EVEX instrs to VEX encoding when possible
 ; CHECK-NEXT:       X86 Discriminate Memory Operands
 ; CHECK-NEXT:       X86 Insert Cache Prefetches
 ; CHECK-NEXT:       X86 insert wait instruction
 ; CHECK-NEXT:       Contiguously Lay Out Funclets
 ; CHECK-NEXT:       StackMap Liveness Analysis
 ; CHECK-NEXT:       Live DEBUG_VALUE analysis
 ; CHECK-NEXT:       Machine Sanitizer Binary Metadata