← Back to branch summary

~mmach/netext73/mesa-haswell

« back to all changes in this revision

Viewing changes to src/gallium/drivers/nouveau/codegen/nv50_ir_bb.cpp

  • Committer: mmach
  • Date: 2022-09-22 19:56:13 UTC
  • Revision ID: netbit73@gmail.com-20220922195613-wtik9mmy20tmor0i
2022-09-22 21:17:09

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/gallium/drivers/nouveau/codegen/nv50_ir_bb.cpp
1
 
/*
2
 
 * Copyright 2011 Christoph Bumiller
3
 
 *
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:
10
 
 *
11
 
 * The above copyright notice and this permission notice shall be included in
12
 
 * all copies or substantial portions of the Software.
13
 
 *
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.
21
 
 */
22
 
 
23
 
#include "codegen/nv50_ir.h"
24
 
 
25
 
namespace nv50_ir {
26
 
 
27
 
Function::Function(Program *p, const char *fnName, uint32_t label)
28
 
   : call(this),
29
 
     label(label),
30
 
     name(fnName),
31
 
     prog(p)
32
 
{
33
 
   cfgExit = NULL;
34
 
   domTree = NULL;
35
 
 
36
 
   bbArray = NULL;
37
 
   bbCount = 0;
38
 
   loopNestingBound = 0;
39
 
   regClobberMax = 0;
40
 
 
41
 
   binPos = 0;
42
 
   binSize = 0;
43
 
 
44
 
   stackPtr = NULL;
45
 
   tlsBase = 0;
46
 
   tlsSize = 0;
47
 
 
48
 
   prog->add(this, id);
49
 
}
50
 
 
51
 
Function::~Function()
52
 
{
53
 
   prog->del(this, id);
54
 
 
55
 
   if (domTree)
56
 
      delete domTree;
57
 
   if (bbArray)
58
 
      delete[] bbArray;
59
 
 
60
 
   // clear value refs and defs
61
 
   ins.clear();
62
 
   outs.clear();
63
 
 
64
 
   for (ArrayList::Iterator it = allInsns.iterator(); !it.end(); it.next())
65
 
      delete_Instruction(prog, reinterpret_cast<Instruction *>(it.get()));
66
 
 
67
 
   for (ArrayList::Iterator it = allLValues.iterator(); !it.end(); it.next())
68
 
      delete_Value(prog, reinterpret_cast<LValue *>(it.get()));
69
 
 
70
 
   for (ArrayList::Iterator BBs = allBBlocks.iterator(); !BBs.end(); BBs.next())
71
 
      delete reinterpret_cast<BasicBlock *>(BBs.get());
72
 
}
73
 
 
74
 
BasicBlock::BasicBlock(Function *fn) : cfg(this), dom(this), func(fn)
75
 
{
76
 
   program = func->getProgram();
77
 
 
78
 
   joinAt = phi = entry = exit = NULL;
79
 
 
80
 
   numInsns = 0;
81
 
   binPos = 0;
82
 
   binSize = 0;
83
 
 
84
 
   explicitCont = false;
85
 
 
86
 
   func->add(this, this->id);
87
 
}
88
 
 
89
 
BasicBlock::~BasicBlock()
90
 
{
91
 
   // nothing yet
92
 
}
93
 
 
94
 
BasicBlock *
95
 
BasicBlock::clone(ClonePolicy<Function>& pol) const
96
 
{
97
 
   BasicBlock *bb = new BasicBlock(pol.context());
98
 
 
99
 
   pol.set(this, bb);
100
 
 
101
 
   for (Instruction *i = getFirst(); i; i = i->next)
102
 
      bb->insertTail(i->clone(pol));
103
 
 
104
 
   pol.context()->cfg.insert(&bb->cfg);
105
 
 
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());
109
 
   }
110
 
 
111
 
   return bb;
112
 
}
113
 
 
114
 
