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 BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
18 * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF
19 * OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
24 #include "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
),
82 vert
= new Node
* [count
];
83 data
= new int[5 * count
];
85 for (i
= 0, iter
= cfg
->iteratorDFS(true); !iter
->end(); iter
->next(), ++i
) {
86 vert
[i
] = reinterpret_cast<Node
*>(iter
->get());
89 SEMI(i
) = ANCESTOR(i
) = -1;
91 cfg
->putIterator(iter
);
99 void DominatorTree::buildDFS(Graph::Node
*node
)
101 SEMI(node
->tag
) = node
->tag
;
103 for (Graph::EdgeIterator ei
= node
->outgoing(); !ei
.end(); ei
.next()) {
104 if (SEMI(ei
.getNode()->tag
) < 0) {
105 buildDFS(ei
.getNode());
106 PARENT(ei
.getNode()->tag
) = node
->tag
;
111 void DominatorTree::squash(int v
)
113 if (ANCESTOR(ANCESTOR(v
)) >= 0) {
116 if (SEMI(LABEL(ANCESTOR(v
))) < SEMI(LABEL(v
)))
117 LABEL(v
) = LABEL(ANCESTOR(v
));
118 ANCESTOR(v
) = ANCESTOR(ANCESTOR(v
));
122 int DominatorTree::eval(int v
)
130 void DominatorTree::link(int v
, int w
)
135 void DominatorTree::build()
137 DLList
*bucket
= new DLList
[count
];
141 buildDFS(cfg
->getRoot());
143 for (w
= count
- 1; w
>= 1; --w
) {
145 assert(nw
->tag
== w
);
146 for (Graph::EdgeIterator ei
= nw
->incident(); !ei
.end(); ei
.next()) {
150 if (SEMI(u
) < SEMI(w
))
154 bucket
[SEMI(w
)].insert(nw
);
157 for (DLList::Iterator it
= bucket
[p
].iterator(); !it
.end(); it
.erase()) {
158 v
= reinterpret_cast<Node
*>(it
.get())->tag
;
160 DOM(v
) = (SEMI(u
) < SEMI(v
)) ? u
: p
;
163 for (w
= 1; w
< count
; ++w
) {
164 if (DOM(w
) != SEMI(w
))
165 DOM(w
) = DOM(DOM(w
));
169 insert(&BasicBlock::get(cfg
->getRoot())->dom
);
172 for (v
= 1; v
< count
; ++v
) {
173 nw
= &BasicBlock::get(vert
[DOM(v
)])->dom
;;
174 nv
= &BasicBlock::get(vert
[v
])->dom
;
175 if (nw
->getGraph() && !nv
->getGraph()) {
177 nw
->attach(nv
, Graph::Edge::TREE
);
191 void DominatorTree::findDominanceFrontiers()
196 for (dtIter
= this->iteratorDFS(false); !dtIter
->end(); dtIter
->next()) {
197 EdgeIterator succIter
, chldIter
;
199 bb
= BasicBlock::get(reinterpret_cast<Node
*>(dtIter
->get()));
202 for (succIter
= bb
->cfg
.outgoing(); !succIter
.end(); succIter
.next()) {
203 BasicBlock
*dfLocal
= BasicBlock::get(succIter
.getNode());
204 if (dfLocal
->idom() != bb
)
205 bb
->getDF().insert(dfLocal
);
208 for (chldIter
= bb
->dom
.outgoing(); !chldIter
.end(); chldIter
.next()) {
209 BasicBlock
*cb
= BasicBlock::get(chldIter
.getNode());
211 DLList::Iterator dfIter
= cb
->getDF().iterator();
212 for (; !dfIter
.end(); dfIter
.next()) {
213 BasicBlock
*dfUp
= BasicBlock::get(dfIter
);
214 if (dfUp
->idom() != bb
)
215 bb
->getDF().insert(dfUp
);
219 this->putIterator(dtIter
);
222 // liveIn(bb) = usedBeforeAssigned(bb) U (liveOut(bb) - assigned(bb))
224 Function::buildLiveSetsPreSSA(BasicBlock
*bb
, const int seq
)
226 BitSet
usedBeforeAssigned(allLValues
.getSize(), true);
227 BitSet
assigned(allLValues
.getSize(), true);
229 bb
->liveSet
.allocate(allLValues
.getSize(), false);
232 for (Graph::EdgeIterator ei
= bb
->cfg
.outgoing(); !ei
.end(); ei
.next()) {
233 BasicBlock
*out
= BasicBlock::get(ei
.getNode());
236 if (out
->cfg
.visit(seq
))
237 buildLiveSetsPreSSA(out
, seq
);
239 bb
->liveSet
= out
->liveSet
;
241 bb
->liveSet
|= out
->liveSet
;
243 if (!n
&& !bb
->liveSet
.marker
)
245 bb
->liveSet
.marker
= true;
247 for (Instruction
*i
= bb
->getEntry(); i
; i
= i
->next
) {
248 for (int s
= 0; i
->srcExists(s
); ++s
)
249 if (i
->getSrc(s
)->asLValue() && !assigned
.test(i
->getSrc(s
)->id
))
250 usedBeforeAssigned
.set(i
->getSrc(s
)->id
);
251 for (int d
= 0; i
->defExists(d
); ++d
)
252 assigned
.set(i
->getDef(d
)->id
);
255 bb
->liveSet
.andNot(assigned
);
256 bb
->liveSet
|= usedBeforeAssigned
;
262 RenamePass(Function
*);
266 void search(BasicBlock
*);
268 inline LValue
*getStackTop(Value
*);
278 Program::convertToSSA()
280 for (ArrayList::Iterator fi
= allFuncs
.iterator(); !fi
.end(); fi
.next()) {
281 Function
*fn
= reinterpret_cast<Function
*>(fi
.get());
282 if (!fn
->convertToSSA())
288 // XXX: add edge from entry to exit ?
290 // Efficiently Computing Static Single Assignment Form and
291 // the Control Dependence Graph,
292 // R. Cytron, J. Ferrante, B. K. Rosen, M. N. Wegman, F. K. Zadeck
294 Function::convertToSSA()
296 // 0. calculate live in variables (for pruned SSA)
297 int seq
= cfg
.nextSequence();
298 for (unsigned i
= 0; i
<= loopNestingBound
; seq
= cfg
.nextSequence(), ++i
)
299 buildLiveSetsPreSSA(BasicBlock::get(cfg
.getRoot()), seq
);
301 // reset liveSet marker for use in regalloc
302 for (ArrayList::Iterator bi
= allBBlocks
.iterator(); !bi
.end(); bi
.next())
303 reinterpret_cast<BasicBlock
*>(bi
.get())->liveSet
.marker
= false;
305 // 1. create the dominator tree
306 domTree
= new DominatorTree(&cfg
);
307 reinterpret_cast<DominatorTree
*>(domTree
)->findDominanceFrontiers();
309 // 2. insert PHI functions
315 int *hasAlready
= new int[allBBlocks
.getSize() * 2];
316 int *work
= &hasAlready
[allBBlocks
.getSize()];
318 memset(hasAlready
, 0, allBBlocks
.getSize() * 2 * sizeof(int));
321 for (var
= 0; var
< allLValues
.getSize(); ++var
) {
322 if (!allLValues
.get(var
))
324 lval
= reinterpret_cast<Value
*>(allLValues
.get(var
))->asLValue();
325 if (!lval
|| !lval
->defs
)
329 // TODO: don't add phi functions for values that aren't used outside
330 // the BB they're defined in
332 // gather blocks with assignments to lval in workList
333 for (ValueDef::Iterator d
= lval
->defs
->iterator(); !d
.end(); d
.next()) {
334 bb
= d
.get()->getInsn()->bb
;
336 continue; // instruction likely been removed but not XXX deleted
338 if (work
[bb
->getId()] == iterCount
)
340 work
[bb
->getId()] = iterCount
;
344 // for each block in workList, insert a phi for lval in the block's
345 // dominance frontier (if we haven't already done so)
346 for (DLList::Iterator wI
= workList
.iterator(); !wI
.end(); wI
.erase()) {
347 bb
= BasicBlock::get(wI
);
349 DLList::Iterator dfIter
= bb
->getDF().iterator();
350 for (; !dfIter
.end(); dfIter
.next()) {
352 BasicBlock
*dfBB
= BasicBlock::get(dfIter
);
354 if (hasAlready
[dfBB
->getId()] >= iterCount
)
356 hasAlready
[dfBB
->getId()] = iterCount
;
358 // pruned SSA: don't need a phi if the value is not live-in
359 if (!dfBB
->liveSet
.test(lval
->id
))
362 // TODO: use dedicated PhiInstruction to lift this limit
363 assert(dfBB
->cfg
.incidentCount() <= NV50_IR_MAX_SRCS
);
365 phi
= new_Instruction(this, OP_PHI
, typeOfSize(lval
->reg
.size
));
366 dfBB
->insertTail(phi
);
368 phi
->setDef(0, lval
);
369 for (int s
= 0; s
< dfBB
->cfg
.incidentCount(); ++s
)
370 phi
->setSrc(s
, lval
);
372 if (work
[dfBB
->getId()] < iterCount
) {
373 work
[dfBB
->getId()] = iterCount
;
381 RenamePass
rename(this);
385 RenamePass::RenamePass(Function
*fn
) : func(fn
), prog(fn
->getProgram())
387 BasicBlock
*root
= BasicBlock::get(func
->cfg
.getRoot());
389 undef
= new_Instruction(func
, OP_NOP
, TYPE_U32
);
390 undef
->setDef(0, new_LValue(func
, FILE_GPR
));
391 root
->insertHead(undef
);
393 stack
= new Stack
[func
->allLValues
.getSize()];
396 RenamePass::~RenamePass()
403 RenamePass::getStackTop(Value
*val
)
405 if (!stack
[val
->id
].getSize())
407 return reinterpret_cast<LValue
*>(stack
[val
->id
].peek().u
.p
);
410 bool RenamePass::run()
414 search(BasicBlock::get(func
->domTree
->getRoot()));
416 ArrayList::Iterator iter
= func
->allInsns
.iterator();
417 for (; !iter
.end(); iter
.next()) {
418 Instruction
*insn
= reinterpret_cast<Instruction
*>(iter
.get());
419 for (int d
= 0; insn
->defExists(d
); ++d
)
420 insn
->def
[d
].restoreDefList();
426 void RenamePass::search(BasicBlock
*bb
)
430 const Target
*targ
= prog
->getTarget();
432 for (Instruction
*stmt
= bb
->getFirst(); stmt
; stmt
= stmt
->next
) {
433 if (stmt
->op
!= OP_PHI
) {
434 for (s
= 0; stmt
->srcExists(s
); ++s
) {
435 lval
= stmt
->getSrc(s
)->asLValue();
438 lval
= getStackTop(lval
);
440 lval
= static_cast<LValue
*>(undef
->getDef(0));
441 stmt
->setSrc(s
, lval
);
444 for (d
= 0; stmt
->defExists(d
); ++d
) {
445 lval
= stmt
->def
[d
].get()->asLValue();
448 new_LValue(func
, targ
->nativeFile(lval
->reg
.file
)));
449 stmt
->def
[d
].get()->reg
.data
.id
= lval
->reg
.data
.id
;
450 stack
[lval
->id
].push(stmt
->def
[d
].get());
454 for (Graph::EdgeIterator ei
= bb
->cfg
.outgoing(); !ei
.end(); ei
.next()) {
457 BasicBlock
*sb
= BasicBlock::get(ei
.getNode());
459 // which predecessor of sb is bb ?
460 for (Graph::EdgeIterator ei
= sb
->cfg
.incident(); !ei
.end(); ei
.next()) {
461 if (ei
.getNode() == &bb
->cfg
)
465 assert(p
< sb
->cfg
.incidentCount());
467 for (phi
= sb
->getPhi(); phi
&& phi
->op
== OP_PHI
; phi
= phi
->next
) {
468 lval
= getStackTop(phi
->getSrc(p
));
470 lval
= undef
->getDef(0)->asLValue();
471 phi
->setSrc(p
, lval
);
475 for (Graph::EdgeIterator ei
= bb
->dom
.outgoing(); !ei
.end(); ei
.next())
476 search(BasicBlock::get(ei
.getNode()));
478 for (Instruction
*stmt
= bb
->getFirst(); stmt
; stmt
= stmt
->next
) {
479 for (d
= 0; stmt
->defExists(d
); ++d
)
480 stack
[stmt
->def
[d
].preSSA()->id
].pop();
484 } // namespace nv50_ir