2 * Copyright 2011 Christoph Bumiller
4 * Permission is hereby granted, free of charge, to any person obtaining a
5 * copy of this software and associated documentation files (the "Software"),
6 * to deal in the Software without restriction, including without limitation
7 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
8 * and/or sell copies of the Software, and to permit persons to whom the
9 * Software is furnished to do so, subject to the following conditions:
11 * The above copyright notice and this permission notice shall be included in
12 * all copies or substantial portions of the Software.
14 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
15 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
16 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
17 * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR
18 * OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
19 * ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
20 * OTHER DEALINGS IN THE SOFTWARE.
23 #include "codegen/nv50_ir.h"
27 Function::Function(Program
*p
, const char *fnName
, uint32_t label
)
60 // clear value refs and defs
64 for (ArrayList::Iterator it
= allInsns
.iterator(); !it
.end(); it
.next())
65 delete_Instruction(prog
, reinterpret_cast<Instruction
*>(it
.get()));
67 for (ArrayList::Iterator it
= allLValues
.iterator(); !it
.end(); it
.next())
68 delete_Value(prog
, reinterpret_cast<LValue
*>(it
.get()));
70 for (ArrayList::Iterator BBs
= allBBlocks
.iterator(); !BBs
.end(); BBs
.next())
71 delete reinterpret_cast<BasicBlock
*>(BBs
.get());
74 BasicBlock::BasicBlock(Function
*fn
) : cfg(this), dom(this), func(fn
)
76 program
= func
->getProgram();
78 joinAt
= phi
= entry
= exit
= NULL
;
86 func
->add(this, this->id
);
89 BasicBlock::~BasicBlock()
95 BasicBlock::clone(ClonePolicy
<Function
>& pol
) const
97 BasicBlock
*bb
= new BasicBlock(pol
.context());
101 for (Instruction
*i
= getFirst(); i
; i
= i
->next
)
102 bb
->insertTail(i
->clone(pol
));
104 pol
.context()->cfg
.insert(&bb
->cfg
);
106 for (Graph::EdgeIterator it
= cfg
.outgoing(); !it
.end(); it
.next()) {
107 BasicBlock
*obb
= BasicBlock::get(it
.getNode());
108 bb
->cfg
.attach(&pol
.get(obb
)->cfg
, it
.getType());
115 BasicBlock::idom() const
117 Graph::Node
*dn
= dom
.parent();
118 return dn
? BasicBlock::get(dn
) : NULL
;
122 BasicBlock::insertHead(Instruction
*inst
)
124 assert(inst
->next
== 0 && inst
->prev
== 0);
126 if (inst
->op
== OP_PHI
) {
128 insertBefore(phi
, inst
);
131 insertBefore(entry
, inst
);
141 insertBefore(entry
, inst
);
144 insertAfter(exit
, inst
); // after last phi
156 BasicBlock::insertTail(Instruction
*inst
)
158 assert(inst
->next
== 0 && inst
->prev
== 0);
160 if (inst
->op
== OP_PHI
) {
162 insertBefore(entry
, inst
);
166 insertAfter(exit
, inst
);
175 insertAfter(exit
, inst
);
186 BasicBlock::insertBefore(Instruction
*q
, Instruction
*p
)
190 assert(p
->next
== 0 && p
->prev
== 0);
193 if (p
->op
== OP_PHI
) {
201 assert(p
->op
== OP_PHI
);
216 BasicBlock::insertAfter(Instruction
*p
, Instruction
*q
)
219 assert(q
->op
!= OP_PHI
|| p
->op
== OP_PHI
);
221 assert(q
->next
== 0 && q
->prev
== 0);
225 if (p
->op
== OP_PHI
&& q
->op
!= OP_PHI
)
239 BasicBlock::remove(Instruction
*insn
)
241 assert(insn
->bb
== this);
244 insn
->prev
->next
= insn
->next
;
247 insn
->next
->prev
= insn
->prev
;
255 if (insn
->prev
&& insn
->prev
->op
!= OP_PHI
)
262 phi
= (insn
->next
&& insn
->next
->op
== OP_PHI
) ? insn
->next
: 0;
270 void BasicBlock::permuteAdjacent(Instruction
*a
, Instruction
*b
)
272 assert(a
->bb
== b
->bb
);
279 assert(a
->next
== b
);
280 assert(a
->op
!= OP_PHI
&& b
->op
!= OP_PHI
);
299 BasicBlock::splitCommon(Instruction
*insn
, BasicBlock
*bb
, bool attach
)
313 while (!cfg
.outgoing(true).end()) {
314 Graph::Edge
*e
= cfg
.outgoing(true).getEdge();
315 bb
->cfg
.attach(e
->getTarget(), e
->getType());
316 this->cfg
.detach(e
->getTarget());
319 for (; insn
; insn
= insn
->next
) {
326 this->cfg
.attach(&bb
->cfg
, Graph::Edge::TREE
);
330 BasicBlock::splitBefore(Instruction
*insn
, bool attach
)
332 BasicBlock
*bb
= new BasicBlock(func
);
333 assert(!insn
|| insn
->op
!= OP_PHI
);
335 splitCommon(insn
, bb
, attach
);
340 BasicBlock::splitAfter(Instruction
*insn
, bool attach
)
342 BasicBlock
*bb
= new BasicBlock(func
);
343 assert(!insn
|| insn
->op
!= OP_PHI
);
348 splitCommon(insn
? insn
->next
: NULL
, bb
, attach
);
353 BasicBlock::dominatedBy(BasicBlock
*that
)
355 Graph::Node
*bn
= &that
->dom
;
356 Graph::Node
*dn
= &this->dom
;
358 while (dn
&& dn
!= bn
)
365 BasicBlock::initiatesSimpleConditional() const
369 Graph::Edge::Type eR
;
371 if (cfg
.outgoingCount() != 2) // -> if and -> else/endif
375 for (Graph::EdgeIterator ei
= cfg
.outgoing(); !ei
.end(); ei
.next())
376 out
[n
++] = ei
.getNode();
377 eR
= out
[1]->outgoing().getType();
379 // IF block is out edge to the right
380 if (eR
== Graph::Edge::CROSS
|| eR
== Graph::Edge::BACK
)
383 if (out
[1]->outgoingCount() != 1) // 0 is IF { RET; }, >1 is more divergence
385 // do they reconverge immediately ?
386 if (out
[1]->outgoing().getNode() == out
[0])
388 if (out
[0]->outgoingCount() == 1)
389 if (out
[0]->outgoing().getNode() == out
[1]->outgoing().getNode())
396 Function::setEntry(BasicBlock
*bb
)
400 cfg
.insert(&bb
->cfg
);
405 Function::setExit(BasicBlock
*bb
)
414 Function::orderInstructions(ArrayList
&result
)
418 for (IteratorRef it
= cfg
.iteratorCFG(); !it
->end(); it
->next()) {
420 BasicBlock::get(reinterpret_cast<Graph::Node
*>(it
->get()));
422 for (Instruction
*insn
= bb
->getFirst(); insn
; insn
= insn
->next
)
423 result
.insert(insn
, insn
->serial
);
426 return result
.getSize();
430 Function::buildLiveSets()
432 for (unsigned i
= 0; i
<= loopNestingBound
; ++i
)
433 buildLiveSetsPreSSA(BasicBlock::get(cfg
.getRoot()), cfg
.nextSequence());
435 for (ArrayList::Iterator bi
= allBBlocks
.iterator(); !bi
.end(); bi
.next())
436 BasicBlock::get(bi
)->liveSet
.marker
= false;
440 Function::buildDefSets()
442 for (unsigned i
= 0; i
<= loopNestingBound
; ++i
)
443 buildDefSetsPreSSA(BasicBlock::get(cfgExit
), cfg
.nextSequence());
445 for (ArrayList::Iterator bi
= allBBlocks
.iterator(); !bi
.end(); bi
.next())
446 BasicBlock::get(bi
)->liveSet
.marker
= false;
450 Pass::run(Program
*prog
, bool ordered
, bool skipPhi
)
454 return doRun(prog
, ordered
, skipPhi
);
458 Pass::doRun(Program
*prog
, bool ordered
, bool skipPhi
)
460 for (IteratorRef it
= prog
->calls
.iteratorDFS(false);
461 !it
->end(); it
->next()) {
462 Graph::Node
*n
= reinterpret_cast<Graph::Node
*>(it
->get());
463 if (!doRun(Function::get(n
), ordered
, skipPhi
))
470 Pass::run(Function
*func
, bool ordered
, bool skipPhi
)
472 prog
= func
->getProgram();
474 return doRun(func
, ordered
, skipPhi
);
478 Pass::doRun(Function
*func
, bool ordered
, bool skipPhi
)
482 Instruction
*insn
, *next
;
488 bbIter
= ordered
? func
->cfg
.iteratorCFG() : func
->cfg
.iteratorDFS();
490 for (; !bbIter
->end(); bbIter
->next()) {
491 bb
= BasicBlock::get(reinterpret_cast<Graph::Node
*>(bbIter
->get()));
494 for (insn
= skipPhi
? bb
->getEntry() : bb
->getFirst(); insn
!= NULL
;
506 Function::printCFGraph(const char *filePath
)
508 FILE *out
= fopen(filePath
, "a");
510 ERROR("failed to open file: %s\n", filePath
);
513 INFO("printing control flow graph to: %s\n", filePath
);
515 fprintf(out
, "digraph G {\n");
517 for (IteratorRef it
= cfg
.iteratorDFS(); !it
->end(); it
->next()) {
518 BasicBlock
*bb
= BasicBlock::get(
519 reinterpret_cast<Graph::Node
*>(it
->get()));
520 int idA
= bb
->getId();
521 for (Graph::EdgeIterator ei
= bb
->cfg
.outgoing(); !ei
.end(); ei
.next()) {
522 int idB
= BasicBlock::get(ei
.getNode())->getId();
523 switch (ei
.getType()) {
524 case Graph::Edge::TREE
:
525 fprintf(out
, "\t%i -> %i;\n", idA
, idB
);
527 case Graph::Edge::FORWARD
:
528 fprintf(out
, "\t%i -> %i [color=green];\n", idA
, idB
);
530 case Graph::Edge::CROSS
:
531 fprintf(out
, "\t%i -> %i [color=red];\n", idA
, idB
);
533 case Graph::Edge::BACK
:
534 fprintf(out
, "\t%i -> %i;\n", idA
, idB
);
536 case Graph::Edge::DUMMY
:
537 fprintf(out
, "\t%i -> %i [style=dotted];\n", idA
, idB
);
550 } // namespace nv50_ir