-// -*-C++-*-
-//***************************************************************************
-// File:
-// SchedPriorities.h
-//
-// Purpose:
-// Encapsulate heuristics for instruction scheduling.
+//===-- SchedPriorities.h - Encapsulate scheduling heuristics --*- C++ -*--===//
//
// Strategy:
// Priority ordering rules:
// (3) Instruction that has the maximum number of dependent instructions.
// Note that rules 2 and 3 are only used if issue conflicts prevent
// choosing a higher priority instruction by rule 1.
-//
-// History:
-// 7/30/01 - Vikram Adve - Created
-//**************************************************************************/
+//
+//===----------------------------------------------------------------------===//
#ifndef LLVM_CODEGEN_SCHEDPRIORITIES_H
#define LLVM_CODEGEN_SCHEDPRIORITIES_H
#include "SchedGraph.h"
#include "llvm/CodeGen/InstrScheduling.h"
-#include "llvm/Analysis/LiveVar/MethodLiveVarInfo.h"
#include "llvm/Target/MachineSchedInfo.h"
+#include "Support/hash_set"
#include <list>
-class Method;
+class Function;
class MachineInstr;
class SchedulingManager;
+class FunctionLiveVarInfo;
+
+//---------------------------------------------------------------------------
+// Debug option levels for instruction scheduling
+
+enum SchedDebugLevel_t {
+ Sched_NoDebugInfo,
+ Sched_Disable,
+ Sched_PrintMachineCode,
+ Sched_PrintSchedTrace,
+ Sched_PrintSchedGraphs,
+};
+
+extern SchedDebugLevel_t SchedDebugLevel;
+
+//---------------------------------------------------------------------------
+// Function: instrIsFeasible
+//
+// Purpose:
+// Used by the priority analysis to filter out instructions
+// that are not feasible to issue in the current cycle.
+// Should only be used during schedule construction..
+//---------------------------------------------------------------------------
+
+bool instrIsFeasible(const SchedulingManager &S, MachineOpCode opCode);
+
struct NodeDelayPair {
const SchedGraphNode* node;
cycles_t delay;
NodeDelayPair(const SchedGraphNode* n, cycles_t d) : node(n), delay(d) {}
- inline bool operator< (const NodeDelayPair& np) { return delay < np.delay; }
+ inline bool operator<(const NodeDelayPair& np) { return delay < np.delay; }
};
inline bool
NDPLessThan(const NodeDelayPair* np1, const NodeDelayPair* np2)
{
- return (np1->delay < np2->delay);
+ return np1->delay < np2->delay;
}
-class NodeHeap: public list<NodeDelayPair*>, public NonCopyable {
+class NodeHeap: public std::list<NodeDelayPair*>, public NonCopyable {
public:
- typedef list<NodeDelayPair*>::iterator iterator;
- typedef list<NodeDelayPair*>::const_iterator const_iterator;
+ typedef std::list<NodeDelayPair*>::iterator iterator;
+ typedef std::list<NodeDelayPair*>::const_iterator const_iterator;
public:
- /*ctor*/ NodeHeap () : list<NodeDelayPair*>(), _size(0) {}
- /*dtor*/ ~NodeHeap () {}
+ NodeHeap() : _size(0) {}
- inline unsigned int size () const { return _size; }
+ inline unsigned size() const { return _size; }
const SchedGraphNode* getNode (const_iterator i) const { return (*i)->node; }
cycles_t getDelay(const_iterator i) const { return (*i)->delay;}
iterator I=begin();
for ( ; I != end() && getDelay(I) >= delay; ++I)
;
- list<NodeDelayPair*>::insert(I, ndp);
+ std::list<NodeDelayPair*>::insert(I, ndp);
}
_size++;
}
class SchedPriorities: public NonCopyable {
public:
- /*ctor*/ SchedPriorities (const Method* method,
- const SchedGraph* _graph);
+ SchedPriorities(const Function *F, const SchedGraph *G,
+ FunctionLiveVarInfo &LVI);
+
// This must be called before scheduling begins.
void initialize ();
private:
cycles_t curTime;
const SchedGraph* graph;
- MethodLiveVarInfo methodLiveVarInfo;
+ FunctionLiveVarInfo &methodLiveVarInfo;
hash_map<const MachineInstr*, bool> lastUseMap;
- vector<cycles_t> nodeDelayVec;
- vector<cycles_t> earliestForNode;
+ std::vector<cycles_t> nodeDelayVec;
+ std::vector<cycles_t> nodeEarliestUseVec;
+ std::vector<cycles_t> earliestReadyTimeForNode;
cycles_t earliestReadyTime;
NodeHeap candsAsHeap; // candidate nodes, ready to go
- hash_set<const SchedGraphNode*> candsAsSet; // same entries as candsAsHeap,
+ hash_set<const SchedGraphNode*> candsAsSet; //same entries as candsAsHeap,
// but as set for fast lookup
- vector<candIndex> mcands; // holds pointers into cands
+ std::vector<candIndex> mcands; // holds pointers into cands
candIndex nextToTry; // next cand after the last
// one tried in this cycle
- int chooseByRule1 (vector<candIndex>& mcands);
- int chooseByRule2 (vector<candIndex>& mcands);
- int chooseByRule3 (vector<candIndex>& mcands);
+ int chooseByRule1 (std::vector<candIndex>& mcands);
+ int chooseByRule2 (std::vector<candIndex>& mcands);
+ int chooseByRule3 (std::vector<candIndex>& mcands);
- void findSetWithMaxDelay (vector<candIndex>& mcands,
+ void findSetWithMaxDelay (std::vector<candIndex>& mcands,
const SchedulingManager& S);
void computeDelays (const SchedGraph* graph);
void initializeReadyHeap (const SchedGraph* graph);
- bool instructionHasLastUse (MethodLiveVarInfo& methodLiveVarInfo,
+ bool instructionHasLastUse (FunctionLiveVarInfo& LVI,
const SchedGraphNode* graphNode);
// NOTE: The next two return references to the actual vector entries.
- // Use with care.
+ // Use the following two if you don't need to modify the value.
cycles_t& getNodeDelayRef (const SchedGraphNode* node) {
assert(node->getNodeId() < nodeDelayVec.size());
return nodeDelayVec[node->getNodeId()];
}
- cycles_t& getEarliestForNodeRef (const SchedGraphNode* node) {
- assert(node->getNodeId() < earliestForNode.size());
- return earliestForNode[node->getNodeId()];
+ cycles_t& getEarliestReadyTimeForNodeRef (const SchedGraphNode* node) {
+ assert(node->getNodeId() < earliestReadyTimeForNode.size());
+ return earliestReadyTimeForNode[node->getNodeId()];
+ }
+
+ cycles_t getNodeDelay (const SchedGraphNode* node) const {
+ return ((SchedPriorities*) this)->getNodeDelayRef(node);
+ }
+ cycles_t getEarliestReadyTimeForNode(const SchedGraphNode* node) const {
+ return ((SchedPriorities*) this)->getEarliestReadyTimeForNodeRef(node);
}
};
-inline void
-SchedPriorities::insertReady(const SchedGraphNode* node)
-{
- candsAsHeap.insert(node, nodeDelayVec[node->getNodeId()]);
- candsAsSet.insert(node);
- mcands.clear(); // ensure reset choices is called before any more choices
- earliestReadyTime = min(earliestReadyTime,
- earliestForNode[node->getNodeId()]);
-
- if (SchedDebugLevel >= Sched_PrintSchedTrace)
- {
- cout << " Cycle " << this->getTime() << ": "
- << " Node " << node->getNodeId() << " is ready; "
- << " Delay = " << this->getNodeDelayRef(node) << "; Instruction: "
- << endl;
- cout << " " << *node->getMachineInstr() << endl;
- }
-}
-
inline void SchedPriorities::updateTime(cycles_t c) {
curTime = c;
nextToTry = candsAsHeap.begin();
mcands.clear();
}
-inline ostream& operator<< (ostream& os, const NodeDelayPair* nd) {
+inline std::ostream &operator<<(std::ostream &os, const NodeDelayPair* nd) {
return os << "Delay for node " << nd->node->getNodeId()
- << " = " << nd->delay << endl;
+ << " = " << (long)nd->delay << "\n";
}
-/***************************************************************************/
-
#endif