BBSchedulerController Class Reference

#include <BBSchedulerController.hh>

Inheritance diagram for BBSchedulerController:

Collaboration diagram for BBSchedulerController:

Public Member Functions
	BBSchedulerController (const TTAMachine::Machine &targetMachine, InterPassData &data, SoftwareBypasser *bypasser=NULL, CopyingDelaySlotFiller *delaySlotFiller=NULL, DataDependenceGraph *bigDDG=NULL)
virtual	~BBSchedulerController ()
virtual void	handleBasicBlock (TTAProgram::BasicBlock &bb, const TTAMachine::Machine &targetMachine, TTAProgram::InstructionReferenceManager &irm, BasicBlockNode *bbn=NULL) override
virtual void	handleControlFlowGraph (ControlFlowGraph &cfg, const TTAMachine::Machine &targetMachine) override
virtual void	handleProcedure (TTAProgram::Procedure &procedure, const TTAMachine::Machine &targetMachine) override
virtual void	handleProgram (TTAProgram::Program &program, const TTAMachine::Machine &targetMachine) override
bool	handleBBNode (ControlFlowGraph &cfg, BasicBlockNode &bbn, const TTAMachine::Machine &targetMachine, int nodeCount)
virtual void	executeDDGPass (TTAProgram::BasicBlock &bb, const TTAMachine::Machine &targetMachine, TTAProgram::InstructionReferenceManager &irm, std::vector< DDGPass * > ddgPasses, BasicBlockNode *bbn=NULL) override
virtual void	handleCFGDDG (ControlFlowGraph &cfg, DataDependenceGraph *ddg, const TTAMachine::Machine &targetMachine)
virtual std::string	shortDescription () const override
virtual std::string	longDescription () const override
Public Member Functions inherited from BasicBlockPass
	BasicBlockPass (InterPassData &data)
virtual	~BasicBlockPass ()
virtual bool	executeLoopPass (TTAProgram::BasicBlock &bb, const TTAMachine::Machine &targetMachine, TTAProgram::InstructionReferenceManager &irm, std::vector< DDGPass * > ddgPasses, BasicBlockNode *bbn=NULL)
virtual DataDependenceGraphBuilder &	ddgBuilder ()
Public Member Functions inherited from SchedulerPass
	SchedulerPass (InterPassData &data)
virtual	~SchedulerPass ()
InterPassData &	interPassData ()
Public Member Functions inherited from ControlFlowGraphPass
	ControlFlowGraphPass (InterPassData &data)
virtual	~ControlFlowGraphPass ()
void	executeBasicBlockPass (ControlFlowGraph &cfg, const TTAMachine::Machine &targetMachine, BasicBlockPass &bbPass)
Public Member Functions inherited from ProcedurePass
	ProcedurePass (InterPassData &data)
virtual	~ProcedurePass ()
Public Member Functions inherited from ProgramPass
	ProgramPass (InterPassData &data)
virtual	~ProgramPass ()

Protected Member Functions
virtual DataDependenceGraph *	createDDGFromBB (TTAProgram::BasicBlock &bb, const TTAMachine::Machine &mach)
Protected Member Functions inherited from BasicBlockPass
void	ddgSnapshot (DataDependenceGraph *ddg, std::string &name, DataDependenceGraph::DumpFileFormat format, bool final)

Private Attributes
const TTAMachine::Machine &	targetMachine_
TTAProgram::Procedure *	scheduledProcedure_
	The currently scheduled procedure.
ControlFlowGraph *	cfg_
	Control flow graph of the procedure.
DataDependenceGraph *	bigDDG_
	whole-procedure DDG.
SoftwareBypasser *	softwareBypasser_
	The software bypasser to use to bypass registers when possible.
CopyingDelaySlotFiller *	delaySlotFiller_
int	basicBlocksScheduled_
	Number of basic blocks scheduled so far.
int	totalBasicBlocks_
	Total basic blocks in the CFG currently being scheduled.
LLVMTCECmdLineOptions *	options_

Additional Inherited Members
Static Public Member Functions inherited from BasicBlockPass
static void	copyRMToBB (SimpleResourceManager &rm, TTAProgram::BasicBlock &bb, const TTAMachine::Machine &targetMachine, TTAProgram::InstructionReferenceManager &irm, int lastCycle=-1)
Static Public Member Functions inherited from ProcedurePass
static void	copyCfgToProcedure (TTAProgram::Procedure &procedure, ControlFlowGraph &cfg)
static void	executeControlFlowGraphPass (TTAProgram::Procedure &procedure, const TTAMachine::Machine &targetmachine, ControlFlowGraphPass &cfgp)
Static Public Member Functions inherited from ProgramPass
static void	executeProcedurePass (TTAProgram::Program &program, const TTAMachine::Machine &targetMachine, ProcedurePass &procedurePass)

