MachineLICM.cpp | Explore in Territory

//===- MachineLICM.cpp - Machine Loop Invariant Code Motion Pass ----------===//
//
// 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 performs loop invariant code motion on machine instructions. We
// attempt to remove as much code from the body of a loop as possible.
//
// This pass is not intended to be a replacement or a complete alternative
// for the LLVM-IR-level LICM pass. It is only designed to hoist simple
// constructs that are not exposed before lowering and instruction selection.
//
//===----------------------------------------------------------------------===//

#include "llvm/ADT/BitVector.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SmallSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/CodeGen/MachineBasicBlock.h"
#include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
#include "llvm/CodeGen/MachineDominators.h"
#include "llvm/CodeGen/MachineFrameInfo.h"
#include "llvm/CodeGen/MachineFunction.h"
#include "llvm/CodeGen/MachineFunctionPass.h"
#include "llvm/CodeGen/MachineInstr.h"
#include "llvm/CodeGen/MachineLoopInfo.h"
#include "llvm/CodeGen/MachineMemOperand.h"
#include "llvm/CodeGen/MachineOperand.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/CodeGen/PseudoSourceValue.h"
#include "llvm/CodeGen/TargetInstrInfo.h"
#include "llvm/CodeGen/TargetLowering.h"
#include "llvm/CodeGen/TargetRegisterInfo.h"
#include "llvm/CodeGen/TargetSchedule.h"
#include "llvm/CodeGen/TargetSubtargetInfo.h"
#include "llvm/IR/DebugLoc.h"
#include "llvm/InitializePasses.h"
#include "llvm/MC/MCInstrDesc.h"
#include "llvm/MC/MCRegister.h"
#include "llvm/MC/MCRegisterInfo.h"
#include "llvm/Pass.h"
#include "llvm/Support/Casting.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
#include <algorithm>
#include <cassert>
#include <limits>
#include <vector>

usingnamespacellvm;

#define DEBUG_TYPE …

static cl::opt<bool>
AvoidSpeculation("avoid-speculation",
                 cl::desc("MachineLICM should avoid speculation"),
                 cl::init(true), cl::Hidden);

static cl::opt<bool>
HoistCheapInsts("hoist-cheap-insts",
                cl::desc("MachineLICM should hoist even cheap instructions"),
                cl::init(false), cl::Hidden);

static cl::opt<bool>
HoistConstStores("hoist-const-stores",
                 cl::desc("Hoist invariant stores"),
                 cl::init(true), cl::Hidden);

static cl::opt<bool> HoistConstLoads("hoist-const-loads",
                                     cl::desc("Hoist invariant loads"),
                                     cl::init(true), cl::Hidden);

// The default threshold of 100 (i.e. if target block is 100 times hotter)
// is based on empirical data on a single target and is subject to tuning.
static cl::opt<unsigned>
BlockFrequencyRatioThreshold("block-freq-ratio-threshold",
                             cl::desc("Do not hoist instructions if target"
                             "block is N times hotter than the source."),
                             cl::init(100), cl::Hidden);

enum class UseBFI { … };

static cl::opt<UseBFI>
DisableHoistingToHotterBlocks("disable-hoisting-to-hotter-blocks",
                              cl::desc("Disable hoisting instructions to"
                              " hotter blocks"),
                              cl::init(UseBFI::PGO), cl::Hidden,
                              cl::values(clEnumValN(UseBFI::None, "none",
                              "disable the feature"),
                              clEnumValN(UseBFI::PGO, "pgo",
                              "enable the feature when using profile data"),
                              clEnumValN(UseBFI::All, "all",
                              "enable the feature with/wo profile data")));

STATISTIC(NumHoisted,
          "Number of machine instructions hoisted out of loops");
STATISTIC(NumLowRP,
          "Number of instructions hoisted in low reg pressure situation");
STATISTIC(NumHighLatency,
          "Number of high latency instructions hoisted");
