in vm/jitrino/src/optimizer/Loop.cpp [379:791]
void LoopBuilder::peelLoops(StlVector<Edge*>& loopEdgesIn) {
// Mark the temporaries that are local to a given basic block
GlobalOpndAnalyzer globalOpndAnalyzer(irManager);
globalOpndAnalyzer.doAnalysis();
// Set def-use chains
MemoryManager peelmem("LoopBuilder::peelLoops.peelmem");
OpndManager& opndManager = irManager.getOpndManager();
InstFactory& instFactory = irManager.getInstFactory();
// Threshold at which a block is considered hot
double heatThreshold = irManager.getHeatThreshold();
StlVector<Edge*> loopEdges(peelmem);
if(flags.insideout_peeling) {
StlVector<Edge*>::reverse_iterator i = loopEdgesIn.rbegin(); while (i != loopEdgesIn.rend()) {
loopEdges.insert(loopEdges.end(), *i);
i++;
}
} else {
StlVector<Edge*>::iterator i = loopEdgesIn.begin();
while (i != loopEdgesIn.end()) {
loopEdges.insert(loopEdges.end(), *i);
i++;
}
}
StlVector<Edge*>::iterator i;
for(i = loopEdges.begin(); i != loopEdges.end(); ++i) {
// The current back-edge
Edge* backEdge = *i;
// The initial header
Node* header = backEdge->getTargetNode();
if (header->isDispatchNode()) {
continue;
}
assert(header->getInDegree() == 2);
Node* originalInvertedHeader = header;
// The initial loop end
Node* tail = backEdge->getSourceNode();
// The initial preheader
Node* preheader = header->getInEdges().front()->getSourceNode();
if (preheader == tail)
preheader = header->getInEdges().back()->getSourceNode();
// Temporary memory for peeling
U_32 maxSize = fg.getMaxNodeId();
MemoryManager tmm("LoopBuilder::peelLoops.tmm");
// Compute nodes in loop
StlBitVector nodesInLoop(tmm, maxSize);
U_32 loopSize = LoopMarker<IdentifyByID>::markNodesOfLoop(nodesInLoop, header, tail);
// Operand renaming table for duplicated nodes
OpndRenameTable* duplicateTable = new (tmm) OpndRenameTable(tmm);
// Perform loop inversion until header has no exit condition or
// until one iteration is peeled.
Node* next;
Node* exit;
if (useProfile || !flags.old_static_peeling) {
//
// Only peel hot loops
//
if(useProfile) {
double preheaderFreq = preheader->getExecCount();
if(header->getExecCount() < heatThreshold || header->getExecCount() < preheaderFreq*flags.peeling_threshold || header->getExecCount() == 0)
continue;
}
//
// Rotate loop one more time if the tail is not a branch (off by default)
//
Opcode op1 = ((Inst*)tail->getLastInst())->getOpcode();
Opcode op2 = ((Inst*)header->getLastInst())->getOpcode();
if(flags.invert && (op1 != Op_Branch) && (op2 != Op_Branch)) {
if(isInversionCandidate(originalInvertedHeader, header, nodesInLoop, next, exit)) {
DefUseBuilder defUses(peelmem);
defUses.initialize(fg);
preheader = FlowGraph::tailDuplicate(irManager, preheader, header, defUses);
tail = header;
header = next;
assert(tail->findTargetEdge(header) != NULL && preheader->findTargetEdge(header) != NULL);
if(tail->findTargetEdge(header) == NULL) {
tail = tail->getUnconditionalEdge()->getTargetNode();
assert(tail != NULL && tail->findTargetEdge(header) != NULL);
}
originalInvertedHeader = header;
}
}
//
// Compute blocks to peel
//
Node* newHeader = header;
Node* newTail = NULL;
StlBitVector nodesToPeel(tmm, maxSize);
if(flags.fullpeel) {
if(loopSize <= flags.fullpeel_max_inst) {
nodesToPeel = nodesInLoop;
newTail = tail;
}
} else {
while(isInversionCandidate(originalInvertedHeader, newHeader, nodesInLoop, next, exit)) {
if(Log::isEnabled()) {
Log::out() << "Peel ";
FlowGraph::printLabel(Log::out(), newHeader);
Log::out() << std::endl;
}
newTail = newHeader;
nodesToPeel.setBit(newHeader->getId());
newHeader = next;
if(newHeader == originalInvertedHeader) {
Log::out() << "One iteration peeled" << std::endl;
break;
}
}
}
if(flags.peel) {
header = newHeader;
if(flags.peel_upto_branch) {
//
// Break final header at branch to peel more instructions
//
if(header != originalInvertedHeader) {
Inst* last = (Inst*)header->getLastInst();
if(header->getOutDegree() > 1)
last = last->getPrevInst();
if (flags.peel_upto_branch_no_instanceof) {
Inst *first = (Inst*)header->getFirstInst();
while ((first != last) && (first->getOpcode() != Op_TauInstanceOf)) {
first = first->getNextInst();
}
last = first;
}
Node* sinkNode = fg.splitNodeAtInstruction(last, true, false, instFactory.makeLabel());
newTail = header;
nodesToPeel.resize(sinkNode->getId()+1);
nodesToPeel.setBit(header->getId());
if(Log::isEnabled()) {
Log::out() << "Sink Node = ";
FlowGraph::printLabel(Log::out(), sinkNode);
Log::out() << ", Header = ";
FlowGraph::printLabel(Log::out(), header);
Log::out() << ", Original Header = ";
FlowGraph::printLabel(Log::out(), originalInvertedHeader);
Log::out() << std::endl;
}
header = sinkNode;
}
}
//
// Peel the nodes
//
if(newTail != NULL) {
DefUseBuilder defUses(peelmem);
defUses.initialize(fg);
Edge* entryEdge = preheader->findTargetEdge(originalInvertedHeader);
double peeledFreq = preheader->getExecCount() * entryEdge->getEdgeProb();
Node* peeled = FlowGraph::duplicateRegion(irManager, originalInvertedHeader, nodesToPeel, defUses, peeledFreq);
assert(peeled->getInDegree() <= 1);
// Break cycle and link to original loop.
if (peeled->getInDegree() == 1) {
fg.replaceEdgeTarget(peeled->getInEdges().front(), header);
}
// Link duplicated region.
fg.replaceEdgeTarget(entryEdge, peeled);
if(newTail->findTargetEdge(header) == NULL) {
//
// An intervening stVar block was added to promote a temp to a var
// in the duplicated block. The new tail should be the stVar block.
//
tail = newTail->getUnconditionalEdge()->getTargetNode();
assert(tail != NULL && tail->findTargetEdge(header) != NULL);
} else {
tail = newTail;
}
assert(header->getInDegree() == 2);
preheader = header->getInEdges().front()->getSourceNode();
if(preheader == tail)
preheader = header->getInEdges().back()->getSourceNode();
}
}
if(preheader->getOutDegree() > 1) {
Edge* edge = preheader->findTargetEdge(header);
assert(edge != NULL);
preheader = fg.spliceBlockOnEdge(edge, instFactory.makeLabel());
}
} else {
while(isInversionCandidate(header, header, nodesInLoop, next, exit)) {
if(Log::isEnabled()) {
Log::out() << "Consider peeling node at L"; FlowGraph::printLabel(Log::out(), header); Log::out() << std::endl;
}
assert(header->isBlockNode());
assert(header->getInDegree() == 2);
assert(header->findSourceEdge(preheader) != NULL);
assert(header->findSourceEdge(tail) != NULL);
// Find variant instructions. Invariant instructions need not be duplicated.
StlVector<Inst*> variantInsts(tmm);
StlHashSet<Opnd*> variantOpnds(tmm);
StlVector<Inst*> invariantInsts(tmm);
Inst* first = (Inst*)header->getFirstInst();
Inst* inst;
for(inst = first->getNextInst(); inst != NULL; inst = inst->getNextInst()) {
if (isVariantInst(inst, variantOpnds)) {
if (Log::isEnabled()) {
Log::out() << "Inst ";
inst->print(Log::out());
Log::out() << " is variant" << std::endl;
}
variantInsts.push_back(inst);
Opnd* dst = inst->getDst();
variantOpnds.insert(dst);
} else {
if (Log::isEnabled()) {
Log::out() << "Inst ";
inst->print(Log::out());
Log::out() << " is invariant" << std::endl;
}
invariantInsts.push_back(inst);
}
}
// Heuristic #0: If no invariant in header, don't peel.
if (invariantInsts.empty()) {
Log::out() << "Peeling heuristic #0, no invariant" << std::endl;
break;
}
// Heuristic #1: If the last instruction is a variant check, stop peeling.
Inst* last = (Inst*)header->getLastInst();
if (last->getOperation().isCheck() && !variantInsts.empty() && last == variantInsts.back() &&
!(last->getDst()->isNull()
|| (last->getDst()->getType()->tag == Type::Tau))) {
hoistHeaderInvariants(preheader, header, invariantInsts);
Log::out() << "Peeling heuristic #1, last inst is variant check" << std::endl;
break;
}
// Heuristic #2: If a defined tmp may be live on exit, don't peel this node.
// Promoting such tmps to vars is expensive, since we need to find all uses.
StlVector<Inst*> globalInsts(tmm);
Opnd* unhandledGlobal = NULL;
bool hasExit = exit != NULL;
bool exitIsUnwind = hasExit && (exit == fg.getUnwindNode());
bool exitIsNotDominated = !hasExit ||
(dom.hasDomInfo(header) && dom.hasDomInfo(exit) && !dom.dominates(header, exit));
StlVector<Inst*>::iterator iiter;
for(iiter = variantInsts.begin(); iiter != variantInsts.end(); ++iiter) {
Inst* inst = *iiter;
Opnd* dst = inst->getDst();
if (dst->isGlobal() && !dst->isVarOpnd() && !dst->isNull()) {
// Defined global temp.
if(exitIsNotDominated || exitIsUnwind || (inst == last && exit->isDispatchNode())) {
globalInsts.push_back(inst);
} else {
unhandledGlobal = dst;
break;
}
}
}
if (unhandledGlobal != NULL) {
if (Log::isEnabled()) {
Log::out() << "Stop peeling node at " ; FlowGraph::printLabel(Log::out(), header); Log::out() << ": unhandled global operand. ";
unhandledGlobal->print(Log::out());
Log::out() << std::endl;
}
hoistHeaderInvariants(preheader, header, invariantInsts);
break;
}
// Duplicate instructions
Node* peeled = fg.createBlockNode(instFactory.makeLabel());
if (Log::isEnabled()) {
Log::out() << "Peeling node "; FlowGraph::printLabel(Log::out(), header); Log::out() << " as "; FlowGraph::printLabel(Log::out(), peeled); Log::out() << std::endl;
}
Inst* nextInst;
// Peel instructions to peeled block. Leave clones of variant insts.
for(inst = first->getNextInst(), iiter = variantInsts.begin(); inst != NULL; inst = nextInst) {
nextInst = inst->getNextInst();
if (iiter != variantInsts.end() && inst == *iiter) {
// Make clone in place.
++iiter;
Inst* clone = instFactory.clone(inst, opndManager, duplicateTable);
clone->insertBefore(nextInst);
inst->unlink();
if (Log::isEnabled()) {
Log::out() << "Peeling: copying ";
inst->print(Log::out());
Log::out() << " to ";
clone->print(Log::out());
Log::out() << std::endl;
}
} else {
if(inst->getOperation().canThrow())
FlowGraph::eliminateCheck(fg, header, inst, false);
else
inst->unlink();
if (Log::isEnabled()) {
Log::out() << "Peeling: not copying ";
inst->print(Log::out());
Log::out() << std::endl;
}
}
peeled->appendInst(inst);
}
assert(iiter == variantInsts.end());
fg.replaceEdgeTarget(preheader->findTargetEdge(header), peeled);
if (hasExit) {
fg.addEdge(peeled, exit);
}
fg.addEdge(peeled, next);
if (!globalInsts.empty()) {
OpndRenameTable* patchTable = new (tmm) OpndRenameTable(tmm);
// Need to patch global defs. Create store blocks and merge at next
if (Log::isEnabled()) {
Log::out() << "Merging global temps in node ";FlowGraph::printLabel(Log::out(), header); Log::out()<<" and ";FlowGraph::printLabel(Log::out(), peeled);Log::out()<<std::endl;
}
Node* newpreheaderSt = fg.createBlockNode(instFactory.makeLabel());
Node* newtailSt = fg.createBlockNode(instFactory.makeLabel());
fg.replaceEdgeTarget(peeled->findTargetEdge(next), newpreheaderSt);
fg.addEdge(newpreheaderSt, next);
fg.replaceEdgeTarget(header->findTargetEdge(next), newtailSt);
fg.addEdge(newtailSt, next);
StlVector<Inst*>::iterator i;
for(i = globalInsts.begin(); i != globalInsts.end(); ++i) {
Inst* inst = *i;
Opnd* dst = inst->getDst();
Opnd* dstPreheader = opndManager.createSsaTmpOpnd(dst->getType());
Opnd* dstTail = duplicateTable->getMapping(dst);
inst->setDst(dstPreheader);
VarOpnd* dstVar;
if ((inst->getOpcode() == Op_LdVar) && (variantOpnds.find(inst->getSrc(0)) == variantOpnds.end())) {
// If dst is generated from a LdVar, reuse that var instead of promoting to a new var.
dstVar = inst->getSrc(0)->asVarOpnd();
assert(dstVar != NULL);
} else {
// Create a new var and initialize it the original and duplicated blocks.
dstVar = opndManager.createVarOpnd(dst->getType(), false);
Inst* stPreheader = instFactory.makeStVar(dstVar, dstPreheader);
newpreheaderSt->appendInst(stPreheader);
Inst* stTail = instFactory.makeStVar(dstVar, dstTail);
newtailSt->appendInst(stTail);
}
Inst* ldVar = instFactory.makeLdVar(dst, dstVar);
next->prependInst(ldVar);
patchTable->setMapping(dst, dstPreheader);
}
FlowGraph::renameOperandsInNode(peeled, patchTable);
// Rotate
preheader = newpreheaderSt;
tail = newtailSt;
} else {
if (peeled->getOutDegree() > 1) {
// Remove critical edge
preheader = fg.createBlockNode(instFactory.makeLabel());
fg.replaceEdgeTarget(peeled->findTargetEdge(next), preheader);
fg.addEdge(preheader, next);
} else {
preheader = peeled;
}
tail = header;
}
// Prepare to peel next node.
header = next;
if (flags.aggressive_peeling) {
if (header == originalInvertedHeader) {
if (Log::isEnabled()) {
Log::out()<<"Stop peeling node at ";FlowGraph::printLabel(Log::out(), header); Log::out() << ": peeled one iteration" << std::endl;
}
break;
}
} else {
break;
}
}
}
assert(header->getInDegree() == 2);
backEdge = header->findSourceEdge(tail);
assert(backEdge != NULL);
*i = backEdge;
}
loopEdgesIn.clear();
if(flags.insideout_peeling) {
StlVector<Edge*>::reverse_iterator i = loopEdges.rbegin();
while (i != loopEdges.rend()) {
loopEdgesIn.insert(loopEdgesIn.end(), *i);
i++;
}
} else {
StlVector<Edge*>::iterator i = loopEdges.begin();
while (i != loopEdges.end()) {
loopEdgesIn.insert(loopEdgesIn.end(), *i);
i++;
}
}
}