Detailed Description

A class that control operation of a basic block scheduler.

This class handles calling other optimization passes and tranferring data for the actual BB scheduler and loop scheudlers etc.

Definition at line 60 of file BBSchedulerController.hh.

Constructor & Destructor Documentation

BBSchedulerController()

BBSchedulerController::BBSchedulerController	(	const TTAMachine::Machine &	targetMachine,
		InterPassData &	data,
		SoftwareBypasser *	bypasser = NULL,
		CopyingDelaySlotFiller *	delaySlotFiller = NULL,
		DataDependenceGraph *	bigDDG = NULL
	)

Constructs the basic block scheduler.

Parameters

data	Interpass data
bypasser	Helper module implementing software bypassing
delaySlotFiller	Helper module implementing jump delay slot filling

Definition at line 90 of file BBSchedulerController.cc.

    : BasicBlockPass(data),
      ControlFlowGraphPass(data),
      ProcedurePass(data),
      ProgramPass(data),
      targetMachine_(targetMachine),
      scheduledProcedure_(NULL),
      bigDDG_(bigDDG),
      softwareBypasser_(bypasser),
      delaySlotFiller_(delaySlotFiller),
      basicBlocksScheduled_(0),
      totalBasicBlocks_(0) {
    CmdLineOptions *cmdLineOptions = Application::cmdLineOptions();
    options_ = dynamic_cast<LLVMTCECmdLineOptions*>(cmdLineOptions);
}

References Application::cmdLineOptions(), and options_.

Here is the call graph for this function:

~BBSchedulerController()

BBSchedulerController::~BBSchedulerController ( )

virtual

Definition at line 109 of file BBSchedulerController.cc.

                                              {
}

Member Function Documentation

createDDGFromBB()

DataDependenceGraph * BBSchedulerController::createDDGFromBB ( TTAProgram::BasicBlock &  bb, const TTAMachine::Machine &  mach  )

protectedvirtual

Helper function used to create DDG for BBPass.

Overrided version in order to use subgraphs.

Parameters

bb	BasicBlock where DDG is to be created from

Reimplemented from BasicBlockPass.

Definition at line 438 of file BBSchedulerController.cc.

                                                                 {
    if (bigDDG_ != NULL) {
        return bigDDG_->createSubgraph(bb);
    } else {
        return this->ddgBuilder().build(
bb, DataDependenceGraph::INTRA_BB_ANTIDEPS, mach,
            scheduledProcedure_->name() + '_' + 
            Conversion::toString(basicBlocksScheduled_) + ".dot");
    }
}

References basicBlocksScheduled_, bigDDG_, DataDependenceGraphBuilder::build(), DataDependenceGraph::createSubgraph(), BasicBlockPass::ddgBuilder(), DataDependenceGraph::INTRA_BB_ANTIDEPS, TTAProgram::Procedure::name(), scheduledProcedure_, and Conversion::toString().

Referenced by executeDDGPass().

Here is the call graph for this function:

executeDDGPass()

void BBSchedulerController::executeDDGPass ( TTAProgram::BasicBlock &  bb, const TTAMachine::Machine &  targetMachine, TTAProgram::InstructionReferenceManager &  irm, std::vector< DDGPass * >  ddgPasses, BasicBlockNode *  bbn = NULL  )

overridevirtual

Creates a DDG from the given basic block and executes the set of DDG passes for that.

Reimplemented from BasicBlockPass.