STATISTIC(NumCSEed,
          "Number of hoisted machine instructions CSEed");
STATISTIC(NumPostRAHoisted,
          "Number of machine instructions hoisted out of loops post regalloc");
STATISTIC(NumStoreConst,
          "Number of stores of const phys reg hoisted out of loops");
STATISTIC(NumNotHoistedDueToHotness,
          "Number of instructions not hoisted due to block frequency");

namespace {
  enum HoistResult { … };

  class MachineLICMBase : public MachineFunctionPass { … };

  class MachineLICM : public MachineLICMBase { … };

  class EarlyMachineLICM : public MachineLICMBase { … };

} // end anonymous namespace

char MachineLICM::ID;
char EarlyMachineLICM::ID;

char &llvm::MachineLICMID = …;
char &llvm::EarlyMachineLICMID = …;

INITIALIZE_PASS_BEGIN(MachineLICM, DEBUG_TYPE,
                      "Machine Loop Invariant Code Motion", false, false)
INITIALIZE_PASS_DEPENDENCY(MachineLoopInfoWrapperPass)
INITIALIZE_PASS_DEPENDENCY(MachineBlockFrequencyInfoWrapperPass)
INITIALIZE_PASS_DEPENDENCY(MachineDominatorTreeWrapperPass)
INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
INITIALIZE_PASS_END(MachineLICM, DEBUG_TYPE,
                    "Machine Loop Invariant Code Motion", false, false)

INITIALIZE_PASS_BEGIN(EarlyMachineLICM, "early-machinelicm",
                      "Early Machine Loop Invariant Code Motion", false, false)
INITIALIZE_PASS_DEPENDENCY(MachineLoopInfoWrapperPass)
INITIALIZE_PASS_DEPENDENCY(MachineBlockFrequencyInfoWrapperPass)
INITIALIZE_PASS_DEPENDENCY(MachineDominatorTreeWrapperPass)
INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
INITIALIZE_PASS_END(EarlyMachineLICM, "early-machinelicm",
                    "Early Machine Loop Invariant Code Motion", false, false)

bool MachineLICMBase::runOnMachineFunction(MachineFunction &MF) { … }

/// Return true if instruction stores to the specified frame.
static bool InstructionStoresToFI(const MachineInstr *MI, int FI) { … }

static void applyBitsNotInRegMaskToRegUnitsMask(const TargetRegisterInfo &TRI,
                                                BitVector &RUs,
                                                const uint32_t *Mask) { … }

/// Examine the instruction for potential LICM candidate. Also
/// gather register def and frame object update information.
void MachineLICMBase::ProcessMI(MachineInstr *MI, BitVector &RUDefs,
                                BitVector &RUClobbers,
                                SmallDenseSet<int> &StoredFIs,
                                SmallVectorImpl<CandidateInfo> &Candidates,
                                MachineLoop *CurLoop) { … }

/// Walk the specified region of the CFG and hoist loop invariants out to the
/// preheader.
void MachineLICMBase::HoistRegionPostRA(MachineLoop *CurLoop,
                                        MachineBasicBlock *CurPreheader) { … }

/// Add register 'Reg' to the livein sets of BBs in the current loop, and make
/// sure it is not killed by any instructions in the loop.
void MachineLICMBase::AddToLiveIns(MCRegister Reg, MachineLoop *CurLoop) { … }

/// When an instruction is found to only use loop invariant operands that is
/// safe to hoist, this instruction is called to do the dirty work.
void MachineLICMBase::HoistPostRA(MachineInstr *MI, unsigned Def,
                                  MachineLoop *CurLoop,
                                  MachineBasicBlock *CurPreheader) { … }

/// Check if this mbb is guaranteed to execute. If not then a load from this mbb
/// may not be safe to hoist.
bool MachineLICMBase::IsGuaranteedToExecute(MachineBasicBlock *BB,
                                            MachineLoop *CurLoop) { … }

