From e5a4d52035a440ec56b0cab968d193da3624c165 Mon Sep 17 00:00:00 2001 From: Tanya Lattner Date: Sun, 1 May 2005 01:27:47 +0000 Subject: [PATCH] SMS for superblocks. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@21643 91177308-0d34-0410-b5e6-96231b3b80d8 --- .../ModuloSchedulingSuperBlock.cpp | 282 +++++++++++++++++++++ .../ModuloScheduling/ModuloSchedulingSuperBlock.h | 97 +++++++ 2 files changed, 379 insertions(+) create mode 100644 lib/Target/SparcV9/ModuloScheduling/ModuloSchedulingSuperBlock.cpp create mode 100644 lib/Target/SparcV9/ModuloScheduling/ModuloSchedulingSuperBlock.h diff --git a/lib/Target/SparcV9/ModuloScheduling/ModuloSchedulingSuperBlock.cpp b/lib/Target/SparcV9/ModuloScheduling/ModuloSchedulingSuperBlock.cpp new file mode 100644 index 00000000000..bc18027ff4d --- /dev/null +++ b/lib/Target/SparcV9/ModuloScheduling/ModuloSchedulingSuperBlock.cpp @@ -0,0 +1,282 @@ +//===-- ModuloSchedulingSuperBlock.cpp - ModuloScheduling--------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file was developed by the LLVM research group and is distributed under +// the University of Illinois Open Source License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This ModuloScheduling pass is based on the Swing Modulo Scheduling +// algorithm, but has been extended to support SuperBlocks (multiple +// basic block, single entry, multipl exit loops). +// +//===----------------------------------------------------------------------===// + +#define DEBUG_TYPE "ModuloSchedSB" + +#include "DependenceAnalyzer.h" +#include "ModuloSchedulingSuperBlock.h" +#include "llvm/ADT/Statistic.h" +#include "llvm/CodeGen/MachineFunction.h" +#include "llvm/CodeGen/Passes.h" +#include "llvm/Support/CFG.h" +#include "llvm/Support/Debug.h" +#include "llvm/Support/GraphWriter.h" +#include "llvm/Instructions.h" +#include "../MachineCodeForInstruction.h" +#include "../SparcV9RegisterInfo.h" +#include "../SparcV9Internals.h" +#include "../SparcV9TmpInstr.h" +#include +#include + +using namespace llvm; +/// Create ModuloSchedulingSBPass +/// +FunctionPass *llvm::createModuloSchedulingSBPass(TargetMachine & targ) { + DEBUG(std::cerr << "Created ModuloSchedulingSBPass\n"); + return new ModuloSchedulingSBPass(targ); +} + +//Graph Traits for printing out the dependence graph +template +static void WriteGraphToFile(std::ostream &O, const std::string &GraphName, + const GraphType >) { + std::string Filename = GraphName + ".dot"; + O << "Writing '" << Filename << "'..."; + std::ofstream F(Filename.c_str()); + + if (F.good()) + WriteGraph(F, GT); + else + O << " error opening file for writing!"; + O << "\n"; +}; + +namespace llvm { + Statistic<> NumLoops("moduloschedSB-numLoops", "Total Number of Loops"); + Statistic<> NumSB("moduloschedSB-numSuperBlocks", "Total Number of SuperBlocks"); + Statistic<> BBWithCalls("modulosched-BBCalls", "Basic Blocks rejected due to calls"); + Statistic<> BBWithCondMov("modulosched-loopCondMov", "Basic Blocks rejected due to conditional moves"); + bool ModuloSchedulingSBPass::runOnFunction(Function &F) { + bool Changed = false; + + //Get MachineFunction + MachineFunction &MF = MachineFunction::get(&F); + + //Get Loop Info & Dependence Anaysis info + LoopInfo &LI = getAnalysis(); + DependenceAnalyzer &DA = getAnalysis(); + + //Worklist of superblocks + std::vector > Worklist; + FindSuperBlocks(F, LI, Worklist); + + DEBUG(if(Worklist.size() == 0) std::cerr << "No superblocks in function to ModuloSchedule\n"); + + //Loop over worklist and ModuloSchedule each SuperBlock + for(std::vector >::iterator SB = Worklist.begin(), + SBE = Worklist.end(); SB != SBE; ++SB) { + + //Print out Superblock + DEBUG(std::cerr << "ModuloScheduling SB: \n"; + for(std::vector::const_iterator BI = SB->begin(), + BE = SB->end(); BI != BE; ++BI) { + (*BI)->print(std::cerr);}); + + if(!CreateDefMap(*SB)) { + defaultInst = 0; + defMap.clear(); + continue; + } + + MSchedGraph *MSG = new MSchedGraph(*SB, target, indVarInstrs[*SB], DA, + machineTollvm[*SB]); + + //Write Graph out to file + DEBUG(WriteGraphToFile(std::cerr, F.getName(), MSG)); + DEBUG(MSG->print(std::cerr)); + + } + return Changed; + + } + + void ModuloSchedulingSBPass::FindSuperBlocks(Function &F, LoopInfo &LI, + std::vector > &Worklist) { + + //Get MachineFunction + MachineFunction &MF = MachineFunction::get(&F); + + //Map of LLVM BB to machine BB + std::map bbMap; + + for (MachineFunction::iterator BI = MF.begin(); BI != MF.end(); ++BI) { + BasicBlock *llvmBB = (BasicBlock*) BI->getBasicBlock(); + assert(!bbMap.count(llvmBB) && "LLVM BB already in map!"); + bbMap[llvmBB] = &*BI; + } + + //Iterate over the loops, and find super blocks + for(LoopInfo::iterator LB = LI.begin(), LE = LI.end(); LB != LE; ++LB) { + Loop *L = *LB; + ++NumLoops; + + //If loop is not single entry, try the next one + if(!L->getLoopPreheader()) + continue; + + //Check size of this loop, we don't want SBB loops + if(L->getBlocks().size() == 1) + continue; + + //Check if this loop contains no sub loops + if(L->getSubLoops().size() == 0) { + + std::vector superBlock; + + //Get Loop Headers + BasicBlock *header = L->getHeader(); + + //Follow the header and make sure each BB only has one entry and is valid + BasicBlock *current = header; + assert(bbMap.count(current) && "LLVM BB must have corresponding Machine BB\n"); + MachineBasicBlock *currentMBB = bbMap[header]; + bool done = false; + bool success = true; + + while(!done) { + + if(MachineBBisValid(currentMBB)) { + + //Loop over successors of this BB, they should be in the loop block + //and be valid + BasicBlock *next = 0; + for(succ_iterator I = succ_begin(current), E = succ_end(current); + I != E; ++I) { + if(L->contains(*I)) { + if(!next) + next = *I; + else { + done = true; + success = false; + break; + } + } + } + if(success) { + superBlock.push_back(currentMBB); + if(next == header) + done = true; + else if(!next->getSinglePredecessor()) { + done = true; + success = false; + } + else { + //Check that the next BB only has one entry + current = next; + assert(bbMap.count(current) && "LLVM BB must have corresponding Machine BB"); + currentMBB = bbMap[current]; + } + } + } + else { + done = true; + success = false; + } + } + + if(success) { + ++NumSB; + Worklist.push_back(superBlock); + } + + } + + } + } + + /// This function checks if a Machine Basic Block is valid for modulo + /// scheduling. This means that it has no control flow (if/else or + /// calls) in the block. Currently ModuloScheduling only works on + /// single basic block loops. + bool ModuloSchedulingSBPass::MachineBBisValid(const MachineBasicBlock *BI) { + + //Check size of our basic block.. make sure we have more then just the terminator in it + if(BI->getBasicBlock()->size() == 1) + return false; + + //Get Target machine instruction info + const TargetInstrInfo *TMI = target.getInstrInfo(); + + //Check each instruction and look for calls, keep map to get index later + std::map indexMap; + + unsigned count = 0; + for(MachineBasicBlock::const_iterator I = BI->begin(), E = BI->end(); I != E; ++I) { + //Get opcode to check instruction type + MachineOpCode OC = I->getOpcode(); + + //Look for calls + if(TMI->isCall(OC)) { + ++BBWithCalls; + return false; + } + + //Look for conditional move + if(OC == V9::MOVRZr || OC == V9::MOVRZi || OC == V9::MOVRLEZr || OC == V9::MOVRLEZi + || OC == V9::MOVRLZr || OC == V9::MOVRLZi || OC == V9::MOVRNZr || OC == V9::MOVRNZi + || OC == V9::MOVRGZr || OC == V9::MOVRGZi || OC == V9::MOVRGEZr + || OC == V9::MOVRGEZi || OC == V9::MOVLEr || OC == V9::MOVLEi || OC == V9::MOVLEUr + || OC == V9::MOVLEUi || OC == V9::MOVFLEr || OC == V9::MOVFLEi + || OC == V9::MOVNEr || OC == V9::MOVNEi || OC == V9::MOVNEGr || OC == V9::MOVNEGi + || OC == V9::MOVFNEr || OC == V9::MOVFNEi) { + ++BBWithCondMov; + return false; + } + + indexMap[I] = count; + + if(TMI->isNop(OC)) + continue; + + ++count; + } + + return true; + } +} + +bool ModuloSchedulingSBPass::CreateDefMap(std::vector &SB) { + defaultInst = 0; + + for(std::vector::iterator BI = SB.begin(), + BE = SB.end(); BI != BE; ++BI) { + + for(MachineBasicBlock::const_iterator I = (*BI)->begin(), E = (*BI)->end(); I != E; ++I) { + for(unsigned opNum = 0; opNum < I->getNumOperands(); ++opNum) { + const MachineOperand &mOp = I->getOperand(opNum); + if(mOp.getType() == MachineOperand::MO_VirtualRegister && mOp.isDef()) { + + //assert if this is the second def we have seen + assert(!defMap.count(mOp.getVRegValue()) && "Def already in the map"); + defMap[mOp.getVRegValue()] = (MachineInstr*) &*I; + } + + //See if we can use this Value* as our defaultInst + if(!defaultInst && mOp.getType() == MachineOperand::MO_VirtualRegister) { + Value *V = mOp.getVRegValue(); + if(!isa(V) && !isa(V) && !isa(V) && !isa(V)) + defaultInst = (Instruction*) V; + } + } + } + } + + if(!defaultInst) + return false; + + return true; + +} diff --git a/lib/Target/SparcV9/ModuloScheduling/ModuloSchedulingSuperBlock.h b/lib/Target/SparcV9/ModuloScheduling/ModuloSchedulingSuperBlock.h new file mode 100644 index 00000000000..8d38784a240 --- /dev/null +++ b/lib/Target/SparcV9/ModuloScheduling/ModuloSchedulingSuperBlock.h @@ -0,0 +1,97 @@ +//===-- ModuloSchedulingSuperBlock.h -Swing Modulo Scheduling-----*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file was developed by the LLVM research group and is distributed under +// the University of Illinois Open Source License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +//Swing Modulo Scheduling done on Superblocks ( entry, multiple exit, +//multiple basic block loops). +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_MODULOSCHEDULINGSB_H +#define LLVM_MODULOSCHEDULINGSB_H + +#include "llvm/Analysis/LoopInfo.h" +#include "llvm/Function.h" +#include "llvm/Pass.h" +#include "llvm/CodeGen/MachineBasicBlock.h" +#include "MSSchedule.h" +#include "MSchedGraph.h" + +namespace llvm { + + //Struct to contain ModuloScheduling Specific Information for each node + struct MSNodeAttributes { + 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, + int d=-1, int h=-1) : ASAP(asap), ALAP(alap), + MOB(mob), depth(d), + height(h) {} + }; + + + typedef std::vector SuperBlock; + + class ModuloSchedulingSBPass : public FunctionPass { + const TargetMachine ⌖ + + //Map to hold Value* defs + std::map defMap; + + //Map to hold list of instructions associate to the induction var for each BB + std::map > indVarInstrs; + + //Map to hold machine to llvm instrs for each valid BB + std::map > machineTollvm; + + //LLVM Instruction we know we can add TmpInstructions to its MCFI + Instruction *defaultInst; + + //Map that holds node to node attribute information + std::map nodeToAttributesMap; + + //Map to hold all reccurrences + std::set > > recurrenceList; + + //Set of edges to ignore, stored as src node and index into vector of successors + std::set > edgesToIgnore; + + //Vector containing the partial order + std::vector > partialOrder; + + //Vector containing the final node order + std::vector FinalNodeOrder; + + //Schedule table, key is the cycle number and the vector is resource, node pairs + MSSchedule schedule; + + //Current initiation interval + int II; + + //Internal Functions + void FindSuperBlocks(Function &F, LoopInfo &LI, + std::vector > &Worklist); + bool MachineBBisValid(const MachineBasicBlock *B); + bool CreateDefMap(std::vector &SB); + + public: + ModuloSchedulingSBPass(TargetMachine &targ) : target(targ) {} + virtual bool runOnFunction(Function &F); + virtual const char* getPassName() const { return "ModuloScheduling-SuperBlock"; } + + + // getAnalysisUsage + virtual void getAnalysisUsage(AnalysisUsage &AU) const { + AU.addRequired(); + AU.addRequired(); + } + }; +} +#endif -- 2.11.4.GIT