← Back to branch summary

~ubuntu-branches/ubuntu/precise/mesa/precise-updates

« back to all changes in this revision

Viewing changes to src/gallium/drivers/nv50/codegen/nv50_ir_peephole.cpp

  • Committer: Package Import Robot
  • Author(s): Robert Hooker
  • Date: 2012-02-02 12:05:48 UTC
  • mfrom: (1.7.1) (3.3.27 sid)
  • Revision ID: package-import@ubuntu.com-20120202120548-nvkma85jq0h4coix
Tags: 8.0~rc2-0ubuntu4
Drop drisearchdir handling, it is no longer needed with multiarch
and dri-alternates being removed.

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/gallium/drivers/nv50/codegen/nv50_ir_peephole.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 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
 
20
 * SOFTWARE.
 
21
 */
 
22
 
 
23
#include "nv50_ir.h"
 
24
#include "nv50_ir_target.h"
 
25
#include "nv50_ir_build_util.h"
 
26
 
 
27
extern "C" {
 
28
#include "util/u_math.h"
 
29
}
 
30
 
 
31
namespace nv50_ir {
 
32
 
 
33
bool
 
34
Instruction::isNop() const
 
35
{
 
36
   if (op == OP_CONSTRAINT || op == OP_PHI)
 
37
      return true;
 
38
   if (terminator || join) // XXX: should terminator imply flow ?
 
39
      return false;
 
40
   if (!fixed && op == OP_NOP)
 
41
      return true;
 
42
 
 
43
   if (def[0].exists() && def[0].rep()->reg.data.id < 0) {
 
44
      for (int d = 1; defExists(d); ++d)
 
45
         if (def[d].rep()->reg.data.id >= 0)
 
46
            WARN("part of vector result is unused !\n");
 
47
      return true;
 
48
   }
 
49
 
 
50
   if (op == OP_MOV || op == OP_UNION) {
 
51
      if (!def[0].rep()->equals(getSrc(0)))
 
52
         return false;
 
53
      if (op == OP_UNION)
 
54
         if (!def[0].rep()->equals(getSrc(1)))
 
55
            return false;
 
56
      return true;
 
57
   }
 
58
 
 
59
   return false;
 
60
}
 
61
 
 
62
bool Instruction::isDead() const
 
63
{
 
64
   if (op == OP_STORE ||
 
65
       op == OP_EXPORT)
 
66
      return false;
 
67
 
 
68
   for (int d = 0; defExists(d); ++d)
 
69
      if (getDef(d)->refCount() || getDef(d)->reg.data.id >= 0)
 
70
         return false;
 
71
 
 
72
   if (terminator || asFlow())
 
73
      return false;
 
74
   if (fixed)
 
75
      return false;
 
76
 
 
77
   return true;
 
78
};
 
79
 
 
80
// =============================================================================
 
81
 
 
82
class CopyPropagation : public Pass
 
83
{
 
84
private:
 
85
   virtual bool visit(BasicBlock *);
 
86
};
 
87
 
 
88
// Propagate all MOVs forward to make subsequent optimization easier, except if
 
89
// the sources stem from a phi, in which case we don't want to mess up potential
 
90
// swaps $rX <-> $rY, i.e. do not create live range overlaps of phi src and def.
 
91
bool
 
92
CopyPropagation::visit(BasicBlock *bb)
 
93
{
 
94
   Instruction *mov, *si, *next;
 
95
 
 
96
   for (mov = bb->getEntry(); mov; mov = next) {
 
97
      next = mov->next;
 
98
      if (mov->op != OP_MOV || mov->fixed || !mov->getSrc(0)->asLValue())
 
99
         continue;
 
100
      si = mov->getSrc(0)->getInsn();
 
101
      if (mov->getDef(0)->reg.data.id < 0 && si && si->op != OP_PHI) {
 
102
         // propagate
 
103
         mov->def[0].replace(mov->getSrc(0), false);
 
104
         delete_Instruction(prog, mov);
 
105
      }
 
106
   }
 
107
   return true;
 
108
}
 
109
 
 
110
// =============================================================================
 
111
 
 
112
class LoadPropagation : public Pass
 
113
{
 
114
private:
 
115
   virtual bool visit(BasicBlock *);
 
116
 
 
117
   void checkSwapSrc01(Instruction *);
 
118
 
 
119
   bool isCSpaceLoad(Instruction *);
 
120
   bool isImmd32Load(Instruction *);
 
121
};
 
122
 
 
123
bool
 
124
LoadPropagation::isCSpaceLoad(Instruction *ld)
 
125
{
 
126
   return ld && ld->op == OP_LOAD && ld->src[0].getFile() == FILE_MEMORY_CONST;
 
127
}
 
128
 
 
129
bool
 
130
LoadPropagation::isImmd32Load(Instruction *ld)
 
131
{
 
132
   if (!ld || (ld->op != OP_MOV) || (typeSizeof(ld->dType) != 4))
 
133
      return false;
 
134
   return ld->src[0].getFile() == FILE_IMMEDIATE;
 
135
}
 
136
 
 
137
void
 
138
LoadPropagation::checkSwapSrc01(Instruction *insn)
 
139
{
 
140
   if (!prog->getTarget()->getOpInfo(insn).commutative)
 
141
      if (insn->op != OP_SET && insn->op != OP_SLCT)
 
142
         return;
 
143
   if (insn->src[1].getFile() != FILE_GPR)
 
144
      return;
 
145
 
 
146
   Instruction *i0 = insn->getSrc(0)->getInsn();
 
147
   Instruction *i1 = insn->getSrc(1)->getInsn();
 
148
 
 
149
   if (isCSpaceLoad(i0)) {
 
150
      if (!isCSpaceLoad(i1))
 
151
         insn->swapSources(0, 1);
 
152
      else
 
153
         return;
 
154
   } else
 
155
   if (isImmd32Load(i0)) {
 
156
      if (!isCSpaceLoad(i1) && !isImmd32Load(i1))
 
157
         insn->swapSources(0, 1);
 
158
      else
 
159
         return;
 
160
   } else {
 
161
      return;
 
162
   }
 
163
 
 
164
   if (insn->op == OP_SET)
 
165
      insn->asCmp()->setCond = reverseCondCode(insn->asCmp()->setCond);
 
166
   else
 
167
   if (insn->op == OP_SLCT)
 
168
      insn->asCmp()->setCond = inverseCondCode(insn->asCmp()->setCond);
 
169
}
 
170
 
 
171
bool
 
172
LoadPropagation::visit(BasicBlock *bb)
 
173
{
 
174
   const Target *targ = prog->getTarget();
 
175
   Instruction *next;
 
176
 
 
177
   for (Instruction *i = bb->getEntry(); i; i = next) {
 
178
      next = i->next;
 
179
 
 
180
      if (i->srcExists(1))
 
181
         checkSwapSrc01(i);
 
182
 
 
183
      for (int s = 0; i->srcExists(s); ++s) {
 
184
         Instruction *ld = i->getSrc(s)->getInsn();
 
185
 
 
186
         if (!ld || ld->fixed || (ld->op != OP_LOAD && ld->op != OP_MOV))
 
187
            continue;
 
188
         if (!targ->insnCanLoad(i, s, ld))
 
189
            continue;
 
190
 
 
191
         // propagate !
 
192
         i->setSrc(s, ld->getSrc(0));
 
193
         if (ld->src[0].isIndirect(0))
 
194
            i->setIndirect(s, 0, ld->getIndirect(0, 0));
 
195
 
 
196
         if (ld->getDef(0)->refCount() == 0)
 
197
            delete_Instruction(prog, ld);
 
198
      }
 
199
   }
 
200
   return true;
 
201
}
 
202
 
 
203
// =============================================================================
 
204
 
 
205
// Evaluate constant expressions.
 
206
class ConstantFolding : public Pass
 
207
{
 
208
public:
 
209
   bool foldAll(Program *);
 
210
 
 
211
private:
 
212
   virtual bool visit(BasicBlock *);
 
213
 
 
214
   void expr(Instruction *, ImmediateValue *, ImmediateValue *);
 
215
   void opnd(Instruction *, ImmediateValue *, int s);
 
216
 
 
217
   void unary(Instruction *, const ImmediateValue&);
 
218
 
 
219
   // TGSI 'true' is converted to -1 by F2I(NEG(SET)), track back to SET
 
220
   CmpInstruction *findOriginForTestWithZero(Value *);
 
221
 
 
222
   unsigned int foldCount;
 
223
 
 
224
   BuildUtil bld;
 
225
};
 
226
 
 
227
// TODO: remember generated immediates and only revisit these
 
228
bool
 
229
ConstantFolding::foldAll(Program *prog)
 
230
{
 
231
   unsigned int iterCount = 0;
 
232
   do {
 
233
      foldCount = 0;
 
234
      if (!run(prog))
 
235
         return false;
 
236
   } while (foldCount && ++iterCount < 2);
 
237
   return true;
 
238
}
 
239
 
 
240
bool
 
241
ConstantFolding::visit(BasicBlock *bb)
 
242
{
 
243
   Instruction *i, *next;
 
244
 
 
245
   for (i = bb->getEntry(); i; i = next) {
 
246
      next = i->next;
 
247
      if (i->op == OP_MOV) // continue early, MOV appears frequently
 
248
         continue;
 
249
 
 
250
      ImmediateValue *src0 = i->src[0].getImmediate();
 
251
      ImmediateValue *src1 = i->src[1].getImmediate();
 
252
 
 
253
      if (src0 && src1)
 
254
         expr(i, src0, src1);
 
255
      else
 
256
      if (src0)
 
257
         opnd(i, src0, 0);
 
258
      else
 
259
      if (src1)
 
260
         opnd(i, src1, 1);
 
261
   }
 
262
   return true;
 
263
}
 
264
 
 
265
CmpInstruction *
 
266
ConstantFolding::findOriginForTestWithZero(Value *value)
 
267
{
 
268
   if (!value)
 
269
      return NULL;
 
270
   Instruction *insn = value->getInsn();
 
271
 
 
272
   while (insn && insn->op != OP_SET) {
 
273
      Instruction *next = NULL;
 
274
      switch (insn->op) {
 
275
      case OP_NEG:
 
276
      case OP_ABS:
 
277
      case OP_CVT:
 
278
         next = insn->getSrc(0)->getInsn();
 
279
         if (insn->sType != next->dType)
 
280
            return NULL;
 
281
         break;
 
282
      case OP_MOV:
 
283
         next = insn->getSrc(0)->getInsn();
 
284
         break;
 
285
      default:
 
286
         return NULL;
 
287
      }
 
288
      insn = next;
 
289
   }
 
290
   return insn ? insn->asCmp() : NULL;
 
291
}
 
292
 
 
293
void
 
294
Modifier::applyTo(ImmediateValue& imm) const
 
295
{
 
296
   switch (imm.reg.type) {
 
297
   case TYPE_F32:
 
298
      if (bits & NV50_IR_MOD_ABS)
 
299
         imm.reg.data.f32 = fabsf(imm.reg.data.f32);
 
300
      if (bits & NV50_IR_MOD_NEG)
 
301
         imm.reg.data.f32 = -imm.reg.data.f32;
 
302
      if (bits & NV50_IR_MOD_SAT) {
 
303
         if (imm.reg.data.f32 < 0.0f)
 
304
            imm.reg.data.f32 = 0.0f;
 
305
         else
 
306
         if (imm.reg.data.f32 > 1.0f)
 
307
            imm.reg.data.f32 = 1.0f;
 
308
      }
 
309
      assert(!(bits & NV50_IR_MOD_NOT));
 
310
      break;
 
311
 
 
312
   case TYPE_S8: // NOTE: will be extended
 
313
   case TYPE_S16:
 
314
   case TYPE_S32:
 
315
   case TYPE_U8: // NOTE: treated as signed
 
316
   case TYPE_U16:
 
317
   case TYPE_U32:
 
318
      if (bits & NV50_IR_MOD_ABS)
 
319
         imm.reg.data.s32 = (imm.reg.data.s32 >= 0) ?
 
320
            imm.reg.data.s32 : -imm.reg.data.s32;
 
321
      if (bits & NV50_IR_MOD_NEG)
 
322
         imm.reg.data.s32 = -imm.reg.data.s32;
 
323
      if (bits & NV50_IR_MOD_NOT)
 
324
         imm.reg.data.s32 = ~imm.reg.data.s32;
 
325
      break;
 
326
 
 
327
   case TYPE_F64:
 
328
      if (bits & NV50_IR_MOD_ABS)
 
329
         imm.reg.data.f64 = fabs(imm.reg.data.f64);
 
330
      if (bits & NV50_IR_MOD_NEG)
 
331
         imm.reg.data.f64 = -imm.reg.data.f64;
 
332
      if (bits & NV50_IR_MOD_SAT) {
 
333
         if (imm.reg.data.f64 < 0.0)
 
334
            imm.reg.data.f64 = 0.0;
 
335
         else
 
336
         if (imm.reg.data.f64 > 1.0)
 
337
            imm.reg.data.f64 = 1.0;
 
338
      }
 
339
      assert(!(bits & NV50_IR_MOD_NOT));
 
340
      break;
 
341
 
 
342
   default:
 
343
      assert(!"invalid/unhandled type");
 
344
      imm.reg.data.u64 = 0;
 
345
      break;
 
346
   }
 
347
}
 
348
 
 
349
operation
 
350
Modifier::getOp() const
 
351
{
 
352
   switch (bits) {
 
353
   case NV50_IR_MOD_ABS: return OP_ABS;
 
354
   case NV50_IR_MOD_NEG: return OP_NEG;
 
355
   case NV50_IR_MOD_SAT: return OP_SAT;
 
356
   case NV50_IR_MOD_NOT: return OP_NOT;
 
357
   case 0:
 
358
      return OP_MOV;
 
359
   default:
 
360
      return OP_CVT;
 
361
   }
 
362
}
 
363
 
 
364
void
 
365
ConstantFolding::expr(Instruction *i,
 
366
                      ImmediateValue *src0, ImmediateValue *src1)
 
367
{
 
368
   ImmediateValue imm0(src0, i->sType);
 
369
   ImmediateValue imm1(src1, i->sType);
 
370
   struct Storage res;
 
371
   struct Storage *const a = &imm0.reg, *const b = &imm1.reg;
 
372
 
 
373
   i->src[0].mod.applyTo(imm0);
 
374
   i->src[1].mod.applyTo(imm1);
 
375
 
 
376
   switch (i->op) {
 
377
   case OP_MAD:
 
378
   case OP_FMA:
 
379
   case OP_MUL:
 
380
      if (i->dnz && i->dType == TYPE_F32) {
 
381
         if (!isfinite(a->data.f32))
 
382
            a->data.f32 = 0.0f;
 
383
         if (!isfinite(b->data.f32))
 
384
            b->data.f32 = 0.0f;
 
385
      }
 
386
      switch (i->dType) {
 
387
      case TYPE_F32: res.data.f32 = a->data.f32 * b->data.f32; break;
 
388
      case TYPE_F64: res.data.f64 = a->data.f64 * b->data.f64; break;
 
389
      case TYPE_S32:
 
390
      case TYPE_U32: res.data.u32 = a->data.u32 * b->data.u32; break;
 
391
      default:
 
392
         return;
 
393
      }
 
394
      break;
 
395
   case OP_DIV:
 
396
      if (b->data.u32 == 0)
 
397
         break;
 
398
      switch (i->dType) {
 
399
      case TYPE_F32: res.data.f32 = a->data.f32 / b->data.f32; break;
 
400
      case TYPE_F64: res.data.f64 = a->data.f64 / b->data.f64; break;
 
401
      case TYPE_S32: res.data.s32 = a->data.s32 / b->data.s32; break;
 
402
      case TYPE_U32: res.data.u32 = a->data.u32 / b->data.u32; break;
 
403
      default:
 
404
         return;
 
405
      }
 
406
      break;
 
407
   case OP_ADD:
 
408
      switch (i->dType) {
 
409
      case TYPE_F32: res.data.f32 = a->data.f32 + b->data.f32; break;
 
410
      case TYPE_F64: res.data.f64 = a->data.f64 + b->data.f64; break;
 
411
      case TYPE_S32:
 
412
      case TYPE_U32: res.data.u32 = a->data.u32 + b->data.u32; break;
 
413
      default:
 
414
         return;
 
415
      }
 
416
      break;
 
417
   case OP_POW:
 
418
      switch (i->dType) {
 
419
      case TYPE_F32: res.data.f32 = pow(a->data.f32, b->data.f32); break;
 
420
      case TYPE_F64: res.data.f64 = pow(a->data.f64, b->data.f64); break;
 
421
      default:
 
422
         return;
 
423
      }
 
424
      break;
 
425
   case OP_MAX:
 
426
      switch (i->dType) {
 
427
      case TYPE_F32: res.data.f32 = MAX2(a->data.f32, b->data.f32); break;
 
428
      case TYPE_F64: res.data.f64 = MAX2(a->data.f64, b->data.f64); break;
 
429
      case TYPE_S32: res.data.s32 = MAX2(a->data.s32, b->data.s32); break;
 
430
      case TYPE_U32: res.data.u32 = MAX2(a->data.u32, b->data.u32); break;
 
431
      default:
 
432
         return;
 
433
      }
 
434
      break;
 
435
   case OP_MIN:
 
436
      switch (i->dType) {
 
437
      case TYPE_F32: res.data.f32 = MIN2(a->data.f32, b->data.f32); break;
 
438
      case TYPE_F64: res.data.f64 = MIN2(a->data.f64, b->data.f64); break;
 
439
      case TYPE_S32: res.data.s32 = MIN2(a->data.s32, b->data.s32); break;
 
440
      case TYPE_U32: res.data.u32 = MIN2(a->data.u32, b->data.u32); break;
 
441
      default:
 
442
         return;
 
443
      }
 
444
      break;
 
445
   case OP_AND:
 
446
      res.data.u64 = a->data.u64 & b->data.u64;
 
447
      break;
 
448
   case OP_OR:
 
449
      res.data.u64 = a->data.u64 | b->data.u64;
 
450
      break;
 
451
   case OP_XOR:
 
452
      res.data.u64 = a->data.u64 ^ b->data.u64;
 
453
      break;
 
454
   case OP_SHL:
 
455
      res.data.u32 = a->data.u32 << b->data.u32;
 
456
      break;
 
457
   case OP_SHR:
 
458
      switch (i->dType) {
 
459
      case TYPE_S32: res.data.s32 = a->data.s32 >> b->data.u32; break;
 
460
      case TYPE_U32: res.data.u32 = a->data.u32 >> b->data.u32; break;
 
461
      default:
 
462
         return;
 
463
      }
 
464
      break;
 
465
   case OP_SLCT:
 
466
      if (a->data.u32 != b->data.u32)
 
467
         return;
 
468
      res.data.u32 = a->data.u32;
 
469
      break;
 
470
   default:
 
471
      return;
 
472
   }
 
473
   ++foldCount;
 
474
 
 
475
   i->src[0].mod = Modifier(0);
 
476
   i->src[1].mod = Modifier(0);
 
477
 
 
478
   i->setSrc(0, new_ImmediateValue(i->bb->getProgram(), res.data.u32));
 
479
   i->setSrc(1, NULL);
 
480
 
 
481
   i->getSrc(0)->reg.data = res.data;
 
482
 
 
483
   if (i->op == OP_MAD || i->op == OP_FMA) {
 
484
      i->op = OP_ADD;
 
485
 
 
486
      i->setSrc(1, i->getSrc(0));
 
487
      i->setSrc(0, i->getSrc(2));
 
488
      i->setSrc(2, NULL);
 
489
 
 
490
      i->src[1].mod = i->src[2].mod;
 
491
 
 
492
      src0 = i->src[0].getImmediate();
 
493
      if (src0)
 
494
         expr(i, src0, i->getSrc(1)->asImm());
 
495
   } else {
 
496
      i->op = OP_MOV;
 
497
   }
 
498
}
 
499
 
 
500
void
 
501
ConstantFolding::unary(Instruction *i, const ImmediateValue &imm)
 
502
{
 
503
   Storage res;
 
504
 
 
505
   if (i->dType != TYPE_F32)
 
506
      return;
 
507
   switch (i->op) {
 
508
   case OP_NEG: res.data.f32 = -imm.reg.data.f32; break;
 
509
   case OP_ABS: res.data.f32 = fabsf(imm.reg.data.f32); break;
 
510
   case OP_RCP: res.data.f32 = 1.0f / imm.reg.data.f32; break;
 
511
   case OP_RSQ: res.data.f32 = 1.0f / sqrtf(imm.reg.data.f32); break;
 
512
   case OP_LG2: res.data.f32 = log2f(imm.reg.data.f32); break;
 
513
   case OP_EX2: res.data.f32 = exp2f(imm.reg.data.f32); break;
 
514
   case OP_SIN: res.data.f32 = sinf(imm.reg.data.f32); break;
 
515
   case OP_COS: res.data.f32 = cosf(imm.reg.data.f32); break;
 
516
   case OP_SQRT: res.data.f32 = sqrtf(imm.reg.data.f32); break;
 
517
   case OP_PRESIN:
 
518
   case OP_PREEX2:
 
519
      // these should be handled in subsequent OP_SIN/COS/EX2
 
520
      res.data.f32 = imm.reg.data.f32;
 
521
      break;
 
522
   default:
 
523
      return;
 
524
   }
 
525
   i->op = OP_MOV;
 
526
   i->setSrc(0, new_ImmediateValue(i->bb->getProgram(), res.data.f32));
 
527
   i->src[0].mod = Modifier(0);
 
528
}
 
529
 
 
530
void
 
531
ConstantFolding::opnd(Instruction *i, ImmediateValue *src, int s)
 
532
{
 
533
   const int t = !s;
 
534
   const operation op = i->op;
 
535
 
 
536
   ImmediateValue imm(src, i->sType);
 
537
 
 
538
   i->src[s].mod.applyTo(imm);
 
539
 
 
540
   switch (i->op) {
 
541
   case OP_MUL:
 
542
      if (i->dType == TYPE_F32 && i->getSrc(t)->refCount() == 1) {
 
543
         Instruction *si = i->getSrc(t)->getUniqueInsn();
 
544
 
 
545
         if (si && si->op == OP_MUL) {
 
546
            float f = imm.reg.data.f32;
 
547
 
 
548
            if (si->src[1].getImmediate()) {
 
549
               f *= si->src[1].getImmediate()->reg.data.f32;
 
550
               si->setSrc(1, new_ImmediateValue(prog, f));
 
551
               i->def[0].replace(i->getSrc(t), false);
 
552
               break;
 
553
            } else {
 
554
               int fac;
 
555
               if (f == 0.125f) fac = -3;
 
556
               else
 
557
               if (f == 0.250f) fac = -2;
 
558
               else
 
559
               if (f == 0.500f) fac = -1;
 
560
               else
 
561
               if (f == 2.000f) fac = +1;
 
562
               else
 
563
               if (f == 4.000f) fac = +2;
 
564
               else
 
565
               if (f == 8.000f) fac = +3;
 
566
               else
 
567
                  fac = 0;
 
568
               if (fac) {
 
569
                  // FIXME: allowed & modifier
 
570
                  si->postFactor = fac;
 
571
                  i->def[0].replace(i->getSrc(t), false);
 
572
                  break;
 
573
               }
 
574
            }
 
575
         }
 
576
      }
 
577
      if (imm.isInteger(0)) {
 
578
         i->op = OP_MOV;
 
579
         i->setSrc(0, i->getSrc(s));
 
580
         i->setSrc(1, NULL);
 
581
      } else
 
582
      if (imm.isInteger(1) || imm.isInteger(-1)) {
 
583
         if (imm.isNegative())
 
584
            i->src[t].mod = i->src[t].mod ^ Modifier(NV50_IR_MOD_NEG);
 
585
         i->op = i->src[t].mod.getOp();
 
586
         if (s == 0) {
 
587
            i->setSrc(0, i->getSrc(1));
 
588
            i->src[0].mod = i->src[1].mod;
 
589
            i->src[1].mod = 0;
 
590
         }
 
591
         if (i->op != OP_CVT)
 
592
            i->src[0].mod = 0;
 
593
         i->setSrc(1, NULL);
 
594
      } else
 
595
      if (imm.isInteger(2) || imm.isInteger(-2)) {
 
596
         if (imm.isNegative())
 
597
            i->src[t].mod = i->src[t].mod ^ Modifier(NV50_IR_MOD_NEG);
 
598
         i->op = OP_ADD;
 
599
         i->setSrc(s, i->getSrc(t));
 
600
         i->src[s].mod = i->src[t].mod;
 
601
      } else
 
602
      if (!isFloatType(i->sType) && !imm.isNegative() && imm.isPow2()) {
 
603
         i->op = OP_SHL;
 
604
         imm.applyLog2();
 
605
         i->setSrc(1, new_ImmediateValue(prog, imm.reg.data.u32));
 
606
      }
 
607
      break;
 
608
   case OP_ADD:
 
609
      if (imm.isInteger(0)) {
 
610
         if (s == 0) {
 
611
            i->setSrc(0, i->getSrc(1));
 
612
            i->src[0].mod = i->src[1].mod;
 
613
         }
 
614
         i->setSrc(1, NULL);
 
615
         i->op = i->src[0].mod.getOp();
 
616
         if (i->op != OP_CVT)
 
617
            i->src[0].mod = Modifier(0);
 
618
      }
 
619
      break;
 
620
 
 
621
   case OP_DIV:
 
622
      if (s != 1 || (i->dType != TYPE_S32 && i->dType != TYPE_U32))
 
623
         break;
 
624
      bld.setPosition(i, false);
 
625
      if (imm.reg.data.u32 == 0) {
 
626
         break;
 
627
      } else
 
628
      if (imm.reg.data.u32 == 1) {
 
629
         i->op = OP_MOV;
 
630
         i->setSrc(1, NULL);
 
631
      } else
 
632
      if (i->dType == TYPE_U32 && imm.isPow2()) {
 
633
         i->op = OP_SHR;
 
634
         i->setSrc(1, bld.mkImm(util_logbase2(imm.reg.data.u32)));
 
635
      } else
 
636
      if (i->dType == TYPE_U32) {
 
637
         Instruction *mul;
 
638
         Value *tA, *tB;
 
639
         const uint32_t d = imm.reg.data.u32;
 
640
         uint32_t m;
 
641
         int r, s;
 
642
         uint32_t l = util_logbase2(d);
 
643
         if (((uint32_t)1 << l) < d)
 
644
            ++l;
 
645
         m = (((uint64_t)1 << 32) * (((uint64_t)1 << l) - d)) / d + 1;
 
646
         r = l ? 1 : 0;
 
647
         s = l ? (l - 1) : 0;
 
648
 
 
649
         tA = bld.getSSA();
 
650
         tB = bld.getSSA();
 
651
         mul = bld.mkOp2(OP_MUL, TYPE_U32, tA, i->getSrc(0),
 
652
                         bld.loadImm(NULL, m));
 
653
         mul->subOp = NV50_IR_SUBOP_MUL_HIGH;
 
654
         bld.mkOp2(OP_SUB, TYPE_U32, tB, i->getSrc(0), tA);
 
655
         tA = bld.getSSA();
 
656
         if (r)
 
657
            bld.mkOp2(OP_SHR, TYPE_U32, tA, tB, bld.mkImm(r));
 
658
         else
 
659
            tA = tB;
 
660
         tB = s ? bld.getSSA() : i->getDef(0);
 
661
         bld.mkOp2(OP_ADD, TYPE_U32, tB, mul->getDef(0), tA);
 
662
         if (s)
 
663
            bld.mkOp2(OP_SHR, TYPE_U32, i->getDef(0), tB, bld.mkImm(s));
 
664
 
 
665
         delete_Instruction(prog, i);
 
666
      } else
 
667
      if (imm.reg.data.s32 == -1) {
 
668
         i->op = OP_NEG;
 
669
         i->setSrc(1, NULL);
 
670
      } else {
 
671
         LValue *tA, *tB;
 
672
         LValue *tD;
 
673
         const int32_t d = imm.reg.data.s32;
 
674
         int32_t m;
 
675
         int32_t l = util_logbase2(static_cast<unsigned>(abs(d)));
 
676
         if ((1 << l) < abs(d))
 
677
            ++l;
 
678
         if (!l)
 
679
            l = 1;
 
680
         m = ((uint64_t)1 << (32 + l - 1)) / abs(d) + 1 - ((uint64_t)1 << 32);
 
681
 
 
682
         tA = bld.getSSA();
 
683
         tB = bld.getSSA();
 
684
         bld.mkOp3(OP_MAD, TYPE_S32, tA, i->getSrc(0), bld.loadImm(NULL, m),
 
685
                   i->getSrc(0))->subOp = NV50_IR_SUBOP_MUL_HIGH;
 
686
         if (l > 1)
 
687
            bld.mkOp2(OP_SHR, TYPE_S32, tB, tA, bld.mkImm(l - 1));
 
688
         else
 
689
            tB = tA;
 
690
         tA = bld.getSSA();
 
691
         bld.mkCmp(OP_SET, CC_LT, TYPE_S32, tA, i->getSrc(0), bld.mkImm(0));
 
692
         tD = (d < 0) ? bld.getSSA() : i->getDef(0)->asLValue();
 
693
         bld.mkOp2(OP_SUB, TYPE_U32, tD, tB, tA);
 
694
         if (d < 0)
 
695
            bld.mkOp1(OP_NEG, TYPE_S32, i->getDef(0), tB);
 
696
 
 
697
         delete_Instruction(prog, i);
 
698
      }
 
699
      break;
 
700
 
 
701
   case OP_MOD:
 
702
      if (i->sType == TYPE_U32 && imm.isPow2()) {
 
703
         bld.setPosition(i, false);
 
704
         i->op = OP_AND;
 
705
         i->setSrc(1, bld.loadImm(NULL, imm.reg.data.u32 - 1));
 
706
      }
 
707
      break;
 
708
 
 
709
   case OP_SET: // TODO: SET_AND,OR,XOR
 
710
   {
 
711
      CmpInstruction *si = findOriginForTestWithZero(i->getSrc(t));
 
712
      CondCode cc, ccZ;
 
713
      if (i->src[t].mod != Modifier(0))
 
714
         return;
 
715
      if (imm.reg.data.u32 != 0 || !si || si->op != OP_SET)
 
716
         return;
 
717
      cc = si->setCond;
 
718
      ccZ = (CondCode)((unsigned int)i->asCmp()->setCond & ~CC_U);
 
719
      if (s == 0)
 
720
         ccZ = reverseCondCode(ccZ);
 
721
      switch (ccZ) {
 
722
      case CC_LT: cc = CC_FL; break;
 
723
      case CC_GE: cc = CC_TR; break;
 
724
      case CC_EQ: cc = inverseCondCode(cc); break;
 
725
      case CC_LE: cc = inverseCondCode(cc); break;
 
726
      case CC_GT: break;
 
727
      case CC_NE: break;
 
728
      default:
 
729
         return;
 
730
      }
 
731
      i->asCmp()->setCond = cc;
 
732
      i->setSrc(0, si->src[0]);
 
733
      i->setSrc(1, si->src[1]);
 
734
      i->sType = si->sType;
 
735
   }
 
736
      break;
 
737
 
 
738
   case OP_SHL:
 
739
   {
 
740
      if (s != 1 || i->src[0].mod != Modifier(0))
 
741
         break;
 
742
      // try to concatenate shifts
 
743
      Instruction *si = i->getSrc(0)->getInsn();
 
744
      if (!si ||
 
745
          si->op != OP_SHL || si->src[1].mod != Modifier(0))
 
746
         break;
 
747
      ImmediateValue *siImm = si->src[1].getImmediate();
 
748
      if (siImm) {
 
749
         bld.setPosition(i, false);
 
750
         i->setSrc(0, si->getSrc(0));
 
751
         i->setSrc(1, bld.loadImm(NULL,
 
752
                                  imm.reg.data.u32 + siImm->reg.data.u32));
 
753
      }
 
754
   }
 
755
      break;
 
756
 
 
757
   case OP_ABS:
 
758
   case OP_NEG:
 
759
   case OP_LG2:
 
760
   case OP_RCP:
 
761
   case OP_SQRT:
 
762
   case OP_RSQ:
 
763
   case OP_PRESIN:
 
764
   case OP_SIN:
 
765
   case OP_COS:
 
766
   case OP_PREEX2:
 
767
   case OP_EX2:
 
768
      unary(i, imm);
 
769
      break;
 
770
   default:
 
771
      return;
 
772
   }
 
773
   if (i->op != op)
 
774
      foldCount++;
 
775
}
 
776
 
 
777
// =============================================================================
 
778
 
 
779
// Merge modifier operations (ABS, NEG, NOT) into ValueRefs where allowed.
 
780
class ModifierFolding : public Pass
 
781
{
 
782
private:
 
783
   virtual bool visit(BasicBlock *);
 
784
};
 
785
 
 
786
bool
 
787
ModifierFolding::visit(BasicBlock *bb)
 
788
{
 
789
   const Target *target = prog->getTarget();
 
790
 
 
791
   Instruction *i, *next, *mi;
 
792
   Modifier mod;
 
793
 
 
794
   for (i = bb->getEntry(); i; i = next) {
 
795
      next = i->next;
 
796
 
 
797
      if (0 && i->op == OP_SUB) {
 
798
         // turn "sub" into "add neg" (do we really want this ?)
 
799
         i->op = OP_ADD;
 
800
         i->src[0].mod = i->src[0].mod ^ Modifier(NV50_IR_MOD_NEG);
 
801
      }
 
802
 
 
803
      for (int s = 0; s < 3 && i->srcExists(s); ++s) {
 
804
         mi = i->getSrc(s)->getInsn();
 
805
         if (!mi ||
 
806
             mi->predSrc >= 0 || mi->getDef(0)->refCount() > 8)
 
807
            continue;
 
808
         if (i->sType == TYPE_U32 && mi->dType == TYPE_S32) {
 
809
            if ((i->op != OP_ADD &&
 
810
                 i->op != OP_MUL) ||
 
811
                (mi->op != OP_ABS &&
 
812
                 mi->op != OP_NEG))
 
813
               continue;
 
814
         } else
 
815
         if (i->sType != mi->dType) {
 
816
            continue;
 
817
         }
 
818
         if ((mod = Modifier(mi->op)) == Modifier(0))
 
819
            continue;
 
820
         mod = mod * mi->src[0].mod;
 
821
 
 
822
         if ((i->op == OP_ABS) || i->src[s].mod.abs()) {
 
823
            // abs neg [abs] = abs
 
824
            mod = mod & Modifier(~(NV50_IR_MOD_NEG | NV50_IR_MOD_ABS));
 
825
         } else
 
826
         if ((i->op == OP_NEG) && mod.neg()) {
 
827
            assert(s == 0);
 
828
            // neg as both opcode and modifier on same insn is prohibited
 
829
            // neg neg abs = abs, neg neg = identity
 
830
            mod = mod & Modifier(~NV50_IR_MOD_NEG);
 
831
            i->op = mod.getOp();
 
832
            mod = mod & Modifier(~NV50_IR_MOD_ABS);
 
833
            if (mod == Modifier(0))
 
834
               i->op = OP_MOV;
 
835
         }
 
836
 
 
837
         if (target->isModSupported(i, s, mod)) {
 
838
            i->setSrc(s, mi->getSrc(0));
 
839
            i->src[s].mod = i->src[s].mod * mod;
 
840
         }
 
841
      }
 
842
 
 
843
      if (i->op == OP_SAT) {
 
844
         mi = i->getSrc(0)->getInsn();
 
845
         if (mi &&
 
846
             mi->getDef(0)->refCount() <= 1 && target->isSatSupported(mi)) {
 
847
            mi->saturate = 1;
 
848
            mi->setDef(0, i->getDef(0));
 
849
            delete_Instruction(prog, i);
 
850
         }
 
851
      }
 
852
   }
 
853
 
 
854
   return true;
 
855
}
 
856
 
 
857
// =============================================================================
 
858
 
 
859
// MUL + ADD -> MAD/FMA
 
860
// MIN/MAX(a, a) -> a, etc.
 
861
// SLCT(a, b, const) -> cc(const) ? a : b
 
862
// RCP(RCP(a)) -> a
 
863
// MUL(MUL(a, b), const) -> MUL_Xconst(a, b)
 
864
class AlgebraicOpt : public Pass
 
865
{
 
866
private:
 
867
   virtual bool visit(BasicBlock *);
 
868
 
 
869
   void handleADD(Instruction *);
 
870
   void handleMINMAX(Instruction *);
 
871
   void handleRCP(Instruction *);
 
872
   void handleSLCT(Instruction *);
 
873
   void handleLOGOP(Instruction *);
 
874
   void handleCVT(Instruction *);
 
875
};
 
876
 
 
877
void
 
878
AlgebraicOpt::handleADD(Instruction *add)
 
879
{
 
880
   Value *src0 = add->getSrc(0);
 
881
   Value *src1 = add->getSrc(1);
 
882
   Value *src;
 
883
   int s;
 
884
   Modifier mod[4];
 
885
 
 
886
   if (!prog->getTarget()->isOpSupported(OP_MAD, add->dType))
 
887
      return;
 
888
 
 
889
   if (src0->reg.file != FILE_GPR || src1->reg.file != FILE_GPR)
 
890
      return;
 
891
 
 
892
   if (src0->refCount() == 1 &&
 
893
       src0->getUniqueInsn() && src0->getUniqueInsn()->op == OP_MUL)
 
894
      s = 0;
 
895
   else
 
896
   if (src1->refCount() == 1 &&
 
897
       src1->getUniqueInsn() && src1->getUniqueInsn()->op == OP_MUL)
 
898
      s = 1;
 
899
   else
 
900
      return;
 
901
 
 
902
   if ((src0->getUniqueInsn() && src0->getUniqueInsn()->bb != add->bb) ||
 
903
       (src1->getUniqueInsn() && src1->getUniqueInsn()->bb != add->bb))
 
904
      return;
 
905
 
 
906
   src = add->getSrc(s);
 
907
 
 
908
   mod[0] = add->src[0].mod;
 
909
   mod[1] = add->src[1].mod;
 
910
   mod[2] = src->getUniqueInsn()->src[0].mod;
 
911
   mod[3] = src->getUniqueInsn()->src[1].mod;
 
912
 
 
913
   if (((mod[0] | mod[1]) | (mod[2] | mod[3])) & Modifier(~NV50_IR_MOD_NEG))
 
914
      return;
 
915
 
 
916
   add->op = OP_MAD;
 
917
   add->subOp = src->getInsn()->subOp; // potentially mul-high
 
918
 
 
919
   add->setSrc(2, add->src[s ? 0 : 1]);
 
920
 
 
921
   add->setSrc(0, src->getInsn()->getSrc(0));
 
922
   add->src[0].mod = mod[2] ^ mod[s];
 
923
   add->setSrc(1, src->getInsn()->getSrc(1));
 
924
   add->src[1].mod = mod[3];
 
925
}
 
926
 
 
927
void
 
928
AlgebraicOpt::handleMINMAX(Instruction *minmax)
 
929
{
 
930
   Value *src0 = minmax->getSrc(0);
 
931
   Value *src1 = minmax->getSrc(1);
 
932
 
 
933
   if (src0 != src1 || src0->reg.file != FILE_GPR)
 
934
      return;
 
935
   if (minmax->src[0].mod == minmax->src[1].mod) {
 
936
      if (minmax->src[0].mod) {
 
937
         minmax->op = OP_CVT;
 
938
         minmax->setSrc(1, NULL);
 
939
      } else {
 
940
         minmax->def[0].replace(minmax->getSrc(0), false);
 
941
         minmax->bb->remove(minmax);
 
942
      }
 
943
   } else {
 
944
      // TODO:
 
945
      // min(x, -x) = -abs(x)
 
946
      // min(x, -abs(x)) = -abs(x)
 
947
      // min(x, abs(x)) = x
 
948
      // max(x, -abs(x)) = x
 
949
      // max(x, abs(x)) = abs(x)
 
950
      // max(x, -x) = abs(x)
 
951
   }
 
952
}
 
953
 
 
954
void
 
955
AlgebraicOpt::handleRCP(Instruction *rcp)
 
956
{
 
957
   Instruction *si = rcp->getSrc(0)->getUniqueInsn();
 
958
 
 
959
   if (si && si->op == OP_RCP) {
 
960
      Modifier mod = rcp->src[0].mod * si->src[0].mod;
 
961
      rcp->op = mod.getOp();
 
962
      rcp->setSrc(0, si->getSrc(0));
 
963
   }
 
964
}
 
965
 
 
966
void
 
967
AlgebraicOpt::handleSLCT(Instruction *slct)
 
968
{
 
969
   if (slct->getSrc(2)->reg.file == FILE_IMMEDIATE) {
 
970
      if (slct->getSrc(2)->asImm()->compare(slct->asCmp()->setCond, 0.0f))
 
971
         slct->setSrc(0, slct->getSrc(1));
 
972
   } else
 
973
   if (slct->getSrc(0) != slct->getSrc(1)) {
 
974
      return;
 
975
   }
 
976
   slct->op = OP_MOV;
 
977
   slct->setSrc(1, NULL);
 
978
   slct->setSrc(2, NULL);
 
979
}
 
980
 
 
981
void
 
982
AlgebraicOpt::handleLOGOP(Instruction *logop)
 
983
{
 
984
   Value *src0 = logop->getSrc(0);
 
985
   Value *src1 = logop->getSrc(1);
 
986
 
 
987
   if (src0->reg.file != FILE_GPR || src1->reg.file != FILE_GPR)
 
988
      return;
 
989
 
 
990
   if (src0 == src1) {
 
991
      if (logop->src[0].mod != Modifier(0) ||
 
992
          logop->src[1].mod != Modifier(0))
 
993
         return;
 
994
      if (logop->op == OP_AND || logop->op == OP_OR) {
 
995
         logop->def[0].replace(logop->getSrc(0), false);
 
996
         delete_Instruction(prog, logop);
 
997
      }
 
998
   } else {
 
999
      // try AND(SET, SET) -> SET_AND(SET)
 
1000
      Instruction *set0 = src0->getInsn();
 
1001
      Instruction *set1 = src1->getInsn();
 
1002
 
 
1003
      if (!set0 || set0->fixed || !set1 || set1->fixed)
 
1004
         return;
 
1005
      if (set1->op != OP_SET) {
 
1006
         Instruction *xchg = set0;
 
1007
         set0 = set1;
 
1008
         set1 = xchg;
 
1009
         if (set1->op != OP_SET)
 
1010
            return;
 
1011
      }
 
1012
      if (set0->op != OP_SET &&
 
1013
          set0->op != OP_SET_AND &&
 
1014
          set0->op != OP_SET_OR &&
 
1015
          set0->op != OP_SET_XOR)
 
1016
         return;
 
1017
      if (set0->getDef(0)->refCount() > 1 &&
 
1018
          set1->getDef(0)->refCount() > 1)
 
1019
         return;
 
1020
      if (set0->getPredicate() || set1->getPredicate())
 
1021
         return;
 
1022
      // check that they don't source each other
 
1023
      for (int s = 0; s < 2; ++s)
 
1024
         if (set0->getSrc(s) == set1->getDef(0) ||
 
1025
             set1->getSrc(s) == set0->getDef(0))
 
1026
            return;
 
1027
 
 
1028
      set0 = set0->clone(true);
 
1029
      set1 = set1->clone(false);
 
1030
      logop->bb->insertAfter(logop, set1);
 
1031
      logop->bb->insertAfter(logop, set0);
 
1032
 
 
1033
      set0->dType = TYPE_U8;
 
1034
      set0->getDef(0)->reg.file = FILE_PREDICATE;
 
1035
      set0->getDef(0)->reg.size = 1;
 
1036
      set1->setSrc(2, set0->getDef(0));
 
1037
      switch (logop->op) {
 
1038
      case OP_AND: set1->op = OP_SET_AND; break;
 
1039
      case OP_OR:  set1->op = OP_SET_OR; break;
 
1040
      case OP_XOR: set1->op = OP_SET_XOR; break;
 
1041
      default:
 
1042
         assert(0);
 
1043
         break;
 
1044
      }
 
1045
      set1->setDef(0, logop->getDef(0));
 
1046
      delete_Instruction(prog, logop);
 
1047
   }
 
1048
}
 
1049
 
 
1050
// F2I(NEG(SET with result 1.0f/0.0f)) -> SET with result -1/0
 
1051
void
 
1052
AlgebraicOpt::handleCVT(Instruction *cvt)
 
1053
{
 
1054
   if (cvt->sType != TYPE_F32 ||
 
1055
       cvt->dType != TYPE_S32 || cvt->src[0].mod != Modifier(0))
 
1056
      return;
 
1057
   Instruction *insn = cvt->getSrc(0)->getInsn();
 
1058
   if (!insn || insn->op != OP_NEG || insn->dType != TYPE_F32)
 
1059
      return;
 
1060
   if (insn->src[0].mod != Modifier(0))
 
1061
      return;
 
1062
   insn = insn->getSrc(0)->getInsn();
 
1063
   if (!insn || insn->op != OP_SET || insn->dType != TYPE_F32)
 
1064
      return;
 
1065
 
 
1066
   Instruction *bset = insn->clone(false);
 
1067
   bset->dType = TYPE_U32;
 
1068
   bset->setDef(0, cvt->getDef(0));
 
1069
   cvt->bb->insertAfter(cvt, bset);
 
1070
   delete_Instruction(prog, cvt);
 
1071
}
 
1072
 
 
1073
bool
 
1074
AlgebraicOpt::visit(BasicBlock *bb)
 
1075
{
 
1076
   Instruction *next;
 
1077
   for (Instruction *i = bb->getEntry(); i; i = next) {
 
1078
      next = i->next;
 
1079
      switch (i->op) {
 
1080
      case OP_ADD:
 
1081
         handleADD(i);
 
1082
         break;
 
1083
      case OP_RCP:
 
1084
         handleRCP(i);
 
1085
         break;
 
1086
      case OP_MIN:
 
1087
      case OP_MAX:
 
1088
         handleMINMAX(i);
 
1089
         break;
 
1090
      case OP_SLCT:
 
1091
         handleSLCT(i);
 
1092
         break;
 
1093
      case OP_AND:
 
1094
      case OP_OR:
 
1095
      case OP_XOR:
 
1096
         handleLOGOP(i);
 
1097
         break;
 
1098
      case OP_CVT:
 
1099
         handleCVT(i);
 
1100
         break;
 
1101
      default:
 
1102
         break;
 
1103
      }
 
1104
   }
 
1105
 
 
1106
   return true;
 
1107
}
 
1108
 
 
1109
// =============================================================================
 
1110
 
 
1111
static inline void
 
1112
updateLdStOffset(Instruction *ldst, int32_t offset, Function *fn)
 
1113
{
 
1114
   if (offset != ldst->getSrc(0)->reg.data.offset) {
 
1115
      if (ldst->getSrc(0)->refCount() > 1)
 
1116
         ldst->setSrc(0, ldst->getSrc(0)->clone(fn));
 
1117
      ldst->getSrc(0)->reg.data.offset = offset;
 
1118
   }
 
1119
}
 
1120
 
 
1121
// Combine loads and stores, forward stores to loads where possible.
 
1122
class MemoryOpt : public Pass
 
1123
{
 
1124
private:
 
1125
   class Record
 
1126
   {
 
1127
   public:
 
1128
      Record *next;
 
1129
      Instruction *insn;
 
1130
      const Value *rel[2];
 
1131
      const Value *base;
 
1132
      int32_t offset;
 
1133
      int8_t fileIndex;
 
1134
      uint8_t size;
 
1135
      bool locked;
 
1136
      Record *prev;
 
1137
 
 
1138
      bool overlaps(const Instruction *ldst) const;
 
1139
 
 
1140
      inline void link(Record **);
 
1141
      inline void unlink(Record **);
 
1142
      inline void set(const Instruction *ldst);
 
1143
   };
 
1144
 
 
1145
public:
 
1146
   MemoryOpt();
 
1147
 
 
1148
   Record *loads[DATA_FILE_COUNT];
 
1149
   Record *stores[DATA_FILE_COUNT];
 
1150
 
 
1151
   MemoryPool recordPool;
 
1152
 
 
1153
private:
 
1154
   virtual bool visit(BasicBlock *);
 
1155
   bool runOpt(BasicBlock *);
 
1156
 
 
1157
   Record **getList(const Instruction *);
 
1158
 
 
1159
   Record *findRecord(const Instruction *, bool load, bool& isAdjacent) const;
 
1160
 
 
1161
   // merge @insn into load/store instruction from @rec
 
1162
   bool combineLd(Record *rec, Instruction *ld);
 
1163
   bool combineSt(Record *rec, Instruction *st);
 
1164
 
 
1165
   bool replaceLdFromLd(Instruction *ld, Record *ldRec);
 
1166
   bool replaceLdFromSt(Instruction *ld, Record *stRec);
 
1167
   bool replaceStFromSt(Instruction *restrict st, Record *stRec);
 
1168
 
 
1169
   void addRecord(Instruction *ldst);
 
1170
   void purgeRecords(Instruction *const st, DataFile);
 
1171
   void lockStores(Instruction *const ld);
 
1172
   void reset();
 
1173
 
 
1174
private:
 
1175
   Record *prevRecord;
 
1176
};
 
1177
 
 
1178
MemoryOpt::MemoryOpt() : recordPool(sizeof(MemoryOpt::Record), 6)
 
1179
{
 
1180
   for (int i = 0; i < DATA_FILE_COUNT; ++i) {
 
1181
      loads[i] = NULL;
 
1182
      stores[i] = NULL;
 
1183
   }
 
1184
   prevRecord = NULL;
 
1185
}
 
1186
 
 
1187
void
 
1188
MemoryOpt::reset()
 
1189
{
 
1190
   for (unsigned int i = 0; i < DATA_FILE_COUNT; ++i) {
 
1191
      Record *it, *next;
 
1192
      for (it = loads[i]; it; it = next) {
 
1193
         next = it->next;
 
1194
         recordPool.release(it);
 
1195
      }
 
1196
      loads[i] = NULL;
 
1197
      for (it = stores[i]; it; it = next) {
 
1198
         next = it->next;
 
1199
         recordPool.release(it);
 
1200
      }
 
1201
      stores[i] = NULL;
 
1202
   }
 
1203
}
 
1204
 
 
1205
bool
 
1206
MemoryOpt::combineLd(Record *rec, Instruction *ld)
 
1207
{
 
1208
   int32_t offRc = rec->offset;
 
1209
   int32_t offLd = ld->getSrc(0)->reg.data.offset;
 
1210
   int sizeRc = rec->size;
 
1211
   int sizeLd = typeSizeof(ld->dType);
 
1212
   int size = sizeRc + sizeLd;
 
1213
   int d, j;
 
1214
 
 
1215
   // only VFETCH can do a 96 byte load
 
1216
   if (ld->op != OP_VFETCH && size == 12)
 
1217
      return false;
 
1218
   // no unaligned loads
 
1219
   if (((size == 0x8) && (MIN2(offLd, offRc) & 0x7)) ||
 
1220
       ((size == 0xc) && (MIN2(offLd, offRc) & 0xf)))
 
1221
      return false;
 
1222
 
 
1223
   assert(sizeRc + sizeLd <= 16 && offRc != offLd);
 
1224
 
 
1225
   for (j = 0; sizeRc; sizeRc -= rec->insn->getDef(j)->reg.size, ++j);
 
1226
 
 
1227
   if (offLd < offRc) {
 
1228
      int sz;
 
1229
      for (sz = 0, d = 0; sz < sizeLd; sz += ld->getDef(d)->reg.size, ++d);
 
1230
      // d: nr of definitions in ld
 
1231
      // j: nr of definitions in rec->insn, move:
 
1232
      for (d = d + j - 1; j > 0; --j, --d)
 
1233
         rec->insn->setDef(d, rec->insn->getDef(j - 1));
 
1234
 
 
1235
      if (rec->insn->getSrc(0)->refCount() > 1)
 
1236
         rec->insn->setSrc(0, rec->insn->getSrc(0)->clone(func));
 
1237
      rec->offset = rec->insn->getSrc(0)->reg.data.offset = offLd;
 
1238
 
 
1239
      d = 0;
 
1240
   } else {
 
1241
      d = j;
 
1242
   }
 
1243
   // move definitions of @ld to @rec->insn
 
1244
   for (j = 0; sizeLd; ++j, ++d) {
 
1245
      sizeLd -= ld->getDef(j)->reg.size;
 
1246
      rec->insn->setDef(d, ld->getDef(j));
 
1247
   }
 
1248
 
 
1249
   rec->size = size;
 
1250
   rec->insn->setType(typeOfSize(size));
 
1251
 
 
1252
   delete_Instruction(prog, ld);
 
1253
 
 
1254
   return true;
 
1255
}
 
1256
 
 
1257
bool
 
1258
MemoryOpt::combineSt(Record *rec, Instruction *st)
 
1259
{
 
1260
   int32_t offRc = rec->offset;
 
1261
   int32_t offSt = st->getSrc(0)->reg.data.offset;
 
1262
   int sizeRc = rec->size;
 
1263
   int sizeSt = typeSizeof(st->dType);
 
1264
   int s = sizeSt / 4;
 
1265
   int size = sizeRc + sizeSt;
 
1266
   int j, k;
 
1267
   Value *src[4]; // no modifiers in ValueRef allowed for st
 
1268
   Value *extra[3];
 
1269
 
 
1270
   if (size == 12) // XXX: check if EXPORT a[] can do this after all
 
1271
      return false;
 
1272
   if (size == 8 && MIN2(offRc, offSt) & 0x7)
 
1273
      return false;
 
1274
 
 
1275
   st->takeExtraSources(0, extra); // save predicate and indirect address
 
1276
 
 
1277
   if (offRc < offSt) {
 
1278
      // save values from @st
 
1279
      for (s = 0; sizeSt; ++s) {
 
1280
         sizeSt -= st->getSrc(s + 1)->reg.size;
 
1281
         src[s] = st->getSrc(s + 1);
 
1282
      }
 
1283
      // set record's values as low sources of @st
 
1284
      for (j = 1; sizeRc; ++j) {
 
1285
         sizeRc -= st->getSrc(j)->reg.size;
 
1286
         st->setSrc(j, rec->insn->getSrc(j));
 
1287
      }
 
1288
      // set saved values as high sources of @st
 
1289
      for (k = j, j = 0; j < s; ++j)
 
1290
         st->setSrc(k++, src[j]);
 
1291
 
 
1292
      updateLdStOffset(st, offRc, func);
 
1293
   } else {
 
1294
      for (j = 1; sizeSt; ++j)
 
1295
         sizeSt -= st->getSrc(j)->reg.size;
 
1296
      for (s = 1; sizeRc; ++j, ++s) {
 
1297
         sizeRc -= rec->insn->getSrc(s)->reg.size;
 
1298
         st->setSrc(j, rec->insn->getSrc(s));
 
1299
      }
 
1300
      rec->offset = offSt;
 
1301
   }
 
1302
   st->putExtraSources(0, extra); // restore pointer and predicate
 
1303
 
 
1304
   delete_Instruction(prog, rec->insn);
 
1305
   rec->insn = st;
 
1306
   rec->size = size;
 
1307
   rec->insn->setType(typeOfSize(size));
 
1308
   return true;
 
1309
}
 
1310
 
 
1311
void
 
1312
MemoryOpt::Record::set(const Instruction *ldst)
 
1313
{
 
1314
   const Symbol *mem = ldst->getSrc(0)->asSym();
 
1315
   fileIndex = mem->reg.fileIndex;
 
1316
   rel[0] = ldst->getIndirect(0, 0);
 
1317
   rel[1] = ldst->getIndirect(0, 1);
 
1318
   offset = mem->reg.data.offset;
 
1319
   base = mem->getBase();
 
1320
   size = typeSizeof(ldst->sType);
 
1321
}
 
1322
 
 
1323
void
 
1324
MemoryOpt::Record::link(Record **list)
 
1325
{
 
1326
   next = *list;
 
1327
   if (next)
 
1328
      next->prev = this;
 
1329
   prev = NULL;
 
1330
   *list = this;
 
1331
}
 
1332
 
 
1333
void
 
1334
MemoryOpt::Record::unlink(Record **list)
 
1335
{
 
1336
   if (next)
 
1337
      next->prev = prev;
 
1338
   if (prev)
 
1339
      prev->next = next;
 
1340
   else
 
1341
      *list = next;
 
1342
}
 
1343
 
 
1344
MemoryOpt::Record **
 
1345
MemoryOpt::getList(const Instruction *insn)
 
1346
{
 
1347
   if (insn->op == OP_LOAD || insn->op == OP_VFETCH)
 
1348
      return &loads[insn->src[0].getFile()];
 
1349
   return &stores[insn->src[0].getFile()];
 
1350
}
 
1351
 
 
1352
void
 
1353
MemoryOpt::addRecord(Instruction *i)
 
1354
{
 
1355
   Record **list = getList(i);
 
1356
   Record *it = reinterpret_cast<Record *>(recordPool.allocate());
 
1357
 
 
1358
   it->link(list);
 
1359
   it->set(i);
 
1360
   it->insn = i;
 
1361
   it->locked = false;
 
1362
}
 
1363
 
 
1364
MemoryOpt::Record *
 
1365
MemoryOpt::findRecord(const Instruction *insn, bool load, bool& isAdj) const
 
1366
{
 
1367
   const Symbol *sym = insn->getSrc(0)->asSym();
 
1368
   const int size = typeSizeof(insn->sType);
 
1369
   Record *rec = NULL;
 
1370
   Record *it = load ? loads[sym->reg.file] : stores[sym->reg.file];
 
1371
 
 
1372
   for (; it; it = it->next) {
 
1373
      if (it->locked && insn->op != OP_LOAD)
 
1374
         continue;
 
1375
      if ((it->offset >> 4) != (sym->reg.data.offset >> 4) ||
 
1376
          it->rel[0] != insn->getIndirect(0, 0) ||
 
1377
          it->fileIndex != sym->reg.fileIndex ||
 
1378
          it->rel[1] != insn->getIndirect(0, 1))
 
1379
         continue;
 
1380
 
 
1381
      if (it->offset < sym->reg.data.offset) {
 
1382
         if (it->offset + it->size >= sym->reg.data.offset) {
 
1383
            isAdj = (it->offset + it->size == sym->reg.data.offset);
 
1384
            if (!isAdj)
 
1385
               return it;
 
1386
            if (!(it->offset & 0x7))
 
1387
               rec = it;
 
1388
         }
 
1389
      } else {
 
1390
         isAdj = it->offset != sym->reg.data.offset;
 
1391
         if (size <= it->size && !isAdj)
 
1392
            return it;
 
1393
         else
 
1394
         if (!(sym->reg.data.offset & 0x7))
 
1395
            if (it->offset - size <= sym->reg.data.offset)
 
1396
               rec = it;
 
1397
      }
 
1398
   }
 
1399
   return rec;
 
1400
}
 
1401
 
 
1402
bool
 
1403
MemoryOpt::replaceLdFromSt(Instruction *ld, Record *rec)
 
1404
{
 
1405
   Instruction *st = rec->insn;
 
1406
   int32_t offSt = rec->offset;
 
1407
   int32_t offLd = ld->getSrc(0)->reg.data.offset;
 
1408
   int d, s;
 
1409
 
 
1410
   for (s = 1; offSt != offLd && st->srcExists(s); ++s)
 
1411
      offSt += st->getSrc(s)->reg.size;
 
1412
   if (offSt != offLd)
 
1413
      return false;
 
1414
 
 
1415
   for (d = 0; ld->defExists(d) && st->srcExists(s); ++d, ++s) {
 
1416
      if (ld->getDef(d)->reg.size != st->getSrc(s)->reg.size)
 
1417
         return false;
 
1418
      if (st->getSrc(s)->reg.file != FILE_GPR)
 
1419
         return false;
 
1420
      ld->def[d].replace(st->getSrc(s), false);
 
1421
   }
 
1422
   ld->bb->remove(ld);
 
1423
   return true;
 
1424
}
 
1425
 
 
1426
bool
 
1427
MemoryOpt::replaceLdFromLd(Instruction *ldE, Record *rec)
 
1428
{
 
1429
   Instruction *ldR = rec->insn;
 
1430
   int32_t offR = rec->offset;
 
1431
   int32_t offE = ldE->getSrc(0)->reg.data.offset;
 
1432
   int dR, dE;
 
1433
 
 
1434
   assert(offR <= offE);
 
1435
   for (dR = 0; offR < offE && ldR->defExists(dR); ++dR)
 
1436
      offR += ldR->getDef(dR)->reg.size;
 
1437
   if (offR != offE)
 
1438
      return false;
 
1439
 
 
1440
   for (dE = 0; ldE->defExists(dE) && ldR->defExists(dR); ++dE, ++dR) {
 
1441
      if (ldE->getDef(dE)->reg.size != ldR->getDef(dR)->reg.size)
 
1442
         return false;
 
1443
      ldE->def[dE].replace(ldR->getDef(dR), false);
 
1444
   }
 
1445
 
 
1446
   delete_Instruction(prog, ldE);
 
1447
   return true;
 
1448
}
 
1449
 
 
1450
bool
 
1451
MemoryOpt::replaceStFromSt(Instruction *restrict st, Record *rec)
 
1452
{
 
1453
   const Instruction *const ri = rec->insn;
 
1454
   Value *extra[3];
 
1455
 
 
1456
   int32_t offS = st->getSrc(0)->reg.data.offset;
 
1457
   int32_t offR = rec->offset;
 
1458
   int32_t endS = offS + typeSizeof(st->dType);
 
1459
   int32_t endR = offR + typeSizeof(ri->dType);
 
1460
 
 
1461
   rec->size = MAX2(endS, endR) - MIN2(offS, offR);
 
1462
 
 
1463
   st->takeExtraSources(0, extra);
 
1464
 
 
1465
   if (offR < offS) {
 
1466
      Value *vals[4];
 
1467
      int s, n;
 
1468
      int k = 0;
 
1469
      // get non-replaced sources of ri
 
1470
      for (s = 1; offR < offS; offR += ri->getSrc(s)->reg.size, ++s)
 
1471
         vals[k++] = ri->getSrc(s);
 
1472
      n = s;
 
1473
      // get replaced sources of st
 
1474
      for (s = 1; st->srcExists(s); offS += st->getSrc(s)->reg.size, ++s)
 
1475
         vals[k++] = st->getSrc(s);
 
1476
      // skip replaced sources of ri
 
1477
      for (s = n; offR < endS; offR += ri->getSrc(s)->reg.size, ++s);
 
1478
      // get non-replaced sources after values covered by st
 
1479
      for (; offR < endR; offR += ri->getSrc(s)->reg.size, ++s)
 
1480
         vals[k++] = ri->getSrc(s);
 
1481
      for (s = 0; s < k; ++s)
 
1482
         st->setSrc(s + 1, vals[s]);
 
1483
      st->setSrc(0, ri->getSrc(0));
 
1484
   } else
 
1485
   if (endR > endS) {
 
1486
      int j, s;
 
1487
      for (j = 1; offR < endS; offR += ri->getSrc(j++)->reg.size);
 
1488
      for (s = 1; offS < endS; offS += st->getSrc(s++)->reg.size);
 
1489
      for (; offR < endR; offR += ri->getSrc(j++)->reg.size)
 
1490
         st->setSrc(s++, ri->getSrc(j));
 
1491
   }
 
1492
   st->putExtraSources(0, extra);
 
1493
 
 
1494
   delete_Instruction(prog, rec->insn);
 
1495
 
 
1496
   rec->insn = st;
 
1497
   rec->offset = st->getSrc(0)->reg.data.offset;
 
1498
 
 
1499
   st->setType(typeOfSize(rec->size));
 
1500
 
 
1501
   return true;
 
1502
}
 
1503
 
 
1504
bool
 
1505
MemoryOpt::Record::overlaps(const Instruction *ldst) const
 
1506
{
 
1507
   Record that;
 
1508
   that.set(ldst);
 
1509
 
 
1510
   if (this->fileIndex != that.fileIndex)
 
1511
      return false;
 
1512
 
 
1513
   if (this->rel[0] || that.rel[0])
 
1514
      return this->base == that.base;
 
1515
   return
 
1516
      (this->offset < that.offset + that.size) &&
 
1517
      (this->offset + this->size > that.offset);
 
1518
}
 
1519
 
 
1520
// We must not eliminate stores that affect the result of @ld if
 
1521
// we find later stores to the same location, and we may no longer
 
1522
// merge them with later stores.
 
1523
// The stored value can, however, still be used to determine the value
 
1524
// returned by future loads.
 
1525
void
 
1526
MemoryOpt::lockStores(Instruction *const ld)
 
1527
{
 
1528
   for (Record *r = stores[ld->src[0].getFile()]; r; r = r->next)
 
1529
      if (!r->locked && r->overlaps(ld))
 
1530
         r->locked = true;
 
1531
}
 
1532
 
 
1533
// Prior loads from the location of @st are no longer valid.
 
1534
// Stores to the location of @st may no longer be used to derive
 
1535
// the value at it nor be coalesced into later stores.
 
1536
void
 
1537
MemoryOpt::purgeRecords(Instruction *const st, DataFile f)
 
1538
{
 
1539
   if (st)
 
1540
      f = st->src[0].getFile();
 
1541
 
 
1542
   for (Record *r = loads[f]; r; r = r->next)
 
1543
      if (!st || r->overlaps(st))
 
1544
         r->unlink(&loads[f]);
 
1545
 
 
1546
   for (Record *r = stores[f]; r; r = r->next)
 
1547
      if (!st || r->overlaps(st))
 
1548
         r->unlink(&stores[f]);
 
1549
}
 
1550
 
 
1551
bool
 
1552
MemoryOpt::visit(BasicBlock *bb)
 
1553
{
 
1554
   bool ret = runOpt(bb);
 
1555
   // Run again, one pass won't combine 4 32 bit ld/st to a single 128 bit ld/st
 
1556
   // where 96 bit memory operations are forbidden.
 
1557
   if (ret)
 
1558
      ret = runOpt(bb);
 
1559
   return ret;
 
1560
}
 
1561
 
 
1562
bool
 
1563
MemoryOpt::runOpt(BasicBlock *bb)
 
1564
{
 
1565
   Instruction *ldst, *next;
 
1566
   Record *rec;
 
1567
   bool isAdjacent = true;
 
1568
 
 
1569
   for (ldst = bb->getEntry(); ldst; ldst = next) {
 
1570
      bool keep = true;
 
1571
      bool isLoad = true;
 
1572
      next = ldst->next;
 
1573
 
 
1574
      if (ldst->op == OP_LOAD || ldst->op == OP_VFETCH) {
 
1575
         if (ldst->isDead()) {
 
1576
            // might have been produced by earlier optimization
 
1577
            delete_Instruction(prog, ldst);
 
1578
            continue;
 
1579
         }
 
1580
      } else
 
1581
      if (ldst->op == OP_STORE || ldst->op == OP_EXPORT) {
 
1582
         isLoad = false;
 
1583
      } else {
 
1584
         // TODO: maybe have all fixed ops act as barrier ?
 
1585
         if (ldst->op == OP_CALL) {
 
1586
            purgeRecords(NULL, FILE_MEMORY_LOCAL);
 
1587
            purgeRecords(NULL, FILE_MEMORY_GLOBAL);
 
1588
            purgeRecords(NULL, FILE_MEMORY_SHARED);
 
1589
            purgeRecords(NULL, FILE_SHADER_OUTPUT);
 
1590
         } else
 
1591
         if (ldst->op == OP_EMIT || ldst->op == OP_RESTART) {
 
1592
            purgeRecords(NULL, FILE_SHADER_OUTPUT);
 
1593
         }
 
1594
         continue;
 
1595
      }
 
1596
      if (ldst->getPredicate()) // TODO: handle predicated ld/st
 
1597
         continue;
 
1598
 
 
1599
      if (isLoad) {
 
1600
         DataFile file = ldst->src[0].getFile();
 
1601
 
 
1602
         // if ld l[]/g[] look for previous store to eliminate the reload
 
1603
         if (file == FILE_MEMORY_GLOBAL || file == FILE_MEMORY_LOCAL) {
 
1604
            // TODO: shared memory ?
 
1605
            rec = findRecord(ldst, false, isAdjacent);
 
1606
            if (rec && !isAdjacent)
 
1607
               keep = !replaceLdFromSt(ldst, rec);
 
1608
         }
 
1609
 
 
1610
         // or look for ld from the same location and replace this one
 
1611
         rec = keep ? findRecord(ldst, true, isAdjacent) : NULL;
 
1612
         if (rec) {
 
1613
            if (!isAdjacent)
 
1614
               keep = !replaceLdFromLd(ldst, rec);
 
1615
            else
 
1616
               // or combine a previous load with this one
 
1617
               keep = !combineLd(rec, ldst);
 
1618
         }
 
1619
         if (keep)
 
1620
            lockStores(ldst);
 
1621
      } else {
 
1622
         rec = findRecord(ldst, false, isAdjacent);
 
1623
         if (rec) {
 
1624
            if (!isAdjacent)
 
1625
               keep = !replaceStFromSt(ldst, rec);
 
1626
            else
 
1627
               keep = !combineSt(rec, ldst);
 
1628
         }
 
1629
         if (keep)
 
1630
            purgeRecords(ldst, DATA_FILE_COUNT);
 
1631
      }
 
1632
      if (keep)
 
1633
         addRecord(ldst);
 
1634
   }
 
1635
   reset();
 
1636
 
 
1637
   return true;
 
1638
}
 
1639
 
 
1640
// =============================================================================
 
1641
 
 
1642
// Turn control flow into predicated instructions (after register allocation !).
 
1643
// TODO:
 
1644
// Could move this to before register allocation on NVC0 and also handle nested
 
1645
// constructs.
 
1646
class FlatteningPass : public Pass
 
1647
{
 
1648
private:
 
1649
   virtual bool visit(BasicBlock *);
 
1650
 
 
1651
   bool tryPredicateConditional(BasicBlock *);
 
1652
   void predicateInstructions(BasicBlock *, Value *pred, CondCode cc);
 
1653
   void tryPropagateBranch(BasicBlock *);
 
1654
   inline bool isConstantCondition(Value *pred);
 
1655
   inline bool mayPredicate(const Instruction *, const Value *pred) const;
 
1656
   inline void removeFlow(Instruction *);
 
1657
};
 
1658
 
 
1659
bool
 
1660
FlatteningPass::isConstantCondition(Value *pred)
 
1661
{
 
1662
   Instruction *insn = pred->getUniqueInsn();
 
1663
   assert(insn);
 
1664
   if (insn->op != OP_SET || insn->srcExists(2))
 
1665
      return false;
 
1666
 
 
1667
   for (int s = 0; s < 2 && insn->srcExists(s); ++s) {
 
1668
      Instruction *ld = insn->getSrc(s)->getUniqueInsn();
 
1669
      DataFile file;
 
1670
      if (ld) {
 
1671
         if (ld->op != OP_MOV && ld->op != OP_LOAD)
 
1672
            return false;
 
1673
         if (ld->src[0].isIndirect(0))
 
1674
            return false;
 
1675
         file = ld->src[0].getFile();
 
1676
      } else {
 
1677
         file = insn->src[s].getFile();
 
1678
         // catch $r63 on NVC0
 
1679
         if (file == FILE_GPR && insn->getSrc(s)->reg.data.id > prog->maxGPR)
 
1680
            file = FILE_IMMEDIATE;
 
1681
      }
 
1682
      if (file != FILE_IMMEDIATE && file != FILE_MEMORY_CONST)
 
1683
         return false;
 
1684
   }
 
1685
   return true;
 
1686
}
 
1687
 
 
1688
void
 
1689
FlatteningPass::removeFlow(Instruction *insn)
 
1690
{
 
1691
   FlowInstruction *term = insn ? insn->asFlow() : NULL;
 
1692
   if (!term)
 
1693
      return;
 
1694
   Graph::Edge::Type ty = term->bb->cfg.outgoing().getType();
 
1695
 
 
1696
   if (term->op == OP_BRA) {
 
1697
      // TODO: this might get more difficult when we get arbitrary BRAs
 
1698
      if (ty == Graph::Edge::CROSS || ty == Graph::Edge::BACK)
 
1699
         return;
 
1700
   } else
 
1701
   if (term->op != OP_JOIN)
 
1702
      return;
 
1703
 
 
1704
   delete_Instruction(prog, term);
 
1705
 
 
1706
   Value *pred = term->getPredicate();
 
1707
 
 
1708
   if (pred && pred->refCount() == 0) {
 
1709
      Instruction *pSet = pred->getUniqueInsn();
 
1710
      pred->join->reg.data.id = -1; // deallocate
 
1711
      if (pSet->isDead())
 
1712
         delete_Instruction(prog, pSet);
 
1713
   }
 
1714
}
 
1715
 
 
1716
void
 
1717
FlatteningPass::predicateInstructions(BasicBlock *bb, Value *pred, CondCode cc)
 
1718
{
 
1719
   for (Instruction *i = bb->getEntry(); i; i = i->next) {
 
1720
      if (i->isNop())
 
1721
         continue;
 
1722
      assert(!i->getPredicate());
 
1723
      i->setPredicate(cc, pred);
 
1724
   }
 
1725
   removeFlow(bb->getExit());
 
1726
}
 
1727
 
 
1728
bool
 
1729
FlatteningPass::mayPredicate(const Instruction *insn, const Value *pred) const
 
1730
{
 
1731
   if (insn->isPseudo())
 
1732
      return true;
 
1733
   // TODO: calls where we don't know which registers are modified
 
1734
 
 
1735
   if (!prog->getTarget()->mayPredicate(insn, pred))
 
1736
      return false;
 
1737
   for (int d = 0; insn->defExists(d); ++d)
 
1738
      if (insn->getDef(d)->equals(pred))
 
1739
         return false;
 
1740
   return true;
 
1741
}
 
1742
 
 
1743
// If we conditionally skip over or to a branch instruction, replace it.
 
1744
// NOTE: We do not update the CFG anymore here !
 
1745
void
 
1746
FlatteningPass::tryPropagateBranch(BasicBlock *bb)
 
1747
{
 
1748
   BasicBlock *bf = NULL;
 
1749
   unsigned int i;
 
1750
 
 
1751
   if (bb->cfg.outgoingCount() != 2)
 
1752
      return;
 
1753
   if (!bb->getExit() || bb->getExit()->op != OP_BRA)
 
1754
      return;
 
1755
   Graph::EdgeIterator ei = bb->cfg.outgoing();
 
1756
 
 
1757
   for (i = 0; !ei.end(); ++i, ei.next()) {
 
1758
      bf = BasicBlock::get(ei.getNode());
 
1759
      if (bf->getInsnCount() == 1)
 
1760
         break;
 
1761
   }
 
1762
   if (ei.end() || !bf->getExit())
 
1763
      return;
 
1764
   FlowInstruction *bra = bb->getExit()->asFlow();
 
1765
   FlowInstruction *rep = bf->getExit()->asFlow();
 
1766
 
 
1767
   if (rep->getPredicate())
 
1768
      return;
 
1769
   if (rep->op != OP_BRA &&
 
1770
       rep->op != OP_JOIN &&
 
1771
       rep->op != OP_EXIT)
 
1772
      return;
 
1773
 
 
1774
   bra->op = rep->op;
 
1775
   bra->target.bb = rep->target.bb;
 
1776
   if (i) // 2nd out block means branch not taken
 
1777
      bra->cc = inverseCondCode(bra->cc);
 
1778
   bf->remove(rep);
 
1779
}
 
1780
 
 
1781
bool
 
1782
FlatteningPass::visit(BasicBlock *bb)
 
1783
{
 
1784
   if (tryPredicateConditional(bb))
 
1785
      return true;
 
1786
 
 
1787
   // try to attach join to previous instruction
 
1788
   Instruction *insn = bb->getExit();
 
1789
   if (insn && insn->op == OP_JOIN && !insn->getPredicate()) {
 
1790
      insn = insn->prev;
 
1791
      if (insn && !insn->getPredicate() && !insn->asFlow() && !insn->isNop()) {
 
1792
         insn->join = 1;
 
1793
         bb->remove(bb->getExit());
 
1794
         return true;
 
1795
      }
 
1796
   }
 
1797
 
 
1798
   tryPropagateBranch(bb);
 
1799
 
 
1800
   return true;
 
1801
}
 
1802
 
 
1803
bool
 
1804
FlatteningPass::tryPredicateConditional(BasicBlock *bb)
 
1805
{
 
1806
   BasicBlock *bL = NULL, *bR = NULL;
 
1807
   unsigned int nL = 0, nR = 0, limit = 12;
 
1808
   Instruction *insn;
 
1809
   unsigned int mask;
 
1810
 
 
1811
   mask = bb->initiatesSimpleConditional();
 
1812
   if (!mask)
 
1813
      return false;
 
1814
 
 
1815
   assert(bb->getExit());
 
1816
   Value *pred = bb->getExit()->getPredicate();
 
1817
   assert(pred);
 
1818
 
 
1819
   if (isConstantCondition(pred))
 
1820
      limit = 4;
 
1821
 
 
1822
   Graph::EdgeIterator ei = bb->cfg.outgoing();
 
1823
 
 
1824
   if (mask & 1) {
 
1825
      bL = BasicBlock::get(ei.getNode());
 
1826
      for (insn = bL->getEntry(); insn; insn = insn->next, ++nL)
 
1827
         if (!mayPredicate(insn, pred))
 
1828
            return false;
 
1829
      if (nL > limit)
 
1830
         return false; // too long, do a real branch
 
1831
   }
 
1832
   ei.next();
 
1833
 
 
1834
   if (mask & 2) {
 
1835
      bR = BasicBlock::get(ei.getNode());
 
1836
      for (insn = bR->getEntry(); insn; insn = insn->next, ++nR)
 
1837
         if (!mayPredicate(insn, pred))
 
1838
            return false;
 
1839
      if (nR > limit)
 
1840
         return false; // too long, do a real branch
 
1841
   }
 
1842
 
 
1843
   if (bL)
 
1844
      predicateInstructions(bL, pred, bb->getExit()->cc);
 
1845
   if (bR)
 
1846
      predicateInstructions(bR, pred, inverseCondCode(bb->getExit()->cc));
 
1847
 
 
1848
   if (bb->joinAt) {
 
1849
      bb->remove(bb->joinAt);
 
1850
      bb->joinAt = NULL;
 
1851
   }
 
1852
   removeFlow(bb->getExit()); // delete the branch/join at the fork point
 
1853
 
 
1854
   // remove potential join operations at the end of the conditional
 
1855
   if (prog->getTarget()->joinAnterior) {
 
1856
      bb = BasicBlock::get((bL ? bL : bR)->cfg.outgoing().getNode());
 
1857
      if (bb->getEntry() && bb->getEntry()->op == OP_JOIN)
 
1858
         removeFlow(bb->getEntry());
 
1859
   }
 
1860
 
 
1861
   return true;
 
1862
}
 
1863
 
 
1864
// =============================================================================
 
1865
 
 
1866
// Common subexpression elimination. Stupid O^2 implementation.
 
1867
class LocalCSE : public Pass
 
1868
{
 
1869
private:
 
1870
   virtual bool visit(BasicBlock *);
 
1871
 
 
1872
   inline bool tryReplace(Instruction **, Instruction *);
 
1873
 
 
1874
   DLList ops[OP_LAST + 1];
 
1875
};
 
1876
 
 
1877
class GlobalCSE : public Pass
 
1878
{
 
1879
private:
 
1880
   virtual bool visit(BasicBlock *);
 
1881
};
 
1882
 
 
1883
bool
 
1884
Instruction::isActionEqual(const Instruction *that) const
 
1885
{
 
1886
   if (this->op != that->op ||
 
1887
       this->dType != that->dType ||
 
1888
       this->sType != that->sType)
 
1889
      return false;
 
1890
   if (this->cc != that->cc)
 
1891
      return false;
 
1892
 
 
1893
   if (this->asTex()) {
 
1894
      if (memcmp(&this->asTex()->tex,
 
1895
                 &that->asTex()->tex,
 
1896
                 sizeof(this->asTex()->tex)))
 
1897
         return false;
 
1898
   } else
 
1899
   if (this->asCmp()) {
 
1900
      if (this->asCmp()->setCond != that->asCmp()->setCond)
 
1901
         return false;
 
1902
   } else
 
1903
   if (this->asFlow()) {
 
1904
      return false;
 
1905
   } else {
 
1906
      if (this->atomic != that->atomic ||
 
1907
          this->ipa != that->ipa ||
 
1908
          this->lanes != that->lanes ||
 
1909
          this->perPatch != that->perPatch)
 
1910
         return false;
 
1911
      if (this->postFactor != that->postFactor)
 
1912
         return false;
 
1913
   }
 
1914
 
 
1915
   if (this->subOp != that->subOp ||
 
1916
       this->saturate != that->saturate ||
 
1917
       this->rnd != that->rnd ||
 
1918
       this->ftz != that->ftz ||
 
1919
       this->dnz != that->dnz ||
 
1920
       this->cache != that->cache)
 
1921
      return false;
 
1922
 
 
1923
   return true;
 
1924
}
 
1925
 
 
1926
bool
 
1927
Instruction::isResultEqual(const Instruction *that) const
 
1928
{
 
1929
   unsigned int d, s;
 
1930
 
 
1931
   // NOTE: location of discard only affects tex with liveOnly and quadops
 
1932
   if (!this->defExists(0) && this->op != OP_DISCARD)
 
1933
      return false;
 
1934
 
 
1935
   if (!isActionEqual(that))
 
1936
      return false;
 
1937
 
 
1938
   if (this->predSrc != that->predSrc)
 
1939
      return false;
 
1940
 
 
1941
   for (d = 0; this->defExists(d); ++d) {
 
1942
      if (!that->defExists(d) ||
 
1943
          !this->getDef(d)->equals(that->getDef(d), false))
 
1944
         return false;
 
1945
   }
 
1946
   if (that->defExists(d))
 
1947
      return false;
 
1948
 
 
1949
   for (s = 0; this->srcExists(s); ++s) {
 
1950
      if (!that->srcExists(s))
 
1951
         return false;
 
1952
      if (this->src[s].mod != that->src[s].mod)
 
1953
         return false;
 
1954
      if (!this->getSrc(s)->equals(that->getSrc(s), true))
 
1955
         return false;
 
1956
   }
 
1957
   if (that->srcExists(s))
 
1958
      return false;
 
1959
 
 
1960
   if (op == OP_LOAD || op == OP_VFETCH) {
 
1961
      switch (src[0].getFile()) {
 
1962
      case FILE_MEMORY_CONST:
 
1963
      case FILE_SHADER_INPUT:
 
1964
         return true;
 
1965
      default:
 
1966
         return false;
 
1967
      }
 
1968
   }
 
1969
 
 
1970
   return true;
 
1971
}
 
1972
 
 
1973
// pull through common expressions from different in-blocks
 
1974
bool
 
1975
GlobalCSE::visit(BasicBlock *bb)
 
1976
{
 
1977
   Instruction *phi, *next, *ik;
 
1978
   int s;
 
1979
 
 
1980
   for (phi = bb->getPhi(); phi && phi->op == OP_PHI; phi = next) {
 
1981
      next = phi->next;
 
1982
      if (phi->getSrc(0)->refCount() > 1)
 
1983
         continue;
 
1984
      ik = phi->getSrc(0)->getInsn();
 
1985
      for (s = 1; phi->srcExists(s); ++s) {
 
1986
         if (phi->getSrc(s)->refCount() > 1)
 
1987
            break;
 
1988
         if (!phi->getSrc(s)->getInsn()->isResultEqual(ik))
 
1989
            break;
 
1990
      }
 
1991
      if (!phi->srcExists(s)) {
 
1992
         Instruction *entry = bb->getEntry();
 
1993
         ik->bb->remove(ik);
 
1994
         if (!entry || entry->op != OP_JOIN)
 
1995
            bb->insertHead(ik);
 
1996
         else
 
1997
            bb->insertAfter(entry, ik);
 
1998
         ik->setDef(0, phi->getDef(0));
 
1999
         delete_Instruction(prog, phi);
 
2000
      }
 
2001
   }
 
2002
 
 
2003
   return true;
 
2004
}
 
2005
 
 
2006
bool
 
2007
LocalCSE::tryReplace(Instruction **ptr, Instruction *i)
 
2008
{
 
2009
   Instruction *old = *ptr;
 
2010
   if (!old->isResultEqual(i))
 
2011
      return false;
 
2012
   for (int d = 0; old->defExists(d); ++d)
 
2013
      old->def[d].replace(i->getDef(d), false);
 
2014
   delete_Instruction(prog, old);
 
2015
   *ptr = NULL;
 
2016
   return true;
 
2017
}
 
2018
 
 
2019
bool
 
2020
LocalCSE::visit(BasicBlock *bb)
 
2021
{
 
2022
   unsigned int replaced;
 
2023
 
 
2024
   do {
 
2025
      Instruction *ir, *next;
 
2026
 
 
2027
      replaced = 0;
 
2028
 
 
2029
      // will need to know the order of instructions
 
2030
      int serial = 0;
 
2031
      for (ir = bb->getEntry(); ir; ir = ir->next)
 
2032
         ir->serial = serial++;
 
2033
 
 
2034
      for (ir = bb->getEntry(); ir; ir = next) {
 
2035
         int s;
 
2036
         Value *src = NULL;
 
2037
 
 
2038
         next = ir->next;
 
2039
 
 
2040
         if (ir->fixed) {
 
2041
            ops[ir->op].insert(ir);
 
2042
            continue;
 
2043
         }
 
2044
 
 
2045
         for (s = 0; ir->srcExists(s); ++s)
 
2046
            if (ir->getSrc(s)->asLValue())
 
2047
               if (!src || ir->getSrc(s)->refCount() < src->refCount())
 
2048
                  src = ir->getSrc(s);
 
2049
 
 
2050
         if (src) {
 
2051
            for (ValueRef::Iterator refs = src->uses->iterator(); !refs.end();
 
2052
                 refs.next()) {
 
2053
               Instruction *ik = refs.get()->getInsn();
 
2054
               if (ik->serial < ir->serial && ik->bb == ir->bb)
 
2055
                  if (tryReplace(&ir, ik))
 
2056
                     break;
 
2057
            }
 
2058
         } else {
 
2059
            DLLIST_FOR_EACH(&ops[ir->op], iter)
 
2060
            {
 
2061
               Instruction *ik = reinterpret_cast<Instruction *>(iter.get());
 
2062
               if (tryReplace(&ir, ik))
 
2063
                  break;
 
2064
            }
 
2065
         }
 
2066
 
 
2067
         if (ir)
 
2068
            ops[ir->op].insert(ir);
 
2069
         else
 
2070
            ++replaced;
 
2071
      }
 
2072
      for (unsigned int i = 0; i <= OP_LAST; ++i)
 
2073
         ops[i].clear();
 
2074
 
 
2075
   } while (replaced);
 
2076
 
 
2077
   return true;
 
2078
}
 
2079
 
 
2080
// =============================================================================
 
2081
 
 
2082
// Remove computations of unused values.
 
2083
class DeadCodeElim : public Pass
 
2084
{
 
2085
public:
 
2086
   bool buryAll(Program *);
 
2087
 
 
2088
private:
 
2089
   virtual bool visit(BasicBlock *);
 
2090
 
 
2091
   void checkSplitLoad(Instruction *ld); // for partially dead loads
 
2092
 
 
2093
   unsigned int deadCount;
 
2094
};
 
2095
 
 
2096
bool
 
2097
DeadCodeElim::buryAll(Program *prog)
 
2098
{
 
2099
   do {
 
2100
      deadCount = 0;
 
2101
      if (!this->run(prog, false, false))
 
2102
         return false;
 
2103
   } while (deadCount);
 
2104
 
 
2105
   return true;
 
2106
}
 
2107
 
 
2108
bool
 
2109
DeadCodeElim::visit(BasicBlock *bb)
 
2110
{
 
2111
   Instruction *next;
 
2112
 
 
2113
   for (Instruction *i = bb->getFirst(); i; i = next) {
 
2114
      next = i->next;
 
2115
      if (i->isDead()) {
 
2116
         ++deadCount;
 
2117
         delete_Instruction(prog, i);
 
2118
      } else
 
2119
      if (i->defExists(1) && (i->op == OP_VFETCH || i->op == OP_LOAD)) {
 
2120
         checkSplitLoad(i);
 
2121
      }
 
2122
   }
 
2123
   return true;
 
2124
}
 
2125
 
 
2126
void
 
2127
DeadCodeElim::checkSplitLoad(Instruction *ld1)
 
2128
{
 
2129
   Instruction *ld2 = NULL; // can get at most 2 loads
 
2130
   Value *def1[4];
 
2131
   Value *def2[4];
 
2132
   int32_t addr1, addr2;
 
2133
   int32_t size1, size2;
 
2134
   int d, n1, n2;
 
2135
   uint32_t mask = 0xffffffff;
 
2136
 
 
2137
   for (d = 0; ld1->defExists(d); ++d)
 
2138
      if (!ld1->getDef(d)->refCount() && ld1->getDef(d)->reg.data.id < 0)
 
2139
         mask &= ~(1 << d);
 
2140
   if (mask == 0xffffffff)
 
2141
      return;
 
2142
 
 
2143
   addr1 = ld1->getSrc(0)->reg.data.offset;
 
2144
   n1 = n2 = 0;
 
2145
   size1 = size2 = 0;
 
2146
   for (d = 0; ld1->defExists(d); ++d) {
 
2147
      if (mask & (1 << d)) {
 
2148
         if (size1 && (addr1 & 0x7))
 
2149
            break;
 
2150
         def1[n1] = ld1->getDef(d);
 
2151
         size1 += def1[n1++]->reg.size;
 
2152
      } else
 
2153
      if (!n1) {
 
2154
         addr1 += ld1->getDef(d)->reg.size;
 
2155
      } else {
 
2156
         break;
 
2157
      }
 
2158
   }
 
2159
   for (addr2 = addr1 + size1; ld1->defExists(d); ++d) {
 
2160
      if (mask & (1 << d)) {
 
2161
         def2[n2] = ld1->getDef(d);
 
2162
         size2 += def2[n2++]->reg.size;
 
2163
      } else {
 
2164
         assert(!n2);
 
2165
         addr2 += ld1->getDef(d)->reg.size;
 
2166
      }
 
2167
   }
 
2168
 
 
2169
   updateLdStOffset(ld1, addr1, func);
 
2170
   ld1->setType(typeOfSize(size1));
 
2171
   for (d = 0; d < 4; ++d)
 
2172
      ld1->setDef(d, (d < n1) ? def1[d] : NULL);
 
2173
 
 
2174
   if (!n2)
 
2175
      return;
 
2176
 
 
2177
   ld2 = ld1->clone(false);
 
2178
   updateLdStOffset(ld2, addr2, func);
 
2179
   ld2->setType(typeOfSize(size2));
 
2180
   for (d = 0; d < 4; ++d)
 
2181
      ld2->setDef(d, (d < n2) ? def2[d] : NULL);
 
2182
 
 
2183
   ld1->bb->insertAfter(ld1, ld2);
 
2184
}
 
2185
 
 
2186
// =============================================================================
 
2187
 
 
2188
#define RUN_PASS(l, n, f)                       \
 
2189
   if (level >= (l)) {                          \
 
2190
      if (dbgFlags & NV50_IR_DEBUG_VERBOSE)     \
 
2191
         INFO("PEEPHOLE: %s\n", #n);            \
 
2192
      n pass;                                   \
 
2193
      if (!pass.f(this))                        \
 
2194
         return false;                          \
 
2195
   }
 
2196
 
 
2197
bool
 
2198
Program::optimizeSSA(int level)
 
2199
{
 
2200
   RUN_PASS(1, DeadCodeElim, buryAll);
 
2201
   RUN_PASS(1, CopyPropagation, run);
 
2202
   RUN_PASS(2, GlobalCSE, run);
 
2203
   RUN_PASS(1, LocalCSE, run);
 
2204
   RUN_PASS(2, AlgebraicOpt, run);
 
2205
   RUN_PASS(2, ModifierFolding, run); // before load propagation -> less checks
 
2206
   RUN_PASS(1, ConstantFolding, foldAll);
 
2207
   RUN_PASS(1, LoadPropagation, run);
 
2208
   RUN_PASS(2, MemoryOpt, run);
 
2209
   RUN_PASS(2, LocalCSE, run);
 
2210
   RUN_PASS(0, DeadCodeElim, buryAll);
 
2211
   return true;
 
2212
}
 
2213
 
 
2214
bool
 
2215
Program::optimizePostRA(int level)
 
2216
{
 
2217
   RUN_PASS(2, FlatteningPass, run);
 
2218
   return true;
 
2219
}
 
2220
 
 
2221
}