/// Check if \p MI is trivially remateralizable and if it does not have any
/// virtual register uses. Even though rematerializable RA might not actually
/// rematerialize it in this scenario. In that case we do not want to hoist such
/// instruction out of the loop in a belief RA will sink it back if needed.
bool MachineLICMBase::isTriviallyReMaterializable(
    const MachineInstr &MI) const { … }

void MachineLICMBase::EnterScope(MachineBasicBlock *MBB) { … }

void MachineLICMBase::ExitScope(MachineBasicBlock *MBB) { … }

/// Destroy scope for the MBB that corresponds to the given dominator tree node
/// if its a leaf or all of its children are done. Walk up the dominator tree to
/// destroy ancestors which are now done.
void MachineLICMBase::ExitScopeIfDone(MachineDomTreeNode *Node,
    DenseMap<MachineDomTreeNode*, unsigned> &OpenChildren,
    const DenseMap<MachineDomTreeNode*, MachineDomTreeNode*> &ParentMap) { … }

/// Walk the specified loop in the CFG (defined by all blocks dominated by the
/// specified header block, and that are in the current loop) in depth first
/// order w.r.t the DominatorTree. This allows us to visit definitions before
/// uses, allowing us to hoist a loop body in one pass without iteration.
void MachineLICMBase::HoistOutOfLoop(MachineDomTreeNode *HeaderN,
                                     MachineLoop *CurLoop,
                                     MachineBasicBlock *CurPreheader) { … }

static bool isOperandKill(const MachineOperand &MO, MachineRegisterInfo *MRI) { … }

/// Find all virtual register references that are liveout of the preheader to
/// initialize the starting "register pressure". Note this does not count live
/// through (livein but not used) registers.
void MachineLICMBase::InitRegPressure(MachineBasicBlock *BB) { … }

/// Update estimate of register pressure after the specified instruction.
void MachineLICMBase::UpdateRegPressure(const MachineInstr *MI,
                                        bool ConsiderUnseenAsDef) { … }

/// Calculate the additional register pressure that the registers used in MI
/// cause.
///
/// If 'ConsiderSeen' is true, updates 'RegSeen' and uses the information to
/// figure out which usages are live-ins.
/// FIXME: Figure out a way to consider 'RegSeen' from all code paths.
DenseMap<unsigned, int>
MachineLICMBase::calcRegisterCost(const MachineInstr *MI, bool ConsiderSeen,
                                  bool ConsiderUnseenAsDef) { … }

/// Return true if this machine instruction loads from global offset table or
/// constant pool.
static bool mayLoadFromGOTOrConstantPool(MachineInstr &MI) { … }

// This function iterates through all the operands of the input store MI and
// checks that each register operand statisfies isCallerPreservedPhysReg.
// This means, the value being stored and the address where it is being stored
// is constant throughout the body of the function (not including prologue and
// epilogue). When called with an MI that isn't a store, it returns false.
// A future improvement can be to check if the store registers are constant
// throughout the loop rather than throughout the funtion.
static bool isInvariantStore(const MachineInstr &MI,
                             const TargetRegisterInfo *TRI,
                             const MachineRegisterInfo *MRI) { … }

// Return true if the input MI is a copy instruction that feeds an invariant
// store instruction. This means that the src of the copy has to satisfy
// isCallerPreservedPhysReg and atleast one of it's users should satisfy
// isInvariantStore.
static bool isCopyFeedingInvariantStore(const MachineInstr &MI,
                                        const MachineRegisterInfo *MRI,
                                        const TargetRegisterInfo *TRI) { … }

/// Returns true if the instruction may be a suitable candidate for LICM.
/// e.g. If the instruction is a call, then it's obviously not safe to hoist it.
bool MachineLICMBase::IsLICMCandidate(MachineInstr &I, MachineLoop *CurLoop) { … }

/// Returns true if the instruction is loop invariant.
bool MachineLICMBase::IsLoopInvariantInst(MachineInstr &I,
                                          MachineLoop *CurLoop) { … }

