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"
24 #include "codegen/nv50_ir_target.h"
28 // Converts nv50 IR generated from TGSI to SSA form.
30 // DominatorTree implements an algorithm for finding immediate dominators,
31 // as described by T. Lengauer & R. Tarjan.
32 class DominatorTree
: public Graph
35 DominatorTree(Graph
*cfg
);
38 bool dominates(BasicBlock
*, BasicBlock
*);
40 void findDominanceFrontiers();
44 void buildDFS(Node
*);
47 inline void link(int, int);
58 #define SEMI(i) (data[(i) + 0 * count])
59 #define ANCESTOR(i) (data[(i) + 1 * count])
60 #define PARENT(i) (data[(i) + 2 * count])
61 #define LABEL(i) (data[(i) + 3 * count])
62 #define DOM(i) (data[(i) + 4 * count])
65 void DominatorTree::debugPrint()
67 for (int i
= 0; i
< count
; ++i
) {
68 INFO("SEMI(%i) = %i\n", i
, SEMI(i
));
69 INFO("ANCESTOR(%i) = %i\n", i
, ANCESTOR(i
));
70 INFO("PARENT(%i) = %i\n", i
, PARENT(i
));
71 INFO("LABEL(%i) = %i\n", i
, LABEL(i
));
72 INFO("DOM(%i) = %i\n", i
, DOM(i
));
76 DominatorTree::DominatorTree(Graph
*cfgraph
) : cfg(cfgraph
),
81 vert
= new Node
* [count
];
82 data
= new int[5 * count
];
84 for (IteratorRef it
= cfg
->iteratorDFS(true); !it
->end(); it
->next(), ++i
) {
85 vert
[i
] = reinterpret_cast<Node
*>(it
->get());
88 SEMI(i
) = ANCESTOR(i
) = -1;
97 void DominatorTree::buildDFS(Graph::Node
*node
)
99 SEMI(node
->tag
) = node
->tag
;
101 for (Graph::EdgeIterator ei
= node
->outgoing(); !ei
.end(); ei
.next()) {
102 if (SEMI(ei
.getNode()->tag
) < 0) {
103 buildDFS(ei
.getNode());
104 PARENT(ei
.getNode()->tag
) = node
->tag
;
109 void DominatorTree::squash(int v
)
111 if (ANCESTOR(ANCESTOR(v
)) >= 0) {
114 if (SEMI(LABEL(ANCESTOR(v
))) < SEMI(LABEL(v
)))
115 LABEL(v
) = LABEL(ANCESTOR(v
));
116 ANCESTOR(v
) = ANCESTOR(ANCESTOR(v
));
120 int DominatorTree::eval(int v
)
128 void DominatorTree::link(int v
, int w
)
133 void DominatorTree::build()
135 DLList
*bucket
= new DLList
[count
];
139 buildDFS(cfg
->getRoot());
141 for (w
= count
- 1; w
>= 1; --w
) {
143 assert(nw
->tag
== w
);
144 for (Graph::EdgeIterator ei
= nw
->incident(); !ei
.end(); ei
.next()) {
148 if (SEMI(u
) < SEMI(w
))
152 bucket
[SEMI(w
)].insert(nw
);
155 for (DLList::Iterator it
= bucket
[p
].iterator(); !it
.end(); it
.erase()) {
156 v
= reinterpret_cast<Node
*>(it
.get())->tag
;
158 DOM(v
) = (SEMI(u
) < SEMI(v
)) ? u
: p
;
161 for (w
= 1; w
< count
; ++w
) {
162 if (DOM(w
) != SEMI(w
))
163 DOM(w
) = DOM(DOM(w
));
167 insert(&BasicBlock::get(cfg
->getRoot())->dom
);
170 for (v
= 1; v
< count
; ++v
) {
171 nw
= &BasicBlock::get(vert
[DOM(v
)])->dom
;;
172 nv
= &BasicBlock::get(vert
[v
])->dom
;
173 if (nw
->getGraph() && !nv
->getGraph()) {
175 nw
->attach(nv
, Graph::Edge::TREE
);
189 void DominatorTree::findDominanceFrontiers()
193 for (IteratorRef dtIt
= iteratorDFS(false); !dtIt
->end(); dtIt
->next()) {
194 EdgeIterator succIt
, chldIt
;
196 bb
= BasicBlock::get(reinterpret_cast<Node
*>(dtIt
->get()));
199 for (succIt
= bb
->cfg
.outgoing(); !succIt
.end(); succIt
.next()) {
200 BasicBlock
*dfLocal
= BasicBlock::get(succIt
.getNode());
201 if (dfLocal
->idom() != bb
)
202 bb
->getDF().insert(dfLocal
);
205 for (chldIt
= bb
->dom
.outgoing(); !chldIt
.end(); chldIt
.next()) {
206 BasicBlock
*cb
= BasicBlock::get(chldIt
.getNode());
208 DLList::Iterator dfIt
= cb
->getDF().iterator();
209 for (; !dfIt
.end(); dfIt
.next()) {
210 BasicBlock
*dfUp
= BasicBlock::get(dfIt
);
211 if (dfUp
->idom() != bb
)
212 bb
->getDF().insert(dfUp
);
218 // liveIn(bb) = usedBeforeAssigned(bb) U (liveOut(bb) - assigned(bb))
220 Function::buildLiveSetsPreSSA(BasicBlock
*bb
, const int seq
)
222 Function
*f
= bb
->getFunction();
223 BitSet
usedBeforeAssigned(allLValues
.getSize(), true);
224 BitSet
assigned(allLValues
.getSize(), true);
226 bb
->liveSet
.allocate(allLValues
.getSize(), false);
229 for (Graph::EdgeIterator ei
= bb
->cfg
.outgoing(); !ei
.end(); ei
.next()) {
230 BasicBlock
*out
= BasicBlock::get(ei
.getNode());
233 if (out
->cfg
.visit(seq
))
234 buildLiveSetsPreSSA(out
, seq
);
236 bb
->liveSet
= out
->liveSet
;
238 bb
->liveSet
|= out
->liveSet
;
240 if (!n
&& !bb
->liveSet
.marker
)
242 bb
->liveSet
.marker
= true;
244 for (Instruction
*i
= bb
->getEntry(); i
; i
= i
->next
) {
245 for (int s
= 0; i
->srcExists(s
); ++s
)
246 if (i
->getSrc(s
)->asLValue() && !assigned
.test(i
->getSrc(s
)->id
))
247 usedBeforeAssigned
.set(i
->getSrc(s
)->id
);
248 for (int d
= 0; i
->defExists(d
); ++d
)
249 assigned
.set(i
->getDef(d
)->id
);
252 if (bb
== BasicBlock::get(f
->cfgExit
)) {
253 for (std::deque
<ValueRef
>::iterator it
= f
->outs
.begin();
254 it
!= f
->outs
.end(); ++it
) {
255 if (!assigned
.test(it
->get()->id
))
256 usedBeforeAssigned
.set(it
->get()->id
);
260 bb
->liveSet
.andNot(assigned
);
261 bb
->liveSet
|= usedBeforeAssigned
;
265 Function::buildDefSetsPreSSA(BasicBlock
*bb
, const int seq
)
267 bb
->defSet
.allocate(allLValues
.getSize(), !bb
->liveSet
.marker
);
268 bb
->liveSet
.marker
= true;
270 for (Graph::EdgeIterator ei
= bb
->cfg
.incident(); !ei
.end(); ei
.next()) {
271 BasicBlock
*in
= BasicBlock::get(ei
.getNode());
273 if (in
->cfg
.visit(seq
))
274 buildDefSetsPreSSA(in
, seq
);
276 bb
->defSet
|= in
->defSet
;
279 for (Instruction
*i
= bb
->getEntry(); i
; i
= i
->next
) {
280 for (int d
= 0; i
->defExists(d
); ++d
)
281 bb
->defSet
.set(i
->getDef(d
)->id
);
288 RenamePass(Function
*);
292 void search(BasicBlock
*);
294 inline LValue
*getStackTop(Value
*);
296 LValue
*mkUndefined(Value
*);
305 Program::convertToSSA()
307 for (ArrayList::Iterator fi
= allFuncs
.iterator(); !fi
.end(); fi
.next()) {
308 Function
*fn
= reinterpret_cast<Function
*>(fi
.get());
309 if (!fn
->convertToSSA())
315 // XXX: add edge from entry to exit ?
317 // Efficiently Computing Static Single Assignment Form and
318 // the Control Dependence Graph,
319 // R. Cytron, J. Ferrante, B. K. Rosen, M. N. Wegman, F. K. Zadeck
321 Function::convertToSSA()
323 // 0. calculate live in variables (for pruned SSA)
326 // 1. create the dominator tree
327 domTree
= new DominatorTree(&cfg
);
328 reinterpret_cast<DominatorTree
*>(domTree
)->findDominanceFrontiers();
330 // 2. insert PHI functions
336 int *hasAlready
= new int[allBBlocks
.getSize() * 2];
337 int *work
= &hasAlready
[allBBlocks
.getSize()];
339 memset(hasAlready
, 0, allBBlocks
.getSize() * 2 * sizeof(int));
342 for (var
= 0; var
< allLValues
.getSize(); ++var
) {
343 if (!allLValues
.get(var
))
345 lval
= reinterpret_cast<Value
*>(allLValues
.get(var
))->asLValue();
346 if (!lval
|| lval
->defs
.empty())
350 // TODO: don't add phi functions for values that aren't used outside
351 // the BB they're defined in
353 // gather blocks with assignments to lval in workList
354 for (Value::DefIterator d
= lval
->defs
.begin();
355 d
!= lval
->defs
.end(); ++d
) {
356 bb
= ((*d
)->getInsn() ? (*d
)->getInsn()->bb
: NULL
);
358 continue; // instruction likely been removed but not XXX deleted
360 if (work
[bb
->getId()] == iterCount
)
362 work
[bb
->getId()] = iterCount
;
366 // for each block in workList, insert a phi for lval in the block's
367 // dominance frontier (if we haven't already done so)
368 for (DLList::Iterator wI
= workList
.iterator(); !wI
.end(); wI
.erase()) {
369 bb
= BasicBlock::get(wI
);
371 DLList::Iterator dfIter
= bb
->getDF().iterator();
372 for (; !dfIter
.end(); dfIter
.next()) {
374 BasicBlock
*dfBB
= BasicBlock::get(dfIter
);
376 if (hasAlready
[dfBB
->getId()] >= iterCount
)
378 hasAlready
[dfBB
->getId()] = iterCount
;
380 // pruned SSA: don't need a phi if the value is not live-in
381 if (!dfBB
->liveSet
.test(lval
->id
))
384 phi
= new_Instruction(this, OP_PHI
, typeOfSize(lval
->reg
.size
));
385 dfBB
->insertTail(phi
);
387 phi
->setDef(0, lval
);
388 for (int s
= 0; s
< dfBB
->cfg
.incidentCount(); ++s
)
389 phi
->setSrc(s
, lval
);
391 if (work
[dfBB
->getId()] < iterCount
) {
392 work
[dfBB
->getId()] = iterCount
;
400 RenamePass
rename(this);
404 RenamePass::RenamePass(Function
*fn
) : func(fn
), prog(fn
->getProgram())
406 stack
= new Stack
[func
->allLValues
.getSize()];
409 RenamePass::~RenamePass()
416 RenamePass::getStackTop(Value
*val
)
418 if (!stack
[val
->id
].getSize())
420 return reinterpret_cast<LValue
*>(stack
[val
->id
].peek().u
.p
);
424 RenamePass::mkUndefined(Value
*val
)
426 LValue
*lval
= val
->asLValue();
428 LValue
*ud
= new_LValue(func
, lval
);
429 Instruction
*nop
= new_Instruction(func
, OP_NOP
, typeOfSize(lval
->reg
.size
));
431 BasicBlock::get(func
->cfg
.getRoot())->insertHead(nop
);
435 bool RenamePass::run()
439 search(BasicBlock::get(func
->domTree
->getRoot()));
444 // Go through BBs in dominance order, create new values for each definition,
445 // and replace all sources with their current new values.
447 // NOTE: The values generated for function inputs/outputs have no connection
448 // to their corresponding outputs/inputs in other functions. Only allocation
449 // of physical registers will establish this connection.
451 void RenamePass::search(BasicBlock
*bb
)
455 const Target
*targ
= prog
->getTarget();
457 // Put current definitions for function inputs values on the stack.
458 // They can be used before any redefinitions are pushed.
459 if (bb
== BasicBlock::get(func
->cfg
.getRoot())) {
460 for (std::deque
<ValueDef
>::iterator it
= func
->ins
.begin();
461 it
!= func
->ins
.end(); ++it
) {
462 lval
= it
->get()->asLValue();
465 ssa
= new_LValue(func
, targ
->nativeFile(lval
->reg
.file
));
466 ssa
->reg
.size
= lval
->reg
.size
;
467 ssa
->reg
.data
.id
= lval
->reg
.data
.id
;
470 stack
[lval
->id
].push(ssa
);
474 for (Instruction
*stmt
= bb
->getFirst(); stmt
; stmt
= stmt
->next
) {
475 // PHI sources get definitions from the passes through the incident BBs,
476 // so skip them here.
477 if (stmt
->op
!= OP_PHI
) {
478 for (s
= 0; stmt
->srcExists(s
); ++s
) {
479 lval
= stmt
->getSrc(s
)->asLValue();
482 // Values on the stack created in previously visited blocks, and
483 // function inputs, will be valid because they dominate this one.
484 lval
= getStackTop(lval
);
486 lval
= mkUndefined(stmt
->getSrc(s
));
487 stmt
->setSrc(s
, lval
);
490 for (d
= 0; stmt
->defExists(d
); ++d
) {
491 lval
= stmt
->def(d
).get()->asLValue();
494 new_LValue(func
, targ
->nativeFile(lval
->reg
.file
)));
495 stmt
->def(d
).get()->reg
.size
= lval
->reg
.size
;
496 stmt
->def(d
).get()->reg
.data
.id
= lval
->reg
.data
.id
;
497 stack
[lval
->id
].push(stmt
->def(d
).get());
501 // Update sources of PHI ops corresponding to this BB in outgoing BBs.
502 for (Graph::EdgeIterator ei
= bb
->cfg
.outgoing(); !ei
.end(); ei
.next()) {
505 BasicBlock
*sb
= BasicBlock::get(ei
.getNode());
507 // which predecessor of sb is bb ?
508 for (Graph::EdgeIterator ei
= sb
->cfg
.incident(); !ei
.end(); ei
.next()) {
509 if (ei
.getNode() == &bb
->cfg
)
513 assert(p
< sb
->cfg
.incidentCount());
515 for (phi
= sb
->getPhi(); phi
&& phi
->op
== OP_PHI
; phi
= phi
->next
) {
516 lval
= getStackTop(phi
->getSrc(p
));
518 lval
= mkUndefined(phi
->getSrc(p
));
519 phi
->setSrc(p
, lval
);
523 // Visit the BBs we dominate.
524 for (Graph::EdgeIterator ei
= bb
->dom
.outgoing(); !ei
.end(); ei
.next())
525 search(BasicBlock::get(ei
.getNode()));
527 // Update function outputs to the last definitions of their pre-SSA values.
528 // I hope they're unique, i.e. that we get PHIs for all of them ...
529 if (bb
== BasicBlock::get(func
->cfgExit
)) {
530 for (std::deque
<ValueRef
>::iterator it
= func
->outs
.begin();
531 it
!= func
->outs
.end(); ++it
) {
532 lval
= it
->get()->asLValue();
535 lval
= getStackTop(lval
);
537 lval
= mkUndefined(it
->get());
542 // Pop the values we created in this block from the stack because we will
543 // return to blocks that we do not dominate.
544 for (Instruction
*stmt
= bb
->getFirst(); stmt
; stmt
= stmt
->next
) {
545 if (stmt
->op
== OP_NOP
)
547 for (d
= 0; stmt
->defExists(d
); ++d
)
548 stack
[stmt
->def(d
).preSSA()->id
].pop();
552 } // namespace nv50_ir