Peel2BBLoops Class Reference

#include <Peel2BBLoops.hh>

Inheritance diagram for Peel2BBLoops:

Collaboration diagram for Peel2BBLoops:

Classes
struct	BBNodes

Public Member Functions
	Peel2BBLoops (InterPassData &data, const TTAMachine::Machine &targetMachine)
void	handleControlFlowGraph (ControlFlowGraph &cfg, const TTAMachine::Machine &targetMachine) override
virtual std::string	shortDescription () const override
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 SchedulerPass
	SchedulerPass (InterPassData &data)
virtual	~SchedulerPass ()
InterPassData &	interPassData ()
virtual std::string	longDescription () const

Private Member Functions
bool	negateOp (ProgramOperationPtr po)
BBNodes	testIf2BBLoop (ControlFlowGraph &cfg, BasicBlockNode &bbn)
void	peel2BBLoop (ControlFlowGraph &cfg, BBNodes &bbns)
void	updateCFG (ControlFlowGraph &cfg, BBNodes &bbns)
void	performCodeMotion (BBNodes &bbns)
void	appendBB (const TTAProgram::BasicBlock &src, TTAProgram::BasicBlock &dest, BasicBlockNode *newJumpDest)

Private Attributes
TTAProgram::CodeGenerator *	codeGenerator_
TTAProgram::InstructionReferenceManager *	irm_
const TTAMachine::Machine &	mach_

Detailed Description

Definition at line 22 of file Peel2BBLoops.hh.

Constructor & Destructor Documentation

Peel2BBLoops()

Peel2BBLoops::Peel2BBLoops	(	InterPassData &	data,
		const TTAMachine::Machine &	targetMachine
	)

Definition at line 31 of file Peel2BBLoops.cc.

                                                                 :
    ControlFlowGraphPass(data),
    codeGenerator_(new TTAProgram::CodeGenerator(targetMachine)),
    irm_(NULL), mach_(targetMachine) {}

Member Function Documentation

appendBB()

void Peel2BBLoops::appendBB ( const TTAProgram::BasicBlock &  src, TTAProgram::BasicBlock &  dest, BasicBlockNode *  newJumpDest  )

private

Definition at line 172 of file Peel2BBLoops.cc.

                                                                                              {
 
    std::map<ProgramOperationPtr,ProgramOperationPtr> poMapping;
 
    ProgramOperationPtr prevPO = nullptr;
    for (int j = 0; j < src.instructionCount(); j++) {
        const TTAProgram::Instruction& ins = src.instructionAtIndex(j);
        TTAProgram::Instruction* newIns = new TTAProgram::Instruction();
        dest.add(newIns);
        for (int i = 0; i < ins.moveCount(); i++) {
            const TTAProgram::Move& move = ins.move(i);
            auto moveCopy = move.copy();
            MoveNode* newMN = nullptr;
 
            if (moveCopy->source().isFUPort()) {
                ProgramOperationPtr newPO =
                    SimpleIfConverter::fixTerminalPO(
                        static_cast<TTAProgram::TerminalFUPort&>(
                                moveCopy->source()),
                        poMapping);
                if (newPO != NULL) {
                    prevPO = newPO;
                    newMN = new MoveNode(moveCopy);
                    newPO->addOutputNode(*newMN);
                    newMN->setSourceOperationPtr(newPO);
                }
            }
            if (moveCopy->destination().isFUPort()) {
                ProgramOperationPtr newPO = SimpleIfConverter::fixTerminalPO(
                        static_cast<TTAProgram::TerminalFUPort&>(
                            moveCopy->destination()),
                        poMapping);
                if (newPO != NULL) {
                    prevPO = newPO;
                    if (newMN == nullptr)
                        newMN = new MoveNode(moveCopy);
                    newPO->addInputNode(*newMN);
                    newMN->addDestinationOperationPtr(newPO);
                }
            }
 
            // for jumps, need to update target and inverse guard.
            if (moveCopy->isJump() && newJumpDest != nullptr) {
                if (!moveCopy->isUnconditional()) {
 
                    // if fake guard, first try to inverse the op that
                    // generated it, but if it fails negate the guard.
                    if (!(moveCopy->guard().guard().parentBus() == nullptr
                          && negateOp(prevPO))) {
 
                        moveCopy->setGuard(
                            codeGenerator_->createInverseGuard(
                                moveCopy->guard()));
                    }
 
                } else { // bz / bnz
                    // TODO: put these into a map?
                    std::map<std::string, std::string> branchNegations =
                        {{"BZ", "BNZ"}, {"BNZ", "BZ"},
                         {"BZ1", "BNZ1"}, {"BNZ1", "BZ1"},
                         {"BEQ", "BNE"}, {"BNE", "BEQ"},
                         {"BGT", "BLE"}, {"BLE", "BGT"},
                         {"BGTU", "BLEU"}, {"BLEU", "BGTU"},
                         {"BLT", "BGE"}, {"BGE", "BLT"},
                         {"BLTU", "BGEU"}, {"BGEU", "BLTU"}
                        };
                    auto *dest = dynamic_cast<TTAProgram::TerminalFUPort*>(
                        &moveCopy->destination());
                    assert(dest);
                    TCEString jumpName = dest->hintOperation().name();
                    if (branchNegations.count(jumpName) > 0) {
                        OperationPool pool;
                        std::string negatedOpName = branchNegations[jumpName];
                        const Operation& negatedOp =
                            pool.operation(negatedOpName.c_str());
                        newMN->destinationOperation().setOperation(negatedOp);
                    } else {
                        assert (false &&
                                "Cannot neg unknown conditional jump instr");
                    }
                }
                moveCopy->setSource(
                    new TTAProgram::TerminalBasicBlockReference(
                        newJumpDest->basicBlock()));
            }
            newIns->addMove(moveCopy);
        }
    }
}

