projects / mesa.git / blob
? search:


ce411731b229ab35cd43ab625ff98d461dd43bc7
[mesa.git] / src / mesa / shader / prog_optimize.c
1 /*
2 * Mesa 3-D graphics library
3 * Version: 7.5
4 *
5 * Copyright (C) 2009 VMware, Inc. All Rights Reserved.
6 *
7 * Permission is hereby granted, free of charge, to any person obtaining a
8 * copy of this software and associated documentation files (the "Software"),
9 * to deal in the Software without restriction, including without limitation
10 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
11 * and/or sell copies of the Software, and to permit persons to whom the
12 * Software is furnished to do so, subject to the following conditions:
13 *
14 * The above copyright notice and this permission notice shall be included
15 * in all copies or substantial portions of the Software.
16 *
17 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
18 * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
19 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
20 * VMWARE BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
21 * AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
22 * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
23 */
24
25
26
27 #include "main/glheader.h"
28 #include "main/context.h"
29 #include "main/macros.h"
30 #include "program.h"
31 #include "prog_instruction.h"
32 #include "prog_optimize.h"
33 #include "prog_print.h"
34
35
36 #define MAX_LOOP_NESTING 50
37
38
39 static GLboolean dbg = GL_FALSE;
40
41 /* Returns the mask of channels read from the given srcreg in this instruction.
42 */
43 static GLuint
44 get_src_arg_mask(const struct prog_instruction *inst, int arg)
45 {
46 int writemask = inst->DstReg.WriteMask;
47
48 if (inst->CondUpdate)
49 writemask = WRITEMASK_XYZW;
50
51 switch (inst->Opcode) {
52 case OPCODE_MOV:
53 case OPCODE_ABS:
54 case OPCODE_ADD:
55 case OPCODE_MUL:
56 case OPCODE_SUB:
57 return writemask;
58 case OPCODE_RCP:
59 case OPCODE_SIN:
60 case OPCODE_COS:
61 case OPCODE_RSQ:
62 case OPCODE_POW:
63 case OPCODE_EX2:
64 return WRITEMASK_X;
65 case OPCODE_DP2:
66 return WRITEMASK_XY;
67 case OPCODE_DP3:
68 case OPCODE_XPD:
69 return WRITEMASK_XYZ;
70 default:
71 return WRITEMASK_XYZW;
72 }
73 }
74
75 /**
76 * In 'prog' remove instruction[i] if removeFlags[i] == TRUE.
77 * \return number of instructions removed
78 */
79 static GLuint
80 remove_instructions(struct gl_program *prog, const GLboolean *removeFlags)
81 {
82 GLint i, removeEnd = 0, removeCount = 0;
83 GLuint totalRemoved = 0;
84
85 /* go backward */
86 for (i = prog->NumInstructions - 1; i >= 0; i--) {
87 if (removeFlags[i]) {
88 totalRemoved++;
89 if (removeCount == 0) {
90 /* begin a run of instructions to remove */
91 removeEnd = i;
92 removeCount = 1;
93 }
94 else {
95 /* extend the run of instructions to remove */
96 removeCount++;
97 }
98 }
99 else {
100 /* don't remove this instruction, but check if the preceeding
101 * instructions are to be removed.
102 */
103 if (removeCount > 0) {
104 GLint removeStart = removeEnd - removeCount + 1;
105 _mesa_delete_instructions(prog, removeStart, removeCount);
106 removeStart = removeCount = 0; /* reset removal info */
107 }
108 }
109 }
110 /* Finish removing if the first instruction was to be removed. */
111 if (removeCount > 0) {
112 GLint removeStart = removeEnd - removeCount + 1;
113 _mesa_delete_instructions(prog, removeStart, removeCount);
114 }
115 return totalRemoved;
116 }
117
118
119 /**
120 * Remap register indexes according to map.
121 * \param prog the program to search/replace
122 * \param file the type of register file to search/replace
123 * \param map maps old register indexes to new indexes
124 */
125 static void
126 replace_regs(struct gl_program *prog, gl_register_file file, const GLint map[])
127 {
128 GLuint i;
129
130 for (i = 0; i < prog->NumInstructions; i++) {
131 struct prog_instruction *inst = prog->Instructions + i;
132 const GLuint numSrc = _mesa_num_inst_src_regs(inst->Opcode);
133 GLuint j;
134 for (j = 0; j < numSrc; j++) {
135 if (inst->SrcReg[j].File == file) {
136 GLuint index = inst->SrcReg[j].Index;
137 ASSERT(map[index] >= 0);
138 inst->SrcReg[j].Index = map[index];
139 }
140 }
141 if (inst->DstReg.File == file) {
142 const GLuint index = inst->DstReg.Index;
143 ASSERT(map[index] >= 0);
144 inst->DstReg.Index = map[index];
145 }
146 }
147 }
148
149
150 /**
151 * Consolidate temporary registers to use low numbers. For example, if the
152 * shader only uses temps 4, 5, 8, replace them with 0, 1, 2.
153 */
154 static void
155 _mesa_consolidate_registers(struct gl_program *prog)
156 {
157 GLboolean tempUsed[MAX_PROGRAM_TEMPS];
158 GLint tempMap[MAX_PROGRAM_TEMPS];
159 GLuint tempMax = 0, i;
160
161 if (dbg) {
162 _mesa_printf("Optimize: Begin register consolidation\n");
163 }
164
165 memset(tempUsed, 0, sizeof(tempUsed));
166
167 for (i = 0; i < MAX_PROGRAM_TEMPS; i++) {
168 tempMap[i] = -1;
169 }
170
171 /* set tempUsed[i] if temporary [i] is referenced */
172 for (i = 0; i < prog->NumInstructions; i++) {
173 const struct prog_instruction *inst = prog->Instructions + i;
174 const GLuint numSrc = _mesa_num_inst_src_regs(inst->Opcode);
175 GLuint j;
176 for (j = 0; j < numSrc; j++) {
177 if (inst->SrcReg[j].File == PROGRAM_TEMPORARY) {
178 const GLuint index = inst->SrcReg[j].Index;
179 ASSERT(index < MAX_PROGRAM_TEMPS);
180 tempUsed[index] = GL_TRUE;
181 tempMax = MAX2(tempMax, index);
182 break;
183 }
184 }
185 if (inst->DstReg.File == PROGRAM_TEMPORARY) {
186 const GLuint index = inst->DstReg.Index;
187 ASSERT(index < MAX_PROGRAM_TEMPS);
188 tempUsed[index] = GL_TRUE;
189 tempMax = MAX2(tempMax, index);
190 }
191 }
192
193 /* allocate a new index for each temp that's used */
194 {
195 GLuint freeTemp = 0;
196 for (i = 0; i <= tempMax; i++) {
197 if (tempUsed[i]) {
198 tempMap[i] = freeTemp++;
199 /*_mesa_printf("replace %u with %u\n", i, tempMap[i]);*/
200 }
201 }
202 if (freeTemp == tempMax + 1) {
203 /* no consolidation possible */
204 return;
205 }
206 if (dbg) {
207 _mesa_printf("Replace regs 0..%u with 0..%u\n", tempMax, freeTemp-1);
208 }
209 }
210
211 replace_regs(prog, PROGRAM_TEMPORARY, tempMap);
212
213 if (dbg) {
214 _mesa_printf("Optimize: End register consolidation\n");
215 }
216 }
217
218
219 /**
220 * Remove dead instructions from the given program.
221 * This is very primitive for now. Basically look for temp registers
222 * that are written to but never read. Remove any instructions that
223 * write to such registers. Be careful with condition code setters.
224 */
225 static void
226 _mesa_remove_dead_code(struct gl_program *prog)
227 {
228 GLboolean tempRead[MAX_PROGRAM_TEMPS][4];
229 GLboolean *removeInst; /* per-instruction removal flag */
230 GLuint i, rem = 0, comp;
231
232 memset(tempRead, 0, sizeof(tempRead));
233
234 if (dbg) {
235 _mesa_printf("Optimize: Begin dead code removal\n");
236 /*_mesa_print_program(prog);*/
237 }
238
239 removeInst = (GLboolean *)
240 _mesa_calloc(prog->NumInstructions * sizeof(GLboolean));
241
242 /* Determine which temps are read and written */
243 for (i = 0; i < prog->NumInstructions; i++) {
244 const struct prog_instruction *inst = prog->Instructions + i;
245 const GLuint numSrc = _mesa_num_inst_src_regs(inst->Opcode);
246 GLuint j;
247
248 /* check src regs */
249 for (j = 0; j < numSrc; j++) {
250 if (inst->SrcReg[j].File == PROGRAM_TEMPORARY) {
251 const GLuint index = inst->SrcReg[j].Index;
252 GLuint read_mask;
253 ASSERT(index < MAX_PROGRAM_TEMPS);
254 read_mask = get_src_arg_mask(inst, j);
255
256 if (inst->SrcReg[j].RelAddr) {
257 if (dbg)
258 _mesa_printf("abort remove dead code (indirect temp)\n");
259 goto done;
260 }
261
262 for (comp = 0; comp < 4; comp++) {
263 GLuint swz = (inst->SrcReg[j].Swizzle >> (3 * comp)) & 0x7;
264
265 if ((read_mask & (1 << comp)) == 0)
266 continue;
267
268 switch (swz) {
269 case SWIZZLE_X:
270 tempRead[index][0] = GL_TRUE;
271 break;
272 case SWIZZLE_Y:
273 tempRead[index][1] = GL_TRUE;
274 break;
275 case SWIZZLE_Z:
276 tempRead[index][2] = GL_TRUE;
277 break;
278 case SWIZZLE_W:
279 tempRead[index][3] = GL_TRUE;
280 break;
281 }
282 }
283 }
284 }
285
286 /* check dst reg */
287 if (inst->DstReg.File == PROGRAM_TEMPORARY) {
288 const GLuint index = inst->DstReg.Index;
289 ASSERT(index < MAX_PROGRAM_TEMPS);
290
291 if (inst->DstReg.RelAddr) {
292 if (dbg)
293 _mesa_printf("abort remove dead code (indirect temp)\n");
294 goto done;
295 }
296
297 if (inst->CondUpdate) {
298 /* If we're writing to this register and setting condition
299 * codes we cannot remove the instruction. Prevent removal
300 * by setting the 'read' flag.
301 */
302 tempRead[index][0] = GL_TRUE;
303 tempRead[index][1] = GL_TRUE;
304 tempRead[index][2] = GL_TRUE;
305 tempRead[index][3] = GL_TRUE;
306 }
307 }
308 }
309
310 /* find instructions that write to dead registers, flag for removal */
311 for (i = 0; i < prog->NumInstructions; i++) {
312 struct prog_instruction *inst = prog->Instructions + i;
313 const GLuint numDst = _mesa_num_inst_dst_regs(inst->Opcode);
314
315 if (numDst != 0 && inst->DstReg.File == PROGRAM_TEMPORARY) {
316 GLint chan, index = inst->DstReg.Index;
317
318 for (chan = 0; chan < 4; chan++) {
319 if (!tempRead[index][chan] &&
320 inst->DstReg.WriteMask & (1 << chan)) {
321 if (dbg) {
322 _mesa_printf("Remove writemask on %u.%c\n", i,
323 chan == 3 ? 'w' : 'x' + chan);
324 }
325 inst->DstReg.WriteMask &= ~(1 << chan);
326 rem++;
327 }
328 }
329
330 if (inst->DstReg.WriteMask == 0) {
331 /* If we cleared all writes, the instruction can be removed. */
332 if (dbg)
333 _mesa_printf("Remove instruction %u: \n", i);
334 removeInst[i] = GL_TRUE;
335 }
336 }
337 }
338
339 /* now remove the instructions which aren't needed */
340 rem = remove_instructions(prog, removeInst);
341
342 if (dbg) {
343 _mesa_printf("Optimize: End dead code removal.\n");
344 _mesa_printf(" %u channel writes removed\n", rem);
345 _mesa_printf(" %u instructions removed\n", rem);
346 /*_mesa_print_program(prog);*/
347 }
348
349 done:
350 _mesa_free(removeInst);
351 }
352
353
354 enum temp_use
355 {
356 READ,
357 WRITE,
358 FLOW,
359 END
360 };
361
362 /**
363 * Scan forward in program from 'start' for the next occurance of TEMP[index].
364 * Return READ, WRITE, FLOW or END to indicate the next usage or an indicator
365 * that we can't look further.
366 */
367 static enum temp_use
368 find_next_temp_use(const struct gl_program *prog, GLuint start, GLuint index)
369 {
370 GLuint i;
371
372 for (i = start; i < prog->NumInstructions; i++) {
373 const struct prog_instruction *inst = prog->Instructions + i;
374 switch (inst->Opcode) {
375 case OPCODE_BGNLOOP:
376 case OPCODE_ENDLOOP:
377 case OPCODE_BGNSUB:
378 case OPCODE_ENDSUB:
379 return FLOW;
380 default:
381 {
382 const GLuint numSrc = _mesa_num_inst_src_regs(inst->Opcode);
383 GLuint j;
384 for (j = 0; j < numSrc; j++) {
385 if (inst->SrcReg[j].File == PROGRAM_TEMPORARY &&
386 inst->SrcReg[j].Index == index)
387 return READ;
388 }
389 if (inst->DstReg.File == PROGRAM_TEMPORARY &&
390 inst->DstReg.Index == index)
391 return WRITE;
392 }
393 }
394 }
395
396 return END;
397 }
398
399 static GLboolean _mesa_is_flow_control_opcode(enum prog_opcode opcode)
400 {
401 switch (opcode) {
402 case OPCODE_BGNLOOP:
403 case OPCODE_BGNSUB:
404 case OPCODE_BRA:
405 case OPCODE_CAL:
406 case OPCODE_CONT:
407 case OPCODE_IF:
408 case OPCODE_ELSE:
409 case OPCODE_END:
410 case OPCODE_ENDIF:
411 case OPCODE_ENDLOOP:
412 case OPCODE_ENDSUB:
413 case OPCODE_RET:
414 return GL_TRUE;
415 default:
416 return GL_FALSE;
417 }
418 }
419
420 /**
421 * Try to remove use of extraneous MOV instructions, to free them up for dead
422 * code removal.
423 */
424 static void
425 _mesa_remove_extra_move_use(struct gl_program *prog)
426 {
427 GLuint i, j;
428
429 if (dbg) {
430 _mesa_printf("Optimize: Begin remove extra move use\n");
431 _mesa_print_program(prog);
432 }
433
434 /*
435 * Look for sequences such as this:
436 * MOV tmpX, arg0;
437 * ...
438 * FOO tmpY, tmpX, arg1;
439 * and convert into:
440 * MOV tmpX, arg0;
441 * ...
442 * FOO tmpY, arg0, arg1;
443 */
444
445 for (i = 0; i + 1 < prog->NumInstructions; i++) {
446 const struct prog_instruction *mov = prog->Instructions + i;
447
448 if (mov->Opcode != OPCODE_MOV ||
449 mov->DstReg.File != PROGRAM_TEMPORARY ||
450 mov->DstReg.RelAddr ||
451 mov->DstReg.CondMask != COND_TR ||
452 mov->SaturateMode != SATURATE_OFF ||
453 mov->SrcReg[0].RelAddr)
454 continue;
455
456 /* Walk through remaining instructions until the or src reg gets
457 * rewritten or we get into some flow-control, eliminating the use of
458 * this MOV.
459 */
460 for (j = i + 1; j < prog->NumInstructions; j++) {
461 struct prog_instruction *inst2 = prog->Instructions + j;
462 int arg;
463
464 if (_mesa_is_flow_control_opcode(inst2->Opcode))
465 break;
466
467 /* First rewrite this instruction's args if appropriate. */
468 for (arg = 0; arg < _mesa_num_inst_src_regs(inst2->Opcode); arg++) {
469 int comp;
470 int read_mask = get_src_arg_mask(inst2, arg);
471
472 if (inst2->SrcReg[arg].File != mov->DstReg.File ||
473 inst2->SrcReg[arg].Index != mov->DstReg.Index ||
474 inst2->SrcReg[arg].RelAddr ||
475 inst2->SrcReg[arg].Abs)
476 continue;
477
478 /* Check that all the sources for this arg of inst2 come from inst1
479 * or constants.
480 */
481 for (comp = 0; comp < 4; comp++) {
482 int src_swz = GET_SWZ(inst2->SrcReg[arg].Swizzle, comp);
483
484 /* If the MOV didn't write that channel, can't use it. */
485 if ((read_mask & (1 << comp)) &&
486 src_swz <= SWIZZLE_W &&
487 (mov->DstReg.WriteMask & (1 << src_swz)) == 0)
488 break;
489 }
490 if (comp != 4)
491 continue;
492
493 /* Adjust the swizzles of inst2 to point at MOV's source */
494 for (comp = 0; comp < 4; comp++) {
495 int inst2_swz = GET_SWZ(inst2->SrcReg[arg].Swizzle, comp);
496
497 if (inst2_swz <= SWIZZLE_W) {
498 GLuint s = GET_SWZ(mov->SrcReg[0].Swizzle, inst2_swz);
499 inst2->SrcReg[arg].Swizzle &= ~(7 << (3 * comp));
500 inst2->SrcReg[arg].Swizzle |= s << (3 * comp);
501 inst2->SrcReg[arg].Negate ^= (((mov->SrcReg[0].Negate >>
502 inst2_swz) & 0x1) << comp);
503 }
504 }
505 inst2->SrcReg[arg].File = mov->SrcReg[0].File;
506 inst2->SrcReg[arg].Index = mov->SrcReg[0].Index;
507 }
508
509 /* If this instruction overwrote part of the move, our time is up. */
510 if ((inst2->DstReg.File == mov->DstReg.File &&
511 (inst2->DstReg.RelAddr ||
512 inst2->DstReg.Index == mov->DstReg.Index)) ||
513 (inst2->DstReg.File == mov->SrcReg[0].File &&
514 (inst2->DstReg.RelAddr ||
515 inst2->DstReg.Index == mov->SrcReg[0].Index)))
516 break;
517 }
518 }
519
520 if (dbg) {
521 _mesa_printf("Optimize: End remove extra move use.\n");
522 /*_mesa_print_program(prog);*/
523 }
524 }
525
526 /**
527 * Try to remove extraneous MOV instructions from the given program.
528 */
529 static void
530 _mesa_remove_extra_moves(struct gl_program *prog)
531 {
532 GLboolean *removeInst; /* per-instruction removal flag */
533 GLuint i, rem, loopNesting = 0, subroutineNesting = 0;
534
535 if (dbg) {
536 _mesa_printf("Optimize: Begin remove extra moves\n");
537 _mesa_print_program(prog);
538 }
539
540 removeInst = (GLboolean *)
541 _mesa_calloc(prog->NumInstructions * sizeof(GLboolean));
542
543 /*
544 * Look for sequences such as this:
545 * FOO tmpX, arg0, arg1;
546 * MOV tmpY, tmpX;
547 * and convert into:
548 * FOO tmpY, arg0, arg1;
549 */
550
551 for (i = 0; i < prog->NumInstructions; i++) {
552 const struct prog_instruction *inst = prog->Instructions + i;
553
554 switch (inst->Opcode) {
555 case OPCODE_BGNLOOP:
556 loopNesting++;
557 break;
558 case OPCODE_ENDLOOP:
559 loopNesting--;
560 break;
561 case OPCODE_BGNSUB:
562 subroutineNesting++;
563 break;
564 case OPCODE_ENDSUB:
565 subroutineNesting--;
566 break;
567 case OPCODE_MOV:
568 if (i > 0 &&
569 loopNesting == 0 &&
570 subroutineNesting == 0 &&
571 inst->SrcReg[0].File == PROGRAM_TEMPORARY &&
572 inst->SrcReg[0].Swizzle == SWIZZLE_XYZW) {
573 /* see if this MOV can be removed */
574 const GLuint tempIndex = inst->SrcReg[0].Index;
575 struct prog_instruction *prevInst;
576 GLuint prevI;
577
578 /* get pointer to previous instruction */
579 prevI = i - 1;
580 while (prevI > 0 && removeInst[prevI])
581 prevI--;
582 prevInst = prog->Instructions + prevI;
583
584 if (prevInst->DstReg.File == PROGRAM_TEMPORARY &&
585 prevInst->DstReg.Index == tempIndex &&
586 prevInst->DstReg.WriteMask == WRITEMASK_XYZW) {
587
588 enum temp_use next_use =
589 find_next_temp_use(prog, i + 1, tempIndex);
590
591 if (next_use == WRITE || next_use == END) {
592 /* OK, we can safely remove this MOV instruction.
593 * Transform:
594 * prevI: FOO tempIndex, x, y;
595 * i: MOV z, tempIndex;
596 * Into:
597 * prevI: FOO z, x, y;
598 */
599
600 /* patch up prev inst */
601 prevInst->DstReg.File = inst->DstReg.File;
602 prevInst->DstReg.Index = inst->DstReg.Index;
603
604 /* flag this instruction for removal */
605 removeInst[i] = GL_TRUE;
606
607 if (dbg) {
608 _mesa_printf("Remove MOV at %u\n", i);
609 _mesa_printf("new prev inst %u: ", prevI);
610 _mesa_print_instruction(prevInst);
611 }
612 }
613 }
614 }
615 break;
616 default:
617 ; /* nothing */
618 }
619 }
620
621 /* now remove the instructions which aren't needed */
622 rem = remove_instructions(prog, removeInst);
623
624 _mesa_free(removeInst);
625
626 if (dbg) {
627 _mesa_printf("Optimize: End remove extra moves. %u instructions removed\n", rem);
628 /*_mesa_print_program(prog);*/
629 }
630 }
631
632
633 /** A live register interval */
634 struct interval
635 {
636 GLuint Reg; /** The temporary register index */
637 GLuint Start, End; /** Start/end instruction numbers */
638 };
639
640
641 /** A list of register intervals */
642 struct interval_list
643 {
644 GLuint Num;
645 struct interval Intervals[MAX_PROGRAM_TEMPS];
646 };
647
648
649 static void
650 append_interval(struct interval_list *list, const struct interval *inv)
651 {
652 list->Intervals[list->Num++] = *inv;
653 }
654
655
656 /** Insert interval inv into list, sorted by interval end */
657 static void
658 insert_interval_by_end(struct interval_list *list, const struct interval *inv)
659 {
660 /* XXX we could do a binary search insertion here since list is sorted */
661 GLint i = list->Num - 1;
662 while (i >= 0 && list->Intervals[i].End > inv->End) {
663 list->Intervals[i + 1] = list->Intervals[i];
664 i--;
665 }
666 list->Intervals[i + 1] = *inv;
667 list->Num++;
668
669 #ifdef DEBUG
670 {
671 GLuint i;
672 for (i = 0; i + 1 < list->Num; i++) {
673 ASSERT(list->Intervals[i].End <= list->Intervals[i + 1].End);
674 }
675 }
676 #endif
677 }
678
679
680 /** Remove the given interval from the interval list */
681 static void
682 remove_interval(struct interval_list *list, const struct interval *inv)
683 {
684 /* XXX we could binary search since list is sorted */
685 GLuint k;
686 for (k = 0; k < list->Num; k++) {
687 if (list->Intervals[k].Reg == inv->Reg) {
688 /* found, remove it */
689 ASSERT(list->Intervals[k].Start == inv->Start);
690 ASSERT(list->Intervals[k].End == inv->End);
691 while (k < list->Num - 1) {
692 list->Intervals[k] = list->Intervals[k + 1];
693 k++;
694 }
695 list->Num--;
696 return;
697 }
698 }
699 }
700
701
702 /** called by qsort() */
703 static int
704 compare_start(const void *a, const void *b)
705 {
706 const struct interval *ia = (const struct interval *) a;
707 const struct interval *ib = (const struct interval *) b;
708 if (ia->Start < ib->Start)
709 return -1;
710 else if (ia->Start > ib->Start)
711 return +1;
712 else
713 return 0;
714 }
715
716 /** sort the interval list according to interval starts */
717 static void
718 sort_interval_list_by_start(struct interval_list *list)
719 {
720 qsort(list->Intervals, list->Num, sizeof(struct interval), compare_start);
721 #ifdef DEBUG
722 {
723 GLuint i;
724 for (i = 0; i + 1 < list->Num; i++) {
725 ASSERT(list->Intervals[i].Start <= list->Intervals[i + 1].Start);
726 }
727 }
728 #endif
729 }
730
731
732 /**
733 * Update the intermediate interval info for register 'index' and
734 * instruction 'ic'.
735 */
736 static void
737 update_interval(GLint intBegin[], GLint intEnd[], GLuint index, GLuint ic)
738 {
739 ASSERT(index < MAX_PROGRAM_TEMPS);
740 if (intBegin[index] == -1) {
741 ASSERT(intEnd[index] == -1);
742 intBegin[index] = intEnd[index] = ic;
743 }
744 else {
745 intEnd[index] = ic;
746 }
747 }
748
749
750 /**
751 * Find first/last instruction that references each temporary register.
752 */
753 GLboolean
754 _mesa_find_temp_intervals(const struct prog_instruction *instructions,
755 GLuint numInstructions,
756 GLint intBegin[MAX_PROGRAM_TEMPS],
757 GLint intEnd[MAX_PROGRAM_TEMPS])
758 {
759 struct loop_info
760 {
761 GLuint Start, End; /**< Start, end instructions of loop */
762 };
763 struct loop_info loopStack[MAX_LOOP_NESTING];
764 GLuint loopStackDepth = 0;
765 GLuint i;
766
767 for (i = 0; i < MAX_PROGRAM_TEMPS; i++){
768 intBegin[i] = intEnd[i] = -1;
769 }
770
771 /* Scan instructions looking for temporary registers */
772 for (i = 0; i < numInstructions; i++) {
773 const struct prog_instruction *inst = instructions + i;
774 if (inst->Opcode == OPCODE_BGNLOOP) {
775 loopStack[loopStackDepth].Start = i;
776 loopStack[loopStackDepth].End = inst->BranchTarget;
777 loopStackDepth++;
778 }
779 else if (inst->Opcode == OPCODE_ENDLOOP) {
780 loopStackDepth--;
781 }
782 else if (inst->Opcode == OPCODE_CAL) {
783 return GL_FALSE;
784 }
785 else {
786 const GLuint numSrc = 3;/*_mesa_num_inst_src_regs(inst->Opcode);*/
787 GLuint j;
788 for (j = 0; j < numSrc; j++) {
789 if (inst->SrcReg[j].File == PROGRAM_TEMPORARY) {
790 const GLuint index = inst->SrcReg[j].Index;
791 if (inst->SrcReg[j].RelAddr)
792 return GL_FALSE;
793 update_interval(intBegin, intEnd, index, i);
794 if (loopStackDepth > 0) {
795 /* extend temp register's interval to end of loop */
796 GLuint loopEnd = loopStack[loopStackDepth - 1].End;
797 update_interval(intBegin, intEnd, index, loopEnd);
798 }
799 }
800 }
801 if (inst->DstReg.File == PROGRAM_TEMPORARY) {
802 const GLuint index = inst->DstReg.Index;
803 if (inst->DstReg.RelAddr)
804 return GL_FALSE;
805 update_interval(intBegin, intEnd, index, i);
806 if (loopStackDepth > 0) {
807 /* extend temp register's interval to end of loop */
808 GLuint loopEnd = loopStack[loopStackDepth - 1].End;
809 update_interval(intBegin, intEnd, index, loopEnd);
810 }
811 }
812 }
813 }
814
815 return GL_TRUE;
816 }
817
818
819 /**
820 * Find the live intervals for each temporary register in the program.
821 * For register R, the interval [A,B] indicates that R is referenced
822 * from instruction A through instruction B.
823 * Special consideration is needed for loops and subroutines.
824 * \return GL_TRUE if success, GL_FALSE if we cannot proceed for some reason
825 */
826 static GLboolean
827 find_live_intervals(struct gl_program *prog,
828 struct interval_list *liveIntervals)
829 {
830 GLint intBegin[MAX_PROGRAM_TEMPS], intEnd[MAX_PROGRAM_TEMPS];
831 GLuint i;
832
833 /*
834 * Note: we'll return GL_FALSE below if we find relative indexing
835 * into the TEMP register file. We can't handle that yet.
836 * We also give up on subroutines for now.
837 */
838
839 if (dbg) {
840 _mesa_printf("Optimize: Begin find intervals\n");
841 }
842
843 /* build intermediate arrays */
844 if (!_mesa_find_temp_intervals(prog->Instructions, prog->NumInstructions,
845 intBegin, intEnd))
846 return GL_FALSE;
847
848 /* Build live intervals list from intermediate arrays */
849 liveIntervals->Num = 0;
850 for (i = 0; i < MAX_PROGRAM_TEMPS; i++) {
851 if (intBegin[i] >= 0) {
852 struct interval inv;
853 inv.Reg = i;
854 inv.Start = intBegin[i];
855 inv.End = intEnd[i];
856 append_interval(liveIntervals, &inv);
857 }
858 }
859
860 /* Sort the list according to interval starts */
861 sort_interval_list_by_start(liveIntervals);
862
863 if (dbg) {
864 /* print interval info */
865 for (i = 0; i < liveIntervals->Num; i++) {
866 const struct interval *inv = liveIntervals->Intervals + i;
867 _mesa_printf("Reg[%d] live [%d, %d]:",
868 inv->Reg, inv->Start, inv->End);
869 if (1) {
870 int j;
871 for (j = 0; j < inv->Start; j++)
872 _mesa_printf(" ");
873 for (j = inv->Start; j <= inv->End; j++)
874 _mesa_printf("x");
875 }
876 _mesa_printf("\n");
877 }
878 }
879
880 return GL_TRUE;
881 }
882
883
884 /** Scan the array of used register flags to find free entry */
885 static GLint
886 alloc_register(GLboolean usedRegs[MAX_PROGRAM_TEMPS])
887 {
888 GLuint k;
889 for (k = 0; k < MAX_PROGRAM_TEMPS; k++) {
890 if (!usedRegs[k]) {
891 usedRegs[k] = GL_TRUE;
892 return k;
893 }
894 }
895 return -1;
896 }
897
898
899 /**
900 * This function implements "Linear Scan Register Allocation" to reduce
901 * the number of temporary registers used by the program.
902 *
903 * We compute the "live interval" for all temporary registers then
904 * examine the overlap of the intervals to allocate new registers.
905 * Basically, if two intervals do not overlap, they can use the same register.
906 */
907 static void
908 _mesa_reallocate_registers(struct gl_program *prog)
909 {
910 struct interval_list liveIntervals;
911 GLint registerMap[MAX_PROGRAM_TEMPS];
912 GLboolean usedRegs[MAX_PROGRAM_TEMPS];
913 GLuint i;
914 GLint maxTemp = -1;
915
916 if (dbg) {
917 _mesa_printf("Optimize: Begin live-interval register reallocation\n");
918 _mesa_print_program(prog);
919 }
920
921 for (i = 0; i < MAX_PROGRAM_TEMPS; i++){
922 registerMap[i] = -1;
923 usedRegs[i] = GL_FALSE;
924 }
925
926 if (!find_live_intervals(prog, &liveIntervals)) {
927 if (dbg)
928 _mesa_printf("Aborting register reallocation\n");
929 return;
930 }
931
932 {
933 struct interval_list activeIntervals;
934 activeIntervals.Num = 0;
935
936 /* loop over live intervals, allocating a new register for each */
937 for (i = 0; i < liveIntervals.Num; i++) {
938 const struct interval *live = liveIntervals.Intervals + i;
939
940 if (dbg)
941 _mesa_printf("Consider register %u\n", live->Reg);
942
943 /* Expire old intervals. Intervals which have ended with respect
944 * to the live interval can have their remapped registers freed.
945 */
946 {
947 GLint j;
948 for (j = 0; j < activeIntervals.Num; j++) {
949 const struct interval *inv = activeIntervals.Intervals + j;
950 if (inv->End >= live->Start) {
951 /* Stop now. Since the activeInterval list is sorted
952 * we know we don't have to go further.
953 */
954 break;
955 }
956 else {
957 /* Interval 'inv' has expired */
958 const GLint regNew = registerMap[inv->Reg];
959 ASSERT(regNew >= 0);
960
961 if (dbg)
962 _mesa_printf(" expire interval for reg %u\n", inv->Reg);
963
964 /* remove interval j from active list */
965 remove_interval(&activeIntervals, inv);
966 j--; /* counter-act j++ in for-loop above */
967
968 /* return register regNew to the free pool */
969 if (dbg)
970 _mesa_printf(" free reg %d\n", regNew);
971 ASSERT(usedRegs[regNew] == GL_TRUE);
972 usedRegs[regNew] = GL_FALSE;
973 }
974 }
975 }
976
977 /* find a free register for this live interval */
978 {
979 const GLint k = alloc_register(usedRegs);
980 if (k < 0) {
981 /* out of registers, give up */
982 return;
983 }
984 registerMap[live->Reg] = k;
985 maxTemp = MAX2(maxTemp, k);
986 if (dbg)
987 _mesa_printf(" remap register %u -> %d\n", live->Reg, k);
988 }
989
990 /* Insert this live interval into the active list which is sorted
991 * by increasing end points.
992 */
993 insert_interval_by_end(&activeIntervals, live);
994 }
995 }
996
997 if (maxTemp + 1 < liveIntervals.Num) {
998 /* OK, we've reduced the number of registers needed.
999 * Scan the program and replace all the old temporary register
1000 * indexes with the new indexes.
1001 */
1002 replace_regs(prog, PROGRAM_TEMPORARY, registerMap);
1003
1004 prog->NumTemporaries = maxTemp + 1;
1005 }
1006
1007 if (dbg) {
1008 _mesa_printf("Optimize: End live-interval register reallocation\n");
1009 _mesa_printf("Num temp regs before: %u after: %u\n",
1010 liveIntervals.Num, maxTemp + 1);
1011 _mesa_print_program(prog);
1012 }
1013 }
1014
1015
1016 /**
1017 * Apply optimizations to the given program to eliminate unnecessary
1018 * instructions, temp regs, etc.
1019 */
1020 void
1021 _mesa_optimize_program(GLcontext *ctx, struct gl_program *program)
1022 {
1023 _mesa_remove_extra_move_use(program);
1024
1025 if (1)
1026 _mesa_remove_dead_code(program);
1027
1028 if (0) /* not tested much yet */
1029 _mesa_remove_extra_moves(program);
1030
1031 if (0)
1032 _mesa_consolidate_registers(program);
1033 else
1034 _mesa_reallocate_registers(program);
1035 }