llvm/lib/CodeGen/InitUndef.cpp

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