src/mesa/drivers/dri/r300/compiler/radeon_pair_regalloc.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_program_pair.h"
  29
  30 #include <stdio.h>
  31
  32 #include "radeon_compiler.h"
  33 #include "radeon_dataflow.h"
  34
  35
  36 #define VERBOSE 0
  37
  38 #define DBG(...) do { if (VERBOSE) fprintf(stderr, __VA_ARGS__); } while(0)
  39
  40
  41 struct live_intervals {
  42         int Start;
  43         int End;
  44         struct live_intervals * Next;
  45 };
  46
  47 struct register_info {
  48         struct live_intervals Live;
  49
  50         unsigned int Used:1;
  51         unsigned int Allocated:1;
  52         unsigned int File:3;
  53         unsigned int Index:RC_REGISTER_INDEX_BITS;
  54 };
  55
  56 struct hardware_register {
  57         struct live_intervals * Used;
  58 };
  59
  60 struct regalloc_state {
  61         struct radeon_compiler * C;
  62
  63         struct register_info Input[RC_REGISTER_MAX_INDEX];
  64         struct register_info Temporary[RC_REGISTER_MAX_INDEX];
  65
  66         struct hardware_register * HwTemporary;
  67         unsigned int NumHwTemporaries;
  68 };
  69
  70 static void print_live_intervals(struct live_intervals * src)
  71 {
  72         if (!src) {
  73                 DBG("(null)");
  74                 return;
  75         }
  76
  77         while(src) {
  78                 DBG("(%i,%i)", src->Start, src->End);
  79                 src = src->Next;
  80         }
  81 }
  82
  83 static void add_live_intervals(struct regalloc_state * s,
  84                 struct live_intervals ** dst, struct live_intervals * src)
  85 {
  86         struct live_intervals ** dst_backup = dst;
  87
  88         if (VERBOSE) {
  89                 DBG("add_live_intervals: ");
  90                 print_live_intervals(*dst);
  91                 DBG(" to ");
  92                 print_live_intervals(src);
  93                 DBG("\n");
  94         }
  95
  96         while(src) {
  97                 if (*dst && (*dst)->End < src->Start) {
  98                         dst = &(*dst)->Next;
  99                 } else if (!*dst || (*dst)->Start > src->End) {
 100                         struct live_intervals * li = memory_pool_malloc(&s->C->Pool, sizeof(*li));
 101                         li->Start = src->Start;
 102                         li->End = src->End;
 103                         li->Next = *dst;
 104                         *dst = li;
 105                         src = src->Next;
 106                 } else {
 107                         if (src->End > (*dst)->End)
 108                                 (*dst)->End = src->End;
 109                         if (src->Start < (*dst)->Start)
 110                                 (*dst)->Start = src->Start;
 111                         src = src->Next;
 112                 }
 113         }
 114
 115         if (VERBOSE) {
 116                 DBG("    result: ");
 117                 print_live_intervals(*dst_backup);
 118                 DBG("\n");
 119         }
 120 }
 121
 122 static int overlap_live_intervals(struct live_intervals * dst, struct live_intervals * src)
 123 {
 124         if (VERBOSE) {
 125                 DBG("overlap_live_intervals: ");
 126                 print_live_intervals(dst);
 127                 DBG(" to ");
 128                 print_live_intervals(src);
 129                 DBG("\n");
 130         }
 131
 132         while(src && dst) {
 133                 if (dst->End <= src->Start) {
 134                         dst = dst->Next;
 135                 } else if (dst->End <= src->End) {
 136                         DBG("    overlap\n");
 137                         return 1;
 138                 } else if (dst->Start < src->End) {
 139                         DBG("    overlap\n");
 140                         return 1;
 141                 } else {
 142                         src = src->Next;
 143                 }
 144         }
 145
 146         DBG("    no overlap\n");
 147
 148         return 0;
 149 }
 150
 151 static int try_add_live_intervals(struct regalloc_state * s,
 152                 struct live_intervals ** dst, struct live_intervals * src)
 153 {
 154         if (overlap_live_intervals(*dst, src))
 155                 return 0;
 156
 157         add_live_intervals(s, dst, src);
 158         return 1;
 159 }
 160
 161 static void scan_callback(void * data, struct rc_instruction * inst,
 162                 rc_register_file file, unsigned int index, unsigned int chan)
 163 {
 164         struct regalloc_state * s = data;
 165         struct register_info * reg;
 166
 167         if (file == RC_FILE_TEMPORARY)
 168                 reg = &s->Temporary[index];
 169         else if (file == RC_FILE_INPUT)
 170                 reg = &s->Input[index];
 171         else
 172                 return;
 173
 174         if (!reg->Used) {
 175                 reg->Used = 1;
 176                 if (file == RC_FILE_INPUT)
 177                         reg->Live.Start = -1;
 178                 else
 179                         reg->Live.Start = inst->IP;
 180                 reg->Live.End = inst->IP;
 181         } else {
 182                 if (inst->IP > reg->Live.End)
 183                         reg->Live.End = inst->IP;
 184         }
 185 }
 186
 187 static void compute_live_intervals(struct regalloc_state * s)
 188 {
 189         rc_recompute_ips(s->C);
 190
 191         for(struct rc_instruction * inst = s->C->Program.Instructions.Next;
 192             inst != &s->C->Program.Instructions;
 193             inst = inst->Next) {
 194                 rc_for_all_reads(inst, scan_callback, s);
 195                 rc_for_all_writes(inst, scan_callback, s);
 196         }
 197 }
 198
 199 static void remap_register(void * data, struct rc_instruction * inst,
 200                 rc_register_file * file, unsigned int * index)
 201 {
 202         struct regalloc_state * s = data;
 203         const struct register_info * reg;
 204
 205         if (*file == RC_FILE_TEMPORARY)
 206                 reg = &s->Temporary[*index];
 207         else if (*file == RC_FILE_INPUT)
 208                 reg = &s->Input[*index];
 209         else
 210                 return;
 211
 212         if (reg->Allocated) {
 213                 *file = reg->File;
 214                 *index = reg->Index;
 215         }
 216 }
 217
 218 static void do_regalloc(struct regalloc_state * s)
 219 {
 220         /* Simple and stupid greedy register allocation */
 221         for(unsigned int index = 0; index < RC_REGISTER_MAX_INDEX; ++index) {
 222                 struct register_info * reg = &s->Temporary[index];
 223
 224                 if (!reg->Used)
 225                         continue;
 226
 227                 for(unsigned int hwreg = 0; hwreg < s->NumHwTemporaries; ++hwreg) {
 228                         if (try_add_live_intervals(s, &s->HwTemporary[hwreg].Used, &reg->Live)) {
 229                                 reg->Allocated = 1;
 230                                 reg->File = RC_FILE_TEMPORARY;
 231                                 reg->Index = hwreg;
 232                                 goto success;
 233                         }
 234                 }
 235
 236                 rc_error(s->C, "Ran out of hardware temporaries\n");
 237                 return;
 238
 239         success:;
 240         }
 241
 242         /* Rewrite all instructions based on the translation table we built */
 243         for(struct rc_instruction * inst = s->C->Program.Instructions.Next;
 244             inst != &s->C->Program.Instructions;
 245             inst = inst->Next) {
 246                 rc_remap_registers(inst, &remap_register, s);
 247         }
 248 }
 249
 250 static void alloc_input(void * data, unsigned int input, unsigned int hwreg)
 251 {
 252         struct regalloc_state * s = data;
 253
 254         if (!s->Input[input].Used)
 255                 return;
 256
 257         add_live_intervals(s, &s->HwTemporary[hwreg].Used, &s->Input[input].Live);
 258
 259         s->Input[input].Allocated = 1;
 260         s->Input[input].File = RC_FILE_TEMPORARY;
 261         s->Input[input].Index = hwreg;
 262
 263 }
 264
 265 void rc_pair_regalloc(struct r300_fragment_program_compiler *c, unsigned maxtemps)
 266 {
 267         struct regalloc_state s;
 268
 269         memset(&s, 0, sizeof(s));
 270         s.C = &c->Base;
 271         s.NumHwTemporaries = maxtemps;
 272         s.HwTemporary = memory_pool_malloc(&s.C->Pool, maxtemps*sizeof(struct hardware_register));
 273         memset(s.HwTemporary, 0, maxtemps*sizeof(struct hardware_register));
 274
 275         compute_live_intervals(&s);
 276
 277         c->AllocateHwInputs(c, &alloc_input, &s);
 278
 279         do_regalloc(&s);
 280 }