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 <stdio.h>
  39
  40 #include "memory_pool.h"
  41 #include "radeon_compiler.h"
  42
  43 #define error(fmt, args...) do { \
  44         rc_error(&s->Compiler->Base, "%s::%s(): " fmt "\n",     \
  45                 __FILE__, __FUNCTION__, ##args);        \
  46 } while(0)
  47
  48 struct pair_state_instruction {
  49         struct rc_sub_instruction Instruction;
  50         unsigned int IP; /**< Position of this instruction in original program */
  51
  52         unsigned int IsTex:1; /**< Is a texture instruction */
  53         unsigned int NeedRGB:1; /**< Needs the RGB ALU */
  54         unsigned int NeedAlpha:1; /**< Needs the Alpha ALU */
  55         unsigned int IsTranscendent:1; /**< Is a special transcendent instruction */
  56
  57         /**
  58          * Number of (read and write) dependencies that must be resolved before
  59          * this instruction can be scheduled.
  60          */
  61         unsigned int NumDependencies:5;
  62
  63         /**
  64          * Next instruction in the linked list of ready instructions.
  65          */
  66         struct pair_state_instruction *NextReady;
  67
  68         /**
  69          * Values that this instruction writes
  70          */
  71         struct reg_value *Values[4];
  72 };
  73
  74
  75 /**
  76  * Used to keep track of which instructions read a value.
  77  */
  78 struct reg_value_reader {
  79         struct pair_state_instruction *Reader;
  80         struct reg_value_reader *Next;
  81 };
  82
  83 /**
  84  * Used to keep track which values are stored in each component of a
  85  * RC_FILE_TEMPORARY.
  86  */
  87 struct reg_value {
  88         struct pair_state_instruction *Writer;
  89         struct reg_value *Next; /**< Pointer to the next value to be written to the same RC_FILE_TEMPORARY component */
  90
  91         /**
  92          * Unordered linked list of instructions that read from this value.
  93          */
  94         struct reg_value_reader *Readers;
  95
  96         /**
  97          * Number of readers of this value. This is calculated during @ref scan_instructions
  98          * and continually decremented during code emission.
  99          * When this count reaches zero, the instruction that writes the @ref Next value
 100          * can be scheduled.
 101          */
 102         unsigned int NumReaders;
 103 };
 104
 105 /**
 106  * Used to translate a RC_FILE_INPUT or RC_FILE_TEMPORARY Mesa register
 107  * to the proper hardware temporary.
 108  */
 109 struct pair_register_translation {
 110         unsigned int Allocated:1;
 111         unsigned int HwIndex:8;
 112         unsigned int RefCount:23; /**< # of times this occurs in an unscheduled instruction SrcReg or DstReg */
 113
 114         /**
 115          * Notes the value that is currently contained in each component
 116          * (only used for RC_FILE_TEMPORARY registers).
 117          */
 118         struct reg_value *Value[4];
 119 };
 120
 121 struct pair_state {
 122         struct r300_fragment_program_compiler * Compiler;
 123         const struct radeon_pair_handler *Handler;
 124         unsigned int Verbose;
 125         void *UserData;
 126
 127         /**
 128          * Translate Mesa registers to hardware registers
 129          */
 130         struct pair_register_translation Inputs[RC_REGISTER_MAX_INDEX];
 131         struct pair_register_translation Temps[RC_REGISTER_MAX_INDEX];
 132
 133         struct {
 134                 unsigned int RefCount; /**< # of times this occurs in an unscheduled SrcReg or DstReg */
 135         } HwTemps[128];
 136
 137         /**
 138          * Linked list of instructions that can be scheduled right now,
 139          * based on which ALU/TEX resources they require.
 140          */
 141         struct pair_state_instruction *ReadyFullALU;
 142         struct pair_state_instruction *ReadyRGB;
 143         struct pair_state_instruction *ReadyAlpha;
 144         struct pair_state_instruction *ReadyTEX;
 145 };
 146
 147
 148 static struct pair_register_translation *get_register(struct pair_state *s, rc_register_file file, unsigned int index)
 149 {
 150         switch(file) {
 151         case RC_FILE_TEMPORARY: return &s->Temps[index];
 152         case RC_FILE_INPUT: return &s->Inputs[index];
 153         default: return 0;
 154         }
 155 }
 156
 157 static void alloc_hw_reg(struct pair_state *s, rc_register_file file, unsigned int index, unsigned int hwindex)
 158 {
 159         struct pair_register_translation *t = get_register(s, file, index);
 160         assert(!s->HwTemps[hwindex].RefCount);
 161         assert(!t->Allocated);
 162         s->HwTemps[hwindex].RefCount = t->RefCount;
 163         t->Allocated = 1;
 164         t->HwIndex = hwindex;
 165 }
 166
 167 static unsigned int get_hw_reg(struct pair_state *s, rc_register_file file, unsigned int index)
 168 {
 169         unsigned int hwindex;
 170
 171         struct pair_register_translation *t = get_register(s, file, index);
 172         if (!t) {
 173                 error("get_hw_reg: %i[%i]\n", file, index);
 174                 return 0;
 175         }
 176
 177         if (t->Allocated)
 178                 return t->HwIndex;
 179
 180         for(hwindex = 0; hwindex < s->Handler->MaxHwTemps; ++hwindex)
 181                 if (!s->HwTemps[hwindex].RefCount)
 182                         break;
 183
 184         if (hwindex >= s->Handler->MaxHwTemps) {
 185                 error("Ran out of hardware temporaries");
 186                 return 0;
 187         }
 188
 189         alloc_hw_reg(s, file, index, hwindex);
 190         return hwindex;
 191 }
 192
 193
 194 static void deref_hw_reg(struct pair_state *s, unsigned int hwindex)
 195 {
 196         if (!s->HwTemps[hwindex].RefCount) {
 197                 error("Hwindex %i refcount error", hwindex);
 198                 return;
 199         }
 200
 201         s->HwTemps[hwindex].RefCount--;
 202 }
 203
 204 static void add_pairinst_to_list(struct pair_state_instruction **list, struct pair_state_instruction *pairinst)
 205 {
 206         pairinst->NextReady = *list;
 207         *list = pairinst;
 208 }
 209
 210 /**
 211  * The given instruction has become ready. Link it into the ready
 212  * instructions.
 213  */
 214 static void instruction_ready(struct pair_state *s, struct pair_state_instruction *pairinst)
 215 {
 216         if (s->Verbose)
 217                 fprintf(stderr, "instruction_ready(%i)\n", pairinst->IP);
 218
 219         if (pairinst->IsTex)
 220                 add_pairinst_to_list(&s->ReadyTEX, pairinst);
 221         else if (!pairinst->NeedAlpha)
 222                 add_pairinst_to_list(&s->ReadyRGB, pairinst);
 223         else if (!pairinst->NeedRGB)
 224                 add_pairinst_to_list(&s->ReadyAlpha, pairinst);
 225         else
 226                 add_pairinst_to_list(&s->ReadyFullALU, pairinst);
 227 }
 228
 229
 230 /**
 231  * Finally rewrite ADD, MOV, MUL as the appropriate native instruction
 232  * and reverse the order of arguments for CMP.
 233  */
 234 static void final_rewrite(struct pair_state *s, struct rc_sub_instruction *inst)
 235 {
 236         struct rc_src_register tmp;
 237
 238         switch(inst->Opcode) {
 239         case RC_OPCODE_ADD:
 240                 inst->SrcReg[2] = inst->SrcReg[1];
 241                 inst->SrcReg[1].File = RC_FILE_NONE;
 242                 inst->SrcReg[1].Swizzle = RC_SWIZZLE_1111;
 243                 inst->SrcReg[1].Negate = RC_MASK_NONE;
 244                 inst->Opcode = RC_OPCODE_MAD;
 245                 break;
 246         case RC_OPCODE_CMP:
 247                 tmp = inst->SrcReg[2];
 248                 inst->SrcReg[2] = inst->SrcReg[0];
 249                 inst->SrcReg[0] = tmp;
 250                 break;
 251         case RC_OPCODE_MOV:
 252                 /* AMD say we should use CMP.
 253                  * However, when we transform
 254                  *  KIL -r0;
 255                  * into
 256                  *  CMP tmp, -r0, -r0, 0;
 257                  *  KIL tmp;
 258                  * we get incorrect behaviour on R500 when r0 == 0.0.
 259                  * It appears that the R500 KIL hardware treats -0.0 as less
 260                  * than zero.
 261                  */
 262                 inst->SrcReg[1].File = RC_FILE_NONE;
 263                 inst->SrcReg[1].Swizzle = RC_SWIZZLE_1111;
 264                 inst->SrcReg[2].File = RC_FILE_NONE;
 265                 inst->SrcReg[2].Swizzle = RC_SWIZZLE_0000;
 266                 inst->Opcode = RC_OPCODE_MAD;
 267                 break;
 268         case RC_OPCODE_MUL:
 269                 inst->SrcReg[2].File = RC_FILE_NONE;
 270                 inst->SrcReg[2].Swizzle = RC_SWIZZLE_0000;
 271                 inst->Opcode = RC_OPCODE_MAD;
 272                 break;
 273         default:
 274                 /* nothing to do */
 275                 break;
 276         }
 277 }
 278
 279
 280 /**
 281  * Classify an instruction according to which ALUs etc. it needs
 282  */
 283 static void classify_instruction(struct pair_state *s,
 284         struct pair_state_instruction *psi)
 285 {
 286         psi->NeedRGB = (psi->Instruction.DstReg.WriteMask & RC_MASK_XYZ) ? 1 : 0;
 287         psi->NeedAlpha = (psi->Instruction.DstReg.WriteMask & RC_MASK_W) ? 1 : 0;
 288
 289         switch(psi->Instruction.Opcode) {
 290         case RC_OPCODE_ADD:
 291         case RC_OPCODE_CMP:
 292         case RC_OPCODE_DDX:
 293         case RC_OPCODE_DDY:
 294         case RC_OPCODE_FRC:
 295         case RC_OPCODE_MAD:
 296         case RC_OPCODE_MAX:
 297         case RC_OPCODE_MIN:
 298         case RC_OPCODE_MOV:
 299         case RC_OPCODE_MUL:
 300                 break;
 301         case RC_OPCODE_COS:
 302         case RC_OPCODE_EX2:
 303         case RC_OPCODE_LG2:
 304         case RC_OPCODE_RCP:
 305         case RC_OPCODE_RSQ:
 306         case RC_OPCODE_SIN:
 307                 psi->IsTranscendent = 1;
 308                 psi->NeedAlpha = 1;
 309                 break;
 310         case RC_OPCODE_DP4:
 311                 psi->NeedAlpha = 1;
 312                 /* fall through */
 313         case RC_OPCODE_DP3:
 314                 psi->NeedRGB = 1;
 315                 break;
 316         case RC_OPCODE_KIL:
 317         case RC_OPCODE_TEX:
 318         case RC_OPCODE_TXB:
 319         case RC_OPCODE_TXP:
 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         unsigned int 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                 const struct rc_opcode_info * opcode = rc_get_opcode_info(pairinst->Instruction.Opcode);
 350                 int j;
 351                 for(j = 0; j < opcode->NumSrcRegs; 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 == RC_FILE_TEMPORARY) {
 360                                 int i;
 361                                 for(i = 0; i < 4; ++i) {
 362                                         unsigned int 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 == RC_FILE_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                 if (opcode->HasDstReg) {
 388                         struct pair_register_translation *t =
 389                                 get_register(s, pairinst->Instruction.DstReg.File, pairinst->Instruction.DstReg.Index);
 390                         if (t) {
 391                                 t->RefCount++;
 392
 393                                 if (pairinst->Instruction.DstReg.File == RC_FILE_TEMPORARY) {
 394                                         int j;
 395                                         for(j = 0; j < 4; ++j) {
 396                                                 if (!GET_BIT(pairinst->Instruction.DstReg.WriteMask, j))
 397                                                         continue;
 398
 399                                                 struct reg_value* v = memory_pool_malloc(&s->Compiler->Base.Pool, sizeof(*v));
 400                                                 memset(v, 0, sizeof(struct reg_value));
 401                                                 v->Writer = pairinst;
 402                                                 if (t->Value[j]) {
 403                                                         pairinst->NumDependencies++;
 404                                                         t->Value[j]->Next = v;
 405                                                 }
 406                                                 t->Value[j] = v;
 407                                                 pairinst->Values[j] = v;
 408                                         }
 409                                 }
 410                         }
 411                 }
 412
 413                 if (s->Verbose)
 414                         fprintf(stderr, "scan(%i): NumDeps = %i\n", ip, pairinst->NumDependencies);
 415
 416                 if (!pairinst->NumDependencies)
 417                         instruction_ready(s, pairinst);
 418         }
 419
 420         /* Clear the RC_FILE_TEMPORARY state */
 421         int i, j;
 422         for(i = 0; i < RC_REGISTER_MAX_INDEX; ++i) {
 423                 for(j = 0; j < 4; ++j)
 424                         s->Temps[i].Value[j] = 0;
 425         }
 426 }
 427
 428
 429 static void decrement_dependencies(struct pair_state *s, struct pair_state_instruction *pairinst)
 430 {
 431         assert(pairinst->NumDependencies > 0);
 432         if (!--pairinst->NumDependencies)
 433                 instruction_ready(s, pairinst);
 434 }
 435
 436 /**
 437  * Update the dependency tracking state based on what the instruction
 438  * at the given IP does.
 439  */
 440 static void commit_instruction(struct pair_state *s, struct pair_state_instruction *pairinst)
 441 {
 442         struct rc_sub_instruction *inst = &pairinst->Instruction;
 443
 444         if (s->Verbose)
 445                 fprintf(stderr, "commit_instruction(%i)\n", pairinst->IP);
 446
 447         if (inst->DstReg.File == RC_FILE_TEMPORARY) {
 448                 struct pair_register_translation *t = &s->Temps[inst->DstReg.Index];
 449                 deref_hw_reg(s, t->HwIndex);
 450
 451                 int i;
 452                 for(i = 0; i < 4; ++i) {
 453                         if (!GET_BIT(inst->DstReg.WriteMask, i))
 454                                 continue;
 455
 456                         t->Value[i] = pairinst->Values[i];
 457                         if (t->Value[i]->NumReaders) {
 458                                 struct reg_value_reader *r;
 459                                 for(r = pairinst->Values[i]->Readers; r; r = r->Next)
 460                                         decrement_dependencies(s, r->Reader);
 461                         } else if (t->Value[i]->Next) {
 462                                 /* This happens when the only reader writes
 463                                  * the register at the same time */
 464                                 decrement_dependencies(s, t->Value[i]->Next->Writer);
 465                         }
 466                 }
 467         }
 468
 469         const struct rc_opcode_info * opcode = rc_get_opcode_info(inst->Opcode);
 470         int i;
 471         for(i = 0; i < opcode->NumSrcRegs; i++) {
 472                 struct pair_register_translation *t = get_register(s, inst->SrcReg[i].File, inst->SrcReg[i].Index);
 473                 if (!t)
 474                         continue;
 475
 476                 deref_hw_reg(s, get_hw_reg(s, inst->SrcReg[i].File, inst->SrcReg[i].Index));
 477
 478                 if (inst->SrcReg[i].File != RC_FILE_TEMPORARY)
 479                         continue;
 480
 481                 int j;
 482                 for(j = 0; j < 4; ++j) {
 483                         unsigned int swz = GET_SWZ(inst->SrcReg[i].Swizzle, j);
 484                         if (swz >= 4)
 485                                 continue;
 486                         if (!t->Value[swz])
 487                                 continue;
 488
 489                         /* Do not free a dependency if this instruction
 490                          * also rewrites the value. See scan_instructions. */
 491                         if (inst->DstReg.File == RC_FILE_TEMPORARY &&
 492                             inst->DstReg.Index == inst->SrcReg[i].Index &&
 493                             GET_BIT(inst->DstReg.WriteMask, swz))
 494                                 continue;
 495
 496                         if (!--t->Value[swz]->NumReaders) {
 497                                 if (t->Value[swz]->Next)
 498                                         decrement_dependencies(s, t->Value[swz]->Next->Writer);
 499                         }
 500                 }
 501         }
 502 }
 503
 504
 505 /**
 506  * Emit all ready texture instructions in a single block.
 507  *
 508  * Emit as a single block to (hopefully) sample many textures in parallel,
 509  * and to avoid hardware indirections on R300.
 510  *
 511  * In R500, we don't really know when the result of a texture instruction
 512  * arrives. So allocate all destinations first, to make sure they do not
 513  * arrive early and overwrite a texture coordinate we're going to use later
 514  * in the block.
 515  */
 516 static void emit_all_tex(struct pair_state *s)
 517 {
 518         struct pair_state_instruction *readytex;
 519         struct pair_state_instruction *pairinst;
 520
 521         assert(s->ReadyTEX);
 522
 523         // Don't let the ready list change under us!
 524         readytex = s->ReadyTEX;
 525         s->ReadyTEX = 0;
 526
 527         // Allocate destination hardware registers in one block to avoid conflicts.
 528         for(pairinst = readytex; pairinst; pairinst = pairinst->NextReady) {
 529                 struct rc_sub_instruction *inst = &pairinst->Instruction;
 530                 if (inst->Opcode != RC_OPCODE_KIL)
 531                         get_hw_reg(s, inst->DstReg.File, inst->DstReg.Index);
 532         }
 533
 534         if (s->Compiler->Base.Debug)
 535                 fprintf(stderr, " BEGIN_TEX\n");
 536
 537         if (s->Handler->BeginTexBlock)
 538                 s->Compiler->Base.Error = s->Compiler->Base.Error || !s->Handler->BeginTexBlock(s->UserData);
 539
 540         for(pairinst = readytex; pairinst; pairinst = pairinst->NextReady) {
 541                 struct rc_sub_instruction *inst = &pairinst->Instruction;
 542                 commit_instruction(s, pairinst);
 543
 544                 if (inst->Opcode != RC_OPCODE_KIL)
 545                         inst->DstReg.Index = get_hw_reg(s, inst->DstReg.File, inst->DstReg.Index);
 546                 inst->SrcReg[0].Index = get_hw_reg(s, inst->SrcReg[0].File, inst->SrcReg[0].Index);
 547
 548                 if (s->Compiler->Base.Debug) {
 549                         /* Should print the TEX instruction here */
 550                 }
 551
 552                 struct radeon_pair_texture_instruction rpti;
 553
 554                 switch(inst->Opcode) {
 555                 case RC_OPCODE_TEX: rpti.Opcode = RADEON_OPCODE_TEX; break;
 556                 case RC_OPCODE_TXB: rpti.Opcode = RADEON_OPCODE_TXB; break;
 557                 case RC_OPCODE_TXP: rpti.Opcode = RADEON_OPCODE_TXP; break;
 558                 default:
 559                 case RC_OPCODE_KIL: rpti.Opcode = RADEON_OPCODE_KIL; break;
 560                 }
 561
 562                 rpti.DestIndex = inst->DstReg.Index;
 563                 rpti.WriteMask = inst->DstReg.WriteMask;
 564                 rpti.TexSrcUnit = inst->TexSrcUnit;
 565                 rpti.TexSrcTarget = inst->TexSrcTarget;
 566                 rpti.SrcIndex = inst->SrcReg[0].Index;
 567                 rpti.SrcSwizzle = inst->SrcReg[0].Swizzle;
 568
 569                 s->Compiler->Base.Error = s->Compiler->Base.Error || !s->Handler->EmitTex(s->UserData, &rpti);
 570         }
 571
 572         if (s->Compiler->Base.Debug)
 573                 fprintf(stderr, " END_TEX\n");
 574 }
 575
 576
 577 static int alloc_pair_source(struct pair_state *s, struct radeon_pair_instruction *pair,
 578         struct rc_src_register src, unsigned int rgb, unsigned int alpha)
 579 {
 580         int candidate = -1;
 581         int candidate_quality = -1;
 582         int i;
 583
 584         if (!rgb && !alpha)
 585                 return 0;
 586
 587         unsigned int constant;
 588         unsigned int index;
 589
 590         if (src.File == RC_FILE_TEMPORARY || src.File == RC_FILE_INPUT) {
 591                 constant = 0;
 592                 index = get_hw_reg(s, src.File, src.Index);
 593         } else {
 594                 constant = 1;
 595                 index = src.Index;
 596         }
 597
 598         for(i = 0; i < 3; ++i) {
 599                 int q = 0;
 600                 if (rgb) {
 601                         if (pair->RGB.Src[i].Used) {
 602                                 if (pair->RGB.Src[i].Constant != constant ||
 603                                     pair->RGB.Src[i].Index != index)
 604                                         continue;
 605                                 q++;
 606                         }
 607                 }
 608                 if (alpha) {
 609                         if (pair->Alpha.Src[i].Used) {
 610                                 if (pair->Alpha.Src[i].Constant != constant ||
 611                                     pair->Alpha.Src[i].Index != index)
 612                                         continue;
 613                                 q++;
 614                         }
 615                 }
 616                 if (q > candidate_quality) {
 617                         candidate_quality = q;
 618                         candidate = i;
 619                 }
 620         }
 621
 622         if (candidate >= 0) {
 623                 if (rgb) {
 624                         pair->RGB.Src[candidate].Used = 1;
 625                         pair->RGB.Src[candidate].Constant = constant;
 626                         pair->RGB.Src[candidate].Index = index;
 627                 }
 628                 if (alpha) {
 629                         pair->Alpha.Src[candidate].Used = 1;
 630                         pair->Alpha.Src[candidate].Constant = constant;
 631                         pair->Alpha.Src[candidate].Index = index;
 632                 }
 633         }
 634
 635         return candidate;
 636 }
 637
 638 /**
 639  * Fill the given ALU instruction's opcodes and source operands into the given pair,
 640  * if possible.
 641  */
 642 static int fill_instruction_into_pair(
 643         struct pair_state *s,
 644         struct radeon_pair_instruction *pair,
 645         struct pair_state_instruction *pairinst)
 646 {
 647         struct rc_sub_instruction *inst = &pairinst->Instruction;
 648
 649         assert(!pairinst->NeedRGB || pair->RGB.Opcode == RC_OPCODE_NOP);
 650         assert(!pairinst->NeedAlpha || pair->Alpha.Opcode == RC_OPCODE_NOP);
 651
 652         if (pairinst->NeedRGB) {
 653                 if (pairinst->IsTranscendent)
 654                         pair->RGB.Opcode = RC_OPCODE_REPL_ALPHA;
 655                 else
 656                         pair->RGB.Opcode = inst->Opcode;
 657                 if (inst->SaturateMode == RC_SATURATE_ZERO_ONE)
 658                         pair->RGB.Saturate = 1;
 659         }
 660         if (pairinst->NeedAlpha) {
 661                 pair->Alpha.Opcode = inst->Opcode;
 662                 if (inst->SaturateMode == RC_SATURATE_ZERO_ONE)
 663                         pair->Alpha.Saturate = 1;
 664         }
 665
 666         const struct rc_opcode_info * opcode = rc_get_opcode_info(inst->Opcode);
 667         int nargs = opcode->NumSrcRegs;
 668         int i;
 669
 670         /* Special case for DDX/DDY (MDH/MDV). */
 671         if (inst->Opcode == RC_OPCODE_DDX || inst->Opcode == RC_OPCODE_DDY) {
 672                 if (pair->RGB.Src[0].Used || pair->Alpha.Src[0].Used)
 673                         return 0;
 674                 else
 675                         nargs++;
 676         }
 677
 678         for(i = 0; i < nargs; ++i) {
 679                 int source;
 680                 if (pairinst->NeedRGB && !pairinst->IsTranscendent) {
 681                         unsigned int srcrgb = 0;
 682                         unsigned int srcalpha = 0;
 683                         int j;
 684                         for(j = 0; j < 3; ++j) {
 685                                 unsigned int swz = GET_SWZ(inst->SrcReg[i].Swizzle, j);
 686                                 if (swz < 3)
 687                                         srcrgb = 1;
 688                                 else if (swz < 4)
 689                                         srcalpha = 1;
 690                         }
 691                         source = alloc_pair_source(s, pair, inst->SrcReg[i], srcrgb, srcalpha);
 692                         if (source < 0)
 693                                 return 0;
 694                         pair->RGB.Arg[i].Source = source;
 695                         pair->RGB.Arg[i].Swizzle = inst->SrcReg[i].Swizzle & 0x1ff;
 696                         pair->RGB.Arg[i].Abs = inst->SrcReg[i].Abs;
 697                         pair->RGB.Arg[i].Negate = !!(inst->SrcReg[i].Negate & (RC_MASK_X | RC_MASK_Y | RC_MASK_Z));
 698                 }
 699                 if (pairinst->NeedAlpha) {
 700                         unsigned int srcrgb = 0;
 701                         unsigned int srcalpha = 0;
 702                         unsigned int swz = GET_SWZ(inst->SrcReg[i].Swizzle, pairinst->IsTranscendent ? 0 : 3);
 703                         if (swz < 3)
 704                                 srcrgb = 1;
 705                         else if (swz < 4)
 706                                 srcalpha = 1;
 707                         source = alloc_pair_source(s, pair, inst->SrcReg[i], srcrgb, srcalpha);
 708                         if (source < 0)
 709                                 return 0;
 710                         pair->Alpha.Arg[i].Source = source;
 711                         pair->Alpha.Arg[i].Swizzle = swz;
 712                         pair->Alpha.Arg[i].Abs = inst->SrcReg[i].Abs;
 713                         pair->Alpha.Arg[i].Negate = !!(inst->SrcReg[i].Negate & RC_MASK_W);
 714                 }
 715         }
 716
 717         return 1;
 718 }
 719
 720
 721 /**
 722  * Fill in the destination register information.
 723  *
 724  * This is split from filling in source registers because we want
 725  * to avoid allocating hardware temporaries for destinations until
 726  * we are absolutely certain that we're going to emit a certain
 727  * instruction pairing.
 728  */
 729 static void fill_dest_into_pair(
 730         struct pair_state *s,
 731         struct radeon_pair_instruction *pair,
 732         struct pair_state_instruction *pairinst)
 733 {
 734         struct rc_sub_instruction *inst = &pairinst->Instruction;
 735
 736         if (inst->DstReg.File == RC_FILE_OUTPUT) {
 737                 if (inst->DstReg.Index == s->Compiler->OutputColor) {
 738                         pair->RGB.OutputWriteMask |= inst->DstReg.WriteMask & RC_MASK_XYZ;
 739                         pair->Alpha.OutputWriteMask |= GET_BIT(inst->DstReg.WriteMask, 3);
 740                 } else if (inst->DstReg.Index == s->Compiler->OutputDepth) {
 741                         pair->Alpha.DepthWriteMask |= GET_BIT(inst->DstReg.WriteMask, 3);
 742                 }
 743         } else {
 744                 unsigned int hwindex = get_hw_reg(s, inst->DstReg.File, inst->DstReg.Index);
 745                 if (pairinst->NeedRGB) {
 746                         pair->RGB.DestIndex = hwindex;
 747                         pair->RGB.WriteMask |= inst->DstReg.WriteMask & RC_MASK_XYZ;
 748                 }
 749                 if (pairinst->NeedAlpha) {
 750                         pair->Alpha.DestIndex = hwindex;
 751                         pair->Alpha.WriteMask |= GET_BIT(inst->DstReg.WriteMask, 3);
 752                 }
 753         }
 754 }
 755
 756
 757 /**
 758  * Find a good ALU instruction or pair of ALU instruction and emit it.
 759  *
 760  * Prefer emitting full ALU instructions, so that when we reach a point
 761  * where no full ALU instruction can be emitted, we have more candidates
 762  * for RGB/Alpha pairing.
 763  */
 764 static void emit_alu(struct pair_state *s)
 765 {
 766         struct radeon_pair_instruction pair;
 767         struct pair_state_instruction *psi;
 768
 769         if (s->ReadyFullALU || !(s->ReadyRGB && s->ReadyAlpha)) {
 770                 if (s->ReadyFullALU) {
 771                         psi = s->ReadyFullALU;
 772                         s->ReadyFullALU = s->ReadyFullALU->NextReady;
 773                 } else if (s->ReadyRGB) {
 774                         psi = s->ReadyRGB;
 775                         s->ReadyRGB = s->ReadyRGB->NextReady;
 776                 } else {
 777                         psi = s->ReadyAlpha;
 778                         s->ReadyAlpha = s->ReadyAlpha->NextReady;
 779                 }
 780
 781                 memset(&pair, 0, sizeof(pair));
 782                 fill_instruction_into_pair(s, &pair, psi);
 783                 fill_dest_into_pair(s, &pair, psi);
 784                 commit_instruction(s, psi);
 785         } else {
 786                 struct pair_state_instruction **prgb;
 787                 struct pair_state_instruction **palpha;
 788
 789                 /* Some pairings might fail because they require too
 790                  * many source slots; try all possible pairings if necessary */
 791                 for(prgb = &s->ReadyRGB; *prgb; prgb = &(*prgb)->NextReady) {
 792                         for(palpha = &s->ReadyAlpha; *palpha; palpha = &(*palpha)->NextReady) {
 793                                 struct pair_state_instruction * psirgb = *prgb;
 794                                 struct pair_state_instruction * psialpha = *palpha;
 795                                 memset(&pair, 0, sizeof(pair));
 796                                 fill_instruction_into_pair(s, &pair, psirgb);
 797                                 if (!fill_instruction_into_pair(s, &pair, psialpha))
 798                                         continue;
 799                                 *prgb = (*prgb)->NextReady;
 800                                 *palpha = (*palpha)->NextReady;
 801                                 fill_dest_into_pair(s, &pair, psirgb);
 802                                 fill_dest_into_pair(s, &pair, psialpha);
 803                                 commit_instruction(s, psirgb);
 804                                 commit_instruction(s, psialpha);
 805                                 goto success;
 806                         }
 807                 }
 808
 809                 /* No success in pairing; just take the first RGB instruction */
 810                 psi = s->ReadyRGB;
 811                 s->ReadyRGB = s->ReadyRGB->NextReady;
 812
 813                 memset(&pair, 0, sizeof(pair));
 814                 fill_instruction_into_pair(s, &pair, psi);
 815                 fill_dest_into_pair(s, &pair, psi);
 816                 commit_instruction(s, psi);
 817         success: ;
 818         }
 819
 820         if (s->Compiler->Base.Debug)
 821                 radeonPrintPairInstruction(&pair);
 822
 823         s->Compiler->Base.Error = s->Compiler->Base.Error || !s->Handler->EmitPaired(s->UserData, &pair);
 824 }
 825
 826 /* Callback function for assigning input registers to hardware registers */
 827 static void alloc_helper(void * data, unsigned input, unsigned hwreg)
 828 {
 829         struct pair_state * s = data;
 830         alloc_hw_reg(s, RC_FILE_INPUT, input, hwreg);
 831 }
 832
 833 void radeonPairProgram(
 834         struct r300_fragment_program_compiler * compiler,
 835         const struct radeon_pair_handler* handler, void *userdata)
 836 {
 837         struct pair_state s;
 838
 839         memset(&s, 0, sizeof(s));
 840         s.Compiler = compiler;
 841         s.Handler = handler;
 842         s.UserData = userdata;
 843         s.Verbose = 0 && s.Compiler->Base.Debug;
 844
 845         if (s.Compiler->Base.Debug)
 846                 fprintf(stderr, "Emit paired program\n");
 847
 848         scan_instructions(&s);
 849         s.Compiler->AllocateHwInputs(s.Compiler, &alloc_helper, &s);
 850
 851         while(!s.Compiler->Base.Error &&
 852               (s.ReadyTEX || s.ReadyRGB || s.ReadyAlpha || s.ReadyFullALU)) {
 853                 if (s.ReadyTEX)
 854                         emit_all_tex(&s);
 855
 856                 while(s.ReadyFullALU || s.ReadyRGB || s.ReadyAlpha)
 857                         emit_alu(&s);
 858         }
 859
 860         if (s.Compiler->Base.Debug)
 861                 fprintf(stderr, " END\n");
 862 }
 863
 864
 865 static void print_pair_src(int i, struct radeon_pair_instruction_source* src)
 866 {
 867         fprintf(stderr, "  Src%i = %s[%i]", i, src->Constant ? "CNST" : "TEMP", src->Index);
 868 }
 869
 870 static const char* opcode_string(rc_opcode opcode)
 871 {
 872         return rc_get_opcode_info(opcode)->Name;
 873 }
 874
 875 static int num_pairinst_args(rc_opcode opcode)
 876 {
 877         return rc_get_opcode_info(opcode)->NumSrcRegs;
 878 }
 879
 880 static char swizzle_char(rc_swizzle swz)
 881 {
 882         switch(swz) {
 883         case RC_SWIZZLE_X: return 'x';
 884         case RC_SWIZZLE_Y: return 'y';
 885         case RC_SWIZZLE_Z: return 'z';
 886         case RC_SWIZZLE_W: return 'w';
 887         case RC_SWIZZLE_ZERO: return '0';
 888         case RC_SWIZZLE_ONE: return '1';
 889         case RC_SWIZZLE_HALF: return 'H';
 890         case RC_SWIZZLE_UNUSED: return '_';
 891         default: return '?';
 892         }
 893 }
 894
 895 void radeonPrintPairInstruction(struct radeon_pair_instruction *inst)
 896 {
 897         int nargs;
 898         int i;
 899
 900         fprintf(stderr, "       RGB:  ");
 901         for(i = 0; i < 3; ++i) {
 902                 if (inst->RGB.Src[i].Used)
 903                         print_pair_src(i, inst->RGB.Src + i);
 904         }
 905         fprintf(stderr, "\n");
 906         fprintf(stderr, "       Alpha:");
 907         for(i = 0; i < 3; ++i) {
 908                 if (inst->Alpha.Src[i].Used)
 909                         print_pair_src(i, inst->Alpha.Src + i);
 910         }
 911         fprintf(stderr, "\n");
 912
 913         fprintf(stderr, "  %s%s", opcode_string(inst->RGB.Opcode), inst->RGB.Saturate ? "_SAT" : "");
 914         if (inst->RGB.WriteMask)
 915                 fprintf(stderr, " TEMP[%i].%s%s%s", inst->RGB.DestIndex,
 916                         (inst->RGB.WriteMask & 1) ? "x" : "",
 917                         (inst->RGB.WriteMask & 2) ? "y" : "",
 918                         (inst->RGB.WriteMask & 4) ? "z" : "");
 919         if (inst->RGB.OutputWriteMask)
 920                 fprintf(stderr, " COLOR.%s%s%s",
 921                         (inst->RGB.OutputWriteMask & 1) ? "x" : "",
 922                         (inst->RGB.OutputWriteMask & 2) ? "y" : "",
 923                         (inst->RGB.OutputWriteMask & 4) ? "z" : "");
 924         nargs = num_pairinst_args(inst->RGB.Opcode);
 925         for(i = 0; i < nargs; ++i) {
 926                 const char* abs = inst->RGB.Arg[i].Abs ? "|" : "";
 927                 const char* neg = inst->RGB.Arg[i].Negate ? "-" : "";
 928                 fprintf(stderr, ", %s%sSrc%i.%c%c%c%s", neg, abs, inst->RGB.Arg[i].Source,
 929                         swizzle_char(GET_SWZ(inst->RGB.Arg[i].Swizzle, 0)),
 930                         swizzle_char(GET_SWZ(inst->RGB.Arg[i].Swizzle, 1)),
 931                         swizzle_char(GET_SWZ(inst->RGB.Arg[i].Swizzle, 2)),
 932                         abs);
 933         }
 934         fprintf(stderr, "\n");
 935
 936         fprintf(stderr, "  %s%s", opcode_string(inst->Alpha.Opcode), inst->Alpha.Saturate ? "_SAT" : "");
 937         if (inst->Alpha.WriteMask)
 938                 fprintf(stderr, " TEMP[%i].w", inst->Alpha.DestIndex);
 939         if (inst->Alpha.OutputWriteMask)
 940                 fprintf(stderr, " COLOR.w");
 941         if (inst->Alpha.DepthWriteMask)
 942                 fprintf(stderr, " DEPTH.w");
 943         nargs = num_pairinst_args(inst->Alpha.Opcode);
 944         for(i = 0; i < nargs; ++i) {
 945                 const char* abs = inst->Alpha.Arg[i].Abs ? "|" : "";
 946                 const char* neg = inst->Alpha.Arg[i].Negate ? "-" : "";
 947                 fprintf(stderr, ", %s%sSrc%i.%c%s", neg, abs, inst->Alpha.Arg[i].Source,
 948                         swizzle_char(inst->Alpha.Arg[i].Swizzle), abs);
 949         }
 950         fprintf(stderr, "\n");
 951 }