584 lines · cpp
1//===- DetectDeadLanes.cpp - SubRegister Lane Usage Analysis --*- C++ -*---===//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/// \file10/// Analysis that tracks defined/used subregister lanes across COPY instructions11/// and instructions that get lowered to a COPY (PHI, REG_SEQUENCE,12/// INSERT_SUBREG, EXTRACT_SUBREG).13/// The information is used to detect dead definitions and the usage of14/// (completely) undefined values and mark the operands as such.15/// This pass is necessary because the dead/undef status is not obvious anymore16/// when subregisters are involved.17///18/// Example:19/// %0 = some definition20/// %1 = IMPLICIT_DEF21/// %2 = REG_SEQUENCE %0, sub0, %1, sub122/// %3 = EXTRACT_SUBREG %2, sub123/// = use %324/// The %0 definition is dead and %3 contains an undefined value.25//26//===----------------------------------------------------------------------===//27 28#include "llvm/CodeGen/DetectDeadLanes.h"29#include "llvm/CodeGen/MachineFunctionPass.h"30#include "llvm/CodeGen/MachineRegisterInfo.h"31#include "llvm/CodeGen/TargetRegisterInfo.h"32#include "llvm/InitializePasses.h"33#include "llvm/Pass.h"34#include "llvm/Support/Debug.h"35#include "llvm/Support/raw_ostream.h"36 37using namespace llvm;38 39#define DEBUG_TYPE "detect-dead-lanes"40 41DeadLaneDetector::DeadLaneDetector(const MachineRegisterInfo *MRI,42 const TargetRegisterInfo *TRI)43 : MRI(MRI), TRI(TRI) {44 unsigned NumVirtRegs = MRI->getNumVirtRegs();45 VRegInfos = std::unique_ptr<VRegInfo[]>(new VRegInfo[NumVirtRegs]);46 WorklistMembers.resize(NumVirtRegs);47 DefinedByCopy.resize(NumVirtRegs);48}49 50/// Returns true if \p MI will get lowered to a series of COPY instructions.51/// We call this a COPY-like instruction.52static bool lowersToCopies(const MachineInstr &MI) {53 // Note: We could support instructions with MCInstrDesc::isRegSequenceLike(),54 // isExtractSubRegLike(), isInsertSubregLike() in the future even though they55 // are not lowered to a COPY.56 switch (MI.getOpcode()) {57 case TargetOpcode::COPY:58 case TargetOpcode::PHI:59 case TargetOpcode::INSERT_SUBREG:60 case TargetOpcode::REG_SEQUENCE:61 case TargetOpcode::EXTRACT_SUBREG:62 return true;63 }64 return false;65}66 67static bool isCrossCopy(const MachineRegisterInfo &MRI,68 const MachineInstr &MI,69 const TargetRegisterClass *DstRC,70 const MachineOperand &MO) {71 assert(lowersToCopies(MI));72 Register SrcReg = MO.getReg();73 const TargetRegisterClass *SrcRC = MRI.getRegClass(SrcReg);74 if (DstRC == SrcRC)75 return false;76 77 unsigned SrcSubIdx = MO.getSubReg();78 79 const TargetRegisterInfo &TRI = *MRI.getTargetRegisterInfo();80 unsigned DstSubIdx = 0;81 switch (MI.getOpcode()) {82 case TargetOpcode::INSERT_SUBREG:83 if (MO.getOperandNo() == 2)84 DstSubIdx = MI.getOperand(3).getImm();85 break;86 case TargetOpcode::REG_SEQUENCE: {87 unsigned OpNum = MO.getOperandNo();88 DstSubIdx = MI.getOperand(OpNum+1).getImm();89 break;90 }91 case TargetOpcode::EXTRACT_SUBREG: {92 unsigned SubReg = MI.getOperand(2).getImm();93 SrcSubIdx = TRI.composeSubRegIndices(SubReg, SrcSubIdx);94 }95 }96 97 unsigned PreA, PreB; // Unused.98 if (SrcSubIdx && DstSubIdx)99 return !TRI.getCommonSuperRegClass(SrcRC, SrcSubIdx, DstRC, DstSubIdx, PreA,100 PreB);101 if (SrcSubIdx)102 return !TRI.getMatchingSuperRegClass(SrcRC, DstRC, SrcSubIdx);103 if (DstSubIdx)104 return !TRI.getMatchingSuperRegClass(DstRC, SrcRC, DstSubIdx);105 return !TRI.getCommonSubClass(SrcRC, DstRC);106}107 108void DeadLaneDetector::addUsedLanesOnOperand(const MachineOperand &MO,109 LaneBitmask UsedLanes) {110 if (!MO.readsReg())111 return;112 Register MOReg = MO.getReg();113 if (!MOReg.isVirtual())114 return;115 116 unsigned MOSubReg = MO.getSubReg();117 if (MOSubReg != 0)118 UsedLanes = TRI->composeSubRegIndexLaneMask(MOSubReg, UsedLanes);119 UsedLanes &= MRI->getMaxLaneMaskForVReg(MOReg);120 121 unsigned MORegIdx = MOReg.virtRegIndex();122 DeadLaneDetector::VRegInfo &MORegInfo = VRegInfos[MORegIdx];123 LaneBitmask PrevUsedLanes = MORegInfo.UsedLanes;124 // Any change at all?125 if ((UsedLanes & ~PrevUsedLanes).none())126 return;127 128 // Set UsedLanes and remember instruction for further propagation.129 MORegInfo.UsedLanes = PrevUsedLanes | UsedLanes;130 if (DefinedByCopy.test(MORegIdx))131 PutInWorklist(MORegIdx);132}133 134void DeadLaneDetector::transferUsedLanesStep(const MachineInstr &MI,135 LaneBitmask UsedLanes) {136 for (const MachineOperand &MO : MI.uses()) {137 if (!MO.isReg() || !MO.getReg().isVirtual())138 continue;139 LaneBitmask UsedOnMO = transferUsedLanes(MI, UsedLanes, MO);140 addUsedLanesOnOperand(MO, UsedOnMO);141 }142}143 144LaneBitmask145DeadLaneDetector::transferUsedLanes(const MachineInstr &MI,146 LaneBitmask UsedLanes,147 const MachineOperand &MO) const {148 unsigned OpNum = MO.getOperandNo();149 assert(lowersToCopies(MI) &&150 DefinedByCopy[MI.getOperand(0).getReg().virtRegIndex()]);151 152 switch (MI.getOpcode()) {153 case TargetOpcode::COPY:154 case TargetOpcode::PHI:155 return UsedLanes;156 case TargetOpcode::REG_SEQUENCE: {157 assert(OpNum % 2 == 1);158 unsigned SubIdx = MI.getOperand(OpNum + 1).getImm();159 return TRI->reverseComposeSubRegIndexLaneMask(SubIdx, UsedLanes);160 }161 case TargetOpcode::INSERT_SUBREG: {162 unsigned SubIdx = MI.getOperand(3).getImm();163 LaneBitmask MO2UsedLanes =164 TRI->reverseComposeSubRegIndexLaneMask(SubIdx, UsedLanes);165 if (OpNum == 2)166 return MO2UsedLanes;167 168 const MachineOperand &Def = MI.getOperand(0);169 Register DefReg = Def.getReg();170 const TargetRegisterClass *RC = MRI->getRegClass(DefReg);171 LaneBitmask MO1UsedLanes;172 if (RC->CoveredBySubRegs)173 MO1UsedLanes = UsedLanes & ~TRI->getSubRegIndexLaneMask(SubIdx);174 else175 MO1UsedLanes = RC->LaneMask;176 177 assert(OpNum == 1);178 return MO1UsedLanes;179 }180 case TargetOpcode::EXTRACT_SUBREG: {181 assert(OpNum == 1);182 unsigned SubIdx = MI.getOperand(2).getImm();183 return TRI->composeSubRegIndexLaneMask(SubIdx, UsedLanes);184 }185 default:186 llvm_unreachable("function must be called with COPY-like instruction");187 }188}189 190void DeadLaneDetector::transferDefinedLanesStep(const MachineOperand &Use,191 LaneBitmask DefinedLanes) {192 if (!Use.readsReg())193 return;194 // Check whether the operand writes a vreg and is part of a COPY-like195 // instruction.196 const MachineInstr &MI = *Use.getParent();197 if (MI.getDesc().getNumDefs() != 1)198 return;199 // FIXME: PATCHPOINT instructions announce a Def that does not always exist,200 // they really need to be modeled differently!201 if (MI.getOpcode() == TargetOpcode::PATCHPOINT)202 return;203 const MachineOperand &Def = *MI.defs().begin();204 Register DefReg = Def.getReg();205 if (!DefReg.isVirtual())206 return;207 unsigned DefRegIdx = DefReg.virtRegIndex();208 if (!DefinedByCopy.test(DefRegIdx))209 return;210 211 unsigned OpNum = Use.getOperandNo();212 DefinedLanes =213 TRI->reverseComposeSubRegIndexLaneMask(Use.getSubReg(), DefinedLanes);214 DefinedLanes = transferDefinedLanes(Def, OpNum, DefinedLanes);215 216 VRegInfo &RegInfo = VRegInfos[DefRegIdx];217 LaneBitmask PrevDefinedLanes = RegInfo.DefinedLanes;218 // Any change at all?219 if ((DefinedLanes & ~PrevDefinedLanes).none())220 return;221 222 RegInfo.DefinedLanes = PrevDefinedLanes | DefinedLanes;223 PutInWorklist(DefRegIdx);224}225 226LaneBitmask DeadLaneDetector::transferDefinedLanes(227 const MachineOperand &Def, unsigned OpNum, LaneBitmask DefinedLanes) const {228 const MachineInstr &MI = *Def.getParent();229 // Translate DefinedLanes if necessary.230 switch (MI.getOpcode()) {231 case TargetOpcode::REG_SEQUENCE: {232 unsigned SubIdx = MI.getOperand(OpNum + 1).getImm();233 DefinedLanes = TRI->composeSubRegIndexLaneMask(SubIdx, DefinedLanes);234 DefinedLanes &= TRI->getSubRegIndexLaneMask(SubIdx);235 break;236 }237 case TargetOpcode::INSERT_SUBREG: {238 unsigned SubIdx = MI.getOperand(3).getImm();239 if (OpNum == 2) {240 DefinedLanes = TRI->composeSubRegIndexLaneMask(SubIdx, DefinedLanes);241 DefinedLanes &= TRI->getSubRegIndexLaneMask(SubIdx);242 } else {243 assert(OpNum == 1 && "INSERT_SUBREG must have two operands");244 // Ignore lanes defined by operand 2.245 DefinedLanes &= ~TRI->getSubRegIndexLaneMask(SubIdx);246 }247 break;248 }249 case TargetOpcode::EXTRACT_SUBREG: {250 unsigned SubIdx = MI.getOperand(2).getImm();251 assert(OpNum == 1 && "EXTRACT_SUBREG must have one register operand only");252 DefinedLanes = TRI->reverseComposeSubRegIndexLaneMask(SubIdx, DefinedLanes);253 break;254 }255 case TargetOpcode::COPY:256 case TargetOpcode::PHI:257 break;258 default:259 llvm_unreachable("function must be called with COPY-like instruction");260 }261 262 assert(Def.getSubReg() == 0 &&263 "Should not have subregister defs in machine SSA phase");264 DefinedLanes &= MRI->getMaxLaneMaskForVReg(Def.getReg());265 return DefinedLanes;266}267 268LaneBitmask DeadLaneDetector::determineInitialDefinedLanes(Register Reg) {269 // Live-In or unused registers have no definition but are considered fully270 // defined.271 if (!MRI->hasOneDef(Reg))272 return LaneBitmask::getAll();273 274 const MachineOperand &Def = *MRI->def_begin(Reg);275 const MachineInstr &DefMI = *Def.getParent();276 if (lowersToCopies(DefMI)) {277 // Start optimisatically with no used or defined lanes for copy278 // instructions. The following dataflow analysis will add more bits.279 unsigned RegIdx = Register(Reg).virtRegIndex();280 DefinedByCopy.set(RegIdx);281 PutInWorklist(RegIdx);282 283 if (Def.isDead())284 return LaneBitmask::getNone();285 286 // COPY/PHI can copy across unrelated register classes (example: float/int)287 // with incompatible subregister structure. Do not include these in the288 // dataflow analysis since we cannot transfer lanemasks in a meaningful way.289 const TargetRegisterClass *DefRC = MRI->getRegClass(Reg);290 291 // Determine initially DefinedLanes.292 LaneBitmask DefinedLanes;293 for (const MachineOperand &MO : DefMI.uses()) {294 if (!MO.isReg() || !MO.readsReg())295 continue;296 Register MOReg = MO.getReg();297 if (!MOReg)298 continue;299 300 LaneBitmask MODefinedLanes;301 if (MOReg.isPhysical()) {302 MODefinedLanes = LaneBitmask::getAll();303 } else if (isCrossCopy(*MRI, DefMI, DefRC, MO)) {304 MODefinedLanes = LaneBitmask::getAll();305 } else {306 assert(MOReg.isVirtual());307 if (MRI->hasOneDef(MOReg)) {308 const MachineOperand &MODef = *MRI->def_begin(MOReg);309 const MachineInstr &MODefMI = *MODef.getParent();310 // Bits from copy-like operations will be added later.311 if (lowersToCopies(MODefMI) || MODefMI.isImplicitDef())312 continue;313 }314 unsigned MOSubReg = MO.getSubReg();315 MODefinedLanes = MRI->getMaxLaneMaskForVReg(MOReg);316 MODefinedLanes = TRI->reverseComposeSubRegIndexLaneMask(317 MOSubReg, MODefinedLanes);318 }319 320 unsigned OpNum = MO.getOperandNo();321 DefinedLanes |= transferDefinedLanes(Def, OpNum, MODefinedLanes);322 }323 return DefinedLanes;324 }325 if (DefMI.isImplicitDef() || Def.isDead())326 return LaneBitmask::getNone();327 328 assert(Def.getSubReg() == 0 &&329 "Should not have subregister defs in machine SSA phase");330 return MRI->getMaxLaneMaskForVReg(Reg);331}332 333LaneBitmask DeadLaneDetector::determineInitialUsedLanes(Register Reg) {334 LaneBitmask UsedLanes = LaneBitmask::getNone();335 for (const MachineOperand &MO : MRI->use_nodbg_operands(Reg)) {336 if (!MO.readsReg())337 continue;338 339 const MachineInstr &UseMI = *MO.getParent();340 if (UseMI.isKill())341 continue;342 343 unsigned SubReg = MO.getSubReg();344 if (lowersToCopies(UseMI)) {345 assert(UseMI.getDesc().getNumDefs() == 1);346 const MachineOperand &Def = *UseMI.defs().begin();347 Register DefReg = Def.getReg();348 // The used lanes of COPY-like instruction operands are determined by the349 // following dataflow analysis.350 if (DefReg.isVirtual()) {351 // But ignore copies across incompatible register classes.352 bool CrossCopy = false;353 if (lowersToCopies(UseMI)) {354 const TargetRegisterClass *DstRC = MRI->getRegClass(DefReg);355 CrossCopy = isCrossCopy(*MRI, UseMI, DstRC, MO);356 if (CrossCopy)357 LLVM_DEBUG(dbgs() << "Copy across incompatible classes: " << UseMI);358 }359 360 if (!CrossCopy)361 continue;362 }363 }364 365 // Shortcut: All lanes are used.366 if (SubReg == 0)367 return MRI->getMaxLaneMaskForVReg(Reg);368 369 UsedLanes |= TRI->getSubRegIndexLaneMask(SubReg);370 }371 return UsedLanes;372}373 374namespace {375 376class DetectDeadLanes {377public:378 bool run(MachineFunction &MF);379 380private:381 /// update the operand status.382 /// The first return value shows whether MF been changed.383 /// The second return value indicates we need to call384 /// DeadLaneDetector::computeSubRegisterLaneBitInfo and this function again385 /// to propagate changes.386 std::pair<bool, bool>387 modifySubRegisterOperandStatus(const DeadLaneDetector &DLD,388 MachineFunction &MF);389 390 bool isUndefRegAtInput(const MachineOperand &MO,391 const DeadLaneDetector::VRegInfo &RegInfo) const;392 393 bool isUndefInput(const DeadLaneDetector &DLD, const MachineOperand &MO,394 bool *CrossCopy) const;395 396 const MachineRegisterInfo *MRI = nullptr;397 const TargetRegisterInfo *TRI = nullptr;398};399 400struct DetectDeadLanesLegacy : public MachineFunctionPass {401 static char ID;402 DetectDeadLanesLegacy() : MachineFunctionPass(ID) {}403 404 StringRef getPassName() const override { return "Detect Dead Lanes"; }405 406 void getAnalysisUsage(AnalysisUsage &AU) const override {407 AU.setPreservesCFG();408 MachineFunctionPass::getAnalysisUsage(AU);409 }410 411 bool runOnMachineFunction(MachineFunction &MF) override {412 return DetectDeadLanes().run(MF);413 }414};415 416} // end anonymous namespace417 418char DetectDeadLanesLegacy::ID = 0;419char &llvm::DetectDeadLanesID = DetectDeadLanesLegacy::ID;420 421INITIALIZE_PASS(DetectDeadLanesLegacy, DEBUG_TYPE, "Detect Dead Lanes", false,422 false)423 424bool DetectDeadLanes::isUndefRegAtInput(425 const MachineOperand &MO, const DeadLaneDetector::VRegInfo &RegInfo) const {426 unsigned SubReg = MO.getSubReg();427 LaneBitmask Mask = TRI->getSubRegIndexLaneMask(SubReg);428 return (RegInfo.DefinedLanes & RegInfo.UsedLanes & Mask).none();429}430 431bool DetectDeadLanes::isUndefInput(const DeadLaneDetector &DLD,432 const MachineOperand &MO,433 bool *CrossCopy) const {434 if (!MO.isUse())435 return false;436 const MachineInstr &MI = *MO.getParent();437 if (!lowersToCopies(MI))438 return false;439 const MachineOperand &Def = MI.getOperand(0);440 Register DefReg = Def.getReg();441 if (!DefReg.isVirtual())442 return false;443 unsigned DefRegIdx = DefReg.virtRegIndex();444 if (!DLD.isDefinedByCopy(DefRegIdx))445 return false;446 447 const DeadLaneDetector::VRegInfo &DefRegInfo = DLD.getVRegInfo(DefRegIdx);448 LaneBitmask UsedLanes = DLD.transferUsedLanes(MI, DefRegInfo.UsedLanes, MO);449 if (UsedLanes.any())450 return false;451 452 Register MOReg = MO.getReg();453 if (MOReg.isVirtual()) {454 const TargetRegisterClass *DstRC = MRI->getRegClass(DefReg);455 *CrossCopy = isCrossCopy(*MRI, MI, DstRC, MO);456 }457 return true;458}459 460void DeadLaneDetector::computeSubRegisterLaneBitInfo() {461 // First pass: Populate defs/uses of vregs with initial values462 unsigned NumVirtRegs = MRI->getNumVirtRegs();463 for (unsigned RegIdx = 0; RegIdx < NumVirtRegs; ++RegIdx) {464 Register Reg = Register::index2VirtReg(RegIdx);465 466 // Determine used/defined lanes and add copy instructions to worklist.467 VRegInfo &Info = VRegInfos[RegIdx];468 Info.DefinedLanes = determineInitialDefinedLanes(Reg);469 Info.UsedLanes = determineInitialUsedLanes(Reg);470 }471 472 // Iterate as long as defined lanes/used lanes keep changing.473 while (!Worklist.empty()) {474 unsigned RegIdx = Worklist.front();475 Worklist.pop_front();476 WorklistMembers.reset(RegIdx);477 VRegInfo &Info = VRegInfos[RegIdx];478 Register Reg = Register::index2VirtReg(RegIdx);479 480 // Transfer UsedLanes to operands of DefMI (backwards dataflow).481 MachineOperand &Def = *MRI->def_begin(Reg);482 const MachineInstr &MI = *Def.getParent();483 transferUsedLanesStep(MI, Info.UsedLanes);484 // Transfer DefinedLanes to users of Reg (forward dataflow).485 for (const MachineOperand &MO : MRI->use_nodbg_operands(Reg))486 transferDefinedLanesStep(MO, Info.DefinedLanes);487 }488 489 LLVM_DEBUG({490 dbgs() << "Defined/Used lanes:\n";491 for (unsigned RegIdx = 0; RegIdx < NumVirtRegs; ++RegIdx) {492 Register Reg = Register::index2VirtReg(RegIdx);493 const VRegInfo &Info = VRegInfos[RegIdx];494 dbgs() << printReg(Reg, nullptr)495 << " Used: " << PrintLaneMask(Info.UsedLanes)496 << " Def: " << PrintLaneMask(Info.DefinedLanes) << '\n';497 }498 dbgs() << "\n";499 });500}501 502std::pair<bool, bool>503DetectDeadLanes::modifySubRegisterOperandStatus(const DeadLaneDetector &DLD,504 MachineFunction &MF) {505 bool Changed = false;506 bool Again = false;507 // Mark operands as dead/unused.508 for (MachineBasicBlock &MBB : MF) {509 for (MachineInstr &MI : MBB) {510 for (MachineOperand &MO : MI.operands()) {511 if (!MO.isReg())512 continue;513 Register Reg = MO.getReg();514 if (!Reg.isVirtual())515 continue;516 unsigned RegIdx = Reg.virtRegIndex();517 const DeadLaneDetector::VRegInfo &RegInfo = DLD.getVRegInfo(RegIdx);518 if (MO.isDef() && !MO.isDead() && RegInfo.UsedLanes.none()) {519 LLVM_DEBUG(dbgs()520 << "Marking operand '" << MO << "' as dead in " << MI);521 MO.setIsDead();522 Changed = true;523 }524 if (MO.readsReg()) {525 bool CrossCopy = false;526 if (isUndefRegAtInput(MO, RegInfo)) {527 LLVM_DEBUG(dbgs()528 << "Marking operand '" << MO << "' as undef in " << MI);529 MO.setIsUndef();530 Changed = true;531 } else if (isUndefInput(DLD, MO, &CrossCopy)) {532 LLVM_DEBUG(dbgs()533 << "Marking operand '" << MO << "' as undef in " << MI);534 MO.setIsUndef();535 Changed = true;536 if (CrossCopy)537 Again = true;538 }539 }540 }541 }542 }543 544 return std::make_pair(Changed, Again);545}546 547PreservedAnalyses548DetectDeadLanesPass::run(MachineFunction &MF,549 MachineFunctionAnalysisManager &MFAM) {550 if (!DetectDeadLanes().run(MF))551 return PreservedAnalyses::all();552 auto PA = getMachineFunctionPassPreservedAnalyses();553 PA.preserveSet<CFGAnalyses>();554 return PA;555}556 557bool DetectDeadLanes::run(MachineFunction &MF) {558 // Don't bother if we won't track subregister liveness later. This pass is559 // required for correctness if subregister liveness is enabled because the560 // register coalescer cannot deal with hidden dead defs. However without561 // subregister liveness enabled, the expected benefits of this pass are small562 // so we safe the compile time.563 MRI = &MF.getRegInfo();564 if (!MRI->subRegLivenessEnabled()) {565 LLVM_DEBUG(dbgs() << "Skipping Detect dead lanes pass\n");566 return false;567 }568 569 TRI = MRI->getTargetRegisterInfo();570 571 DeadLaneDetector DLD(MRI, TRI);572 573 bool Changed = false;574 bool Again;575 do {576 DLD.computeSubRegisterLaneBitInfo();577 bool LocalChanged;578 std::tie(LocalChanged, Again) = modifySubRegisterOperandStatus(DLD, MF);579 Changed |= LocalChanged;580 } while (Again);581 582 return Changed;583}584