2 * Copyright (c) 2017-2019 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 "sfn_liverange.h"
25 #include "sfn_debug.h"
26 #include "sfn_value.h"
27 #include "sfn_value_gpr.h"
29 #include "program/prog_instruction.h"
30 #include "util/bitscan.h"
31 #include "util/u_math.h"
37 /* std::sort is significantly faster than qsort */
40 /* If <windows.h> is included this is defined and clashes with
41 * std::numeric_limits<>::max()
50 using std::numeric_limits
;
51 using std::unique_ptr
;
54 prog_scope_storage::prog_scope_storage(int n
):
60 prog_scope_storage::~prog_scope_storage()
65 prog_scope_storage::create(prog_scope
*p
, prog_scope_type type
, int id
,
68 storage
[current_slot
] = prog_scope(p
, type
, id
, lvl
, s_begin
);
69 return &storage
[current_slot
++];
72 prog_scope::prog_scope(prog_scope
*parent
, prog_scope_type type
, int id
,
73 int depth
, int scope_begin
):
76 scope_nesting_depth(depth
),
77 scope_begin(scope_begin
),
79 break_loop_line(numeric_limits
<int>::max()),
84 prog_scope::prog_scope():
85 prog_scope(nullptr, undefined_scope
, -1, -1, -1)
89 prog_scope_type
prog_scope::type() const
94 prog_scope
*prog_scope::parent() const
99 int prog_scope::nesting_depth() const
101 return scope_nesting_depth
;
104 bool prog_scope::is_loop() const
106 return (scope_type
== loop_body
);
109 bool prog_scope::is_in_loop() const
111 if (scope_type
== loop_body
)
115 return parent_scope
->is_in_loop();
120 const prog_scope
*prog_scope::innermost_loop() const
122 if (scope_type
== loop_body
)
126 return parent_scope
->innermost_loop();
131 const prog_scope
*prog_scope::outermost_loop() const
133 const prog_scope
*loop
= nullptr;
134 const prog_scope
*p
= this;
137 if (p
->type() == loop_body
)
145 bool prog_scope::is_child_of_ifelse_id_sibling(const prog_scope
*scope
) const
147 const prog_scope
*my_parent
= in_parent_ifelse_scope();
149 /* is a direct child? */
150 if (my_parent
== scope
)
152 /* is a child of the conditions sibling? */
153 if (my_parent
->id() == scope
->id())
155 my_parent
= my_parent
->in_parent_ifelse_scope();
160 bool prog_scope::is_child_of(const prog_scope
*scope
) const
162 const prog_scope
*my_parent
= parent();
164 if (my_parent
== scope
)
166 my_parent
= my_parent
->parent();
171 const prog_scope
*prog_scope::enclosing_conditional() const
173 if (is_conditional())
177 return parent_scope
->enclosing_conditional();
182 bool prog_scope::contains_range_of(const prog_scope
& other
) const
184 return (begin() <= other
.begin()) && (end() >= other
.end());
187 bool prog_scope::is_conditional() const
189 return scope_type
== if_branch
||
190 scope_type
== else_branch
||
191 scope_type
== switch_case_branch
||
192 scope_type
== switch_default_branch
;
195 const prog_scope
*prog_scope::in_else_scope() const
197 if (scope_type
== else_branch
)
201 return parent_scope
->in_else_scope();
206 const prog_scope
*prog_scope::in_parent_ifelse_scope() const
209 return parent_scope
->in_ifelse_scope();
214 const prog_scope
*prog_scope::in_ifelse_scope() const
216 if (scope_type
== if_branch
||
217 scope_type
== else_branch
)
221 return parent_scope
->in_ifelse_scope();
226 bool prog_scope::is_switchcase_scope_in_loop() const
228 return (scope_type
== switch_case_branch
||
229 scope_type
== switch_default_branch
) &&
233 bool prog_scope::break_is_for_switchcase() const
235 if (scope_type
== loop_body
)
238 if (scope_type
== switch_case_branch
||
239 scope_type
== switch_default_branch
||
240 scope_type
== switch_body
)
244 return parent_scope
->break_is_for_switchcase();
249 int prog_scope::id() const
254 int prog_scope::begin() const
259 int prog_scope::end() const
264 void prog_scope::set_end(int end
)
270 void prog_scope::set_loop_break_line(int line
)
272 if (scope_type
== loop_body
) {
273 break_loop_line
= MIN2(break_loop_line
, line
);
276 parent()->set_loop_break_line(line
);
280 int prog_scope::loop_break_line() const
282 return break_loop_line
;
285 temp_access::temp_access():
287 needs_component_tracking(false),
288 is_array_element(false)
292 void temp_access::update_access_mask(int mask
)
294 if (access_mask
&& access_mask
!= mask
)
295 needs_component_tracking
= true;
299 void temp_access::record_write(int line
, prog_scope
*scope
, int writemask
, bool is_array_elm
)
303 update_access_mask(writemask
);
304 is_array_element
|= is_array_elm
;
306 if (writemask
& WRITEMASK_X
)
307 comp
[0].record_write(line
, scope
);
308 if (writemask
& WRITEMASK_Y
)
309 comp
[1].record_write(line
, scope
);
310 if (writemask
& WRITEMASK_Z
)
311 comp
[2].record_write(line
, scope
);
312 if (writemask
& WRITEMASK_W
)
313 comp
[3].record_write(line
, scope
);
316 void temp_access::record_read(int line
, prog_scope
*scope
, int readmask
, bool is_array_elm
)
318 update_access_mask(readmask
);
319 is_array_element
|= is_array_elm
;
321 if (readmask
& WRITEMASK_X
)
322 comp
[0].record_read(line
, scope
);
323 if (readmask
& WRITEMASK_Y
)
324 comp
[1].record_read(line
, scope
);
325 if (readmask
& WRITEMASK_Z
)
326 comp
[2].record_read(line
, scope
);
327 if (readmask
& WRITEMASK_W
)
328 comp
[3].record_read(line
, scope
);
331 inline static register_live_range
make_live_range(int b
, int e
)
333 register_live_range lt
;
336 lt
.is_array_elm
= false;
340 register_live_range
temp_access::get_required_live_range()
342 register_live_range result
= make_live_range(-1, -1);
344 unsigned mask
= access_mask
;
346 unsigned chan
= u_bit_scan(&mask
);
347 register_live_range lt
= comp
[chan
].get_required_live_range();
350 if ((result
.begin
< 0) || (result
.begin
> lt
.begin
))
351 result
.begin
= lt
.begin
;
354 if (lt
.end
> result
.end
)
357 if (!needs_component_tracking
)
360 result
.is_array_elm
= is_array_element
;
365 temp_comp_access::conditionality_untouched
= std::numeric_limits
<int>::max();
368 temp_comp_access::write_is_unconditional
= std::numeric_limits
<int>::max() - 1;
371 temp_comp_access::temp_comp_access():
372 last_read_scope(nullptr),
373 first_read_scope(nullptr),
374 first_write_scope(nullptr),
378 first_read(numeric_limits
<int>::max()),
379 conditionality_in_loop_id(conditionality_untouched
),
380 if_scope_write_flags(0),
381 next_ifelse_nesting_depth(0),
382 current_unpaired_if_write_scope(nullptr),
383 was_written_in_current_else_scope(false)
387 void temp_comp_access::record_read(int line
, prog_scope
*scope
)
389 last_read_scope
= scope
;
392 if (first_read
> line
) {
394 first_read_scope
= scope
;
397 /* If the conditionality of the first write is already resolved then
398 * no further checks are required.
400 if (conditionality_in_loop_id
== write_is_unconditional
||
401 conditionality_in_loop_id
== write_is_conditional
)
404 /* Check whether we are in a condition within a loop */
405 const prog_scope
*ifelse_scope
= scope
->in_ifelse_scope();
406 const prog_scope
*enclosing_loop
;
407 if (ifelse_scope
&& (enclosing_loop
= ifelse_scope
->innermost_loop())) {
409 /* If we have either not yet written to this register nor writes are
410 * resolved as unconditional in the enclosing loop then check whether
411 * we read before write in an IF/ELSE branch.
413 if ((conditionality_in_loop_id
!= write_is_conditional
) &&
414 (conditionality_in_loop_id
!= enclosing_loop
->id())) {
416 if (current_unpaired_if_write_scope
) {
418 /* Has been written in this or a parent scope? - this makes the temporary
419 * unconditionally set at this point.
421 if (scope
->is_child_of(current_unpaired_if_write_scope
))
424 /* Has been written in the same scope before it was read? */
425 if (ifelse_scope
->type() == if_branch
) {
426 if (current_unpaired_if_write_scope
->id() == scope
->id())
429 if (was_written_in_current_else_scope
)
434 /* The temporary was read (conditionally) before it is written, hence
435 * it should survive a loop. This can be signaled like if it were
436 * conditionally written.
438 conditionality_in_loop_id
= write_is_conditional
;
443 void temp_comp_access::record_write(int line
, prog_scope
*scope
)
447 if (first_write
< 0) {
449 first_write_scope
= scope
;
451 /* If the first write we encounter is not in a conditional branch, or
452 * the conditional write is not within a loop, then this is to be
453 * considered an unconditional dominant write.
455 const prog_scope
*conditional
= scope
->enclosing_conditional();
456 if (!conditional
|| !conditional
->innermost_loop()) {
457 conditionality_in_loop_id
= write_is_unconditional
;
461 /* The conditionality of the first write is already resolved. */
462 if (conditionality_in_loop_id
== write_is_unconditional
||
463 conditionality_in_loop_id
== write_is_conditional
)
466 /* If the nesting depth is larger than the supported level,
467 * then we assume conditional writes.
469 if (next_ifelse_nesting_depth
>= supported_ifelse_nesting_depth
) {
470 conditionality_in_loop_id
= write_is_conditional
;
474 /* If we are in an IF/ELSE scope within a loop and the loop has not
475 * been resolved already, then record this write.
477 const prog_scope
*ifelse_scope
= scope
->in_ifelse_scope();
478 if (ifelse_scope
&& ifelse_scope
->innermost_loop() &&
479 ifelse_scope
->innermost_loop()->id() != conditionality_in_loop_id
)
480 record_ifelse_write(*ifelse_scope
);
483 void temp_comp_access::record_ifelse_write(const prog_scope
& scope
)
485 if (scope
.type() == if_branch
) {
486 /* The first write in an IF branch within a loop implies unresolved
487 * conditionality (if it was untouched or unconditional before).
489 conditionality_in_loop_id
= conditionality_unresolved
;
490 was_written_in_current_else_scope
= false;
491 record_if_write(scope
);
493 was_written_in_current_else_scope
= true;
494 record_else_write(scope
);
498 void temp_comp_access::record_if_write(const prog_scope
& scope
)
500 /* Don't record write if this IF scope if it ...
501 * - is not the first write in this IF scope,
502 * - has already been written in a parent IF scope.
503 * In both cases this write is a secondary write that doesn't contribute
504 * to resolve conditionality.
506 * Record the write if it
507 * - is the first one (obviously),
508 * - happens in an IF branch that is a child of the ELSE branch of the
509 * last active IF/ELSE pair. In this case recording this write is used to
510 * established whether the write is (un-)conditional in the scope enclosing
511 * this outer IF/ELSE pair.
513 if (!current_unpaired_if_write_scope
||
514 (current_unpaired_if_write_scope
->id() != scope
.id() &&
515 scope
.is_child_of_ifelse_id_sibling(current_unpaired_if_write_scope
))) {
516 if_scope_write_flags
|= 1 << next_ifelse_nesting_depth
;
517 current_unpaired_if_write_scope
= &scope
;
518 next_ifelse_nesting_depth
++;
522 void temp_comp_access::record_else_write(const prog_scope
& scope
)
524 int mask
= 1 << (next_ifelse_nesting_depth
- 1);
526 /* If the temporary was written in an IF branch on the same scope level
527 * and this branch is the sibling of this ELSE branch, then we have a
528 * pair of writes that makes write access to this temporary unconditional
529 * in the enclosing scope.
532 if ((if_scope_write_flags
& mask
) &&
533 (scope
.id() == current_unpaired_if_write_scope
->id())) {
534 --next_ifelse_nesting_depth
;
535 if_scope_write_flags
&= ~mask
;
537 /* The following code deals with propagating unconditionality from
538 * inner levels of nested IF/ELSE to the outer levels like in
541 * 2: if (a) { <- start scope A
546 * 7: } else { <- start scope B
549 * A: else <- start scope C
555 const prog_scope
*parent_ifelse
= scope
.parent()->in_ifelse_scope();
557 if (1 << (next_ifelse_nesting_depth
- 1) & if_scope_write_flags
) {
558 /* We are at the end of scope C and already recorded a write
559 * within an IF scope (A), the sibling of the parent ELSE scope B,
560 * and it is not yet resolved. Mark that as the last relevant
561 * IF scope. Below the write will be resolved for the A/B
564 current_unpaired_if_write_scope
= parent_ifelse
;
566 current_unpaired_if_write_scope
= nullptr;
568 /* Promote the first write scope to the enclosing scope because
569 * the current IF/ELSE pair is now irrelevant for the analysis.
570 * This is also required to evaluate the minimum life time for t in
581 first_write_scope
= scope
.parent();
583 /* If some parent is IF/ELSE and in a loop then propagate the
584 * write to that scope. Otherwise the write is unconditional
585 * because it happens in both corresponding IF/ELSE branches
586 * in this loop, and hence, record the loop id to signal the
589 if (parent_ifelse
&& parent_ifelse
->is_in_loop()) {
590 record_ifelse_write(*parent_ifelse
);
592 conditionality_in_loop_id
= scope
.innermost_loop()->id();
595 /* The temporary was not written in the IF branch corresponding
596 * to this ELSE branch, hence the write is conditional.
598 conditionality_in_loop_id
= write_is_conditional
;
602 bool temp_comp_access::conditional_ifelse_write_in_loop() const
604 return conditionality_in_loop_id
<= conditionality_unresolved
;
607 void temp_comp_access::propagate_live_range_to_dominant_write_scope()
609 first_write
= first_write_scope
->begin();
610 int lr
= first_write_scope
->end();
616 register_live_range
temp_comp_access::get_required_live_range()
618 bool keep_for_full_loop
= false;
620 /* This register component is not used at all, or only read,
621 * mark it as unused and ignore it when renaming.
622 * glsl_to_tgsi_visitor::renumber_registers will take care of
623 * eliminating registers that are not written to.
626 return make_live_range(-1, -1);
628 assert(first_write_scope
);
630 /* Only written to, just make sure the register component is not
631 * reused in the range it is used to write to
633 if (!last_read_scope
)
634 return make_live_range(first_write
, last_write
+ 1);
636 const prog_scope
*enclosing_scope_first_read
= first_read_scope
;
637 const prog_scope
*enclosing_scope_first_write
= first_write_scope
;
639 /* We read before writing in a loop
640 * hence the value must survive the loops
642 if ((first_read
<= first_write
) &&
643 first_read_scope
->is_in_loop()) {
644 keep_for_full_loop
= true;
645 enclosing_scope_first_read
= first_read_scope
->outermost_loop();
648 /* A conditional write within a (nested) loop must survive the outermost
649 * loop if the last read was not within the same scope.
651 const prog_scope
*conditional
= enclosing_scope_first_write
->enclosing_conditional();
652 if (conditional
&& !conditional
->contains_range_of(*last_read_scope
) &&
653 (conditional
->is_switchcase_scope_in_loop() ||
654 conditional_ifelse_write_in_loop())) {
655 keep_for_full_loop
= true;
656 enclosing_scope_first_write
= conditional
->outermost_loop();
659 /* Evaluate the scope that is shared by all: required first write scope,
660 * required first read before write scope, and last read scope.
662 const prog_scope
*enclosing_scope
= enclosing_scope_first_read
;
663 if (enclosing_scope_first_write
->contains_range_of(*enclosing_scope
))
664 enclosing_scope
= enclosing_scope_first_write
;
666 if (last_read_scope
->contains_range_of(*enclosing_scope
))
667 enclosing_scope
= last_read_scope
;
669 while (!enclosing_scope
->contains_range_of(*enclosing_scope_first_write
) ||
670 !enclosing_scope
->contains_range_of(*last_read_scope
)) {
671 enclosing_scope
= enclosing_scope
->parent();
672 assert(enclosing_scope
);
675 /* Propagate the last read scope to the target scope */
676 while (enclosing_scope
->nesting_depth() < last_read_scope
->nesting_depth()) {
677 /* If the read is in a loop and we have to move up the scope we need to
678 * extend the live range to the end of this current loop because at this
679 * point we don't know whether the component was written before
680 * un-conditionally in the same loop.
682 if (last_read_scope
->is_loop())
683 last_read
= last_read_scope
->end();
685 last_read_scope
= last_read_scope
->parent();
688 /* If the variable has to be kept for the whole loop, and we
689 * are currently in a loop, then propagate the live range.
691 if (keep_for_full_loop
&& first_write_scope
->is_loop())
692 propagate_live_range_to_dominant_write_scope();
694 /* Propagate the first_dominant_write scope to the target scope */
695 while (enclosing_scope
->nesting_depth() < first_write_scope
->nesting_depth()) {
696 /* Propagate live_range if there was a break in a loop and the write was
697 * after the break inside that loop. Note, that this is only needed if
698 * we move up in the scopes.
700 if (first_write_scope
->loop_break_line() < first_write
) {
701 keep_for_full_loop
= true;
702 propagate_live_range_to_dominant_write_scope();
705 first_write_scope
= first_write_scope
->parent();
707 /* Propagte live_range if we are now in a loop */
708 if (keep_for_full_loop
&& first_write_scope
->is_loop())
709 propagate_live_range_to_dominant_write_scope();
712 /* The last write past the last read is dead code, but we have to
713 * ensure that the component is not reused too early, hence extend the
714 * live_range past the last write.
716 if (last_write
>= last_read
)
717 last_read
= last_write
+ 1;
719 /* Here we are at the same scope, all is resolved */
720 return make_live_range(first_write
, last_read
);
723 /* Helper class for sorting and searching the registers based
725 class register_merge_record
{
733 bool operator < (const register_merge_record
& rhs
) const {
734 return begin
< rhs
.begin
;
738 LiverangeEvaluator::LiverangeEvaluator():
749 void LiverangeEvaluator::run(const Shader
& shader
,
750 std::vector
<register_live_range
>& register_live_ranges
)
752 temp_acc
.resize(register_live_ranges
.size());
753 fill(temp_acc
.begin(), temp_acc
.end(), temp_access());
755 sfn_log
<< SfnLog::merge
<< "have " << temp_acc
.size() << " temps\n";
757 for (const auto& block
: shader
.m_ir
) {
758 for (const auto& ir
: block
) {
759 switch (ir
->type()) {
760 case Instruction::cond_if
:
761 case Instruction::cond_else
:
762 case Instruction::loop_begin
:
770 scopes
.reset(new prog_scope_storage(n_scopes
));
772 cur_scope
= scopes
->create(nullptr, outer_scope
, 0, 0, line
);
776 for (auto& v
: shader
.m_temp
) {
777 if (v
.second
->type() == Value::gpr
) {
778 const auto& g
= static_cast<const GPRValue
&>(*v
.second
);
780 sfn_log
<< SfnLog::merge
<< "Record INPUT write for "
781 << g
<< " in " << temp_acc
.size() << " temps\n";
782 temp_acc
[g
.sel()].record_write(line
, cur_scope
, 1 << g
.chan(), false);
783 temp_acc
[g
.sel()].record_read(line
, cur_scope
, 1 << g
.chan(), false);
788 for (const auto& block
: shader
.m_ir
)
789 for (const auto& ir
: block
) {
790 ir
->evalue_liveness(*this);
791 if (ir
->type() != Instruction::alu
||
792 static_cast<const AluInstruction
&>(*ir
).flag(alu_last_instr
))
796 assert(cur_scope
->type() == outer_scope
);
797 cur_scope
->set_end(line
);
800 get_required_live_ranges(register_live_ranges
);
804 void LiverangeEvaluator::record_read(const Value
& src
, bool is_array_elm
)
806 sfn_log
<< SfnLog::merge
<< "Record read l:" << line
<< " reg:" << src
<< "\n";
807 if (src
.type() == Value::gpr
) {
808 const GPRValue
& v
= static_cast<const GPRValue
&>(src
);
810 temp_acc
[v
.sel()].record_read(line
, cur_scope
, 1 << v
.chan(), is_array_elm
);
812 } else if (src
.type() == Value::gpr_array_value
) {
813 const GPRArrayValue
& v
= static_cast<const GPRArrayValue
&>(src
);
814 v
.record_read(*this);
818 void LiverangeEvaluator::record_write(const Value
& src
, bool is_array_elm
)
820 sfn_log
<< SfnLog::merge
<< "Record write for "
821 << src
<< " in " << temp_acc
.size() << " temps\n";
823 if (src
.type() == Value::gpr
) {
824 const GPRValue
& v
= static_cast<const GPRValue
&>(src
);
825 assert(v
.sel() < temp_acc
.size());
827 temp_acc
[v
.sel()].record_write(line
, cur_scope
, 1 << v
.chan(), is_array_elm
);
829 } else if (src
.type() == Value::gpr_array_value
) {
830 const GPRArrayValue
& v
= static_cast<const GPRArrayValue
&>(src
);
831 v
.record_write(*this);
835 void LiverangeEvaluator::record_read(const GPRVector
& src
)
837 for (int i
= 0; i
< 4; ++i
)
839 record_read(*src
.reg_i(i
));
842 void LiverangeEvaluator::record_write(const GPRVector
& dst
)
844 for (int i
= 0; i
< 4; ++i
)
846 record_write(*dst
.reg_i(i
));
849 void LiverangeEvaluator::get_required_live_ranges(std::vector
<register_live_range
>& register_live_ranges
)
851 sfn_log
<< SfnLog::merge
<< "== register live ranges ==========\n";
852 for(unsigned i
= 0; i
< register_live_ranges
.size(); ++i
) {
853 sfn_log
<< SfnLog::merge
<< setw(4) << i
;
854 register_live_ranges
[i
] = temp_acc
[i
].get_required_live_range();
855 sfn_log
<< SfnLog::merge
<< ": [" << register_live_ranges
[i
].begin
<< ", "
856 << register_live_ranges
[i
].end
<< "]\n";
858 sfn_log
<< SfnLog::merge
<< "==================================\n\n";
861 void LiverangeEvaluator::scope_if()
863 cur_scope
= scopes
->create(cur_scope
, if_branch
, if_id
++,
864 cur_scope
->nesting_depth() + 1, line
+ 1);
867 void LiverangeEvaluator::scope_else()
869 assert(cur_scope
->type() == if_branch
);
870 cur_scope
->set_end(line
- 1);
871 cur_scope
= scopes
->create(cur_scope
->parent(), else_branch
,
872 cur_scope
->id(), cur_scope
->nesting_depth(),
876 void LiverangeEvaluator::scope_endif()
878 cur_scope
->set_end(line
- 1);
879 cur_scope
= cur_scope
->parent();
883 void LiverangeEvaluator::scope_loop_begin()
885 cur_scope
= scopes
->create(cur_scope
, loop_body
, loop_id
++,
886 cur_scope
->nesting_depth() + 1, line
);
889 void LiverangeEvaluator::scope_loop_end()
891 assert(cur_scope
->type() == loop_body
);
892 cur_scope
->set_end(line
);
893 cur_scope
= cur_scope
->parent();
897 void LiverangeEvaluator::scope_loop_break()
899 cur_scope
->set_loop_break_line(line
);
902 /* This functions evaluates the register merges by using a binary
903 * search to find suitable merge candidates. */
905 std::vector
<rename_reg_pair
>
906 get_temp_registers_remapping(const std::vector
<register_live_range
>& live_ranges
)
909 std::vector
<rename_reg_pair
> result(live_ranges
.size(), rename_reg_pair
{false, false, 0});
910 std::vector
<register_merge_record
> reg_access
;
912 for (unsigned i
= 0; i
< live_ranges
.size(); ++i
) {
913 if (live_ranges
[i
].begin
>= 0) {
914 register_merge_record r
;
915 r
.begin
= live_ranges
[i
].begin
;
916 r
.end
= live_ranges
[i
].end
;
917 r
.is_array_elm
= live_ranges
[i
].is_array_elm
;
920 reg_access
.push_back(r
);
924 std::sort(reg_access
.begin(), reg_access
.end());
926 for (auto& r
: reg_access
)
927 sfn_log
<< SfnLog::merge
<< "Use Range " <<r
.reg
<< " ["
928 << r
.begin
<< ", " << r
.end
<< "]\n";
930 auto trgt
= reg_access
.begin();
931 auto reg_access_end
= reg_access
.end();
932 auto first_erase
= reg_access_end
;
933 auto search_start
= trgt
+ 1;
935 while (trgt
!= reg_access_end
) {
936 /* Find the next register that has a live-range starting past the
937 * search start and that is not an array element. Array elements can't
938 * be moved (Moving the whole array could be an option to be implemented later)*/
940 sfn_log
<< SfnLog::merge
<< "Next target is "
941 << trgt
->reg
<< "[" << trgt
->begin
<< ", " << trgt
->end
<< "]\n";
944 auto src
= upper_bound(search_start
, reg_access_end
, trgt
->end
,
945 [](int bound
, const register_merge_record
& m
){
946 return bound
< m
.begin
&& !m
.is_array_elm
;}
949 if (src
!= reg_access_end
) {
950 result
[src
->reg
].new_reg
= trgt
->reg
;
951 result
[src
->reg
].valid
= true;
953 sfn_log
<< SfnLog::merge
<< "Map "
954 << src
->reg
<< "[" << src
->begin
<< ", " << src
->end
<< "] to "
955 << trgt
->reg
<< "[" << trgt
->begin
<< ", " << trgt
->end
<< ":";
956 trgt
->end
= src
->end
;
957 sfn_log
<< SfnLog::merge
<< trgt
->end
<< "]\n";
959 /* Since we only search forward, don't remove the renamed
960 * register just now, only mark it. */
963 if (first_erase
== reg_access_end
)
966 search_start
= src
+ 1;
968 /* Moving to the next target register it is time to remove
969 * the already merged registers from the search range */
970 if (first_erase
!= reg_access_end
) {
971 auto outp
= first_erase
;
972 auto inp
= first_erase
+ 1;
974 while (inp
!= reg_access_end
) {
980 reg_access_end
= outp
;
981 first_erase
= reg_access_end
;
984 search_start
= trgt
+ 1;