2 * Copyright © 2017 Gert Wollny
4 * Permission is hereby granted, free of charge, to any person obtaining a
5 * copy of this software and associated documentation files (the "Software"),
6 * to deal in the Software without restriction, including without limitation
7 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
8 * and/or sell copies of the Software, and to permit persons to whom the
9 * Software is furnished to do so, subject to the following conditions:
11 * The above copyright notice and this permission notice (including the next
12 * paragraph) shall be included in all copies or substantial portions of the
15 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
16 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
17 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
18 * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
19 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
20 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
21 * DEALINGS IN THE SOFTWARE.
24 #include "st_glsl_to_tgsi_temprename.h"
25 #include "st_glsl_to_tgsi_array_merge.h"
26 #include "tgsi/tgsi_info.h"
27 #include "tgsi/tgsi_strings.h"
28 #include "program/prog_instruction.h"
29 #include "util/bitscan.h"
33 /* std::sort is significantly faster than qsort */
42 #include "program/prog_print.h"
43 #include "util/debug.h"
49 /* If <windows.h> is included this is defined and clashes with
50 * std::numeric_limits<>::max()
56 using std::numeric_limits
;
58 /* Without c++11 define the nullptr for forward-compatibility
59 * and better readibility */
60 #if __cplusplus < 201103L
65 /* Prepare to make it possible to specify log file */
66 static std::ostream
& debug_log
= cerr
;
68 /* Helper function to check whether we want to seen debugging output */
69 static inline bool is_debug_enabled ()
71 static int debug_enabled
= -1;
72 if (debug_enabled
< 0)
73 debug_enabled
= env_var_as_boolean("GLSL_TO_TGSI_RENAME_DEBUG", false);
74 return debug_enabled
> 0;
76 #define RENAME_DEBUG(X) if (is_debug_enabled()) do { X; } while (false);
78 #define RENAME_DEBUG(X)
83 enum prog_scope_type
{
84 outer_scope
, /* Outer program scope */
85 loop_body
, /* Inside a loop */
86 if_branch
, /* Inside if branch */
87 else_branch
, /* Inside else branch */
88 switch_body
, /* Inside switch statmenet */
89 switch_case_branch
, /* Inside switch case statmenet */
90 switch_default_branch
, /* Inside switch default statmenet */
96 prog_scope(prog_scope
*parent
, prog_scope_type type
, int id
,
97 int depth
, int begin
);
99 prog_scope_type
type() const;
100 prog_scope
*parent() const;
101 int nesting_depth() const;
105 int loop_break_line() const;
107 const prog_scope
*in_else_scope() const;
108 const prog_scope
*in_ifelse_scope() const;
109 const prog_scope
*in_parent_ifelse_scope() const;
110 const prog_scope
*innermost_loop() const;
111 const prog_scope
*outermost_loop() const;
112 const prog_scope
*enclosing_conditional() const;
114 bool is_loop() const;
115 bool is_in_loop() const;
116 bool is_switchcase_scope_in_loop() const;
117 bool is_conditional() const;
118 bool is_child_of(const prog_scope
*scope
) const;
119 bool is_child_of_ifelse_id_sibling(const prog_scope
*scope
) const;
121 bool break_is_for_switchcase() const;
122 bool contains_range_of(const prog_scope
& other
) const;
124 void set_end(int end
);
125 void set_loop_break_line(int line
);
128 prog_scope_type scope_type
;
130 int scope_nesting_depth
;
134 prog_scope
*parent_scope
;
137 /* Some storage class to encapsulate the prog_scope (de-)allocations */
138 class prog_scope_storage
{
140 prog_scope_storage(void *mem_ctx
, int n
);
141 ~prog_scope_storage();
142 prog_scope
* create(prog_scope
*p
, prog_scope_type type
, int id
,
143 int lvl
, int s_begin
);
150 /* Class to track the access to a component of a temporary register. */
152 class temp_comp_access
{
156 void record_read(int line
, prog_scope
*scope
);
157 void record_write(int line
, prog_scope
*scope
);
158 register_live_range
get_required_live_range();
160 void propagate_live_range_to_dominant_write_scope();
161 bool conditional_ifelse_write_in_loop() const;
163 void record_ifelse_write(const prog_scope
& scope
);
164 void record_if_write(const prog_scope
& scope
);
165 void record_else_write(const prog_scope
& scope
);
167 prog_scope
*last_read_scope
;
168 prog_scope
*first_read_scope
;
169 prog_scope
*first_write_scope
;
176 /* This member variable tracks the current resolution of conditional writing
177 * to this temporary in IF/ELSE clauses.
179 * The initial value "conditionality_untouched" indicates that this
180 * temporary has not yet been written to within an if clause.
182 * A positive (other than "conditionality_untouched") number refers to the
183 * last loop id for which the write was resolved as unconditional. With each
184 * new loop this value will be overwitten by "conditionality_unresolved"
185 * on entering the first IF clause writing this temporary.
187 * The value "conditionality_unresolved" indicates that no resolution has
188 * been achieved so far. If the variable is set to this value at the end of
189 * the processing of the whole shader it also indicates a conditional write.
191 * The value "write_is_conditional" marks that the variable is written
192 * conditionally (i.e. not in all relevant IF/ELSE code path pairs) in at
195 int conditionality_in_loop_id
;
197 /* Helper constants to make the tracking code more readable. */
198 static const int write_is_conditional
= -1;
199 static const int conditionality_unresolved
= 0;
200 static const int conditionality_untouched
;
201 static const int write_is_unconditional
;
203 /* A bit field tracking the nexting levels of if-else clauses where the
204 * temporary has (so far) been written to in the if branch, but not in the
207 unsigned int if_scope_write_flags
;
209 int next_ifelse_nesting_depth
;
210 static const int supported_ifelse_nesting_depth
= 32;
212 /* Tracks the last if scope in which the temporary was written to
213 * without a write in the correspondig else branch. Is also used
214 * to track read-before-write in the according scope.
216 const prog_scope
*current_unpaired_if_write_scope
;
218 /* Flag to resolve read-before-write in the else scope. */
219 bool was_written_in_current_else_scope
;
223 temp_comp_access::conditionality_untouched
= numeric_limits
<int>::max();
226 temp_comp_access::write_is_unconditional
= numeric_limits
<int>::max() - 1;
228 /* Class to track the access to all components of a temporary register. */
232 void record_read(int line
, prog_scope
*scope
, int swizzle
);
233 void record_write(int line
, prog_scope
*scope
, int writemask
);
234 register_live_range
get_required_live_range();
236 void update_access_mask(int mask
);
238 temp_comp_access comp
[4];
240 bool needs_component_tracking
;
243 /* Class to track array access.
244 * Compared to the temporary tracking this is very simplified, mainly because
245 * with the likely indirect access one can not really establish access
246 * patterns for individual elements. Instead the life range evaluation is
247 * always for the whole array, handles only loops and the fact whether a
248 * value was accessed conditionally in a loop.
253 void record_access(int line
, prog_scope
*scope
, int swizzle
);
254 void get_required_live_range(array_live_range
&lr
);
258 prog_scope
*first_access_scope
;
259 prog_scope
*last_access_scope
;
260 unsigned accumulated_swizzle
:4;
261 int conditional_access_in_loop
:1;
264 prog_scope_storage::prog_scope_storage(void *mc
, int n
):
268 storage
= ralloc_array(mem_ctx
, prog_scope
, n
);
271 prog_scope_storage::~prog_scope_storage()
273 ralloc_free(storage
);
277 prog_scope_storage::create(prog_scope
*p
, prog_scope_type type
, int id
,
278 int lvl
, int s_begin
)
280 storage
[current_slot
] = prog_scope(p
, type
, id
, lvl
, s_begin
);
281 return &storage
[current_slot
++];
284 prog_scope::prog_scope(prog_scope
*parent
, prog_scope_type type
, int id
,
285 int depth
, int scope_begin
):
288 scope_nesting_depth(depth
),
289 scope_begin(scope_begin
),
291 break_loop_line(numeric_limits
<int>::max()),
296 prog_scope_type
prog_scope::type() const
301 prog_scope
*prog_scope::parent() const
306 int prog_scope::nesting_depth() const
308 return scope_nesting_depth
;
311 bool prog_scope::is_loop() const
313 return (scope_type
== loop_body
);
316 bool prog_scope::is_in_loop() const
318 if (scope_type
== loop_body
)
322 return parent_scope
->is_in_loop();
327 const prog_scope
*prog_scope::innermost_loop() const
329 if (scope_type
== loop_body
)
333 return parent_scope
->innermost_loop();
338 const prog_scope
*prog_scope::outermost_loop() const
340 const prog_scope
*loop
= nullptr;
341 const prog_scope
*p
= this;
344 if (p
->type() == loop_body
)
352 bool prog_scope::is_child_of_ifelse_id_sibling(const prog_scope
*scope
) const
354 const prog_scope
*my_parent
= in_parent_ifelse_scope();
356 /* is a direct child? */
357 if (my_parent
== scope
)
359 /* is a child of the conditions sibling? */
360 if (my_parent
->id() == scope
->id())
362 my_parent
= my_parent
->in_parent_ifelse_scope();
367 bool prog_scope::is_child_of(const prog_scope
*scope
) const
369 const prog_scope
*my_parent
= parent();
371 if (my_parent
== scope
)
373 my_parent
= my_parent
->parent();
378 const prog_scope
*prog_scope::enclosing_conditional() const
380 if (is_conditional())
384 return parent_scope
->enclosing_conditional();
389 bool prog_scope::contains_range_of(const prog_scope
& other
) const
391 return (begin() <= other
.begin()) && (end() >= other
.end());
394 bool prog_scope::is_conditional() const
396 return scope_type
== if_branch
||
397 scope_type
== else_branch
||
398 scope_type
== switch_case_branch
||
399 scope_type
== switch_default_branch
;
402 const prog_scope
*prog_scope::in_else_scope() const
404 if (scope_type
== else_branch
)
408 return parent_scope
->in_else_scope();
413 const prog_scope
*prog_scope::in_parent_ifelse_scope() const
416 return parent_scope
->in_ifelse_scope();
421 const prog_scope
*prog_scope::in_ifelse_scope() const
423 if (scope_type
== if_branch
||
424 scope_type
== else_branch
)
428 return parent_scope
->in_ifelse_scope();
433 bool prog_scope::is_switchcase_scope_in_loop() const
435 return (scope_type
== switch_case_branch
||
436 scope_type
== switch_default_branch
) &&
440 bool prog_scope::break_is_for_switchcase() const
442 if (scope_type
== loop_body
)
445 if (scope_type
== switch_case_branch
||
446 scope_type
== switch_default_branch
||
447 scope_type
== switch_body
)
451 return parent_scope
->break_is_for_switchcase();
456 int prog_scope::id() const
461 int prog_scope::begin() const
466 int prog_scope::end() const
471 void prog_scope::set_end(int end
)
477 void prog_scope::set_loop_break_line(int line
)
479 if (scope_type
== loop_body
) {
480 break_loop_line
= MIN2(break_loop_line
, line
);
483 parent()->set_loop_break_line(line
);
487 int prog_scope::loop_break_line() const
489 return break_loop_line
;
492 temp_access::temp_access():
494 needs_component_tracking(false)
498 void temp_access::update_access_mask(int mask
)
500 if (access_mask
&& access_mask
!= mask
)
501 needs_component_tracking
= true;
505 void temp_access::record_write(int line
, prog_scope
*scope
, int writemask
)
507 update_access_mask(writemask
);
509 if (writemask
& WRITEMASK_X
)
510 comp
[0].record_write(line
, scope
);
511 if (writemask
& WRITEMASK_Y
)
512 comp
[1].record_write(line
, scope
);
513 if (writemask
& WRITEMASK_Z
)
514 comp
[2].record_write(line
, scope
);
515 if (writemask
& WRITEMASK_W
)
516 comp
[3].record_write(line
, scope
);
519 void temp_access::record_read(int line
, prog_scope
*scope
, int readmask
)
521 update_access_mask(readmask
);
523 if (readmask
& WRITEMASK_X
)
524 comp
[0].record_read(line
, scope
);
525 if (readmask
& WRITEMASK_Y
)
526 comp
[1].record_read(line
, scope
);
527 if (readmask
& WRITEMASK_Z
)
528 comp
[2].record_read(line
, scope
);
529 if (readmask
& WRITEMASK_W
)
530 comp
[3].record_read(line
, scope
);
533 array_access::array_access():
536 first_access_scope(nullptr),
537 last_access_scope(nullptr),
538 accumulated_swizzle(0),
539 conditional_access_in_loop(false)
543 void array_access::record_access(int line
, prog_scope
*scope
, int swizzle
)
545 if (!first_access_scope
) {
547 first_access_scope
= scope
;
549 last_access_scope
= scope
;
551 accumulated_swizzle
|= swizzle
;
552 if (scope
->in_ifelse_scope() && scope
->innermost_loop())
553 conditional_access_in_loop
= true;
556 void array_access::get_required_live_range(array_live_range
& lr
)
558 RENAME_DEBUG(debug_log
<< "first_access_scope=" << first_access_scope
<< "\n");
559 RENAME_DEBUG(debug_log
<< "last_access_scope=" << last_access_scope
<< "\n");
561 if (first_access_scope
== last_access_scope
) {
562 lr
.set_live_range(first_access
, last_access
);
563 lr
.set_access_mask(accumulated_swizzle
);
567 const prog_scope
*shared_scope
= first_access_scope
;
568 const prog_scope
*other_scope
= last_access_scope
;
570 assert(shared_scope
);
571 RENAME_DEBUG(debug_log
<< "shared_scope=" << shared_scope
<< "\n");
573 if (conditional_access_in_loop
) {
574 const prog_scope
*help
= shared_scope
->outermost_loop();
578 help
= other_scope
->outermost_loop();
582 if (first_access
> shared_scope
->begin())
583 first_access
= shared_scope
->begin();
584 if (last_access
< shared_scope
->end())
585 last_access
= shared_scope
->end();
588 /* See if any of the two is the parent of the other. */
589 if (other_scope
->contains_range_of(*shared_scope
)) {
590 shared_scope
= other_scope
;
591 } else while (!shared_scope
->contains_range_of(*other_scope
)) {
592 assert(shared_scope
->parent());
593 if (shared_scope
->type() == loop_body
) {
594 if (last_access
< shared_scope
->end())
595 last_access
= shared_scope
->end();
597 shared_scope
= shared_scope
->parent();
600 while (shared_scope
!= other_scope
) {
601 if (other_scope
->type() == loop_body
) {
602 if (last_access
< other_scope
->end())
603 last_access
= other_scope
->end();
605 other_scope
= other_scope
->parent();
608 lr
.set_live_range(first_access
, last_access
);
609 lr
.set_access_mask(accumulated_swizzle
);
613 inline static register_live_range
make_live_range(int b
, int e
)
615 register_live_range lt
;
621 register_live_range
temp_access::get_required_live_range()
623 register_live_range result
= make_live_range(-1, -1);
625 unsigned mask
= access_mask
;
627 unsigned chan
= u_bit_scan(&mask
);
628 register_live_range lt
= comp
[chan
].get_required_live_range();
631 if ((result
.begin
< 0) || (result
.begin
> lt
.begin
))
632 result
.begin
= lt
.begin
;
635 if (lt
.end
> result
.end
)
638 if (!needs_component_tracking
)
644 temp_comp_access::temp_comp_access():
645 last_read_scope(nullptr),
646 first_read_scope(nullptr),
647 first_write_scope(nullptr),
651 first_read(numeric_limits
<int>::max()),
652 conditionality_in_loop_id(conditionality_untouched
),
653 if_scope_write_flags(0),
654 next_ifelse_nesting_depth(0),
655 current_unpaired_if_write_scope(nullptr),
656 was_written_in_current_else_scope(false)
660 void temp_comp_access::record_read(int line
, prog_scope
*scope
)
662 last_read_scope
= scope
;
665 if (first_read
> line
) {
667 first_read_scope
= scope
;
670 /* If the conditionality of the first write is already resolved then
671 * no further checks are required.
673 if (conditionality_in_loop_id
== write_is_unconditional
||
674 conditionality_in_loop_id
== write_is_conditional
)
677 /* Check whether we are in a condition within a loop */
678 const prog_scope
*ifelse_scope
= scope
->in_ifelse_scope();
679 const prog_scope
*enclosing_loop
;
680 if (ifelse_scope
&& (enclosing_loop
= ifelse_scope
->innermost_loop())) {
682 /* If we have either not yet written to this register nor writes are
683 * resolved as unconditional in the enclosing loop then check whether
684 * we read before write in an IF/ELSE branch.
686 if ((conditionality_in_loop_id
!= write_is_conditional
) &&
687 (conditionality_in_loop_id
!= enclosing_loop
->id())) {
689 if (current_unpaired_if_write_scope
) {
691 /* Has been written in this or a parent scope? - this makes the temporary
692 * unconditionally set at this point.
694 if (scope
->is_child_of(current_unpaired_if_write_scope
))
697 /* Has been written in the same scope before it was read? */
698 if (ifelse_scope
->type() == if_branch
) {
699 if (current_unpaired_if_write_scope
->id() == scope
->id())
702 if (was_written_in_current_else_scope
)
707 /* The temporary was read (conditionally) before it is written, hence
708 * it should survive a loop. This can be signaled like if it were
709 * conditionally written.
711 conditionality_in_loop_id
= write_is_conditional
;
716 void temp_comp_access::record_write(int line
, prog_scope
*scope
)
720 if (first_write
< 0) {
722 first_write_scope
= scope
;
724 /* If the first write we encounter is not in a conditional branch, or
725 * the conditional write is not within a loop, then this is to be
726 * considered an unconditional dominant write.
728 const prog_scope
*conditional
= scope
->enclosing_conditional();
729 if (!conditional
|| !conditional
->innermost_loop()) {
730 conditionality_in_loop_id
= write_is_unconditional
;
734 /* The conditionality of the first write is already resolved. */
735 if (conditionality_in_loop_id
== write_is_unconditional
||
736 conditionality_in_loop_id
== write_is_conditional
)
739 /* If the nesting depth is larger than the supported level,
740 * then we assume conditional writes.
742 if (next_ifelse_nesting_depth
>= supported_ifelse_nesting_depth
) {
743 conditionality_in_loop_id
= write_is_conditional
;
747 /* If we are in an IF/ELSE scope within a loop and the loop has not
748 * been resolved already, then record this write.
750 const prog_scope
*ifelse_scope
= scope
->in_ifelse_scope();
751 if (ifelse_scope
&& ifelse_scope
->innermost_loop() &&
752 ifelse_scope
->innermost_loop()->id() != conditionality_in_loop_id
)
753 record_ifelse_write(*ifelse_scope
);
756 void temp_comp_access::record_ifelse_write(const prog_scope
& scope
)
758 if (scope
.type() == if_branch
) {
759 /* The first write in an IF branch within a loop implies unresolved
760 * conditionality (if it was untouched or unconditional before).
762 conditionality_in_loop_id
= conditionality_unresolved
;
763 was_written_in_current_else_scope
= false;
764 record_if_write(scope
);
766 was_written_in_current_else_scope
= true;
767 record_else_write(scope
);
771 void temp_comp_access::record_if_write(const prog_scope
& scope
)
773 /* Don't record write if this IF scope if it ...
774 * - is not the first write in this IF scope,
775 * - has already been written in a parent IF scope.
776 * In both cases this write is a secondary write that doesn't contribute
777 * to resolve conditionality.
779 * Record the write if it
780 * - is the first one (obviously),
781 * - happens in an IF branch that is a child of the ELSE branch of the
782 * last active IF/ELSE pair. In this case recording this write is used to
783 * established whether the write is (un-)conditional in the scope enclosing
784 * this outer IF/ELSE pair.
786 if (!current_unpaired_if_write_scope
||
787 (current_unpaired_if_write_scope
->id() != scope
.id() &&
788 scope
.is_child_of_ifelse_id_sibling(current_unpaired_if_write_scope
))) {
789 if_scope_write_flags
|= 1 << next_ifelse_nesting_depth
;
790 current_unpaired_if_write_scope
= &scope
;
791 next_ifelse_nesting_depth
++;
795 void temp_comp_access::record_else_write(const prog_scope
& scope
)
797 int mask
= 1 << (next_ifelse_nesting_depth
- 1);
799 /* If the temporary was written in an IF branch on the same scope level
800 * and this branch is the sibling of this ELSE branch, then we have a
801 * pair of writes that makes write access to this temporary unconditional
802 * in the enclosing scope.
805 if ((if_scope_write_flags
& mask
) &&
806 (scope
.id() == current_unpaired_if_write_scope
->id())) {
807 --next_ifelse_nesting_depth
;
808 if_scope_write_flags
&= ~mask
;
810 /* The following code deals with propagating unconditionality from
811 * inner levels of nested IF/ELSE to the outer levels like in
814 * 2: if (a) { <- start scope A
819 * 7: } else { <- start scope B
822 * A: else <- start scope C
828 const prog_scope
*parent_ifelse
= scope
.parent()->in_ifelse_scope();
830 if (1 << (next_ifelse_nesting_depth
- 1) & if_scope_write_flags
) {
831 /* We are at the end of scope C and already recorded a write
832 * within an IF scope (A), the sibling of the parent ELSE scope B,
833 * and it is not yet resolved. Mark that as the last relevant
834 * IF scope. Below the write will be resolved for the A/B
837 current_unpaired_if_write_scope
= parent_ifelse
;
839 current_unpaired_if_write_scope
= nullptr;
841 /* Promote the first write scope to the enclosing scope because
842 * the current IF/ELSE pair is now irrelevant for the analysis.
843 * This is also required to evaluate the minimum life time for t in
854 first_write_scope
= scope
.parent();
856 /* If some parent is IF/ELSE and in a loop then propagate the
857 * write to that scope. Otherwise the write is unconditional
858 * because it happens in both corresponding IF/ELSE branches
859 * in this loop, and hence, record the loop id to signal the
862 if (parent_ifelse
&& parent_ifelse
->is_in_loop()) {
863 record_ifelse_write(*parent_ifelse
);
865 conditionality_in_loop_id
= scope
.innermost_loop()->id();
868 /* The temporary was not written in the IF branch corresponding
869 * to this ELSE branch, hence the write is conditional.
871 conditionality_in_loop_id
= write_is_conditional
;
875 bool temp_comp_access::conditional_ifelse_write_in_loop() const
877 return conditionality_in_loop_id
<= conditionality_unresolved
;
880 void temp_comp_access::propagate_live_range_to_dominant_write_scope()
882 first_write
= first_write_scope
->begin();
883 int lr
= first_write_scope
->end();
889 register_live_range
temp_comp_access::get_required_live_range()
891 bool keep_for_full_loop
= false;
893 /* This register component is not used at all, or only read,
894 * mark it as unused and ignore it when renaming.
895 * glsl_to_tgsi_visitor::renumber_registers will take care of
896 * eliminating registers that are not written to.
899 return make_live_range(-1, -1);
901 assert(first_write_scope
);
903 /* Only written to, just make sure the register component is not
904 * reused in the range it is used to write to
906 if (!last_read_scope
)
907 return make_live_range(first_write
, last_write
+ 1);
909 const prog_scope
*enclosing_scope_first_read
= first_read_scope
;
910 const prog_scope
*enclosing_scope_first_write
= first_write_scope
;
912 /* We read before writing in a loop
913 * hence the value must survive the loops
915 if ((first_read
<= first_write
) &&
916 first_read_scope
->is_in_loop()) {
917 keep_for_full_loop
= true;
918 enclosing_scope_first_read
= first_read_scope
->outermost_loop();
921 /* A conditional write within a (nested) loop must survive the outermost
922 * loop if the last read was not within the same scope.
924 const prog_scope
*conditional
= enclosing_scope_first_write
->enclosing_conditional();
925 if (conditional
&& !conditional
->contains_range_of(*last_read_scope
) &&
926 (conditional
->is_switchcase_scope_in_loop() ||
927 conditional_ifelse_write_in_loop())) {
928 keep_for_full_loop
= true;
929 enclosing_scope_first_write
= conditional
->outermost_loop();
932 /* Evaluate the scope that is shared by all: required first write scope,
933 * required first read before write scope, and last read scope.
935 const prog_scope
*enclosing_scope
= enclosing_scope_first_read
;
936 if (enclosing_scope_first_write
->contains_range_of(*enclosing_scope
))
937 enclosing_scope
= enclosing_scope_first_write
;
939 if (last_read_scope
->contains_range_of(*enclosing_scope
))
940 enclosing_scope
= last_read_scope
;
942 while (!enclosing_scope
->contains_range_of(*enclosing_scope_first_write
) ||
943 !enclosing_scope
->contains_range_of(*last_read_scope
)) {
944 enclosing_scope
= enclosing_scope
->parent();
945 assert(enclosing_scope
);
948 /* Propagate the last read scope to the target scope */
949 while (enclosing_scope
->nesting_depth() < last_read_scope
->nesting_depth()) {
950 /* If the read is in a loop and we have to move up the scope we need to
951 * extend the live range to the end of this current loop because at this
952 * point we don't know whether the component was written before
953 * un-conditionally in the same loop.
955 if (last_read_scope
->is_loop())
956 last_read
= last_read_scope
->end();
958 last_read_scope
= last_read_scope
->parent();
961 /* If the variable has to be kept for the whole loop, and we
962 * are currently in a loop, then propagate the live range.
964 if (keep_for_full_loop
&& first_write_scope
->is_loop())
965 propagate_live_range_to_dominant_write_scope();
967 /* Propagate the first_dominant_write scope to the target scope */
968 while (enclosing_scope
->nesting_depth() < first_write_scope
->nesting_depth()) {
969 /* Propagate live_range if there was a break in a loop and the write was
970 * after the break inside that loop. Note, that this is only needed if
971 * we move up in the scopes.
973 if (first_write_scope
->loop_break_line() < first_write
) {
974 keep_for_full_loop
= true;
975 propagate_live_range_to_dominant_write_scope();
978 first_write_scope
= first_write_scope
->parent();
980 /* Propagte live_range if we are now in a loop */
981 if (keep_for_full_loop
&& first_write_scope
->is_loop())
982 propagate_live_range_to_dominant_write_scope();
985 /* The last write past the last read is dead code, but we have to
986 * ensure that the component is not reused too early, hence extend the
987 * live_range past the last write.
989 if (last_write
>= last_read
)
990 last_read
= last_write
+ 1;
992 /* Here we are at the same scope, all is resolved */
993 return make_live_range(first_write
, last_read
);
996 /* Helper class for sorting and searching the registers based
998 class register_merge_record
{
1005 bool operator < (const register_merge_record
& rhs
) const {
1006 return begin
< rhs
.begin
;
1010 class access_recorder
{
1012 access_recorder(int _ntemps
, int _narrays
);
1015 void record_read(const st_src_reg
& src
, int line
, prog_scope
*scope
);
1016 void record_write(const st_dst_reg
& src
, int line
, prog_scope
*scope
,
1019 void get_required_live_ranges(register_live_range
*register_live_ranges
,
1020 array_live_range
*array_live_ranges
);
1025 temp_access
*temp_acc
;
1026 array_access
*array_acc
;
1029 access_recorder::access_recorder(int _ntemps
, int _narrays
):
1033 temp_acc
= new temp_access
[ntemps
];
1034 array_acc
= new array_access
[narrays
];
1037 access_recorder::~access_recorder()
1043 void access_recorder::record_read(const st_src_reg
& src
, int line
,
1047 for (int idx
= 0; idx
< 4; ++idx
) {
1048 int swz
= GET_SWZ(src
.swizzle
, idx
);
1049 readmask
|= (1 << swz
) & 0xF;
1052 if (src
.file
== PROGRAM_TEMPORARY
)
1053 temp_acc
[src
.index
].record_read(line
, scope
, readmask
);
1055 if (src
.file
== PROGRAM_ARRAY
) {
1056 assert(src
.array_id
<= narrays
);
1057 array_acc
[src
.array_id
- 1].record_access(line
, scope
, readmask
);
1061 record_read(*src
.reladdr
, line
, scope
);
1063 record_read(*src
.reladdr2
, line
, scope
);
1066 void access_recorder::record_write(const st_dst_reg
& dst
, int line
,
1067 prog_scope
*scope
, bool can_reswizzle
)
1069 if (dst
.file
== PROGRAM_TEMPORARY
)
1070 temp_acc
[dst
.index
].record_write(line
, scope
, dst
.writemask
);
1072 if (dst
.file
== PROGRAM_ARRAY
) {
1073 assert(dst
.array_id
<= narrays
);
1075 /* If the array is written as dst of a multi-dst operation, we must not
1076 * reswizzle the access, because we would have to reswizzle also the
1077 * other dst. For now just fill the mask to make interleaving impossible.
1079 array_acc
[dst
.array_id
- 1].record_access(line
, scope
,
1080 can_reswizzle
? dst
.writemask
: 0xF);
1084 record_read(*dst
.reladdr
, line
, scope
);
1086 record_read(*dst
.reladdr2
, line
, scope
);
1089 void access_recorder::get_required_live_ranges(struct register_live_range
*register_live_ranges
,
1090 class array_live_range
*array_live_ranges
)
1092 RENAME_DEBUG(debug_log
<< "== register live ranges ==========\n");
1093 for(int i
= 0; i
< ntemps
; ++i
) {
1094 RENAME_DEBUG(debug_log
<< setw(4) << i
);
1095 register_live_ranges
[i
] = temp_acc
[i
].get_required_live_range();
1096 RENAME_DEBUG(debug_log
<< ": [" << register_live_ranges
[i
].begin
<< ", "
1097 << register_live_ranges
[i
].end
<< "]\n");
1099 RENAME_DEBUG(debug_log
<< "==================================\n\n");
1101 RENAME_DEBUG(debug_log
<< "== array live ranges ==========\n");
1102 for(int i
= 0; i
< narrays
; ++i
) {
1103 RENAME_DEBUG(debug_log
<< setw(4) << i
);
1104 array_acc
[i
].get_required_live_range(array_live_ranges
[i
]);
1105 RENAME_DEBUG(debug_log
<< ": [" <<array_live_ranges
[i
].begin() << ", "
1106 << array_live_ranges
[i
].end() << "]\n");
1108 RENAME_DEBUG(debug_log
<< "==================================\n\n");
1114 /* Function used for debugging. */
1115 static void dump_instruction(ostream
& os
, int line
, prog_scope
*scope
,
1116 const glsl_to_tgsi_instruction
& inst
);
1119 /* Scan the program and estimate the required register live ranges.
1120 * The arraylive_ranges must be pre-allocated
1123 get_temp_registers_required_live_ranges(void *mem_ctx
, exec_list
*instructions
,
1124 int ntemps
, struct register_live_range
*register_live_ranges
,
1125 int narrays
, class array_live_range
*array_live_ranges
)
1131 bool is_at_end
= false;
1134 /* Count scopes to allocate the needed space without the need for
1137 foreach_in_list(glsl_to_tgsi_instruction
, inst
, instructions
) {
1138 if (inst
->op
== TGSI_OPCODE_BGNLOOP
||
1139 inst
->op
== TGSI_OPCODE_SWITCH
||
1140 inst
->op
== TGSI_OPCODE_CASE
||
1141 inst
->op
== TGSI_OPCODE_IF
||
1142 inst
->op
== TGSI_OPCODE_UIF
||
1143 inst
->op
== TGSI_OPCODE_ELSE
||
1144 inst
->op
== TGSI_OPCODE_DEFAULT
)
1148 prog_scope_storage
scopes(mem_ctx
, n_scopes
);
1150 access_recorder
access(ntemps
, narrays
);
1152 prog_scope
*cur_scope
= scopes
.create(nullptr, outer_scope
, 0, 0, line
);
1154 RENAME_DEBUG(debug_log
<< "========= Begin shader ============\n");
1156 foreach_in_list(glsl_to_tgsi_instruction
, inst
, instructions
) {
1158 assert(!"GLSL_TO_TGSI: shader has instructions past end marker");
1162 RENAME_DEBUG(dump_instruction(debug_log
, line
, cur_scope
, *inst
));
1165 case TGSI_OPCODE_BGNLOOP
: {
1166 cur_scope
= scopes
.create(cur_scope
, loop_body
, loop_id
++,
1167 cur_scope
->nesting_depth() + 1, line
);
1170 case TGSI_OPCODE_ENDLOOP
: {
1171 cur_scope
->set_end(line
);
1172 cur_scope
= cur_scope
->parent();
1176 case TGSI_OPCODE_IF
:
1177 case TGSI_OPCODE_UIF
: {
1178 assert(num_inst_src_regs(inst
) == 1);
1179 access
.record_read(inst
->src
[0], line
, cur_scope
);
1180 cur_scope
= scopes
.create(cur_scope
, if_branch
, if_id
++,
1181 cur_scope
->nesting_depth() + 1, line
+ 1);
1184 case TGSI_OPCODE_ELSE
: {
1185 assert(cur_scope
->type() == if_branch
);
1186 cur_scope
->set_end(line
- 1);
1187 cur_scope
= scopes
.create(cur_scope
->parent(), else_branch
,
1188 cur_scope
->id(), cur_scope
->nesting_depth(),
1192 case TGSI_OPCODE_END
: {
1193 cur_scope
->set_end(line
);
1197 case TGSI_OPCODE_ENDIF
: {
1198 cur_scope
->set_end(line
- 1);
1199 cur_scope
= cur_scope
->parent();
1203 case TGSI_OPCODE_SWITCH
: {
1204 assert(num_inst_src_regs(inst
) == 1);
1205 prog_scope
*scope
= scopes
.create(cur_scope
, switch_body
, switch_id
++,
1206 cur_scope
->nesting_depth() + 1, line
);
1207 /* We record the read only for the SWITCH statement itself, like it
1208 * is used by the only consumer of TGSI_OPCODE_SWITCH in tgsi_exec.c.
1210 access
.record_read(inst
->src
[0], line
, cur_scope
);
1214 case TGSI_OPCODE_ENDSWITCH
: {
1215 cur_scope
->set_end(line
- 1);
1216 /* Remove the case level, it might not have been
1217 * closed with a break.
1219 if (cur_scope
->type() != switch_body
)
1220 cur_scope
= cur_scope
->parent();
1222 cur_scope
= cur_scope
->parent();
1226 case TGSI_OPCODE_CASE
: {
1227 /* Take care of tracking the registers. */
1228 prog_scope
*switch_scope
= cur_scope
->type() == switch_body
?
1229 cur_scope
: cur_scope
->parent();
1231 assert(num_inst_src_regs(inst
) == 1);
1232 access
.record_read(inst
->src
[0], line
, switch_scope
);
1234 /* Fall through to allocate the scope. */
1236 case TGSI_OPCODE_DEFAULT
: {
1237 prog_scope_type t
= inst
->op
== TGSI_OPCODE_CASE
? switch_case_branch
1238 : switch_default_branch
;
1239 prog_scope
*switch_scope
= (cur_scope
->type() == switch_body
) ?
1240 cur_scope
: cur_scope
->parent();
1241 assert(switch_scope
->type() == switch_body
);
1242 prog_scope
*scope
= scopes
.create(switch_scope
, t
,
1244 switch_scope
->nesting_depth() + 1,
1246 /* Previous case falls through, so scope was not yet closed. */
1247 if ((cur_scope
!= switch_scope
) && (cur_scope
->end() == -1))
1248 cur_scope
->set_end(line
- 1);
1252 case TGSI_OPCODE_BRK
: {
1253 if (cur_scope
->break_is_for_switchcase()) {
1254 cur_scope
->set_end(line
- 1);
1256 cur_scope
->set_loop_break_line(line
);
1260 case TGSI_OPCODE_CAL
:
1261 case TGSI_OPCODE_RET
:
1262 /* These opcodes are not supported and if a subroutine would
1263 * be called in a shader, then the live_range tracking would have
1264 * to follow that call to see which registers are used there.
1265 * Since this is not done, we have to bail out here and signal
1266 * that no register merge will take place.
1270 for (unsigned j
= 0; j
< num_inst_src_regs(inst
); j
++) {
1271 access
.record_read(inst
->src
[j
], line
, cur_scope
);
1273 for (unsigned j
= 0; j
< inst
->tex_offset_num_offset
; j
++) {
1274 access
.record_read(inst
->tex_offsets
[j
], line
, cur_scope
);
1276 unsigned ndst
= num_inst_dst_regs(inst
);
1277 for (unsigned j
= 0; j
< ndst
; j
++) {
1278 access
.record_write(inst
->dst
[j
], line
, cur_scope
, ndst
== 1);
1280 access
.record_read(inst
->resource
, line
, cur_scope
);
1286 RENAME_DEBUG(debug_log
<< "==================================\n\n");
1288 /* Make sure last scope is closed, even though no
1289 * TGSI_OPCODE_END was given.
1291 if (cur_scope
->end() < 0)
1292 cur_scope
->set_end(line
- 1);
1294 access
.get_required_live_ranges(register_live_ranges
, array_live_ranges
);
1298 /* Find the next register between [start, end) that has a live range starting
1299 * at or after bound by using a binary search.
1300 * start points at the beginning of the search range,
1301 * end points at the element past the end of the search range, and
1302 * the array comprising [start, end) must be sorted in ascending order.
1304 static register_merge_record
*
1305 find_next_rename(register_merge_record
* start
, register_merge_record
* end
, int bound
)
1307 int delta
= (end
- start
);
1310 int half
= delta
>> 1;
1311 register_merge_record
* middle
= start
+ half
;
1313 if (bound
<= middle
->begin
) {
1325 #ifndef USE_STL_SORT
1326 static int register_merge_record_compare (const void *a
, const void *b
) {
1327 const register_merge_record
*aa
= static_cast<const register_merge_record
*>(a
);
1328 const register_merge_record
*bb
= static_cast<const register_merge_record
*>(b
);
1329 return aa
->begin
< bb
->begin
? -1 : (aa
->begin
> bb
->begin
? 1 : 0);
1333 /* This functions evaluates the register merges by using a binary
1334 * search to find suitable merge candidates. */
1335 void get_temp_registers_remapping(void *mem_ctx
, int ntemps
,
1336 const struct register_live_range
*live_ranges
,
1337 struct rename_reg_pair
*result
)
1339 register_merge_record
*reg_access
= ralloc_array(mem_ctx
, register_merge_record
, ntemps
);
1342 for (int i
= 0; i
< ntemps
; ++i
) {
1343 if (live_ranges
[i
].begin
>= 0) {
1344 reg_access
[used_temps
].begin
=live_ranges
[i
].begin
;
1345 reg_access
[used_temps
].end
=live_ranges
[i
].end
;
1346 reg_access
[used_temps
].reg
= i
;
1347 reg_access
[used_temps
].erase
= false;
1353 std::sort(reg_access
, reg_access
+ used_temps
);
1355 std::qsort(reg_access
, used_temps
, sizeof(register_merge_record
),
1356 register_merge_record_compare
);
1359 register_merge_record
*trgt
= reg_access
;
1360 register_merge_record
*reg_access_end
= reg_access
+ used_temps
;
1361 register_merge_record
*first_erase
= reg_access_end
;
1362 register_merge_record
*search_start
= trgt
+ 1;
1364 while (trgt
!= reg_access_end
) {
1365 register_merge_record
*src
= find_next_rename(search_start
, reg_access_end
,
1367 if (src
!= reg_access_end
) {
1368 result
[src
->reg
].new_reg
= trgt
->reg
;
1369 result
[src
->reg
].valid
= true;
1370 trgt
->end
= src
->end
;
1372 /* Since we only search forward, don't remove the renamed
1373 * register just now, only mark it. */
1376 if (first_erase
== reg_access_end
)
1379 search_start
= src
+ 1;
1381 /* Moving to the next target register it is time to remove
1382 * the already merged registers from the search range */
1383 if (first_erase
!= reg_access_end
) {
1384 register_merge_record
*outp
= first_erase
;
1385 register_merge_record
*inp
= first_erase
+ 1;
1387 while (inp
!= reg_access_end
) {
1393 reg_access_end
= outp
;
1394 first_erase
= reg_access_end
;
1397 search_start
= trgt
+ 1;
1400 ralloc_free(reg_access
);
1403 /* Code below used for debugging */
1406 void dump_instruction(ostream
& os
, int line
, prog_scope
*scope
,
1407 const glsl_to_tgsi_instruction
& inst
)
1409 const struct tgsi_opcode_info
*info
= inst
.info
;
1410 int indent
= scope
->nesting_depth();
1411 if ((scope
->type() == switch_case_branch
||
1412 scope
->type() == switch_default_branch
) &&
1413 (info
->opcode
== TGSI_OPCODE_CASE
||
1414 info
->opcode
== TGSI_OPCODE_DEFAULT
))
1417 if (info
->opcode
== TGSI_OPCODE_ENDIF
||
1418 info
->opcode
== TGSI_OPCODE_ELSE
||
1419 info
->opcode
== TGSI_OPCODE_ENDLOOP
||
1420 info
->opcode
== TGSI_OPCODE_ENDSWITCH
)
1423 os
<< setw(4) << line
<< ": ";
1424 os
<< setw(indent
* 4) << " ";