BasicBlock *
115
 
BasicBlock::idom() const
116
 
{
117
 
   Graph::Node *dn = dom.parent();
118
 
   return dn ? BasicBlock::get(dn) : NULL;
119
 
}
120
 
 
121
 
void
122
 
BasicBlock::insertHead(Instruction *inst)
123
 
{
124
 
   assert(inst->next == 0 && inst->prev == 0);
125
 
 
126
 
   if (inst->op == OP_PHI) {
127
 
      if (phi) {
128
 
         insertBefore(phi, inst);
129
 
      } else {
130
 
         if (entry) {
131
 
            insertBefore(entry, inst);
132
 
         } else {
133
 
            assert(!exit);
134
 
            phi = exit = inst;
135
 
            inst->bb = this;
136
 
            ++numInsns;
137
 
         }
138
 
      }
139
 
   } else {
140
 
      if (entry) {
141
 
         insertBefore(entry, inst);
142
 
      } else {
143
 
         if (phi) {
144
 
            insertAfter(exit, inst); // after last phi
145
 
         } else {
146
 
            assert(!exit);
147
 
            entry = exit = inst;
148
 
            inst->bb = this;
149
 
            ++numInsns;
150
 
         }
151
 
      }
152
 
   }
153
 
}
154
 
 
155
 
void
156
 
BasicBlock::insertTail(Instruction *inst)
157
 
{
158
 
   assert(inst->next == 0 && inst->prev == 0);
159
 
 
160
 
   if (inst->op == OP_PHI) {
161
 
      if (entry) {
162
 
         insertBefore(entry, inst);
163
 
      } else
164
 
      if (exit) {
165
 
         assert(phi);
166
 
         insertAfter(exit, inst);
167
 
      } else {
168
 
         assert(!phi);
169
 
         phi = exit = inst;
170
 
         inst->bb = this;
171
 
         ++numInsns;
172
 
      }
173
 
   } else {
174
 
      if (exit) {
175
 
         insertAfter(exit, inst);
176
 
      } else {
177
 
         assert(!phi);
178
 
         entry = exit = inst;
179
 
         inst->bb = this;
180
 
         ++numInsns;
181
 
      }
182
 
   }
183
 
}
184
 
 
185
 
void
186
 
BasicBlock::insertBefore(Instruction *q, Instruction *p)
187
 
{
188
 
   assert(p && q);
189
 
 
190
 
   assert(p->next == 0 && p->prev == 0);
191
 
 
192
 
   if (q == entry) {
193
 
      if (p->op == OP_PHI) {
194
 
         if (!phi)
195
 
            phi = p;
196
 
      } else {
197
 
         entry = p;
198
 
      }
199
 
   } else
200
 
   if (q == phi) {
201
 
      assert(p->op == OP_PHI);
202
 
      phi = p;
203
 
   }
204
 
 
205
 
   p->next = q;
206
 
   p->prev = q->prev;
207
 
   if (p->prev)
208
 
      p->prev->next = p;
209
 
   q->prev = p;
210
 
 
211
 
   p->bb = this;
212
 
   ++numInsns;
213
 
}
214
 
 
215
 
void
216
 
BasicBlock::insertAfter(Instruction *p, Instruction *q)
217
 
{
218
 
   assert(p && q);
219
 
   assert(q->op != OP_PHI || p->op == OP_PHI);
220
 
 
221
 
   assert(q->next == 0 && q->prev == 0);
222
 
 
223
 
   if (p == exit)
224
 
      exit = q;
225
 
   if (p->op == OP_PHI && q->op != OP_PHI)
226
 
      entry = q;
227
 
 
228
 
   q->prev = p;
229
 
   q->next = p->next;
230
 
   if (q->next)
231
 
      q->next->prev = q;
232
 
   p->next = q;
233
 
 
234
 
   q->bb = this;
235
 
   ++numInsns;
236
 
}
237
 
 
238
 
