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(TargetOpcode::INIT_UNDEF), TmpInitSubReg); 181 Register NewReg = MRI->createVirtualRegister(TargetRegClass); 182 BuildMI(*MI.getParent(), &MI, MI.getDebugLoc(), 183 TII->get(TargetOpcode::INSERT_SUBREG), NewReg) 184 .addReg(LatestReg) 185 .addReg(TmpInitSubReg) 186 .addImm(ind); 187 LatestReg = NewReg; 188 } 189 190 UseMO.setReg(LatestReg); 191 } 192 193 return Changed; 194 } 195 196 bool InitUndef::fixupIllOperand(MachineInstr *MI, MachineOperand &MO) { 197 198 LLVM_DEBUG( 199 dbgs() << "Emitting PseudoInitUndef Instruction for implicit register " 200 << printReg(MO.getReg()) << '\n'); 201 202 const TargetRegisterClass *TargetRegClass = 203 TRI->getLargestSuperClass(MRI->getRegClass(MO.getReg())); 204 LLVM_DEBUG(dbgs() << "Register Class ID" << TargetRegClass->getID() << "\n"); 205 Register NewReg = MRI->createVirtualRegister(TargetRegClass); 206 BuildMI(*MI->getParent(), MI, MI->getDebugLoc(), 207 TII->get(TargetOpcode::INIT_UNDEF), NewReg); 208 MO.setReg(NewReg); 209 if (MO.isUndef()) 210 MO.setIsUndef(false); 211 return true; 212 } 213 214 bool InitUndef::processBasicBlock(MachineFunction &MF, MachineBasicBlock &MBB, 215 const DeadLaneDetector &DLD) { 216 bool Changed = false; 217 for (MachineBasicBlock::iterator I = MBB.begin(); I != MBB.end(); ++I) { 218 MachineInstr &MI = *I; 219 220 // If we used NoReg to represent the passthru, switch this back to being 221 // an IMPLICIT_DEF before TwoAddressInstructions. 222 unsigned UseOpIdx; 223 if (MI.getNumDefs() != 0 && MI.isRegTiedToUseOperand(0, &UseOpIdx)) { 224 MachineOperand &UseMO = MI.getOperand(UseOpIdx); 225 if (UseMO.getReg() == MCRegister::NoRegister) { 226 const TargetRegisterClass *RC = 227 TII->getRegClass(MI.getDesc(), UseOpIdx, TRI, MF); 228 Register NewDest = MRI->createVirtualRegister(RC); 229 // We don't have a way to update dead lanes, so keep track of the 230 // new register so that we avoid querying it later. 231 NewRegs.insert(NewDest); 232 BuildMI(MBB, I, I->getDebugLoc(), TII->get(TargetOpcode::IMPLICIT_DEF), 233 NewDest); 234 UseMO.setReg(NewDest); 235 Changed = true; 236 } 237 } 238 239 if (isEarlyClobberMI(MI)) { 240 if (MRI->subRegLivenessEnabled()) 241 Changed |= handleSubReg(MF, MI, DLD); 242 Changed |= handleReg(&MI); 243 } 244 } 245 return Changed; 246 } 247 248 bool InitUndef::runOnMachineFunction(MachineFunction &MF) { 249 ST = &MF.getSubtarget(); 250 251 // supportsInitUndef is implemented to reflect if an architecture has support 252 // for the InitUndef pass. Support comes from having the relevant Pseudo 253 // instructions that can be used to initialize the register. The function 254 // returns false by default so requires an implementation per architecture. 255 // Support can be added by overriding the function in a way that best fits 256 // the architecture. 257 if (!ST->supportsInitUndef()) 258 return false; 259 260 MRI = &MF.getRegInfo(); 261 TII = ST->getInstrInfo(); 262 TRI = MRI->getTargetRegisterInfo(); 263 264 bool Changed = false; 265 DeadLaneDetector DLD(MRI, TRI); 266 DLD.computeSubRegisterLaneBitInfo(); 267 268 for (MachineBasicBlock &BB : MF) 269 Changed |= processBasicBlock(MF, BB, DLD); 270 271 for (auto *DeadMI : DeadInsts) 272 DeadMI->eraseFromParent(); 273 DeadInsts.clear(); 274 275 return Changed; 276 } 277