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

   1 /*
   2  * Copyright (C) 2009 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 #include "radeon_dataflow.h"
  29
  30 #include "radeon_compiler.h"
  31
  32
  33 struct updatemask_state {
  34         unsigned char Output[RC_REGISTER_MAX_INDEX];
  35         unsigned char Temporary[RC_REGISTER_MAX_INDEX];
  36         unsigned char Address;
  37         unsigned char Special[RC_NUM_SPECIAL_REGISTERS];
  38 };
  39
  40 struct instruction_state {
  41         unsigned char WriteMask:4;
  42         unsigned char WriteALUResult:1;
  43         unsigned char SrcReg[3];
  44 };
  45
  46 struct loopinfo {
  47         struct updatemask_state * Breaks;
  48         unsigned int BreakCount;
  49         unsigned int BreaksReserved;
  50 };
  51
  52 struct branchinfo {
  53         unsigned int HaveElse:1;
  54
  55         struct updatemask_state StoreEndif;
  56         struct updatemask_state StoreElse;
  57 };
  58
  59 struct deadcode_state {
  60         struct radeon_compiler * C;
  61         struct instruction_state * Instructions;
  62
  63         struct updatemask_state R;
  64
  65         struct branchinfo * BranchStack;
  66         unsigned int BranchStackSize;
  67         unsigned int BranchStackReserved;
  68
  69         struct loopinfo * LoopStack;
  70         unsigned int LoopStackSize;
  71         unsigned int LoopStackReserved;
  72 };
  73
  74
  75 static void or_updatemasks(
  76         struct updatemask_state * dst,
  77         struct updatemask_state * a,
  78         struct updatemask_state * b)
  79 {
  80         for(unsigned int i = 0; i < RC_REGISTER_MAX_INDEX; ++i) {
  81                 dst->Output[i] = a->Output[i] | b->Output[i];
  82                 dst->Temporary[i] = a->Temporary[i] | b->Temporary[i];
  83         }
  84
  85         for(unsigned int i = 0; i < RC_NUM_SPECIAL_REGISTERS; ++i)
  86                 dst->Special[i] = a->Special[i] | b->Special[i];
  87
  88         dst->Address = a->Address | b->Address;
  89 }
  90
  91 static void push_break(struct deadcode_state *s)
  92 {
  93         struct loopinfo * loop = &s->LoopStack[s->LoopStackSize - 1];
  94         memory_pool_array_reserve(&s->C->Pool, struct updatemask_state,
  95                 loop->Breaks, loop->BreakCount, loop->BreaksReserved, 1);
  96
  97         memcpy(&loop->Breaks[loop->BreakCount++], &s->R, sizeof(s->R));
  98 }
  99
 100 static void push_loop(struct deadcode_state * s)
 101 {
 102         memory_pool_array_reserve(&s->C->Pool, struct loopinfo, s->LoopStack,
 103                         s->LoopStackSize, s->LoopStackReserved, 1);
 104         memset(&s->LoopStack[s->LoopStackSize++], 0, sizeof(struct loopinfo));
 105 }
 106
 107 static void push_branch(struct deadcode_state * s)
 108 {
 109         memory_pool_array_reserve(&s->C->Pool, struct branchinfo, s->BranchStack,
 110                         s->BranchStackSize, s->BranchStackReserved, 1);
 111
 112         struct branchinfo * branch = &s->BranchStack[s->BranchStackSize++];
 113         branch->HaveElse = 0;
 114         memcpy(&branch->StoreEndif, &s->R, sizeof(s->R));
 115 }
 116
 117 static unsigned char * get_used_ptr(struct deadcode_state *s, rc_register_file file, unsigned int index)
 118 {
 119         if (file == RC_FILE_OUTPUT || file == RC_FILE_TEMPORARY) {
 120                 if (index >= RC_REGISTER_MAX_INDEX) {
 121                         rc_error(s->C, "%s: index %i is out of bounds for file %i\n", __FUNCTION__, index, file);
 122                         return 0;
 123                 }
 124
 125                 if (file == RC_FILE_OUTPUT)
 126                         return &s->R.Output[index];
 127                 else
 128                         return &s->R.Temporary[index];
 129         } else if (file == RC_FILE_ADDRESS) {
 130                 return &s->R.Address;
 131         } else if (file == RC_FILE_SPECIAL) {
 132                 if (index >= RC_NUM_SPECIAL_REGISTERS) {
 133                         rc_error(s->C, "%s: special file index %i out of bounds\n", __FUNCTION__, index);
 134                         return 0;
 135                 }
 136
 137                 return &s->R.Special[index];
 138         }
 139
 140         return 0;
 141 }
 142
 143 static void mark_used(struct deadcode_state * s, rc_register_file file, unsigned int index, unsigned int mask)
 144 {
 145         unsigned char * pused = get_used_ptr(s, file, index);
 146         if (pused)
 147                 *pused |= mask;
 148 }
 149
 150 static void update_instruction(struct deadcode_state * s, struct rc_instruction * inst)
 151 {
 152         const struct rc_opcode_info * opcode = rc_get_opcode_info(inst->U.I.Opcode);
 153         struct instruction_state * insts = &s->Instructions[inst->IP];
 154         unsigned int usedmask = 0;
 155
 156         if (opcode->HasDstReg) {
 157                 unsigned char * pused = get_used_ptr(s, inst->U.I.DstReg.File, inst->U.I.DstReg.Index);
 158                 if (pused) {
 159                         usedmask = *pused & inst->U.I.DstReg.WriteMask;
 160                         if (!inst->U.I.DstReg.RelAddr)
 161                                 *pused &= ~usedmask;
 162                 }
 163
 164                 if (inst->U.I.DstReg.RelAddr)
 165                         mark_used(s, RC_FILE_ADDRESS, 0, RC_MASK_X);
 166         }
 167
 168         insts->WriteMask |= usedmask;
 169
 170         if (inst->U.I.WriteALUResult) {
 171                 unsigned char * pused = get_used_ptr(s, RC_FILE_SPECIAL, RC_SPECIAL_ALU_RESULT);
 172                 if (pused && *pused) {
 173                         if (inst->U.I.WriteALUResult == RC_ALURESULT_X)
 174                                 usedmask |= RC_MASK_X;
 175                         else if (inst->U.I.WriteALUResult == RC_ALURESULT_W)
 176                                 usedmask |= RC_MASK_W;
 177
 178                         *pused = 0;
 179                         insts->WriteALUResult = 1;
 180                 }
 181         }
 182
 183         unsigned int srcmasks[3];
 184         rc_compute_sources_for_writemask(inst, usedmask, srcmasks);
 185
 186         for(unsigned int src = 0; src < opcode->NumSrcRegs; ++src) {
 187                 unsigned int refmask = 0;
 188                 unsigned int newsrcmask = srcmasks[src] & ~insts->SrcReg[src];
 189                 insts->SrcReg[src] |= newsrcmask;
 190
 191                 for(unsigned int chan = 0; chan < 4; ++chan) {
 192                         if (GET_BIT(newsrcmask, chan))
 193                                 refmask |= 1 << GET_SWZ(inst->U.I.SrcReg[src].Swizzle, chan);
 194                 }
 195
 196                 /* get rid of spurious bits from ZERO, ONE, etc. swizzles */
 197                 refmask &= RC_MASK_XYZW;
 198
 199                 if (!refmask)
 200                         continue;
 201
 202                 mark_used(s, inst->U.I.SrcReg[src].File, inst->U.I.SrcReg[src].Index, refmask);
 203
 204                 if (inst->U.I.SrcReg[src].RelAddr)
 205                         mark_used(s, RC_FILE_ADDRESS, 0, RC_MASK_X);
 206         }
 207 }
 208
 209 static void mark_output_use(void * data, unsigned int index, unsigned int mask)
 210 {
 211         struct deadcode_state * s = data;
 212
 213         mark_used(s, RC_FILE_OUTPUT, index, mask);
 214 }
 215
 216 void rc_dataflow_deadcode(struct radeon_compiler * c, rc_dataflow_mark_outputs_fn dce, void * userdata)
 217 {
 218         struct deadcode_state s;
 219         unsigned int nr_instructions;
 220         unsigned has_temp_reladdr_src = 0;
 221
 222         memset(&s, 0, sizeof(s));
 223         s.C = c;
 224
 225         nr_instructions = rc_recompute_ips(c);
 226         s.Instructions = memory_pool_malloc(&c->Pool, sizeof(struct instruction_state)*nr_instructions);
 227         memset(s.Instructions, 0, sizeof(struct instruction_state)*nr_instructions);
 228
 229         dce(userdata, &s, &mark_output_use);
 230
 231         for(struct rc_instruction * inst = c->Program.Instructions.Prev;
 232             inst != &c->Program.Instructions;
 233             inst = inst->Prev) {
 234                 const struct rc_opcode_info * opcode = rc_get_opcode_info(inst->U.I.Opcode);
 235
 236                 switch(opcode->Opcode){
 237                 /* Mark all sources in the loop body as used before doing
 238                  * normal deadcode analysis.  This is probably not optimal.
 239                  */
 240                 case RC_OPCODE_ENDLOOP:
 241                 {
 242                         int endloops = 1;
 243                         struct rc_instruction *ptr;
 244                         for(ptr = inst->Prev; endloops > 0; ptr = ptr->Prev){
 245                                 opcode = rc_get_opcode_info(ptr->U.I.Opcode);
 246                                 if(ptr->U.I.Opcode == RC_OPCODE_BGNLOOP){
 247                                         endloops--;
 248                                         continue;
 249                                 }
 250                                 if(ptr->U.I.Opcode == RC_OPCODE_ENDLOOP){
 251                                         endloops++;
 252                                         continue;
 253                                 }
 254                                 if(opcode->HasDstReg){
 255                                         int src = 0;
 256                                         unsigned int srcmasks[3];
 257                                         rc_compute_sources_for_writemask(ptr,
 258                                                 ptr->U.I.DstReg.WriteMask, srcmasks);
 259                                         for(src=0; src < opcode->NumSrcRegs; src++){
 260                                                 mark_used(&s,
 261                                                         ptr->U.I.SrcReg[src].File,
 262                                                         ptr->U.I.SrcReg[src].Index,
 263                                                         srcmasks[src]);
 264                                         }
 265                                 }
 266                         }
 267                         push_loop(&s);
 268                         break;
 269                 }
 270                 case RC_OPCODE_BRK:
 271                         push_break(&s);
 272                         break;
 273                 case RC_OPCODE_BGNLOOP:
 274                 {
 275                         unsigned int i;
 276                         struct loopinfo * loop = &s.LoopStack[s.LoopStackSize-1];
 277                         for(i = 0; i < loop->BreakCount; i++) {
 278                                 or_updatemasks(&s.R, &s.R, &loop->Breaks[i]);
 279                         }
 280                         break;
 281                 }
 282                 case RC_OPCODE_CONT:
 283                         break;
 284                 case RC_OPCODE_ENDIF:
 285                         push_branch(&s);
 286                         break;
 287                 default:
 288                         if (opcode->IsFlowControl && s.BranchStackSize) {
 289                                 struct branchinfo * branch = &s.BranchStack[s.BranchStackSize-1];
 290                                 if (opcode->Opcode == RC_OPCODE_IF) {
 291                                         or_updatemasks(&s.R,
 292                                                         &s.R,
 293                                                         branch->HaveElse ? &branch->StoreElse : &branch->StoreEndif);
 294
 295                                         s.BranchStackSize--;
 296                                 } else if (opcode->Opcode == RC_OPCODE_ELSE) {
 297                                         if (branch->HaveElse) {
 298                                                 rc_error(c, "%s: Multiple ELSE for one IF/ENDIF\n", __FUNCTION__);
 299                                         } else {
 300                                                 memcpy(&branch->StoreElse, &s.R, sizeof(s.R));
 301                                                 memcpy(&s.R, &branch->StoreEndif, sizeof(s.R));
 302                                                 branch->HaveElse = 1;
 303                                         }
 304                                 } else {
 305                                         rc_error(c, "%s: Unhandled control flow instruction %s\n", __FUNCTION__, opcode->Name);
 306                                 }
 307                         }
 308
 309                         if (!has_temp_reladdr_src) {
 310                                 for (unsigned i = 0; i < opcode->NumSrcRegs; i++) {
 311                                         if (inst->U.I.SrcReg[i].File == RC_FILE_TEMPORARY &&
 312                                             inst->U.I.SrcReg[i].RelAddr) {
 313                                                 /* If there is a register read from a temporary file with relative addressing,
 314                                                  * mark all preceding written registers as used. */
 315                                                 for (struct rc_instruction *ptr = inst->Prev;
 316                                                      ptr != &c->Program.Instructions;
 317                                                      ptr = ptr->Prev) {
 318                                                         if (opcode->HasDstReg &&
 319                                                             ptr->U.I.DstReg.File == RC_FILE_TEMPORARY &&
 320                                                             ptr->U.I.DstReg.WriteMask) {
 321                                                                 mark_used(&s,
 322                                                                           ptr->U.I.DstReg.File,
 323                                                                           ptr->U.I.DstReg.Index,
 324                                                                           ptr->U.I.DstReg.WriteMask);
 325                                                         }
 326                                                 }
 327
 328                                                 has_temp_reladdr_src = 1;
 329                                         }
 330                                 }
 331                         }
 332                 }
 333
 334                 update_instruction(&s, inst);
 335         }
 336
 337         unsigned int ip = 0;
 338         for(struct rc_instruction * inst = c->Program.Instructions.Next;
 339             inst != &c->Program.Instructions;
 340             inst = inst->Next, ++ip) {
 341                 const struct rc_opcode_info * opcode = rc_get_opcode_info(inst->U.I.Opcode);
 342                 int dead = 1;
 343
 344                 if (!opcode->HasDstReg) {
 345                         dead = 0;
 346                 } else {
 347                         inst->U.I.DstReg.WriteMask = s.Instructions[ip].WriteMask;
 348                         if (s.Instructions[ip].WriteMask)
 349                                 dead = 0;
 350
 351                         if (s.Instructions[ip].WriteALUResult)
 352                                 dead = 0;
 353                         else
 354                                 inst->U.I.WriteALUResult = RC_ALURESULT_NONE;
 355                 }
 356
 357                 if (dead) {
 358                         struct rc_instruction * todelete = inst;
 359                         inst = inst->Prev;
 360                         rc_remove_instruction(todelete);
 361                         continue;
 362                 }
 363
 364                 unsigned int srcmasks[3];
 365                 unsigned int usemask = s.Instructions[ip].WriteMask;
 366
 367                 if (inst->U.I.WriteALUResult == RC_ALURESULT_X)
 368                         usemask |= RC_MASK_X;
 369                 else if (inst->U.I.WriteALUResult == RC_ALURESULT_W)
 370                         usemask |= RC_MASK_W;
 371
 372                 rc_compute_sources_for_writemask(inst, usemask, srcmasks);
 373
 374                 for(unsigned int src = 0; src < 3; ++src) {
 375                         for(unsigned int chan = 0; chan < 4; ++chan) {
 376                                 if (!GET_BIT(srcmasks[src], chan))
 377                                         SET_SWZ(inst->U.I.SrcReg[src].Swizzle, chan, RC_SWIZZLE_UNUSED);
 378                         }
 379                 }
 380         }
 381
 382         rc_calculate_inputs_outputs(c);
 383 }