WindowScheduler.h

Go to the documentation of this file.

//======----------- 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 concept of the window algorithm was first unveiled in Steven Muchnick's
// book, "Advanced Compiler Design And Implementation", and later elaborated
// upon in Venkatraman Govindaraju's report, "Implementation of Software
// Pipelining Using Window Scheduling".
//
// The window algorithm can be perceived as a modulo scheduling algorithm with a
// stage count of 2. It boasts a higher scheduling success rate in targets with
// severe resource conflicts when compared to the classic Swing Modulo
// Scheduling (SMS) algorithm. To align with the LLVM scheduling framework, we
// have enhanced the original window algorithm. The primary steps are as
// follows:
//
// 1. Instead of duplicating the original MBB twice as mentioned in the
// literature, we copy it three times, generating TripleMBB and the
// corresponding TripleDAG.
//
// 2. We establish a scheduling window on TripleMBB and execute list scheduling
// within it.
//
// 3. After multiple list scheduling, we select the best outcome and expand it
// into the final scheduling result.
//
// To cater to the needs of various targets, we have developed the window
// scheduler in a form that is easily derivable. We recommend employing this
// algorithm in targets with severe resource conflicts, and it can be utilized
// either before or after the Register Allocator (RA).
//
// The default implementation provided here is before RA. If it is to be used
// after RA, certain critical algorithm functions will need to be derived.
//
//===----------------------------------------------------------------------===//
#ifndef LLVM_CODEGEN_WINDOWSCHEDULER_H
#define LLVM_CODEGEN_WINDOWSCHEDULER_H
 
#include "llvm/ADT/DenseSet.h"
#include "llvm/CodeGen/MachineLoopInfo.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/CodeGen/MachineScheduler.h"
#include "llvm/CodeGen/ScheduleDAGInstrs.h"
#include "llvm/CodeGen/TargetSubtargetInfo.h"
 
namespace llvm {
 
class MachineDominatorTree;
 
enum WindowSchedulingFlag {
  WS_Off,  /// Turn off window algorithm.
  WS_On,   /// Use window algorithm after SMS algorithm fails.
  WS_Force /// Use window algorithm instead of SMS algorithm.
};
 
/// TriCloneInfo describes an MI clone in TripleMBB: the original MI it was
/// cloned from and the index of the copy (0, 1, or 2) it belongs to.
struct TriCloneInfo {
  MachineInstr *Ori = nullptr;
  unsigned Copy = 0;
};
 
/// The main class in the implementation of the target independent window
/// scheduler.
class LLVM_ABI WindowScheduler {
protected:
  MachineSchedContext *Context = nullptr;
  MachineFunction *MF = nullptr;
  MachineBasicBlock *MBB = nullptr;
  MachineLoop &Loop;
  const TargetSubtargetInfo *Subtarget = nullptr;
  const TargetInstrInfo *TII = nullptr;
  const TargetRegisterInfo *TRI = nullptr;
  MachineRegisterInfo *MRI = nullptr;
  MachineDominatorTree *MDT = nullptr;
 
  /// To innovatively identify the dependencies between MIs across two trips, we
  /// construct a DAG for a new MBB, which is created by copying the original
  /// MBB three times. We refer to this new MBB as 'TripleMBB' and the
  /// corresponding DAG as 'TripleDAG'.
  /// If the dependencies are more than two trips, we avoid applying window
  /// algorithm by identifying successive phis in the old MBB.
  std::unique_ptr<ScheduleDAGInstrs> TripleDAG;
  /// OriMIs keeps the MIs removed from the original MBB.
  SmallVector<MachineInstr *> OriMIs;
  /// TriMIs keeps the MIs of TripleMBB, which is used to restore TripleMBB.
  SmallVector<MachineInstr *> TriMIs;
  /// TriToOri keeps the mappings between the MI clones in TripleMBB and the
  /// information about their original MI and copy index.
  DenseMap<MachineInstr *, TriCloneInfo> TriToOri;
  /// OriToCycle keeps the mappings between the original MI and its issue cycle.
  DenseMap<MachineInstr *, int> OriToCycle;
  /// LoopCarriedMemDeps keeps ordered pairs (Pred, Succ) of original memory MIs
  /// such that the iteration-N access Pred must be ordered before the
  /// iteration-(N+1) access Succ.
  DenseSet<std::pair<MachineInstr *, MachineInstr *>> LoopCarriedMemDeps;
  /// MemDepEdgeFailed is set when enforcing a loop-carried memory dependence as
  /// an artificial DAG edge would have created a cycle, so the edge could not
  /// be added. In that case the current window must be abandoned, as its
  /// schedule would not honor the dependence.
  bool MemDepEdgeFailed = false;
  /// SchedResult keeps the result of each list scheduling, and the format of
  /// the tuple is <MI pointer, Cycle, Stage, Order ID>.
  SmallVector<std::tuple<MachineInstr *, int, int, int>, 256> SchedResult;
  /// SchedPhiNum records the number of phi in the original MBB, and the
  /// scheduling starts with MI after phis.
  unsigned SchedPhiNum = 0;
  /// SchedInstrNum records the MIs involved in scheduling in the original MBB,
  /// excluding debug instructions.
  unsigned SchedInstrNum = 0;
  /// BestII and BestOffset record the characteristics of the best scheduling
  /// result and are used together with SchedResult as the final window
  /// scheduling result.
  unsigned BestII = UINT_MAX;
  unsigned BestOffset = 0;
  /// BaseII is the II obtained when the window offset is SchedPhiNum. This
  /// offset is the initial position of the sliding window.
  unsigned BaseII = 0;
 
public:
  WindowScheduler(MachineSchedContext *C, MachineLoop &ML,
                  MachineDominatorTree *MDT = nullptr);
  virtual ~WindowScheduler() = default;
 