References TTAProgram::CodeSnippet::add(), MoveNode::addDestinationOperationPtr(), TTAProgram::Instruction::addMove(), assert, BasicBlockNode::basicBlock(), codeGenerator_, TTAProgram::Move::copy(), TTAProgram::CodeGenerator::createInverseGuard(), MoveNode::destinationOperation(), SimpleIfConverter::fixTerminalPO(), TTAProgram::CodeSnippet::instructionAtIndex(), TTAProgram::CodeSnippet::instructionCount(), TTAProgram::Instruction::move(), TTAProgram::Instruction::moveCount(), negateOp(), OperationPool::operation(), ProgramOperation::setOperation(), and MoveNode::setSourceOperationPtr().

Referenced by performCodeMotion().

Here is the call graph for this function:

handleControlFlowGraph()

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

overridevirtual

Handles a cfg.

Parameters

cfg	cfg to be optimized.

Reimplemented from ControlFlowGraphPass.

Definition at line 101 of file Peel2BBLoops.cc.

                                                                   {
    if (codeGenerator_ == NULL) {
        codeGenerator_ = new TTAProgram::CodeGenerator(targetMachine);
    }
 
    irm_ = &cfg.instructionReferenceManager();
 
    for (int i = 0; i < cfg.nodeCount(); i++) {
 
        // first find the block containing the main body(end) of the loop
        BasicBlockNode& bbn = cfg.node(i);
 
        if (auto loopBlocks = testIf2BBLoop(cfg, bbn)) {
            peel2BBLoop(cfg, loopBlocks);
 
            // performing this may change other basic blocks so lets start
            // from beginning(may it?)
            i = 0;
        }
    }
}

References codeGenerator_, ControlFlowGraph::instructionReferenceManager(), irm_, BoostGraph< GraphNode, GraphEdge >::node(), BoostGraph< GraphNode, GraphEdge >::nodeCount(), peel2BBLoop(), and testIf2BBLoop().

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

Here is the call graph for this function:

negateOp()

bool Peel2BBLoops::negateOp ( ProgramOperationPtr  po )

private

Negates operation into operation which generates opposite predicate value.

