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;
366
temp_comp_access::conditionality_untouched = std::numeric_limits<int>::max();
369
temp_comp_access::write_is_unconditional = std::numeric_limits<int>::max() - 1;
372
temp_comp_access::temp_comp_access():
373
last_read_scope(nullptr),
374
first_read_scope(nullptr),
375
first_write_scope(nullptr),
379
first_read(numeric_limits<int>::max()),
380
conditionality_in_loop_id(conditionality_untouched),
381
if_scope_write_flags(0),
382
next_ifelse_nesting_depth(0),
383
current_unpaired_if_write_scope(nullptr),
384
was_written_in_current_else_scope(false)
388
void temp_comp_access::record_read(int line, prog_scope *scope)
390
last_read_scope = scope;
391
if (last_read < line)
394
if (first_read > line) {
396
first_read_scope = scope;
399
/* If the conditionality of the first write is already resolved then
400
* no further checks are required.
402
if (conditionality_in_loop_id == write_is_unconditional ||
403
conditionality_in_loop_id == write_is_conditional)
406
/* Check whether we are in a condition within a loop */
407
const prog_scope *ifelse_scope = scope->in_ifelse_scope();
408
const prog_scope *enclosing_loop;
409
if (ifelse_scope && (enclosing_loop = ifelse_scope->innermost_loop())) {
411
/* If we have either not yet written to this register nor writes are
412
* resolved as unconditional in the enclosing loop then check whether
413
* we read before write in an IF/ELSE branch.
415
if ((conditionality_in_loop_id != write_is_conditional) &&
416
(conditionality_in_loop_id != enclosing_loop->id())) {
418
if (current_unpaired_if_write_scope) {
420
/* Has been written in this or a parent scope? - this makes the temporary
421
* unconditionally set at this point.
423
if (scope->is_child_of(current_unpaired_if_write_scope))
426
/* Has been written in the same scope before it was read? */
427
if (ifelse_scope->type() == if_branch) {
428
if (current_unpaired_if_write_scope->id() == scope->id())
431
if (was_written_in_current_else_scope)
436
/* The temporary was read (conditionally) before it is written, hence
437
* it should survive a loop. This can be signaled like if it were
438
* conditionally written.
440
conditionality_in_loop_id = write_is_conditional;
445
void temp_comp_access::record_write(int line, prog_scope *scope)
449
if (first_write < 0) {
451
first_write_scope = scope;
453
/* If the first write we encounter is not in a conditional branch, or
454
* the conditional write is not within a loop, then this is to be
455
* considered an unconditional dominant write.
457
const prog_scope *conditional = scope->enclosing_conditional();
458
if (!conditional || !conditional->innermost_loop()) {
459
conditionality_in_loop_id = write_is_unconditional;
463
/* The conditionality of the first write is already resolved. */
464
if (conditionality_in_loop_id == write_is_unconditional ||
465
conditionality_in_loop_id == write_is_conditional)
468
/* If the nesting depth is larger than the supported level,
469
* then we assume conditional writes.
471
if (next_ifelse_nesting_depth >= supported_ifelse_nesting_depth) {
472
conditionality_in_loop_id = write_is_conditional;
476
/* If we are in an IF/ELSE scope within a loop and the loop has not
477
* been resolved already, then record this write.
479
const prog_scope *ifelse_scope = scope->in_ifelse_scope();
480
if (ifelse_scope && ifelse_scope->innermost_loop() &&
481
ifelse_scope->innermost_loop()->id() != conditionality_in_loop_id)
482
record_ifelse_write(*ifelse_scope);
485
void temp_comp_access::record_ifelse_write(const prog_scope& scope)
487
if (scope.type() == if_branch) {
488
/* The first write in an IF branch within a loop implies unresolved
489
* conditionality (if it was untouched or unconditional before).
491
conditionality_in_loop_id = conditionality_unresolved;
492
was_written_in_current_else_scope = false;
493
record_if_write(scope);
495
was_written_in_current_else_scope = true;
496
record_else_write(scope);
500
void temp_comp_access::record_if_write(const prog_scope& scope)
502
/* Don't record write if this IF scope if it ...
503
* - is not the first write in this IF scope,
504
* - has already been written in a parent IF scope.
505
* In both cases this write is a secondary write that doesn't contribute
506
* to resolve conditionality.
508
* Record the write if it
509
* - is the first one (obviously),
510
* - happens in an IF branch that is a child of the ELSE branch of the
511
* last active IF/ELSE pair. In this case recording this write is used to
512
* established whether the write is (un-)conditional in the scope enclosing
513
* this outer IF/ELSE pair.
515
if (!current_unpaired_if_write_scope ||
516
(current_unpaired_if_write_scope->id() != scope.id() &&
517
scope.is_child_of_ifelse_id_sibling(current_unpaired_if_write_scope))) {
518
if_scope_write_flags |= 1 << next_ifelse_nesting_depth;
519
current_unpaired_if_write_scope = &scope;
520
next_ifelse_nesting_depth++;
524
void temp_comp_access::record_else_write(const prog_scope& scope)
526
int mask = 1 << (next_ifelse_nesting_depth - 1);
528
/* If the temporary was written in an IF branch on the same scope level
529
* and this branch is the sibling of this ELSE branch, then we have a
530
* pair of writes that makes write access to this temporary unconditional
531
* in the enclosing scope.
534
if ((if_scope_write_flags & mask) &&
535
(scope.id() == current_unpaired_if_write_scope->id())) {
536
--next_ifelse_nesting_depth;
537
if_scope_write_flags &= ~mask;
539
/* The following code deals with propagating unconditionality from
540
* inner levels of nested IF/ELSE to the outer levels like in
543
* 2: if (a) { <- start scope A
548
* 7: } else { <- start scope B
551
* A: else <- start scope C
557
const prog_scope *parent_ifelse = scope.parent()->in_ifelse_scope();
559
if (1 << (next_ifelse_nesting_depth - 1) & if_scope_write_flags) {
560
/* We are at the end of scope C and already recorded a write
561
* within an IF scope (A), the sibling of the parent ELSE scope B,
562
* and it is not yet resolved. Mark that as the last relevant
563
* IF scope. Below the write will be resolved for the A/B
566
current_unpaired_if_write_scope = parent_ifelse;
568
current_unpaired_if_write_scope = nullptr;
570
/* Promote the first write scope to the enclosing scope because
571
* the current IF/ELSE pair is now irrelevant for the analysis.
572
* This is also required to evaluate the minimum life time for t in
583
first_write_scope = scope.parent();
585
/* If some parent is IF/ELSE and in a loop then propagate the
586
* write to that scope. Otherwise the write is unconditional
587
* because it happens in both corresponding IF/ELSE branches
588
* in this loop, and hence, record the loop id to signal the
591
if (parent_ifelse && parent_ifelse->is_in_loop()) {
592
record_ifelse_write(*parent_ifelse);
594
conditionality_in_loop_id = scope.innermost_loop()->id();
597
/* The temporary was not written in the IF branch corresponding
598
* to this ELSE branch, hence the write is conditional.
600
conditionality_in_loop_id = write_is_conditional;
604
bool temp_comp_access::conditional_ifelse_write_in_loop() const
606
return conditionality_in_loop_id <= conditionality_unresolved;
609
void temp_comp_access::propagate_live_range_to_dominant_write_scope()
611
first_write = first_write_scope->begin();
612
int lr = first_write_scope->end();
618
register_live_range temp_comp_access::get_required_live_range()
620
bool keep_for_full_loop = false;
622
/* This register component is not used at all, or only read,
623
* mark it as unused and ignore it when renaming.
624
* glsl_to_tgsi_visitor::renumber_registers will take care of
625
* eliminating registers that are not written to.
628
return make_live_range(-1, -1);
630
assert(first_write_scope);
632
/* Only written to, just make sure the register component is not
633
* reused in the range it is used to write to
635
if (!last_read_scope)
636
return make_live_range(first_write, last_write + 1);
638
const prog_scope *enclosing_scope_first_read = first_read_scope;
639
const prog_scope *enclosing_scope_first_write = first_write_scope;
641
/* We read before writing in a loop
642
* hence the value must survive the loops
644
if ((first_read <= first_write) &&
645
first_read_scope->is_in_loop()) {
646
keep_for_full_loop = true;
647
enclosing_scope_first_read = first_read_scope->outermost_loop();
650
/* A conditional write within a (nested) loop must survive the outermost
651
* loop if the last read was not within the same scope.
653
const prog_scope *conditional = enclosing_scope_first_write->enclosing_conditional();
654
if (conditional && !conditional->contains_range_of(*last_read_scope) &&
655
(conditional->is_switchcase_scope_in_loop() ||
656
conditional_ifelse_write_in_loop())) {
657
keep_for_full_loop = true;
658
enclosing_scope_first_write = conditional->outermost_loop();
661
/* Evaluate the scope that is shared by all: required first write scope,
662
* required first read before write scope, and last read scope.
664
const prog_scope *enclosing_scope = enclosing_scope_first_read;
665
if (enclosing_scope_first_write->contains_range_of(*enclosing_scope))
666
enclosing_scope = enclosing_scope_first_write;
668
if (last_read_scope->contains_range_of(*enclosing_scope))
669
enclosing_scope = last_read_scope;
671
while (!enclosing_scope->contains_range_of(*enclosing_scope_first_write) ||
672
!enclosing_scope->contains_range_of(*last_read_scope)) {
673
enclosing_scope = enclosing_scope->parent();
674
assert(enclosing_scope);
677
/* Propagate the last read scope to the target scope */
678
while (enclosing_scope->nesting_depth() < last_read_scope->nesting_depth()) {
679
/* If the read is in a loop and we have to move up the scope we need to
680
* extend the live range to the end of this current loop because at this
681
* point we don't know whether the component was written before
682
* un-conditionally in the same loop.
684
if (last_read_scope->is_loop())
685
last_read = last_read_scope->end();
687
last_read_scope = last_read_scope->parent();
690
/* If the variable has to be kept for the whole loop, and we
691
* are currently in a loop, then propagate the live range.
693
if (keep_for_full_loop && first_write_scope->is_loop())
694
propagate_live_range_to_dominant_write_scope();
696
/* Propagate the first_dominant_write scope to the target scope */
697
while (enclosing_scope->nesting_depth() < first_write_scope->nesting_depth()) {
698
/* Propagate live_range if there was a break in a loop and the write was
699
* after the break inside that loop. Note, that this is only needed if
700
* we move up in the scopes.
702
if (first_write_scope->loop_break_line() < first_write) {
703
keep_for_full_loop = true;
704
propagate_live_range_to_dominant_write_scope();
707
first_write_scope = first_write_scope->parent();
709
/* Propagate live_range if we are now in a loop */
710
if (keep_for_full_loop && first_write_scope->is_loop())
711
propagate_live_range_to_dominant_write_scope();
714
/* The last write past the last read is dead code, but we have to
715
* ensure that the component is not reused too early, hence extend the
716
* live_range past the last write.
718
if (last_write >= last_read)
719
last_read = last_write + 1;
721
/* Here we are at the same scope, all is resolved */
722
return make_live_range(first_write, last_read);
725
/* Helper class for sorting and searching the registers based
727
class register_merge_record {
735
bool operator < (const register_merge_record& rhs) const {
736
return begin < rhs.begin;
740
LiverangeEvaluator::LiverangeEvaluator():
751
void LiverangeEvaluator::run(const Shader& shader,
752
std::vector<register_live_range>& register_live_ranges)
754
temp_acc.resize(register_live_ranges.size());
755
fill(temp_acc.begin(), temp_acc.end(), temp_access());
757
sfn_log << SfnLog::merge << "have " << temp_acc.size() << " temps\n";
759
for (const auto& block: shader.m_ir) {
760
for (const auto& ir: block) {
761
switch (ir->type()) {
762
case Instruction::cond_if:
763
case Instruction::cond_else:
764
case Instruction::loop_begin:
772
scopes.reset(new prog_scope_storage(n_scopes));
774
cur_scope = scopes->create(nullptr, outer_scope, 0, 0, line);
778
for (auto& v: shader.m_temp) {
779
if (v.second->type() == Value::gpr) {
780
sfn_log << SfnLog::merge << "Record " << *v.second << "\n";
781
const auto& g = static_cast<const GPRValue&>(*v.second);
783
sfn_log << SfnLog::merge << "Record INPUT write for "
784
<< g << " in " << temp_acc.size() << " temps\n";
785
temp_acc[g.sel()].record_write(line, cur_scope, 1 << g.chan(), false);
786
temp_acc[g.sel()].record_read(line, cur_scope, 1 << g.chan(), false);
788
if (g.keep_alive()) {
789
sfn_log << SfnLog::merge << "Record KEEP ALIVE for "
790
<< g << " in " << temp_acc.size() << " temps\n";
791
temp_acc[g.sel()].record_read(0x7fffff, cur_scope, 1 << g.chan(), false);
796
for (const auto& block: shader.m_ir)
797
for (const auto& ir: block) {
798
ir->evalue_liveness(*this);
799
if (ir->type() != Instruction::alu ||
800
static_cast<const AluInstruction&>(*ir).flag(alu_last_instr))
804
assert(cur_scope->type() == outer_scope);
805
cur_scope->set_end(line);
808
get_required_live_ranges(register_live_ranges);
812
void LiverangeEvaluator::record_read(const Value& src, bool is_array_elm)
814
sfn_log << SfnLog::merge << "Record read l:" << line << " reg:" << src << "\n";
815
if (src.type() == Value::gpr) {
816
const GPRValue& v = static_cast<const GPRValue&>(src);
818
temp_acc[v.sel()].record_read(v.keep_alive() ? 0x7fffff: line, cur_scope, 1 << v.chan(), is_array_elm);
820
} else if (src.type() == Value::gpr_array_value) {
821
const GPRArrayValue& v = static_cast<const GPRArrayValue&>(src);
822
v.record_read(*this);
823
} else if (src.type() == Value::kconst) {
824
const UniformValue& v = static_cast<const UniformValue&>(src);
826
record_read(*v.addr(),is_array_elm);
830
void LiverangeEvaluator::record_write(const Value& src, bool is_array_elm)
832
sfn_log << SfnLog::merge << "Record write for "
833
<< src << " in " << temp_acc.size() << " temps\n";
835
if (src.type() == Value::gpr) {
836
const GPRValue& v = static_cast<const GPRValue&>(src);
837
assert(v.sel() < temp_acc.size());
839
temp_acc[v.sel()].record_write(line, cur_scope, 1 << v.chan(), is_array_elm);
841
} else if (src.type() == Value::gpr_array_value) {
842
const GPRArrayValue& v = static_cast<const GPRArrayValue&>(src);
843
v.record_write(*this);
844
} else if (src.type() == Value::kconst) {
845
const UniformValue& v = static_cast<const UniformValue&>(src);
847
record_write(*v.addr(),is_array_elm);
851
void LiverangeEvaluator::record_read(const GPRVector& src)
853
for (int i = 0; i < 4; ++i)
855
record_read(*src.reg_i(i));
858
void LiverangeEvaluator::record_write(const GPRVector& dst)
860
for (int i = 0; i < 4; ++i)
862
record_write(*dst.reg_i(i));
865
void LiverangeEvaluator::get_required_live_ranges(std::vector<register_live_range>& register_live_ranges)
867
sfn_log << SfnLog::merge << "== register live ranges ==========\n";
868
for(unsigned i = 0; i < register_live_ranges.size(); ++i) {
869
sfn_log << SfnLog::merge << setw(4) << i;
870
register_live_ranges[i] = temp_acc[i].get_required_live_range();
871
sfn_log << SfnLog::merge << ": [" << register_live_ranges[i].begin << ", "
872
<< register_live_ranges[i].end << "]\n";
874
sfn_log << SfnLog::merge << "==================================\n\n";
877
void LiverangeEvaluator::scope_if()
879
cur_scope = scopes->create(cur_scope, if_branch, if_id++,
880
cur_scope->nesting_depth() + 1, line + 1);
883
void LiverangeEvaluator::scope_else()
885
assert(cur_scope->type() == if_branch);
886
cur_scope->set_end(line - 1);
887
cur_scope = scopes->create(cur_scope->parent(), else_branch,
888
cur_scope->id(), cur_scope->nesting_depth(),
892
void LiverangeEvaluator::scope_endif()
894
cur_scope->set_end(line - 1);
895
cur_scope = cur_scope->parent();
899
void LiverangeEvaluator::scope_loop_begin()
901
cur_scope = scopes->create(cur_scope, loop_body, loop_id++,
902
cur_scope->nesting_depth() + 1, line);
905
void LiverangeEvaluator::scope_loop_end()
907
assert(cur_scope->type() == loop_body);
908
cur_scope->set_end(line);
909
cur_scope = cur_scope->parent();
913
void LiverangeEvaluator::scope_loop_break()
915
cur_scope->set_loop_break_line(line);
918
/* This functions evaluates the register merges by using a binary
919
* search to find suitable merge candidates. */
921
std::vector<rename_reg_pair>
922
get_temp_registers_remapping(const std::vector<register_live_range>& live_ranges)
925
std::vector<rename_reg_pair> result(live_ranges.size(), rename_reg_pair{false, false, 0});
926
std::vector<register_merge_record> reg_access;
928
for (unsigned i = 0; i < live_ranges.size(); ++i) {
929
if (live_ranges[i].begin >= 0) {
930
register_merge_record r;
931
r.begin = live_ranges[i].begin;
932
r.end = live_ranges[i].end;
933
r.is_array_elm = live_ranges[i].is_array_elm;
936
reg_access.push_back(r);
940
std::sort(reg_access.begin(), reg_access.end());
942
for (auto& r : reg_access)
943
sfn_log << SfnLog::merge << "Use Range " <<r.reg << " ["
944
<< r.begin << ", " << r.end << "]\n";
946
auto trgt = reg_access.begin();
947
auto reg_access_end = reg_access.end();
948
auto first_erase = reg_access_end;
949
auto search_start = trgt + 1;
951
while (trgt != reg_access_end) {
952
/* Find the next register that has a live-range starting past the
953
* search start and that is not an array element. Array elements can't
954
* be moved (Moving the whole array could be an option to be implemented later)*/
956
sfn_log << SfnLog::merge << "Next target is "
957
<< trgt->reg << "[" << trgt->begin << ", " << trgt->end << "]\n";
960
auto src = upper_bound(search_start, reg_access_end, trgt->end,
961
[](int bound, const register_merge_record& m){
962
return bound < m.begin && !m.is_array_elm;}
965
if (src != reg_access_end) {
966
result[src->reg].new_reg = trgt->reg;
967
result[src->reg].valid = true;
969
sfn_log << SfnLog::merge << "Map "
970
<< src->reg << "[" << src->begin << ", " << src->end << "] to "
971
<< trgt->reg << "[" << trgt->begin << ", " << trgt->end << ":";
972
trgt->end = src->end;
973
sfn_log << SfnLog::merge << trgt->end << "]\n";
975
/* Since we only search forward, don't remove the renamed
976
* register just now, only mark it. */
979
if (first_erase == reg_access_end)
982
search_start = src + 1;
984
/* Moving to the next target register it is time to remove
985
* the already merged registers from the search range */
986
if (first_erase != reg_access_end) {
987
auto outp = first_erase;
988
auto inp = first_erase + 1;
990
while (inp != reg_access_end) {
996
reg_access_end = outp;
997
first_erase = reg_access_end;
1000
search_start = trgt + 1;
added
removed
src/gallium/drivers/r600/sfn/sfn_liverange.cpp
