llvm/llvm/lib/CodeGen/PHIElimination.cpp

//===- PhiElimination.cpp - Eliminate PHI nodes by inserting copies -------===//
//
// 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
//
//===----------------------------------------------------------------------===//
//
// This pass eliminates machine instruction PHI nodes by inserting copy
// instructions.  This destroys SSA information, but is the desired input for
// some register allocators.
//
//===----------------------------------------------------------------------===//

#include "llvm/CodeGen/PHIElimination.h"
#include "PHIEliminationUtils.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/CodeGen/LiveInterval.h"
#include "llvm/CodeGen/LiveIntervals.h"
#include "llvm/CodeGen/LiveVariables.h"
#include "llvm/CodeGen/MachineBasicBlock.h"
#include "llvm/CodeGen/MachineDominators.h"
#include "llvm/CodeGen/MachineFunction.h"
#include "llvm/CodeGen/MachineFunctionPass.h"
#include "llvm/CodeGen/MachineInstr.h"
#include "llvm/CodeGen/MachineInstrBuilder.h"
#include "llvm/CodeGen/MachineLoopInfo.h"
#include "llvm/CodeGen/MachineOperand.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/CodeGen/SlotIndexes.h"
#include "llvm/CodeGen/TargetInstrInfo.h"
#include "llvm/CodeGen/TargetOpcodes.h"
#include "llvm/CodeGen/TargetRegisterInfo.h"
#include "llvm/CodeGen/TargetSubtargetInfo.h"
#include "llvm/Pass.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
#include <cassert>
#include <iterator>
#include <utility>

usingnamespacellvm;

#define DEBUG_TYPE …

static cl::opt<bool>
    DisableEdgeSplitting("disable-phi-elim-edge-splitting", cl::init(false),
                         cl::Hidden,
                         cl::desc("Disable critical edge splitting "
                                  "during PHI elimination"));

static cl::opt<bool>
    SplitAllCriticalEdges("phi-elim-split-all-critical-edges", cl::init(false),
                          cl::Hidden,
                          cl::desc("Split all critical edges during "
                                   "PHI elimination"));

static cl::opt<bool> NoPhiElimLiveOutEarlyExit(
    "no-phi-elim-live-out-early-exit", cl::init(false), cl::Hidden,
    cl::desc("Do not use an early exit if isLiveOutPastPHIs returns true."));

namespace {

class PHIEliminationImpl { … };

class PHIElimination : public MachineFunctionPass { … };

} // end anonymous namespace

PreservedAnalyses
PHIEliminationPass::run(MachineFunction &MF,
                        MachineFunctionAnalysisManager &MFAM) { … }

STATISTIC(NumLowered, "Number of phis lowered");
STATISTIC(NumCriticalEdgesSplit, "Number of critical edges split");
STATISTIC(NumReused, "Number of reused lowered phis");

char PHIElimination::ID = …;

char &llvm::PHIEliminationID = …;

INITIALIZE_PASS_BEGIN(PHIElimination, DEBUG_TYPE,
                      "Eliminate PHI nodes for register allocation", false,
                      false)
INITIALIZE_PASS_DEPENDENCY(LiveVariablesWrapperPass)
INITIALIZE_PASS_END(PHIElimination, DEBUG_TYPE,
                    "Eliminate PHI nodes for register allocation", false, false)

void PHIElimination::getAnalysisUsage(AnalysisUsage &AU) const { … }

bool PHIEliminationImpl::run(MachineFunction &MF) { … }

/// EliminatePHINodes - Eliminate phi nodes by inserting copy instructions in
/// predecessor basic blocks.
bool PHIEliminationImpl::EliminatePHINodes(MachineFunction &MF,
                                           MachineBasicBlock &MBB) { … }

/// Return true if all defs of VirtReg are implicit-defs.
/// This includes registers with no defs.
static bool isImplicitlyDefined(unsigned VirtReg,
                                const MachineRegisterInfo &MRI) { … }

/// Return true if all sources of the phi node are implicit_def's, or undef's.
static bool allPhiOperandsUndefined(const MachineInstr &MPhi,
                                    const MachineRegisterInfo &MRI) { … }
/// LowerPHINode - Lower the PHI node at the top of the specified block.
void PHIEliminationImpl::LowerPHINode(MachineBasicBlock &MBB,
                                      MachineBasicBlock::iterator LastPHIIt,
                                      bool AllEdgesCritical) { … }

/// analyzePHINodes - Gather information about the PHI nodes in here. In
/// particular, we want to map the number of uses of a virtual register which is
/// used in a PHI node. We map that to the BB the vreg is coming from. This is
/// used later to determine when the vreg is killed in the BB.
void PHIEliminationImpl::analyzePHINodes(const MachineFunction &MF) { … }

bool PHIEliminationImpl::SplitPHIEdges(
    MachineFunction &MF, MachineBasicBlock &MBB, MachineLoopInfo *MLI,
    std::vector<SparseBitVector<>> *LiveInSets) { … }

bool PHIEliminationImpl::isLiveIn(Register Reg, const MachineBasicBlock *MBB) { … }

bool PHIEliminationImpl::isLiveOutPastPHIs(Register Reg,
                                           const MachineBasicBlock *MBB) { … }