ShrinkWrap.cpp | Explore in Territory

//===- ShrinkWrap.cpp - Compute safe point for prolog/epilog insertion ----===//
//
// 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 looks for safe point where the prologue and epilogue can be
// inserted.
// The safe point for the prologue (resp. epilogue) is called Save
// (resp. Restore).
// A point is safe for prologue (resp. epilogue) if and only if
// it 1) dominates (resp. post-dominates) all the frame related operations and
// between 2) two executions of the Save (resp. Restore) point there is an
// execution of the Restore (resp. Save) point.
//
// For instance, the following points are safe:
// for (int i = 0; i < 10; ++i) {
//   Save
//   ...
//   Restore
// }
// Indeed, the execution looks like Save -> Restore -> Save -> Restore ...
// And the following points are not:
// for (int i = 0; i < 10; ++i) {
//   Save
//   ...
// }
// for (int i = 0; i < 10; ++i) {
//   ...
//   Restore
// }
// Indeed, the execution looks like Save -> Save -> ... -> Restore -> Restore.
//
// This pass also ensures that the safe points are 3) cheaper than the regular
// entry and exits blocks.
//
// Property #1 is ensured via the use of MachineDominatorTree and
// MachinePostDominatorTree.
// Property #2 is ensured via property #1 and MachineLoopInfo, i.e., both
// points must be in the same loop.
// Property #3 is ensured via the MachineBlockFrequencyInfo.
//
// If this pass found points matching all these properties, then
// MachineFrameInfo is updated with this information.
//
//===----------------------------------------------------------------------===//

#include "llvm/ADT/BitVector.h"
#include "llvm/ADT/PostOrderIterator.h"
#include "llvm/ADT/SetVector.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/CFG.h"
#include "llvm/Analysis/ValueTracking.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/MachineOperand.h"
#include "llvm/CodeGen/MachineOptimizationRemarkEmitter.h"
#include "llvm/CodeGen/MachinePostDominators.h"
#include "llvm/CodeGen/RegisterClassInfo.h"
#include "llvm/CodeGen/RegisterScavenging.h"
#include "llvm/CodeGen/TargetFrameLowering.h"
#include "llvm/CodeGen/TargetInstrInfo.h"
#include "llvm/CodeGen/TargetLowering.h"
#include "llvm/CodeGen/TargetRegisterInfo.h"
#include "llvm/CodeGen/TargetSubtargetInfo.h"
#include "llvm/IR/Attributes.h"
#include "llvm/IR/Function.h"
#include "llvm/InitializePasses.h"
#include "llvm/MC/MCAsmInfo.h"
#include "llvm/Pass.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Target/TargetMachine.h"
#include <cassert>
#include <cstdint>
#include <memory>

usingnamespacellvm;

#define DEBUG_TYPE …

STATISTIC(NumFunc, "Number of functions");
STATISTIC(NumCandidates, "Number of shrink-wrapping candidates");
STATISTIC(NumCandidatesDropped,
          "Number of shrink-wrapping candidates dropped because of frequency");

static cl::opt<cl::boolOrDefault>
EnableShrinkWrapOpt("enable-shrink-wrap", cl::Hidden,
                    cl::desc("enable the shrink-wrapping pass"));
static cl::opt<bool> EnablePostShrinkWrapOpt(
    "enable-shrink-wrap-region-split", cl::init(true), cl::Hidden,
    cl::desc("enable splitting of the restore block if possible"));

namespace {

/// Class to determine where the safe point to insert the
/// prologue and epilogue are.
/// Unlike the paper from Fred C. Chow, PLDI'88, that introduces the
/// shrink-wrapping term for prologue/epilogue placement, this pass
/// does not rely on expensive data-flow analysis. Instead we use the
/// dominance properties and loop information to decide which point
/// are safe for such insertion.
class ShrinkWrap : public MachineFunctionPass { … };

} // end anonymous namespace

char ShrinkWrap::ID = …;

char &llvm::ShrinkWrapID = …;

INITIALIZE_PASS_BEGIN(ShrinkWrap, DEBUG_TYPE, "Shrink Wrap Pass", false, false)
INITIALIZE_PASS_DEPENDENCY(MachineBlockFrequencyInfoWrapperPass)
INITIALIZE_PASS_DEPENDENCY(MachineDominatorTreeWrapperPass)
INITIALIZE_PASS_DEPENDENCY(MachinePostDominatorTreeWrapperPass)
INITIALIZE_PASS_DEPENDENCY(MachineLoopInfoWrapperPass)
INITIALIZE_PASS_DEPENDENCY(MachineOptimizationRemarkEmitterPass)
INITIALIZE_PASS_END(ShrinkWrap, DEBUG_TYPE, "Shrink Wrap Pass", false, false)

bool ShrinkWrap::useOrDefCSROrFI(const MachineInstr &MI, RegScavenger *RS,
                                 bool StackAddressUsed) const { … }

