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

   1 /*
   2  * Copyright 2010 Tom Stellard <tstellar@gmail.com>
   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
  32 #include "radeon_emulate_loops.h"
  33
  34 #include "radeon_compiler.h"
  35
  36 struct emulate_loop_state {
  37         struct radeon_compiler * C;
  38         struct loop_info * Loops;
  39         unsigned int LoopCount;
  40         unsigned int LoopReserved;
  41 };
  42
  43 struct loop_info {
  44         struct rc_instruction * BeginLoop;
  45         struct rc_instruction * EndLoop;
  46 };
  47
  48 static unsigned int loop_count_instructions(struct loop_info * loop)
  49 {
  50         unsigned int count = 0;
  51         struct rc_instruction * inst = loop->BeginLoop->Next;
  52         while(inst != loop->EndLoop){
  53                 count++;
  54                 inst = inst->Next;
  55         }
  56         return count;
  57 }
  58
  59 static unsigned int loop_calc_iterations(struct loop_info * loop,
  60                 unsigned int loop_count, unsigned int max_instructions)
  61 {
  62         unsigned int icount = loop_count_instructions(loop);
  63         return max_instructions / (loop_count * icount);
  64 }
  65
  66 static void loop_unroll(struct emulate_loop_state * s,
  67                         struct loop_info *loop, unsigned int iterations)
  68 {
  69         unsigned int i;
  70         struct rc_instruction * ptr;
  71         struct rc_instruction * first = loop->BeginLoop->Next;
  72         struct rc_instruction * last = loop->EndLoop->Prev;
  73         struct rc_instruction * append_to = last;
  74         rc_remove_instruction(loop->BeginLoop);
  75         rc_remove_instruction(loop->EndLoop);
  76         for( i = 1; i < iterations; i++){
  77                 for(ptr = first; ptr != last->Next; ptr = ptr->Next){
  78                         struct rc_instruction *new = rc_alloc_instruction(s->C);
  79                         memcpy(new, ptr, sizeof(struct rc_instruction));
  80                         rc_insert_instruction(append_to, new);
  81                         append_to = new;
  82                 }
  83         }
  84 }
  85
  86 /**
  87  * This function prepares a loop to be unrolled by converting it into an if
  88  * statement.  Here is an outline of the conversion process:
  89  * BGNLOOP;                         -> BGNLOOP;
  90  * SGE temp[0], temp[1], temp[2];   -> SLT temp[0], temp[1], temp[2];
  91  * IF temp[0];                      -> IF temp[0];
  92  * BRK;                             ->
  93  * ENDIF;                           -> <Loop Body>
  94  * <Loop Body>                      -> ENDIF;
  95  * ENDLOOP;                         -> ENDLOOP
  96  *
  97  * @param inst Pointer to a BGNLOOP instruction.
  98  */
  99 static struct rc_instruction * transform_loop(struct emulate_loop_state * s,
 100                                                 struct rc_instruction * inst)
 101 {
 102         struct loop_info *loop;
 103         struct rc_instruction * ptr;
 104
 105         memory_pool_array_reserve(&s->C->Pool, struct loop_info,
 106                         s->Loops, s->LoopCount, s->LoopReserved, 1);
 107
 108         loop = &s->Loops[s->LoopCount++];
 109         memset(loop, 0, sizeof(struct loop_info));
 110
 111         loop->BeginLoop = inst;
 112         /* Reverse the SGE instruction */
 113         ptr = inst->Next;
 114         ptr->U.I.Opcode = RC_OPCODE_SLT;
 115         while(!loop->EndLoop){
 116                 struct rc_instruction * endif;
 117                 if(ptr->Type == RC_INSTRUCTION_NORMAL){
 118                 }
 119                 switch(ptr->U.I.Opcode){
 120                 case RC_OPCODE_BGNLOOP:
 121                         /* Nested loop */
 122                         ptr = transform_loop(s, ptr);
 123                         break;
 124                 case RC_OPCODE_BRK:
 125                         /* The BRK instruction should always be followed by
 126                          * an ENDIF.  This ENDIF will eventually replace the
 127                          * ENDLOOP insruction. */
 128                         endif = ptr->Next;
 129                         rc_remove_instruction(ptr);
 130                         rc_remove_instruction(endif);
 131                         break;
 132                 case RC_OPCODE_ENDLOOP:
 133                         /* Insert the ENDIF before ENDLOOP. */
 134                         rc_insert_instruction(ptr->Prev, endif);
 135                         loop->EndLoop = ptr;
 136                         break;
 137                 }
 138                 ptr = ptr->Next;
 139         }
 140         return ptr;
 141 }
 142
 143 static void rc_transform_loops(struct emulate_loop_state * s)
 144 {
 145         struct rc_instruction * ptr = s->C->Program.Instructions.Next;
 146         while(ptr != &s->C->Program.Instructions) {
 147                 if(ptr->Type == RC_INSTRUCTION_NORMAL &&
 148                                         ptr->U.I.Opcode == RC_OPCODE_BGNLOOP){
 149                         ptr = transform_loop(s, ptr);
 150                 }
 151                 ptr = ptr->Next;
 152         }
 153 }
 154
 155 static void rc_unroll_loops(struct emulate_loop_state *s,
 156                                                 unsigned int max_instructions)
 157 {
 158         int i;
 159         /* Iterate backwards of the list of loops so that loops that nested
 160          * loops are unrolled first.
 161          */
 162         for( i = s->LoopCount - 1; i >= 0; i-- ){
 163                 unsigned int iterations = loop_calc_iterations(&s->Loops[i],
 164                                                 s->LoopCount, max_instructions);
 165                 loop_unroll(s, &s->Loops[i], iterations);
 166         }
 167 }
 168
 169 void rc_emulate_loops(struct radeon_compiler *c, unsigned int max_instructions)
 170 {
 171         struct emulate_loop_state s;
 172
 173         memset(&s, 0, sizeof(struct emulate_loop_state));
 174         s.C = c;
 175
 176         /* We may need to move these two operations to r3xx_(vert|frag)prog.c
 177          * and run the optimization passes between them in order to increase
 178          * the number of unrolls we can do for each loop.
 179          */
 180         rc_transform_loops(&s);
 181
 182         rc_unroll_loops(&s, max_instructions);
 183 }