Definition at line 455 of file BBSchedulerController.cc.

                                                        {
    int minCycle = 0;
    DataDependenceGraph* ddg = NULL;
    SimpleResourceManager* rm = NULL;
    // Used for live info dumping.
    static int bbNumber = 0;
    int min = INT_MAX;
    int fastest = 0;
    if (ddgPasses.size() > 1) {
        for (unsigned int i = 0; i < ddgPasses.size(); i++) {
            ddg = createDDGFromBB(bb, targetMachine);
            rm = SimpleResourceManager::createRM(targetMachine);
            rm->setDDG(ddg);
            rm->setCFG(cfg_);
            rm->setBBN(bbn);
 
            int size =
                ddgPasses[i]->handleDDG(*ddg, *rm, targetMachine, minCycle, true);
            if (size < min) {
                min = size;
                fastest = i;
            }
            SimpleResourceManager::disposeRM(rm);
            delete ddg;  
            ddg = NULL;
        }
    }
    ddg = createDDGFromBB(bb, targetMachine);
    rm = SimpleResourceManager::createRM(targetMachine);
    rm->setDDG(static_cast<DataDependenceGraph*>(ddg->rootGraph()));
    rm->setCFG(cfg_);
    rm->setBBN(bbn);
 
    if (options_ != NULL && options_->printResourceConstraints()) {
        TCEString ddgName = ddg->name();
        // Use the BBN id if possible so it's easier to find the matching BBs when
        // looking at the if-conversion CFGs.
        if (bbn != NULL)
            ddgName << bbn->nodeID(); 
        else
            ddgName << bbNumber;
        ResourceConstraintAnalyzer rcAnalyzer(*ddg, *rm, ddgName);
        rcAnalyzer.analyzePreSchedule();
    }
 
    
#ifdef DDG_SNAPSHOTS
    std::string name = "scheduling";
    ddgSnapshot(ddg, name, false);
#endif
 
    try {
        ddgPasses[fastest]->handleDDG(*ddg, *rm, targetMachine, minCycle);
        if (bbn->isHWLoop()) {
            bbn->predecessor()->updateHWloopLength(
                ddg->largestCycle() + 1 - ddg->smallestCycle());
        }
    } catch (const Exception &e) {
        debugLog(e.errorMessageStack());
        abortWithError("Scheduling failed!");
    }
 
#ifdef DDG_SNAPSHOTS
    std::string name = "scheduling";
    ddgSnapshot(ddg, name, true);
#endif
 
    copyRMToBB(*rm, bb, targetMachine, irm);
 
    bbNumber++;
 
    if (options_ != NULL && options_->printResourceConstraints()) {
        TCEString ddgName = ddg->name();
        // Use the BBN id if possible so it's easier to find the matching BBs when
        // looking at the if-conversion CFGs.
        if (bbn != NULL)
            ddgName << bbn->nodeID(); 
        else
            ddgName << bbNumber;
        ResourceConstraintAnalyzer rcAnalyzer(*ddg, *rm, ddgName);
        rcAnalyzer.analyze();
    }
    
    if (delaySlotFiller_ != NULL && bigDDG_ != NULL) {
        rm->clearOldResources();
        delaySlotFiller_->addResourceManager(bb, *rm);
    } else {
        SimpleResourceManager::disposeRM(rm);
    }
 
    // print some stats about the loop kernel body DDGs
    if (Application::verboseLevel() > 1 && bb.isInInnerLoop()) {
        Application::logStream()
            << "DDG height " <<  ddg->height() << std::endl;        
    }
 
    delete ddg;
}

References abortWithError, CopyingDelaySlotFiller::addResourceManager(), ResourceConstraintAnalyzer::analyze(), ResourceConstraintAnalyzer::analyzePreSchedule(), bigDDG_, cfg_, SimpleResourceManager::clearOldResources(), BasicBlockPass::copyRMToBB(), createDDGFromBB(), SimpleResourceManager::createRM(), BasicBlockPass::ddgSnapshot(), debugLog, delaySlotFiller_, SimpleResourceManager::disposeRM(), Exception::errorMessageStack(), BoostGraph< GraphNode, GraphEdge >::height(), BasicBlockNode::isHWLoop(), TTAProgram::BasicBlock::isInInnerLoop(), DataDependenceGraph::largestCycle(), Application::logStream(), BoostGraph< GraphNode, GraphEdge >::name(), GraphNode::nodeID(), options_, BasicBlockNode::predecessor(), SchedulerCmdLineOptions::printResourceConstraints(), BoostGraph< GraphNode, GraphEdge >::rootGraph(), SimpleResourceManager::setBBN(), SimpleResourceManager::setCFG(), SimpleResourceManager::setDDG(), DataDependenceGraph::smallestCycle(), BasicBlockNode::updateHWloopLength(), and Application::verboseLevel().

Referenced by handleBasicBlock().

Here is the call graph for this function:

handleBasicBlock()

void BBSchedulerController::handleBasicBlock ( TTAProgram::BasicBlock &  bb, const TTAMachine::Machine &  targetMachine, TTAProgram::InstructionReferenceManager &  irm, BasicBlockNode *  bbn = NULL  )

overridevirtual