void
239
 
BasicBlock::remove(Instruction *insn)
240
 
{
241
 
   assert(insn->bb == this);
242
 
 
243
 
   if (insn->prev)
244
 
      insn->prev->next = insn->next;
245
 
 
246
 
   if (insn->next)
247
 
      insn->next->prev = insn->prev;
248
 
   else
249
 
      exit = insn->prev;
250
 
 
251
 
   if (insn == entry) {
252
 
      if (insn->next)
253
 
         entry = insn->next;
254
 
      else
255
 
      if (insn->prev && insn->prev->op != OP_PHI)
256
 
         entry = insn->prev;
257
 
      else
258
 
         entry = NULL;
259
 
   }
260
 
 
261
 
   if (insn == phi)
262
 
      phi = (insn->next && insn->next->op == OP_PHI) ? insn->next : 0;
263
 
 
264
 
   --numInsns;
265
 
   insn->bb = NULL;
266
 
   insn->next =
267
 
   insn->prev = NULL;
268
 
}
269
 
 
270
 
void BasicBlock::permuteAdjacent(Instruction *a, Instruction *b)
271
 
{
272
 
   assert(a->bb == b->bb);
273
 
 
274
 
   if (a->next != b) {
275
 
      Instruction *i = a;
276
 
      a = b;
277
 
      b = i;
278
 
   }
279
 
   assert(a->next == b);
280
 
   assert(a->op != OP_PHI && b->op != OP_PHI);
281
 
 
282
 
   if (b == exit)
283
 
      exit = a;
284
 
   if (a == entry)
285
 
      entry = b;
286
 
 
287
 
   b->prev = a->prev;
288
 
   a->next = b->next;
289
 
   b->next = a;
290
 
   a->prev = b;
291
 
 
292
 
   if (b->prev)
293
 
      b->prev->next = b;
294
 
   if (a->next)
295
 
      a->next->prev = a;
296
 
}
297
 
 
298
 
void
299
 
BasicBlock::splitCommon(Instruction *insn, BasicBlock *bb, bool attach)
300
 
{
301
 
   bb->entry = insn;
302
 
 
303
 
   if (insn) {
304
 
      exit = insn->prev;
305
 
      insn->prev = NULL;
306
 
   }
307
 
 
308
 
   if (exit)
309
 
      exit->next = NULL;
310
 
   else
311
 
      entry = NULL;
312
 
 
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());
317
 
   }
318
 
 
319
 
   for (; insn; insn = insn->next) {
320
 
      this->numInsns--;
321
 
      bb->numInsns++;
322
 
      insn->bb = bb;
323
 
      bb->exit = insn;
324
 
   }
325
 
   if (attach)
326
 
      this->cfg.attach(&bb->cfg, Graph::Edge::TREE);
327
 
}
328
 
 
329
 
BasicBlock *
330
 
BasicBlock::splitBefore(Instruction *insn, bool attach)
331
 
{
332
 
   BasicBlock *bb = new BasicBlock(func);
333
 
   assert(!insn || insn->op != OP_PHI);
334
 
 
335
 
   bb->joinAt = joinAt;
336
 
   joinAt = NULL;
337
 
 
338
 
   splitCommon(insn, bb, attach);
339
 
   return bb;
340
 
}
341
 
 
342
 
BasicBlock *
343
 
BasicBlock::splitAfter(Instruction *insn, bool attach)
344
 
{
345
 
   BasicBlock *bb = new BasicBlock(func);
346
 
   assert(!insn || insn->op != OP_PHI);
347
 
 
348
 
   bb->joinAt = joinAt;
349
 
   joinAt = NULL;
350
 
 
351
 
   splitCommon(insn ? insn->next : NULL, bb, attach);
352
 
   return bb;
353
 
}
354
 
 
355
 
bool
356
 
BasicBlock::dominatedBy(BasicBlock *that)
357
 
