298 lines · 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-exception6//7//===----------------------------------------------------------------------===//8//9// This file implements a function pass that initializes undef value to10// temporary pseudo instruction to prevent register allocation resulting in a11// constraint violated result for the particular instruction. It also rewrites12// the NoReg tied operand back to an IMPLICIT_DEF.13//14// Certain instructions have register overlapping constraints, and15// will cause illegal instruction trap if violated, we use early clobber to16// model this constraint, but it can't prevent register allocator allocating17// same or overlapped if the input register is undef value, so convert18// IMPLICIT_DEF to temporary pseudo instruction and remove it later could19// prevent that happen, it's not best way to resolve this, and it might20// change the order of program or increase the register pressure, so ideally we21// 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 same25// issue due to the partial of register is undef. If we pseudoinit the whole26// register, then it will generate redundant COPY instruction. Currently, it27// will generate INSERT_SUBREG to make sure the whole register is occupied28// when program encounter operation that has early-clobber constraint.29//30//31// See also: https://github.com/llvm/llvm-project/issues/5015732//33// Additionally, this pass rewrites tied operands of instructions34// from NoReg to IMPLICIT_DEF. (Not that this is a non-overlapping set of35// operands to the above.) We use NoReg to side step a MachineCSE36// optimization quality problem but need to convert back before37// TwoAddressInstruction. See pr64282 for context.38//39//===----------------------------------------------------------------------===//40 41#include "llvm/CodeGen/InitUndef.h"42#include "llvm/ADT/SmallSet.h"43#include "llvm/ADT/SmallVector.h"44#include "llvm/CodeGen/DetectDeadLanes.h"45#include "llvm/CodeGen/MachineFunction.h"46#include "llvm/CodeGen/MachineFunctionPass.h"47#include "llvm/CodeGen/MachineRegisterInfo.h"48#include "llvm/CodeGen/TargetInstrInfo.h"49#include "llvm/CodeGen/TargetRegisterInfo.h"50#include "llvm/CodeGen/TargetSubtargetInfo.h"51#include "llvm/InitializePasses.h"52#include "llvm/MC/MCRegister.h"53#include "llvm/Pass.h"54#include "llvm/Support/Debug.h"55 56using namespace llvm;57 58#define DEBUG_TYPE "init-undef"59#define INIT_UNDEF_NAME "Init Undef Pass"60 61namespace {62 63class InitUndefLegacy : public MachineFunctionPass {64public:65 static char ID;66 67 InitUndefLegacy() : MachineFunctionPass(ID) {}68 69 bool runOnMachineFunction(MachineFunction &MF) override;70 71 void getAnalysisUsage(AnalysisUsage &AU) const override {72 AU.setPreservesCFG();73 MachineFunctionPass::getAnalysisUsage(AU);74 }75 76 StringRef getPassName() const override { return INIT_UNDEF_NAME; }77};78 79class InitUndef {80 const TargetInstrInfo *TII;81 MachineRegisterInfo *MRI;82 const TargetSubtargetInfo *ST;83 const TargetRegisterInfo *TRI;84 85 // Newly added vregs, assumed to be fully rewritten86 SmallSet<Register, 8> NewRegs;87 SmallVector<MachineInstr *, 8> DeadInsts;88 89public:90 bool run(MachineFunction &MF);91 92private:93 bool processBasicBlock(MachineFunction &MF, MachineBasicBlock &MBB,94 const DeadLaneDetector *DLD);95 bool handleSubReg(MachineFunction &MF, MachineInstr &MI,96 const DeadLaneDetector &DLD);97 bool fixupIllOperand(MachineInstr *MI, MachineOperand &MO);98 bool handleReg(MachineInstr *MI);99};100 101} // end anonymous namespace102 103char InitUndefLegacy::ID = 0;104INITIALIZE_PASS(InitUndefLegacy, DEBUG_TYPE, INIT_UNDEF_NAME, false, false)105char &llvm::InitUndefID = InitUndefLegacy::ID;106 107static bool isEarlyClobberMI(MachineInstr &MI) {108 return llvm::any_of(MI.all_defs(), [](const MachineOperand &DefMO) {109 return DefMO.isReg() && DefMO.isEarlyClobber();110 });111}112 113static bool findImplictDefMIFromReg(Register Reg, MachineRegisterInfo *MRI) {114 for (auto &DefMI : MRI->def_instructions(Reg)) {115 if (DefMI.getOpcode() == TargetOpcode::IMPLICIT_DEF)116 return true;117 }118 return false;119}120 121bool InitUndef::handleReg(MachineInstr *MI) {122 bool Changed = false;123 for (auto &UseMO : MI->uses()) {124 if (!UseMO.isReg())125 continue;126 if (UseMO.isTied())127 continue;128 if (!UseMO.getReg().isVirtual())129 continue;130 131 if (UseMO.isUndef() || findImplictDefMIFromReg(UseMO.getReg(), MRI))132 Changed |= fixupIllOperand(MI, UseMO);133 }134 return Changed;135}136 137bool InitUndef::handleSubReg(MachineFunction &MF, MachineInstr &MI,138 const DeadLaneDetector &DLD) {139 bool Changed = false;140 141 for (MachineOperand &UseMO : MI.uses()) {142 if (!UseMO.isReg())143 continue;144 if (!UseMO.getReg().isVirtual())145 continue;146 if (UseMO.isTied())147 continue;148 149 Register Reg = UseMO.getReg();150 if (NewRegs.count(Reg))151 continue;152 DeadLaneDetector::VRegInfo Info = DLD.getVRegInfo(Reg.virtRegIndex());153 154 if (Info.UsedLanes == Info.DefinedLanes)155 continue;156 157 const TargetRegisterClass *TargetRegClass = MRI->getRegClass(Reg);158 159 LaneBitmask NeedDef = Info.UsedLanes & ~Info.DefinedLanes;160 161 LLVM_DEBUG({162 dbgs() << "Instruction has undef subregister.\n";163 dbgs() << printReg(Reg, nullptr)164 << " Used: " << PrintLaneMask(Info.UsedLanes)165 << " Def: " << PrintLaneMask(Info.DefinedLanes)166 << " Need Def: " << PrintLaneMask(NeedDef) << "\n";167 });168 169 SmallVector<unsigned> SubRegIndexNeedInsert;170 TRI->getCoveringSubRegIndexes(TargetRegClass, NeedDef,171 SubRegIndexNeedInsert);172 173 // It's not possible to create the INIT_UNDEF when there is no register174 // class associated for the subreg. This may happen for artificial subregs175 // that are not directly addressable.176 if (any_of(SubRegIndexNeedInsert, [&](unsigned Ind) -> bool {177 return !TRI->getSubRegisterClass(TargetRegClass, Ind);178 }))179 continue;180 181 Register LatestReg = Reg;182 for (auto ind : SubRegIndexNeedInsert) {183 Changed = true;184 const TargetRegisterClass *SubRegClass =185 TRI->getSubRegisterClass(TargetRegClass, ind);186 Register TmpInitSubReg = MRI->createVirtualRegister(SubRegClass);187 LLVM_DEBUG(dbgs() << "Register Class ID" << SubRegClass->getID() << "\n");188 BuildMI(*MI.getParent(), &MI, MI.getDebugLoc(),189 TII->get(TargetOpcode::INIT_UNDEF), TmpInitSubReg);190 Register NewReg = MRI->createVirtualRegister(TargetRegClass);191 BuildMI(*MI.getParent(), &MI, MI.getDebugLoc(),192 TII->get(TargetOpcode::INSERT_SUBREG), NewReg)193 .addReg(LatestReg)194 .addReg(TmpInitSubReg)195 .addImm(ind);196 LatestReg = NewReg;197 }198 199 UseMO.setReg(LatestReg);200 }201 202 return Changed;203}204 205bool InitUndef::fixupIllOperand(MachineInstr *MI, MachineOperand &MO) {206 207 LLVM_DEBUG(208 dbgs() << "Emitting PseudoInitUndef Instruction for implicit register "209 << printReg(MO.getReg()) << '\n');210 211 const TargetRegisterClass *TargetRegClass = MRI->getRegClass(MO.getReg());212 LLVM_DEBUG(dbgs() << "Register Class ID" << TargetRegClass->getID() << "\n");213 Register NewReg = MRI->createVirtualRegister(TargetRegClass);214 BuildMI(*MI->getParent(), MI, MI->getDebugLoc(),215 TII->get(TargetOpcode::INIT_UNDEF), NewReg);216 MO.setReg(NewReg);217 if (MO.isUndef())218 MO.setIsUndef(false);219 return true;220}221 222bool InitUndef::processBasicBlock(MachineFunction &MF, MachineBasicBlock &MBB,223 const DeadLaneDetector *DLD) {224 bool Changed = false;225 for (MachineBasicBlock::iterator I = MBB.begin(); I != MBB.end(); ++I) {226 MachineInstr &MI = *I;227 228 // If we used NoReg to represent the passthru, switch this back to being229 // an IMPLICIT_DEF before TwoAddressInstructions.230 unsigned UseOpIdx;231 if (MI.getNumDefs() != 0 && MI.isRegTiedToUseOperand(0, &UseOpIdx)) {232 MachineOperand &UseMO = MI.getOperand(UseOpIdx);233 if (UseMO.getReg() == MCRegister::NoRegister) {234 const TargetRegisterClass *RC =235 TII->getRegClass(MI.getDesc(), UseOpIdx);236 Register NewDest = MRI->createVirtualRegister(RC);237 // We don't have a way to update dead lanes, so keep track of the238 // new register so that we avoid querying it later.239 NewRegs.insert(NewDest);240 BuildMI(MBB, I, I->getDebugLoc(), TII->get(TargetOpcode::IMPLICIT_DEF),241 NewDest);242 UseMO.setReg(NewDest);243 Changed = true;244 }245 }246 247 if (isEarlyClobberMI(MI)) {248 if (MRI->subRegLivenessEnabled())249 Changed |= handleSubReg(MF, MI, *DLD);250 Changed |= handleReg(&MI);251 }252 }253 return Changed;254}255 256bool InitUndefLegacy::runOnMachineFunction(MachineFunction &MF) {257 return InitUndef().run(MF);258}259 260PreservedAnalyses InitUndefPass::run(MachineFunction &MF,261 MachineFunctionAnalysisManager &MFAM) {262 if (!InitUndef().run(MF))263 return PreservedAnalyses::all();264 auto PA = getMachineFunctionPassPreservedAnalyses();265 PA.preserveSet<CFGAnalyses>();266 return PA;267}268 269bool InitUndef::run(MachineFunction &MF) {270 ST = &MF.getSubtarget();271 272 // The pass is only needed if early-clobber defs and undef ops cannot be273 // allocated to the same register.274 if (!ST->requiresDisjointEarlyClobberAndUndef())275 return false;276 277 MRI = &MF.getRegInfo();278 TII = ST->getInstrInfo();279 TRI = MRI->getTargetRegisterInfo();280 281 bool Changed = false;282 std::unique_ptr<DeadLaneDetector> DLD;283 if (MRI->subRegLivenessEnabled()) {284 DLD = std::make_unique<DeadLaneDetector>(MRI, TRI);285 DLD->computeSubRegisterLaneBitInfo();286 }287 288 for (MachineBasicBlock &BB : MF)289 Changed |= processBasicBlock(MF, BB, DLD.get());290 291 for (auto *DeadMI : DeadInsts)292 DeadMI->eraseFromParent();293 DeadInsts.clear();294 NewRegs.clear();295 296 return Changed;297}298