Schedules a single basic block.

Parameters

bb	The basic block to schedule.
targetMachine	The target machine.

Exceptions

Exception

several TCE exceptions can be thrown in case of a scheduling error.

Reimplemented from BasicBlockPass.

Definition at line 121 of file BBSchedulerController.cc.

                                                                     {
    // TODO: define them somewhere in one place.
    static const TCEString SP_DATUM = "STACK_POINTER";
    static const TCEString FP_DATUM = "FRAME_POINTER";
    static const TCEString RV_DATUM = "RV_REGISTER";
    // high part of 64-bit return values.
    static const TCEString RV_HIGH_DATUM = "RV_HIGH_REGISTER";
 
    if (bb.instructionCount() == 0)
        return;
 
    bool bbScheduled = false;
 
    RegisterRenamer* rr = NULL;
 
    SchedulerCmdLineOptions* options =
        dynamic_cast<SchedulerCmdLineOptions*>(
            Application::cmdLineOptions());
 
    // create register renamer if enabled and we know the
    // reserved registers.
    if (options != NULL && options->renameRegisters() && bigDDG_ != NULL
        && BasicBlockPass::interPassData().hasDatum(SP_DATUM) &&
        BasicBlockPass::interPassData().hasDatum(FP_DATUM) &&
        BasicBlockPass::interPassData().hasDatum(RV_DATUM) &&
        BasicBlockPass::interPassData().hasDatum(RV_DATUM)) {
        rr = new RegisterRenamer(targetMachine, bbn->basicBlock());
    }
 
    std::vector<DDGPass*> bbSchedulers;
 
    if (options_ != NULL && options_->useBubbleFish2Scheduler()) {
        bbSchedulers.push_back(new BF2Scheduler(
                                   BasicBlockPass::interPassData(), rr));
    } else if (options_ != NULL && options_->useBUScheduler()) {
        bbSchedulers.push_back(new BUBasicBlockScheduler(
                BasicBlockPass::interPassData(), softwareBypasser_, rr));
    } else if (options_ != NULL && options_->useTDScheduler()) {
        bbSchedulers.push_back(new BasicBlockScheduler(
            BasicBlockPass::interPassData(), softwareBypasser_, rr));
    } else {
        bbSchedulers.push_back(new BF2Scheduler(
                                   BasicBlockPass::interPassData(), rr));
    }
 
    if (options_->isLoopOptDefined() &&
        cfg_->isSingleBBLoop(*bbn) && 
        bb.lastInstruction().hasJump() &&
        bigDDG_ != NULL) {
 
        LoopAnalyzer::LoopAnalysisResult* analysis = NULL;
        if (Application::verboseLevel() > 1) {
            Application::logStream() 
                << "CFG detects single BB loop" << std::endl
                << "tripcount: " << bb.tripCount() << std::endl;
        }
        if (bigDDG_ && bb.tripCount() == 0 && options_->useBubbleFish2Scheduler()) {
            analysis = LoopAnalyzer::analyze(*bbn, *bigDDG_);
            if (analysis != NULL) {
                bb.setTripCount(analysis->iterationCount);
                if (analysis->counterValueNode == NULL) {
                    if (Application::verboseLevel() > 1) {
                        Application::logStream() 
                            << "loop analyzis analyzed loop to have fixed trip count"
                            << analysis->iterationCount << std::endl;
                    }
                } else {
                    if (Application::verboseLevel() > 1) {
                        Application::logStream() 
                            << "loop analyzis analyzed loop to have variable trip count"
                            << analysis->counterValueNode->toString()
                            << " + "
                            << analysis->iterationCount << " divided by"
                            << analysis->counterMultiplier << std::endl;
                    }   
                }
            }
        }
        
        if ((((bb.tripCount() > 0 || (analysis && analysis->counterValueNode)) &&
              MachineConnectivityCheck::tempRegisterFiles(targetMachine).empty()) ||
             options_->useBubbleFish2Scheduler())) {
            if (analysis) {
                (static_cast<BF2Scheduler*>(bbSchedulers[0]))->
                    setLoopLimits(analysis);
            }
            // software pipeline instead of calling the flat BB scheduler
            if (Application::verboseLevel() > 1) {
                Application::logStream()
                    << "executing loop pass with trip count " << bb.tripCount()
                    << std::endl;
            }
            
            if (executeLoopPass(
                    bb, targetMachine, irm, bbSchedulers, bbn) ) {
                bbScheduled = true;
            } else {
                if (Application::verboseLevel() > 1) {
                    Application::logStream()
                        << "loop scheduler failed, using basic block "
                        << "scheduler instead" << std::endl;
                }
                bbScheduled = false;
            }
        }
        // if not scheduled yet (or loop scheduling failed)
    }
    if (!bbScheduled) {
 
        executeDDGPass(
            bb, targetMachine, irm, bbSchedulers, bbn);
 
        ++basicBlocksScheduled_;
    }
    if (rr != NULL) {
        delete rr;
    }
 
    // these are no longer needed. delete them to save memory.
    if (bb.liveRangeData_ != NULL) {
        bb.liveRangeData_->regFirstDefines_.clear();
        bb.liveRangeData_->regDefines_.clear();
        bb.liveRangeData_->regLastUses_.clear();
        
        bb.liveRangeData_->regDefReaches_.clear();
        bb.liveRangeData_->registersUsedAfter_.clear();
        bb.liveRangeData_->regFirstUses_.clear();
        bb.liveRangeData_->regDefines_.clear();
    } else {
        std::cerr << "Wargning: BB liverange data null for: " 
                  << bbn->toString() << std::endl;
    }
    for (unsigned int i = 0; i < bbSchedulers.size(); i++)
        delete bbSchedulers[i];
}