/// Helper function to find the immediate (post) dominator.
template <typename ListOfBBs, typename DominanceAnalysis>
static MachineBasicBlock *FindIDom(MachineBasicBlock &Block, ListOfBBs BBs,
                                   DominanceAnalysis &Dom, bool Strict = true) { … }

static bool isAnalyzableBB(const TargetInstrInfo &TII,
                           MachineBasicBlock &Entry) { … }

/// Determines if any predecessor of MBB is on the path from block that has use
/// or def of CSRs/FI to MBB.
/// ReachableByDirty: All blocks reachable from block that has use or def of
/// CSR/FI.
static bool
hasDirtyPred(const DenseSet<const MachineBasicBlock *> &ReachableByDirty,
             const MachineBasicBlock &MBB) { … }

/// Derives the list of all the basic blocks reachable from MBB.
static void markAllReachable(DenseSet<const MachineBasicBlock *> &Visited,
                             const MachineBasicBlock &MBB) { … }

/// Collect blocks reachable by use or def of CSRs/FI.
static void collectBlocksReachableByDirty(
    const DenseSet<const MachineBasicBlock *> &DirtyBBs,
    DenseSet<const MachineBasicBlock *> &ReachableByDirty) { … }

/// \return true if there is a clean path from SavePoint to the original
/// Restore.
static bool
isSaveReachableThroughClean(const MachineBasicBlock *SavePoint,
                            ArrayRef<MachineBasicBlock *> CleanPreds) { … }

/// This function updates the branches post restore point split.
///
/// Restore point has been split.
/// Old restore point: MBB
/// New restore point: NMBB
/// Any basic block(say BBToUpdate) which had a fallthrough to MBB
/// previously should
/// 1. Fallthrough to NMBB iff NMBB is inserted immediately above MBB in the
/// block layout OR
/// 2. Branch unconditionally to NMBB iff NMBB is inserted at any other place.
static void updateTerminator(MachineBasicBlock *BBToUpdate,
                             MachineBasicBlock *NMBB,
                             const TargetInstrInfo *TII) { … }

/// This function splits the restore point and returns new restore point/BB.
///
/// DirtyPreds: Predessors of \p MBB that are ReachableByDirty
///
/// Decision has been made to split the restore point.
/// old restore point: \p MBB
/// new restore point: \p NMBB
/// This function makes the necessary block layout changes so that
/// 1. \p NMBB points to \p MBB unconditionally
/// 2. All dirtyPreds that previously pointed to \p MBB point to \p NMBB
static MachineBasicBlock *
tryToSplitRestore(MachineBasicBlock *MBB,
                  ArrayRef<MachineBasicBlock *> DirtyPreds,
                  const TargetInstrInfo *TII) { … }

/// This function undoes the restore point split done earlier.
///
/// DirtyPreds: All predecessors of \p NMBB that are ReachableByDirty.
///
/// Restore point was split and the change needs to be unrolled. Make necessary
/// changes to reset restore point from \p NMBB to \p MBB.
static void rollbackRestoreSplit(MachineFunction &MF, MachineBasicBlock *NMBB,
                                 MachineBasicBlock *MBB,
                                 ArrayRef<MachineBasicBlock *> DirtyPreds,
                                 const TargetInstrInfo *TII) { … }

// A block is deemed fit for restore point split iff there exist
// 1. DirtyPreds - preds of CurRestore reachable from use or def of CSR/FI
// 2. CleanPreds - preds of CurRestore that arent DirtyPreds
bool ShrinkWrap::checkIfRestoreSplittable(
    const MachineBasicBlock *CurRestore,
    const DenseSet<const MachineBasicBlock *> &ReachableByDirty,
    SmallVectorImpl<MachineBasicBlock *> &DirtyPreds,
    SmallVectorImpl<MachineBasicBlock *> &CleanPreds,
    const TargetInstrInfo *TII, RegScavenger *RS) { … }

bool ShrinkWrap::postShrinkWrapping(bool HasCandidate, MachineFunction &MF,
                                    RegScavenger *RS) { … }

void ShrinkWrap::updateSaveRestorePoints(MachineBasicBlock &MBB,
                                         RegScavenger *RS) { … }

static bool giveUpWithRemarks(MachineOptimizationRemarkEmitter *ORE,
                              StringRef RemarkName, StringRef RemarkMessage,
                              const DiagnosticLocation &Loc,
                              const MachineBasicBlock *MBB) { … }

bool ShrinkWrap::performShrinkWrapping(
    const ReversePostOrderTraversal<MachineBasicBlock *> &RPOT,
    RegScavenger *RS) { … }

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

bool ShrinkWrap::isShrinkWrapEnabled(const MachineFunction &MF) { … }
llvm/llvm/lib/CodeGen/ShrinkWrap.cpp
