0,0 → 1,550 |
/* |
* Copyright 2011 Christoph Bumiller |
* |
* Permission is hereby granted, free of charge, to any person obtaining a |
* copy of this software and associated documentation files (the "Software"), |
* to deal in the Software without restriction, including without limitation |
* the rights to use, copy, modify, merge, publish, distribute, sublicense, |
* and/or sell copies of the Software, and to permit persons to whom the |
* Software is furnished to do so, subject to the following conditions: |
* |
* The above copyright notice and this permission notice shall be included in |
* all copies or substantial portions of the Software. |
* |
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR |
* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, |
* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL |
* THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR |
* OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, |
* ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR |
* OTHER DEALINGS IN THE SOFTWARE. |
*/ |
|
#include "codegen/nv50_ir.h" |
|
namespace nv50_ir { |
|
Function::Function(Program *p, const char *fnName, uint32_t label) |
: call(this), |
label(label), |
name(fnName), |
prog(p) |
{ |
cfgExit = NULL; |
domTree = NULL; |
|
bbArray = NULL; |
bbCount = 0; |
loopNestingBound = 0; |
regClobberMax = 0; |
|
binPos = 0; |
binSize = 0; |
|
stackPtr = NULL; |
tlsBase = 0; |
tlsSize = 0; |
|
prog->add(this, id); |
} |
|
Function::~Function() |
{ |
prog->del(this, id); |
|
if (domTree) |
delete domTree; |
if (bbArray) |
delete[] bbArray; |
|
// clear value refs and defs |
ins.clear(); |
outs.clear(); |
|
for (ArrayList::Iterator it = allInsns.iterator(); !it.end(); it.next()) |
delete_Instruction(prog, reinterpret_cast<Instruction *>(it.get())); |
|
for (ArrayList::Iterator it = allLValues.iterator(); !it.end(); it.next()) |
delete_Value(prog, reinterpret_cast<LValue *>(it.get())); |
|
for (ArrayList::Iterator BBs = allBBlocks.iterator(); !BBs.end(); BBs.next()) |
delete reinterpret_cast<BasicBlock *>(BBs.get()); |
} |
|
BasicBlock::BasicBlock(Function *fn) : cfg(this), dom(this), func(fn) |
{ |
program = func->getProgram(); |
|
joinAt = phi = entry = exit = NULL; |
|
numInsns = 0; |
binPos = 0; |
binSize = 0; |
|
explicitCont = false; |
|
func->add(this, this->id); |
} |
|
BasicBlock::~BasicBlock() |
{ |
// nothing yet |
} |
|
BasicBlock * |
BasicBlock::clone(ClonePolicy<Function>& pol) const |
{ |
BasicBlock *bb = new BasicBlock(pol.context()); |
|
pol.set(this, bb); |
|
for (Instruction *i = getFirst(); i; i = i->next) |
bb->insertTail(i->clone(pol)); |
|
pol.context()->cfg.insert(&bb->cfg); |
|
for (Graph::EdgeIterator it = cfg.outgoing(); !it.end(); it.next()) { |
BasicBlock *obb = BasicBlock::get(it.getNode()); |
bb->cfg.attach(&pol.get(obb)->cfg, it.getType()); |
} |
|
return bb; |
} |
|
BasicBlock * |
BasicBlock::idom() const |
{ |
Graph::Node *dn = dom.parent(); |
return dn ? BasicBlock::get(dn) : NULL; |
} |
|
void |
BasicBlock::insertHead(Instruction *inst) |
{ |
assert(inst->next == 0 && inst->prev == 0); |
|
if (inst->op == OP_PHI) { |
if (phi) { |
insertBefore(phi, inst); |
} else { |
if (entry) { |
insertBefore(entry, inst); |
} else { |
assert(!exit); |
phi = exit = inst; |
inst->bb = this; |
++numInsns; |
} |
} |
} else { |
if (entry) { |
insertBefore(entry, inst); |
} else { |
if (phi) { |
insertAfter(exit, inst); // after last phi |
} else { |
assert(!exit); |
entry = exit = inst; |
inst->bb = this; |
++numInsns; |
} |
} |
} |
} |
|
void |
BasicBlock::insertTail(Instruction *inst) |
{ |
assert(inst->next == 0 && inst->prev == 0); |
|
if (inst->op == OP_PHI) { |
if (entry) { |
insertBefore(entry, inst); |
} else |
if (exit) { |
assert(phi); |
insertAfter(exit, inst); |
} else { |
assert(!phi); |
phi = exit = inst; |
inst->bb = this; |
++numInsns; |
} |
} else { |
if (exit) { |
insertAfter(exit, inst); |
} else { |
assert(!phi); |
entry = exit = inst; |
inst->bb = this; |
++numInsns; |
} |
} |
} |
|
void |
BasicBlock::insertBefore(Instruction *q, Instruction *p) |
{ |
assert(p && q); |
|
assert(p->next == 0 && p->prev == 0); |
|
if (q == entry) { |
if (p->op == OP_PHI) { |
if (!phi) |
phi = p; |
} else { |
entry = p; |
} |
} else |
if (q == phi) { |
assert(p->op == OP_PHI); |
phi = p; |
} |
|
p->next = q; |
p->prev = q->prev; |
if (p->prev) |
p->prev->next = p; |
q->prev = p; |
|
p->bb = this; |
++numInsns; |
} |
|
void |
BasicBlock::insertAfter(Instruction *p, Instruction *q) |
{ |
assert(p && q); |
assert(q->op != OP_PHI || p->op == OP_PHI); |
|
assert(q->next == 0 && q->prev == 0); |
|
if (p == exit) |
exit = q; |
if (p->op == OP_PHI && q->op != OP_PHI) |
entry = q; |
|
q->prev = p; |
q->next = p->next; |
if (q->next) |
q->next->prev = q; |
p->next = q; |
|
q->bb = this; |
++numInsns; |
} |
|
void |
BasicBlock::remove(Instruction *insn) |
{ |
assert(insn->bb == this); |
|
if (insn->prev) |
insn->prev->next = insn->next; |
|
if (insn->next) |
insn->next->prev = insn->prev; |
else |
exit = insn->prev; |
|
if (insn == entry) { |
if (insn->next) |
entry = insn->next; |
else |
if (insn->prev && insn->prev->op != OP_PHI) |
entry = insn->prev; |
else |
entry = NULL; |
} |
|
if (insn == phi) |
phi = (insn->next && insn->next->op == OP_PHI) ? insn->next : 0; |
|
--numInsns; |
insn->bb = NULL; |
insn->next = |
insn->prev = NULL; |
} |
|
void BasicBlock::permuteAdjacent(Instruction *a, Instruction *b) |
{ |
assert(a->bb == b->bb); |
|
if (a->next != b) { |
Instruction *i = a; |
a = b; |
b = i; |
} |
assert(a->next == b); |
assert(a->op != OP_PHI && b->op != OP_PHI); |
|
if (b == exit) |
exit = a; |
if (a == entry) |
entry = b; |
|
b->prev = a->prev; |
a->next = b->next; |
b->next = a; |
a->prev = b; |
|
if (b->prev) |
b->prev->next = b; |
if (a->prev) |
a->next->prev = a; |
} |
|
void |
BasicBlock::splitCommon(Instruction *insn, BasicBlock *bb, bool attach) |
{ |
bb->entry = insn; |
|
if (insn) { |
exit = insn->prev; |
insn->prev = NULL; |
} |
|
if (exit) |
exit->next = NULL; |
else |
entry = NULL; |
|
while (!cfg.outgoing(true).end()) { |
Graph::Edge *e = cfg.outgoing(true).getEdge(); |
bb->cfg.attach(e->getTarget(), e->getType()); |
this->cfg.detach(e->getTarget()); |
} |
|
for (; insn; insn = insn->next) { |
this->numInsns--; |
bb->numInsns++; |
insn->bb = bb; |
bb->exit = insn; |
} |
if (attach) |
this->cfg.attach(&bb->cfg, Graph::Edge::TREE); |
} |
|
BasicBlock * |
BasicBlock::splitBefore(Instruction *insn, bool attach) |
{ |
BasicBlock *bb = new BasicBlock(func); |
assert(!insn || insn->op != OP_PHI); |
|
splitCommon(insn, bb, attach); |
return bb; |
} |
|
BasicBlock * |
BasicBlock::splitAfter(Instruction *insn, bool attach) |
{ |
BasicBlock *bb = new BasicBlock(func); |
assert(!insn || insn->op != OP_PHI); |
|
bb->joinAt = joinAt; |
joinAt = NULL; |
|
splitCommon(insn ? insn->next : NULL, bb, attach); |
return bb; |
} |
|
bool |
BasicBlock::dominatedBy(BasicBlock *that) |
{ |
Graph::Node *bn = &that->dom; |
Graph::Node *dn = &this->dom; |
|
while (dn && dn != bn) |
dn = dn->parent(); |
|
return dn != NULL; |
} |
|
unsigned int |
BasicBlock::initiatesSimpleConditional() const |
{ |
Graph::Node *out[2]; |
int n; |
Graph::Edge::Type eR; |
|
if (cfg.outgoingCount() != 2) // -> if and -> else/endif |
return false; |
|
n = 0; |
for (Graph::EdgeIterator ei = cfg.outgoing(); !ei.end(); ei.next()) |
out[n++] = ei.getNode(); |
eR = out[1]->outgoing().getType(); |
|
// IF block is out edge to the right |
if (eR == Graph::Edge::CROSS || eR == Graph::Edge::BACK) |
return 0x2; |
|
if (out[1]->outgoingCount() != 1) // 0 is IF { RET; }, >1 is more divergence |
return 0x0; |
// do they reconverge immediately ? |
if (out[1]->outgoing().getNode() == out[0]) |
return 0x1; |
if (out[0]->outgoingCount() == 1) |
if (out[0]->outgoing().getNode() == out[1]->outgoing().getNode()) |
return 0x3; |
|
return 0x0; |
} |
|
bool |
Function::setEntry(BasicBlock *bb) |
{ |
if (cfg.getRoot()) |
return false; |
cfg.insert(&bb->cfg); |
return true; |
} |
|
bool |
Function::setExit(BasicBlock *bb) |
{ |
if (cfgExit) |
return false; |
cfgExit = &bb->cfg; |
return true; |
} |
|
unsigned int |
Function::orderInstructions(ArrayList &result) |
{ |
result.clear(); |
|
for (IteratorRef it = cfg.iteratorCFG(); !it->end(); it->next()) { |
BasicBlock *bb = |
BasicBlock::get(reinterpret_cast<Graph::Node *>(it->get())); |
|
for (Instruction *insn = bb->getFirst(); insn; insn = insn->next) |
result.insert(insn, insn->serial); |
} |
|
return result.getSize(); |
} |
|
void |
Function::buildLiveSets() |
{ |
for (unsigned i = 0; i <= loopNestingBound; ++i) |
buildLiveSetsPreSSA(BasicBlock::get(cfg.getRoot()), cfg.nextSequence()); |
|
for (ArrayList::Iterator bi = allBBlocks.iterator(); !bi.end(); bi.next()) |
BasicBlock::get(bi)->liveSet.marker = false; |
} |
|
void |
Function::buildDefSets() |
{ |
for (unsigned i = 0; i <= loopNestingBound; ++i) |
buildDefSetsPreSSA(BasicBlock::get(cfgExit), cfg.nextSequence()); |
|
for (ArrayList::Iterator bi = allBBlocks.iterator(); !bi.end(); bi.next()) |
BasicBlock::get(bi)->liveSet.marker = false; |
} |
|
bool |
Pass::run(Program *prog, bool ordered, bool skipPhi) |
{ |
this->prog = prog; |
err = false; |
return doRun(prog, ordered, skipPhi); |
} |
|
bool |
Pass::doRun(Program *prog, bool ordered, bool skipPhi) |
{ |
for (IteratorRef it = prog->calls.iteratorDFS(false); |
!it->end(); it->next()) { |
Graph::Node *n = reinterpret_cast<Graph::Node *>(it->get()); |
if (!doRun(Function::get(n), ordered, skipPhi)) |
return false; |
} |
return !err; |
} |
|
bool |
Pass::run(Function *func, bool ordered, bool skipPhi) |
{ |
prog = func->getProgram(); |
err = false; |
return doRun(func, ordered, skipPhi); |
} |
|
bool |
Pass::doRun(Function *func, bool ordered, bool skipPhi) |
{ |
IteratorRef bbIter; |
BasicBlock *bb; |
Instruction *insn, *next; |
|
this->func = func; |
if (!visit(func)) |
return false; |
|
bbIter = ordered ? func->cfg.iteratorCFG() : func->cfg.iteratorDFS(); |
|
for (; !bbIter->end(); bbIter->next()) { |
bb = BasicBlock::get(reinterpret_cast<Graph::Node *>(bbIter->get())); |
if (!visit(bb)) |
break; |
for (insn = skipPhi ? bb->getEntry() : bb->getFirst(); insn != NULL; |
insn = next) { |
next = insn->next; |
if (!visit(insn)) |
break; |
} |
} |
|
return !err; |
} |
|
void |
Function::printCFGraph(const char *filePath) |
{ |
FILE *out = fopen(filePath, "a"); |
if (!out) { |
ERROR("failed to open file: %s\n", filePath); |
return; |
} |
INFO("printing control flow graph to: %s\n", filePath); |
|
fprintf(out, "digraph G {\n"); |
|
for (IteratorRef it = cfg.iteratorDFS(); !it->end(); it->next()) { |
BasicBlock *bb = BasicBlock::get( |
reinterpret_cast<Graph::Node *>(it->get())); |
int idA = bb->getId(); |
for (Graph::EdgeIterator ei = bb->cfg.outgoing(); !ei.end(); ei.next()) { |
int idB = BasicBlock::get(ei.getNode())->getId(); |
switch (ei.getType()) { |
case Graph::Edge::TREE: |
fprintf(out, "\t%i -> %i;\n", idA, idB); |
break; |
case Graph::Edge::FORWARD: |
fprintf(out, "\t%i -> %i [color=green];\n", idA, idB); |
break; |
case Graph::Edge::CROSS: |
fprintf(out, "\t%i -> %i [color=red];\n", idA, idB); |
break; |
case Graph::Edge::BACK: |
fprintf(out, "\t%i -> %i;\n", idA, idB); |
break; |
case Graph::Edge::DUMMY: |
fprintf(out, "\t%i -> %i [style=dotted];\n", idA, idB); |
break; |
default: |
assert(0); |
break; |
} |
} |
} |
|
fprintf(out, "}\n"); |
fclose(out); |
} |
|
} // namespace nv50_ir |