/// Return true if the specified instruction is used by a phi node and hoisting
/// it could cause a copy to be inserted.
bool MachineLICMBase::HasLoopPHIUse(const MachineInstr *MI,
                                    MachineLoop *CurLoop) { … }

/// Compute operand latency between a def of 'Reg' and an use in the current
/// loop, return true if the target considered it high.
bool MachineLICMBase::HasHighOperandLatency(MachineInstr &MI, unsigned DefIdx,
                                            Register Reg,
                                            MachineLoop *CurLoop) const { … }

/// Return true if the instruction is marked "cheap" or the operand latency
/// between its def and a use is one or less.
bool MachineLICMBase::IsCheapInstruction(MachineInstr &MI) const { … }

/// Visit BBs from header to current BB, check if hoisting an instruction of the
/// given cost matrix can cause high register pressure.
bool
MachineLICMBase::CanCauseHighRegPressure(const DenseMap<unsigned, int>& Cost,
                                         bool CheapInstr) { … }

/// Traverse the back trace from header to the current block and update their
/// register pressures to reflect the effect of hoisting MI from the current
/// block to the preheader.
void MachineLICMBase::UpdateBackTraceRegPressure(const MachineInstr *MI) { … }

/// Return true if it is potentially profitable to hoist the given loop
/// invariant.
bool MachineLICMBase::IsProfitableToHoist(MachineInstr &MI,
                                          MachineLoop *CurLoop) { … }

/// Unfold a load from the given machineinstr if the load itself could be
/// hoisted. Return the unfolded and hoistable load, or null if the load
/// couldn't be unfolded or if it wouldn't be hoistable.
MachineInstr *MachineLICMBase::ExtractHoistableLoad(MachineInstr *MI,
                                                    MachineLoop *CurLoop) { … }

/// Initialize the CSE map with instructions that are in the current loop
/// preheader that may become duplicates of instructions that are hoisted
/// out of the loop.
void MachineLICMBase::InitCSEMap(MachineBasicBlock *BB) { … }

/// Initialize AllowedToHoistLoads with information about whether invariant
/// loads can be moved outside a given loop
void MachineLICMBase::InitializeLoadsHoistableLoops() { … }

/// Find an instruction amount PrevMIs that is a duplicate of MI.
/// Return this instruction if it's found.
MachineInstr *
MachineLICMBase::LookForDuplicate(const MachineInstr *MI,
                                  std::vector<MachineInstr *> &PrevMIs) { … }

/// Given a LICM'ed instruction, look for an instruction on the preheader that
/// computes the same value. If it's found, do a RAU on with the definition of
/// the existing instruction rather than hoisting the instruction to the
/// preheader.
bool MachineLICMBase::EliminateCSE(
    MachineInstr *MI,
    DenseMap<unsigned, std::vector<MachineInstr *>>::iterator &CI) { … }

/// Return true if the given instruction will be CSE'd if it's hoisted out of
/// the loop.
bool MachineLICMBase::MayCSE(MachineInstr *MI) { … }

/// When an instruction is found to use only loop invariant operands
/// that are safe to hoist, this instruction is called to do the dirty work.
/// It returns true if the instruction is hoisted.
unsigned MachineLICMBase::Hoist(MachineInstr *MI, MachineBasicBlock *Preheader,
                                MachineLoop *CurLoop) { … }

/// Get the preheader for the current loop, splitting a critical edge if needed.
MachineBasicBlock *
MachineLICMBase::getCurPreheader(MachineLoop *CurLoop,
                                 MachineBasicBlock *CurPreheader) { … }

/// Is the target basic block at least "BlockFrequencyRatioThreshold"
/// times hotter than the source basic block.
bool MachineLICMBase::isTgtHotterThanSrc(MachineBasicBlock *SrcBlock,
                                         MachineBasicBlock *TgtBlock) { … }
llvm/llvm/lib/CodeGen/MachineLICM.cpp