References LoopAnalyzer::analyze(), BasicBlockNode::basicBlock(), basicBlocksScheduled_, bigDDG_, cfg_, Application::cmdLineOptions(), LoopAnalyzer::LoopAnalysisResult::counterMultiplier, LoopAnalyzer::LoopAnalysisResult::counterValueNode, executeDDGPass(), BasicBlockPass::executeLoopPass(), InterPassData::hasDatum(), TTAProgram::Instruction::hasJump(), TTAProgram::CodeSnippet::instructionCount(), SchedulerPass::interPassData(), SchedulerCmdLineOptions::isLoopOptDefined(), ControlFlowGraph::isSingleBBLoop(), LoopAnalyzer::LoopAnalysisResult::iterationCount, TTAProgram::CodeSnippet::lastInstruction(), TTAProgram::BasicBlock::liveRangeData_, Application::logStream(), options, options_, LiveRangeData::regDefines_, LiveRangeData::regDefReaches_, LiveRangeData::regFirstDefines_, LiveRangeData::regFirstUses_, LiveRangeData::registersUsedAfter_, LiveRangeData::regLastUses_, TTAProgram::BasicBlock::setTripCount(), softwareBypasser_, MachineConnectivityCheck::tempRegisterFiles(), BasicBlockNode::toString(), MoveNode::toString(), TTAProgram::BasicBlock::tripCount(), LLVMTCECmdLineOptions::useBubbleFish2Scheduler(), LLVMTCECmdLineOptions::useBUScheduler(), LLVMTCECmdLineOptions::useTDScheduler(), and Application::verboseLevel().

Referenced by handleBBNode().

Here is the call graph for this function:

handleBBNode()

bool BBSchedulerController::handleBBNode	(	ControlFlowGraph &	cfg,
		BasicBlockNode &	bbn,
		const TTAMachine::Machine &	targetMachine,
		int	nodeCount
	)

Definition at line 558 of file BBSchedulerController.cc.

                                                           {
 
    TCEString procName = cfg.procedureName();
    if (procName == "") procName = cfg.name();
 
    if (!bb.isNormalBB() || bb.isScheduled()) {
        return false;
    }
 
    handleBasicBlock(
        bb.basicBlock(), targetMachine,
        cfg.instructionReferenceManager(), &bb);
    bb.setScheduled();
 
    if (delaySlotFiller_ != NULL && bigDDG_ != NULL) {
        delaySlotFiller_->bbnScheduled(bb);
    }
 
    // if some node is removed, make sure does not skip some node and
    // then try to handle too many nodes.
    if (cfg.nodeCount() != nodeCount) {
        return true;
    }
    return false;
}

References BasicBlockNode::basicBlock(), CopyingDelaySlotFiller::bbnScheduled(), bigDDG_, delaySlotFiller_, handleBasicBlock(), ControlFlowGraph::instructionReferenceManager(), BasicBlockNode::isNormalBB(), BasicBlockNode::isScheduled(), BoostGraph< GraphNode, GraphEdge >::name(), BoostGraph< GraphNode, GraphEdge >::nodeCount(), ControlFlowGraph::procedureName(), and BasicBlockNode::setScheduled().

Referenced by handleCFGDDG().

