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,132 @@ +//===- 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. + /// Return true if MF has been changed. + 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; + + /// According to information from the \p DefinedLanes and the \p UsedLanes, + /// update the operand status. + /// The first return value shows whether MF been changed. + /// The second return value requests this function need run again. + std::pair modifySubRegisterOperandStatus(MachineFunction &MF); + + /// Update the \p DefinedLanes and the \p UsedLanes for all virtual registers. + void computeSubRegisterLaneBitInfo(); + + 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,7 @@ return true; } -std::pair DetectDeadLanes::runOnce(MachineFunction &MF) { +void DetectDeadLanes::computeSubRegisterLaneBitInfo() { // First pass: Populate defs/uses of vregs with initial values unsigned NumVirtRegs = MRI->getNumVirtRegs(); for (unsigned RegIdx = 0; RegIdx < NumVirtRegs; ++RegIdx) { @@ -524,7 +434,10 @@ } dbgs() << "\n"; }); +} +std::pair +DetectDeadLanes::modifySubRegisterOperandStatus(MachineFunction &MF) { bool Changed = false; bool Again = false; // Mark operands as dead/unused. @@ -567,35 +480,50 @@ 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"); - return false; - } - 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); + computeSubRegisterLaneBitInfo(); + bool Changed = false; - bool Again; - do { + bool Again = true; + while (NeedSetUndef && Again) { bool LocalChanged; - std::tie(LocalChanged, Again) = runOnce(MF); + std::tie(LocalChanged, Again) = modifySubRegisterOperandStatus(MF); + if (LocalChanged) + computeSubRegisterLaneBitInfo(); Changed |= LocalChanged; - } 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. + if (!MF.getRegInfo().subRegLivenessEnabled()) { + LLVM_DEBUG(dbgs() << "Skipping Detect dead lanes pass\n"); + return false; + } + return getSubRegisterLaneBitInfo(MF, nullptr, true); +}