llvm/llvm/include/llvm/CodeGen/WindowScheduler.h

//======----------- 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/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 {

enum WindowSchedulingFlag { … };

/// The main class in the implementation of the target independent window
/// scheduler.
class WindowScheduler { … };
} // namespace llvm
#endif