Here is the call graph for this function:

handleCFGDDG()

void BBSchedulerController::handleCFGDDG ( ControlFlowGraph &  cfg, DataDependenceGraph *  ddg, const TTAMachine::Machine &  targetMachine  )

virtual

Definition at line 586 of file BBSchedulerController.cc.

                                            {
    cfg_ = &cfg;
    bigDDG_ = ddg;
 
    ScheduleEstimator est(ProcedurePass::interPassData());
    est.handleControlFlowGraph(cfg, targetMachine);
 
    int nodeCount = cfg.nodeCount();
 
    // for handle single-BB-loops
    for (int bbIndex = 0; bbIndex < nodeCount; ++bbIndex) {
        BasicBlockNode& bb = cfg.node(bbIndex);
        if (!cfg.isSingleBBLoop(bb)) {
            continue;
        }
 
        if (handleBBNode(cfg, bb, targetMachine, nodeCount)) {
            nodeCount = cfg.nodeCount();
            bbIndex = 0;
        }
    }
 
    // then handle BBs which do not have outgoing jumps.
    for (int bbIndex = 0; bbIndex < nodeCount; ++bbIndex) {
        BasicBlockNode& bb = cfg.node(bbIndex);
        auto jumpDest = cfg.jumpSuccessor(bb);
        if (jumpDest != nullptr && jumpDest->isNormalBB()) {
            continue;
        }
 
        if (handleBBNode(cfg, bb, targetMachine, nodeCount)) {
            nodeCount = cfg.nodeCount();
            bbIndex = 0;
        }
    }
 
 
    for (int bbIndex = cfg.nodeCount() -1; bbIndex >= 0; --bbIndex) {
        BasicBlockNode& bb = cfg.node(bbIndex);
        auto jumpDest = cfg.jumpSuccessor(bb);
        if (jumpDest == nullptr || !jumpDest->isNormalBB()) {
            continue;
        }
 
        if (cfg.allScheduledInBetween(bb, *jumpDest)) {
            if (handleBBNode(cfg, bb, targetMachine, nodeCount)) {
                nodeCount = cfg.nodeCount();
                bbIndex = nodeCount -1;
            }
        }
    }
 
    for (int bbIndex = cfg.nodeCount() -1; bbIndex >= 0; --bbIndex) {
        BasicBlockNode& bb = cfg.node(bbIndex);
        if (handleBBNode(cfg, bb, targetMachine, nodeCount)) {
            nodeCount = cfg.nodeCount();
            bbIndex = nodeCount -1;
        }
    }
}

References ControlFlowGraph::allScheduledInBetween(), bigDDG_, cfg_, handleBBNode(), ScheduleEstimator::handleControlFlowGraph(), SchedulerPass::interPassData(), ControlFlowGraph::isSingleBBLoop(), ControlFlowGraph::jumpSuccessor(), BoostGraph< GraphNode, GraphEdge >::node(), and BoostGraph< GraphNode, GraphEdge >::nodeCount().

Referenced by llvm::LLVMTCEIRBuilder::compileOptimized(), and handleControlFlowGraph().

Here is the call graph for this function:

handleControlFlowGraph()

void BBSchedulerController::handleControlFlowGraph ( ControlFlowGraph &  cfg, const TTAMachine::Machine &  targetMachine  )

overridevirtual

Schedules all nodes in a control flow graph.

The original control flow graph nodes are modified during scheduling.

Parameters

cfg	The control flow graph to schedule.
targetMachine	The target machine.

Exceptions

Exception

In case of an error during scheduling. The exception type can be any subtype of Exception.

Reimplemented from ControlFlowGraphPass.

Definition at line 381 of file BBSchedulerController.cc.

                                                                   {
    return handleCFGDDG(cfg, bigDDG_, targetMachine);
}

References bigDDG_, and handleCFGDDG().

Referenced by handleProcedure().

Here is the call graph for this function:

handleProcedure()

void BBSchedulerController::handleProcedure ( TTAProgram::Procedure &  procedure, const TTAMachine::Machine &  targetMachine  )

overridevirtual

Schedules a procedure.

The original procedure is modified during scheduling.

Parameters

procedure	The procedure to schedule.
targetMachine	The target machine.

Todo:

remove the targetMachine argument. The machine is given in the constructor and assumed to be the same for whole lifetime of the scheduler instance.

Exceptions

Exception

In case of an error during scheduling. The exception type can be any subtype of Exception.

Reimplemented from ProcedurePass.

