src/mesa/drivers/dri/r300/compiler/radeon_program_pair.c

   1 /*
   2  * Copyright (C) 2008 Nicolai Haehnle.
   3  *
   4  * All Rights Reserved.
   5  *
   6  * Permission is hereby granted, free of charge, to any person obtaining
   7  * a copy of this software and associated documentation files (the
   8  * "Software"), to deal in the Software without restriction, including
   9  * without limitation the rights to use, copy, modify, merge, publish,
  10  * distribute, sublicense, and/or sell copies of the Software, and to
  11  * permit persons to whom the Software is furnished to do so, subject to
  12  * the following conditions:
  13  *
  14  * The above copyright notice and this permission notice (including the
  15  * next paragraph) shall be included in all copies or substantial
  16  * portions of the Software.
  17  *
  18  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  19  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  20  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
  21  * IN NO EVENT SHALL THE COPYRIGHT OWNER(S) AND/OR ITS SUPPLIERS BE
  22  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
  23  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
  24  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  25  *
  26  */
  27
  28 /**
  29  * @file
  30  *
  31  * Perform temporary register allocation and attempt to pair off instructions
  32  * in RGB and Alpha pairs. Also attempts to optimize the TEX instruction
  33  * vs. ALU instruction scheduling.
  34  */
  35
  36 #include "radeon_program_pair.h"
  37
  38 #include "memory_pool.h"
  39 #include "radeon_compiler.h"
  40 #include "shader/prog_print.h"
  41
  42 #define error(fmt, args...) do { \
  43         rc_error(&s->Compiler->Base, "%s::%s(): " fmt "\n",     \
  44                 __FILE__, __FUNCTION__, ##args);        \
  45 } while(0)
  46
  47 struct pair_state_instruction {
  48         struct prog_instruction Instruction;
  49         GLuint IP; /**< Position of this instruction in original program */
  50
  51         GLuint IsTex:1; /**< Is a texture instruction */
  52         GLuint NeedRGB:1; /**< Needs the RGB ALU */
  53         GLuint NeedAlpha:1; /**< Needs the Alpha ALU */
  54         GLuint IsTranscendent:1; /**< Is a special transcendent instruction */
  55
  56         /**
  57          * Number of (read and write) dependencies that must be resolved before
  58          * this instruction can be scheduled.
  59          */
  60         GLuint NumDependencies:5;
  61
  62         /**
  63          * Next instruction in the linked list of ready instructions.
  64          */
  65         struct pair_state_instruction *NextReady;
  66
  67         /**
  68          * Values that this instruction writes
  69          */
  70         struct reg_value *Values[4];
  71 };
  72
  73
  74 /**
  75  * Used to keep track of which instructions read a value.
  76  */
  77 struct reg_value_reader {
  78         struct pair_state_instruction *Reader;
  79         struct reg_value_reader *Next;
  80 };
  81
  82 /**
  83  * Used to keep track which values are stored in each component of a
  84  * PROGRAM_TEMPORARY.
  85  */
  86 struct reg_value {
  87         struct pair_state_instruction *Writer;
  88         struct reg_value *Next; /**< Pointer to the next value to be written to the same PROGRAM_TEMPORARY component */
  89
  90         /**
  91          * Unordered linked list of instructions that read from this value.
  92          */
  93         struct reg_value_reader *Readers;
  94
  95         /**
  96          * Number of readers of this value. This is calculated during @ref scan_instructions
  97          * and continually decremented during code emission.
  98          * When this count reaches zero, the instruction that writes the @ref Next value
  99          * can be scheduled.
 100          */
 101         GLuint NumReaders;
 102 };
 103
 104 /**
 105  * Used to translate a PROGRAM_INPUT or PROGRAM_TEMPORARY Mesa register
 106  * to the proper hardware temporary.
 107  */
 108 struct pair_register_translation {
 109         GLuint Allocated:1;
 110         GLuint HwIndex:8;
 111         GLuint RefCount:23; /**< # of times this occurs in an unscheduled instruction SrcReg or DstReg */
 112
 113         /**
 114          * Notes the value that is currently contained in each component
 115          * (only used for PROGRAM_TEMPORARY registers).
 116          */
 117         struct reg_value *Value[4];
 118 };
 119
 120 struct pair_state {
 121         struct r300_fragment_program_compiler * Compiler;
 122         const struct radeon_pair_handler *Handler;
 123         GLboolean Verbose;
 124         void *UserData;
 125
 126         /**
 127          * Translate Mesa registers to hardware registers
 128          */
 129         struct pair_register_translation Inputs[FRAG_ATTRIB_MAX];
 130         struct pair_register_translation Temps[MAX_PROGRAM_TEMPS];
 131
 132         struct {
 133                 GLuint RefCount; /**< # of times this occurs in an unscheduled SrcReg or DstReg */
 134         } HwTemps[128];
 135
 136         /**
 137          * Linked list of instructions that can be scheduled right now,
 138          * based on which ALU/TEX resources they require.
 139          */
 140         struct pair_state_instruction *ReadyFullALU;
 141         struct pair_state_instruction *ReadyRGB;
 142         struct pair_state_instruction *ReadyAlpha;
 143         struct pair_state_instruction *ReadyTEX;
 144 };
 145
 146
 147 static struct pair_register_translation *get_register(struct pair_state *s, GLuint file, GLuint index)
 148 {
 149         switch(file) {
 150         case PROGRAM_TEMPORARY: return &s->Temps[index];
 151         case PROGRAM_INPUT: return &s->Inputs[index];
 152         default: return 0;
 153         }
 154 }
 155
 156 static void alloc_hw_reg(struct pair_state *s, GLuint file, GLuint index, GLuint hwindex)
 157 {
 158         struct pair_register_translation *t = get_register(s, file, index);
 159         ASSERT(!s->HwTemps[hwindex].RefCount);
 160         ASSERT(!t->Allocated);
 161         s->HwTemps[hwindex].RefCount = t->RefCount;
 162         t->Allocated = 1;
 163         t->HwIndex = hwindex;
 164 }
 165
 166 static GLuint get_hw_reg(struct pair_state *s, GLuint file, GLuint index)
 167 {
 168         GLuint hwindex;
 169
 170         struct pair_register_translation *t = get_register(s, file, index);
 171         if (!t) {
 172                 error("get_hw_reg: %i[%i]\n", file, index);
 173                 return 0;
 174         }
 175
 176         if (t->Allocated)
 177                 return t->HwIndex;
 178
 179         for(hwindex = 0; hwindex < s->Handler->MaxHwTemps; ++hwindex)
 180                 if (!s->HwTemps[hwindex].RefCount)
 181                         break;
 182
 183         if (hwindex >= s->Handler->MaxHwTemps) {
 184                 error("Ran out of hardware temporaries");
 185                 return 0;
 186         }
 187
 188         alloc_hw_reg(s, file, index, hwindex);
 189         return hwindex;
 190 }
 191
 192
 193 static void deref_hw_reg(struct pair_state *s, GLuint hwindex)
 194 {
 195         if (!s->HwTemps[hwindex].RefCount) {
 196                 error("Hwindex %i refcount error", hwindex);
 197                 return;
 198         }
 199
 200         s->HwTemps[hwindex].RefCount--;
 201 }
 202
 203 static void add_pairinst_to_list(struct pair_state_instruction **list, struct pair_state_instruction *pairinst)
 204 {
 205         pairinst->NextReady = *list;
 206         *list = pairinst;
 207 }
 208
 209 /**
 210  * The given instruction has become ready. Link it into the ready
 211  * instructions.
 212  */
 213 static void instruction_ready(struct pair_state *s, struct pair_state_instruction *pairinst)
 214 {
 215         if (s->Verbose)
 216                 _mesa_printf("instruction_ready(%i)\n", pairinst->IP);
 217
 218         if (pairinst->IsTex)
 219                 add_pairinst_to_list(&s->ReadyTEX, pairinst);
 220         else if (!pairinst->NeedAlpha)
 221                 add_pairinst_to_list(&s->ReadyRGB, pairinst);
 222         else if (!pairinst->NeedRGB)
 223                 add_pairinst_to_list(&s->ReadyAlpha, pairinst);
 224         else
 225                 add_pairinst_to_list(&s->ReadyFullALU, pairinst);
 226 }
 227
 228
 229 /**
 230  * Finally rewrite ADD, MOV, MUL as the appropriate native instruction
 231  * and reverse the order of arguments for CMP.
 232  */
 233 static void final_rewrite(struct pair_state *s, struct prog_instruction *inst)
 234 {
 235         struct prog_src_register tmp;
 236
 237         switch(inst->Opcode) {
 238         case OPCODE_ADD:
 239                 inst->SrcReg[2] = inst->SrcReg[1];
 240                 inst->SrcReg[1].File = PROGRAM_BUILTIN;
 241                 inst->SrcReg[1].Swizzle = SWIZZLE_1111;
 242                 inst->SrcReg[1].Negate = NEGATE_NONE;
 243                 inst->Opcode = OPCODE_MAD;
 244                 break;
 245         case OPCODE_CMP:
 246                 tmp = inst->SrcReg[2];
 247                 inst->SrcReg[2] = inst->SrcReg[0];
 248                 inst->SrcReg[0] = tmp;
 249                 break;
 250         case OPCODE_MOV:
 251                 /* AMD say we should use CMP.
 252                  * However, when we transform
 253                  *  KIL -r0;
 254                  * into
 255                  *  CMP tmp, -r0, -r0, 0;
 256                  *  KIL tmp;
 257                  * we get incorrect behaviour on R500 when r0 == 0.0.
 258                  * It appears that the R500 KIL hardware treats -0.0 as less
 259                  * than zero.
 260                  */
 261                 inst->SrcReg[1].File = PROGRAM_BUILTIN;
 262                 inst->SrcReg[1].Swizzle = SWIZZLE_1111;
 263                 inst->SrcReg[2].File = PROGRAM_BUILTIN;
 264                 inst->SrcReg[2].Swizzle = SWIZZLE_0000;
 265                 inst->Opcode = OPCODE_MAD;
 266                 break;
 267         case OPCODE_MUL:
 268                 inst->SrcReg[2].File = PROGRAM_BUILTIN;
 269                 inst->SrcReg[2].Swizzle = SWIZZLE_0000;
 270                 inst->Opcode = OPCODE_MAD;
 271                 break;
 272         default:
 273                 /* nothing to do */
 274                 break;
 275         }
 276 }
 277
 278
 279 /**
 280  * Classify an instruction according to which ALUs etc. it needs
 281  */
 282 static void classify_instruction(struct pair_state *s,
 283         struct pair_state_instruction *psi)
 284 {
 285         psi->NeedRGB = (psi->Instruction.DstReg.WriteMask & WRITEMASK_XYZ) ? 1 : 0;
 286         psi->NeedAlpha = (psi->Instruction.DstReg.WriteMask & WRITEMASK_W) ? 1 : 0;
 287
 288         switch(psi->Instruction.Opcode) {
 289         case OPCODE_ADD:
 290         case OPCODE_CMP:
 291         case OPCODE_DDX:
 292         case OPCODE_DDY:
 293         case OPCODE_FRC:
 294         case OPCODE_MAD:
 295         case OPCODE_MAX:
 296         case OPCODE_MIN:
 297         case OPCODE_MOV:
 298         case OPCODE_MUL:
 299                 break;
 300         case OPCODE_COS:
 301         case OPCODE_EX2:
 302         case OPCODE_LG2:
 303         case OPCODE_RCP:
 304         case OPCODE_RSQ:
 305         case OPCODE_SIN:
 306                 psi->IsTranscendent = 1;
 307                 psi->NeedAlpha = 1;
 308                 break;
 309         case OPCODE_DP4:
 310                 psi->NeedAlpha = 1;
 311                 /* fall through */
 312         case OPCODE_DP3:
 313                 psi->NeedRGB = 1;
 314                 break;
 315         case OPCODE_KIL:
 316         case OPCODE_TEX:
 317         case OPCODE_TXB:
 318         case OPCODE_TXP:
 319         case OPCODE_END:
 320                 psi->IsTex = 1;
 321                 break;
 322         default:
 323                 error("Unknown opcode %d\n", psi->Instruction.Opcode);
 324                 break;
 325         }
 326 }
 327
 328
 329 /**
 330  * Count which (input, temporary) register is read and written how often,
 331  * and scan the instruction stream to find dependencies.
 332  */
 333 static void scan_instructions(struct pair_state *s)
 334 {
 335         struct rc_instruction *source;
 336         GLuint ip;
 337
 338         for(source = s->Compiler->Base.Program.Instructions.Next, ip = 0;
 339             source != &s->Compiler->Base.Program.Instructions;
 340             source = source->Next, ++ip) {
 341                 struct pair_state_instruction *pairinst = memory_pool_malloc(&s->Compiler->Base.Pool, sizeof(*pairinst));
 342                 memset(pairinst, 0, sizeof(struct pair_state_instruction));
 343
 344                 pairinst->Instruction = source->I;
 345                 pairinst->IP = ip;
 346                 final_rewrite(s, &pairinst->Instruction);
 347                 classify_instruction(s, pairinst);
 348
 349                 int nsrc = _mesa_num_inst_src_regs(pairinst->Instruction.Opcode);
 350                 int j;
 351                 for(j = 0; j < nsrc; j++) {
 352                         struct pair_register_translation *t =
 353                                 get_register(s, pairinst->Instruction.SrcReg[j].File, pairinst->Instruction.SrcReg[j].Index);
 354                         if (!t)
 355                                 continue;
 356
 357                         t->RefCount++;
 358
 359                         if (pairinst->Instruction.SrcReg[j].File == PROGRAM_TEMPORARY) {
 360                                 int i;
 361                                 for(i = 0; i < 4; ++i) {
 362                                         GLuint swz = GET_SWZ(pairinst->Instruction.SrcReg[j].Swizzle, i);
 363                                         if (swz >= 4)
 364                                                 continue; /* constant or NIL swizzle */
 365                                         if (!t->Value[swz])
 366                                                 continue; /* this is an undefined read */
 367
 368                                         /* Do not add a dependency if this instruction
 369                                          * also rewrites the value. The code below adds
 370                                          * a dependency for the DstReg, which is a superset
 371                                          * of the SrcReg dependency. */
 372                                         if (pairinst->Instruction.DstReg.File == PROGRAM_TEMPORARY &&
 373                                             pairinst->Instruction.DstReg.Index == pairinst->Instruction.SrcReg[j].Index &&
 374                                             GET_BIT(pairinst->Instruction.DstReg.WriteMask, swz))
 375                                                 continue;
 376
 377                                         struct reg_value_reader* r = memory_pool_malloc(&s->Compiler->Base.Pool, sizeof(*r));
 378                                         pairinst->NumDependencies++;
 379                                         t->Value[swz]->NumReaders++;
 380                                         r->Reader = pairinst;
 381                                         r->Next = t->Value[swz]->Readers;
 382                                         t->Value[swz]->Readers = r;
 383                                 }
 384                         }
 385                 }
 386
 387                 int ndst = _mesa_num_inst_dst_regs(pairinst->Instruction.Opcode);
 388                 if (ndst) {
 389                         struct pair_register_translation *t =
 390                                 get_register(s, pairinst->Instruction.DstReg.File, pairinst->Instruction.DstReg.Index);
 391                         if (t) {
 392                                 t->RefCount++;
 393
 394                                 if (pairinst->Instruction.DstReg.File == PROGRAM_TEMPORARY) {
 395                                         int j;
 396                                         for(j = 0; j < 4; ++j) {
 397                                                 if (!GET_BIT(pairinst->Instruction.DstReg.WriteMask, j))
 398                                                         continue;
 399
 400                                                 struct reg_value* v = memory_pool_malloc(&s->Compiler->Base.Pool, sizeof(*v));
 401                                                 memset(v, 0, sizeof(struct reg_value));
 402                                                 v->Writer = pairinst;
 403                                                 if (t->Value[j]) {
 404                                                         pairinst->NumDependencies++;
 405                                                         t->Value[j]->Next = v;
 406                                                 }
 407                                                 t->Value[j] = v;
 408                                                 pairinst->Values[j] = v;
 409                                         }
 410                                 }
 411                         }
 412                 }
 413
 414                 if (s->Verbose)
 415                         _mesa_printf("scan(%i): NumDeps = %i\n", ip, pairinst->NumDependencies);
 416
 417                 if (!pairinst->NumDependencies)
 418                         instruction_ready(s, pairinst);
 419         }
 420
 421         /* Clear the PROGRAM_TEMPORARY state */
 422         int i, j;
 423         for(i = 0; i < MAX_PROGRAM_TEMPS; ++i) {
 424                 for(j = 0; j < 4; ++j)
 425                         s->Temps[i].Value[j] = 0;
 426         }
 427 }
 428
 429
 430 static void decrement_dependencies(struct pair_state *s, struct pair_state_instruction *pairinst)
 431 {
 432         ASSERT(pairinst->NumDependencies > 0);
 433         if (!--pairinst->NumDependencies)
 434                 instruction_ready(s, pairinst);
 435 }
 436
 437 /**
 438  * Update the dependency tracking state based on what the instruction
 439  * at the given IP does.
 440  */
 441 static void commit_instruction(struct pair_state *s, struct pair_state_instruction *pairinst)
 442 {
 443         struct prog_instruction *inst = &pairinst->Instruction;
 444
 445         if (s->Verbose)
 446                 _mesa_printf("commit_instruction(%i)\n", pairinst->IP);
 447
 448         if (inst->DstReg.File == PROGRAM_TEMPORARY) {
 449                 struct pair_register_translation *t = &s->Temps[inst->DstReg.Index];
 450                 deref_hw_reg(s, t->HwIndex);
 451
 452                 int i;
 453                 for(i = 0; i < 4; ++i) {
 454                         if (!GET_BIT(inst->DstReg.WriteMask, i))
 455                                 continue;
 456
 457                         t->Value[i] = pairinst->Values[i];
 458                         if (t->Value[i]->NumReaders) {
 459                                 struct reg_value_reader *r;
 460                                 for(r = pairinst->Values[i]->Readers; r; r = r->Next)
 461                                         decrement_dependencies(s, r->Reader);
 462                         } else if (t->Value[i]->Next) {
 463                                 /* This happens when the only reader writes
 464                                  * the register at the same time */
 465                                 decrement_dependencies(s, t->Value[i]->Next->Writer);
 466                         }
 467                 }
 468         }
 469
 470         int nsrc = _mesa_num_inst_src_regs(inst->Opcode);
 471         int i;
 472         for(i = 0; i < nsrc; i++) {
 473                 struct pair_register_translation *t = get_register(s, inst->SrcReg[i].File, inst->SrcReg[i].Index);
 474                 if (!t)
 475                         continue;
 476
 477                 deref_hw_reg(s, get_hw_reg(s, inst->SrcReg[i].File, inst->SrcReg[i].Index));
 478
 479                 if (inst->SrcReg[i].File != PROGRAM_TEMPORARY)
 480                         continue;
 481
 482                 int j;
 483                 for(j = 0; j < 4; ++j) {
 484                         GLuint swz = GET_SWZ(inst->SrcReg[i].Swizzle, j);
 485                         if (swz >= 4)
 486                                 continue;
 487                         if (!t->Value[swz])
 488                                 continue;
 489
 490                         /* Do not free a dependency if this instruction
 491                          * also rewrites the value. See scan_instructions. */
 492                         if (inst->DstReg.File == PROGRAM_TEMPORARY &&
 493                             inst->DstReg.Index == inst->SrcReg[i].Index &&
 494                             GET_BIT(inst->DstReg.WriteMask, swz))
 495                                 continue;
 496
 497                         if (!--t->Value[swz]->NumReaders) {
 498                                 if (t->Value[swz]->Next)
 499                                         decrement_dependencies(s, t->Value[swz]->Next->Writer);
 500                         }
 501                 }
 502         }
 503 }
 504
 505
 506 /**
 507  * Emit all ready texture instructions in a single block.
 508  *
 509  * Emit as a single block to (hopefully) sample many textures in parallel,
 510  * and to avoid hardware indirections on R300.
 511  *
 512  * In R500, we don't really know when the result of a texture instruction
 513  * arrives. So allocate all destinations first, to make sure they do not
 514  * arrive early and overwrite a texture coordinate we're going to use later
 515  * in the block.
 516  */
 517 static void emit_all_tex(struct pair_state *s)
 518 {
 519         struct pair_state_instruction *readytex;
 520         struct pair_state_instruction *pairinst;
 521
 522         ASSERT(s->ReadyTEX);
 523
 524         // Don't let the ready list change under us!
 525         readytex = s->ReadyTEX;
 526         s->ReadyTEX = 0;
 527
 528         // Allocate destination hardware registers in one block to avoid conflicts.
 529         for(pairinst = readytex; pairinst; pairinst = pairinst->NextReady) {
 530                 struct prog_instruction *inst = &pairinst->Instruction;
 531                 if (inst->Opcode != OPCODE_KIL)
 532                         get_hw_reg(s, inst->DstReg.File, inst->DstReg.Index);
 533         }
 534
 535         if (s->Compiler->Base.Debug)
 536                 _mesa_printf(" BEGIN_TEX\n");
 537
 538         if (s->Handler->BeginTexBlock)
 539                 s->Compiler->Base.Error = s->Compiler->Base.Error || !s->Handler->BeginTexBlock(s->UserData);
 540
 541         for(pairinst = readytex; pairinst; pairinst = pairinst->NextReady) {
 542                 struct prog_instruction *inst = &pairinst->Instruction;
 543                 commit_instruction(s, pairinst);
 544
 545                 if (inst->Opcode != OPCODE_KIL)
 546                         inst->DstReg.Index = get_hw_reg(s, inst->DstReg.File, inst->DstReg.Index);
 547                 inst->SrcReg[0].Index = get_hw_reg(s, inst->SrcReg[0].File, inst->SrcReg[0].Index);
 548
 549                 if (s->Compiler->Base.Debug) {
 550                         _mesa_printf("   ");
 551                         _mesa_print_instruction(inst);
 552                         fflush(stderr);
 553                 }
 554
 555                 struct radeon_pair_texture_instruction rpti;
 556
 557                 switch(inst->Opcode) {
 558                 case OPCODE_TEX: rpti.Opcode = RADEON_OPCODE_TEX; break;
 559                 case OPCODE_TXB: rpti.Opcode = RADEON_OPCODE_TXB; break;
 560                 case OPCODE_TXP: rpti.Opcode = RADEON_OPCODE_TXP; break;
 561                 default:
 562                 case OPCODE_KIL: rpti.Opcode = RADEON_OPCODE_KIL; break;
 563                 }
 564
 565                 rpti.DestIndex = inst->DstReg.Index;
 566                 rpti.WriteMask = inst->DstReg.WriteMask;
 567                 rpti.TexSrcUnit = inst->TexSrcUnit;
 568                 rpti.TexSrcTarget = inst->TexSrcTarget;
 569                 rpti.SrcIndex = inst->SrcReg[0].Index;
 570                 rpti.SrcSwizzle = inst->SrcReg[0].Swizzle;
 571
 572                 s->Compiler->Base.Error = s->Compiler->Base.Error || !s->Handler->EmitTex(s->UserData, &rpti);
 573         }
 574
 575         if (s->Compiler->Base.Debug)
 576                 _mesa_printf(" END_TEX\n");
 577 }
 578
 579
 580 static int alloc_pair_source(struct pair_state *s, struct radeon_pair_instruction *pair,
 581         struct prog_src_register src, GLboolean rgb, GLboolean alpha)
 582 {
 583         int candidate = -1;
 584         int candidate_quality = -1;
 585         int i;
 586
 587         if (!rgb && !alpha)
 588                 return 0;
 589
 590         GLuint constant;
 591         GLuint index;
 592
 593         if (src.File == PROGRAM_TEMPORARY || src.File == PROGRAM_INPUT) {
 594                 constant = 0;
 595                 index = get_hw_reg(s, src.File, src.Index);
 596         } else {
 597                 constant = 1;
 598                 index = src.Index;
 599         }
 600
 601         for(i = 0; i < 3; ++i) {
 602                 int q = 0;
 603                 if (rgb) {
 604                         if (pair->RGB.Src[i].Used) {
 605                                 if (pair->RGB.Src[i].Constant != constant ||
 606                                     pair->RGB.Src[i].Index != index)
 607                                         continue;
 608                                 q++;
 609                         }
 610                 }
 611                 if (alpha) {
 612                         if (pair->Alpha.Src[i].Used) {
 613                                 if (pair->Alpha.Src[i].Constant != constant ||
 614                                     pair->Alpha.Src[i].Index != index)
 615                                         continue;
 616                                 q++;
 617                         }
 618                 }
 619                 if (q > candidate_quality) {
 620                         candidate_quality = q;
 621                         candidate = i;
 622                 }
 623         }
 624
 625         if (candidate >= 0) {
 626                 if (rgb) {
 627                         pair->RGB.Src[candidate].Used = 1;
 628                         pair->RGB.Src[candidate].Constant = constant;
 629                         pair->RGB.Src[candidate].Index = index;
 630                 }
 631                 if (alpha) {
 632                         pair->Alpha.Src[candidate].Used = 1;
 633                         pair->Alpha.Src[candidate].Constant = constant;
 634                         pair->Alpha.Src[candidate].Index = index;
 635                 }
 636         }
 637
 638         return candidate;
 639 }
 640
 641 /**
 642  * Fill the given ALU instruction's opcodes and source operands into the given pair,
 643  * if possible.
 644  */
 645 static GLboolean fill_instruction_into_pair(
 646         struct pair_state *s,
 647         struct radeon_pair_instruction *pair,
 648         struct pair_state_instruction *pairinst)
 649 {
 650         struct prog_instruction *inst = &pairinst->Instruction;
 651
 652         ASSERT(!pairinst->NeedRGB || pair->RGB.Opcode == OPCODE_NOP);
 653         ASSERT(!pairinst->NeedAlpha || pair->Alpha.Opcode == OPCODE_NOP);
 654
 655         if (pairinst->NeedRGB) {
 656                 if (pairinst->IsTranscendent)
 657                         pair->RGB.Opcode = OPCODE_REPL_ALPHA;
 658                 else
 659                         pair->RGB.Opcode = inst->Opcode;
 660                 if (inst->SaturateMode == SATURATE_ZERO_ONE)
 661                         pair->RGB.Saturate = 1;
 662         }
 663         if (pairinst->NeedAlpha) {
 664                 pair->Alpha.Opcode = inst->Opcode;
 665                 if (inst->SaturateMode == SATURATE_ZERO_ONE)
 666                         pair->Alpha.Saturate = 1;
 667         }
 668
 669         int nargs = _mesa_num_inst_src_regs(inst->Opcode);
 670         int i;
 671
 672         /* Special case for DDX/DDY (MDH/MDV). */
 673         if (inst->Opcode == OPCODE_DDX || inst->Opcode == OPCODE_DDY) {
 674                 if (pair->RGB.Src[0].Used || pair->Alpha.Src[0].Used)
 675                         return GL_FALSE;
 676                 else
 677                         nargs++;
 678         }
 679
 680         for(i = 0; i < nargs; ++i) {
 681                 int source;
 682                 if (pairinst->NeedRGB && !pairinst->IsTranscendent) {
 683                         GLboolean srcrgb = GL_FALSE;
 684                         GLboolean srcalpha = GL_FALSE;
 685                         int j;
 686                         for(j = 0; j < 3; ++j) {
 687                                 GLuint swz = GET_SWZ(inst->SrcReg[i].Swizzle, j);
 688                                 if (swz < 3)
 689                                         srcrgb = GL_TRUE;
 690                                 else if (swz < 4)
 691                                         srcalpha = GL_TRUE;
 692                         }
 693                         source = alloc_pair_source(s, pair, inst->SrcReg[i], srcrgb, srcalpha);
 694                         if (source < 0)
 695                                 return GL_FALSE;
 696                         pair->RGB.Arg[i].Source = source;
 697                         pair->RGB.Arg[i].Swizzle = inst->SrcReg[i].Swizzle & 0x1ff;
 698                         pair->RGB.Arg[i].Abs = inst->SrcReg[i].Abs;
 699                         pair->RGB.Arg[i].Negate = !!(inst->SrcReg[i].Negate & (NEGATE_X | NEGATE_Y | NEGATE_Z));
 700                 }
 701                 if (pairinst->NeedAlpha) {
 702                         GLboolean srcrgb = GL_FALSE;
 703                         GLboolean srcalpha = GL_FALSE;
 704                         GLuint swz = GET_SWZ(inst->SrcReg[i].Swizzle, pairinst->IsTranscendent ? 0 : 3);
 705                         if (swz < 3)
 706                                 srcrgb = GL_TRUE;
 707                         else if (swz < 4)
 708                                 srcalpha = GL_TRUE;
 709                         source = alloc_pair_source(s, pair, inst->SrcReg[i], srcrgb, srcalpha);
 710                         if (source < 0)
 711                                 return GL_FALSE;
 712                         pair->Alpha.Arg[i].Source = source;
 713                         pair->Alpha.Arg[i].Swizzle = swz;
 714                         pair->Alpha.Arg[i].Abs = inst->SrcReg[i].Abs;
 715                         pair->Alpha.Arg[i].Negate = !!(inst->SrcReg[i].Negate & NEGATE_W);
 716                 }
 717         }
 718
 719         return GL_TRUE;
 720 }
 721
 722
 723 /**
 724  * Fill in the destination register information.
 725  *
 726  * This is split from filling in source registers because we want
 727  * to avoid allocating hardware temporaries for destinations until
 728  * we are absolutely certain that we're going to emit a certain
 729  * instruction pairing.
 730  */
 731 static void fill_dest_into_pair(
 732         struct pair_state *s,
 733         struct radeon_pair_instruction *pair,
 734         struct pair_state_instruction *pairinst)
 735 {
 736         struct prog_instruction *inst = &pairinst->Instruction;
 737
 738         if (inst->DstReg.File == PROGRAM_OUTPUT) {
 739                 if (inst->DstReg.Index == s->Compiler->OutputColor) {
 740                         pair->RGB.OutputWriteMask |= inst->DstReg.WriteMask & WRITEMASK_XYZ;
 741                         pair->Alpha.OutputWriteMask |= GET_BIT(inst->DstReg.WriteMask, 3);
 742                 } else if (inst->DstReg.Index == s->Compiler->OutputDepth) {
 743                         pair->Alpha.DepthWriteMask |= GET_BIT(inst->DstReg.WriteMask, 3);
 744                 }
 745         } else {
 746                 GLuint hwindex = get_hw_reg(s, inst->DstReg.File, inst->DstReg.Index);
 747                 if (pairinst->NeedRGB) {
 748                         pair->RGB.DestIndex = hwindex;
 749                         pair->RGB.WriteMask |= inst->DstReg.WriteMask & WRITEMASK_XYZ;
 750                 }
 751                 if (pairinst->NeedAlpha) {
 752                         pair->Alpha.DestIndex = hwindex;
 753                         pair->Alpha.WriteMask |= GET_BIT(inst->DstReg.WriteMask, 3);
 754                 }
 755         }
 756 }
 757
 758
 759 /**
 760  * Find a good ALU instruction or pair of ALU instruction and emit it.
 761  *
 762  * Prefer emitting full ALU instructions, so that when we reach a point
 763  * where no full ALU instruction can be emitted, we have more candidates
 764  * for RGB/Alpha pairing.
 765  */
 766 static void emit_alu(struct pair_state *s)
 767 {
 768         struct radeon_pair_instruction pair;
 769         struct pair_state_instruction *psi;
 770
 771         if (s->ReadyFullALU || !(s->ReadyRGB && s->ReadyAlpha)) {
 772                 if (s->ReadyFullALU) {
 773                         psi = s->ReadyFullALU;
 774                         s->ReadyFullALU = s->ReadyFullALU->NextReady;
 775                 } else if (s->ReadyRGB) {
 776                         psi = s->ReadyRGB;
 777                         s->ReadyRGB = s->ReadyRGB->NextReady;
 778                 } else {
 779                         psi = s->ReadyAlpha;
 780                         s->ReadyAlpha = s->ReadyAlpha->NextReady;
 781                 }
 782
 783                 _mesa_bzero(&pair, sizeof(pair));
 784                 fill_instruction_into_pair(s, &pair, psi);
 785                 fill_dest_into_pair(s, &pair, psi);
 786                 commit_instruction(s, psi);
 787         } else {
 788                 struct pair_state_instruction **prgb;
 789                 struct pair_state_instruction **palpha;
 790
 791                 /* Some pairings might fail because they require too
 792                  * many source slots; try all possible pairings if necessary */
 793                 for(prgb = &s->ReadyRGB; *prgb; prgb = &(*prgb)->NextReady) {
 794                         for(palpha = &s->ReadyAlpha; *palpha; palpha = &(*palpha)->NextReady) {
 795                                 struct pair_state_instruction * psirgb = *prgb;
 796                                 struct pair_state_instruction * psialpha = *palpha;
 797                                 _mesa_bzero(&pair, sizeof(pair));
 798                                 fill_instruction_into_pair(s, &pair, psirgb);
 799                                 if (!fill_instruction_into_pair(s, &pair, psialpha))
 800                                         continue;
 801                                 *prgb = (*prgb)->NextReady;
 802                                 *palpha = (*palpha)->NextReady;
 803                                 fill_dest_into_pair(s, &pair, psirgb);
 804                                 fill_dest_into_pair(s, &pair, psialpha);
 805                                 commit_instruction(s, psirgb);
 806                                 commit_instruction(s, psialpha);
 807                                 goto success;
 808                         }
 809                 }
 810
 811                 /* No success in pairing; just take the first RGB instruction */
 812                 psi = s->ReadyRGB;
 813                 s->ReadyRGB = s->ReadyRGB->NextReady;
 814
 815                 _mesa_bzero(&pair, sizeof(pair));
 816                 fill_instruction_into_pair(s, &pair, psi);
 817                 fill_dest_into_pair(s, &pair, psi);
 818                 commit_instruction(s, psi);
 819         success: ;
 820         }
 821
 822         if (s->Compiler->Base.Debug)
 823                 radeonPrintPairInstruction(&pair);
 824
 825         s->Compiler->Base.Error = s->Compiler->Base.Error || !s->Handler->EmitPaired(s->UserData, &pair);
 826 }
 827
 828 /* Callback function for assigning input registers to hardware registers */
 829 static void alloc_helper(void * data, unsigned input, unsigned hwreg)
 830 {
 831         struct pair_state * s = data;
 832         alloc_hw_reg(s, PROGRAM_INPUT, input, hwreg);
 833 }
 834
 835 void radeonPairProgram(
 836         struct r300_fragment_program_compiler * compiler,
 837         const struct radeon_pair_handler* handler, void *userdata)
 838 {
 839         struct pair_state s;
 840
 841         _mesa_bzero(&s, sizeof(s));
 842         s.Compiler = compiler;
 843         s.Handler = handler;
 844         s.UserData = userdata;
 845         s.Verbose = GL_FALSE && s.Compiler->Base.Debug;
 846
 847         if (s.Compiler->Base.Debug)
 848                 _mesa_printf("Emit paired program\n");
 849
 850         scan_instructions(&s);
 851         s.Compiler->AllocateHwInputs(s.Compiler, &alloc_helper, &s);
 852
 853         while(!s.Compiler->Base.Error &&
 854               (s.ReadyTEX || s.ReadyRGB || s.ReadyAlpha || s.ReadyFullALU)) {
 855                 if (s.ReadyTEX)
 856                         emit_all_tex(&s);
 857
 858                 while(s.ReadyFullALU || s.ReadyRGB || s.ReadyAlpha)
 859                         emit_alu(&s);
 860         }
 861
 862         if (s.Compiler->Base.Debug)
 863                 _mesa_printf(" END\n");
 864 }
 865
 866
 867 static void print_pair_src(int i, struct radeon_pair_instruction_source* src)
 868 {
 869         _mesa_printf("  Src%i = %s[%i]", i, src->Constant ? "CNST" : "TEMP", src->Index);
 870 }
 871
 872 static const char* opcode_string(GLuint opcode)
 873 {
 874         if (opcode == OPCODE_REPL_ALPHA)
 875                 return "SOP";
 876         else
 877                 return _mesa_opcode_string(opcode);
 878 }
 879
 880 static int num_pairinst_args(GLuint opcode)
 881 {
 882         if (opcode == OPCODE_REPL_ALPHA)
 883                 return 0;
 884         else
 885                 return _mesa_num_inst_src_regs(opcode);
 886 }
 887
 888 static char swizzle_char(GLuint swz)
 889 {
 890         switch(swz) {
 891         case SWIZZLE_X: return 'x';
 892         case SWIZZLE_Y: return 'y';
 893         case SWIZZLE_Z: return 'z';
 894         case SWIZZLE_W: return 'w';
 895         case SWIZZLE_ZERO: return '0';
 896         case SWIZZLE_ONE: return '1';
 897         case SWIZZLE_NIL: return '_';
 898         default: return '?';
 899         }
 900 }
 901
 902 void radeonPrintPairInstruction(struct radeon_pair_instruction *inst)
 903 {
 904         int nargs;
 905         int i;
 906
 907         _mesa_printf("       RGB:  ");
 908         for(i = 0; i < 3; ++i) {
 909                 if (inst->RGB.Src[i].Used)
 910                         print_pair_src(i, inst->RGB.Src + i);
 911         }
 912         _mesa_printf("\n");
 913         _mesa_printf("       Alpha:");
 914         for(i = 0; i < 3; ++i) {
 915                 if (inst->Alpha.Src[i].Used)
 916                         print_pair_src(i, inst->Alpha.Src + i);
 917         }
 918         _mesa_printf("\n");
 919
 920         _mesa_printf("  %s%s", opcode_string(inst->RGB.Opcode), inst->RGB.Saturate ? "_SAT" : "");
 921         if (inst->RGB.WriteMask)
 922                 _mesa_printf(" TEMP[%i].%s%s%s", inst->RGB.DestIndex,
 923                         (inst->RGB.WriteMask & 1) ? "x" : "",
 924                         (inst->RGB.WriteMask & 2) ? "y" : "",
 925                         (inst->RGB.WriteMask & 4) ? "z" : "");
 926         if (inst->RGB.OutputWriteMask)
 927                 _mesa_printf(" COLOR.%s%s%s",
 928                         (inst->RGB.OutputWriteMask & 1) ? "x" : "",
 929                         (inst->RGB.OutputWriteMask & 2) ? "y" : "",
 930                         (inst->RGB.OutputWriteMask & 4) ? "z" : "");
 931         nargs = num_pairinst_args(inst->RGB.Opcode);
 932         for(i = 0; i < nargs; ++i) {
 933                 const char* abs = inst->RGB.Arg[i].Abs ? "|" : "";
 934                 const char* neg = inst->RGB.Arg[i].Negate ? "-" : "";
 935                 _mesa_printf(", %s%sSrc%i.%c%c%c%s", neg, abs, inst->RGB.Arg[i].Source,
 936                         swizzle_char(GET_SWZ(inst->RGB.Arg[i].Swizzle, 0)),
 937                         swizzle_char(GET_SWZ(inst->RGB.Arg[i].Swizzle, 1)),
 938                         swizzle_char(GET_SWZ(inst->RGB.Arg[i].Swizzle, 2)),
 939                         abs);
 940         }
 941         _mesa_printf("\n");
 942
 943         _mesa_printf("  %s%s", opcode_string(inst->Alpha.Opcode), inst->Alpha.Saturate ? "_SAT" : "");
 944         if (inst->Alpha.WriteMask)
 945                 _mesa_printf(" TEMP[%i].w", inst->Alpha.DestIndex);
 946         if (inst->Alpha.OutputWriteMask)
 947                 _mesa_printf(" COLOR.w");
 948         if (inst->Alpha.DepthWriteMask)
 949                 _mesa_printf(" DEPTH.w");
 950         nargs = num_pairinst_args(inst->Alpha.Opcode);
 951         for(i = 0; i < nargs; ++i) {
 952                 const char* abs = inst->Alpha.Arg[i].Abs ? "|" : "";
 953                 const char* neg = inst->Alpha.Arg[i].Negate ? "-" : "";
 954                 _mesa_printf(", %s%sSrc%i.%c%s", neg, abs, inst->Alpha.Arg[i].Source,
 955                         swizzle_char(inst->Alpha.Arg[i].Swizzle), abs);
 956         }
 957         _mesa_printf("\n");
 958 }