diff --git a/llvm/include/llvm/CodeGen/DetectDeadLanes.h b/llvm/include/llvm/CodeGen/DetectDeadLanes.h new file mode 100644 --- /dev/null +++ b/llvm/include/llvm/CodeGen/DetectDeadLanes.h @@ -0,0 +1,124 @@ +//===- DetectDeadLanes.h - SubRegister Lane Usage Analysis --*- C++ -*-----===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +/// \file +/// Analysis that tracks defined/used subregister lanes across COPY instructions +/// and instructions that get lowered to a COPY (PHI, REG_SEQUENCE, +/// INSERT_SUBREG, EXTRACT_SUBREG). +/// The information is used to detect dead definitions and the usage of +/// (completely) undefined values and mark the operands as such. +/// This pass is necessary because the dead/undef status is not obvious anymore +/// when subregisters are involved. +/// +/// Example: +/// %0 = some definition +/// %1 = IMPLICIT_DEF +/// %2 = REG_SEQUENCE %0, sub0, %1, sub1 +/// %3 = EXTRACT_SUBREG %2, sub1 +/// = use %3 +/// The %0 definition is dead and %3 contains an undefined value. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CODEGEN_DETECTDEADLANES_H +#define LLVM_CODEGEN_DETECTDEADLANES_H + +#include "llvm/ADT/BitVector.h" +#include "llvm/CodeGen/MachineFunctionPass.h" +#include "llvm/CodeGen/MachineRegisterInfo.h" +#include "llvm/CodeGen/TargetRegisterInfo.h" +#include "llvm/InitializePasses.h" +#include "llvm/Pass.h" +#include "llvm/Support/Debug.h" +#include "llvm/Support/raw_ostream.h" +#include + +using namespace llvm; + +/// Contains a bitmask of which lanes of a given virtual register are +/// defined and which ones are actually used. +struct VRegInfo { + LaneBitmask UsedLanes; + LaneBitmask DefinedLanes; +}; + +class DetectDeadLanes : public MachineFunctionPass { +public: + bool runOnMachineFunction(MachineFunction &MF) override; + + static char ID; + DetectDeadLanes() : MachineFunctionPass(ID) {} + + StringRef getPassName() const override { return "Detect Dead Lanes"; } + + void getAnalysisUsage(AnalysisUsage &AU) const override { + AU.setPreservesCFG(); + MachineFunctionPass::getAnalysisUsage(AU); + } + + // Provide the Used/undef LaneBit status for all virtual reigster. + bool getSubRegisterLaneBitInfo(MachineFunction &MF, VRegInfo *Info, + bool NeedSetUndef = false); + +private: + /// Add used lane bits on the register used by operand \p MO. This translates + /// the bitmask based on the operands subregister, and puts the register into + /// the worklist if any new bits were added. + void addUsedLanesOnOperand(const MachineOperand &MO, LaneBitmask UsedLanes); + + /// Given a bitmask \p UsedLanes for the used lanes on a def output of a + /// COPY-like instruction determine the lanes used on the use operands + /// and call addUsedLanesOnOperand() for them. + void transferUsedLanesStep(const MachineInstr &MI, LaneBitmask UsedLanes); + + /// Given a use regiser operand \p Use and a mask of defined lanes, check + /// if the operand belongs to a lowersToCopies() instruction, transfer the + /// mask to the def and put the instruction into the worklist. + void transferDefinedLanesStep(const MachineOperand &Use, + LaneBitmask DefinedLanes); + + /// Given a mask \p DefinedLanes of lanes defined at operand \p OpNum + /// of COPY-like instruction, determine which lanes are defined at the output + /// operand \p Def. + LaneBitmask transferDefinedLanes(const MachineOperand &Def, unsigned OpNum, + LaneBitmask DefinedLanes) const; + + /// Given a mask \p UsedLanes used from the output of instruction \p MI + /// determine which lanes are used from operand \p MO of this instruction. + LaneBitmask transferUsedLanes(const MachineInstr &MI, LaneBitmask UsedLanes, + const MachineOperand &MO) const; + + std::pair runOnce(MachineFunction &MF, bool NeedSetUndef = false); + + LaneBitmask determineInitialDefinedLanes(unsigned Reg); + LaneBitmask determineInitialUsedLanes(unsigned Reg); + + bool isUndefRegAtInput(const MachineOperand &MO, + const VRegInfo &RegInfo) const; + + bool isUndefInput(const MachineOperand &MO, bool *CrossCopy) const; + + void PutInWorklist(unsigned RegIdx) { + if (WorklistMembers.test(RegIdx)) + return; + WorklistMembers.set(RegIdx); + Worklist.push_back(RegIdx); + } + + const MachineRegisterInfo *MRI; + const TargetRegisterInfo *TRI; + VRegInfo *VRegInfos; + /// Worklist containing virtreg indexes. + std::deque Worklist; + BitVector WorklistMembers; + /// This bitvector is set for each vreg index where the vreg is defined + /// by an instruction where lowersToCopies()==true. + BitVector DefinedByCopy; +}; + +#endif // LLVM_CODEGEN_DETECTDEADLANES_H \ No newline at end of file diff --git a/llvm/lib/CodeGen/DetectDeadLanes.cpp b/llvm/lib/CodeGen/DetectDeadLanes.cpp --- a/llvm/lib/CodeGen/DetectDeadLanes.cpp +++ b/llvm/lib/CodeGen/DetectDeadLanes.cpp @@ -25,102 +25,12 @@ // //===----------------------------------------------------------------------===// -#include "llvm/ADT/BitVector.h" -#include "llvm/CodeGen/MachineFunctionPass.h" -#include "llvm/CodeGen/MachineRegisterInfo.h" -#include "llvm/CodeGen/TargetRegisterInfo.h" -#include "llvm/InitializePasses.h" -#include "llvm/Pass.h" -#include "llvm/Support/Debug.h" -#include "llvm/Support/raw_ostream.h" -#include +#include "llvm/CodeGen/DetectDeadLanes.h" using namespace llvm; #define DEBUG_TYPE "detect-dead-lanes" -namespace { - -/// Contains a bitmask of which lanes of a given virtual register are -/// defined and which ones are actually used. -struct VRegInfo { - LaneBitmask UsedLanes; - LaneBitmask DefinedLanes; -}; - -class DetectDeadLanes : public MachineFunctionPass { -public: - bool runOnMachineFunction(MachineFunction &MF) override; - - static char ID; - DetectDeadLanes() : MachineFunctionPass(ID) {} - - StringRef getPassName() const override { return "Detect Dead Lanes"; } - - void getAnalysisUsage(AnalysisUsage &AU) const override { - AU.setPreservesCFG(); - MachineFunctionPass::getAnalysisUsage(AU); - } - -private: - /// Add used lane bits on the register used by operand \p MO. This translates - /// the bitmask based on the operands subregister, and puts the register into - /// the worklist if any new bits were added. - void addUsedLanesOnOperand(const MachineOperand &MO, LaneBitmask UsedLanes); - - /// Given a bitmask \p UsedLanes for the used lanes on a def output of a - /// COPY-like instruction determine the lanes used on the use operands - /// and call addUsedLanesOnOperand() for them. - void transferUsedLanesStep(const MachineInstr &MI, LaneBitmask UsedLanes); - - /// Given a use regiser operand \p Use and a mask of defined lanes, check - /// if the operand belongs to a lowersToCopies() instruction, transfer the - /// mask to the def and put the instruction into the worklist. - void transferDefinedLanesStep(const MachineOperand &Use, - LaneBitmask DefinedLanes); - - /// Given a mask \p DefinedLanes of lanes defined at operand \p OpNum - /// of COPY-like instruction, determine which lanes are defined at the output - /// operand \p Def. - LaneBitmask transferDefinedLanes(const MachineOperand &Def, unsigned OpNum, - LaneBitmask DefinedLanes) const; - - /// Given a mask \p UsedLanes used from the output of instruction \p MI - /// determine which lanes are used from operand \p MO of this instruction. - LaneBitmask transferUsedLanes(const MachineInstr &MI, LaneBitmask UsedLanes, - const MachineOperand &MO) const; - - std::pair runOnce(MachineFunction &MF); - - LaneBitmask determineInitialDefinedLanes(unsigned Reg); - LaneBitmask determineInitialUsedLanes(unsigned Reg); - - bool isUndefRegAtInput(const MachineOperand &MO, - const VRegInfo &RegInfo) const; - - bool isUndefInput(const MachineOperand &MO, bool *CrossCopy) const; - - const MachineRegisterInfo *MRI; - const TargetRegisterInfo *TRI; - - void PutInWorklist(unsigned RegIdx) { - if (WorklistMembers.test(RegIdx)) - return; - WorklistMembers.set(RegIdx); - Worklist.push_back(RegIdx); - } - - VRegInfo *VRegInfos; - /// Worklist containing virtreg indexes. - std::deque Worklist; - BitVector WorklistMembers; - /// This bitvector is set for each vreg index where the vreg is defined - /// by an instruction where lowersToCopies()==true. - BitVector DefinedByCopy; -}; - -} // end anonymous namespace - char DetectDeadLanes::ID = 0; char &llvm::DetectDeadLanesID = DetectDeadLanes::ID; @@ -484,7 +394,8 @@ return true; } -std::pair DetectDeadLanes::runOnce(MachineFunction &MF) { +std::pair DetectDeadLanes::runOnce(MachineFunction &MF, + bool NeedSetUndef) { // First pass: Populate defs/uses of vregs with initial values unsigned NumVirtRegs = MRI->getNumVirtRegs(); for (unsigned RegIdx = 0; RegIdx < NumVirtRegs; ++RegIdx) { @@ -527,6 +438,9 @@ bool Changed = false; bool Again = false; + if (!NeedSetUndef) + return std::make_pair(Changed, Again); + // Mark operands as dead/unused. for (MachineBasicBlock &MBB : MF) { for (MachineInstr &MI : MBB) { @@ -567,12 +481,9 @@ return std::make_pair(Changed, Again); } -bool DetectDeadLanes::runOnMachineFunction(MachineFunction &MF) { - // Don't bother if we won't track subregister liveness later. This pass is - // required for correctness if subregister liveness is enabled because the - // register coalescer cannot deal with hidden dead defs. However without - // subregister liveness enabled, the expected benefits of this pass are small - // so we safe the compile time. +bool DetectDeadLanes::getSubRegisterLaneBitInfo(MachineFunction &MF, + VRegInfo *Info, + bool NeedSetUndef) { MRI = &MF.getRegInfo(); if (!MRI->subRegLivenessEnabled()) { LLVM_DEBUG(dbgs() << "Skipping Detect dead lanes pass\n"); @@ -582,7 +493,10 @@ TRI = MRI->getTargetRegisterInfo(); unsigned NumVirtRegs = MRI->getNumVirtRegs(); - VRegInfos = new VRegInfo[NumVirtRegs]; + if (Info == nullptr) + VRegInfos = new VRegInfo[NumVirtRegs]; + else + VRegInfos = Info; WorklistMembers.resize(NumVirtRegs); DefinedByCopy.resize(NumVirtRegs); @@ -590,12 +504,25 @@ bool Again; do { bool LocalChanged; - std::tie(LocalChanged, Again) = runOnce(MF); + std::tie(LocalChanged, Again) = runOnce(MF, NeedSetUndef); Changed |= LocalChanged; - } while(Again); + } while (Again); DefinedByCopy.clear(); WorklistMembers.clear(); - delete[] VRegInfos; + + if (Info == nullptr) + delete[] VRegInfos; + return Changed; } + +bool DetectDeadLanes::runOnMachineFunction(MachineFunction &MF) { + // Don't bother if we won't track subregister liveness later. This pass is + // required for correctness if subregister liveness is enabled because the + // register coalescer cannot deal with hidden dead defs. However without + // subregister liveness enabled, the expected benefits of this pass are small + // so we safe the compile time. + // bool Changed = false; + return getSubRegisterLaneBitInfo(MF, nullptr, true); +}