Definition at line 277 of file BBSchedulerController.cc.

                                            {
    ControlFlowGraph cfg(procedure, BasicBlockPass::interPassData());
 
    if (Application::verboseLevel() > 0) {
        totalBasicBlocks_ = cfg.nodeCount() - 3;
        Application::logStream() 
            << " -- " << totalBasicBlocks_ << " basic blocks" << std::endl;
        basicBlocksScheduled_ = 0;
    }
 
#ifdef CFG_SNAPSHOTS
    cfg.writeToDotFile(procedure.name() + "_cfg.dot");
#endif
 
    SchedulerCmdLineOptions* opts =
        dynamic_cast<SchedulerCmdLineOptions*>(Application::cmdLineOptions());
    int lowMemThreshold = DEFAULT_LOWMEM_MODE_THRESHOLD;
 
    if (opts != NULL && opts->lowMemModeThreshold() > -1) {
        lowMemThreshold = opts->lowMemModeThreshold();
    }
    
    if (procedure.instructionCount() < lowMemThreshold) {
        // create the procedure-wide ddg.
        bigDDG_ = ddgBuilder().build(
            cfg, DataDependenceGraph::SINGLE_BB_LOOP_ANTIDEPS, targetMachine);
 
        if (options_ != NULL && options_->dumpDDGsDot()) {
            bigDDG_->writeToDotFile( 
                (boost::format("proc_%s_before_scheduling.dot") % 
                 bigDDG_->name()).str());
        }
 
        if (options_ != NULL && options_->dumpDDGsXML()) {
            bigDDG_->writeToXMLFile( 
                (boost::format("proc_%s_before_scheduling.xml") % 
                 bigDDG_->name()).str());
        }
    }
 
    if (delaySlotFiller_ != NULL && bigDDG_ != NULL) {
        delaySlotFiller_->initialize(cfg, *bigDDG_, targetMachine);
    }
 
#ifdef BIG_DDG_SNAPSHOTS
    bigDDG_->writeToDotFile(bigDDG_->name() + "_unscheduled_ddg.dot");
#endif
    scheduledProcedure_ = &procedure;
 
    // dsf also called between scheduling.. have to update these before it.
    // delay slot filler needs refs to be into instrs in cfg, not in
    // original program
    cfg.updateReferencesFromProcToCfg();
 
    procedure.clear();
 
    handleControlFlowGraph(cfg, targetMachine);
 
    if (delaySlotFiller_ != NULL && bigDDG_ != NULL) {
        delaySlotFiller_->fillDelaySlots(cfg, *bigDDG_, targetMachine);
    }
 
#ifdef CFG_SNAPSHOTS
    cfg.writeToDotFile(procedure.name() + "_cfg_after.dot");
#endif
 
    // now all basic blocks are scheduled, let's put them back to the
    // original procedure
    cfg.copyToProcedure(procedure);
    if (bigDDG_ != NULL) {
 
        if (options_ != NULL && options_->dumpDDGsDot()) {
            bigDDG_->writeToDotFile(
                (boost::format("proc_%s_after_scheduling.dot") % bigDDG_->name())
                .str());
        } 
 
        if (options_ != NULL && options_->dumpDDGsXML()) {
            bigDDG_->writeToXMLFile(
                (boost::format("proc_%s_after_scheduling.xml") % bigDDG_->name())
                .str());
        } 
        delete bigDDG_;
        bigDDG_ = NULL;
    }
    if (delaySlotFiller_ != NULL) {
        delaySlotFiller_->finalizeProcedure();
    }
    scheduledProcedure_ = NULL;
}

References basicBlocksScheduled_, bigDDG_, DataDependenceGraphBuilder::build(), TTAProgram::Procedure::clear(), Application::cmdLineOptions(), ControlFlowGraph::copyToProcedure(), BasicBlockPass::ddgBuilder(), DEFAULT_LOWMEM_MODE_THRESHOLD, delaySlotFiller_, LLVMTCECmdLineOptions::dumpDDGsDot(), LLVMTCECmdLineOptions::dumpDDGsXML(), CopyingDelaySlotFiller::fillDelaySlots(), CopyingDelaySlotFiller::finalizeProcedure(), handleControlFlowGraph(), CopyingDelaySlotFiller::initialize(), TTAProgram::CodeSnippet::instructionCount(), SchedulerPass::interPassData(), Application::logStream(), SchedulerCmdLineOptions::lowMemModeThreshold(), BoostGraph< GraphNode, GraphEdge >::name(), TTAProgram::Procedure::name(), BoostGraph< GraphNode, GraphEdge >::nodeCount(), options_, scheduledProcedure_, DataDependenceGraph::SINGLE_BB_LOOP_ANTIDEPS, totalBasicBlocks_, ControlFlowGraph::updateReferencesFromProcToCfg(), Application::verboseLevel(), GraphBase< GraphNode, GraphEdge >::writeToDotFile(), and DataDependenceGraph::writeToXMLFile().

