ModuloSchedule.cpp | Explore in Territory

//===- ModuloSchedule.cpp - Software pipeline schedule expansion ----------===//
//
// 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/ModuloSchedule.h"
#include "llvm/ADT/StringExtras.h"
#include "llvm/Analysis/MemoryLocation.h"
#include "llvm/CodeGen/LiveIntervals.h"
#include "llvm/CodeGen/MachineInstrBuilder.h"
#include "llvm/CodeGen/MachineLoopInfo.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/InitializePasses.h"
#include "llvm/MC/MCContext.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/raw_ostream.h"

#define DEBUG_TYPE …
usingnamespacellvm;

static cl::opt<bool> SwapBranchTargetsMVE(
    "pipeliner-swap-branch-targets-mve", cl::Hidden, cl::init(false),
    cl::desc("Swap target blocks of a conditional branch for MVE expander"));

void ModuloSchedule::print(raw_ostream &OS) { … }

//===----------------------------------------------------------------------===//
// ModuloScheduleExpander implementation
//===----------------------------------------------------------------------===//

/// Return the register values for  the operands of a Phi instruction.
/// This function assume the instruction is a Phi.
static void getPhiRegs(MachineInstr &Phi, MachineBasicBlock *Loop,
                       unsigned &InitVal, unsigned &LoopVal) { … }

/// Return the Phi register value that comes from the incoming block.
static unsigned getInitPhiReg(MachineInstr &Phi, MachineBasicBlock *LoopBB) { … }

/// Return the Phi register value that comes the loop block.
static unsigned getLoopPhiReg(MachineInstr &Phi, MachineBasicBlock *LoopBB) { … }

void ModuloScheduleExpander::expand() { … }

void ModuloScheduleExpander::generatePipelinedLoop() { … }

void ModuloScheduleExpander::cleanup() { … }

/// Generate the pipeline prolog code.
void ModuloScheduleExpander::generateProlog(unsigned LastStage,
                                            MachineBasicBlock *KernelBB,
                                            ValueMapTy *VRMap,
                                            MBBVectorTy &PrologBBs) { … }

/// Generate the pipeline epilog code. The epilog code finishes the iterations
/// that were started in either the prolog or the kernel.  We create a basic
/// block for each stage that needs to complete.
void ModuloScheduleExpander::generateEpilog(
    unsigned LastStage, MachineBasicBlock *KernelBB, MachineBasicBlock *OrigBB,
    ValueMapTy *VRMap, ValueMapTy *VRMapPhi, MBBVectorTy &EpilogBBs,
    MBBVectorTy &PrologBBs) { … }

/// Replace all uses of FromReg that appear outside the specified
/// basic block with ToReg.
static void replaceRegUsesAfterLoop(unsigned FromReg, unsigned ToReg,
                                    MachineBasicBlock *MBB,
                                    MachineRegisterInfo &MRI,
                                    LiveIntervals &LIS) { … }

/// Return true if the register has a use that occurs outside the
/// specified loop.
static bool hasUseAfterLoop(unsigned Reg, MachineBasicBlock *BB,
                            MachineRegisterInfo &MRI) { … }

/// Generate Phis for the specific block in the generated pipelined code.
/// This function looks at the Phis from the original code to guide the
/// creation of new Phis.
void ModuloScheduleExpander::generateExistingPhis(
    MachineBasicBlock *NewBB, MachineBasicBlock *BB1, MachineBasicBlock *BB2,
    MachineBasicBlock *KernelBB, ValueMapTy *VRMap, InstrMapTy &InstrMap,
    unsigned LastStageNum, unsigned CurStageNum, bool IsLast) { … }

/// Generate Phis for the specified block in the generated pipelined code.
/// These are new Phis needed because the definition is scheduled after the
/// use in the pipelined sequence.
void ModuloScheduleExpander::generatePhis(
    MachineBasicBlock *NewBB, MachineBasicBlock *BB1, MachineBasicBlock *BB2,
    MachineBasicBlock *KernelBB, ValueMapTy *VRMap, ValueMapTy *VRMapPhi,
    InstrMapTy &InstrMap, unsigned LastStageNum, unsigned CurStageNum,
    bool IsLast) { … }

