2 * Copyright © 2019 Valve Corporation
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 DEALINGS
24 * Rhys Perry (pendingchaos02@gmail.com)
31 #include "aco_builder.h"
41 bool operator<(const phi_use
& other
) const {
42 return std::make_tuple(block
, phi_def
) <
43 std::make_tuple(other
.block
, other
.phi_def
);
48 std::map
<unsigned, unsigned> latest
;
49 std::map
<unsigned, std::map
<phi_use
, uint64_t>> phis
;
52 Operand
get_ssa(Program
*program
, unsigned block_idx
, ssa_state
*state
)
55 auto pos
= state
->latest
.find(block_idx
);
56 if (pos
!= state
->latest
.end())
57 return Operand({pos
->second
, s2
});
59 Block
& block
= program
->blocks
[block_idx
];
60 size_t pred
= block
.linear_preds
.size();
63 } else if (pred
== 1) {
64 block_idx
= block
.linear_preds
[0];
67 unsigned res
= program
->allocateId();
68 state
->latest
[block_idx
] = res
;
70 aco_ptr
<Pseudo_instruction
> phi
{create_instruction
<Pseudo_instruction
>(aco_opcode::p_linear_phi
, Format::PSEUDO
, pred
, 1)};
71 for (unsigned i
= 0; i
< pred
; i
++) {
72 phi
->operands
[i
] = get_ssa(program
, block
.linear_preds
[i
], state
);
73 if (phi
->operands
[i
].isTemp()) {
75 state
->phis
[phi
->operands
[i
].tempId()][(phi_use
){&block
, res
}] |= (uint64_t)1 << i
;
78 phi
->definitions
[0] = Definition(Temp
{res
, s2
});
79 block
.instructions
.emplace(block
.instructions
.begin(), std::move(phi
));
81 return Operand({res
, s2
});
86 void update_phi(Program
*program
, ssa_state
*state
, Block
*block
, unsigned phi_def
, uint64_t operand_mask
) {
87 for (auto& phi
: block
->instructions
) {
88 if (phi
->opcode
!= aco_opcode::p_phi
&& phi
->opcode
!= aco_opcode::p_linear_phi
)
90 if (phi
->opcode
!= aco_opcode::p_linear_phi
)
92 if (phi
->definitions
[0].tempId() != phi_def
)
94 assert(ffsll(operand_mask
) <= phi
->operands
.size());
96 uint64_t operands
= operand_mask
;
98 unsigned operand
= u_bit_scan64(&operands
);
99 Operand new_operand
= get_ssa(program
, block
->linear_preds
[operand
], state
);
100 phi
->operands
[operand
] = new_operand
;
101 if (!new_operand
.isUndefined())
102 state
->phis
[new_operand
.tempId()][(phi_use
){block
, phi_def
}] |= (uint64_t)1 << operand
;
109 Temp
write_ssa(Program
*program
, Block
*block
, ssa_state
*state
, unsigned previous
) {
110 unsigned id
= program
->allocateId();
111 state
->latest
[block
->index
] = id
;
115 std::map
<phi_use
, uint64_t> phis
;
116 phis
.swap(state
->phis
[previous
]);
117 for (auto& phi
: phis
)
118 update_phi(program
, state
, phi
.first
.block
, phi
.first
.phi_def
, phi
.second
);
124 void insert_before_logical_end(Block
*block
, aco_ptr
<Instruction
> instr
)
126 auto IsLogicalEnd
= [] (const aco_ptr
<Instruction
>& instr
) -> bool {
127 return instr
->opcode
== aco_opcode::p_logical_end
;
129 auto it
= std::find_if(block
->instructions
.crbegin(), block
->instructions
.crend(), IsLogicalEnd
);
131 if (it
== block
->instructions
.crend()) {
132 assert(block
->instructions
.back()->format
== Format::PSEUDO_BRANCH
);
133 block
->instructions
.insert(std::prev(block
->instructions
.end()), std::move(instr
));
136 block
->instructions
.insert(std::prev(it
.base()), std::move(instr
));
139 void lower_divergent_bool_phi(Program
*program
, Block
*block
, aco_ptr
<Instruction
>& phi
)
141 Builder
bld(program
);
144 state
.latest
[block
->index
] = phi
->definitions
[0].tempId();
145 for (unsigned i
= 0; i
< phi
->operands
.size(); i
++) {
146 Block
*pred
= &program
->blocks
[block
->logical_preds
[i
]];
148 if (phi
->operands
[i
].isUndefined())
151 assert(phi
->operands
[i
].isTemp());
152 Temp phi_src
= phi
->operands
[i
].getTemp();
153 assert(phi_src
.regClass() == s2
);
155 Operand cur
= get_ssa(program
, pred
->index
, &state
);
156 Temp new_cur
= write_ssa(program
, pred
, &state
, cur
.isTemp() ? cur
.tempId() : 0);
158 if (cur
.isUndefined()) {
159 insert_before_logical_end(pred
, bld
.sop1(aco_opcode::s_mov_b64
, Definition(new_cur
), phi_src
).get_ptr());
161 Temp tmp1
= bld
.tmp(s2
), tmp2
= bld
.tmp(s2
);
162 insert_before_logical_end(pred
,
163 bld
.sop2(aco_opcode::s_andn2_b64
, Definition(tmp1
), bld
.def(s1
, scc
),
164 cur
, Operand(exec
, s2
)).get_ptr());
165 insert_before_logical_end(pred
,
166 bld
.sop2(aco_opcode::s_and_b64
, Definition(tmp2
), bld
.def(s1
, scc
),
167 phi_src
, Operand(exec
, s2
)).get_ptr());
168 insert_before_logical_end(pred
,
169 bld
.sop2(aco_opcode::s_or_b64
, Definition(new_cur
), bld
.def(s1
, scc
),
170 tmp1
, tmp2
).get_ptr());
174 unsigned num_preds
= block
->linear_preds
.size();
175 if (phi
->operands
.size() != num_preds
) {
176 Pseudo_instruction
* new_phi
{create_instruction
<Pseudo_instruction
>(aco_opcode::p_linear_phi
, Format::PSEUDO
, num_preds
, 1)};
177 new_phi
->definitions
[0] = phi
->definitions
[0];
180 phi
->opcode
= aco_opcode::p_linear_phi
;
182 assert(phi
->operands
.size() == num_preds
);
184 for (unsigned i
= 0; i
< num_preds
; i
++)
185 phi
->operands
[i
] = get_ssa(program
, block
->linear_preds
[i
], &state
);
190 void lower_linear_bool_phi(Program
*program
, Block
*block
, aco_ptr
<Instruction
>& phi
)
192 Builder
bld(program
);
194 for (unsigned i
= 0; i
< phi
->operands
.size(); i
++) {
195 if (!phi
->operands
[i
].isTemp())
198 Temp phi_src
= phi
->operands
[i
].getTemp();
199 if (phi_src
.regClass() == s2
) {
200 Temp new_phi_src
= bld
.tmp(s1
);
201 insert_before_logical_end(&program
->blocks
[block
->linear_preds
[i
]],
202 bld
.sopc(aco_opcode::s_cmp_lg_u64
, bld
.scc(Definition(new_phi_src
)),
203 Operand(0u), phi_src
).get_ptr());
204 phi
->operands
[i
].setTemp(new_phi_src
);
209 void lower_bool_phis(Program
* program
)
211 for (Block
& block
: program
->blocks
) {
212 for (aco_ptr
<Instruction
>& phi
: block
.instructions
) {
213 if (phi
->opcode
== aco_opcode::p_phi
) {
214 assert(phi
->definitions
[0].regClass() != s1
);
215 if (phi
->definitions
[0].regClass() == s2
)
216 lower_divergent_bool_phi(program
, &block
, phi
);
217 } else if (phi
->opcode
== aco_opcode::p_linear_phi
) {
218 /* if it's a valid non-boolean phi, this should be a no-op */
219 if (phi
->definitions
[0].regClass() == s1
)
220 lower_linear_bool_phi(program
, &block
, phi
);