BasicBlockPass Class Reference

#include <BasicBlockPass.hh>

Inheritance diagram for BasicBlockPass:

Collaboration diagram for BasicBlockPass:

Public Member Functions
	BasicBlockPass (InterPassData &data)
virtual	~BasicBlockPass ()
virtual void	handleBasicBlock (TTAProgram::BasicBlock &basicBlock, const TTAMachine::Machine &targetMachine, TTAProgram::InstructionReferenceManager &irm, BasicBlockNode *bbn=NULL)
virtual void	executeDDGPass (TTAProgram::BasicBlock &bb, const TTAMachine::Machine &targetMachine, TTAProgram::InstructionReferenceManager &irm, std::vector< DDGPass * > ddgPasses, BasicBlockNode *bbn=NULL)
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 ()
virtual std::string	shortDescription () const =0
virtual std::string	longDescription () const

Static Public Member Functions
static void	copyRMToBB (SimpleResourceManager &rm, TTAProgram::BasicBlock &bb, const TTAMachine::Machine &targetMachine, TTAProgram::InstructionReferenceManager &irm, int lastCycle=-1)

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

Private Attributes
DataDependenceGraphBuilder	ddgBuilder_

Detailed Description

Interface for scheduler passes that handle basic blocks.

Definition at line 60 of file BasicBlockPass.hh.

Constructor & Destructor Documentation

BasicBlockPass()

BasicBlockPass::BasicBlockPass

(

InterPassData &

data

)

Constructor.

Definition at line 51 of file BasicBlockPass.cc.

                                                  : 
    SchedulerPass(data), ddgBuilder_(data) {
}

~BasicBlockPass()

BasicBlockPass::~BasicBlockPass ( )

virtual

Destructor.

Definition at line 58 of file BasicBlockPass.cc.

                                {
}

Member Function Documentation

copyRMToBB()

void BasicBlockPass::copyRMToBB ( SimpleResourceManager &  rm, TTAProgram::BasicBlock &  bb, const TTAMachine::Machine &  targetMachine, TTAProgram::InstructionReferenceManager &  irm, int  lastCycle = -1  )

static

Copies moves back from resourcemanager to basicblock, putting them to correct instructions based in their cycle, and adding the final delay slots.

Parameters

rm	the resourcemanager
bb	the basicblock
targetMachine	machine we are scheduling for.
irm	IRM to keep book of the instruction references.
lastCycle	the last instruction cycle of BB to copy.

Returns

number of cycles/instructions copied.

Definition at line 213 of file BasicBlockPass.cc.

                                                               {
 
    // find the largest cycle any of a pipelines is still used
    if (lastCycle == -1) {
        const int rmLastCycle = rm.largestCycle();
        lastCycle = rmLastCycle;
    }
 
    // only first ins of bb may have incoming references
    for (int i = 1; i < bb.instructionCount(); i++) {
        if (irm.hasReference(bb.instructionAtIndex(i))) {
            std::cerr << "non-first has ref:, index: " << i <<
                " bb size: " << bb.instructionCount() << std::endl;
        }
        assert (!irm.hasReference(bb.instructionAtIndex(i)));
    }
 
    TTAProgram::Instruction refHolder;
    if (bb.instructionCount() && irm.hasReference(bb.instructionAtIndex(0))) {
        irm.replace(bb.instructionAtIndex(0), refHolder);
    }
 
    int moveCount = 0;
 
    // update the BB with the new instructions
    bb.clear();
 
    int index = rm.smallestCycle();
    if (rm.initiationInterval() > 0 && rm.initiationInterval() != INT_MAX) {
        lastCycle = rm.initiationInterval() -1;
        index = 0;
    }
 
    for (; index <= lastCycle; ++index) {
        TTAProgram::Instruction* newInstruction = rm.instruction(index);
        if (newInstruction->hasControlFlowMove()) {
            // Add delay slots of the last control flow instruction
            // to loop end count. There can be multiple control
            // flow instructions in a basic block in case thread yield
            // emitter is enabled and it has inserted one or more
            // calls to thread_yield().
 
            // only this this when not modulo-scheduling.
            if (rm.initiationInterval() < 1 || 
                rm.initiationInterval() == INT_MAX) {
                lastCycle = 
                    std::max(
                        lastCycle, 
                        index + targetMachine.controlUnit()->delaySlots());
//                assert(lastCycle >= rmLastCycle);
            }
        }
 
        moveCount += newInstruction->moveCount();
        bb.add(newInstruction);
#if 0
        Application::logStream() 
            << newInstruction->instructionTemplate().name() << ": "
            << newInstruction->toString() << std::endl;
#endif
        rm.loseInstructionOwnership(index);
    }
 
    if (irm.hasReference(refHolder)) {
        irm.replace(refHolder, bb.firstInstruction());
    }
 
    const int instructionCount = lastCycle + 1 - rm.smallestCycle();
    if (Application::verboseLevel() > 1 && bb.isInInnerLoop()) {
        const int busCount = targetMachine.busNavigator().count();
        const int moveSlotCount = busCount * instructionCount;
        Application::logStream() 
            << "BB -- inner loop with trip count: " << bb.tripCount() 
            << std::endl
            << "BB -- instruction count: " << instructionCount << std::endl;
        Application::logStream()
            << "BB -- move slots used: " << moveCount << " of " 
            << moveSlotCount << " (" << (float)moveCount * 100 / moveSlotCount
            << "%)" << std::endl;
    }
 
    return;
}

