1 /* 2 * Copyright 2013 Vadim Girlin <vadimgirlin (at) gmail.com> 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 * on the rights to use, copy, modify, merge, publish, distribute, sub 8 * license, and/or sell copies of the Software, and to permit persons to whom 9 * the Software is furnished to do so, subject to the following conditions: 10 * 11 * The above copyright notice and this permission notice (including the next 12 * paragraph) shall be included in all copies or substantial portions of the 13 * Software. 14 * 15 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 16 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 17 * FITNESS FOR A PARTICULAR PURPOSE AND NON-INFRINGEMENT. IN NO EVENT SHALL 18 * THE AUTHOR(S) AND/OR THEIR SUPPLIERS BE LIABLE FOR ANY CLAIM, 19 * DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR 20 * OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE 21 * USE OR OTHER DEALINGS IN THE SOFTWARE. 22 * 23 * Authors: 24 * Vadim Girlin 25 */ 26 27 #define RA_DEBUG 0 28 29 #if RA_DEBUG 30 #define RA_DUMP(q) do { q } while (0) 31 #else 32 #define RA_DUMP(q) 33 #endif 34 35 #include "sb_shader.h" 36 #include "sb_pass.h" 37 38 namespace r600_sb { 39 40 int ra_coalesce::run() { 41 return sh.coal.run(); 42 } 43 44 void coalescer::add_edge(value* a, value* b, unsigned cost) { 45 assert(a->is_sgpr() && b->is_sgpr()); 46 edges.insert(new ra_edge(a,b, cost)); 47 } 48 49 void coalescer::create_chunk(value *v) { 50 51 assert(v->is_sgpr()); 52 53 ra_chunk *c = new ra_chunk(); 54 55 c->values.push_back(v); 56 57 if (v->is_chan_pinned()) 58 c->flags |= RCF_PIN_CHAN; 59 if (v->is_reg_pinned()) { 60 c->flags |= RCF_PIN_REG; 61 } 62 63 c->pin = v->pin_gpr; 64 65 RA_DUMP( 66 sblog << "create_chunk: "; 67 dump_chunk(c); 68 ); 69 70 all_chunks.push_back(c); 71 v->chunk = c; 72 73 } 74 75 void coalescer::unify_chunks(ra_edge *e) { 76 ra_chunk *c1 = e->a->chunk, *c2 = e->b->chunk; 77 78 RA_DUMP( 79 sblog << "unify_chunks: "; 80 dump_chunk(c1); 81 dump_chunk(c2); 82 ); 83 84 if (c2->is_chan_pinned() && !c1->is_chan_pinned()) { 85 c1->flags |= RCF_PIN_CHAN; 86 c1->pin = sel_chan(c1->pin.sel(), c2->pin.chan()); 87 } 88 89 if (c2->is_reg_pinned() && !c1->is_reg_pinned()) { 90 c1->flags |= RCF_PIN_REG; 91 c1->pin = sel_chan(c2->pin.sel(), c1->pin.chan()); 92 } 93 94 c1->values.reserve(c1->values.size() + c2->values.size()); 95 96 for (vvec::iterator I = c2->values.begin(), E = c2->values.end(); I != E; 97 ++I) { 98 (*I)->chunk = c1; 99 c1->values.push_back(*I); 100 } 101 102 chunk_vec::iterator F = std::find(all_chunks.begin(), all_chunks.end(), c2); 103 assert(F != all_chunks.end()); 104 105 all_chunks.erase(F); 106 107 c1->cost += c2->cost + e->cost; 108 delete c2; 109 } 110 111 bool coalescer::chunks_interference(ra_chunk *c1, ra_chunk *c2) { 112 unsigned pin_flags = (c1->flags & c2->flags) & 113 (RCF_PIN_CHAN | RCF_PIN_REG); 114 115 if ((pin_flags & RCF_PIN_CHAN) && 116 c1->pin.chan() != c2->pin.chan()) 117 return true; 118 119 if ((pin_flags & RCF_PIN_REG) && 120 c1->pin.sel() != c2->pin.sel()) 121 return true; 122 123 for (vvec::iterator I = c1->values.begin(), E = c1->values.end(); I != E; 124 ++I) { 125 value *v1 = *I; 126 127 for (vvec::iterator I = c2->values.begin(), E = c2->values.end(); I != E; 128 ++I) { 129 value *v2 = *I; 130 131 if (!v1->v_equal(v2) && v1->interferences.contains(v2)) 132 return true; 133 } 134 } 135 return false; 136 } 137 138 void coalescer::build_chunks() { 139 140 for (edge_queue::iterator I = edges.begin(), E = edges.end(); 141 I != E; ++I) { 142 143 ra_edge *e = *I; 144 145 if (!e->a->chunk) 146 create_chunk(e->a); 147 148 if (!e->b->chunk) 149 create_chunk(e->b); 150 151 ra_chunk *c1 = e->a->chunk, *c2 = e->b->chunk; 152 153 if (c1 == c2) { 154 c1->cost += e->cost; 155 } else if (!chunks_interference(c1, c2)) 156 unify_chunks(e); 157 } 158 } 159 160 ra_constraint* coalescer::create_constraint(constraint_kind kind) { 161 ra_constraint *c = new ra_constraint(kind); 162 all_constraints.push_back(c); 163 return c; 164 } 165 166 void coalescer::dump_edges() { 167 sblog << "######## affinity edges\n"; 168 169 for (edge_queue::iterator I = edges.begin(), E = edges.end(); 170 I != E; ++I) { 171 ra_edge* e = *I; 172 sblog << " ra_edge "; 173 dump::dump_val(e->a); 174 sblog << " <-> "; 175 dump::dump_val(e->b); 176 sblog << " cost = " << e->cost << "\n"; 177 } 178 } 179 180 void coalescer::dump_chunks() { 181 sblog << "######## chunks\n"; 182 183 for (chunk_vec::iterator I = all_chunks.begin(), E = all_chunks.end(); 184 I != E; ++I) { 185 ra_chunk* c = *I; 186 dump_chunk(c); 187 } 188 } 189 190 191 void coalescer::dump_constraint_queue() { 192 sblog << "######## constraints\n"; 193 194 for (constraint_queue::iterator I = constraints.begin(), 195 E = constraints.end(); I != E; ++I) { 196 ra_constraint* c = *I; 197 dump_constraint(c); 198 } 199 } 200 201 void coalescer::dump_chunk(ra_chunk* c) { 202 sblog << " ra_chunk cost = " << c->cost << " : "; 203 dump::dump_vec(c->values); 204 205 if (c->flags & RCF_PIN_REG) 206 sblog << " REG = " << c->pin.sel(); 207 208 if (c->flags & RCF_PIN_CHAN) 209 sblog << " CHAN = " << c->pin.chan(); 210 211 sblog << (c->flags & RCF_GLOBAL ? " GLOBAL" : ""); 212 213 sblog << "\n"; 214 } 215 216 void coalescer::dump_constraint(ra_constraint* c) { 217 sblog << " ra_constraint: "; 218 switch (c->kind) { 219 case CK_PACKED_BS: sblog << "PACKED_BS"; break; 220 case CK_PHI: sblog << "PHI"; break; 221 case CK_SAME_REG: sblog << "SAME_REG"; break; 222 default: sblog << "UNKNOWN_KIND"; assert(0); break; 223 } 224 225 sblog << " cost = " << c->cost << " : "; 226 dump::dump_vec(c->values); 227 228 sblog << "\n"; 229 } 230 231 void coalescer::get_chunk_interferences(ra_chunk *c, val_set &s) { 232 233 for (vvec::iterator I = c->values.begin(), E = c->values.end(); I != E; 234 ++I) { 235 value *v = *I; 236 s.add_set(v->interferences); 237 } 238 s.remove_vec(c->values); 239 } 240 241 void coalescer::build_chunk_queue() { 242 for (chunk_vec::iterator I = all_chunks.begin(), 243 E = all_chunks.end(); I != E; ++I) { 244 ra_chunk *c = *I; 245 246 if (!c->is_fixed()) 247 chunks.insert(c); 248 } 249 } 250 251 void coalescer::build_constraint_queue() { 252 for (constraint_vec::iterator I = all_constraints.begin(), 253 E = all_constraints.end(); I != E; ++I) { 254 ra_constraint *c = *I; 255 unsigned cost = 0; 256 257 if (c->values.empty() || !c->values.front()->is_sgpr()) 258 continue; 259 260 if (c->kind != CK_SAME_REG) 261 continue; 262 263 for (vvec::iterator I = c->values.begin(), E = c->values.end(); 264 I != E; ++I) { 265 value *v = *I; 266 if (!v->chunk) 267 create_chunk(v); 268 else 269 cost += v->chunk->cost; 270 } 271 c->cost = cost; 272 constraints.insert(c); 273 } 274 } 275 276 void coalescer::color_chunks() { 277 278 for (chunk_queue::iterator I = chunks.begin(), E = chunks.end(); 279 I != E; ++I) { 280 ra_chunk *c = *I; 281 if (c->is_fixed() || c->values.size() == 1) 282 continue; 283 284 sb_bitset rb; 285 val_set interf; 286 287 get_chunk_interferences(c, interf); 288 289 RA_DUMP( 290 sblog << "color_chunks: "; 291 dump_chunk(c); 292 sblog << "\n interferences: "; 293 dump::dump_set(sh,interf); 294 sblog << "\n"; 295 ); 296 297 init_reg_bitset(rb, interf); 298 299 unsigned pass = c->is_reg_pinned() ? 0 : 1; 300 301 unsigned cs = c->is_chan_pinned() ? c->pin.chan() : 0; 302 unsigned ce = c->is_chan_pinned() ? cs + 1 : 4; 303 304 unsigned color = 0; 305 306 while (pass < 2) { 307 308 unsigned rs, re; 309 310 if (pass == 0) { 311 rs = c->pin.sel(); 312 re = rs + 1; 313 } else { 314 rs = 0; 315 re = sh.num_nontemp_gpr(); 316 } 317 318 for (unsigned reg = rs; reg < re; ++reg) { 319 for (unsigned chan = cs; chan < ce; ++chan) { 320 unsigned bit = sel_chan(reg, chan); 321 if (bit >= rb.size() || !rb.get(bit)) { 322 color = bit; 323 break; 324 } 325 } 326 if (color) 327 break; 328 } 329 330 if (color) 331 break; 332 333 ++pass; 334 } 335 336 assert(color); 337 color_chunk(c, color); 338 } 339 } 340 341 void coalescer::init_reg_bitset(sb_bitset &bs, val_set &vs) { 342 343 for (val_set::iterator I = vs.begin(sh), E = vs.end(sh); I != E; ++I) { 344 value *v = *I; 345 346 if (!v->is_any_gpr()) 347 continue; 348 349 unsigned gpr = v->get_final_gpr(); 350 if (!gpr) 351 continue; 352 353 if (gpr) { 354 if (gpr >= bs.size()) 355 bs.resize(gpr + 64); 356 bs.set(gpr, 1); 357 } 358 } 359 } 360 361 void coalescer::color_chunk(ra_chunk *c, sel_chan color) { 362 363 vvec vv = c->values; 364 365 for (vvec::iterator I = vv.begin(), E = vv.end(); I != E; 366 ++I) { 367 value *v = *I; 368 369 if (v->is_reg_pinned() && v->pin_gpr.sel() != color.sel()) { 370 detach_value(v); 371 continue; 372 } 373 374 if (v->is_chan_pinned() && v->pin_gpr.chan() != color.chan()) { 375 detach_value(v); 376 continue; 377 } 378 379 v->gpr = color; 380 381 if (v->constraint && v->constraint->kind == CK_PHI) 382 v->fix(); 383 384 385 RA_DUMP( 386 sblog << " assigned " << color << " to "; 387 dump::dump_val(v); 388 sblog << "\n"; 389 ); 390 } 391 392 c->pin = color; 393 394 if (c->is_reg_pinned()) { 395 c->fix(); 396 } 397 } 398 399 coalescer::~coalescer() { 400 401 // FIXME use pool allocator ?? 402 403 for (constraint_vec::iterator I = all_constraints.begin(), 404 E = all_constraints.end(); I != E; ++I) { 405 delete (*I); 406 } 407 408 for (chunk_vec::iterator I = all_chunks.begin(), 409 E = all_chunks.end(); I != E; ++I) { 410 delete (*I); 411 } 412 413 for (edge_queue::iterator I = edges.begin(), E = edges.end(); 414 I != E; ++I) { 415 delete (*I); 416 } 417 } 418 419 int coalescer::run() { 420 int r; 421 422 RA_DUMP( dump_edges(); ); 423 424 build_chunks(); 425 RA_DUMP( dump_chunks(); ); 426 427 build_constraint_queue(); 428 RA_DUMP( dump_constraint_queue(); ); 429 430 if ((r = color_constraints())) 431 return r; 432 433 build_chunk_queue(); 434 color_chunks(); 435 436 return 0; 437 } 438 439 void coalescer::color_phi_constraint(ra_constraint* c) { 440 } 441 442 ra_chunk* coalescer::detach_value(value *v) { 443 444 vvec::iterator F = std::find(v->chunk->values.begin(), 445 v->chunk->values.end(), v); 446 447 assert(F != v->chunk->values.end()); 448 v->chunk->values.erase(F); 449 create_chunk(v); 450 451 if (v->is_reg_pinned()) { 452 v->chunk->fix(); 453 } 454 455 RA_DUMP( 456 sblog << " detached : "; 457 dump_chunk(v->chunk); 458 ); 459 460 return v->chunk; 461 462 } 463 464 int coalescer::color_reg_constraint(ra_constraint *c) { 465 unsigned k, cnt = c->values.size(); 466 vvec & cv = c->values; 467 468 ra_chunk *ch[4]; 469 unsigned swz[4] = {0, 1, 2, 3}; 470 val_set interf[4]; 471 sb_bitset rb[4]; 472 473 bool reg_pinned = false; 474 unsigned pin_reg = ~0; 475 476 unsigned chan_mask = 0; 477 478 k = 0; 479 for (vvec::iterator I = cv.begin(), E = cv.end(); I != E; ++I, ++k) { 480 value *v = *I; 481 482 if (!v->chunk) 483 create_chunk(v); 484 485 ch[k] = v->chunk; 486 487 if (v->chunk->is_chan_pinned()) { 488 unsigned chan = 1 << v->chunk->pin.chan(); 489 490 if (chan & chan_mask) { // channel already in use 491 ch[k] = detach_value(v); 492 assert(!ch[k]->is_chan_pinned()); 493 } else { 494 chan_mask |= chan; 495 } 496 } 497 498 if (v->chunk->is_reg_pinned()) { 499 if (!reg_pinned) { 500 reg_pinned = true; 501 pin_reg = v->chunk->pin.sel(); 502 } 503 } 504 505 get_chunk_interferences(ch[k], interf[k]); 506 init_reg_bitset(rb[k], interf[k]); 507 } 508 509 unsigned start_reg, end_reg; 510 511 start_reg = 0; 512 end_reg = sh.num_nontemp_gpr(); 513 514 unsigned min_reg = end_reg; 515 unsigned min_swz[4]; 516 unsigned i, pass = reg_pinned ? 0 : 1; 517 518 bool done = false; 519 520 while (pass < 2) { 521 522 unsigned rs, re; 523 524 if (pass == 0) { 525 re = pin_reg + 1; 526 rs = pin_reg; 527 } else { 528 re = end_reg; 529 rs = start_reg; 530 } 531 532 min_reg = re; 533 534 // cycle on swizzle combinations 535 do { 536 for (i = 0; i < cnt; ++i) { 537 if (ch[i]->flags & RCF_PIN_CHAN) 538 if (ch[i]->pin.chan() != swz[i]) 539 break; 540 } 541 if (i != cnt) 542 continue; 543 544 // looking for minimal reg number such that the constrained chunks 545 // may be colored with the current swizzle combination 546 for (unsigned reg = rs; reg < min_reg; ++reg) { 547 for (i = 0; i < cnt; ++i) { 548 unsigned bit = sel_chan(reg, swz[i]); 549 if (bit < rb[i].size() && rb[i].get(bit)) 550 break; 551 } 552 if (i == cnt) { 553 done = true; 554 min_reg = reg; 555 std::copy(swz, swz + 4, min_swz); 556 break; 557 } 558 } 559 560 if (pass == 0 && done) 561 break; 562 563 } while (std::next_permutation(swz, swz + 4)); 564 565 if (!done && pass) { 566 sblog << "sb: ra_coalesce - out of registers\n"; 567 return -1; 568 } 569 570 if (pass == 0 && done) 571 break; 572 573 ++pass; 574 }; 575 576 assert(done); 577 578 RA_DUMP( 579 sblog << "min reg = " << min_reg << " min_swz = " 580 << min_swz[0] << min_swz[1] << min_swz[2] << min_swz[3] << "\n"; 581 ); 582 583 for (i = 0; i < cnt; ++i) { 584 sel_chan color(min_reg, min_swz[i]); 585 ra_chunk *cc = ch[i]; 586 587 if (cc->is_fixed()) { 588 if (cc->pin != color) 589 cc = detach_value(cv[i]); 590 else 591 continue; 592 } 593 594 color_chunk(cc, color); 595 cc->fix(); 596 cc->set_prealloc(); 597 } 598 599 return 0; 600 } 601 602 int coalescer::color_constraints() { 603 int r; 604 605 for (constraint_queue::iterator I = constraints.begin(), 606 E = constraints.end(); I != E; ++I) { 607 608 ra_constraint *c = *I; 609 610 RA_DUMP( 611 sblog << "color_constraints: "; 612 dump_constraint(c); 613 ); 614 615 if (c->kind == CK_SAME_REG) { 616 if ((r = color_reg_constraint(c))) 617 return r; 618 } else if (c->kind == CK_PHI) 619 color_phi_constraint(c); 620 } 621 return 0; 622 } 623 624 } // namespace r600_sb 625