Referenced by llvm::LLVMTCEIRBuilder::doFinalization().

Here is the call graph for this function:

handleProgram()

void BBSchedulerController::handleProgram ( TTAProgram::Program &  program, const TTAMachine::Machine &  targetMachine  )

overridevirtual

Schedules a program.

The original program is modified during scheduling.

Parameters

program	The program to schedule.
targetMachine	The target machine.

Exceptions

Exception

In case of an error during scheduling. The exception type can be any subtype of Exception.

Reimplemented from ProgramPass.

Definition at line 397 of file BBSchedulerController.cc.

                                                                        {
    ProgramPass::executeProcedurePass(program, targetMachine, *this);
}

References ProgramPass::executeProcedurePass(), and program.

Here is the call graph for this function:

longDescription()

std::string BBSchedulerController::longDescription ( ) const

overridevirtual

Optional longer description of the pass.

This description can include usage instructions, details of choice of algorithmic details, etc.

Returns

The description as a string.

Reimplemented from SchedulerPass.

Definition at line 422 of file BBSchedulerController.cc.

                                             {
    return
        "Basic block scheduler that uses the longest path information of "
        "data dependency graph to prioritize the ready list. Assumes that "
        "the input has registers allocated and no connectivity missing.";
}

shortDescription()

std::string BBSchedulerController::shortDescription ( ) const

overridevirtual

A short description of the pass, usually the optimization name, such as "basic block scheduler".

Returns

The description as a string.

Implements SchedulerPass.

Definition at line 409 of file BBSchedulerController.cc.

                                              {
    return "Instruction scheduler with a basic block scope.";
}

Member Data Documentation

basicBlocksScheduled_

int BBSchedulerController::basicBlocksScheduled_

private

Number of basic blocks scheduled so far.

Definition at line 128 of file BBSchedulerController.hh.

Referenced by createDDGFromBB(), handleBasicBlock(), and handleProcedure().

bigDDG_

DataDependenceGraph* BBSchedulerController::bigDDG_

private

whole-procedure DDG.

Definition at line 121 of file BBSchedulerController.hh.

Referenced by createDDGFromBB(), executeDDGPass(), handleBasicBlock(), handleBBNode(), handleCFGDDG(), handleControlFlowGraph(), and handleProcedure().

cfg_

ControlFlowGraph* BBSchedulerController::cfg_

private

Control flow graph of the procedure.

Definition at line 118 of file BBSchedulerController.hh.

Referenced by executeDDGPass(), handleBasicBlock(), and handleCFGDDG().

delaySlotFiller_

CopyingDelaySlotFiller* BBSchedulerController::delaySlotFiller_

private

Definition at line 125 of file BBSchedulerController.hh.

Referenced by executeDDGPass(), handleBBNode(), and handleProcedure().

options_

LLVMTCECmdLineOptions* BBSchedulerController::options_

private

Definition at line 132 of file BBSchedulerController.hh.

Referenced by BBSchedulerController(), executeDDGPass(), handleBasicBlock(), and handleProcedure().

scheduledProcedure_

TTAProgram::Procedure* BBSchedulerController::scheduledProcedure_

private

The currently scheduled procedure.

Definition at line 115 of file BBSchedulerController.hh.

Referenced by createDDGFromBB(), and handleProcedure().

softwareBypasser_

SoftwareBypasser* BBSchedulerController::softwareBypasser_

private

The software bypasser to use to bypass registers when possible.

Definition at line 123 of file BBSchedulerController.hh.

Referenced by handleBasicBlock().

targetMachine_

const TTAMachine::Machine& BBSchedulerController::targetMachine_

private

Definition at line 112 of file BBSchedulerController.hh.

totalBasicBlocks_

int BBSchedulerController::totalBasicBlocks_

private

Total basic blocks in the CFG currently being scheduled.

Definition at line 130 of file BBSchedulerController.hh.

Referenced by handleProcedure().

---

The documentation for this class was generated from the following files:

• BBSchedulerController.hh
• BBSchedulerController.cc