This section provides an example of a loop peeler that operates at the MIR level.
/*
Loop Peeler, for dismantled code
11/30/03 Walter Chang <walter@cs.utexas.edu>
This demonstrates loop peeling at the MIR level, using cfg, dominators,
loopTree, and related goodies.
Expects: Your stuff in CFG form. Unfortunately, you must pass it an entire
unit at a time, because that's what Dismantle::dismantle wants, and
we need to re-dismantle to fix up labels.
Gives: Dismantled code with loops peeled.
*/
#include <algorithm>
#include "c_breeze.h"
#include "looppeeldis.h"
#include "cfg.h"
LoopPeelingChangerDismantled::LoopPeelingChangerDismantled(void) :
Changer (Postorder, Subtree, false) {}
/*
at_proc(the_proc, ord)
Runs dominators and loopTree on the_proc, then walks the loop
tree for the_proc
*/
Node * LoopPeelingChangerDismantled::at_proc(procNode *the_proc, Order ord) {
myProc = the_proc;
/* let Dominators decorate things */
Dominators d(the_proc, true);
/* figure out the loop tree */
loopTree l(the_proc);
/* walk that tree */
loopTreeWalk(l.topLoop());
return the_proc;
}
/*
at_unit(the_unit, ord)
If we've finished everything for the unit (coming up in postorder),
re-dismantle the unit to fixup label names.
Changers should be postorder anyway.
*/
Node * LoopPeelingChangerDismantled::at_unit(unitNode *the_unit, Order ord) {
cfg_changer::generate_cfg(the_unit);
return the_unit;
}
/*
change(u)
Loop-peels the unit u.
*/
void LoopPeelingChangerDismantled::change(unitNode *the_unit) {
if(!the_unit) return;
LoopPeelingChangerDismantled lpcd;
the_unit->change(lpcd);
}
/*
change()
Loop-peels everything.
*/
void LoopPeelingChangerDismantled::change() {
unit_list_p u;
for (u=CBZ::Program.begin(); u != CBZ::Program.end(); u++) {
change( *u ); // change each unit
}
}
/*
loopTreeWalk(l)
Walks loop tree in postorder. Peel every natural (SingleEntry) loop.
*/
void LoopPeelingChangerDismantled::loopTreeWalk(loopTreeNode * l) {
loop_set children = l->nestedLoops();
loop_set::iterator child;
/* walk the nested loops */
for(child = children.begin(); child != children.end(); child++) {
loopTreeWalk( (*child) );
}
/* peel this loop, if it is single-entry */
if(l->kind() == loopTreeNode::SingleEntry) {
peel(l);
}
return;
}
/*
peel(loopTreeNode * l)
Peels the single-entry loop indicated by l.
This should leave the original entry blocks to the loop going to the new
copy, and all backedges in the loop copy going to the loop top pointing to
the old loop top. The body of the loop is not otherwise tinkered with.
*/
void LoopPeelingChangerDismantled::peel(loopTreeNode * l) {
/* make list of all basic blocks in l's blockset */
/*
NOTE:
We implicitly assume that when we iterate over the block list in a loop,
that the FIRST block is the loop header. This assumption is empirically
true as of 11/30/03. Should this no longer hold, we must find and move
the header to the front BEFORE ref-cloning the thing.
*/
stmt_list loopBlocks = bbset2list(all_blocks(l));
/* put all basic blocks into one blockNode */
blockNode loopBodyBlock(NULL,
&loopBlocks,
Coord::Unknown,
Coord::Unknown);
/*
ref-clone the block with all the basic blocks in the loop.
ref-clone should not change the order of the basic blocks.
*/
blockNode * loopBodyCopy =
(blockNode *) (ref_clone_changer::clone(&loopBodyBlock, false));
stmt_list::iterator lp;
basicblock_list::iterator lpp;
stmt_list loop_preds;
/*
Look for the entries into the loop, ie, predecessors of
the header that are not themselves part of the loop
*/
basicblockNode * loop_header = l->header();
basicblockNode * loop_newheader =
(basicblockNode *) loopBodyCopy->stmts().front();
for(lpp = loop_header->preds().begin();
lpp != loop_header->preds().end();
lpp++) {
/* If this pred is NOT in the loop's blockset */
if( find(l->blocks().begin(), l->blocks().end(),
(*lpp) )
== l->blocks().end()) {
/* add this pred to the list of loop entries */
loop_preds.push_front( (*lpp) );
}
}
string lnhName = ((labelNode *) loop_newheader->stmts().front())->name();
/*
A basic block always ends in a goto. It is possible for the next-
to-last to be a conditionGoto (but not a goto). These are the only
possible jump statements you will find in a basic block.
*/
/* For every (external) entry point to this loop... */
for(lp = loop_preds.begin(); lp != loop_preds.end(); lp++) {
/* get the last statement in the block*/
stmt_list::iterator lastStmtIter =
((basicblockNode *) (*lp))->stmts().end(); lastStmtIter--;
/* If it comes in via the fall-through... */
if( ((gotoNode *) (*lastStmtIter))->label()->name() == lnhName) {
/* ...join that block to the NEW header */
bbjoin( (basicblockNode *) (*lp), loop_newheader);
}
/* if there is a next-to-last... */
if(lastStmtIter != ((basicblockNode *) (*lp))->stmts().begin()) {
lastStmtIter--;
/* ... and it is a conditionGoto... */
if( (*lastStmtIter)->typ() == Condition ) {
/* ... and it enters the loop... */
if( ((conditiongotoNode *) (*lastStmtIter))->label()->name() ==
lnhName) {
/* ...join that conditionGoto to the NEW header*/
bbjoincond( (basicblockNode *) (*lp), loop_newheader);
}
}
}
}
/*
Now we go through all the blocks in the loop, and for any block that goes
to the top of the loop, make sure it goes to the OLD top of the loop, and
not the top of the cloned body. Ordinarily there should be just one such
block. [I'm not sure about continue...]
*/
/* The first thing in a basic block is ALWAYS a label */
labelNode * loopTop = (labelNode *) loop_header->stmts().front();
/* for all blocks b that head to the loop top */
for(lp = loopBodyCopy->stmts().begin();
lp != loopBodyCopy->stmts().end();
lp++) {
/* The last statement in a basic block is ALWAYS a goto */
gotoNode * endingGoto = (gotoNode *)
((basicblockNode *) (*lp))->stmts().back();
/* If we're going to some loop top... */
if(endingGoto->label()->name() == loopTop->name()) {
/* ... make sure it goes to the OLD loop top */
bbjoin( (basicblockNode *) (*lp), loop_header);
}
/* Now we fix up any conditional jumps to the top */
stmt_list::iterator lastStmtIter =
((basicblockNode *) (*lp))->stmts().end(); lastStmtIter--;
/* if there is a next-to-last... */
if(lastStmtIter != ((basicblockNode *) (*lp))->stmts().begin()) {
lastStmtIter--;
/* ... and it is a conditionGoto... */
if( (*lastStmtIter)->typ() == Condition ) {
/* ... and it goes to some loop top... */
if( ((conditiongotoNode *) (*lastStmtIter))->label()->name() ==
loopTop->name()) {
/* ...join that conditionGoto to the OLD loop top */
bbjoincond( (basicblockNode *) (*lp), loop_header);
}
}
}
}
/*
At this point, all the labels and gotos for the blocks should be pointing
at the correct places, and all that remains is to put the blocks into the
procedure proper.
*/
/* We'll try to add the new blocks immediately before the original */
stmt_list::iterator orig_start = find(myProc->body()->stmts().begin(),
myProc->body()->stmts().end(),
l->header());
for(lp = loopBodyCopy->stmts().begin();
lp != loopBodyCopy->stmts().end();
lp++) {
/* Add block to main body */
myProc->body()->stmts().insert(orig_start, (*lp) );
/* Add to our parent loop's blockset as well
Note that we'll never peel the root "loop" which has no parent */
l->parentLoop()->addBlock( (basicblockNode *) (*lp) );
}
}
/*
bbjoin(b1, b2)
Joins basic blocks b1 and b2, that is, b1's ending goto points to b2's
starting label. Use bbjoincond if you want the conditional to be changed.
Note that bbjoin does NOT make sure that preds and succs are kept sane.
This shouldn't be a problem in practice because we'll only be joining "on
the inside" and re-dismantling will fix it anyway.
*/
void LoopPeelingChangerDismantled::bbjoin(basicblockNode * b1,
basicblockNode * b2) {
gotoNode * endingGoto = (gotoNode *) b1->stmts().back();
labelNode * startLabel = (labelNode *) b2->stmts().front();
/* remove old label's reference */
endingGoto->label()->references().remove(endingGoto);
/* hook up to new label */
endingGoto->label(startLabel);
}
/*
bbjoincond(b1, b2)
Joins basic blocks b1 and b2 via b1's conditionGoto. The conditionGoto in
b1 will go to b2, and the fall-through remains unchanged. Use bbjoin if
you want to join via the fall-through.
Note that bbjoincond does NOT make sure that preds and succs are kept
sane. This shouldn't be a problem in practice because we'll only be
joining "on the inside" and re-dismantling will fix it anyway.
*/
void LoopPeelingChangerDismantled::bbjoincond(basicblockNode * b1,
basicblockNode * b2) {
labelNode * startLabel = (labelNode *) b2->stmts().front();
/* Find the next-to-last node, if it is there... */
stmt_list::iterator i = (b1->stmts()).end(); i--;
if (i != (b1->stmts()).begin()) {
i--;
stmtNode * nextToLast = (*i);
/* if it is a conditionGoto, fix the target to go to b2. */
if (nextToLast->typ() == Condition) {
((conditiongotoNode *) nextToLast)->
label()->references().remove((conditiongotoNode *) nextToLast);
((conditiongotoNode *) nextToLast)->label(startLabel);
}
}
}
/*
bbset2list(bbset)
Converts a basicblock_set to a basicblock_list
*/
stmt_list LoopPeelingChangerDismantled::bbset2list(basicblock_set &
bbset) {
stmt_list bbl;
basicblock_set::iterator bbsi;
for(bbsi = bbset.begin(); bbsi != bbset.end(); bbsi++) {
bbl.push_back( (*bbsi));
}
return stmt_list(bbl);
}
/*
all_blocks(l)
Returns all the blocks the loop l includes, including nested
loops. Changes loopTreeNodes so that blocks include nested loops.
*/
basicblock_set & LoopPeelingChangerDismantled::all_blocks(loopTreeNode * l) {
loop_set children = l->nestedLoops();
loop_set::iterator i;
basicblock_set::iterator j;
basicblock_set & b = l->blocks();
basicblock_set tmp;
for(i = children.begin(); i != children.end(); i++) {
tmp = all_blocks( (*i) );
for(j = tmp.begin(); j != tmp.end(); j++) {
b.insert( (*j) );
}
}
return b;
}