2 * Mesa 3-D graphics library
4 * Copyright (C) 2009 VMware, Inc. All Rights Reserved.
6 * Permission is hereby granted, free of charge, to any person obtaining a
7 * copy of this software and associated documentation files (the "Software"),
8 * to deal in the Software without restriction, including without limitation
9 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
10 * and/or sell copies of the Software, and to permit persons to whom the
11 * Software is furnished to do so, subject to the following conditions:
13 * The above copyright notice and this permission notice shall be included
14 * in all copies or substantial portions of the Software.
16 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
17 * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
18 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
19 * VMWARE BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
20 * AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
21 * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
26 #include "main/glheader.h"
27 #include "main/context.h"
28 #include "main/macros.h"
30 #include "prog_instruction.h"
31 #include "prog_optimize.h"
32 #include "prog_print.h"
35 #define MAX_LOOP_NESTING 50
36 /* MAX_PROGRAM_TEMPS is a low number (256), and we want to be able to
37 * register allocate many temporary values into that small number of
38 * temps. So allow large temporary indices coming into the register
41 #define REG_ALLOCATE_MAX_PROGRAM_TEMPS ((1 << INST_INDEX_BITS) - 1)
43 static GLboolean dbg
= GL_FALSE
;
48 * Returns the mask of channels (bitmask of WRITEMASK_X,Y,Z,W) which
49 * are read from the given src in this instruction, We also provide
50 * one optional masks which may mask other components in the dst
54 get_src_arg_mask(const struct prog_instruction
*inst
,
55 GLuint arg
, GLuint dst_mask
)
57 GLuint read_mask
, channel_mask
;
60 assert(arg
< _mesa_num_inst_src_regs(inst
->Opcode
));
62 /* Form the dst register, find the written channels */
63 switch (inst
->Opcode
) {
83 channel_mask
= inst
->DstReg
.WriteMask
& dst_mask
;
92 channel_mask
= WRITEMASK_X
;
95 channel_mask
= WRITEMASK_XY
;
99 channel_mask
= WRITEMASK_XYZ
;
102 channel_mask
= WRITEMASK_XYZW
;
106 /* Now, given the src swizzle and the written channels, find which
107 * components are actually read
110 for (comp
= 0; comp
< 4; ++comp
) {
111 const GLuint coord
= GET_SWZ(inst
->SrcReg
[arg
].Swizzle
, comp
);
112 if (channel_mask
& (1 << comp
) && coord
<= SWIZZLE_W
)
113 read_mask
|= 1 << coord
;
121 * For a MOV instruction, compute a write mask when src register also has
125 get_dst_mask_for_mov(const struct prog_instruction
*mov
, GLuint src_mask
)
127 const GLuint mask
= mov
->DstReg
.WriteMask
;
129 GLuint updated_mask
= 0x0;
131 assert(mov
->Opcode
== OPCODE_MOV
);
133 for (comp
= 0; comp
< 4; ++comp
) {
135 if ((mask
& (1 << comp
)) == 0)
137 src_comp
= GET_SWZ(mov
->SrcReg
[0].Swizzle
, comp
);
138 if ((src_mask
& (1 << src_comp
)) == 0)
140 updated_mask
|= 1 << comp
;
148 * Ensure that the swizzle is regular. That is, all of the swizzle
149 * terms are SWIZZLE_X,Y,Z,W and not SWIZZLE_ZERO or SWIZZLE_ONE.
152 is_swizzle_regular(GLuint swz
)
154 return GET_SWZ(swz
,0) <= SWIZZLE_W
&&
155 GET_SWZ(swz
,1) <= SWIZZLE_W
&&
156 GET_SWZ(swz
,2) <= SWIZZLE_W
&&
157 GET_SWZ(swz
,3) <= SWIZZLE_W
;
162 * In 'prog' remove instruction[i] if removeFlags[i] == TRUE.
163 * \return number of instructions removed
166 remove_instructions(struct gl_program
*prog
, const GLboolean
*removeFlags
)
168 GLint i
, removeEnd
= 0, removeCount
= 0;
169 GLuint totalRemoved
= 0;
172 for (i
= prog
->NumInstructions
- 1; i
>= 0; i
--) {
173 if (removeFlags
[i
]) {
175 if (removeCount
== 0) {
176 /* begin a run of instructions to remove */
181 /* extend the run of instructions to remove */
186 /* don't remove this instruction, but check if the preceeding
187 * instructions are to be removed.
189 if (removeCount
> 0) {
190 GLint removeStart
= removeEnd
- removeCount
+ 1;
191 _mesa_delete_instructions(prog
, removeStart
, removeCount
);
192 removeStart
= removeCount
= 0; /* reset removal info */
196 /* Finish removing if the first instruction was to be removed. */
197 if (removeCount
> 0) {
198 GLint removeStart
= removeEnd
- removeCount
+ 1;
199 _mesa_delete_instructions(prog
, removeStart
, removeCount
);
206 * Remap register indexes according to map.
207 * \param prog the program to search/replace
208 * \param file the type of register file to search/replace
209 * \param map maps old register indexes to new indexes
212 replace_regs(struct gl_program
*prog
, gl_register_file file
, const GLint map
[])
216 for (i
= 0; i
< prog
->NumInstructions
; i
++) {
217 struct prog_instruction
*inst
= prog
->Instructions
+ i
;
218 const GLuint numSrc
= _mesa_num_inst_src_regs(inst
->Opcode
);
220 for (j
= 0; j
< numSrc
; j
++) {
221 if (inst
->SrcReg
[j
].File
== file
) {
222 GLuint index
= inst
->SrcReg
[j
].Index
;
223 assert(map
[index
] >= 0);
224 inst
->SrcReg
[j
].Index
= map
[index
];
227 if (inst
->DstReg
.File
== file
) {
228 const GLuint index
= inst
->DstReg
.Index
;
229 assert(map
[index
] >= 0);
230 inst
->DstReg
.Index
= map
[index
];
237 * Remove dead instructions from the given program.
238 * This is very primitive for now. Basically look for temp registers
239 * that are written to but never read. Remove any instructions that
240 * write to such registers. Be careful with condition code setters.
243 _mesa_remove_dead_code_global(struct gl_program
*prog
)
245 GLboolean tempRead
[REG_ALLOCATE_MAX_PROGRAM_TEMPS
][4];
246 GLboolean
*removeInst
; /* per-instruction removal flag */
247 GLuint i
, rem
= 0, comp
;
249 memset(tempRead
, 0, sizeof(tempRead
));
252 printf("Optimize: Begin dead code removal\n");
253 /*_mesa_print_program(prog);*/
257 calloc(prog
->NumInstructions
, sizeof(GLboolean
));
259 /* Determine which temps are read and written */
260 for (i
= 0; i
< prog
->NumInstructions
; i
++) {
261 const struct prog_instruction
*inst
= prog
->Instructions
+ i
;
262 const GLuint numSrc
= _mesa_num_inst_src_regs(inst
->Opcode
);
266 for (j
= 0; j
< numSrc
; j
++) {
267 if (inst
->SrcReg
[j
].File
== PROGRAM_TEMPORARY
) {
268 const GLuint index
= inst
->SrcReg
[j
].Index
;
270 assert(index
< REG_ALLOCATE_MAX_PROGRAM_TEMPS
);
271 read_mask
= get_src_arg_mask(inst
, j
, NO_MASK
);
273 if (inst
->SrcReg
[j
].RelAddr
) {
275 printf("abort remove dead code (indirect temp)\n");
279 for (comp
= 0; comp
< 4; comp
++) {
280 const GLuint swz
= GET_SWZ(inst
->SrcReg
[j
].Swizzle
, comp
);
281 if (swz
<= SWIZZLE_W
) {
282 if ((read_mask
& (1 << swz
)) == 0)
284 tempRead
[index
][swz
] = GL_TRUE
;
291 if (inst
->DstReg
.File
== PROGRAM_TEMPORARY
) {
292 const GLuint index
= inst
->DstReg
.Index
;
293 assert(index
< REG_ALLOCATE_MAX_PROGRAM_TEMPS
);
295 if (inst
->DstReg
.RelAddr
) {
297 printf("abort remove dead code (indirect temp)\n");
303 /* find instructions that write to dead registers, flag for removal */
304 for (i
= 0; i
< prog
->NumInstructions
; i
++) {
305 struct prog_instruction
*inst
= prog
->Instructions
+ i
;
306 const GLuint numDst
= _mesa_num_inst_dst_regs(inst
->Opcode
);
308 if (numDst
!= 0 && inst
->DstReg
.File
== PROGRAM_TEMPORARY
) {
309 GLint chan
, index
= inst
->DstReg
.Index
;
311 for (chan
= 0; chan
< 4; chan
++) {
312 if (!tempRead
[index
][chan
] &&
313 inst
->DstReg
.WriteMask
& (1 << chan
)) {
315 printf("Remove writemask on %u.%c\n", i
,
316 chan
== 3 ? 'w' : 'x' + chan
);
318 inst
->DstReg
.WriteMask
&= ~(1 << chan
);
323 if (inst
->DstReg
.WriteMask
== 0) {
324 /* If we cleared all writes, the instruction can be removed. */
326 printf("Remove instruction %u: \n", i
);
327 removeInst
[i
] = GL_TRUE
;
332 /* now remove the instructions which aren't needed */
333 rem
= remove_instructions(prog
, removeInst
);
336 printf("Optimize: End dead code removal.\n");
337 printf(" %u channel writes removed\n", rem
);
338 printf(" %u instructions removed\n", rem
);
339 /*_mesa_print_program(prog);*/
358 * Scan forward in program from 'start' for the next occurances of TEMP[index].
359 * We look if an instruction reads the component given by the masks and if they
361 * Return READ, WRITE, FLOW or END to indicate the next usage or an indicator
362 * that we can't look further.
365 find_next_use(const struct gl_program
*prog
,
372 for (i
= start
; i
< prog
->NumInstructions
; i
++) {
373 const struct prog_instruction
*inst
= prog
->Instructions
+ i
;
374 switch (inst
->Opcode
) {
390 const GLuint numSrc
= _mesa_num_inst_src_regs(inst
->Opcode
);
392 for (j
= 0; j
< numSrc
; j
++) {
393 if (inst
->SrcReg
[j
].RelAddr
||
394 (inst
->SrcReg
[j
].File
== PROGRAM_TEMPORARY
&&
395 inst
->SrcReg
[j
].Index
== (GLint
)index
&&
396 (get_src_arg_mask(inst
,j
,NO_MASK
) & mask
)))
399 if (_mesa_num_inst_dst_regs(inst
->Opcode
) == 1 &&
400 inst
->DstReg
.File
== PROGRAM_TEMPORARY
&&
401 inst
->DstReg
.Index
== index
) {
402 mask
&= ~inst
->DstReg
.WriteMask
;
414 * Is the given instruction opcode a flow-control opcode?
415 * XXX maybe move this into prog_instruction.[ch]
418 _mesa_is_flow_control_opcode(enum prog_opcode opcode
)
440 * Test if the given instruction is a simple MOV (no conditional updating,
441 * not relative addressing, no negation/abs, etc).
444 can_downward_mov_be_modifed(const struct prog_instruction
*mov
)
447 mov
->Opcode
== OPCODE_MOV
&&
448 mov
->SrcReg
[0].RelAddr
== 0 &&
449 mov
->SrcReg
[0].Negate
== 0 &&
450 mov
->SrcReg
[0].Abs
== 0 &&
451 mov
->DstReg
.RelAddr
== 0;
456 can_upward_mov_be_modifed(const struct prog_instruction
*mov
)
459 can_downward_mov_be_modifed(mov
) &&
460 mov
->DstReg
.File
== PROGRAM_TEMPORARY
&&
466 * Try to remove use of extraneous MOV instructions, to free them up for dead
470 _mesa_remove_extra_move_use(struct gl_program
*prog
)
475 printf("Optimize: Begin remove extra move use\n");
476 _mesa_print_program(prog
);
480 * Look for sequences such as this:
483 * FOO tmpY, tmpX, arg1;
487 * FOO tmpY, arg0, arg1;
490 for (i
= 0; i
+ 1 < prog
->NumInstructions
; i
++) {
491 const struct prog_instruction
*mov
= prog
->Instructions
+ i
;
492 GLuint dst_mask
, src_mask
;
493 if (can_upward_mov_be_modifed(mov
) == GL_FALSE
)
496 /* Scanning the code, we maintain the components which are still active in
499 dst_mask
= mov
->DstReg
.WriteMask
;
500 src_mask
= get_src_arg_mask(mov
, 0, NO_MASK
);
502 /* Walk through remaining instructions until the or src reg gets
503 * rewritten or we get into some flow-control, eliminating the use of
506 for (j
= i
+ 1; j
< prog
->NumInstructions
; j
++) {
507 struct prog_instruction
*inst2
= prog
->Instructions
+ j
;
510 if (_mesa_is_flow_control_opcode(inst2
->Opcode
))
513 /* First rewrite this instruction's args if appropriate. */
514 for (arg
= 0; arg
< _mesa_num_inst_src_regs(inst2
->Opcode
); arg
++) {
515 GLuint comp
, read_mask
;
517 if (inst2
->SrcReg
[arg
].File
!= mov
->DstReg
.File
||
518 inst2
->SrcReg
[arg
].Index
!= mov
->DstReg
.Index
||
519 inst2
->SrcReg
[arg
].RelAddr
||
520 inst2
->SrcReg
[arg
].Abs
)
522 read_mask
= get_src_arg_mask(inst2
, arg
, NO_MASK
);
524 /* Adjust the swizzles of inst2 to point at MOV's source if ALL the
525 * components read still come from the mov instructions
527 if (is_swizzle_regular(inst2
->SrcReg
[arg
].Swizzle
) &&
528 (read_mask
& dst_mask
) == read_mask
) {
529 for (comp
= 0; comp
< 4; comp
++) {
530 const GLuint inst2_swz
=
531 GET_SWZ(inst2
->SrcReg
[arg
].Swizzle
, comp
);
532 const GLuint s
= GET_SWZ(mov
->SrcReg
[0].Swizzle
, inst2_swz
);
533 inst2
->SrcReg
[arg
].Swizzle
&= ~(7 << (3 * comp
));
534 inst2
->SrcReg
[arg
].Swizzle
|= s
<< (3 * comp
);
535 inst2
->SrcReg
[arg
].Negate
^= (((mov
->SrcReg
[0].Negate
>>
536 inst2_swz
) & 0x1) << comp
);
538 inst2
->SrcReg
[arg
].File
= mov
->SrcReg
[0].File
;
539 inst2
->SrcReg
[arg
].Index
= mov
->SrcReg
[0].Index
;
543 /* The source of MOV is written. This potentially deactivates some
544 * components from the src and dst of the MOV instruction
546 if (inst2
->DstReg
.File
== mov
->DstReg
.File
&&
547 (inst2
->DstReg
.RelAddr
||
548 inst2
->DstReg
.Index
== mov
->DstReg
.Index
)) {
549 dst_mask
&= ~inst2
->DstReg
.WriteMask
;
550 src_mask
= get_src_arg_mask(mov
, 0, dst_mask
);
553 /* Idem when the destination of mov is written */
554 if (inst2
->DstReg
.File
== mov
->SrcReg
[0].File
&&
555 (inst2
->DstReg
.RelAddr
||
556 inst2
->DstReg
.Index
== mov
->SrcReg
[0].Index
)) {
557 src_mask
&= ~inst2
->DstReg
.WriteMask
;
558 dst_mask
&= get_dst_mask_for_mov(mov
, src_mask
);
566 printf("Optimize: End remove extra move use.\n");
567 /*_mesa_print_program(prog);*/
573 * Complements dead_code_global. Try to remove code in block of code by
574 * carefully monitoring the swizzles. Both functions should be merged into one
575 * with a proper control flow graph
578 _mesa_remove_dead_code_local(struct gl_program
*prog
)
580 GLboolean
*removeInst
;
581 GLuint i
, arg
, rem
= 0;
584 calloc(prog
->NumInstructions
, sizeof(GLboolean
));
586 for (i
= 0; i
< prog
->NumInstructions
; i
++) {
587 const struct prog_instruction
*inst
= prog
->Instructions
+ i
;
588 const GLuint index
= inst
->DstReg
.Index
;
589 const GLuint mask
= inst
->DstReg
.WriteMask
;
592 /* We must deactivate the pass as soon as some indirection is used */
593 if (inst
->DstReg
.RelAddr
)
595 for (arg
= 0; arg
< _mesa_num_inst_src_regs(inst
->Opcode
); arg
++)
596 if (inst
->SrcReg
[arg
].RelAddr
)
599 if (_mesa_is_flow_control_opcode(inst
->Opcode
) ||
600 _mesa_num_inst_dst_regs(inst
->Opcode
) == 0 ||
601 inst
->DstReg
.File
!= PROGRAM_TEMPORARY
||
602 inst
->DstReg
.RelAddr
)
605 use
= find_next_use(prog
, i
+1, index
, mask
);
606 if (use
== WRITE
|| use
== END
)
607 removeInst
[i
] = GL_TRUE
;
610 rem
= remove_instructions(prog
, removeInst
);
619 * Try to inject the destination of mov as the destination of inst and recompute
620 * the swizzles operators for the sources of inst if required. Return GL_TRUE
621 * of the substitution was possible, GL_FALSE otherwise
624 _mesa_merge_mov_into_inst(struct prog_instruction
*inst
,
625 const struct prog_instruction
*mov
)
627 /* Indirection table which associates destination and source components for
628 * the mov instruction
630 const GLuint mask
= get_src_arg_mask(mov
, 0, NO_MASK
);
632 /* Some components are not written by inst. We cannot remove the mov */
633 if (mask
!= (inst
->DstReg
.WriteMask
& mask
))
636 inst
->Saturate
|= mov
->Saturate
;
638 /* Depending on the instruction, we may need to recompute the swizzles.
639 * Also, some other instructions (like TEX) are not linear. We will only
640 * consider completely active sources and destinations
642 switch (inst
->Opcode
) {
644 /* Carstesian instructions: we compute the swizzle */
654 GLuint dst_to_src_comp
[4] = {0,0,0,0};
655 GLuint dst_comp
, arg
;
656 for (dst_comp
= 0; dst_comp
< 4; ++dst_comp
) {
657 if (mov
->DstReg
.WriteMask
& (1 << dst_comp
)) {
658 const GLuint src_comp
= GET_SWZ(mov
->SrcReg
[0].Swizzle
, dst_comp
);
659 assert(src_comp
< 4);
660 dst_to_src_comp
[dst_comp
] = src_comp
;
664 /* Patch each source of the instruction */
665 for (arg
= 0; arg
< _mesa_num_inst_src_regs(inst
->Opcode
); arg
++) {
666 const GLuint arg_swz
= inst
->SrcReg
[arg
].Swizzle
;
667 inst
->SrcReg
[arg
].Swizzle
= 0;
669 /* Reset each active component of the swizzle */
670 for (dst_comp
= 0; dst_comp
< 4; ++dst_comp
) {
671 GLuint src_comp
, arg_comp
;
672 if ((mov
->DstReg
.WriteMask
& (1 << dst_comp
)) == 0)
674 src_comp
= dst_to_src_comp
[dst_comp
];
675 assert(src_comp
< 4);
676 arg_comp
= GET_SWZ(arg_swz
, src_comp
);
677 assert(arg_comp
< 4);
678 inst
->SrcReg
[arg
].Swizzle
|= arg_comp
<< (3*dst_comp
);
681 inst
->DstReg
= mov
->DstReg
;
685 /* Dot products and scalar instructions: we only change the destination */
696 inst
->DstReg
= mov
->DstReg
;
699 /* All other instructions require fully active components with no swizzle */
701 if (mov
->SrcReg
[0].Swizzle
!= SWIZZLE_XYZW
||
702 inst
->DstReg
.WriteMask
!= WRITEMASK_XYZW
)
704 inst
->DstReg
= mov
->DstReg
;
711 * Try to remove extraneous MOV instructions from the given program.
714 _mesa_remove_extra_moves(struct gl_program
*prog
)
716 GLboolean
*removeInst
; /* per-instruction removal flag */
717 GLuint i
, rem
= 0, nesting
= 0;
720 printf("Optimize: Begin remove extra moves\n");
721 _mesa_print_program(prog
);
725 calloc(prog
->NumInstructions
, sizeof(GLboolean
));
728 * Look for sequences such as this:
729 * FOO tmpX, arg0, arg1;
732 * FOO tmpY, arg0, arg1;
735 for (i
= 0; i
< prog
->NumInstructions
; i
++) {
736 const struct prog_instruction
*mov
= prog
->Instructions
+ i
;
738 switch (mov
->Opcode
) {
751 can_downward_mov_be_modifed(mov
) &&
752 mov
->SrcReg
[0].File
== PROGRAM_TEMPORARY
&&
756 /* see if this MOV can be removed */
757 const GLuint id
= mov
->SrcReg
[0].Index
;
758 struct prog_instruction
*prevInst
;
761 /* get pointer to previous instruction */
763 while (prevI
> 0 && removeInst
[prevI
])
765 prevInst
= prog
->Instructions
+ prevI
;
767 if (prevInst
->DstReg
.File
== PROGRAM_TEMPORARY
&&
768 prevInst
->DstReg
.Index
== id
&&
769 prevInst
->DstReg
.RelAddr
== 0) {
771 const GLuint dst_mask
= prevInst
->DstReg
.WriteMask
;
772 enum inst_use next_use
= find_next_use(prog
, i
+1, id
, dst_mask
);
774 if (next_use
== WRITE
|| next_use
== END
) {
775 /* OK, we can safely remove this MOV instruction.
777 * prevI: FOO tempIndex, x, y;
778 * i: MOV z, tempIndex;
780 * prevI: FOO z, x, y;
782 if (_mesa_merge_mov_into_inst(prevInst
, mov
)) {
783 removeInst
[i
] = GL_TRUE
;
785 printf("Remove MOV at %u\n", i
);
786 printf("new prev inst %u: ", prevI
);
787 _mesa_print_instruction(prevInst
);
799 /* now remove the instructions which aren't needed */
800 rem
= remove_instructions(prog
, removeInst
);
805 printf("Optimize: End remove extra moves. %u instructions removed\n", rem
);
806 /*_mesa_print_program(prog);*/
813 /** A live register interval */
816 GLuint Reg
; /** The temporary register index */
817 GLuint Start
, End
; /** Start/end instruction numbers */
821 /** A list of register intervals */
825 struct interval Intervals
[REG_ALLOCATE_MAX_PROGRAM_TEMPS
];
830 append_interval(struct interval_list
*list
, const struct interval
*inv
)
832 list
->Intervals
[list
->Num
++] = *inv
;
836 /** Insert interval inv into list, sorted by interval end */
838 insert_interval_by_end(struct interval_list
*list
, const struct interval
*inv
)
840 /* XXX we could do a binary search insertion here since list is sorted */
841 GLint i
= list
->Num
- 1;
842 while (i
>= 0 && list
->Intervals
[i
].End
> inv
->End
) {
843 list
->Intervals
[i
+ 1] = list
->Intervals
[i
];
846 list
->Intervals
[i
+ 1] = *inv
;
852 for (i
= 0; i
+ 1 < list
->Num
; i
++) {
853 assert(list
->Intervals
[i
].End
<= list
->Intervals
[i
+ 1].End
);
860 /** Remove the given interval from the interval list */
862 remove_interval(struct interval_list
*list
, const struct interval
*inv
)
864 /* XXX we could binary search since list is sorted */
866 for (k
= 0; k
< list
->Num
; k
++) {
867 if (list
->Intervals
[k
].Reg
== inv
->Reg
) {
868 /* found, remove it */
869 assert(list
->Intervals
[k
].Start
== inv
->Start
);
870 assert(list
->Intervals
[k
].End
== inv
->End
);
871 while (k
< list
->Num
- 1) {
872 list
->Intervals
[k
] = list
->Intervals
[k
+ 1];
882 /** called by qsort() */
884 compare_start(const void *a
, const void *b
)
886 const struct interval
*ia
= (const struct interval
*) a
;
887 const struct interval
*ib
= (const struct interval
*) b
;
888 if (ia
->Start
< ib
->Start
)
890 else if (ia
->Start
> ib
->Start
)
897 /** sort the interval list according to interval starts */
899 sort_interval_list_by_start(struct interval_list
*list
)
901 qsort(list
->Intervals
, list
->Num
, sizeof(struct interval
), compare_start
);
905 for (i
= 0; i
+ 1 < list
->Num
; i
++) {
906 assert(list
->Intervals
[i
].Start
<= list
->Intervals
[i
+ 1].Start
);
914 GLuint Start
, End
; /**< Start, end instructions of loop */
918 * Update the intermediate interval info for register 'index' and
922 update_interval(GLint intBegin
[], GLint intEnd
[],
923 struct loop_info
*loopStack
, GLuint loopStackDepth
,
924 GLuint index
, GLuint ic
)
930 /* If the register is used in a loop, extend its lifetime through the end
931 * of the outermost loop that doesn't contain its definition.
933 for (i
= 0; i
< loopStackDepth
; i
++) {
934 if (intBegin
[index
] < loopStack
[i
].Start
) {
935 end
= loopStack
[i
].End
;
940 /* Variables that are live at the end of a loop will also be live at the
941 * beginning, so an instruction inside of a loop should have its live
942 * interval begin at the start of the outermost loop.
944 if (loopStackDepth
> 0 && ic
> loopStack
[0].Start
&& ic
< loopStack
[0].End
) {
945 begin
= loopStack
[0].Start
;
948 assert(index
< REG_ALLOCATE_MAX_PROGRAM_TEMPS
);
949 if (intBegin
[index
] == -1) {
950 assert(intEnd
[index
] == -1);
951 intBegin
[index
] = begin
;
961 * Find first/last instruction that references each temporary register.
964 _mesa_find_temp_intervals(const struct prog_instruction
*instructions
,
965 GLuint numInstructions
,
966 GLint intBegin
[REG_ALLOCATE_MAX_PROGRAM_TEMPS
],
967 GLint intEnd
[REG_ALLOCATE_MAX_PROGRAM_TEMPS
])
969 struct loop_info loopStack
[MAX_LOOP_NESTING
];
970 GLuint loopStackDepth
= 0;
973 for (i
= 0; i
< REG_ALLOCATE_MAX_PROGRAM_TEMPS
; i
++){
974 intBegin
[i
] = intEnd
[i
] = -1;
977 /* Scan instructions looking for temporary registers */
978 for (i
= 0; i
< numInstructions
; i
++) {
979 const struct prog_instruction
*inst
= instructions
+ i
;
980 if (inst
->Opcode
== OPCODE_BGNLOOP
) {
981 loopStack
[loopStackDepth
].Start
= i
;
982 loopStack
[loopStackDepth
].End
= inst
->BranchTarget
;
985 else if (inst
->Opcode
== OPCODE_ENDLOOP
) {
988 else if (inst
->Opcode
== OPCODE_CAL
) {
992 const GLuint numSrc
= 3;/*_mesa_num_inst_src_regs(inst->Opcode);*/
994 for (j
= 0; j
< numSrc
; j
++) {
995 if (inst
->SrcReg
[j
].File
== PROGRAM_TEMPORARY
) {
996 const GLuint index
= inst
->SrcReg
[j
].Index
;
997 if (inst
->SrcReg
[j
].RelAddr
)
999 update_interval(intBegin
, intEnd
, loopStack
, loopStackDepth
,
1003 if (inst
->DstReg
.File
== PROGRAM_TEMPORARY
) {
1004 const GLuint index
= inst
->DstReg
.Index
;
1005 if (inst
->DstReg
.RelAddr
)
1007 update_interval(intBegin
, intEnd
, loopStack
, loopStackDepth
,
1018 * Find the live intervals for each temporary register in the program.
1019 * For register R, the interval [A,B] indicates that R is referenced
1020 * from instruction A through instruction B.
1021 * Special consideration is needed for loops and subroutines.
1022 * \return GL_TRUE if success, GL_FALSE if we cannot proceed for some reason
1025 find_live_intervals(struct gl_program
*prog
,
1026 struct interval_list
*liveIntervals
)
1028 GLint intBegin
[REG_ALLOCATE_MAX_PROGRAM_TEMPS
];
1029 GLint intEnd
[REG_ALLOCATE_MAX_PROGRAM_TEMPS
];
1033 * Note: we'll return GL_FALSE below if we find relative indexing
1034 * into the TEMP register file. We can't handle that yet.
1035 * We also give up on subroutines for now.
1039 printf("Optimize: Begin find intervals\n");
1042 /* build intermediate arrays */
1043 if (!_mesa_find_temp_intervals(prog
->Instructions
, prog
->NumInstructions
,
1047 /* Build live intervals list from intermediate arrays */
1048 liveIntervals
->Num
= 0;
1049 for (i
= 0; i
< REG_ALLOCATE_MAX_PROGRAM_TEMPS
; i
++) {
1050 if (intBegin
[i
] >= 0) {
1051 struct interval inv
;
1053 inv
.Start
= intBegin
[i
];
1054 inv
.End
= intEnd
[i
];
1055 append_interval(liveIntervals
, &inv
);
1059 /* Sort the list according to interval starts */
1060 sort_interval_list_by_start(liveIntervals
);
1063 /* print interval info */
1064 for (i
= 0; i
< liveIntervals
->Num
; i
++) {
1065 const struct interval
*inv
= liveIntervals
->Intervals
+ i
;
1066 printf("Reg[%d] live [%d, %d]:",
1067 inv
->Reg
, inv
->Start
, inv
->End
);
1070 for (j
= 0; j
< inv
->Start
; j
++)
1072 for (j
= inv
->Start
; j
<= inv
->End
; j
++)
1083 /** Scan the array of used register flags to find free entry */
1085 alloc_register(GLboolean usedRegs
[REG_ALLOCATE_MAX_PROGRAM_TEMPS
])
1088 for (k
= 0; k
< REG_ALLOCATE_MAX_PROGRAM_TEMPS
; k
++) {
1090 usedRegs
[k
] = GL_TRUE
;
1099 * This function implements "Linear Scan Register Allocation" to reduce
1100 * the number of temporary registers used by the program.
1102 * We compute the "live interval" for all temporary registers then
1103 * examine the overlap of the intervals to allocate new registers.
1104 * Basically, if two intervals do not overlap, they can use the same register.
1107 _mesa_reallocate_registers(struct gl_program
*prog
)
1109 struct interval_list liveIntervals
;
1110 GLint registerMap
[REG_ALLOCATE_MAX_PROGRAM_TEMPS
];
1111 GLboolean usedRegs
[REG_ALLOCATE_MAX_PROGRAM_TEMPS
];
1116 printf("Optimize: Begin live-interval register reallocation\n");
1117 _mesa_print_program(prog
);
1120 for (i
= 0; i
< REG_ALLOCATE_MAX_PROGRAM_TEMPS
; i
++){
1121 registerMap
[i
] = -1;
1122 usedRegs
[i
] = GL_FALSE
;
1125 if (!find_live_intervals(prog
, &liveIntervals
)) {
1127 printf("Aborting register reallocation\n");
1132 struct interval_list activeIntervals
;
1133 activeIntervals
.Num
= 0;
1135 /* loop over live intervals, allocating a new register for each */
1136 for (i
= 0; i
< liveIntervals
.Num
; i
++) {
1137 const struct interval
*live
= liveIntervals
.Intervals
+ i
;
1140 printf("Consider register %u\n", live
->Reg
);
1142 /* Expire old intervals. Intervals which have ended with respect
1143 * to the live interval can have their remapped registers freed.
1147 for (j
= 0; j
< (GLint
) activeIntervals
.Num
; j
++) {
1148 const struct interval
*inv
= activeIntervals
.Intervals
+ j
;
1149 if (inv
->End
>= live
->Start
) {
1150 /* Stop now. Since the activeInterval list is sorted
1151 * we know we don't have to go further.
1156 /* Interval 'inv' has expired */
1157 const GLint regNew
= registerMap
[inv
->Reg
];
1158 assert(regNew
>= 0);
1161 printf(" expire interval for reg %u\n", inv
->Reg
);
1163 /* remove interval j from active list */
1164 remove_interval(&activeIntervals
, inv
);
1165 j
--; /* counter-act j++ in for-loop above */
1167 /* return register regNew to the free pool */
1169 printf(" free reg %d\n", regNew
);
1170 assert(usedRegs
[regNew
] == GL_TRUE
);
1171 usedRegs
[regNew
] = GL_FALSE
;
1176 /* find a free register for this live interval */
1178 const GLint k
= alloc_register(usedRegs
);
1180 /* out of registers, give up */
1183 registerMap
[live
->Reg
] = k
;
1184 maxTemp
= MAX2(maxTemp
, k
);
1186 printf(" remap register %u -> %d\n", live
->Reg
, k
);
1189 /* Insert this live interval into the active list which is sorted
1190 * by increasing end points.
1192 insert_interval_by_end(&activeIntervals
, live
);
1196 if (maxTemp
+ 1 < (GLint
) liveIntervals
.Num
) {
1197 /* OK, we've reduced the number of registers needed.
1198 * Scan the program and replace all the old temporary register
1199 * indexes with the new indexes.
1201 replace_regs(prog
, PROGRAM_TEMPORARY
, registerMap
);
1203 prog
->NumTemporaries
= maxTemp
+ 1;
1207 printf("Optimize: End live-interval register reallocation\n");
1208 printf("Num temp regs before: %u after: %u\n",
1209 liveIntervals
.Num
, maxTemp
+ 1);
1210 _mesa_print_program(prog
);
1217 print_it(struct gl_context
*ctx
, struct gl_program
*program
, const char *txt
) {
1218 fprintf(stderr
, "%s (%u inst):\n", txt
, program
->NumInstructions
);
1219 _mesa_print_program(program
);
1220 _mesa_print_program_parameters(ctx
, program
);
1221 fprintf(stderr
, "\n\n");
1226 * This pass replaces CMP T0, T1 T2 T0 with MOV T0, T2 when the CMP
1227 * instruction is the first instruction to write to register T0. The are
1228 * several lowering passes done in GLSL IR (e.g. branches and
1229 * relative addressing) that create a large number of conditional assignments
1230 * that ir_to_mesa converts to CMP instructions like the one mentioned above.
1232 * Here is why this conversion is safe:
1233 * CMP T0, T1 T2 T0 can be expanded to:
1239 * If (T1 < 0.0) evaluates to true then our replacement MOV T0, T2 is the same
1240 * as the original program. If (T1 < 0.0) evaluates to false, executing
1241 * MOV T0, T0 will store a garbage value in T0 since T0 is uninitialized.
1242 * Therefore, it doesn't matter that we are replacing MOV T0, T0 with MOV T0, T2
1243 * because any instruction that was going to read from T0 after this was going
1244 * to read a garbage value anyway.
1247 _mesa_simplify_cmp(struct gl_program
* program
)
1249 GLuint tempWrites
[REG_ALLOCATE_MAX_PROGRAM_TEMPS
];
1250 GLuint outputWrites
[MAX_PROGRAM_OUTPUTS
];
1254 printf("Optimize: Begin reads without writes\n");
1255 _mesa_print_program(program
);
1258 for (i
= 0; i
< REG_ALLOCATE_MAX_PROGRAM_TEMPS
; i
++) {
1262 for (i
= 0; i
< MAX_PROGRAM_OUTPUTS
; i
++) {
1263 outputWrites
[i
] = 0;
1266 for (i
= 0; i
< program
->NumInstructions
; i
++) {
1267 struct prog_instruction
*inst
= program
->Instructions
+ i
;
1268 GLuint prevWriteMask
;
1270 /* Give up if we encounter relative addressing or flow control. */
1271 if (_mesa_is_flow_control_opcode(inst
->Opcode
) || inst
->DstReg
.RelAddr
) {
1275 if (inst
->DstReg
.File
== PROGRAM_OUTPUT
) {
1276 assert(inst
->DstReg
.Index
< MAX_PROGRAM_OUTPUTS
);
1277 prevWriteMask
= outputWrites
[inst
->DstReg
.Index
];
1278 outputWrites
[inst
->DstReg
.Index
] |= inst
->DstReg
.WriteMask
;
1279 } else if (inst
->DstReg
.File
== PROGRAM_TEMPORARY
) {
1280 assert(inst
->DstReg
.Index
< REG_ALLOCATE_MAX_PROGRAM_TEMPS
);
1281 prevWriteMask
= tempWrites
[inst
->DstReg
.Index
];
1282 tempWrites
[inst
->DstReg
.Index
] |= inst
->DstReg
.WriteMask
;
1284 /* No other register type can be a destination register. */
1288 /* For a CMP to be considered a conditional write, the destination
1289 * register and source register two must be the same. */
1290 if (inst
->Opcode
== OPCODE_CMP
1291 && !(inst
->DstReg
.WriteMask
& prevWriteMask
)
1292 && inst
->SrcReg
[2].File
== inst
->DstReg
.File
1293 && inst
->SrcReg
[2].Index
== inst
->DstReg
.Index
1294 && inst
->DstReg
.WriteMask
== get_src_arg_mask(inst
, 2, NO_MASK
)) {
1296 inst
->Opcode
= OPCODE_MOV
;
1297 inst
->SrcReg
[0] = inst
->SrcReg
[1];
1299 /* Unused operands are expected to have the file set to
1300 * PROGRAM_UNDEFINED. This is how _mesa_init_instructions initializes
1301 * all of the sources.
1303 inst
->SrcReg
[1].File
= PROGRAM_UNDEFINED
;
1304 inst
->SrcReg
[1].Swizzle
= SWIZZLE_NOOP
;
1305 inst
->SrcReg
[2].File
= PROGRAM_UNDEFINED
;
1306 inst
->SrcReg
[2].Swizzle
= SWIZZLE_NOOP
;
1310 printf("Optimize: End reads without writes\n");
1311 _mesa_print_program(program
);
1316 * Apply optimizations to the given program to eliminate unnecessary
1317 * instructions, temp regs, etc.
1320 _mesa_optimize_program(struct gl_context
*ctx
, struct gl_program
*program
)
1322 GLboolean any_change
;
1324 _mesa_simplify_cmp(program
);
1325 /* Stop when no modifications were output */
1327 any_change
= GL_FALSE
;
1328 _mesa_remove_extra_move_use(program
);
1329 if (_mesa_remove_dead_code_global(program
))
1330 any_change
= GL_TRUE
;
1331 if (_mesa_remove_extra_moves(program
))
1332 any_change
= GL_TRUE
;
1333 if (_mesa_remove_dead_code_local(program
))
1334 any_change
= GL_TRUE
;
1336 any_change
= _mesa_constant_fold(program
) || any_change
;
1337 _mesa_reallocate_registers(program
);
1338 } while (any_change
);