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 rewrite_register(struct regalloc_state * s,
 200                 rc_register_file * file, unsigned int * index)
 201 {
 202         const struct register_info * reg;
 203
 204         if (*file == RC_FILE_TEMPORARY)
 205                 reg = &s->Temporary[*index];
 206         else if (*file == RC_FILE_INPUT)
 207                 reg = &s->Input[*index];
 208         else
 209                 return;
 210
 211         if (reg->Allocated) {
 212                 *file = reg->File;
 213                 *index = reg->Index;
 214         }
 215 }
 216
 217 static void rewrite_normal_instruction(struct regalloc_state * s, struct rc_sub_instruction * inst)
 218 {
 219         const struct rc_opcode_info * opcode = rc_get_opcode_info(inst->Opcode);
 220
 221         if (opcode->HasDstReg) {
 222                 rc_register_file file = inst->DstReg.File;
 223                 unsigned int index = inst->DstReg.Index;
 224
 225                 rewrite_register(s, &file, &index);
 226
 227                 inst->DstReg.File = file;
 228                 inst->DstReg.Index = index;
 229         }
 230
 231         for(unsigned int src = 0; src < opcode->NumSrcRegs; ++src) {
 232                 rc_register_file file = inst->SrcReg[src].File;
 233                 unsigned int index = inst->SrcReg[src].Index;
 234
 235                 rewrite_register(s, &file, &index);
 236
 237                 inst->SrcReg[src].File = file;
 238                 inst->SrcReg[src].Index = index;
 239         }
 240 }
 241
 242 static void rewrite_pair_instruction(struct regalloc_state * s, struct rc_pair_instruction * inst)
 243 {
 244         if (inst->RGB.WriteMask) {
 245                 rc_register_file file = RC_FILE_TEMPORARY;
 246                 unsigned int index = inst->RGB.DestIndex;
 247
 248                 rewrite_register(s, &file, &index);
 249
 250                 inst->RGB.DestIndex = index;
 251         }
 252
 253         if (inst->Alpha.WriteMask) {
 254                 rc_register_file file = RC_FILE_TEMPORARY;
 255                 unsigned int index = inst->Alpha.DestIndex;
 256
 257                 rewrite_register(s, &file, &index);
 258
 259                 inst->Alpha.DestIndex = index;
 260         }
 261
 262         for(unsigned int src = 0; src < 3; ++src) {
 263                 if (inst->RGB.Src[src].Used) {
 264                         rc_register_file file = inst->RGB.Src[src].File;
 265                         unsigned int index = inst->RGB.Src[src].Index;
 266
 267                         rewrite_register(s, &file, &index);
 268
 269                         inst->RGB.Src[src].File = file;
 270                         inst->RGB.Src[src].Index = index;
 271                 }
 272
 273                 if (inst->Alpha.Src[src].Used) {
 274                         rc_register_file file = inst->Alpha.Src[src].File;
 275                         unsigned int index = inst->Alpha.Src[src].Index;
 276
 277                         rewrite_register(s, &file, &index);
 278
 279                         inst->Alpha.Src[src].File = file;
 280                         inst->Alpha.Src[src].Index = index;
 281                 }
 282         }
 283 }
 284
 285 static void do_regalloc(struct regalloc_state * s)
 286 {
 287         /* Simple and stupid greedy register allocation */
 288         for(unsigned int index = 0; index < RC_REGISTER_MAX_INDEX; ++index) {
 289                 struct register_info * reg = &s->Temporary[index];
 290
 291                 if (!reg->Used)
 292                         continue;
 293
 294                 for(unsigned int hwreg = 0; hwreg < s->NumHwTemporaries; ++hwreg) {
 295                         if (try_add_live_intervals(s, &s->HwTemporary[hwreg].Used, &reg->Live)) {
 296                                 reg->Allocated = 1;
 297                                 reg->File = RC_FILE_TEMPORARY;
 298                                 reg->Index = hwreg;
 299                                 goto success;
 300                         }
 301                 }
 302
 303                 rc_error(s->C, "Ran out of hardware temporaries\n");
 304                 return;
 305
 306         success:;
 307         }
 308
 309         /* Rewrite all instructions based on the translation table we built */
 310         for(struct rc_instruction * inst = s->C->Program.Instructions.Next;
 311             inst != &s->C->Program.Instructions;
 312             inst = inst->Next) {
 313                 if (inst->Type == RC_INSTRUCTION_NORMAL)
 314                         rewrite_normal_instruction(s, &inst->U.I);
 315                 else
 316                         rewrite_pair_instruction(s, &inst->U.P);
 317         }
 318 }
 319
 320 static void alloc_input(void * data, unsigned int input, unsigned int hwreg)
 321 {
 322         struct regalloc_state * s = data;
 323
 324         if (!s->Input[input].Used)
 325                 return;
 326
 327         add_live_intervals(s, &s->HwTemporary[hwreg].Used, &s->Input[input].Live);
 328
 329         s->Input[input].Allocated = 1;
 330         s->Input[input].File = RC_FILE_TEMPORARY;
 331         s->Input[input].Index = hwreg;
 332
 333 }
 334
 335 void rc_pair_regalloc(struct r300_fragment_program_compiler *c, unsigned maxtemps)
 336 {
 337         struct regalloc_state s;
 338
 339         memset(&s, 0, sizeof(s));
 340         s.C = &c->Base;
 341         s.NumHwTemporaries = maxtemps;
 342         s.HwTemporary = memory_pool_malloc(&s.C->Pool, maxtemps*sizeof(struct hardware_register));
 343         memset(s.HwTemporary, 0, maxtemps*sizeof(struct hardware_register));
 344
 345         compute_live_intervals(&s);
 346
 347         c->AllocateHwInputs(c, &alloc_input, &s);
 348
 349         do_regalloc(&s);
 350 }