1ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman//===---- LatencyPriorityQueue.h - A latency-oriented priority queue ------===// 2ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman// 3ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman// The LLVM Compiler Infrastructure 4ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman// 5ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman// This file is distributed under the University of Illinois Open Source 6ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman// License. See LICENSE.TXT for details. 7ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman// 8ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman//===----------------------------------------------------------------------===// 9ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman// 10ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman// This file declares the LatencyPriorityQueue class, which is a 11ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman// SchedulingPriorityQueue that schedules using latency information to 12ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman// reduce the length of the critical path through the basic block. 13ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman// 14ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman//===----------------------------------------------------------------------===// 15ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman 16674be02d525d4e24bc6943ed9274958c580bcfbcJakub Staszak#ifndef LLVM_CODEGEN_LATENCYPRIORITYQUEUE_H 17674be02d525d4e24bc6943ed9274958c580bcfbcJakub Staszak#define LLVM_CODEGEN_LATENCYPRIORITYQUEUE_H 18ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman 19ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman#include "llvm/CodeGen/ScheduleDAG.h" 20ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman 21ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohmannamespace llvm { 22ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman class LatencyPriorityQueue; 236e8f4c404825b79f9b9176483653f1aa927dfbdeAndrew Trick 24ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman /// Sorting functions for the Available queue. 25ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman struct latency_sort : public std::binary_function<SUnit*, SUnit*, bool> { 26ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman LatencyPriorityQueue *PQ; 27ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman explicit latency_sort(LatencyPriorityQueue *pq) : PQ(pq) {} 286e8f4c404825b79f9b9176483653f1aa927dfbdeAndrew Trick 29ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman bool operator()(const SUnit* left, const SUnit* right) const; 30ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman }; 31ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman 32ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman class LatencyPriorityQueue : public SchedulingPriorityQueue { 33ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman // SUnits - The SUnits for the current graph. 34ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman std::vector<SUnit> *SUnits; 356e8f4c404825b79f9b9176483653f1aa927dfbdeAndrew Trick 36ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman /// NumNodesSolelyBlocking - This vector contains, for every node in the 37ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman /// Queue, the number of nodes that the node is the sole unscheduled 38ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman /// predecessor for. This is used as a tie-breaker heuristic for better 39ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman /// mobility. 40ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman std::vector<unsigned> NumNodesSolelyBlocking; 416e8f4c404825b79f9b9176483653f1aa927dfbdeAndrew Trick 424de099d8ca651e00fa5fac22bace4f4dba2d0292David Goodwin /// Queue - The queue. 4393d343357944beb701d425fc7ef00dd7b0a32bd7Dan Gohman std::vector<SUnit*> Queue; 4493d343357944beb701d425fc7ef00dd7b0a32bd7Dan Gohman latency_sort Picker; 454de099d8ca651e00fa5fac22bace4f4dba2d0292David Goodwin 46f0f1bfe89a8127d5df82256440eddafd892aeb22Dan Gohman public: 4793d343357944beb701d425fc7ef00dd7b0a32bd7Dan Gohman LatencyPriorityQueue() : Picker(this) { 484de099d8ca651e00fa5fac22bace4f4dba2d0292David Goodwin } 494de099d8ca651e00fa5fac22bace4f4dba2d0292David Goodwin 502da8bc8a5f7705ac131184cd247f48500da0d74eAndrew Trick bool isBottomUp() const { return false; } 512da8bc8a5f7705ac131184cd247f48500da0d74eAndrew Trick 52ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman void initNodes(std::vector<SUnit> &sunits) { 53ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman SUnits = &sunits; 543f23744df4809eba94284e601e81489212c974d4Dan Gohman NumNodesSolelyBlocking.resize(SUnits->size(), 0); 55ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman } 56ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman 57ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman void addNode(const SUnit *SU) { 58ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman NumNodesSolelyBlocking.resize(SUnits->size(), 0); 59ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman } 60ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman 61ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman void updateNode(const SUnit *SU) { 62ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman } 63ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman 64ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman void releaseState() { 65ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman SUnits = 0; 66ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman } 676e8f4c404825b79f9b9176483653f1aa927dfbdeAndrew Trick 68ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman unsigned getLatency(unsigned NodeNum) const { 693f23744df4809eba94284e601e81489212c974d4Dan Gohman assert(NodeNum < (*SUnits).size()); 70557bbe6b5d13faaec38f85a266db457c7cb09ff2David Goodwin return (*SUnits)[NodeNum].getHeight(); 71ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman } 726e8f4c404825b79f9b9176483653f1aa927dfbdeAndrew Trick 73ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman unsigned getNumSolelyBlockNodes(unsigned NodeNum) const { 74ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman assert(NodeNum < NumNodesSolelyBlocking.size()); 75ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman return NumNodesSolelyBlocking[NodeNum]; 76ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman } 776e8f4c404825b79f9b9176483653f1aa927dfbdeAndrew Trick 78ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman bool empty() const { return Queue.empty(); } 796e8f4c404825b79f9b9176483653f1aa927dfbdeAndrew Trick 80a4e4ffd389497eb28f5fe91521fb71da4340e5d6Dan Gohman virtual void push(SUnit *U); 816e8f4c404825b79f9b9176483653f1aa927dfbdeAndrew Trick 8293d343357944beb701d425fc7ef00dd7b0a32bd7Dan Gohman virtual SUnit *pop(); 83ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman 8493d343357944beb701d425fc7ef00dd7b0a32bd7Dan Gohman virtual void remove(SUnit *SU); 85ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman 862da8bc8a5f7705ac131184cd247f48500da0d74eAndrew Trick virtual void dump(ScheduleDAG* DAG) const; 872da8bc8a5f7705ac131184cd247f48500da0d74eAndrew Trick 88953be893e8cffa0ef9bf410036cd96aeb526e98aAndrew Trick // scheduledNode - As nodes are scheduled, we look to see if there are any 89ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman // successor nodes that have a single unscheduled predecessor. If so, that 90ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman // single predecessor has a higher priority, since scheduling it will make 91ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman // the node available. 92953be893e8cffa0ef9bf410036cd96aeb526e98aAndrew Trick void scheduledNode(SUnit *Node); 93ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman 94343f0c046702831a4a6aec951b6a297a23241a55Dan Gohmanprivate: 95ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman void AdjustPriorityOfUnscheduledPreds(SUnit *SU); 96ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman SUnit *getSingleUnscheduledPred(SUnit *SU); 97ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman }; 98ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman} 99ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman 100ade9f1893412184c164aa3eb55a3e007ec647303Dan Gohman#endif 101