References TTAProgram::CodeSnippet::add(), assert, TTAMachine::Machine::busNavigator(), TTAProgram::BasicBlock::clear(), TTAMachine::Machine::controlUnit(), TTAMachine::Machine::Navigator< ComponentType >::count(), TTAMachine::ControlUnit::delaySlots(), TTAProgram::CodeSnippet::firstInstruction(), TTAProgram::Instruction::hasControlFlowMove(), TTAProgram::InstructionReferenceManager::hasReference(), SimpleResourceManager::initiationInterval(), SimpleResourceManager::instruction(), TTAProgram::CodeSnippet::instructionAtIndex(), TTAProgram::CodeSnippet::instructionCount(), TTAProgram::Instruction::instructionTemplate(), TTAProgram::BasicBlock::isInInnerLoop(), SimpleResourceManager::largestCycle(), Application::logStream(), SimpleResourceManager::loseInstructionOwnership(), TTAProgram::Instruction::moveCount(), TTAMachine::Component::name(), TTAProgram::InstructionReferenceManager::replace(), SimpleResourceManager::smallestCycle(), TTAProgram::Instruction::toString(), TTAProgram::BasicBlock::tripCount(), and Application::verboseLevel().

Referenced by LoopPrologAndEpilogBuilder::addPrologFromRM(), executeDDGPass(), BBSchedulerController::executeDDGPass(), and SequentialScheduler::handleBasicBlock().

Here is the call graph for this function:

createDDGFromBB()

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

protectedvirtual

Reimplemented in BBSchedulerController.

Definition at line 302 of file BasicBlockPass.cc.

                                                             {
    return ddgBuilder().build(
        bb, DataDependenceGraph::INTRA_BB_ANTIDEPS, mach, "unknown_bb");
}

References DataDependenceGraphBuilder::build(), ddgBuilder(), and DataDependenceGraph::INTRA_BB_ANTIDEPS.

Referenced by executeDDGPass().

Here is the call graph for this function:

ddgBuilder()

virtual DataDependenceGraphBuilder & BasicBlockPass::ddgBuilder ( )

inlinevirtual

Reimplemented in BasicBlockScheduler, and BUBasicBlockScheduler.

Definition at line 86 of file BasicBlockPass.hh.

{ return ddgBuilder_; }

References ddgBuilder_.

Referenced by createDDGFromBB(), BBSchedulerController::createDDGFromBB(), and BBSchedulerController::handleProcedure().

ddgSnapshot()

void BasicBlockPass::ddgSnapshot ( DataDependenceGraph *  ddg, std::string &  name, DataDependenceGraph::DumpFileFormat  format, bool  final  )

protected

Prints DDG to a dot file before and after scheudling

Parameters

ddg	to print
name	operation name for ddg
final	specify if ddg is after scheduling
format	format of the file

Returns

number of cycles/instructions copied.

Definition at line 172 of file BasicBlockPass.cc.

                {
    static int bbCounter = 0;
 
    if (final) {
    if (format == DataDependenceGraph::DUMP_DOT) {
        ddg->writeToDotFile(
        (boost::format("bb_%.4d_1_after_%2%.dot") % bbCounter % name).str());
    } else {
        ddg->writeToXMLFile(
        (boost::format("bb_%.4d_1_after_%2%.xml") % bbCounter % name).str());
    }
        ++bbCounter;
    } else {
    if (format == DataDependenceGraph::DUMP_DOT) {
        ddg->writeToDotFile(
        (boost::format("bb_%.4d_0_before_%2%.dot") % bbCounter % name).str());
    } else {
        ddg->writeToXMLFile(
        (boost::format("bb_%.4d_0_before_%2%.xml") % bbCounter % name).str());
    }
    Application::logStream() << "\nBB " << bbCounter << std::endl;
    }
}

