src/gallium/drivers/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         struct branchinfo * branch;
 110
 111         memory_pool_array_reserve(&s->C->Pool, struct branchinfo, s->BranchStack,
 112                         s->BranchStackSize, s->BranchStackReserved, 1);
 113
 114         branch = &s->BranchStack[s->BranchStackSize++];
 115         branch->HaveElse = 0;
 116         memcpy(&branch->StoreEndif, &s->R, sizeof(s->R));
 117 }
 118
 119 static unsigned char * get_used_ptr(struct deadcode_state *s, rc_register_file file, unsigned int index)
 120 {
 121         if (file == RC_FILE_OUTPUT || file == RC_FILE_TEMPORARY) {
 122                 if (index >= RC_REGISTER_MAX_INDEX) {
 123                         rc_error(s->C, "%s: index %i is out of bounds for file %i\n", __FUNCTION__, index, file);
 124                         return 0;
 125                 }
 126
 127                 if (file == RC_FILE_OUTPUT)
 128                         return &s->R.Output[index];
 129                 else
 130                         return &s->R.Temporary[index];
 131         } else if (file == RC_FILE_ADDRESS) {
 132                 return &s->R.Address;
 133         } else if (file == RC_FILE_SPECIAL) {
 134                 if (index >= RC_NUM_SPECIAL_REGISTERS) {
 135                         rc_error(s->C, "%s: special file index %i out of bounds\n", __FUNCTION__, index);
 136                         return 0;
 137                 }
 138
 139                 return &s->R.Special[index];
 140         }
 141
 142         return 0;
 143 }
 144
 145 static void mark_used(struct deadcode_state * s, rc_register_file file, unsigned int index, unsigned int mask)
 146 {
 147         unsigned char * pused = get_used_ptr(s, file, index);
 148         if (pused)
 149                 *pused |= mask;
 150 }
 151
 152 static void update_instruction(struct deadcode_state * s, struct rc_instruction * inst)
 153 {
 154         const struct rc_opcode_info * opcode = rc_get_opcode_info(inst->U.I.Opcode);
 155         struct instruction_state * insts = &s->Instructions[inst->IP];
 156         unsigned int usedmask = 0;
 157         unsigned int srcmasks[3];
 158
 159         if (opcode->HasDstReg) {
 160                 unsigned char * pused = get_used_ptr(s, inst->U.I.DstReg.File, inst->U.I.DstReg.Index);
 161                 if (pused) {
 162                         usedmask = *pused & inst->U.I.DstReg.WriteMask;
 163                         *pused &= ~usedmask;
 164                 }
 165         }
 166
 167         insts->WriteMask |= usedmask;
 168
 169         if (inst->U.I.WriteALUResult) {
 170                 unsigned char * pused = get_used_ptr(s, RC_FILE_SPECIAL, RC_SPECIAL_ALU_RESULT);
 171                 if (pused && *pused) {
 172                         if (inst->U.I.WriteALUResult == RC_ALURESULT_X)
 173                                 usedmask |= RC_MASK_X;
 174                         else if (inst->U.I.WriteALUResult == RC_ALURESULT_W)
 175                                 usedmask |= RC_MASK_W;
 176
 177                         *pused = 0;
 178                         insts->WriteALUResult = 1;
 179                 }
 180         }
 181
 182         rc_compute_sources_for_writemask(inst, usedmask, srcmasks);
 183
 184         for(unsigned int src = 0; src < opcode->NumSrcRegs; ++src) {
 185                 unsigned int refmask = 0;
 186                 unsigned int newsrcmask = srcmasks[src] & ~insts->SrcReg[src];
 187                 insts->SrcReg[src] |= newsrcmask;
 188
 189                 for(unsigned int chan = 0; chan < 4; ++chan) {
 190                         if (GET_BIT(newsrcmask, chan))
 191                                 refmask |= 1 << GET_SWZ(inst->U.I.SrcReg[src].Swizzle, chan);
 192                 }
 193
 194                 /* get rid of spurious bits from ZERO, ONE, etc. swizzles */
 195                 refmask &= RC_MASK_XYZW;
 196
 197                 if (!refmask)
 198                         continue;
 199
 200                 mark_used(s, inst->U.I.SrcReg[src].File, inst->U.I.SrcReg[src].Index, refmask);
 201
 202                 if (inst->U.I.SrcReg[src].RelAddr)
 203                         mark_used(s, RC_FILE_ADDRESS, 0, RC_MASK_X);
 204         }
 205 }
 206
 207 static void mark_output_use(void * data, unsigned int index, unsigned int mask)
 208 {
 209         struct deadcode_state * s = data;
 210
 211         mark_used(s, RC_FILE_OUTPUT, index, mask);
 212 }
 213
 214 void rc_dataflow_deadcode(struct radeon_compiler * c, void *user)
 215 {
 216         struct deadcode_state s;
 217         unsigned int nr_instructions;
 218         rc_dataflow_mark_outputs_fn dce = (rc_dataflow_mark_outputs_fn)user;
 219         unsigned int ip;
 220
 221         memset(&s, 0, sizeof(s));
 222         s.C = c;
 223
 224         nr_instructions = rc_recompute_ips(c);
 225         s.Instructions = memory_pool_malloc(&c->Pool, sizeof(struct instruction_state)*nr_instructions);
 226         memset(s.Instructions, 0, sizeof(struct instruction_state)*nr_instructions);
 227
 228         dce(c, &s, &mark_output_use);
 229
 230         for(struct rc_instruction * inst = c->Program.Instructions.Prev;
 231             inst != &c->Program.Instructions;
 232             inst = inst->Prev) {
 233                 const struct rc_opcode_info * opcode = rc_get_opcode_info(inst->U.I.Opcode);
 234
 235                 switch(opcode->Opcode){
 236                 /* Mark all sources in the loop body as used before doing
 237                  * normal deadcode analysis.  This is probably not optimal.
 238                  */
 239                 case RC_OPCODE_ENDLOOP:
 240                 {
 241                         int endloops = 1;
 242                         struct rc_instruction *ptr;
 243                         for(ptr = inst->Prev; endloops > 0; ptr = ptr->Prev){
 244                                 opcode = rc_get_opcode_info(ptr->U.I.Opcode);
 245                                 if(ptr->U.I.Opcode == RC_OPCODE_BGNLOOP){
 246                                         endloops--;
 247                                         continue;
 248                                 }
 249                                 if(ptr->U.I.Opcode == RC_OPCODE_ENDLOOP){
 250                                         endloops++;
 251                                         continue;
 252                                 }
 253                                 if(opcode->HasDstReg){
 254                                         int src = 0;
 255                                         unsigned int srcmasks[3];
 256                                         rc_compute_sources_for_writemask(ptr,
 257                                                 ptr->U.I.DstReg.WriteMask, srcmasks);
 258                                         for(src=0; src < opcode->NumSrcRegs; src++){
 259                                                 mark_used(&s,
 260                                                         ptr->U.I.SrcReg[src].File,
 261                                                         ptr->U.I.SrcReg[src].Index,
 262                                                         srcmasks[src]);
 263                                         }
 264                                 }
 265                         }
 266                         push_loop(&s);
 267                         break;
 268                 }
 269                 case RC_OPCODE_BRK:
 270                         push_break(&s);
 271                         break;
 272                 case RC_OPCODE_BGNLOOP:
 273                 {
 274                         unsigned int i;
 275                         struct loopinfo * loop = &s.LoopStack[s.LoopStackSize-1];
 276                         for(i = 0; i < loop->BreakCount; i++) {
 277                                 or_updatemasks(&s.R, &s.R, &loop->Breaks[i]);
 278                         }
 279                         break;
 280                 }
 281                 case RC_OPCODE_CONT:
 282                         break;
 283                 case RC_OPCODE_ENDIF:
 284                         push_branch(&s);
 285                         break;
 286                 default:
 287                         if (opcode->IsFlowControl && s.BranchStackSize) {
 288                                 struct branchinfo * branch = &s.BranchStack[s.BranchStackSize-1];
 289                                 if (opcode->Opcode == RC_OPCODE_IF) {
 290                                         or_updatemasks(&s.R,
 291                                                         &s.R,
 292                                                         branch->HaveElse ? &branch->StoreElse : &branch->StoreEndif);
 293
 294                                         s.BranchStackSize--;
 295                                 } else if (opcode->Opcode == RC_OPCODE_ELSE) {
 296                                         if (branch->HaveElse) {
 297                                                 rc_error(c, "%s: Multiple ELSE for one IF/ENDIF\n", __FUNCTION__);
 298                                         } else {
 299                                                 memcpy(&branch->StoreElse, &s.R, sizeof(s.R));
 300                                                 memcpy(&s.R, &branch->StoreEndif, sizeof(s.R));
 301                                                 branch->HaveElse = 1;
 302                                         }
 303                                 } else {
 304                                         rc_error(c, "%s: Unhandled control flow instruction %s\n", __FUNCTION__, opcode->Name);
 305                                 }
 306                         }
 307                 }
 308
 309                 update_instruction(&s, inst);
 310         }
 311
 312         ip = 0;
 313         for(struct rc_instruction * inst = c->Program.Instructions.Next;
 314             inst != &c->Program.Instructions;
 315             inst = inst->Next, ++ip) {
 316                 const struct rc_opcode_info * opcode = rc_get_opcode_info(inst->U.I.Opcode);
 317                 int dead = 1;
 318                 unsigned int srcmasks[3];
 319                 unsigned int usemask;
 320
 321                 if (!opcode->HasDstReg) {
 322                         dead = 0;
 323                 } else {
 324                         inst->U.I.DstReg.WriteMask = s.Instructions[ip].WriteMask;
 325                         if (s.Instructions[ip].WriteMask)
 326                                 dead = 0;
 327
 328                         if (s.Instructions[ip].WriteALUResult)
 329                                 dead = 0;
 330                         else
 331                                 inst->U.I.WriteALUResult = RC_ALURESULT_NONE;
 332                 }
 333
 334                 if (dead) {
 335                         struct rc_instruction * todelete = inst;
 336                         inst = inst->Prev;
 337                         rc_remove_instruction(todelete);
 338                         continue;
 339                 }
 340
 341                 usemask = s.Instructions[ip].WriteMask;
 342
 343                 if (inst->U.I.WriteALUResult == RC_ALURESULT_X)
 344                         usemask |= RC_MASK_X;
 345                 else if (inst->U.I.WriteALUResult == RC_ALURESULT_W)
 346                         usemask |= RC_MASK_W;
 347
 348                 rc_compute_sources_for_writemask(inst, usemask, srcmasks);
 349
 350                 for(unsigned int src = 0; src < 3; ++src) {
 351                         for(unsigned int chan = 0; chan < 4; ++chan) {
 352                                 if (!GET_BIT(srcmasks[src], chan))
 353                                         SET_SWZ(inst->U.I.SrcReg[src].Swizzle, chan, RC_SWIZZLE_UNUSED);
 354                         }
 355                 }
 356         }
 357
 358         rc_calculate_inputs_outputs(c);
 359 }