Definition at line 267 of file Peel2BBLoops.cc.

                                                  {
 
    // TODO: Shouldn't these be CAPSed? does this really work?
    std::map<TCEString, TCEString> negateOps;
    negateOps["eq"] = "ne";
    negateOps["ne"] = "eq";
    negateOps["le"] = "gt";
    negateOps["gt"] = "le";
    negateOps["lt"] = "ge";
    negateOps["ge"] = "lt";
    negateOps["leu"] = "gtu";
    negateOps["gtu"] = "leu";
    negateOps["ltu"] = "geu";
    negateOps["geu"] = "ltu";
 
    const Operation& op = po->operation();
    std::cerr << "negating op: " << op.name() << std::endl;
    auto i = negateOps.find(op.name());
    if (i == negateOps.end()) {
        std::cerr << "negated op for: " << op.name() << " not found!" << std::endl;
        return false;
    }
    std::cerr << "negated opname: " << i->second << std::endl;
 
    if (!MachineInfo::supportsOperation(mach_, i->second)) {
        return false;
    }
    OperationPool pool;
    const Operation& negatedOp = pool.operation(i->second.c_str());
    po->setOperation(negatedOp);
    return true;
}

References mach_, Operation::name(), OperationPool::operation(), and MachineInfo::supportsOperation().

Referenced by appendBB().

Here is the call graph for this function:

peel2BBLoop()

void Peel2BBLoops::peel2BBLoop ( ControlFlowGraph &  cfg, BBNodes &  bbns  )

private

Definition at line 124 of file Peel2BBLoops.cc.

                                                                   {
    performCodeMotion(bbns);
    updateCFG(cfg, bbns);
}

References performCodeMotion(), and updateCFG().

Referenced by handleControlFlowGraph().

Here is the call graph for this function:

performCodeMotion()

void Peel2BBLoops::performCodeMotion ( BBNodes &  bbns )

private

Definition at line 156 of file Peel2BBLoops.cc.

                                                  {
    // the nasty jump to middle of bb, removed because copying the code
    assert(SimpleIfConverter::removeJump(bbns.preLoop->basicBlock()));
 
    // then append the end of the loop into the pre-loop BB,
    // and inverse the guard and update the jump destination the post-loop
    appendBB(bbns.endLoop->basicBlock(),
             bbns.preLoop->basicBlock(),
             bbns.postLoop);
 
    // append end of loop to begin of the loop. no need to update jump.
    appendBB(bbns.endLoop->basicBlock(),
             bbns.beginLoop->basicBlock(),
             nullptr);
}

References appendBB(), assert, BasicBlockNode::basicBlock(), Peel2BBLoops::BBNodes::beginLoop, Peel2BBLoops::BBNodes::endLoop, Peel2BBLoops::BBNodes::postLoop, Peel2BBLoops::BBNodes::preLoop, and SimpleIfConverter::removeJump().

Referenced by peel2BBLoop().

Here is the call graph for this function:

shortDescription()

virtual std::string Peel2BBLoops::shortDescription ( ) const

inlineoverridevirtual

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 32 of file Peel2BBLoops.hh.

                                                        {
        return "optimizes two-BB inner loops into single-bb inner loops";
    }

testIf2BBLoop()

Peel2BBLoops::BBNodes Peel2BBLoops::testIf2BBLoop ( ControlFlowGraph &  cfg, BasicBlockNode &  bbn  )

private

Definition at line 37 of file Peel2BBLoops.cc.

                                                                                          {
 
    // entry/exit node or wrong number of succs/preds
    if (!bbn.isNormalBB() || cfg.outDegree(bbn) != 2 ||
        cfg.inDegree(bbn) != 2) {
        return false;
    }
 
    // find possible loop begin node and pre-loop node.
    auto iEdges = cfg.inEdges(bbn);
    BasicBlockNode *loopBegin = NULL;
    BasicBlockNode* preLoop = NULL;
    for (auto e: iEdges) {
        if (e->isFallThroughEdge()) {
            loopBegin = &cfg.tailNode(*e);
        } else {
            preLoop = &cfg.tailNode(*e);
        }
    }
    if (loopBegin == NULL || preLoop == NULL) {
        return false;
    }
 
    auto oEdges = cfg.outEdges(bbn);
    BasicBlockNode *afterLoop = NULL;
    for (auto e: oEdges) {
        if (e->isFallThroughEdge()) {
            afterLoop = &cfg.headNode(*e);
        } else { // jump to loop begin
            if (&cfg.headNode(*e) != loopBegin) {
                return false;
            }
        }
    }
 
    if (afterLoop == NULL) {
        return false;
    }
 
    if (cfg.inDegree(*loopBegin) != 1 || cfg.outDegree(*loopBegin) != 1) {
        return false;
    }
 
    if (!cfg.outEdge(*loopBegin, 0).isFallThroughEdge() ||
        cfg.inEdge(*loopBegin, 0).isFallThroughEdge()) {
        return false;
    }
 
    // incoming must not be fall-through.
    if (cfg.outDegree(*preLoop) != 1) {
        return false;
    }
 
    return BBNodes(preLoop, loopBegin, &bbn, afterLoop);
}