/// Remove instructions that generate values with no uses.
/// Typically, these are induction variable operations that generate values
/// used in the loop itself.  A dead instruction has a definition with
/// no uses, or uses that occur in the original loop only.
void ModuloScheduleExpander::removeDeadInstructions(MachineBasicBlock *KernelBB,
                                                    MBBVectorTy &EpilogBBs) { … }

/// For loop carried definitions, we split the lifetime of a virtual register
/// that has uses past the definition in the next iteration. A copy with a new
/// virtual register is inserted before the definition, which helps with
/// generating a better register assignment.
///
///   v1 = phi(a, v2)     v1 = phi(a, v2)
///   v2 = phi(b, v3)     v2 = phi(b, v3)
///   v3 = ..             v4 = copy v1
///   .. = V1             v3 = ..
///                       .. = v4
void ModuloScheduleExpander::splitLifetimes(MachineBasicBlock *KernelBB,
                                            MBBVectorTy &EpilogBBs) { … }

/// Remove the incoming block from the Phis in a basic block.
static void removePhis(MachineBasicBlock *BB, MachineBasicBlock *Incoming) { … }

/// Create branches from each prolog basic block to the appropriate epilog
/// block.  These edges are needed if the loop ends before reaching the
/// kernel.
void ModuloScheduleExpander::addBranches(MachineBasicBlock &PreheaderBB,
                                         MBBVectorTy &PrologBBs,
                                         MachineBasicBlock *KernelBB,
                                         MBBVectorTy &EpilogBBs,
                                         ValueMapTy *VRMap) { … }

/// Return true if we can compute the amount the instruction changes
/// during each iteration. Set Delta to the amount of the change.
bool ModuloScheduleExpander::computeDelta(MachineInstr &MI, unsigned &Delta) { … }

/// Update the memory operand with a new offset when the pipeliner
/// generates a new copy of the instruction that refers to a
/// different memory location.
void ModuloScheduleExpander::updateMemOperands(MachineInstr &NewMI,
                                               MachineInstr &OldMI,
                                               unsigned Num) { … }

/// Clone the instruction for the new pipelined loop and update the
/// memory operands, if needed.
MachineInstr *ModuloScheduleExpander::cloneInstr(MachineInstr *OldMI,
                                                 unsigned CurStageNum,
                                                 unsigned InstStageNum) { … }

/// Clone the instruction for the new pipelined loop. If needed, this
/// function updates the instruction using the values saved in the
/// InstrChanges structure.
MachineInstr *ModuloScheduleExpander::cloneAndChangeInstr(
    MachineInstr *OldMI, unsigned CurStageNum, unsigned InstStageNum) { … }

/// Update the machine instruction with new virtual registers.  This
/// function may change the definitions and/or uses.
void ModuloScheduleExpander::updateInstruction(MachineInstr *NewMI,
                                               bool LastDef,
                                               unsigned CurStageNum,
                                               unsigned InstrStageNum,
                                               ValueMapTy *VRMap) { … }

/// Return the instruction in the loop that defines the register.
/// If the definition is a Phi, then follow the Phi operand to
/// the instruction in the loop.
MachineInstr *ModuloScheduleExpander::findDefInLoop(unsigned Reg) { … }

/// Return the new name for the value from the previous stage.
unsigned ModuloScheduleExpander::getPrevMapVal(
    unsigned StageNum, unsigned PhiStage, unsigned LoopVal, unsigned LoopStage,
    ValueMapTy *VRMap, MachineBasicBlock *BB) { … }

/// Rewrite the Phi values in the specified block to use the mappings
/// from the initial operand. Once the Phi is scheduled, we switch
/// to using the loop value instead of the Phi value, so those names
/// do not need to be rewritten.
void ModuloScheduleExpander::rewritePhiValues(MachineBasicBlock *NewBB,
                                              unsigned StageNum,
                                              ValueMapTy *VRMap,
                                              InstrMapTy &InstrMap) { … }

/// Rewrite a previously scheduled instruction to use the register value
/// from the new instruction. Make sure the instruction occurs in the
/// basic block, and we don't change the uses in the new instruction.
void ModuloScheduleExpander::rewriteScheduledInstr(
    MachineBasicBlock *BB, InstrMapTy &InstrMap, unsigned CurStageNum,
    unsigned PhiNum, MachineInstr *Phi, unsigned OldReg, unsigned NewReg,
    unsigned PrevReg) { … }

bool ModuloScheduleExpander::isLoopCarried(MachineInstr &Phi) { … }

//===----------------------------------------------------------------------===//
// PeelingModuloScheduleExpander implementation
//===----------------------------------------------------------------------===//
// This is a reimplementation of ModuloScheduleExpander that works by creating
// a fully correct steady-state kernel and peeling off the prolog and epilogs.
//===----------------------------------------------------------------------===//

namespace {
// Remove any dead phis in MBB. Dead phis either have only one block as input
// (in which case they are the identity) or have no uses.
void EliminateDeadPhis(MachineBasicBlock *MBB, MachineRegisterInfo &MRI,
                       LiveIntervals *LIS, bool KeepSingleSrcPhi = false) { … }

/// Rewrites the kernel block in-place to adhere to the given schedule.
/// KernelRewriter holds all of the state required to perform the rewriting.
class KernelRewriter { … };
} // namespace

KernelRewriter::KernelRewriter(MachineLoop &L, ModuloSchedule &S,
                               MachineBasicBlock *LoopBB, LiveIntervals *LIS)
    : … { … }

void KernelRewriter::rewrite() { … }

Register KernelRewriter::remapUse(Register Reg, MachineInstr &MI) { … }

Register KernelRewriter::phi(Register LoopReg, std::optional<Register> InitReg,
                             const TargetRegisterClass *RC) { … }

Register KernelRewriter::undef(const TargetRegisterClass *RC) { … }

namespace {
/// Describes an operand in the kernel of a pipelined loop. Characteristics of
/// the operand are discovered, such as how many in-loop PHIs it has to jump
/// through and defaults for these phis.
class KernelOperandInfo { … };
} // namespace

MachineBasicBlock *
PeelingModuloScheduleExpander::peelKernel(LoopPeelDirection LPD) { … }

void PeelingModuloScheduleExpander::filterInstructions(MachineBasicBlock *MB,
                                                       int MinStage) { … }

void PeelingModuloScheduleExpander::moveStageBetweenBlocks(
    MachineBasicBlock *DestBB, MachineBasicBlock *SourceBB, unsigned Stage) { … }

Register
PeelingModuloScheduleExpander::getPhiCanonicalReg(MachineInstr *CanonicalPhi,
                                                  MachineInstr *Phi) { … }

void PeelingModuloScheduleExpander::peelPrologAndEpilogs() { … }

MachineBasicBlock *PeelingModuloScheduleExpander::CreateLCSSAExitingBlock() { … }

Register
PeelingModuloScheduleExpander::getEquivalentRegisterIn(Register Reg,
                                                       MachineBasicBlock *BB) { … }

void PeelingModuloScheduleExpander::rewriteUsesOf(MachineInstr *MI) { … }

void PeelingModuloScheduleExpander::fixupBranches() { … }

void PeelingModuloScheduleExpander::rewriteKernel() { … }

void PeelingModuloScheduleExpander::expand() { … }

void PeelingModuloScheduleExpander::validateAgainstModuloScheduleExpander() { … }

MachineInstr *ModuloScheduleExpanderMVE::cloneInstr(MachineInstr *OldMI) { … }

/// Create a dedicated exit for Loop. Exit is the original exit for Loop.
/// If it is already dedicated exit, return it. Otherwise, insert a new
/// block between them and return the new block.
static MachineBasicBlock *createDedicatedExit(MachineBasicBlock *Loop,
                                              MachineBasicBlock *Exit) { … }

/// Insert branch code into the end of MBB. It branches to GreaterThan if the
/// remaining trip count for instructions in LastStage0Insts is greater than
/// RequiredTC, and to Otherwise otherwise.
void ModuloScheduleExpanderMVE::insertCondBranch(MachineBasicBlock &MBB,
                                                 int RequiredTC,
                                                 InstrMapTy &LastStage0Insts,
                                                 MachineBasicBlock &GreaterThan,
                                                 MachineBasicBlock &Otherwise) { … }

/// Generate a pipelined loop that is unrolled by using MVE algorithm and any
/// other necessary blocks. The control flow is modified to execute the
/// pipelined loop if the trip count satisfies the condition, otherwise the
/// original loop. The original loop is also used to execute the remainder
/// iterations which occur due to unrolling.
void ModuloScheduleExpanderMVE::generatePipelinedLoop() { … }

/// Replace MI's use operands according to the maps.
void ModuloScheduleExpanderMVE::updateInstrUse(
    MachineInstr *MI, int StageNum, int PhaseNum,
    SmallVectorImpl<ValueMapTy> &CurVRMap,
    SmallVectorImpl<ValueMapTy> *PrevVRMap) { … }

/// Return a phi if Reg is referenced by the phi.
/// canApply() guarantees that at most only one such phi exists.
static MachineInstr *getLoopPhiUser(Register Reg, MachineBasicBlock *Loop) { … }

/// Generate phis for registers defined by OrigMI.
void ModuloScheduleExpanderMVE::generatePhi(
    MachineInstr *OrigMI, int UnrollNum,
    SmallVectorImpl<ValueMapTy> &PrologVRMap,
    SmallVectorImpl<ValueMapTy> &KernelVRMap,
    SmallVectorImpl<ValueMapTy> &PhiVRMap) { … }

static void replacePhiSrc(MachineInstr &Phi, Register OrigReg, Register NewReg,
                          MachineBasicBlock *NewMBB) { … }

/// Generate phis that merge values from multiple routes
void ModuloScheduleExpanderMVE::mergeRegUsesAfterPipeline(Register OrigReg,
                                                          Register NewReg) { … }

void ModuloScheduleExpanderMVE::generateProlog(
    SmallVectorImpl<ValueMapTy> &PrologVRMap) { … }

void ModuloScheduleExpanderMVE::generateKernel(
    SmallVectorImpl<ValueMapTy> &PrologVRMap,
    SmallVectorImpl<ValueMapTy> &KernelVRMap, InstrMapTy &LastStage0Insts) { … }

void ModuloScheduleExpanderMVE::generateEpilog(
    SmallVectorImpl<ValueMapTy> &KernelVRMap,
    SmallVectorImpl<ValueMapTy> &EpilogVRMap, InstrMapTy &LastStage0Insts) { … }

/// Calculate the number of unroll required and set it to NumUnroll
void ModuloScheduleExpanderMVE::calcNumUnroll() { … }

/// Create new virtual registers for definitions of NewMI and update NewMI.
/// If the definitions are referenced after the pipelined loop, phis are
/// created to merge with other routes.
void ModuloScheduleExpanderMVE::updateInstrDef(MachineInstr *NewMI,
                                               ValueMapTy &VRMap,
                                               bool LastDef) { … }

void ModuloScheduleExpanderMVE::expand() { … }

/// Check if ModuloScheduleExpanderMVE can be applied to L
bool ModuloScheduleExpanderMVE::canApply(MachineLoop &L) { … }

//===----------------------------------------------------------------------===//
// ModuloScheduleTestPass implementation
//===----------------------------------------------------------------------===//
// This pass constructs a ModuloSchedule from its module and runs
// ModuloScheduleExpander.
//
// The module is expected to contain a single-block analyzable loop.
// The total order of instructions is taken from the loop as-is.
// Instructions are expected to be annotated with a PostInstrSymbol.
// This PostInstrSymbol must have the following format:
//  "Stage=%d Cycle=%d".
//===----------------------------------------------------------------------===//

namespace {
class ModuloScheduleTest : public MachineFunctionPass { … };
} // namespace

char ModuloScheduleTest::ID = …;

INITIALIZE_PASS_BEGIN(ModuloScheduleTest, "modulo-schedule-test",
                      "Modulo Schedule test pass", false, false)
INITIALIZE_PASS_DEPENDENCY(MachineLoopInfoWrapperPass)
INITIALIZE_PASS_DEPENDENCY(LiveIntervalsWrapperPass)
INITIALIZE_PASS_END(ModuloScheduleTest, "modulo-schedule-test",
                    "Modulo Schedule test pass", false, false)

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

static void parseSymbolString(StringRef S, int &Cycle, int &Stage) { … }

void ModuloScheduleTest::runOnLoop(MachineFunction &MF, MachineLoop &L) { … }

//===----------------------------------------------------------------------===//
// ModuloScheduleTestAnnotater implementation
//===----------------------------------------------------------------------===//

void ModuloScheduleTestAnnotater::annotate() { … }
llvm/llvm/lib/CodeGen/ModuloSchedule.cpp