{
358
 
   Graph::Node *bn = &that->dom;
359
 
   Graph::Node *dn = &this->dom;
360
 
 
361
 
   while (dn && dn != bn)
362
 
      dn = dn->parent();
363
 
 
364
 
   return dn != NULL;
365
 
}
366
 
 
367
 
unsigned int
368
 
BasicBlock::initiatesSimpleConditional() const
369
 
{
370
 
   Graph::Node *out[2];
371
 
   int n;
372
 
   Graph::Edge::Type eR;
373
 
 
374
 
   if (cfg.outgoingCount() != 2) // -> if and -> else/endif
375
 
      return false;
376
 
 
377
 
   n = 0;
378
 
   for (Graph::EdgeIterator ei = cfg.outgoing(); !ei.end(); ei.next())
379
 
      out[n++] = ei.getNode();
380
 
   eR = out[1]->outgoing().getType();
381
 
 
382
 
   // IF block is out edge to the right
383
 
   if (eR == Graph::Edge::CROSS || eR == Graph::Edge::BACK)
384
 
      return 0x2;
385
 
 
386
 
   if (out[1]->outgoingCount() != 1) // 0 is IF { RET; }, >1 is more divergence
387
 
      return 0x0;
388
 
   // do they reconverge immediately ?
389
 
   if (out[1]->outgoing().getNode() == out[0])
390
 
      return 0x1;
391
 
   if (out[0]->outgoingCount() == 1)
392
 
      if (out[0]->outgoing().getNode() == out[1]->outgoing().getNode())
393
 
         return 0x3;
394
 
 
395
 
   return 0x0;
396
 
}
397
 
 
398
 
bool
399
 
Function::setEntry(BasicBlock *bb)
400
 
{
401
 
   if (cfg.getRoot())
402
 
      return false;
403
 
   cfg.insert(&bb->cfg);
404
 
   return true;
405
 
}
406
 
 
407
 
bool
408
 
Function::setExit(BasicBlock *bb)
409
 
{
410
 
   if (cfgExit)
411
 
      return false;
412
 
   cfgExit = &bb->cfg;
413
 
   return true;
414
 
}
415
 
 
416
 
unsigned int
417
 
Function::orderInstructions(ArrayList &result)
418
 
{
419
 
   result.clear();
420
 
 
421
 
   for (IteratorRef it = cfg.iteratorCFG(); !it->end(); it->next()) {
422
 
      BasicBlock *bb =
423
 
         BasicBlock::get(reinterpret_cast<Graph::Node *>(it->get()));
424
 
 
425
 
      for (Instruction *insn = bb->getFirst(); insn; insn = insn->next)
426
 
         result.insert(insn, insn->serial);
427
 
   }
428
 
 
429
 
   return result.getSize();
430
 
}
431
 
 
432
 
void
433
 
Function::buildLiveSets()
434
 
{
435
 
   for (unsigned i = 0; i <= loopNestingBound; ++i)
436
 
      buildLiveSetsPreSSA(BasicBlock::get(cfg.getRoot()), cfg.nextSequence());
437
 
 
438
 
   for (ArrayList::Iterator bi = allBBlocks.iterator(); !bi.end(); bi.next())
439
 
      BasicBlock::get(bi)->liveSet.marker = false;
440
 
}
441
 
 
442
 
void
443
 
Function::buildDefSets()
444
 
{
445
 
   for (unsigned i = 0; i <= loopNestingBound; ++i)
446
 
      buildDefSetsPreSSA(BasicBlock::get(cfgExit), cfg.nextSequence());
447
 
 
448
 
   for (ArrayList::Iterator bi = allBBlocks.iterator(); !bi.end(); bi.next())
449
 
      BasicBlock::get(bi)->liveSet.marker = false;
450
 
}
451
 
 
452
 
bool
453
 
Pass::run(Program *prog, bool ordered, bool skipPhi)
454
 
