From 20890832ead867e78a3e9b074caecaa62983b33d Mon Sep 17 00:00:00 2001 From: Tanya Lattner Date: Fri, 28 May 2004 20:14:12 +0000 Subject: [PATCH] updates to ModuloSched git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@13881 91177308-0d34-0410-b5e6-96231b3b80d8 --- .../ModuloScheduling/ModuloScheduling.cpp | 97 +++++++++++++++++-- .../ModuloScheduling/ModuloScheduling.h | 4 +- .../ModuloScheduling/ModuloScheduling.cpp | 97 +++++++++++++++++-- .../ModuloScheduling/ModuloScheduling.h | 4 +- 4 files changed, 182 insertions(+), 20 deletions(-) diff --git a/lib/CodeGen/ModuloScheduling/ModuloScheduling.cpp b/lib/CodeGen/ModuloScheduling/ModuloScheduling.cpp index cab600e1157..58fd089943e 100644 --- a/lib/CodeGen/ModuloScheduling/ModuloScheduling.cpp +++ b/lib/CodeGen/ModuloScheduling/ModuloScheduling.cpp @@ -1014,7 +1014,7 @@ void ModuloSchedulingPass::computeSchedule() { if(!ignoreEdge(*schedNode, *I)) { int diff = (*I)->getInEdge(*schedNode).getIteDiff(); int ES_Temp = nodesByCycle->first + (*schedNode)->getLatency() - diff * II; - DEBUG(std::cerr << "Diff: " << diff << " Cycle: " << nodesByCycle->first << "\n"); + DEBUG(std::cerr << "Diff: " << diff << " Cycle: " << nodesByCycle->first << "\n"); DEBUG(std::cerr << "Temp EarlyStart: " << ES_Temp << " Prev EarlyStart: " << EarlyStart << "\n"); EarlyStart = std::max(EarlyStart, ES_Temp); hasPred = true; @@ -1147,7 +1147,8 @@ bool ModuloSchedulingPass::scheduleNode(MSchedGraphNode *node, assert(numFound == 1 && "We should have only found one def to this virtual register!"); }*/ -void ModuloSchedulingPass::writePrologue(std::vector &prologues, MachineBasicBlock *origBB, std::vector &llvm_prologues) { +void ModuloSchedulingPass::writePrologues(std::vector &prologues, const MachineBasicBlock *origBB, std::vector &llvm_prologues) { + std::map > inKernel; int maxStageCount = 0; @@ -1159,13 +1160,14 @@ void ModuloSchedulingPass::writePrologue(std::vector &prolo continue; //Put int the map so we know what instructions in each stage are in the kernel - if(I->second > 0) + if(I->second > 0) { + DEBUG(std::cerr << "Inserting instruction " << *(I->first->getInst()) << " into map at stage " << I->second << "\n"); inKernel[I->second].insert(I->first->getInst()); + } } //Now write the prologues - for(std::map >::iterator I = inKernel.begin(), E = inKernel.end(); - I != E; ++I) { + for(int i = 1; i <= maxStageCount; ++i) { BasicBlock *llvmBB = new BasicBlock(); MachineBasicBlock *machineBB = new MachineBasicBlock(llvmBB); @@ -1173,17 +1175,72 @@ void ModuloSchedulingPass::writePrologue(std::vector &prolo //stage that is NOT in the kernel, then it needs to be added into the prologue //We go in order to preserve dependencies for(MachineBasicBlock::const_iterator MI = origBB->begin(), ME = origBB->end(); ME != MI; ++MI) { - if(I->second.count(&*MI)) - continue; - else - machineBB->push_back(MI->clone()); + if(inKernel[i].count(&*MI)) { + inKernel[i].erase(&*MI); + if(inKernel[i].size() <= 0) + break; + else + continue; + } + else { + DEBUG(std::cerr << "Writing instruction to prologue\n"); + machineBB->push_back(MI->clone()); + } } + (((MachineBasicBlock*)origBB)->getParent())->getBasicBlockList().push_back(machineBB); prologues.push_back(machineBB); llvm_prologues.push_back(llvmBB); } } +void ModuloSchedulingPass::writeEpilogues(std::vector &epilogues, const MachineBasicBlock *origBB, std::vector &llvm_epilogues) { + std::map > inKernel; + int maxStageCount = 0; + for(MSSchedule::kernel_iterator I = schedule.kernel_begin(), E = schedule.kernel_end(); I != E; ++I) { + maxStageCount = std::max(maxStageCount, I->second); + + //Ignore the branch, we will handle this separately + if(I->first->isBranch()) + continue; + + //Put int the map so we know what instructions in each stage are in the kernel + if(I->second > 0) { + DEBUG(std::cerr << "Inserting instruction " << *(I->first->getInst()) << " into map at stage " << I->second << "\n"); + inKernel[I->second].insert(I->first->getInst()); + } + } + + //Now write the epilogues + for(int i = 1; i <= maxStageCount; ++i) { + BasicBlock *llvmBB = new BasicBlock(); + MachineBasicBlock *machineBB = new MachineBasicBlock(llvmBB); + + bool last = false; + for(MachineBasicBlock::const_iterator MI = origBB->begin(), ME = origBB->end(); ME != MI; ++MI) { + + if(!last) { + if(inKernel[i].count(&*MI)) { + machineBB->push_back(MI->clone()); + inKernel[i].erase(&*MI); + if(inKernel[i].size() <= 0) + last = true; + } + } + + else + machineBB->push_back(MI->clone()); + + + } + (((MachineBasicBlock*)origBB)->getParent())->getBasicBlockList().push_back(machineBB); + epilogues.push_back(machineBB); + llvm_epilogues.push_back(llvmBB); + } + +} + + void ModuloSchedulingPass::reconstructLoop(const MachineBasicBlock *BB) { @@ -1192,7 +1249,29 @@ void ModuloSchedulingPass::reconstructLoop(const MachineBasicBlock *BB) { std::vector prologues; std::vector llvm_prologues; + //Write prologue + writePrologues(prologues, BB, llvm_prologues); + + //Print out prologue + for(std::vector::iterator I = prologues.begin(), E = prologues.end(); + I != E; ++I) { + std::cerr << "PROLOGUE\n"; + (*I)->print(std::cerr); + } + + + std::vector epilogues; + std::vector llvm_epilogues; + //Write epilogues + writeEpilogues(epilogues, BB, llvm_epilogues); + + //Print out prologue + for(std::vector::iterator I = epilogues.begin(), E = epilogues.end(); + I != E; ++I) { + std::cerr << "EPILOGUE\n"; + (*I)->print(std::cerr); + } //create a vector of epilogues corresponding to each stage /*std::vector epilogues; diff --git a/lib/CodeGen/ModuloScheduling/ModuloScheduling.h b/lib/CodeGen/ModuloScheduling/ModuloScheduling.h index 62abc7c5286..cc4c51514dd 100644 --- a/lib/CodeGen/ModuloScheduling/ModuloScheduling.h +++ b/lib/CodeGen/ModuloScheduling/ModuloScheduling.h @@ -93,8 +93,10 @@ namespace llvm { //void saveValue(const MachineInstr*, const std::set&, std::vector*); - void writePrologue(std::vector &prologues, MachineBasicBlock *origBB, std::vector &llvm_prologues); + void writePrologues(std::vector &prologues, const MachineBasicBlock *origBB, std::vector &llvm_prologues); + void writeEpilogues(std::vector &epilogues, const MachineBasicBlock *origBB, std::vector &llvm_epilogues); + public: ModuloSchedulingPass(TargetMachine &targ) : target(targ) {} virtual bool runOnFunction(Function &F); diff --git a/lib/Target/SparcV9/ModuloScheduling/ModuloScheduling.cpp b/lib/Target/SparcV9/ModuloScheduling/ModuloScheduling.cpp index cab600e1157..58fd089943e 100644 --- a/lib/Target/SparcV9/ModuloScheduling/ModuloScheduling.cpp +++ b/lib/Target/SparcV9/ModuloScheduling/ModuloScheduling.cpp @@ -1014,7 +1014,7 @@ void ModuloSchedulingPass::computeSchedule() { if(!ignoreEdge(*schedNode, *I)) { int diff = (*I)->getInEdge(*schedNode).getIteDiff(); int ES_Temp = nodesByCycle->first + (*schedNode)->getLatency() - diff * II; - DEBUG(std::cerr << "Diff: " << diff << " Cycle: " << nodesByCycle->first << "\n"); + DEBUG(std::cerr << "Diff: " << diff << " Cycle: " << nodesByCycle->first << "\n"); DEBUG(std::cerr << "Temp EarlyStart: " << ES_Temp << " Prev EarlyStart: " << EarlyStart << "\n"); EarlyStart = std::max(EarlyStart, ES_Temp); hasPred = true; @@ -1147,7 +1147,8 @@ bool ModuloSchedulingPass::scheduleNode(MSchedGraphNode *node, assert(numFound == 1 && "We should have only found one def to this virtual register!"); }*/ -void ModuloSchedulingPass::writePrologue(std::vector &prologues, MachineBasicBlock *origBB, std::vector &llvm_prologues) { +void ModuloSchedulingPass::writePrologues(std::vector &prologues, const MachineBasicBlock *origBB, std::vector &llvm_prologues) { + std::map > inKernel; int maxStageCount = 0; @@ -1159,13 +1160,14 @@ void ModuloSchedulingPass::writePrologue(std::vector &prolo continue; //Put int the map so we know what instructions in each stage are in the kernel - if(I->second > 0) + if(I->second > 0) { + DEBUG(std::cerr << "Inserting instruction " << *(I->first->getInst()) << " into map at stage " << I->second << "\n"); inKernel[I->second].insert(I->first->getInst()); + } } //Now write the prologues - for(std::map >::iterator I = inKernel.begin(), E = inKernel.end(); - I != E; ++I) { + for(int i = 1; i <= maxStageCount; ++i) { BasicBlock *llvmBB = new BasicBlock(); MachineBasicBlock *machineBB = new MachineBasicBlock(llvmBB); @@ -1173,17 +1175,72 @@ void ModuloSchedulingPass::writePrologue(std::vector &prolo //stage that is NOT in the kernel, then it needs to be added into the prologue //We go in order to preserve dependencies for(MachineBasicBlock::const_iterator MI = origBB->begin(), ME = origBB->end(); ME != MI; ++MI) { - if(I->second.count(&*MI)) - continue; - else - machineBB->push_back(MI->clone()); + if(inKernel[i].count(&*MI)) { + inKernel[i].erase(&*MI); + if(inKernel[i].size() <= 0) + break; + else + continue; + } + else { + DEBUG(std::cerr << "Writing instruction to prologue\n"); + machineBB->push_back(MI->clone()); + } } + (((MachineBasicBlock*)origBB)->getParent())->getBasicBlockList().push_back(machineBB); prologues.push_back(machineBB); llvm_prologues.push_back(llvmBB); } } +void ModuloSchedulingPass::writeEpilogues(std::vector &epilogues, const MachineBasicBlock *origBB, std::vector &llvm_epilogues) { + std::map > inKernel; + int maxStageCount = 0; + for(MSSchedule::kernel_iterator I = schedule.kernel_begin(), E = schedule.kernel_end(); I != E; ++I) { + maxStageCount = std::max(maxStageCount, I->second); + + //Ignore the branch, we will handle this separately + if(I->first->isBranch()) + continue; + + //Put int the map so we know what instructions in each stage are in the kernel + if(I->second > 0) { + DEBUG(std::cerr << "Inserting instruction " << *(I->first->getInst()) << " into map at stage " << I->second << "\n"); + inKernel[I->second].insert(I->first->getInst()); + } + } + + //Now write the epilogues + for(int i = 1; i <= maxStageCount; ++i) { + BasicBlock *llvmBB = new BasicBlock(); + MachineBasicBlock *machineBB = new MachineBasicBlock(llvmBB); + + bool last = false; + for(MachineBasicBlock::const_iterator MI = origBB->begin(), ME = origBB->end(); ME != MI; ++MI) { + + if(!last) { + if(inKernel[i].count(&*MI)) { + machineBB->push_back(MI->clone()); + inKernel[i].erase(&*MI); + if(inKernel[i].size() <= 0) + last = true; + } + } + + else + machineBB->push_back(MI->clone()); + + + } + (((MachineBasicBlock*)origBB)->getParent())->getBasicBlockList().push_back(machineBB); + epilogues.push_back(machineBB); + llvm_epilogues.push_back(llvmBB); + } + +} + + void ModuloSchedulingPass::reconstructLoop(const MachineBasicBlock *BB) { @@ -1192,7 +1249,29 @@ void ModuloSchedulingPass::reconstructLoop(const MachineBasicBlock *BB) { std::vector prologues; std::vector llvm_prologues; + //Write prologue + writePrologues(prologues, BB, llvm_prologues); + + //Print out prologue + for(std::vector::iterator I = prologues.begin(), E = prologues.end(); + I != E; ++I) { + std::cerr << "PROLOGUE\n"; + (*I)->print(std::cerr); + } + + + std::vector epilogues; + std::vector llvm_epilogues; + //Write epilogues + writeEpilogues(epilogues, BB, llvm_epilogues); + + //Print out prologue + for(std::vector::iterator I = epilogues.begin(), E = epilogues.end(); + I != E; ++I) { + std::cerr << "EPILOGUE\n"; + (*I)->print(std::cerr); + } //create a vector of epilogues corresponding to each stage /*std::vector epilogues; diff --git a/lib/Target/SparcV9/ModuloScheduling/ModuloScheduling.h b/lib/Target/SparcV9/ModuloScheduling/ModuloScheduling.h index 62abc7c5286..cc4c51514dd 100644 --- a/lib/Target/SparcV9/ModuloScheduling/ModuloScheduling.h +++ b/lib/Target/SparcV9/ModuloScheduling/ModuloScheduling.h @@ -93,8 +93,10 @@ namespace llvm { //void saveValue(const MachineInstr*, const std::set&, std::vector*); - void writePrologue(std::vector &prologues, MachineBasicBlock *origBB, std::vector &llvm_prologues); + void writePrologues(std::vector &prologues, const MachineBasicBlock *origBB, std::vector &llvm_prologues); + void writeEpilogues(std::vector &epilogues, const MachineBasicBlock *origBB, std::vector &llvm_epilogues); + public: ModuloSchedulingPass(TargetMachine &targ) : target(targ) {} virtual bool runOnFunction(Function &F); -- 2.34.1