aboutsummaryrefslogtreecommitdiff
path: root/lib/Target/SparcV9/ModuloScheduling/ModuloSchedulingSuperBlock.h
diff options
context:
space:
mode:
Diffstat (limited to 'lib/Target/SparcV9/ModuloScheduling/ModuloSchedulingSuperBlock.h')
-rw-r--r--lib/Target/SparcV9/ModuloScheduling/ModuloSchedulingSuperBlock.h121
1 files changed, 108 insertions, 13 deletions
diff --git a/lib/Target/SparcV9/ModuloScheduling/ModuloSchedulingSuperBlock.h b/lib/Target/SparcV9/ModuloScheduling/ModuloSchedulingSuperBlock.h
index 8d38784a24..df9e302e9a 100644
--- a/lib/Target/SparcV9/ModuloScheduling/ModuloSchedulingSuperBlock.h
+++ b/lib/Target/SparcV9/ModuloScheduling/ModuloSchedulingSuperBlock.h
@@ -15,22 +15,24 @@
#define LLVM_MODULOSCHEDULINGSB_H
#include "llvm/Analysis/LoopInfo.h"
+#include "llvm/Analysis/ScalarEvolution.h"
#include "llvm/Function.h"
#include "llvm/Pass.h"
#include "llvm/CodeGen/MachineBasicBlock.h"
-#include "MSSchedule.h"
-#include "MSchedGraph.h"
+#include "MSScheduleSB.h"
+#include "MSchedGraphSB.h"
+
namespace llvm {
//Struct to contain ModuloScheduling Specific Information for each node
- struct MSNodeAttributes {
+ struct MSNodeSBAttributes {
int ASAP; //Earliest time at which the opreation can be scheduled
int ALAP; //Latest time at which the operation can be scheduled.
int MOB;
int depth;
int height;
- MSNodeAttributes(int asap=-1, int alap=-1, int mob=-1,
+ MSNodeSBAttributes(int asap=-1, int alap=-1, int mob=-1,
int d=-1, int h=-1) : ASAP(asap), ALAP(alap),
MOB(mob), depth(d),
height(h) {}
@@ -55,22 +57,22 @@ namespace llvm {
Instruction *defaultInst;
//Map that holds node to node attribute information
- std::map<MSchedGraphNode*, MSNodeAttributes> nodeToAttributesMap;
+ std::map<MSchedGraphSBNode*, MSNodeSBAttributes> nodeToAttributesMap;
//Map to hold all reccurrences
- std::set<std::pair<int, std::vector<MSchedGraphNode*> > > recurrenceList;
+ std::set<std::pair<int, std::vector<MSchedGraphSBNode*> > > recurrenceList;
//Set of edges to ignore, stored as src node and index into vector of successors
- std::set<std::pair<MSchedGraphNode*, unsigned> > edgesToIgnore;
+ std::set<std::pair<MSchedGraphSBNode*, unsigned> > edgesToIgnore;
//Vector containing the partial order
- std::vector<std::set<MSchedGraphNode*> > partialOrder;
+ std::vector<std::set<MSchedGraphSBNode*> > partialOrder;
//Vector containing the final node order
- std::vector<MSchedGraphNode*> FinalNodeOrder;
+ std::vector<MSchedGraphSBNode*> FinalNodeOrder;
//Schedule table, key is the cycle number and the vector is resource, node pairs
- MSSchedule schedule;
+ MSScheduleSB schedule;
//Current initiation interval
int II;
@@ -78,10 +80,99 @@ namespace llvm {
//Internal Functions
void FindSuperBlocks(Function &F, LoopInfo &LI,
std::vector<std::vector<const MachineBasicBlock*> > &Worklist);
- bool MachineBBisValid(const MachineBasicBlock *B);
+ bool MachineBBisValid(const MachineBasicBlock *B,
+ std::map<const MachineInstr*, unsigned> &indexMap,
+ unsigned &offset);
bool CreateDefMap(std::vector<const MachineBasicBlock*> &SB);
-
- public:
+ bool getIndVar(std::vector<const MachineBasicBlock*> &superBlock,
+ std::map<BasicBlock*, MachineBasicBlock*> &bbMap,
+ std::map<const MachineInstr*, unsigned> &indexMap);
+ bool assocIndVar(Instruction *I, std::set<Instruction*> &indVar,
+ std::vector<Instruction*> &stack,
+ std::map<BasicBlock*, MachineBasicBlock*> &bbMap,
+ const BasicBlock *first,
+ std::set<const BasicBlock*> &llvmSuperBlock);
+ int calculateResMII(std::vector<const MachineBasicBlock*> &superBlock);
+ int calculateRecMII(MSchedGraphSB *graph, int MII);
+ void findAllCircuits(MSchedGraphSB *g, int II);
+ void addRecc(std::vector<MSchedGraphSBNode*> &stack,
+ std::map<MSchedGraphSBNode*, MSchedGraphSBNode*> &newNodes);
+ bool circuit(MSchedGraphSBNode *v, std::vector<MSchedGraphSBNode*> &stack,
+ std::set<MSchedGraphSBNode*> &blocked, std::vector<MSchedGraphSBNode*> &SCC,
+ MSchedGraphSBNode *s, std::map<MSchedGraphSBNode*,
+ std::set<MSchedGraphSBNode*> > &B,
+ int II, std::map<MSchedGraphSBNode*, MSchedGraphSBNode*> &newNodes);
+ void unblock(MSchedGraphSBNode *u, std::set<MSchedGraphSBNode*> &blocked,
+ std::map<MSchedGraphSBNode*, std::set<MSchedGraphSBNode*> > &B);
+ void addSCC(std::vector<MSchedGraphSBNode*> &SCC, std::map<MSchedGraphSBNode*, MSchedGraphSBNode*> &newNodes);
+ void calculateNodeAttributes(MSchedGraphSB *graph, int MII);
+ bool ignoreEdge(MSchedGraphSBNode *srcNode, MSchedGraphSBNode *destNode);
+ int calculateASAP(MSchedGraphSBNode *node, int MII, MSchedGraphSBNode *destNode);
+ int calculateALAP(MSchedGraphSBNode *node, int MII,
+ int maxASAP, MSchedGraphSBNode *srcNode);
+ int findMaxASAP();
+ int calculateHeight(MSchedGraphSBNode *node,MSchedGraphSBNode *srcNode);
+ int calculateDepth(MSchedGraphSBNode *node, MSchedGraphSBNode *destNode);
+ void computePartialOrder();
+ void connectedComponentSet(MSchedGraphSBNode *node, std::set<MSchedGraphSBNode*> &ccSet,
+ std::set<MSchedGraphSBNode*> &lastNodes);
+ void searchPath(MSchedGraphSBNode *node,
+ std::vector<MSchedGraphSBNode*> &path,
+ std::set<MSchedGraphSBNode*> &nodesToAdd,
+ std::set<MSchedGraphSBNode*> &new_reccurrence);
+ void orderNodes();
+ bool computeSchedule(std::vector<const MachineBasicBlock*> &BB, MSchedGraphSB *MSG);
+ bool scheduleNode(MSchedGraphSBNode *node, int start, int end);
+ void predIntersect(std::set<MSchedGraphSBNode*> &CurrentSet, std::set<MSchedGraphSBNode*> &IntersectResult);
+ void succIntersect(std::set<MSchedGraphSBNode*> &CurrentSet, std::set<MSchedGraphSBNode*> &IntersectResult);
+ void reconstructLoop(std::vector<const MachineBasicBlock*> &SB);
+ void fixBranches(std::vector<std::vector<MachineBasicBlock*> > &prologues,
+ std::vector<std::vector<BasicBlock*> > &llvm_prologues,
+ std::vector<MachineBasicBlock*> &machineKernelBB,
+ std::vector<BasicBlock*> &llvmKernelBB,
+ std::vector<std::vector<MachineBasicBlock*> > &epilogues,
+ std::vector<std::vector<BasicBlock*> > &llvm_epilogues,
+ std::vector<const MachineBasicBlock*> &SB,
+ std::map<const MachineBasicBlock*, Value*> &sideExits);
+
+ void writePrologues(std::vector<std::vector<MachineBasicBlock *> > &prologues,
+ std::vector<const MachineBasicBlock*> &origBB,
+ std::vector<std::vector<BasicBlock*> > &llvm_prologues,
+ std::map<const Value*, std::pair<const MachineInstr*, int> > &valuesToSave,
+ std::map<Value*, std::map<int, Value*> > &newValues,
+ std::map<Value*, MachineBasicBlock*> &newValLocation);
+
+ void writeKernel(std::vector<BasicBlock*> &llvmBB, std::vector<MachineBasicBlock*> &machineBB,
+ std::map<const Value*, std::pair<const MachineInstr*, int> > &valuesToSave,
+ std::map<Value*, std::map<int, Value*> > &newValues,
+ std::map<Value*, MachineBasicBlock*> &newValLocation,
+ std::map<Value*, std::map<int, Value*> > &kernelPHIs);
+
+ void removePHIs(std::vector<const MachineBasicBlock*> &SB,
+ std::vector<std::vector<MachineBasicBlock*> > &prologues,
+ std::vector<std::vector<MachineBasicBlock*> > &epilogues,
+ std::vector<MachineBasicBlock*> &kernelBB,
+ std::map<Value*, MachineBasicBlock*> &newValLocation);
+
+ void writeEpilogues(std::vector<std::vector<MachineBasicBlock*> > &epilogues,
+ std::vector<const MachineBasicBlock*> &origSB,
+ std::vector<std::vector<BasicBlock*> > &llvm_epilogues,
+ std::map<const Value*, std::pair<const MachineInstr*, int> > &valuesToSave,
+ std::map<Value*, std::map<int, Value*> > &newValues,
+ std::map<Value*, MachineBasicBlock*> &newValLocation,
+ std::map<Value*, std::map<int, Value*> > &kernelPHIs);
+
+ void writeSideExits(std::vector<std::vector<MachineBasicBlock *> > &prologues,
+ std::vector<std::vector<BasicBlock*> > &llvm_prologues,
+ std::vector<std::vector<MachineBasicBlock *> > &epilogues,
+ std::vector<std::vector<BasicBlock*> > &llvm_epilogues,
+ std::map<const MachineBasicBlock*, Value*> &sideExits,
+ std::map<MachineBasicBlock*, std::vector<std::pair<MachineInstr*, int> > > &instrsMovedDown,
+ std::vector<const MachineBasicBlock*> &SB,
+ std::vector<MachineBasicBlock*> &kernelMBBs,
+ std::map<MachineBasicBlock*, int> branchStage);
+
+ public:
ModuloSchedulingSBPass(TargetMachine &targ) : target(targ) {}
virtual bool runOnFunction(Function &F);
virtual const char* getPassName() const { return "ModuloScheduling-SuperBlock"; }
@@ -89,7 +180,11 @@ namespace llvm {
// getAnalysisUsage
virtual void getAnalysisUsage(AnalysisUsage &AU) const {
+ /// HACK: We don't actually need scev, but we have
+ /// to say we do so that the pass manager does not delete it
+ /// before we run.
AU.addRequired<LoopInfo>();
+ AU.addRequired<ScalarEvolution>();
AU.addRequired<DependenceAnalyzer>();
}
};
generated by cgit v1.2.3-18-g5258 (git 2.32.0) at 2025-04-28 22:27:43 +0000