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(*MRI, TargetRegClass, NeedDef, 165 SubRegIndexNeedInsert); 166 167 Register LatestReg = Reg; 168 for (auto ind : SubRegIndexNeedInsert) { 169 Changed = true; 170 const TargetRegisterClass *SubRegClass = 171 TRI->getSubRegisterClass(TargetRegClass, ind); 172 Register TmpInitSubReg = MRI->createVirtualRegister(SubRegClass); 173 LLVM_DEBUG(dbgs() << "Register Class ID" << SubRegClass->getID() << "\n"); 174 BuildMI(*MI.getParent(), &MI, MI.getDebugLoc(), 175 TII->get(TargetOpcode::INIT_UNDEF), TmpInitSubReg); 176 Register NewReg = MRI->createVirtualRegister(TargetRegClass); 177 BuildMI(*MI.getParent(), &MI, MI.getDebugLoc(), 178 TII->get(TargetOpcode::INSERT_SUBREG), NewReg) 179 .addReg(LatestReg) 180 .addReg(TmpInitSubReg) 181 .addImm(ind); 182 LatestReg = NewReg; 183 } 184 185 UseMO.setReg(LatestReg); 186 } 187 188 return Changed; 189 } 190 191 bool InitUndef::fixupIllOperand(MachineInstr *MI, MachineOperand &MO) { 192 193 LLVM_DEBUG( 194 dbgs() << "Emitting PseudoInitUndef Instruction for implicit register " 195 << printReg(MO.getReg()) << '\n'); 196 197 const TargetRegisterClass *TargetRegClass = MRI->getRegClass(MO.getReg()); 198 LLVM_DEBUG(dbgs() << "Register Class ID" << TargetRegClass->getID() << "\n"); 199 Register NewReg = MRI->createVirtualRegister(TargetRegClass); 200 BuildMI(*MI->getParent(), MI, MI->getDebugLoc(), 201 TII->get(TargetOpcode::INIT_UNDEF), NewReg); 202 MO.setReg(NewReg); 203 if (MO.isUndef()) 204 MO.setIsUndef(false); 205 return true; 206 } 207 208 bool InitUndef::processBasicBlock(MachineFunction &MF, MachineBasicBlock &MBB, 209 const DeadLaneDetector *DLD) { 210 bool Changed = false; 211 for (MachineBasicBlock::iterator I = MBB.begin(); I != MBB.end(); ++I) { 212 MachineInstr &MI = *I; 213 214 // If we used NoReg to represent the passthru, switch this back to being 215 // an IMPLICIT_DEF before TwoAddressInstructions. 216 unsigned UseOpIdx; 217 if (MI.getNumDefs() != 0 && MI.isRegTiedToUseOperand(0, &UseOpIdx)) { 218 MachineOperand &UseMO = MI.getOperand(UseOpIdx); 219 if (UseMO.getReg() == MCRegister::NoRegister) { 220 const TargetRegisterClass *RC = 221 TII->getRegClass(MI.getDesc(), UseOpIdx, TRI, MF); 222 Register NewDest = MRI->createVirtualRegister(RC); 223 // We don't have a way to update dead lanes, so keep track of the 224 // new register so that we avoid querying it later. 225 NewRegs.insert(NewDest); 226 BuildMI(MBB, I, I->getDebugLoc(), TII->get(TargetOpcode::IMPLICIT_DEF), 227 NewDest); 228 UseMO.setReg(NewDest); 229 Changed = true; 230 } 231 } 232 233 if (isEarlyClobberMI(MI)) { 234 if (MRI->subRegLivenessEnabled()) 235 Changed |= handleSubReg(MF, MI, *DLD); 236 Changed |= handleReg(&MI); 237 } 238 } 239 return Changed; 240 } 241 242 bool InitUndef::runOnMachineFunction(MachineFunction &MF) { 243 ST = &MF.getSubtarget(); 244 245 // The pass is only needed if early-clobber defs and undef ops cannot be 246 // allocated to the same register. 247 if (!ST->requiresDisjointEarlyClobberAndUndef()) 248 return false; 249 250 MRI = &MF.getRegInfo(); 251 TII = ST->getInstrInfo(); 252 TRI = MRI->getTargetRegisterInfo(); 253 254 bool Changed = false; 255 std::unique_ptr<DeadLaneDetector> DLD; 256 if (MRI->subRegLivenessEnabled()) { 257 DLD = std::make_unique<DeadLaneDetector>(MRI, TRI); 258 DLD->computeSubRegisterLaneBitInfo(); 259 } 260 261 for (MachineBasicBlock &BB : MF) 262 Changed |= processBasicBlock(MF, BB, DLD.get()); 263 264 for (auto *DeadMI : DeadInsts) 265 DeadMI->eraseFromParent(); 266 DeadInsts.clear(); 267 NewRegs.clear(); 268 269 return Changed; 270 } 271