References DataDependenceGraph::DUMP_DOT, Application::logStream(), GraphBase< GraphNode, GraphEdge >::writeToDotFile(), and DataDependenceGraph::writeToXMLFile().

Referenced by executeDDGPass(), and BBSchedulerController::executeDDGPass().

Here is the call graph for this function:

executeDDGPass()

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

virtual

Creates a DDG from the given basic block and executes a DDG pass for that.

Reimplemented in BBSchedulerController.

Definition at line 101 of file BasicBlockPass.cc.

                                                    {
    std::cerr << "Calling bbpass::executedgpass." << std::endl;
 
    DataDependenceGraph* ddg = createDDGFromBB(bb, targetMachine);
 
    // Used for live info dumping.
    static int bbNumber = 0;
 
#ifdef DDG_SNAPSHOTS
    std::string name = "scheduling";
    ddgSnapshot(ddg, name, false);
#endif
    
    SimpleResourceManager* rm = SimpleResourceManager::createRM(targetMachine);
    ddgPasses[0]->handleDDG(*ddg, *rm, targetMachine);
 
#ifdef DDG_SNAPSHOTS
    std::string name = "scheduling";
    ddgSnapshot(ddg, name, true);
#endif
 
    copyRMToBB(*rm, bb, targetMachine, irm);
 
    // Print the live range count for each cycle for the sched_yield emitting
    // paper.
    if (Application::verboseLevel() > 1 || 
        getenv("TCE_DUMP_LIVE_INFO") != NULL) {
        for (int index = 0; index < bb.instructionCount(); ++index) {
            if (bb.liveRangeData_ != NULL) {
                Application::logStream() 
                    << "liveinfo:" << bbNumber << ":" << index + rm->smallestCycle() << ":" 
                << bb.liveRangeData_->registersAlive(
                    rm->smallestCycle()+index, targetMachine.controlUnit()->delaySlots(), *ddg).
                size()
                << std::endl;
            }
        }
        bbNumber++;
    }
 
    delete ddg;
    SimpleResourceManager::disposeRM(rm);
}

References TTAMachine::Machine::controlUnit(), copyRMToBB(), createDDGFromBB(), SimpleResourceManager::createRM(), ddgSnapshot(), TTAMachine::ControlUnit::delaySlots(), SimpleResourceManager::disposeRM(), TTAProgram::CodeSnippet::instructionCount(), TTAProgram::BasicBlock::liveRangeData_, Application::logStream(), LiveRangeData::registersAlive(), SimpleResourceManager::smallestCycle(), and Application::verboseLevel().

Referenced by handleBasicBlock().

Here is the call graph for this function:

executeLoopPass()

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

virtual

Creates a DDG from the given basic block and executes a Loop pass for that.

Definition at line 152 of file BasicBlockPass.cc.

                     {
    // not implemented
    assert(0 && "should not be here?");
    return false;
}

References assert.

Referenced by BBSchedulerController::handleBasicBlock().

handleBasicBlock()

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

virtual

Handles a single basic block.

Modifies the given basic block, so if the old one is to be preserved, client should copy the original. Does not restore the BB even though handling was not successful.

Todo:

: Why both BB and BBN as arguments? If BBN is needed then I think BB argument can be replaced with a BBN one. We always should have it anyways.

Parameters

basicBlock	The basic block to handle.
machine	The target machine if any. (NullMachine::instance() if target machine is irrelevant).

Exceptions

In	case handling is unsuccesful for any reason (basicBlock might still get modified).

Reimplemented in PostpassOperandSharer, SequentialScheduler, and BBSchedulerController.

Definition at line 79 of file BasicBlockPass.cc.

                                                                     {
    if (basicBlock.instructionCount() == 0)
        return;
 
    DDGPass* ddgPass = dynamic_cast<DDGPass*>(this);
    std::vector<DDGPass*> ddgPasses;
    ddgPasses.push_back(ddgPass);
    if (ddgPass != NULL) {
        executeDDGPass(basicBlock, targetMachine, irm, ddgPasses, bbn);
    } else {
        abortWithError("basic block pass is not also a ddg pass so you "
                       "must overload handleBasicBlock method!");
    }
}

References abortWithError, executeDDGPass(), and TTAProgram::CodeSnippet::instructionCount().

Referenced by ControlFlowGraphPass::executeBasicBlockPass().

Here is the call graph for this function:

Member Data Documentation

ddgBuilder_

DataDependenceGraphBuilder BasicBlockPass::ddgBuilder_

private

Definition at line 100 of file BasicBlockPass.hh.

Referenced by ddgBuilder().

---

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

• BasicBlockPass.hh
• BasicBlockPass.cc