2 * Mesa 3-D graphics library
5 * Copyright (C) 2009 VMware, Inc. All Rights Reserved.
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:
14 * The above copyright notice and this permission notice shall be included
15 * in all copies or substantial portions of the Software.
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.
27 #include "main/glheader.h"
28 #include "main/context.h"
29 #include "main/macros.h"
31 #include "prog_instruction.h"
32 #include "prog_optimize.h"
33 #include "prog_print.h"
36 #define MAX_LOOP_NESTING 50
39 static GLboolean dbg
= GL_FALSE
;
41 /* Returns the mask of channels read from the given srcreg in this instruction.
44 get_src_arg_mask(const struct prog_instruction
*inst
, int arg
)
46 int writemask
= inst
->DstReg
.WriteMask
;
49 writemask
= WRITEMASK_XYZW
;
51 switch (inst
->Opcode
) {
71 return WRITEMASK_XYZW
;
76 * In 'prog' remove instruction[i] if removeFlags[i] == TRUE.
77 * \return number of instructions removed
80 remove_instructions(struct gl_program
*prog
, const GLboolean
*removeFlags
)
82 GLint i
, removeEnd
= 0, removeCount
= 0;
83 GLuint totalRemoved
= 0;
86 for (i
= prog
->NumInstructions
- 1; i
>= 0; i
--) {
89 if (removeCount
== 0) {
90 /* begin a run of instructions to remove */
95 /* extend the run of instructions to remove */
100 /* don't remove this instruction, but check if the preceeding
101 * instructions are to be removed.
103 if (removeCount
> 0) {
104 GLint removeStart
= removeEnd
- removeCount
+ 1;
105 _mesa_delete_instructions(prog
, removeStart
, removeCount
);
106 removeStart
= removeCount
= 0; /* reset removal info */
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 removeStart
= removeCount
= 0; /* reset removal info */
121 * Remap register indexes according to map.
122 * \param prog the program to search/replace
123 * \param file the type of register file to search/replace
124 * \param map maps old register indexes to new indexes
127 replace_regs(struct gl_program
*prog
, gl_register_file file
, const GLint map
[])
131 for (i
= 0; i
< prog
->NumInstructions
; i
++) {
132 struct prog_instruction
*inst
= prog
->Instructions
+ i
;
133 const GLuint numSrc
= _mesa_num_inst_src_regs(inst
->Opcode
);
135 for (j
= 0; j
< numSrc
; j
++) {
136 if (inst
->SrcReg
[j
].File
== file
) {
137 GLuint index
= inst
->SrcReg
[j
].Index
;
138 ASSERT(map
[index
] >= 0);
139 inst
->SrcReg
[j
].Index
= map
[index
];
142 if (inst
->DstReg
.File
== file
) {
143 const GLuint index
= inst
->DstReg
.Index
;
144 ASSERT(map
[index
] >= 0);
145 inst
->DstReg
.Index
= map
[index
];
152 * Consolidate temporary registers to use low numbers. For example, if the
153 * shader only uses temps 4, 5, 8, replace them with 0, 1, 2.
156 _mesa_consolidate_registers(struct gl_program
*prog
)
158 GLboolean tempUsed
[MAX_PROGRAM_TEMPS
];
159 GLint tempMap
[MAX_PROGRAM_TEMPS
];
160 GLuint tempMax
= 0, i
;
163 _mesa_printf("Optimize: Begin register consolidation\n");
166 memset(tempUsed
, 0, sizeof(tempUsed
));
168 for (i
= 0; i
< MAX_PROGRAM_TEMPS
; i
++) {
172 /* set tempUsed[i] if temporary [i] is referenced */
173 for (i
= 0; i
< prog
->NumInstructions
; i
++) {
174 const struct prog_instruction
*inst
= prog
->Instructions
+ i
;
175 const GLuint numSrc
= _mesa_num_inst_src_regs(inst
->Opcode
);
177 for (j
= 0; j
< numSrc
; j
++) {
178 if (inst
->SrcReg
[j
].File
== PROGRAM_TEMPORARY
) {
179 const GLuint index
= inst
->SrcReg
[j
].Index
;
180 ASSERT(index
< MAX_PROGRAM_TEMPS
);
181 tempUsed
[index
] = GL_TRUE
;
182 tempMax
= MAX2(tempMax
, index
);
186 if (inst
->DstReg
.File
== PROGRAM_TEMPORARY
) {
187 const GLuint index
= inst
->DstReg
.Index
;
188 ASSERT(index
< MAX_PROGRAM_TEMPS
);
189 tempUsed
[index
] = GL_TRUE
;
190 tempMax
= MAX2(tempMax
, index
);
194 /* allocate a new index for each temp that's used */
197 for (i
= 0; i
<= tempMax
; i
++) {
199 tempMap
[i
] = freeTemp
++;
200 /*_mesa_printf("replace %u with %u\n", i, tempMap[i]);*/
203 if (freeTemp
== tempMax
+ 1) {
204 /* no consolidation possible */
208 _mesa_printf("Replace regs 0..%u with 0..%u\n", tempMax
, freeTemp
-1);
212 replace_regs(prog
, PROGRAM_TEMPORARY
, tempMap
);
215 _mesa_printf("Optimize: End register consolidation\n");
221 * Remove dead instructions from the given program.
222 * This is very primitive for now. Basically look for temp registers
223 * that are written to but never read. Remove any instructions that
224 * write to such registers. Be careful with condition code setters.
227 _mesa_remove_dead_code(struct gl_program
*prog
)
229 GLboolean tempRead
[MAX_PROGRAM_TEMPS
][4];
230 GLboolean
*removeInst
; /* per-instruction removal flag */
231 GLuint i
, rem
= 0, comp
;
233 memset(tempRead
, 0, sizeof(tempRead
));
236 _mesa_printf("Optimize: Begin dead code removal\n");
237 /*_mesa_print_program(prog);*/
240 removeInst
= (GLboolean
*)
241 _mesa_calloc(prog
->NumInstructions
* sizeof(GLboolean
));
243 /* Determine which temps are read and written */
244 for (i
= 0; i
< prog
->NumInstructions
; i
++) {
245 const struct prog_instruction
*inst
= prog
->Instructions
+ i
;
246 const GLuint numSrc
= _mesa_num_inst_src_regs(inst
->Opcode
);
250 for (j
= 0; j
< numSrc
; j
++) {
251 if (inst
->SrcReg
[j
].File
== PROGRAM_TEMPORARY
) {
252 const GLuint index
= inst
->SrcReg
[j
].Index
;
254 ASSERT(index
< MAX_PROGRAM_TEMPS
);
255 read_mask
= get_src_arg_mask(inst
, j
);
257 if (inst
->SrcReg
[j
].RelAddr
) {
259 _mesa_printf("abort remove dead code (indirect temp)\n");
263 for (comp
= 0; comp
< 4; comp
++) {
264 GLuint swz
= (inst
->SrcReg
[j
].Swizzle
>> (3 * comp
)) & 0x7;
266 if ((read_mask
& (1 << comp
)) == 0)
271 tempRead
[index
][0] = GL_TRUE
;
274 tempRead
[index
][1] = GL_TRUE
;
277 tempRead
[index
][2] = GL_TRUE
;
280 tempRead
[index
][3] = GL_TRUE
;
288 if (inst
->DstReg
.File
== PROGRAM_TEMPORARY
) {
289 const GLuint index
= inst
->DstReg
.Index
;
290 ASSERT(index
< MAX_PROGRAM_TEMPS
);
292 if (inst
->DstReg
.RelAddr
) {
294 _mesa_printf("abort remove dead code (indirect temp)\n");
298 if (inst
->CondUpdate
) {
299 /* If we're writing to this register and setting condition
300 * codes we cannot remove the instruction. Prevent removal
301 * by setting the 'read' flag.
303 tempRead
[index
][0] = GL_TRUE
;
304 tempRead
[index
][1] = GL_TRUE
;
305 tempRead
[index
][2] = GL_TRUE
;
306 tempRead
[index
][3] = GL_TRUE
;
311 /* find instructions that write to dead registers, flag for removal */
312 for (i
= 0; i
< prog
->NumInstructions
; i
++) {
313 struct prog_instruction
*inst
= prog
->Instructions
+ i
;
314 const GLuint numDst
= _mesa_num_inst_dst_regs(inst
->Opcode
);
316 if (numDst
!= 0 && inst
->DstReg
.File
== PROGRAM_TEMPORARY
) {
317 GLint chan
, index
= inst
->DstReg
.Index
;
319 for (chan
= 0; chan
< 4; chan
++) {
320 if (!tempRead
[index
][chan
] &&
321 inst
->DstReg
.WriteMask
& (1 << chan
)) {
323 _mesa_printf("Remove writemask on %u.%c\n", i
,
324 chan
== 3 ? 'w' : 'x' + chan
);
326 inst
->DstReg
.WriteMask
&= ~(1 << chan
);
331 if (inst
->DstReg
.WriteMask
== 0) {
332 /* If we cleared all writes, the instruction can be removed. */
334 _mesa_printf("Remove instruction %u: \n", i
);
335 removeInst
[i
] = GL_TRUE
;
340 /* now remove the instructions which aren't needed */
341 rem
= remove_instructions(prog
, removeInst
);
344 _mesa_printf("Optimize: End dead code removal.\n");
345 _mesa_printf(" %u channel writes removed\n", rem
);
346 _mesa_printf(" %u instructions removed\n", rem
);
347 /*_mesa_print_program(prog);*/
351 _mesa_free(removeInst
);
364 * Scan forward in program from 'start' for the next occurance of TEMP[index].
365 * Return READ, WRITE, FLOW or END to indicate the next usage or an indicator
366 * that we can't look further.
369 find_next_temp_use(const struct gl_program
*prog
, GLuint start
, GLuint index
)
373 for (i
= start
; i
< prog
->NumInstructions
; i
++) {
374 const struct prog_instruction
*inst
= prog
->Instructions
+ i
;
375 switch (inst
->Opcode
) {
383 const GLuint numSrc
= _mesa_num_inst_src_regs(inst
->Opcode
);
385 for (j
= 0; j
< numSrc
; j
++) {
386 if (inst
->SrcReg
[j
].File
== PROGRAM_TEMPORARY
&&
387 inst
->SrcReg
[j
].Index
== index
)
390 if (inst
->DstReg
.File
== PROGRAM_TEMPORARY
&&
391 inst
->DstReg
.Index
== index
)
400 static GLboolean
_mesa_is_flow_control_opcode(enum prog_opcode opcode
)
422 * Try to remove use of extraneous MOV instructions, to free them up for dead
426 _mesa_remove_extra_move_use(struct gl_program
*prog
)
431 _mesa_printf("Optimize: Begin remove extra move use\n");
432 _mesa_print_program(prog
);
436 * Look for sequences such as this:
439 * FOO tmpY, tmpX, arg1;
443 * FOO tmpY, arg0, arg1;
446 for (i
= 0; i
+ 1 < prog
->NumInstructions
; i
++) {
447 const struct prog_instruction
*mov
= prog
->Instructions
+ i
;
449 if (mov
->Opcode
!= OPCODE_MOV
||
450 mov
->DstReg
.File
!= PROGRAM_TEMPORARY
||
451 mov
->DstReg
.RelAddr
||
452 mov
->DstReg
.CondMask
!= COND_TR
||
453 mov
->SaturateMode
!= SATURATE_OFF
||
454 mov
->SrcReg
[0].RelAddr
)
457 /* Walk through remaining instructions until the or src reg gets
458 * rewritten or we get into some flow-control, eliminating the use of
461 for (j
= i
+ 1; j
< prog
->NumInstructions
; j
++) {
462 struct prog_instruction
*inst2
= prog
->Instructions
+ j
;
465 if (_mesa_is_flow_control_opcode(inst2
->Opcode
))
468 /* First rewrite this instruction's args if appropriate. */
469 for (arg
= 0; arg
< _mesa_num_inst_src_regs(inst2
->Opcode
); arg
++) {
471 int read_mask
= get_src_arg_mask(inst2
, arg
);
473 if (inst2
->SrcReg
[arg
].File
!= mov
->DstReg
.File
||
474 inst2
->SrcReg
[arg
].Index
!= mov
->DstReg
.Index
||
475 inst2
->SrcReg
[arg
].RelAddr
||
476 inst2
->SrcReg
[arg
].Abs
)
479 /* Check that all the sources for this arg of inst2 come from inst1
482 for (comp
= 0; comp
< 4; comp
++) {
483 int src_swz
= GET_SWZ(inst2
->SrcReg
[arg
].Swizzle
, comp
);
485 /* If the MOV didn't write that channel, can't use it. */
486 if ((read_mask
& (1 << comp
)) &&
487 src_swz
<= SWIZZLE_W
&&
488 (mov
->DstReg
.WriteMask
& (1 << src_swz
)) == 0)
494 /* Adjust the swizzles of inst2 to point at MOV's source */
495 for (comp
= 0; comp
< 4; comp
++) {
496 int inst2_swz
= GET_SWZ(inst2
->SrcReg
[arg
].Swizzle
, comp
);
498 if (inst2_swz
<= SWIZZLE_W
) {
499 GLuint s
= GET_SWZ(mov
->SrcReg
[0].Swizzle
, inst2_swz
);
500 inst2
->SrcReg
[arg
].Swizzle
&= ~(7 << (3 * comp
));
501 inst2
->SrcReg
[arg
].Swizzle
|= s
<< (3 * comp
);
502 inst2
->SrcReg
[arg
].Negate
^= (((mov
->SrcReg
[0].Negate
>>
503 inst2_swz
) & 0x1) << comp
);
506 inst2
->SrcReg
[arg
].File
= mov
->SrcReg
[0].File
;
507 inst2
->SrcReg
[arg
].Index
= mov
->SrcReg
[0].Index
;
510 /* If this instruction overwrote part of the move, our time is up. */
511 if ((inst2
->DstReg
.File
== mov
->DstReg
.File
&&
512 (inst2
->DstReg
.RelAddr
||
513 inst2
->DstReg
.Index
== mov
->DstReg
.Index
)) ||
514 (inst2
->DstReg
.File
== mov
->SrcReg
[0].File
&&
515 (inst2
->DstReg
.RelAddr
||
516 inst2
->DstReg
.Index
== mov
->SrcReg
[0].Index
)))
522 _mesa_printf("Optimize: End remove extra move use.\n");
523 /*_mesa_print_program(prog);*/
528 * Try to remove extraneous MOV instructions from the given program.
531 _mesa_remove_extra_moves(struct gl_program
*prog
)
533 GLboolean
*removeInst
; /* per-instruction removal flag */
534 GLuint i
, rem
, loopNesting
= 0, subroutineNesting
= 0;
537 _mesa_printf("Optimize: Begin remove extra moves\n");
538 _mesa_print_program(prog
);
541 removeInst
= (GLboolean
*)
542 _mesa_calloc(prog
->NumInstructions
* sizeof(GLboolean
));
545 * Look for sequences such as this:
546 * FOO tmpX, arg0, arg1;
549 * FOO tmpY, arg0, arg1;
552 for (i
= 0; i
< prog
->NumInstructions
; i
++) {
553 const struct prog_instruction
*inst
= prog
->Instructions
+ i
;
555 switch (inst
->Opcode
) {
571 subroutineNesting
== 0 &&
572 inst
->SrcReg
[0].File
== PROGRAM_TEMPORARY
&&
573 inst
->SrcReg
[0].Swizzle
== SWIZZLE_XYZW
) {
574 /* see if this MOV can be removed */
575 const GLuint tempIndex
= inst
->SrcReg
[0].Index
;
576 struct prog_instruction
*prevInst
;
579 /* get pointer to previous instruction */
581 while (removeInst
[prevI
] && prevI
> 0)
583 prevInst
= prog
->Instructions
+ prevI
;
585 if (prevInst
->DstReg
.File
== PROGRAM_TEMPORARY
&&
586 prevInst
->DstReg
.Index
== tempIndex
&&
587 prevInst
->DstReg
.WriteMask
== WRITEMASK_XYZW
) {
589 enum temp_use next_use
=
590 find_next_temp_use(prog
, i
+ 1, tempIndex
);
592 if (next_use
== WRITE
|| next_use
== END
) {
593 /* OK, we can safely remove this MOV instruction.
595 * prevI: FOO tempIndex, x, y;
596 * i: MOV z, tempIndex;
598 * prevI: FOO z, x, y;
601 /* patch up prev inst */
602 prevInst
->DstReg
.File
= inst
->DstReg
.File
;
603 prevInst
->DstReg
.Index
= inst
->DstReg
.Index
;
605 /* flag this instruction for removal */
606 removeInst
[i
] = GL_TRUE
;
609 _mesa_printf("Remove MOV at %u\n", i
);
610 _mesa_printf("new prev inst %u: ", prevI
);
611 _mesa_print_instruction(prevInst
);
622 /* now remove the instructions which aren't needed */
623 rem
= remove_instructions(prog
, removeInst
);
625 _mesa_free(removeInst
);
628 _mesa_printf("Optimize: End remove extra moves. %u instructions removed\n", rem
);
629 /*_mesa_print_program(prog);*/
634 /** A live register interval */
637 GLuint Reg
; /** The temporary register index */
638 GLuint Start
, End
; /** Start/end instruction numbers */
642 /** A list of register intervals */
646 struct interval Intervals
[MAX_PROGRAM_TEMPS
];
651 append_interval(struct interval_list
*list
, const struct interval
*inv
)
653 list
->Intervals
[list
->Num
++] = *inv
;
657 /** Insert interval inv into list, sorted by interval end */
659 insert_interval_by_end(struct interval_list
*list
, const struct interval
*inv
)
661 /* XXX we could do a binary search insertion here since list is sorted */
662 GLint i
= list
->Num
- 1;
663 while (i
>= 0 && list
->Intervals
[i
].End
> inv
->End
) {
664 list
->Intervals
[i
+ 1] = list
->Intervals
[i
];
667 list
->Intervals
[i
+ 1] = *inv
;
673 for (i
= 0; i
+ 1 < list
->Num
; i
++) {
674 ASSERT(list
->Intervals
[i
].End
<= list
->Intervals
[i
+ 1].End
);
681 /** Remove the given interval from the interval list */
683 remove_interval(struct interval_list
*list
, const struct interval
*inv
)
685 /* XXX we could binary search since list is sorted */
687 for (k
= 0; k
< list
->Num
; k
++) {
688 if (list
->Intervals
[k
].Reg
== inv
->Reg
) {
689 /* found, remove it */
690 ASSERT(list
->Intervals
[k
].Start
== inv
->Start
);
691 ASSERT(list
->Intervals
[k
].End
== inv
->End
);
692 while (k
< list
->Num
- 1) {
693 list
->Intervals
[k
] = list
->Intervals
[k
+ 1];
703 /** called by qsort() */
705 compare_start(const void *a
, const void *b
)
707 const struct interval
*ia
= (const struct interval
*) a
;
708 const struct interval
*ib
= (const struct interval
*) b
;
709 if (ia
->Start
< ib
->Start
)
711 else if (ia
->Start
> ib
->Start
)
717 /** sort the interval list according to interval starts */
719 sort_interval_list_by_start(struct interval_list
*list
)
721 qsort(list
->Intervals
, list
->Num
, sizeof(struct interval
), compare_start
);
725 for (i
= 0; i
+ 1 < list
->Num
; i
++) {
726 ASSERT(list
->Intervals
[i
].Start
<= list
->Intervals
[i
+ 1].Start
);
734 * Update the intermediate interval info for register 'index' and
738 update_interval(GLint intBegin
[], GLint intEnd
[], GLuint index
, GLuint ic
)
740 ASSERT(index
< MAX_PROGRAM_TEMPS
);
741 if (intBegin
[index
] == -1) {
742 ASSERT(intEnd
[index
] == -1);
743 intBegin
[index
] = intEnd
[index
] = ic
;
752 * Find first/last instruction that references each temporary register.
755 _mesa_find_temp_intervals(const struct prog_instruction
*instructions
,
756 GLuint numInstructions
,
757 GLint intBegin
[MAX_PROGRAM_TEMPS
],
758 GLint intEnd
[MAX_PROGRAM_TEMPS
])
762 GLuint Start
, End
; /**< Start, end instructions of loop */
764 struct loop_info loopStack
[MAX_LOOP_NESTING
];
765 GLuint loopStackDepth
= 0;
768 for (i
= 0; i
< MAX_PROGRAM_TEMPS
; i
++){
769 intBegin
[i
] = intEnd
[i
] = -1;
772 /* Scan instructions looking for temporary registers */
773 for (i
= 0; i
< numInstructions
; i
++) {
774 const struct prog_instruction
*inst
= instructions
+ i
;
775 if (inst
->Opcode
== OPCODE_BGNLOOP
) {
776 loopStack
[loopStackDepth
].Start
= i
;
777 loopStack
[loopStackDepth
].End
= inst
->BranchTarget
;
780 else if (inst
->Opcode
== OPCODE_ENDLOOP
) {
783 else if (inst
->Opcode
== OPCODE_CAL
) {
787 const GLuint numSrc
= 3;/*_mesa_num_inst_src_regs(inst->Opcode);*/
789 for (j
= 0; j
< numSrc
; j
++) {
790 if (inst
->SrcReg
[j
].File
== PROGRAM_TEMPORARY
) {
791 const GLuint index
= inst
->SrcReg
[j
].Index
;
792 if (inst
->SrcReg
[j
].RelAddr
)
794 update_interval(intBegin
, intEnd
, index
, i
);
795 if (loopStackDepth
> 0) {
796 /* extend temp register's interval to end of loop */
797 GLuint loopEnd
= loopStack
[loopStackDepth
- 1].End
;
798 update_interval(intBegin
, intEnd
, index
, loopEnd
);
802 if (inst
->DstReg
.File
== PROGRAM_TEMPORARY
) {
803 const GLuint index
= inst
->DstReg
.Index
;
804 if (inst
->DstReg
.RelAddr
)
806 update_interval(intBegin
, intEnd
, index
, i
);
807 if (loopStackDepth
> 0) {
808 /* extend temp register's interval to end of loop */
809 GLuint loopEnd
= loopStack
[loopStackDepth
- 1].End
;
810 update_interval(intBegin
, intEnd
, index
, loopEnd
);
821 * Find the live intervals for each temporary register in the program.
822 * For register R, the interval [A,B] indicates that R is referenced
823 * from instruction A through instruction B.
824 * Special consideration is needed for loops and subroutines.
825 * \return GL_TRUE if success, GL_FALSE if we cannot proceed for some reason
828 find_live_intervals(struct gl_program
*prog
,
829 struct interval_list
*liveIntervals
)
831 GLint intBegin
[MAX_PROGRAM_TEMPS
], intEnd
[MAX_PROGRAM_TEMPS
];
835 * Note: we'll return GL_FALSE below if we find relative indexing
836 * into the TEMP register file. We can't handle that yet.
837 * We also give up on subroutines for now.
841 _mesa_printf("Optimize: Begin find intervals\n");
844 /* build intermediate arrays */
845 if (!_mesa_find_temp_intervals(prog
->Instructions
, prog
->NumInstructions
,
849 /* Build live intervals list from intermediate arrays */
850 liveIntervals
->Num
= 0;
851 for (i
= 0; i
< MAX_PROGRAM_TEMPS
; i
++) {
852 if (intBegin
[i
] >= 0) {
855 inv
.Start
= intBegin
[i
];
857 append_interval(liveIntervals
, &inv
);
861 /* Sort the list according to interval starts */
862 sort_interval_list_by_start(liveIntervals
);
865 /* print interval info */
866 for (i
= 0; i
< liveIntervals
->Num
; i
++) {
867 const struct interval
*inv
= liveIntervals
->Intervals
+ i
;
868 _mesa_printf("Reg[%d] live [%d, %d]:",
869 inv
->Reg
, inv
->Start
, inv
->End
);
872 for (j
= 0; j
< inv
->Start
; j
++)
874 for (j
= inv
->Start
; j
<= inv
->End
; j
++)
885 /** Scan the array of used register flags to find free entry */
887 alloc_register(GLboolean usedRegs
[MAX_PROGRAM_TEMPS
])
890 for (k
= 0; k
< MAX_PROGRAM_TEMPS
; k
++) {
892 usedRegs
[k
] = GL_TRUE
;
901 * This function implements "Linear Scan Register Allocation" to reduce
902 * the number of temporary registers used by the program.
904 * We compute the "live interval" for all temporary registers then
905 * examine the overlap of the intervals to allocate new registers.
906 * Basically, if two intervals do not overlap, they can use the same register.
909 _mesa_reallocate_registers(struct gl_program
*prog
)
911 struct interval_list liveIntervals
;
912 GLint registerMap
[MAX_PROGRAM_TEMPS
];
913 GLboolean usedRegs
[MAX_PROGRAM_TEMPS
];
918 _mesa_printf("Optimize: Begin live-interval register reallocation\n");
919 _mesa_print_program(prog
);
922 for (i
= 0; i
< MAX_PROGRAM_TEMPS
; i
++){
924 usedRegs
[i
] = GL_FALSE
;
927 if (!find_live_intervals(prog
, &liveIntervals
)) {
929 _mesa_printf("Aborting register reallocation\n");
934 struct interval_list activeIntervals
;
935 activeIntervals
.Num
= 0;
937 /* loop over live intervals, allocating a new register for each */
938 for (i
= 0; i
< liveIntervals
.Num
; i
++) {
939 const struct interval
*live
= liveIntervals
.Intervals
+ i
;
942 _mesa_printf("Consider register %u\n", live
->Reg
);
944 /* Expire old intervals. Intervals which have ended with respect
945 * to the live interval can have their remapped registers freed.
949 for (j
= 0; j
< activeIntervals
.Num
; j
++) {
950 const struct interval
*inv
= activeIntervals
.Intervals
+ j
;
951 if (inv
->End
>= live
->Start
) {
952 /* Stop now. Since the activeInterval list is sorted
953 * we know we don't have to go further.
958 /* Interval 'inv' has expired */
959 const GLint regNew
= registerMap
[inv
->Reg
];
963 _mesa_printf(" expire interval for reg %u\n", inv
->Reg
);
965 /* remove interval j from active list */
966 remove_interval(&activeIntervals
, inv
);
967 j
--; /* counter-act j++ in for-loop above */
969 /* return register regNew to the free pool */
971 _mesa_printf(" free reg %d\n", regNew
);
972 ASSERT(usedRegs
[regNew
] == GL_TRUE
);
973 usedRegs
[regNew
] = GL_FALSE
;
978 /* find a free register for this live interval */
980 const GLint k
= alloc_register(usedRegs
);
982 /* out of registers, give up */
985 registerMap
[live
->Reg
] = k
;
986 maxTemp
= MAX2(maxTemp
, k
);
988 _mesa_printf(" remap register %u -> %d\n", live
->Reg
, k
);
991 /* Insert this live interval into the active list which is sorted
992 * by increasing end points.
994 insert_interval_by_end(&activeIntervals
, live
);
998 if (maxTemp
+ 1 < liveIntervals
.Num
) {
999 /* OK, we've reduced the number of registers needed.
1000 * Scan the program and replace all the old temporary register
1001 * indexes with the new indexes.
1003 replace_regs(prog
, PROGRAM_TEMPORARY
, registerMap
);
1005 prog
->NumTemporaries
= maxTemp
+ 1;
1009 _mesa_printf("Optimize: End live-interval register reallocation\n");
1010 _mesa_printf("Num temp regs before: %u after: %u\n",
1011 liveIntervals
.Num
, maxTemp
+ 1);
1012 _mesa_print_program(prog
);
1018 * Apply optimizations to the given program to eliminate unnecessary
1019 * instructions, temp regs, etc.
1022 _mesa_optimize_program(GLcontext
*ctx
, struct gl_program
*program
)
1024 _mesa_remove_extra_move_use(program
);
1027 _mesa_remove_dead_code(program
);
1029 if (0) /* not tested much yet */
1030 _mesa_remove_extra_moves(program
);
1033 _mesa_consolidate_registers(program
);
1035 _mesa_reallocate_registers(program
);