1//===- RISCVRVVInitUndef.cpp - Initialize undef vector value to pseudo ----===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This file implements a function pass that initializes undef vector value to
10// temporary pseudo instruction and remove it in expandpseudo pass to prevent
11// register allocation resulting in a constraint violated result for vector
12// instruction.  It also rewrites the NoReg tied operand back to an
13// IMPLICIT_DEF.
14//
15// RISC-V vector instruction has register overlapping constraint for certain
16// instructions, and will cause illegal instruction trap if violated, we use
17// early clobber to model this constraint, but it can't prevent register
18// allocator allocated same or overlapped if the input register is undef value,
19// so convert IMPLICIT_DEF to temporary pseudo instruction and remove it later
20// could prevent that happen, it's not best way to resolve this, and it might
21// change the order of program or increase the register pressure, so ideally we
22// should model the constraint right, but before we model the constraint right,
23// it's the only way to prevent that happen.
24//
25// When we enable the subregister liveness option, it will also trigger same
26// issue due to the partial of register is undef. If we pseudoinit the whole
27// register, then it will generate redundant COPY instruction. Currently, it
28// will generate INSERT_SUBREG to make sure the whole register is occupied
29// when program encounter operation that has early-clobber constraint.
30//
31//
32// See also: https://github.com/llvm/llvm-project/issues/50157
33//
34// Additionally, this pass rewrites tied operands of vector instructions
35// from NoReg to IMPLICIT_DEF.  (Not that this is a non-overlapping set of
36// operands to the above.)  We use NoReg to side step a MachineCSE
37// optimization quality problem but need to convert back before
38// TwoAddressInstruction.  See pr64282 for context.
39//
40//===----------------------------------------------------------------------===//
41
42#include "RISCV.h"
43#include "RISCVSubtarget.h"
44#include "llvm/ADT/SmallSet.h"
45#include "llvm/ADT/SmallVector.h"
46#include "llvm/CodeGen/DetectDeadLanes.h"
47#include "llvm/CodeGen/MachineFunctionPass.h"
48using namespace llvm;
49
50#define DEBUG_TYPE "riscv-init-undef"
51#define RISCV_INIT_UNDEF_NAME "RISC-V init undef pass"
52
53namespace {
54
55class RISCVInitUndef : public MachineFunctionPass {
56  const TargetInstrInfo *TII;
57  MachineRegisterInfo *MRI;
58  const RISCVSubtarget *ST;
59  const TargetRegisterInfo *TRI;
60
61  // Newly added vregs, assumed to be fully rewritten
62  SmallSet<Register, 8> NewRegs;
63  SmallVector<MachineInstr *, 8> DeadInsts;
64
65public:
66  static char ID;
67
68  RISCVInitUndef() : MachineFunctionPass(ID) {}
69  bool runOnMachineFunction(MachineFunction &MF) override;
70
71  void getAnalysisUsage(AnalysisUsage &AU) const override {
72    AU.setPreservesCFG();
73    MachineFunctionPass::getAnalysisUsage(AU);
74  }
75
76  StringRef getPassName() const override { return RISCV_INIT_UNDEF_NAME; }
77
78private:
79  bool processBasicBlock(MachineFunction &MF, MachineBasicBlock &MBB,
80                         const DeadLaneDetector &DLD);
81  bool isVectorRegClass(const Register R);
82  const TargetRegisterClass *
83  getVRLargestSuperClass(const TargetRegisterClass *RC) const;
84  bool handleSubReg(MachineFunction &MF, MachineInstr &MI,
85                    const DeadLaneDetector &DLD);
86  bool fixupIllOperand(MachineInstr *MI, MachineOperand &MO);
87  bool handleReg(MachineInstr *MI);
88};
89
90} // end anonymous namespace
91
92char RISCVInitUndef::ID = 0;
93INITIALIZE_PASS(RISCVInitUndef, DEBUG_TYPE, RISCV_INIT_UNDEF_NAME, false, false)
94char &llvm::RISCVInitUndefID = RISCVInitUndef::ID;
95
96const TargetRegisterClass *
97RISCVInitUndef::getVRLargestSuperClass(const TargetRegisterClass *RC) const {
98  if (RISCV::VRM8RegClass.hasSubClassEq(RC))
99    return &RISCV::VRM8RegClass;
100  if (RISCV::VRM4RegClass.hasSubClassEq(RC))
101    return &RISCV::VRM4RegClass;
102  if (RISCV::VRM2RegClass.hasSubClassEq(RC))
103    return &RISCV::VRM2RegClass;
104  if (RISCV::VRRegClass.hasSubClassEq(RC))
105    return &RISCV::VRRegClass;
106  return RC;
107}
108
109bool RISCVInitUndef::isVectorRegClass(const Register R) {
110  const TargetRegisterClass *RC = MRI->getRegClass(R);
111  return RISCV::VRRegClass.hasSubClassEq(RC) ||
112         RISCV::VRM2RegClass.hasSubClassEq(RC) ||
113         RISCV::VRM4RegClass.hasSubClassEq(RC) ||
114         RISCV::VRM8RegClass.hasSubClassEq(RC);
115}
116
117static unsigned getUndefInitOpcode(unsigned RegClassID) {
118  switch (RegClassID) {
119  case RISCV::VRRegClassID:
120    return RISCV::PseudoRVVInitUndefM1;
121  case RISCV::VRM2RegClassID:
122    return RISCV::PseudoRVVInitUndefM2;
123  case RISCV::VRM4RegClassID:
124    return RISCV::PseudoRVVInitUndefM4;
125  case RISCV::VRM8RegClassID:
126    return RISCV::PseudoRVVInitUndefM8;
127  default:
128    llvm_unreachable("Unexpected register class.");
129  }
130}
131
132static bool isEarlyClobberMI(MachineInstr &MI) {
133  return llvm::any_of(MI.defs(), [](const MachineOperand &DefMO) {
134    return DefMO.isReg() && DefMO.isEarlyClobber();
135  });
136}
137
138static bool findImplictDefMIFromReg(Register Reg, MachineRegisterInfo *MRI) {
139  for (auto &DefMI : MRI->def_instructions(Reg)) {
140    if (DefMI.getOpcode() == TargetOpcode::IMPLICIT_DEF)
141      return true;
142  }
143  return false;
144}
145
146bool RISCVInitUndef::handleReg(MachineInstr *MI) {
147  bool Changed = false;
148  for (auto &UseMO : MI->uses()) {
149    if (!UseMO.isReg())
150      continue;
151    if (UseMO.isTied())
152      continue;
153    if (!UseMO.getReg().isVirtual())
154      continue;
155    if (!isVectorRegClass(UseMO.getReg()))
156      continue;
157
158    if (UseMO.isUndef() || findImplictDefMIFromReg(UseMO.getReg(), MRI))
159      Changed |= fixupIllOperand(MI, UseMO);
160  }
161  return Changed;
162}
163
164bool RISCVInitUndef::handleSubReg(MachineFunction &MF, MachineInstr &MI,
165                                  const DeadLaneDetector &DLD) {
166  bool Changed = false;
167
168  for (MachineOperand &UseMO : MI.uses()) {
169    if (!UseMO.isReg())
170      continue;
171    if (!UseMO.getReg().isVirtual())
172      continue;
173    if (UseMO.isTied())
174      continue;
175
176    Register Reg = UseMO.getReg();
177    if (NewRegs.count(Reg))
178      continue;
179    DeadLaneDetector::VRegInfo Info =
180        DLD.getVRegInfo(Register::virtReg2Index(Reg));
181
182    if (Info.UsedLanes == Info.DefinedLanes)
183      continue;
184
185    const TargetRegisterClass *TargetRegClass =
186        getVRLargestSuperClass(MRI->getRegClass(Reg));
187
188    LaneBitmask NeedDef = Info.UsedLanes & ~Info.DefinedLanes;
189
190    LLVM_DEBUG({
191      dbgs() << "Instruction has undef subregister.\n";
192      dbgs() << printReg(Reg, nullptr)
193             << " Used: " << PrintLaneMask(Info.UsedLanes)
194             << " Def: " << PrintLaneMask(Info.DefinedLanes)
195             << " Need Def: " << PrintLaneMask(NeedDef) << "\n";
196    });
197
198    SmallVector<unsigned> SubRegIndexNeedInsert;
199    TRI->getCoveringSubRegIndexes(*MRI, TargetRegClass, NeedDef,
200                                  SubRegIndexNeedInsert);
201
202    Register LatestReg = Reg;
203    for (auto ind : SubRegIndexNeedInsert) {
204      Changed = true;
205      const TargetRegisterClass *SubRegClass =
206          getVRLargestSuperClass(TRI->getSubRegisterClass(TargetRegClass, ind));
207      Register TmpInitSubReg = MRI->createVirtualRegister(SubRegClass);
208      BuildMI(*MI.getParent(), &MI, MI.getDebugLoc(),
209              TII->get(getUndefInitOpcode(SubRegClass->getID())),
210              TmpInitSubReg);
211      Register NewReg = MRI->createVirtualRegister(TargetRegClass);
212      BuildMI(*MI.getParent(), &MI, MI.getDebugLoc(),
213              TII->get(TargetOpcode::INSERT_SUBREG), NewReg)
214          .addReg(LatestReg)
215          .addReg(TmpInitSubReg)
216          .addImm(ind);
217      LatestReg = NewReg;
218    }
219
220    UseMO.setReg(LatestReg);
221  }
222
223  return Changed;
224}
225
226bool RISCVInitUndef::fixupIllOperand(MachineInstr *MI, MachineOperand &MO) {
227
228  LLVM_DEBUG(
229      dbgs() << "Emitting PseudoRVVInitUndef for implicit vector register "
230             << MO.getReg() << '\n');
231
232  const TargetRegisterClass *TargetRegClass =
233      getVRLargestSuperClass(MRI->getRegClass(MO.getReg()));
234  unsigned Opcode = getUndefInitOpcode(TargetRegClass->getID());
235  Register NewReg = MRI->createVirtualRegister(TargetRegClass);
236  BuildMI(*MI->getParent(), MI, MI->getDebugLoc(), TII->get(Opcode), NewReg);
237  MO.setReg(NewReg);
238  if (MO.isUndef())
239    MO.setIsUndef(false);
240  return true;
241}
242
243bool RISCVInitUndef::processBasicBlock(MachineFunction &MF,
244                                       MachineBasicBlock &MBB,
245                                       const DeadLaneDetector &DLD) {
246  bool Changed = false;
247  for (MachineBasicBlock::iterator I = MBB.begin(); I != MBB.end(); ++I) {
248    MachineInstr &MI = *I;
249
250    // If we used NoReg to represent the passthru, switch this back to being
251    // an IMPLICIT_DEF before TwoAddressInstructions.
252    unsigned UseOpIdx;
253    if (MI.getNumDefs() != 0 && MI.isRegTiedToUseOperand(0, &UseOpIdx)) {
254      MachineOperand &UseMO = MI.getOperand(UseOpIdx);
255      if (UseMO.getReg() == RISCV::NoRegister) {
256        const TargetRegisterClass *RC =
257          TII->getRegClass(MI.getDesc(), UseOpIdx, TRI, MF);
258        Register NewDest = MRI->createVirtualRegister(RC);
259        // We don't have a way to update dead lanes, so keep track of the
260        // new register so that we avoid querying it later.
261        NewRegs.insert(NewDest);
262        BuildMI(MBB, I, I->getDebugLoc(),
263                TII->get(TargetOpcode::IMPLICIT_DEF), NewDest);
264        UseMO.setReg(NewDest);
265        Changed = true;
266      }
267    }
268
269    if (isEarlyClobberMI(MI)) {
270      if (ST->enableSubRegLiveness())
271        Changed |= handleSubReg(MF, MI, DLD);
272      Changed |= handleReg(&MI);
273    }
274  }
275  return Changed;
276}
277
278bool RISCVInitUndef::runOnMachineFunction(MachineFunction &MF) {
279  ST = &MF.getSubtarget<RISCVSubtarget>();
280  if (!ST->hasVInstructions())
281    return false;
282
283  MRI = &MF.getRegInfo();
284  TII = ST->getInstrInfo();
285  TRI = MRI->getTargetRegisterInfo();
286
287  bool Changed = false;
288  DeadLaneDetector DLD(MRI, TRI);
289  DLD.computeSubRegisterLaneBitInfo();
290
291  for (MachineBasicBlock &BB : MF)
292    Changed |= processBasicBlock(MF, BB, DLD);
293
294  for (auto *DeadMI : DeadInsts)
295    DeadMI->eraseFromParent();
296  DeadInsts.clear();
297
298  return Changed;
299}
300
301FunctionPass *llvm::createRISCVInitUndefPass() { return new RISCVInitUndef(); }
302