Index: llvm/include/llvm/CodeGen/LivenessVerifier.h =================================================================== --- /dev/null +++ llvm/include/llvm/CodeGen/LivenessVerifier.h @@ -0,0 +1,159 @@ +//===- llvm/CodeGen/LivenessVerifier.h - Liveness verifier ------*- 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 +/// +/// Implement a basic register liveness tracking scheme which emphasizes +/// simplicity over speed. This is intended for verification and MIR tooling, +/// not codegen purposes. +/// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CODEGEN_LIVENESSVERIFIER_H +#define LLVM_CODEGEN_LIVENESSVERIFIER_H + +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/DenseSet.h" +#include "llvm/CodeGen/MachineFunction.h" +#include "llvm/CodeGen/TargetRegisterInfo.h" + +namespace llvm { + +class LiveRegTracker { +public: + using RegVector = SmallVector; + using RegMaskVector = SmallVector; + using RegSet = DenseSet; + using RegMap = DenseMap; + using BlockSet = SmallPtrSet; + + const MachineFunction *MF; + const TargetRegisterInfo *TRI; + const MachineRegisterInfo *MRI; + + BlockSet FunctionBlocks; + + BitVector regsReserved; + RegSet regsLive; + RegVector regsDefined, regsDead, regsKilled; + RegMaskVector regMasks; + + void clear() { + regsLive.clear(); + regsDefined.clear(); + regsDead.clear(); + regsKilled.clear(); + regMasks.clear(); + MBBInfoMap.clear(); + } + + struct BBInfo { + // Is this MBB reachable from the MF entry point? + bool reachable = false; + + // Vregs that must be live in because they are used without being + // defined. Map value is the user. vregsLiveIn doesn't include regs + // that only are used by PHI nodes. + RegMap vregsLiveIn; + + // Regs killed in MBB. They may be defined again, and will then be in both + // regsKilled and regsLiveOut. + RegSet regsKilled; + + // Regs defined in MBB and live out. Note that vregs passing through may + // be live out without being mentioned here. + RegSet regsLiveOut; + + // Vregs that pass through MBB untouched. This set is disjoint from + // regsKilled and regsLiveOut. + RegSet vregsPassed; + + // Vregs that must pass through MBB because they are needed by a successor + // block. This set is disjoint from regsLiveOut. + RegSet vregsRequired; + + // Set versions of block's predecessor and successor lists. + BlockSet Preds, Succs; + + BBInfo() = default; + + // Add register to vregsRequired if it belongs there. Return true if + // anything changed. + bool addRequired(Register Reg) { + if (!Reg.isVirtual()) + return false; + if (regsLiveOut.count(Reg)) + return false; + return vregsRequired.insert(Reg).second; + } + + // Same for a full set. + bool addRequired(const RegSet &RS) { + bool Changed = false; + for (Register Reg : RS) + Changed |= addRequired(Reg); + return Changed; + } + + // Same for a full map. + bool addRequired(const RegMap &RM) { + bool Changed = false; + for (const auto &I : RM) + Changed |= addRequired(I.first); + return Changed; + } + + // Live-out registers are either in regsLiveOut or vregsPassed. + bool isLiveOut(Register Reg) const { + return regsLiveOut.count(Reg) || vregsPassed.count(Reg); + } + }; + + // Extra register info per MBB. + DenseMap MBBInfoMap; + + bool isReserved(Register Reg) { + return Reg.id() < regsReserved.size() && regsReserved.test(Reg.id()); + } + + bool isAllocatable(Register Reg) const { + return Reg.id() < TRI->getNumRegs() && TRI->isInAllocatableClass(Reg) && + !regsReserved.test(Reg.id()); + } + + void init(const MachineFunction &MF); + + void markReachable(const MachineBasicBlock *MBB); + + void enterBlock(const MachineBasicBlock *MBB); + void exitBlock(const MachineBasicBlock *MBB); + + void visitInstruction(const MachineInstr &MI); + void visitBundleAfter(const MachineInstr &MI); + + // Add Reg and any sub-registers to RV + void addRegWithSubRegs(RegVector &RV, Register Reg) { + RV.push_back(Reg); + if (Reg.isPhysical()) + append_range(RV, TRI->subregs(Reg.asMCReg())); + } + + // Calculate the largest possible vregsPassed sets. These are the registers + // that can pass through an MBB live, but may not be live every time. It is + // assumed that all vregsPassed sets are empty before the call. + void calcRegsPassed(); + + // Calculate the set of virtual registers that must be passed through each + // basic block in order to satisfy the requirements of successor blocks. This + // is very similar to calcRegsPassed, only backwards. + void calcRegsRequired(); +}; + +} // namespace llvm + +#endif Index: llvm/lib/CodeGen/CMakeLists.txt =================================================================== --- llvm/lib/CodeGen/CMakeLists.txt +++ llvm/lib/CodeGen/CMakeLists.txt @@ -94,6 +94,7 @@ LiveRegUnits.cpp LiveStacks.cpp LiveVariables.cpp + LivenessVerifier.cpp LLVMTargetMachine.cpp LocalStackSlotAllocation.cpp LoopTraversal.cpp Index: llvm/lib/CodeGen/LivenessVerifier.cpp =================================================================== --- /dev/null +++ llvm/lib/CodeGen/LivenessVerifier.cpp @@ -0,0 +1,301 @@ +//===-- llvm/CodeGen/LivenessVerifier.cpp ---------------------------------===// +// +// 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 +// +//===----------------------------------------------------------------------===// + +#include "llvm/CodeGen/LivenessVerifier.h" + +#include "llvm/ADT/PostOrderIterator.h" +#include "llvm/ADT/SetOperations.h" +#include "llvm/CodeGen/MachineFrameInfo.h" +#include "llvm/CodeGen/MachineRegisterInfo.h" +#include "llvm/CodeGen/TargetSubtargetInfo.h" + +using namespace llvm; + +void LiveRegTracker::markReachable(const MachineBasicBlock *MBB) { + BBInfo &MInfo = MBBInfoMap[MBB]; + if (!MInfo.reachable) { + MInfo.reachable = true; + for (const MachineBasicBlock *Succ : MBB->successors()) + markReachable(Succ); + } +} + +void LiveRegTracker::enterBlock(const MachineBasicBlock *MBB) { + regsLive.clear(); + if (MRI->tracksLiveness()) { + for (const auto &LI : MBB->liveins()) { + for (const MCPhysReg &SubReg : TRI->subregs_inclusive(LI.PhysReg)) + regsLive.insert(SubReg); + } + } + + const MachineFrameInfo &MFI = MF->getFrameInfo(); + BitVector PR = MFI.getPristineRegs(*MF); + for (unsigned I : PR.set_bits()) { + for (const MCPhysReg &SubReg : TRI->subregs_inclusive(I)) + regsLive.insert(SubReg); + } + + regsKilled.clear(); + regsDefined.clear(); +} + +void LiveRegTracker::exitBlock(const MachineBasicBlock *MBB) { + MBBInfoMap[MBB].regsLiveOut = regsLive; + regsLive.clear(); +} + +void LiveRegTracker::visitInstruction(const MachineInstr &MI) { + for (const MachineOperand &MO : MI.operands()) { + if (MO.isRegMask()) { + regMasks.push_back(MO.getRegMask()); + continue; + } + + if (!MO.isReg()) + continue; + + Register Reg = MO.getReg(); + // Both use and def operands can read a register. + if (MO.readsReg()) { + if (MO.isKill()) + addRegWithSubRegs(regsKilled, Reg); + if (!regsLive.count(Reg)) { + BBInfo &MInfo = MBBInfoMap[MI.getParent()]; + + if (!MI.isPHI()) + MInfo.vregsLiveIn.insert(std::make_pair(Reg, &MI)); + } + } + + if (MO.isDef()) { + // Register defined. + // TODO: verify that earlyclobber ops are not used. + if (MO.isDead()) + addRegWithSubRegs(regsDead, Reg); + else + addRegWithSubRegs(regsDefined, Reg); + } + } +} + +void LiveRegTracker::visitBundleAfter(const MachineInstr &MI) { + BBInfo &MInfo = MBBInfoMap[MI.getParent()]; + set_union(MInfo.regsKilled, regsKilled); + set_subtract(regsLive, regsKilled); + regsKilled.clear(); + // Kill any masked registers. + while (!regMasks.empty()) { + const uint32_t *Mask = regMasks.pop_back_val(); + for (Register Reg : regsLive) { + if (Reg.isPhysical() && + MachineOperand::clobbersPhysReg(Mask, Reg.asMCReg())) + regsDead.push_back(Reg); + } + } + set_subtract(regsLive, regsDead); + regsDead.clear(); + set_union(regsLive, regsDefined); + regsDefined.clear(); +} + +void LiveRegTracker::init(const MachineFunction &MF) { + this->MF = &MF; + this->TRI = MF.getSubtarget().getRegisterInfo(); + this->MRI = &MF.getRegInfo(); + + regsReserved = MRI->reservedRegsFrozen() ? MRI->getReservedRegs() + : TRI->getReservedRegs(MF); + + if (!MF.empty()) + markReachable(&MF.front()); + + // Build a set of the basic blocks in the function. + FunctionBlocks.clear(); + for (const auto &MBB : MF) { + FunctionBlocks.insert(&MBB); + BBInfo &MInfo = MBBInfoMap[&MBB]; + + MInfo.Preds.insert(MBB.pred_begin(), MBB.pred_end()); + MInfo.Succs.insert(MBB.succ_begin(), MBB.succ_end()); + } +} + +namespace { +// This implements a set of registers that serves as a filter: can filter other +// sets by passing through elements not in the filter and blocking those that +// are. Any filter implicitly includes the full set of physical registers upon +// creation, thus filtering them all out. The filter itself as a set only grows, +// and needs to be as efficient as possible. +struct VRegFilter { + // Add elements to the filter itself. \pre Input set \p FromRegSet must have + // no duplicates. Both virtual and physical registers are fine. + template void add(const RegSetT &FromRegSet) { + SmallVector VRegsBuffer; + filterAndAdd(FromRegSet, VRegsBuffer); + } + // Filter \p FromRegSet through the filter and append passed elements into \p + // ToVRegs. All elements appended are then added to the filter itself. + // \returns true if anything changed. + template + bool filterAndAdd(const RegSetT &FromRegSet, + SmallVectorImpl &ToVRegs) { + unsigned SparseUniverse = Sparse.size(); + unsigned NewSparseUniverse = SparseUniverse; + unsigned NewDenseSize = Dense.size(); + size_t Begin = ToVRegs.size(); + for (Register Reg : FromRegSet) { + if (!Reg.isVirtual()) + continue; + unsigned Index = Register::virtReg2Index(Reg); + if (Index < SparseUniverseMax) { + if (Index < SparseUniverse && Sparse.test(Index)) + continue; + NewSparseUniverse = std::max(NewSparseUniverse, Index + 1); + } else { + if (Dense.count(Reg)) + continue; + ++NewDenseSize; + } + ToVRegs.push_back(Reg); + } + size_t End = ToVRegs.size(); + if (Begin == End) + return false; + // Reserving space in sets once performs better than doing so continuously + // and pays easily for double look-ups (even in Dense with SparseUniverseMax + // tuned all the way down) and double iteration (the second one is over a + // SmallVector, which is a lot cheaper compared to DenseSet or BitVector). + Sparse.resize(NewSparseUniverse); + Dense.reserve(NewDenseSize); + for (unsigned I = Begin; I < End; ++I) { + Register Reg = ToVRegs[I]; + unsigned Index = Register::virtReg2Index(Reg); + if (Index < SparseUniverseMax) + Sparse.set(Index); + else + Dense.insert(Reg); + } + return true; + } + +private: + static constexpr unsigned SparseUniverseMax = 10 * 1024 * 8; + // VRegs indexed within SparseUniverseMax are tracked by Sparse, those beyound + // are tracked by Dense. The only purpose of the threashold and the Dense set + // is to have a reasonably growing memory usage in pathological cases (large + // number of very sparse VRegFilter instances live at the same time). In + // practice even in the worst-by-execution time cases having all elements + // tracked by Sparse (very large SparseUniverseMax scenario) tends to be more + // space efficient than if tracked by Dense. The threashold is set to keep the + // worst-case memory usage within 2x of figures determined empirically for + // "all Dense" scenario in such worst-by-execution-time cases. + BitVector Sparse; + DenseSet Dense; +}; + +// Implements both a transfer function and a (binary, in-place) join operator +// for a dataflow over register sets with set union join and filtering transfer +// (out_b = in_b \ filter_b). filter_b is expected to be set-up ahead of time. +// Maintains out_b as its state, allowing for O(n) iteration over it at any +// time, where n is the size of the set (as opposed to O(U) where U is the +// universe). filter_b implicitly contains all physical registers at all times. +class FilteringVRegSet { + VRegFilter Filter; + SmallVector VRegs; + +public: + // Set-up the filter_b. \pre Input register set \p RS must have no duplicates. + // Both virtual and physical registers are fine. + template void addToFilter(const RegSetT &RS) { + Filter.add(RS); + } + // Passes \p RS through the filter_b (transfer function) and adds what's left + // to itself (out_b). + template bool add(const RegSetT &RS) { + // Double-duty the Filter: to maintain VRegs a set (and the join operation + // a set union) just add everything being added here to the Filter as well. + return Filter.filterAndAdd(RS, VRegs); + } + using const_iterator = decltype(VRegs)::const_iterator; + const_iterator begin() const { return VRegs.begin(); } + const_iterator end() const { return VRegs.end(); } + size_t size() const { return VRegs.size(); } +}; +} // namespace + +void LiveRegTracker::calcRegsPassed() { + // ReversePostOrderTraversal doesn't handle empty functions. + if (MF->empty()) + return; + + for (const MachineBasicBlock *MB : + ReversePostOrderTraversal(MF)) { + FilteringVRegSet VRegs; + BBInfo &Info = MBBInfoMap[MB]; + assert(Info.reachable); + + VRegs.addToFilter(Info.regsKilled); + VRegs.addToFilter(Info.regsLiveOut); + for (const MachineBasicBlock *Pred : MB->predecessors()) { + const BBInfo &PredInfo = MBBInfoMap[Pred]; + if (!PredInfo.reachable) + continue; + + VRegs.add(PredInfo.regsLiveOut); + VRegs.add(PredInfo.vregsPassed); + } + Info.vregsPassed.reserve(VRegs.size()); + Info.vregsPassed.insert(VRegs.begin(), VRegs.end()); + } +} + +void LiveRegTracker::calcRegsRequired() { + // First push live-in regs to predecessors' vregsRequired. + SmallPtrSet todo; + for (const auto &MBB : *MF) { + BBInfo &MInfo = MBBInfoMap[&MBB]; + for (const MachineBasicBlock *Pred : MBB.predecessors()) { + BBInfo &PInfo = MBBInfoMap[Pred]; + if (PInfo.addRequired(MInfo.vregsLiveIn)) + todo.insert(Pred); + } + + // Handle the PHI node. + for (const MachineInstr &MI : MBB.phis()) { + for (unsigned i = 1, e = MI.getNumOperands(); i != e; i += 2) { + // Skip those Operands which are undef regs or not regs. + if (!MI.getOperand(i).isReg() || !MI.getOperand(i).readsReg()) + continue; + + // Get register and predecessor for one PHI edge. + Register Reg = MI.getOperand(i).getReg(); + const MachineBasicBlock *Pred = MI.getOperand(i + 1).getMBB(); + + BBInfo &PInfo = MBBInfoMap[Pred]; + if (PInfo.addRequired(Reg)) + todo.insert(Pred); + } + } + } + + // Iteratively push vregsRequired to predecessors. This will converge to the + // same final state regardless of DenseSet iteration order. + while (!todo.empty()) { + const MachineBasicBlock *MBB = *todo.begin(); + todo.erase(MBB); + BBInfo &MInfo = MBBInfoMap[MBB]; + for (const MachineBasicBlock *Pred : MBB->predecessors()) { + if (Pred == MBB) + continue; + BBInfo &SInfo = MBBInfoMap[Pred]; + if (SInfo.addRequired(MInfo.vregsRequired)) + todo.insert(Pred); + } + } +} Index: llvm/lib/CodeGen/MachineVerifier.cpp =================================================================== --- llvm/lib/CodeGen/MachineVerifier.cpp +++ llvm/lib/CodeGen/MachineVerifier.cpp @@ -38,6 +38,7 @@ #include "llvm/CodeGen/LiveRangeCalc.h" #include "llvm/CodeGen/LiveStacks.h" #include "llvm/CodeGen/LiveVariables.h" +#include "llvm/CodeGen/LivenessVerifier.h" #include "llvm/CodeGen/MachineBasicBlock.h" #include "llvm/CodeGen/MachineFrameInfo.h" #include "llvm/CodeGen/MachineFunction.h" @@ -115,12 +116,8 @@ const MachineInstr *FirstNonPHI; const MachineInstr *FirstTerminator; - BlockSet FunctionBlocks; - BitVector regsReserved; - RegSet regsLive; - RegVector regsDefined, regsDead, regsKilled; - RegMaskVector regMasks; + LiveRegTracker LiveRegs; SlotIndex lastIndex; @@ -131,80 +128,6 @@ append_range(RV, TRI->subregs(Reg.asMCReg())); } - struct BBInfo { - // Is this MBB reachable from the MF entry point? - bool reachable = false; - - // Vregs that must be live in because they are used without being - // defined. Map value is the user. vregsLiveIn doesn't include regs - // that only are used by PHI nodes. - RegMap vregsLiveIn; - - // Regs killed in MBB. They may be defined again, and will then be in both - // regsKilled and regsLiveOut. - RegSet regsKilled; - - // Regs defined in MBB and live out. Note that vregs passing through may - // be live out without being mentioned here. - RegSet regsLiveOut; - - // Vregs that pass through MBB untouched. This set is disjoint from - // regsKilled and regsLiveOut. - RegSet vregsPassed; - - // Vregs that must pass through MBB because they are needed by a successor - // block. This set is disjoint from regsLiveOut. - RegSet vregsRequired; - - // Set versions of block's predecessor and successor lists. - BlockSet Preds, Succs; - - BBInfo() = default; - - // Add register to vregsRequired if it belongs there. Return true if - // anything changed. - bool addRequired(Register Reg) { - if (!Reg.isVirtual()) - return false; - if (regsLiveOut.count(Reg)) - return false; - return vregsRequired.insert(Reg).second; - } - - // Same for a full set. - bool addRequired(const RegSet &RS) { - bool Changed = false; - for (Register Reg : RS) - Changed |= addRequired(Reg); - return Changed; - } - - // Same for a full map. - bool addRequired(const RegMap &RM) { - bool Changed = false; - for (const auto &I : RM) - Changed |= addRequired(I.first); - return Changed; - } - - // Live-out registers are either in regsLiveOut or vregsPassed. - bool isLiveOut(Register Reg) const { - return regsLiveOut.count(Reg) || vregsPassed.count(Reg); - } - }; - - // Extra register info per MBB. - DenseMap MBBInfoMap; - - bool isReserved(Register Reg) { - return Reg.id() < regsReserved.size() && regsReserved.test(Reg.id()); - } - - bool isAllocatable(Register Reg) const { - return Reg.id() < TRI->getNumRegs() && TRI->isInAllocatableClass(Reg) && - !regsReserved.test(Reg.id()); - } - // Analysis information if available LiveVariables *LiveVars; LiveIntervals *LiveInts; @@ -260,10 +183,8 @@ LaneBitmask LaneMask = LaneBitmask::getNone()); void markReachable(const MachineBasicBlock *MBB); - void calcRegsPassed(); void checkPHIOps(const MachineBasicBlock &MBB); - void calcRegsRequired(); void verifyLiveVariables(); void verifyLiveIntervals(); void verifyLiveInterval(const LiveInterval&); @@ -371,6 +292,7 @@ foundErrors = 0; this->MF = &MF; + TM = &MF.getTarget(); TII = MF.getSubtarget().getInstrInfo(); TRI = MF.getSubtarget().getRegisterInfo(); @@ -457,6 +379,9 @@ // Was this the last bundled instruction? InBundle = MI.isBundledWithSucc(); + + if (!MI.isDebugInstr()) + LiveRegs.visitInstruction(MI); } if (CurBundle) visitMachineBundleAfter(CurBundle); @@ -467,12 +392,7 @@ visitMachineFunctionAfter(); // Clean up. - regsLive.clear(); - regsDefined.clear(); - regsDead.clear(); - regsKilled.clear(); - regMasks.clear(); - MBBInfoMap.clear(); + LiveRegs.clear(); return foundErrors; } @@ -573,34 +493,15 @@ errs() << "- lanemask: " << PrintLaneMask(LaneMask) << '\n'; } -void MachineVerifier::markReachable(const MachineBasicBlock *MBB) { - BBInfo &MInfo = MBBInfoMap[MBB]; - if (!MInfo.reachable) { - MInfo.reachable = true; - for (const MachineBasicBlock *Succ : MBB->successors()) - markReachable(Succ); - } -} - void MachineVerifier::visitMachineFunctionBefore() { lastIndex = SlotIndex(); - regsReserved = MRI->reservedRegsFrozen() ? MRI->getReservedRegs() - : TRI->getReservedRegs(*MF); - if (!MF->empty()) - markReachable(&MF->front()); + LiveRegs.init(*MF); - // Build a set of the basic blocks in the function. - FunctionBlocks.clear(); for (const auto &MBB : *MF) { - FunctionBlocks.insert(&MBB); - BBInfo &MInfo = MBBInfoMap[&MBB]; - - MInfo.Preds.insert(MBB.pred_begin(), MBB.pred_end()); + const LiveRegTracker::BBInfo &MInfo = LiveRegs.MBBInfoMap[&MBB]; if (MInfo.Preds.size() != MBB.pred_size()) report("MBB has duplicate entries in its predecessor list.", &MBB); - - MInfo.Succs.insert(MBB.succ_begin(), MBB.succ_end()); if (MInfo.Succs.size() != MBB.succ_size()) report("MBB has duplicate entries in its successor list.", &MBB); } @@ -622,7 +523,7 @@ // If this block has allocatable physical registers live-in, check that // it is an entry block or landing pad. for (const auto &LI : MBB->liveins()) { - if (isAllocatable(LI.PhysReg) && !MBB->isEHPad() && + if (LiveRegs.isAllocatable(LI.PhysReg) && !MBB->isEHPad() && MBB->getIterator() != MBB->getParent()->begin()) { report("MBB has allocatable live-in, but isn't entry or landing-pad.", MBB); report_context(LI.PhysReg); @@ -635,9 +536,9 @@ for (const auto *succ : MBB->successors()) { if (succ->isEHPad()) LandingPadSuccs.insert(succ); - if (!FunctionBlocks.count(succ)) + if (!LiveRegs.FunctionBlocks.count(succ)) report("MBB has successor that isn't part of the function.", MBB); - if (!MBBInfoMap[succ].Preds.count(MBB)) { + if (!LiveRegs.MBBInfoMap[succ].Preds.count(MBB)) { report("Inconsistent CFG", MBB); errs() << "MBB is not in the predecessor list of the successor " << printMBBReference(*succ) << ".\n"; @@ -646,9 +547,9 @@ // Check the predecessor list. for (const MachineBasicBlock *Pred : MBB->predecessors()) { - if (!FunctionBlocks.count(Pred)) + if (!LiveRegs.FunctionBlocks.count(Pred)) report("MBB has predecessor that isn't part of the function.", MBB); - if (!MBBInfoMap[Pred].Succs.count(MBB)) { + if (!LiveRegs.MBBInfoMap[Pred].Succs.count(MBB)) { report("Inconsistent CFG", MBB); errs() << "MBB is not in the successor list of the predecessor " << printMBBReference(*Pred) << ".\n"; @@ -776,27 +677,19 @@ } } - regsLive.clear(); + bool ValidLiveIns = true; if (MRI->tracksLiveness()) { for (const auto &LI : MBB->liveins()) { if (!Register::isPhysicalRegister(LI.PhysReg)) { report("MBB live-in list contains non-physical register", MBB); + ValidLiveIns = false; continue; } - for (const MCPhysReg &SubReg : TRI->subregs_inclusive(LI.PhysReg)) - regsLive.insert(SubReg); } } - const MachineFrameInfo &MFI = MF->getFrameInfo(); - BitVector PR = MFI.getPristineRegs(*MF); - for (unsigned I : PR.set_bits()) { - for (const MCPhysReg &SubReg : TRI->subregs_inclusive(I)) - regsLive.insert(SubReg); - } - - regsKilled.clear(); - regsDefined.clear(); + if (ValidLiveIns) + LiveRegs.enterBlock(MBB); if (Indexes) lastIndex = Indexes->getMBBStartIdx(MBB); @@ -2163,7 +2056,6 @@ } case MachineOperand::MO_RegisterMask: - regMasks.push_back(MO->getRegMask()); break; case MachineOperand::MO_MachineBasicBlock: @@ -2307,9 +2199,6 @@ // Both use and def operands can read a register. if (MO->readsReg()) { - if (MO->isKill()) - addRegWithSubRegs(regsKilled, Reg); - // Check that LiveVars knows this kill (unless we are inside a bundle, in // which case we have already checked that LiveVars knows any kills on the // bundle header instead). @@ -2324,7 +2213,7 @@ if (LiveInts && !LiveInts->isNotInMIMap(*MI)) { SlotIndex UseIdx = LiveInts->getInstructionIndex(*MI); // Check the cached regunit intervals. - if (Reg.isPhysical() && !isReserved(Reg)) { + if (Reg.isPhysical() && !LiveRegs.isReserved(Reg)) { for (MCRegUnitIterator Units(Reg.asMCReg(), TRI); Units.isValid(); ++Units) { if (MRI->isReservedRegUnit(*Units)) @@ -2362,15 +2251,15 @@ } // Use of a dead register. - if (!regsLive.count(Reg)) { + if (!LiveRegs.regsLive.count(Reg)) { if (Reg.isPhysical()) { // Reserved registers may be used even when 'dead'. - bool Bad = !isReserved(Reg); + bool Bad = !LiveRegs.isReserved(Reg); // We are fine if just any subregister has a defined value. if (Bad) { for (const MCPhysReg &SubReg : TRI->subregs(Reg)) { - if (regsLive.count(SubReg)) { + if (LiveRegs.regsLive.count(SubReg)) { Bad = false; break; } @@ -2397,14 +2286,12 @@ } else if (MRI->def_empty(Reg)) { report("Reading virtual register without a def", MO, MONum); } else { - BBInfo &MInfo = MBBInfoMap[MI->getParent()]; + LiveRegTracker::BBInfo &MInfo = LiveRegs.MBBInfoMap[MI->getParent()]; // We don't know which virtual registers are live in, so only complain // if vreg was killed in this MBB. Otherwise keep track of vregs that // must be live in. PHI instructions are handled separately. if (MInfo.regsKilled.count(Reg)) report("Using a killed virtual register", MO, MONum); - else if (!MI->isPHI()) - MInfo.vregsLiveIn.insert(std::make_pair(Reg, MI)); } } } @@ -2412,10 +2299,6 @@ if (MO->isDef()) { // Register defined. // TODO: verify that earlyclobber ops are not used. - if (MO->isDead()) - addRegWithSubRegs(regsDead, Reg); - else - addRegWithSubRegs(regsDefined, Reg); // Verify SSA form. if (MRI->isSSA() && Reg.isVirtual() && @@ -2450,25 +2333,12 @@ // Normal stand-alone instructions are also considered 'bundles', and this // function is called for all of them. void MachineVerifier::visitMachineBundleAfter(const MachineInstr *MI) { - BBInfo &MInfo = MBBInfoMap[MI->getParent()]; - set_union(MInfo.regsKilled, regsKilled); - set_subtract(regsLive, regsKilled); regsKilled.clear(); - // Kill any masked registers. - while (!regMasks.empty()) { - const uint32_t *Mask = regMasks.pop_back_val(); - for (Register Reg : regsLive) - if (Reg.isPhysical() && - MachineOperand::clobbersPhysReg(Mask, Reg.asMCReg())) - regsDead.push_back(Reg); - } - set_subtract(regsLive, regsDead); regsDead.clear(); - set_union(regsLive, regsDefined); regsDefined.clear(); + LiveRegs.visitBundleAfter(*MI); } void MachineVerifier::visitMachineBasicBlockAfter(const MachineBasicBlock *MBB) { - MBBInfoMap[MBB].regsLiveOut = regsLive; - regsLive.clear(); + LiveRegs.exitBlock(MBB); if (Indexes) { SlotIndex stop = Indexes->getMBBEndIdx(MBB); @@ -2584,87 +2454,10 @@ }; } // namespace -// Calculate the largest possible vregsPassed sets. These are the registers that -// can pass through an MBB live, but may not be live every time. It is assumed -// that all vregsPassed sets are empty before the call. -void MachineVerifier::calcRegsPassed() { - if (MF->empty()) - // ReversePostOrderTraversal doesn't handle empty functions. - return; - - for (const MachineBasicBlock *MB : - ReversePostOrderTraversal(MF)) { - FilteringVRegSet VRegs; - BBInfo &Info = MBBInfoMap[MB]; - assert(Info.reachable); - - VRegs.addToFilter(Info.regsKilled); - VRegs.addToFilter(Info.regsLiveOut); - for (const MachineBasicBlock *Pred : MB->predecessors()) { - const BBInfo &PredInfo = MBBInfoMap[Pred]; - if (!PredInfo.reachable) - continue; - - VRegs.add(PredInfo.regsLiveOut); - VRegs.add(PredInfo.vregsPassed); - } - Info.vregsPassed.reserve(VRegs.size()); - Info.vregsPassed.insert(VRegs.begin(), VRegs.end()); - } -} - -// Calculate the set of virtual registers that must be passed through each basic -// block in order to satisfy the requirements of successor blocks. This is very -// similar to calcRegsPassed, only backwards. -void MachineVerifier::calcRegsRequired() { - // First push live-in regs to predecessors' vregsRequired. - SmallPtrSet todo; - for (const auto &MBB : *MF) { - BBInfo &MInfo = MBBInfoMap[&MBB]; - for (const MachineBasicBlock *Pred : MBB.predecessors()) { - BBInfo &PInfo = MBBInfoMap[Pred]; - if (PInfo.addRequired(MInfo.vregsLiveIn)) - todo.insert(Pred); - } - - // Handle the PHI node. - for (const MachineInstr &MI : MBB.phis()) { - for (unsigned i = 1, e = MI.getNumOperands(); i != e; i += 2) { - // Skip those Operands which are undef regs or not regs. - if (!MI.getOperand(i).isReg() || !MI.getOperand(i).readsReg()) - continue; - - // Get register and predecessor for one PHI edge. - Register Reg = MI.getOperand(i).getReg(); - const MachineBasicBlock *Pred = MI.getOperand(i + 1).getMBB(); - - BBInfo &PInfo = MBBInfoMap[Pred]; - if (PInfo.addRequired(Reg)) - todo.insert(Pred); - } - } - } - - // Iteratively push vregsRequired to predecessors. This will converge to the - // same final state regardless of DenseSet iteration order. - while (!todo.empty()) { - const MachineBasicBlock *MBB = *todo.begin(); - todo.erase(MBB); - BBInfo &MInfo = MBBInfoMap[MBB]; - for (const MachineBasicBlock *Pred : MBB->predecessors()) { - if (Pred == MBB) - continue; - BBInfo &SInfo = MBBInfoMap[Pred]; - if (SInfo.addRequired(MInfo.vregsRequired)) - todo.insert(Pred); - } - } -} - // Check PHI instructions at the beginning of MBB. It is assumed that // calcRegsPassed has been run so BBInfo::isLiveOut is valid. void MachineVerifier::checkPHIOps(const MachineBasicBlock &MBB) { - BBInfo &MInfo = MBBInfoMap[&MBB]; + LiveRegTracker::BBInfo &MInfo = LiveRegs.MBBInfoMap[&MBB]; SmallPtrSet seen; for (const MachineInstr &Phi : MBB) { @@ -2708,7 +2501,7 @@ if (MInfo.reachable) { seen.insert(&Pre); - BBInfo &PrInfo = MBBInfoMap[&Pre]; + LiveRegTracker::BBInfo &PrInfo = LiveRegs.MBBInfoMap[&Pre]; if (!MO0.isUndef() && PrInfo.reachable && !PrInfo.isLiveOut(MO0.getReg())) report("PHI operand is not live-out from predecessor", &MO0, I); @@ -2729,17 +2522,17 @@ } void MachineVerifier::visitMachineFunctionAfter() { - calcRegsPassed(); + LiveRegs.calcRegsPassed(); for (const MachineBasicBlock &MBB : *MF) checkPHIOps(MBB); // Now check liveness info if available - calcRegsRequired(); + LiveRegs.calcRegsRequired(); // Check for killed virtual registers that should be live out. for (const auto &MBB : *MF) { - BBInfo &MInfo = MBBInfoMap[&MBB]; + LiveRegTracker::BBInfo &MInfo = LiveRegs.MBBInfoMap[&MBB]; for (Register VReg : MInfo.vregsRequired) if (MInfo.regsKilled.count(VReg)) { report("Virtual register killed in block, but needed live out.", &MBB); @@ -2749,7 +2542,7 @@ } if (!MF->empty()) { - BBInfo &MInfo = MBBInfoMap[&MF->front()]; + LiveRegTracker::BBInfo &MInfo = LiveRegs.MBBInfoMap[&MF->front()]; for (Register VReg : MInfo.vregsRequired) { report("Virtual register defs don't dominate all uses.", MF); report_context_vreg(VReg); @@ -2773,10 +2566,11 @@ for (MachineBasicBlock::RegisterMaskPair P : MBB.liveins()) { MCPhysReg LiveInReg = P.PhysReg; bool hasAliases = MCRegAliasIterator(LiveInReg, TRI, false).isValid(); - if (hasAliases || isAllocatable(LiveInReg) || isReserved(LiveInReg)) + if (hasAliases || LiveRegs.isAllocatable(LiveInReg) || + LiveRegs.isReserved(LiveInReg)) continue; for (const MachineBasicBlock *Pred : MBB.predecessors()) { - BBInfo &PInfo = MBBInfoMap[Pred]; + LiveRegTracker::BBInfo &PInfo = LiveRegs.MBBInfoMap[Pred]; if (!PInfo.regsLiveOut.count(LiveInReg)) { report("Live in register not found to be live out from predecessor.", &MBB); @@ -2813,7 +2607,7 @@ Register Reg = Register::index2VirtReg(I); LiveVariables::VarInfo &VI = LiveVars->getVarInfo(Reg); for (const auto &MBB : *MF) { - BBInfo &MInfo = MBBInfoMap[&MBB]; + LiveRegTracker::BBInfo &MInfo = LiveRegs.MBBInfoMap[&MBB]; // Our vregsRequired should be identical to LiveVariables' AliveBlocks if (MInfo.vregsRequired.count(Reg)) { Index: llvm/test/CodeGen/X86/invalid-liveness.mir =================================================================== --- llvm/test/CodeGen/X86/invalid-liveness.mir +++ llvm/test/CodeGen/X86/invalid-liveness.mir @@ -1,6 +1,9 @@ # RUN: not --crash llc -mtriple=i686-- -run-pass liveintervals -o - %s 2>&1 | FileCheck %s # REQUIRES: asserts +# FIXME: This wants to verify the assertion in LiveRangeCalc but +# needs to bypass the verifier check. + --- | define void @func() { ret void } ... @@ -9,8 +12,9 @@ # on all paths; In this example a def for %0 is missing when jumping from # bb.0 to bb.3. # -# CHECK: Use of %0 does not have a corresponding definition on every path -# CHECK: ERROR: Use not jointly dominated by defs. + +# CHECK: *** Bad machine code: Virtual register defs don't dominate all uses. *** + name: func registers: - { id: 0, class: gr32 } Index: llvm/unittests/Target/WebAssembly/WebAssemblyExceptionInfoTest.cpp =================================================================== --- llvm/unittests/Target/WebAssembly/WebAssemblyExceptionInfoTest.cpp +++ llvm/unittests/Target/WebAssembly/WebAssemblyExceptionInfoTest.cpp @@ -107,8 +107,8 @@ ; predecessors: %bb.2 successors: %bb.4, %bb.6 liveins: $value_stack - %1:i32 = CATCH &__cpp_exception, implicit-def $arguments - BR_IF %bb.4, %58:i32, implicit-def $arguments, implicit-def $value_stack, implicit $value_stack + %0:i32 = CATCH &__cpp_exception, implicit-def $arguments + BR_IF %bb.4, undef %58:i32, implicit-def $arguments, implicit-def $value_stack, implicit $value_stack BR %bb.6, implicit-def $arguments bb.4: @@ -258,7 +258,7 @@ successors: %bb.2, %bb.8 liveins: $value_stack %0:i32 = CATCH &__cpp_exception, implicit-def $arguments - BR_IF %bb.2, %32:i32, implicit-def $arguments, implicit-def $value_stack, implicit $value_stack + BR_IF %bb.2, undef %10:i32, implicit-def $arguments, implicit-def $value_stack, implicit $value_stack BR %bb.8, implicit-def $arguments bb.2: @@ -272,7 +272,7 @@ successors: %bb.4, %bb.6 liveins: $value_stack %1:i32 = CATCH &__cpp_exception, implicit-def $arguments - BR_IF %bb.4, %43:i32, implicit-def $arguments, implicit-def $value_stack, implicit $value_stack + BR_IF %bb.4, undef %43:i32, implicit-def $arguments, implicit-def $value_stack, implicit $value_stack BR %bb.6, implicit-def $arguments bb.4: