llvm/llvm/lib/CodeGen/WindowScheduler.cpp

//======----------- WindowScheduler.cpp - window scheduler -------------======//
//
// 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
//
//===----------------------------------------------------------------------===//
//
// An implementation of the Window Scheduling software pipelining algorithm.
//
// The fundamental concept of the window scheduling algorithm involves folding
// the original MBB at a specific position, followed by list scheduling on the
// folded MIs. The optimal scheduling result is then chosen from various folding
// positions as the final scheduling outcome.
//
// The primary challenge in this algorithm lies in generating the folded MIs and
// establishing their dependencies. We have innovatively employed a new MBB,
// created by copying the original MBB three times, known as TripleMBB. This
// TripleMBB enables the convenient implementation of MI folding and dependency
// establishment. To facilitate the algorithm's implementation, we have also
// devised data structures such as OriMIs, TriMIs, TriToOri, and OriToCycle.
//
// Another challenge in the algorithm is the scheduling of phis. Semantically,
// it is difficult to place the phis in the window and perform list scheduling.
// Therefore, we schedule these phis separately after each list scheduling.
//
// The provided implementation is designed for use before the Register Allocator
// (RA). If the target requires implementation after RA, it is recommended to
// reimplement analyseII(), schedulePhi(), and expand(). Additionally,
// target-specific logic can be added in initialize(), preProcess(), and
// postProcess().
//
// Lastly, it is worth mentioning that getSearchIndexes() is an important
// function. We have experimented with more complex heuristics on downstream
// target and achieved favorable results.
//
//===----------------------------------------------------------------------===//
#include "llvm/CodeGen/WindowScheduler.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/CodeGen/LiveIntervals.h"
#include "llvm/CodeGen/MachineLoopInfo.h"
#include "llvm/CodeGen/MachinePipeliner.h"
#include "llvm/CodeGen/ModuloSchedule.h"
#include "llvm/CodeGen/TargetPassConfig.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/TimeProfiler.h"

usingnamespacellvm;

#define DEBUG_TYPE …

namespace … // namespace

// WindowIILimit serves as an indicator of abnormal scheduling results and could
// potentially be referenced by the derived target window scheduler.
cl::opt<unsigned>
    WindowIILimit("window-ii-limit",
                  cl::desc("The upper limit of II in the window algorithm."),
                  cl::Hidden, cl::init(1000));

WindowScheduler::WindowScheduler(MachineSchedContext *C, MachineLoop &ML)
    : … { … }

bool WindowScheduler::run() { … }

ScheduleDAGInstrs *
WindowScheduler::createMachineScheduler(bool OnlyBuildGraph) { … }

bool WindowScheduler::initialize() { … }

void WindowScheduler::preProcess() { … }

void WindowScheduler::postProcess() { … }

void WindowScheduler::backupMBB() { … }

void WindowScheduler::restoreMBB() { … }

void WindowScheduler::generateTripleMBB() { … }

void WindowScheduler::restoreTripleMBB() { … }

SmallVector<unsigned> WindowScheduler::getSearchIndexes(unsigned SearchNum,
                                                        unsigned SearchRatio) { … }

int WindowScheduler::getEstimatedII(ScheduleDAGInstrs &DAG) { … }

int WindowScheduler::calculateMaxCycle(ScheduleDAGInstrs &DAG,
                                       unsigned Offset) { … }

// By utilizing TripleDAG, we can easily establish dependencies between A and B.
// Based on the MaxCycle and the issue cycle of A and B, we can determine
// whether it is necessary to add a stall cycle. This is because, without
// inserting the stall cycle, the latency constraint between A and B cannot be
// satisfied. The details are as follows:
//
// New MBB:
// ========================================
//                 < Phis >
// ========================================     (sliding direction)
// MBB copy 1                                            |
//                                                       V
//
// ~~~~~~~~~~~~~~~~~~~|~~~~~~~~~~~~~~~~~~~~  ----schedule window-----
//                    |                                  |
// ===================V====================              |
// MBB copy 2      < MI B >                              |
//                                                       |
//                 < MI A >                              V
// ~~~~~~~~~~~~~~~~~~~:~~~~~~~~~~~~~~~~~~~~  ------------------------
//                    :
// ===================V====================
// MBB copy 3      < MI B'>
//
//
//
//
// ========================================
//              < Terminators >
// ========================================
int WindowScheduler::calculateStallCycle(unsigned Offset, int MaxCycle) { … }

unsigned WindowScheduler::analyseII(ScheduleDAGInstrs &DAG, unsigned Offset) { … }

void WindowScheduler::schedulePhi(int Offset, unsigned &II) { … }

DenseMap<MachineInstr *, int> WindowScheduler::getIssueOrder(unsigned Offset,
                                                             unsigned II) { … }

void WindowScheduler::updateScheduleResult(unsigned Offset, unsigned II) { … }

void WindowScheduler::expand() { … }

void WindowScheduler::updateLiveIntervals() { … }

iterator_range<MachineBasicBlock::iterator>
WindowScheduler::getScheduleRange(unsigned Offset, unsigned Num) { … }

int WindowScheduler::getOriCycle(MachineInstr *NewMI) { … }

MachineInstr *WindowScheduler::getOriMI(MachineInstr *NewMI) { … }

unsigned WindowScheduler::getOriStage(MachineInstr *OriMI, unsigned Offset) { … }

Register WindowScheduler::getAntiRegister(MachineInstr *Phi) { … }