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 NewRegs.clear(); 276 277 return Changed; 278 } 279