References BoostGraph< GraphNode, GraphEdge >::headNode(), BoostGraph< GraphNode, GraphEdge >::inDegree(), BoostGraph< GraphNode, GraphEdge >::inEdge(), BoostGraph< GraphNode, GraphEdge >::inEdges(), ControlFlowEdge::isFallThroughEdge(), BasicBlockNode::isNormalBB(), BoostGraph< GraphNode, GraphEdge >::outDegree(), BoostGraph< GraphNode, GraphEdge >::outEdge(), BoostGraph< GraphNode, GraphEdge >::outEdges(), and BoostGraph< GraphNode, GraphEdge >::tailNode().

Referenced by handleControlFlowGraph().

Here is the call graph for this function:

updateCFG()

void Peel2BBLoops::updateCFG ( ControlFlowGraph &  cfg, BBNodes &  bbns  )

private

Definition at line 130 of file Peel2BBLoops.cc.

                                                                 {
    // pre to loop-end needs to be converted from jump to fall-through,
    // with correct predicate(which is got from the loop node, reversing it
    cfg.disconnectNodes(*bbns.preLoop, *bbns.endLoop);
    auto exitEdge = *cfg.connectingEdges(*bbns.endLoop, *bbns.postLoop).begin();
    auto loopEdge = *cfg.connectingEdges(*bbns.endLoop, *bbns.beginLoop).begin();
 
    ControlFlowEdge* intoLoop = new ControlFlowEdge(
        loopEdge->edgePredicate(),
        ControlFlowEdge::CFLOW_EDGE_FALLTHROUGH);
 
    ControlFlowEdge* overLoop = new ControlFlowEdge(
        exitEdge->edgePredicate(),
        ControlFlowEdge::CFLOW_EDGE_JUMP);
 
    cfg.moveOutEdge(*bbns.endLoop, *bbns.beginLoop,  *loopEdge);
    loopEdge->setBackEdge();
    cfg.moveOutEdge(*bbns.endLoop, *bbns.beginLoop,  *exitEdge);
    cfg.connectNodes(*bbns.preLoop, *bbns.beginLoop, *intoLoop);
    cfg.connectNodes(*bbns.preLoop, *bbns.postLoop, *overLoop);
 
    // old loop end bb
    cfg.deleteNodeAndRefs(*bbns.endLoop);
}

References Peel2BBLoops::BBNodes::beginLoop, ControlFlowEdge::CFLOW_EDGE_FALLTHROUGH, ControlFlowEdge::CFLOW_EDGE_JUMP, BoostGraph< GraphNode, GraphEdge >::connectingEdges(), BoostGraph< GraphNode, GraphEdge >::connectNodes(), ControlFlowGraph::deleteNodeAndRefs(), BoostGraph< GraphNode, GraphEdge >::disconnectNodes(), Peel2BBLoops::BBNodes::endLoop, BoostGraph< GraphNode, GraphEdge >::moveOutEdge(), Peel2BBLoops::BBNodes::postLoop, and Peel2BBLoops::BBNodes::preLoop.

Referenced by peel2BBLoop().

Here is the call graph for this function:

Member Data Documentation

codeGenerator_

TTAProgram::CodeGenerator* Peel2BBLoops::codeGenerator_

private

Definition at line 62 of file Peel2BBLoops.hh.

Referenced by appendBB(), and handleControlFlowGraph().

irm_

TTAProgram::InstructionReferenceManager* Peel2BBLoops::irm_

private

Definition at line 63 of file Peel2BBLoops.hh.

Referenced by handleControlFlowGraph().

mach_

const TTAMachine::Machine& Peel2BBLoops::mach_

private

Definition at line 64 of file Peel2BBLoops.hh.

Referenced by negateOp().

---

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

• Peel2BBLoops.hh
• Peel2BBLoops.cc