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.all_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 124 if (UseMO.isUndef() || findImplictDefMIFromReg(UseMO.getReg(), MRI)) 125 Changed |= fixupIllOperand(MI, UseMO); 126 } 127 return Changed; 128 } 129 130 bool InitUndef::handleSubReg(MachineFunction &MF, MachineInstr &MI, 131 const DeadLaneDetector &DLD) { 132 bool Changed = false; 133 134 for (MachineOperand &UseMO : MI.uses()) { 135 if (!UseMO.isReg()) 136 continue; 137 if (!UseMO.getReg().isVirtual()) 138 continue; 139 if (UseMO.isTied()) 140 continue; 141 142 Register Reg = UseMO.getReg(); 143 if (NewRegs.count(Reg)) 144 continue; 145 DeadLaneDetector::VRegInfo Info = 146 DLD.getVRegInfo(Register::virtReg2Index(Reg)); 147 148 if (Info.UsedLanes == Info.DefinedLanes) 149 continue; 150 151 const TargetRegisterClass *TargetRegClass = MRI->getRegClass(Reg); 152 153 LaneBitmask NeedDef = Info.UsedLanes & ~Info.DefinedLanes; 154 155 LLVM_DEBUG({ 156 dbgs() << "Instruction has undef subregister.\n"; 157 dbgs() << printReg(Reg, nullptr) 158 << " Used: " << PrintLaneMask(Info.UsedLanes) 159 << " Def: " << PrintLaneMask(Info.DefinedLanes) 160 << " Need Def: " << PrintLaneMask(NeedDef) << "\n"; 161 }); 162 163 SmallVector<unsigned> SubRegIndexNeedInsert; 164 TRI->getCoveringSubRegIndexes(TargetRegClass, NeedDef, 165 SubRegIndexNeedInsert); 166 167 // It's not possible to create the INIT_UNDEF when there is no register 168 // class associated for the subreg. This may happen for artificial subregs 169 // that are not directly addressable. 170 if (any_of(SubRegIndexNeedInsert, [&](unsigned Ind) -> bool { 171 return !TRI->getSubRegisterClass(TargetRegClass, Ind); 172 })) 173 continue; 174 175 Register LatestReg = Reg; 176 for (auto ind : SubRegIndexNeedInsert) { 177 Changed = true; 178 const TargetRegisterClass *SubRegClass = 179 TRI->getSubRegisterClass(TargetRegClass, ind); 180 Register TmpInitSubReg = MRI->createVirtualRegister(SubRegClass); 181 LLVM_DEBUG(dbgs() << "Register Class ID" << SubRegClass->getID() << "\n"); 182 BuildMI(*MI.getParent(), &MI, MI.getDebugLoc(), 183 TII->get(TargetOpcode::INIT_UNDEF), TmpInitSubReg); 184 Register NewReg = MRI->createVirtualRegister(TargetRegClass); 185 BuildMI(*MI.getParent(), &MI, MI.getDebugLoc(), 186 TII->get(TargetOpcode::INSERT_SUBREG), NewReg) 187 .addReg(LatestReg) 188 .addReg(TmpInitSubReg) 189 .addImm(ind); 190 LatestReg = NewReg; 191 } 192 193 UseMO.setReg(LatestReg); 194 } 195 196 return Changed; 197 } 198 199 bool InitUndef::fixupIllOperand(MachineInstr *MI, MachineOperand &MO) { 200 201 LLVM_DEBUG( 202 dbgs() << "Emitting PseudoInitUndef Instruction for implicit register " 203 << printReg(MO.getReg()) << '\n'); 204 205 const TargetRegisterClass *TargetRegClass = MRI->getRegClass(MO.getReg()); 206 LLVM_DEBUG(dbgs() << "Register Class ID" << TargetRegClass->getID() << "\n"); 207 Register NewReg = MRI->createVirtualRegister(TargetRegClass); 208 BuildMI(*MI->getParent(), MI, MI->getDebugLoc(), 209 TII->get(TargetOpcode::INIT_UNDEF), NewReg); 210 MO.setReg(NewReg); 211 if (MO.isUndef()) 212 MO.setIsUndef(false); 213 return true; 214 } 215 216 bool InitUndef::processBasicBlock(MachineFunction &MF, MachineBasicBlock &MBB, 217 const DeadLaneDetector *DLD) { 218 bool Changed = false; 219 for (MachineBasicBlock::iterator I = MBB.begin(); I != MBB.end(); ++I) { 220 MachineInstr &MI = *I; 221 222 // If we used NoReg to represent the passthru, switch this back to being 223 // an IMPLICIT_DEF before TwoAddressInstructions. 224 unsigned UseOpIdx; 225 if (MI.getNumDefs() != 0 && MI.isRegTiedToUseOperand(0, &UseOpIdx)) { 226 MachineOperand &UseMO = MI.getOperand(UseOpIdx); 227 if (UseMO.getReg() == MCRegister::NoRegister) { 228 const TargetRegisterClass *RC = 229 TII->getRegClass(MI.getDesc(), UseOpIdx, TRI, MF); 230 Register NewDest = MRI->createVirtualRegister(RC); 231 // We don't have a way to update dead lanes, so keep track of the 232 // new register so that we avoid querying it later. 233 NewRegs.insert(NewDest); 234 BuildMI(MBB, I, I->getDebugLoc(), TII->get(TargetOpcode::IMPLICIT_DEF), 235 NewDest); 236 UseMO.setReg(NewDest); 237 Changed = true; 238 } 239 } 240 241 if (isEarlyClobberMI(MI)) { 242 if (MRI->subRegLivenessEnabled()) 243 Changed |= handleSubReg(MF, MI, *DLD); 244 Changed |= handleReg(&MI); 245 } 246 } 247 return Changed; 248 } 249 250 bool InitUndef::runOnMachineFunction(MachineFunction &MF) { 251 ST = &MF.getSubtarget(); 252 253 // The pass is only needed if early-clobber defs and undef ops cannot be 254 // allocated to the same register. 255 if (!ST->requiresDisjointEarlyClobberAndUndef()) 256 return false; 257 258 MRI = &MF.getRegInfo(); 259 TII = ST->getInstrInfo(); 260 TRI = MRI->getTargetRegisterInfo(); 261 262 bool Changed = false; 263 std::unique_ptr<DeadLaneDetector> DLD; 264 if (MRI->subRegLivenessEnabled()) { 265 DLD = std::make_unique<DeadLaneDetector>(MRI, TRI); 266 DLD->computeSubRegisterLaneBitInfo(); 267 } 268 269 for (MachineBasicBlock &BB : MF) 270 Changed |= processBasicBlock(MF, BB, DLD.get()); 271 272 for (auto *DeadMI : DeadInsts) 273 DeadMI->eraseFromParent(); 274 DeadInsts.clear(); 275 NewRegs.clear(); 276 277 return Changed; 278 } 279