1193323Sed//===---- LatencyPriorityQueue.h - A latency-oriented priority queue ------===// 2193323Sed// 3353358Sdim// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4353358Sdim// See https://llvm.org/LICENSE.txt for license information. 5353358Sdim// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6193323Sed// 7193323Sed//===----------------------------------------------------------------------===// 8193323Sed// 9193323Sed// This file declares the LatencyPriorityQueue class, which is a 10193323Sed// SchedulingPriorityQueue that schedules using latency information to 11193323Sed// reduce the length of the critical path through the basic block. 12193323Sed// 13193323Sed//===----------------------------------------------------------------------===// 14193323Sed 15249423Sdim#ifndef LLVM_CODEGEN_LATENCYPRIORITYQUEUE_H 16249423Sdim#define LLVM_CODEGEN_LATENCYPRIORITYQUEUE_H 17193323Sed 18193323Sed#include "llvm/CodeGen/ScheduleDAG.h" 19341825Sdim#include "llvm/Config/llvm-config.h" 20193323Sed 21193323Sednamespace llvm { 22193323Sed class LatencyPriorityQueue; 23218893Sdim 24193323Sed /// Sorting functions for the Available queue. 25327952Sdim struct latency_sort { 26193323Sed LatencyPriorityQueue *PQ; 27193323Sed explicit latency_sort(LatencyPriorityQueue *pq) : PQ(pq) {} 28218893Sdim 29341825Sdim bool operator()(const SUnit* LHS, const SUnit* RHS) const; 30193323Sed }; 31193323Sed 32193323Sed class LatencyPriorityQueue : public SchedulingPriorityQueue { 33193323Sed // SUnits - The SUnits for the current graph. 34193323Sed std::vector<SUnit> *SUnits; 35218893Sdim 36193323Sed /// NumNodesSolelyBlocking - This vector contains, for every node in the 37193323Sed /// Queue, the number of nodes that the node is the sole unscheduled 38193323Sed /// predecessor for. This is used as a tie-breaker heuristic for better 39193323Sed /// mobility. 40193323Sed std::vector<unsigned> NumNodesSolelyBlocking; 41218893Sdim 42198892Srdivacky /// Queue - The queue. 43208599Srdivacky std::vector<SUnit*> Queue; 44208599Srdivacky latency_sort Picker; 45193323Sed 46208599Srdivacky public: 47208599Srdivacky LatencyPriorityQueue() : Picker(this) { 48193323Sed } 49198892Srdivacky 50276479Sdim bool isBottomUp() const override { return false; } 51218893Sdim 52276479Sdim void initNodes(std::vector<SUnit> &sunits) override { 53193323Sed SUnits = &sunits; 54193323Sed NumNodesSolelyBlocking.resize(SUnits->size(), 0); 55193323Sed } 56193323Sed 57276479Sdim void addNode(const SUnit *SU) override { 58193323Sed NumNodesSolelyBlocking.resize(SUnits->size(), 0); 59193323Sed } 60193323Sed 61276479Sdim void updateNode(const SUnit *SU) override { 62193323Sed } 63193323Sed 64276479Sdim void releaseState() override { 65276479Sdim SUnits = nullptr; 66193323Sed } 67218893Sdim 68193323Sed unsigned getLatency(unsigned NodeNum) const { 69193323Sed assert(NodeNum < (*SUnits).size()); 70199989Srdivacky return (*SUnits)[NodeNum].getHeight(); 71193323Sed } 72218893Sdim 73193323Sed unsigned getNumSolelyBlockNodes(unsigned NodeNum) const { 74193323Sed assert(NodeNum < NumNodesSolelyBlocking.size()); 75193323Sed return NumNodesSolelyBlocking[NodeNum]; 76193323Sed } 77218893Sdim 78276479Sdim bool empty() const override { return Queue.empty(); } 79218893Sdim 80276479Sdim void push(SUnit *U) override; 81218893Sdim 82276479Sdim SUnit *pop() override; 83193323Sed 84276479Sdim void remove(SUnit *SU) override; 85193323Sed 86341825Sdim#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 87341825Sdim LLVM_DUMP_METHOD void dump(ScheduleDAG *DAG) const override; 88341825Sdim#endif 89341825Sdim 90234353Sdim // scheduledNode - As nodes are scheduled, we look to see if there are any 91193323Sed // successor nodes that have a single unscheduled predecessor. If so, that 92193323Sed // single predecessor has a higher priority, since scheduling it will make 93193323Sed // the node available. 94341825Sdim void scheduledNode(SUnit *SU) override; 95193323Sed 96193323Sedprivate: 97193323Sed void AdjustPriorityOfUnscheduledPreds(SUnit *SU); 98193323Sed SUnit *getSingleUnscheduledPred(SUnit *SU); 99193323Sed }; 100193323Sed} 101193323Sed 102193323Sed#endif 103