{
455
 
   this->prog = prog;
456
 
   err = false;
457
 
   return doRun(prog, ordered, skipPhi);
458
 
}
459
 
 
460
 
bool
461
 
Pass::doRun(Program *prog, bool ordered, bool skipPhi)
462
 
{
463
 
   for (IteratorRef it = prog->calls.iteratorDFS(false);
464
 
        !it->end(); it->next()) {
465
 
      Graph::Node *n = reinterpret_cast<Graph::Node *>(it->get());
466
 
      if (!doRun(Function::get(n), ordered, skipPhi))
467
 
         return false;
468
 
   }
469
 
   return !err;
470
 
}
471
 
 
472
 
bool
473
 
Pass::run(Function *func, bool ordered, bool skipPhi)
474
 
{
475
 
   prog = func->getProgram();
476
 
   err = false;
477
 
   return doRun(func, ordered, skipPhi);
478
 
}
479
 
 
480
 
bool
481
 
Pass::doRun(Function *func, bool ordered, bool skipPhi)
482
 
{
483
 
   IteratorRef bbIter;
484
 
   BasicBlock *bb;
485
 
   Instruction *insn, *next;
486
 
 
487
 
   this->func = func;
488
 
   if (!visit(func))
489
 
      return false;
490
 
 
491
 
   bbIter = ordered ? func->cfg.iteratorCFG() : func->cfg.iteratorDFS();
492
 
 
493
 
   for (; !bbIter->end(); bbIter->next()) {
494
 
      bb = BasicBlock::get(reinterpret_cast<Graph::Node *>(bbIter->get()));
495
 
      if (!visit(bb))
496
 
         break;
497
 
      for (insn = skipPhi ? bb->getEntry() : bb->getFirst(); insn != NULL;
498
 
           insn = next) {
499
 
         next = insn->next;
500
 
         if (!visit(insn))
501
 
            break;
502
 
      }
503
 
   }
504
 
 
505
 
   return !err;
506
 
}
507
 
 
508
 
void
509
 
Function::printCFGraph(const char *filePath)
510
 
{
511
 
   FILE *out = fopen(filePath, "a");
512
 
   if (!out) {
513
 
      ERROR("failed to open file: %s\n", filePath);
514
 
      return;
515
 
   }
516
 
   INFO("printing control flow graph to: %s\n", filePath);
517
 
 
518
 
   fprintf(out, "digraph G {\n");
519
 
 
520
 
   for (IteratorRef it = cfg.iteratorDFS(); !it->end(); it->next()) {
521
 
      BasicBlock *bb = BasicBlock::get(
522
 
         reinterpret_cast<Graph::Node *>(it->get()));
523
 
      int idA = bb->getId();
524
 
      for (Graph::EdgeIterator ei = bb->cfg.outgoing(); !ei.end(); ei.next()) {
525
 
         int idB = BasicBlock::get(ei.getNode())->getId();
526
 
         switch (ei.getType()) {
527
 
         case Graph::Edge::TREE:
528
 
            fprintf(out, "\t%i -> %i;\n", idA, idB);
529
 
            break;
530
 
         case Graph::Edge::FORWARD:
531
 
            fprintf(out, "\t%i -> %i [color=green];\n", idA, idB);
532
 
            break;
533
 
         case Graph::Edge::CROSS:
534
 
            fprintf(out, "\t%i -> %i [color=red];\n", idA, idB);
535
 
            break;
536
 
         case Graph::Edge::BACK:
537
 
            fprintf(out, "\t%i -> %i;\n", idA, idB);
538
 
            break;
539
 
         default:
540
 
            assert(0);
541
 
            break;
542
 
         }
543
 
      }
544
 
   }
545
 
 
546
 
   fprintf(out, "}\n");
547
 
   fclose(out);
548
 
}
549
 
 
550
 
} // namespace nv50_ir