  bool run();
 
protected:
  /// Two types of ScheduleDAGs are needed, one for creating dependency graphs
  /// only, and the other for list scheduling as determined by the target.
  virtual ScheduleDAGInstrs *
  createMachineScheduler(bool OnlyBuildGraph = false);
  /// Initializes the algorithm and determines if it can be executed.
  virtual bool initialize();
  /// Add some related processing before running window scheduling.
  virtual void preProcess();
  /// Detect loop-carried memory dependences in the original MBB that must be
  /// preserved across loop iterations. This must run on the live MBB before
  /// backupMBB(), as it analyzes the induction recurrence of memory accesses.
  /// The hazardous pairs of original MIs are recorded in LoopCarriedMemDeps.
  void collectLoopCarriedMemDeps();
  /// Add some related processing after running window scheduling.
  virtual void postProcess();
  /// Back up the MIs in the original MBB and remove them from MBB.
  void backupMBB();
  /// Erase the MIs in current MBB and restore the original MIs.
  void restoreMBB();
  /// Make three copies of the original MBB to generate a new TripleMBB.
  virtual void generateTripleMBB();
  /// Restore the order of MIs in TripleMBB after each list scheduling.
  virtual void restoreTripleMBB();
  /// Give the folding position in the window algorithm, where different
  /// heuristics can be used. It determines the performance and compilation time
  /// of the algorithm.
  virtual SmallVector<unsigned> getSearchIndexes(unsigned SearchNum,
                                                 unsigned SearchRatio);
  /// Calculate MIs execution cycle after list scheduling.
  virtual int calculateMaxCycle(ScheduleDAGInstrs &DAG, unsigned Offset);
  /// Calculate the stall cycle between two trips after list scheduling.
  virtual int calculateStallCycle(unsigned Offset, int MaxCycle);
  /// Analyzes the II value after each list scheduling.
  virtual unsigned analyseII(ScheduleDAGInstrs &DAG, unsigned Offset);
  /// Phis are scheduled separately after each list scheduling.
  virtual void schedulePhi(int Offset, unsigned &II);
  /// Get the final issue order of all scheduled MIs including phis.
  DenseMap<MachineInstr *, int> getIssueOrder(unsigned Offset, unsigned II);
  /// Update the scheduling result after each list scheduling.
  virtual void updateScheduleResult(unsigned Offset, unsigned II);
  /// Check whether the final result of window scheduling is valid.
  virtual bool isScheduleValid() { return BestOffset != SchedPhiNum; }
  /// Using the scheduling infrastructure to expand the results of window
  /// scheduling. It is usually necessary to add prologue and epilogue MBBs.
  virtual void expand();
  /// Update the live intervals for all registers used within MBB.
  virtual void updateLiveIntervals();
  /// Estimate a II value at which all MIs will be scheduled successfully.
  int getEstimatedII(ScheduleDAGInstrs &DAG);
  /// Gets the iterator range of MIs in the scheduling window.
  iterator_range<MachineBasicBlock::iterator> getScheduleRange(unsigned Offset,
                                                               unsigned Num);
  /// Get the issue cycle of the new MI based on the cycle of the original MI.
  int getOriCycle(MachineInstr *NewMI);
  /// Get the original MI from which the new MI is cloned.
  MachineInstr *getOriMI(MachineInstr *NewMI);
  /// Get the scheduling stage, where the stage of the new MI is identical to
  /// the original MI.
  unsigned getOriStage(MachineInstr *OriMI, unsigned Offset);
  /// Gets the register in phi which is generated from the current MBB.
  Register getAntiRegister(MachineInstr *Phi);
};
} // namespace llvm
#endif