1/* -*- mode: C; c-file-style: "k&r"; tab-width 4; indent-tabs-mode: t; -*- */
2
3/*
4 * Copyright (C) 2014 Rob Clark <robclark@freedesktop.org>
5 *
6 * Permission is hereby granted, free of charge, to any person obtaining a
7 * copy of this software and associated documentation files (the "Software"),
8 * to deal in the Software without restriction, including without limitation
9 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
10 * and/or sell copies of the Software, and to permit persons to whom the
11 * Software is furnished to do so, subject to the following conditions:
12 *
13 * The above copyright notice and this permission notice (including the next
14 * paragraph) shall be included in all copies or substantial portions of the
15 * Software.
16 *
17 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
18 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
19 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
20 * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
21 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
22 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
23 * SOFTWARE.
24 *
25 * Authors:
26 *    Rob Clark <robclark@freedesktop.org>
27 */
28
29#include "util/u_math.h"
30
31#include "freedreno_util.h"
32
33#include "ir3.h"
34
35/*
36 * Legalize:
37 *
38 * We currently require that scheduling ensures that we have enough nop's
39 * in all the right places.  The legalize step mostly handles fixing up
40 * instruction flags ((ss)/(sy)/(ei)), and collapses sequences of nop's
41 * into fewer nop's w/ rpt flag.
42 */
43
44struct ir3_legalize_ctx {
45	bool has_samp;
46	int max_bary;
47};
48
49/* We want to evaluate each block from the position of any other
50 * predecessor block, in order that the flags set are the union
51 * of all possible program paths.  For stopping condition, we
52 * want to stop when the pair of <pred-block, current-block> has
53 * been visited already.
54 *
55 * XXX is that completely true?  We could have different needs_xyz
56 * flags set depending on path leading to pred-block.. we could
57 * do *most* of this based on chasing src instructions ptrs (and
58 * following all phi srcs).. except the write-after-read hazzard.
59 *
60 * For now we just set ss/sy flag on first instruction on block,
61 * and handle everything within the block as before.
62 */
63
64static void
65legalize_block(struct ir3_legalize_ctx *ctx, struct ir3_block *block)
66{
67	struct ir3_instruction *last_input = NULL;
68	struct ir3_instruction *last_rel = NULL;
69	struct list_head instr_list;
70	regmask_t needs_ss_war;       /* write after read */
71	regmask_t needs_ss;
72	regmask_t needs_sy;
73
74	regmask_init(&needs_ss_war);
75	regmask_init(&needs_ss);
76	regmask_init(&needs_sy);
77
78	/* remove all the instructions from the list, we'll be adding
79	 * them back in as we go
80	 */
81	list_replace(&block->instr_list, &instr_list);
82	list_inithead(&block->instr_list);
83
84	list_for_each_entry_safe (struct ir3_instruction, n, &instr_list, node) {
85		struct ir3_register *reg;
86		unsigned i;
87
88		if (is_meta(n))
89			continue;
90
91		if (is_input(n)) {
92			struct ir3_register *inloc = n->regs[1];
93			assert(inloc->flags & IR3_REG_IMMED);
94			ctx->max_bary = MAX2(ctx->max_bary, inloc->iim_val);
95		}
96
97		/* NOTE: consider dst register too.. it could happen that
98		 * texture sample instruction (for example) writes some
99		 * components which are unused.  A subsequent instruction
100		 * that writes the same register can race w/ the sam instr
101		 * resulting in undefined results:
102		 */
103		for (i = 0; i < n->regs_count; i++) {
104			reg = n->regs[i];
105
106			if (reg_gpr(reg)) {
107
108				/* TODO: we probably only need (ss) for alu
109				 * instr consuming sfu result.. need to make
110				 * some tests for both this and (sy)..
111				 */
112				if (regmask_get(&needs_ss, reg)) {
113					n->flags |= IR3_INSTR_SS;
114					regmask_init(&needs_ss);
115				}
116
117				if (regmask_get(&needs_sy, reg)) {
118					n->flags |= IR3_INSTR_SY;
119					regmask_init(&needs_sy);
120				}
121			}
122
123			/* TODO: is it valid to have address reg loaded from a
124			 * relative src (ie. mova a0, c<a0.x+4>)?  If so, the
125			 * last_rel check below should be moved ahead of this:
126			 */
127			if (reg->flags & IR3_REG_RELATIV)
128				last_rel = n;
129		}
130
131		if (n->regs_count > 0) {
132			reg = n->regs[0];
133			if (regmask_get(&needs_ss_war, reg)) {
134				n->flags |= IR3_INSTR_SS;
135				regmask_init(&needs_ss_war); // ??? I assume?
136			}
137
138			if (last_rel && (reg->num == regid(REG_A0, 0))) {
139				last_rel->flags |= IR3_INSTR_UL;
140				last_rel = NULL;
141			}
142		}
143
144		/* cat5+ does not have an (ss) bit, if needed we need to
145		 * insert a nop to carry the sync flag.  Would be kinda
146		 * clever if we were aware of this during scheduling, but
147		 * this should be a pretty rare case:
148		 */
149		if ((n->flags & IR3_INSTR_SS) && (opc_cat(n->opc) >= 5)) {
150			struct ir3_instruction *nop;
151			nop = ir3_NOP(block);
152			nop->flags |= IR3_INSTR_SS;
153			n->flags &= ~IR3_INSTR_SS;
154		}
155
156		/* need to be able to set (ss) on first instruction: */
157		if (list_empty(&block->instr_list) && (opc_cat(n->opc) >= 5))
158			ir3_NOP(block);
159
160		if (is_nop(n) && !list_empty(&block->instr_list)) {
161			struct ir3_instruction *last = list_last_entry(&block->instr_list,
162					struct ir3_instruction, node);
163			if (is_nop(last) && (last->repeat < 5)) {
164				last->repeat++;
165				last->flags |= n->flags;
166				continue;
167			}
168		}
169
170		list_addtail(&n->node, &block->instr_list);
171
172		if (is_sfu(n))
173			regmask_set(&needs_ss, n->regs[0]);
174
175		if (is_tex(n)) {
176			/* this ends up being the # of samp instructions.. but that
177			 * is ok, everything else only cares whether it is zero or
178			 * not.  We do this here, rather than when we encounter a
179			 * SAMP decl, because (especially in binning pass shader)
180			 * the samp instruction(s) could get eliminated if the
181			 * result is not used.
182			 */
183			ctx->has_samp = true;
184			regmask_set(&needs_sy, n->regs[0]);
185		} else if (is_load(n)) {
186			/* seems like ldlv needs (ss) bit instead??  which is odd but
187			 * makes a bunch of flat-varying tests start working on a4xx.
188			 */
189			if (n->opc == OPC_LDLV)
190				regmask_set(&needs_ss, n->regs[0]);
191			else
192				regmask_set(&needs_sy, n->regs[0]);
193		}
194
195		/* both tex/sfu appear to not always immediately consume
196		 * their src register(s):
197		 */
198		if (is_tex(n) || is_sfu(n) || is_load(n)) {
199			foreach_src(reg, n) {
200				if (reg_gpr(reg))
201					regmask_set(&needs_ss_war, reg);
202			}
203		}
204
205		if (is_input(n))
206			last_input = n;
207	}
208
209	if (last_input) {
210		/* special hack.. if using ldlv to bypass interpolation,
211		 * we need to insert a dummy bary.f on which we can set
212		 * the (ei) flag:
213		 */
214		if (is_mem(last_input) && (last_input->opc == OPC_LDLV)) {
215			struct ir3_instruction *baryf;
216
217			/* (ss)bary.f (ei)r63.x, 0, r0.x */
218			baryf = ir3_instr_create(block, OPC_BARY_F);
219			baryf->flags |= IR3_INSTR_SS;
220			ir3_reg_create(baryf, regid(63, 0), 0);
221			ir3_reg_create(baryf, 0, IR3_REG_IMMED)->iim_val = 0;
222			ir3_reg_create(baryf, regid(0, 0), 0);
223
224			/* insert the dummy bary.f after last_input: */
225			list_delinit(&baryf->node);
226			list_add(&baryf->node, &last_input->node);
227
228			last_input = baryf;
229		}
230		last_input->regs[0]->flags |= IR3_REG_EI;
231	}
232
233	if (last_rel)
234		last_rel->flags |= IR3_INSTR_UL;
235
236	list_first_entry(&block->instr_list, struct ir3_instruction, node)
237		->flags |= IR3_INSTR_SS | IR3_INSTR_SY;
238}
239
240/* NOTE: branch instructions are always the last instruction(s)
241 * in the block.  We take advantage of this as we resolve the
242 * branches, since "if (foo) break;" constructs turn into
243 * something like:
244 *
245 *   block3 {
246 *   	...
247 *   	0029:021: mov.s32s32 r62.x, r1.y
248 *   	0082:022: br !p0.x, target=block5
249 *   	0083:023: br p0.x, target=block4
250 *   	// succs: if _[0029:021: mov.s32s32] block4; else block5;
251 *   }
252 *   block4 {
253 *   	0084:024: jump, target=block6
254 *   	// succs: block6;
255 *   }
256 *   block5 {
257 *   	0085:025: jump, target=block7
258 *   	// succs: block7;
259 *   }
260 *
261 * ie. only instruction in block4/block5 is a jump, so when
262 * resolving branches we can easily detect this by checking
263 * that the first instruction in the target block is itself
264 * a jump, and setup the br directly to the jump's target
265 * (and strip back out the now unreached jump)
266 *
267 * TODO sometimes we end up with things like:
268 *
269 *    br !p0.x, #2
270 *    br p0.x, #12
271 *    add.u r0.y, r0.y, 1
272 *
273 * If we swapped the order of the branches, we could drop one.
274 */
275static struct ir3_block *
276resolve_dest_block(struct ir3_block *block)
277{
278	/* special case for last block: */
279	if (!block->successors[0])
280		return block;
281
282	/* NOTE that we may or may not have inserted the jump
283	 * in the target block yet, so conditions to resolve
284	 * the dest to the dest block's successor are:
285	 *
286	 *   (1) successor[1] == NULL &&
287	 *   (2) (block-is-empty || only-instr-is-jump)
288	 */
289	if (block->successors[1] == NULL) {
290		if (list_empty(&block->instr_list)) {
291			return block->successors[0];
292		} else if (list_length(&block->instr_list) == 1) {
293			struct ir3_instruction *instr = list_first_entry(
294					&block->instr_list, struct ir3_instruction, node);
295			if (instr->opc == OPC_JUMP)
296				return block->successors[0];
297		}
298	}
299	return block;
300}
301
302static bool
303resolve_jump(struct ir3_instruction *instr)
304{
305	struct ir3_block *tblock =
306		resolve_dest_block(instr->cat0.target);
307	struct ir3_instruction *target;
308
309	if (tblock != instr->cat0.target) {
310		list_delinit(&instr->cat0.target->node);
311		instr->cat0.target = tblock;
312		return true;
313	}
314
315	target = list_first_entry(&tblock->instr_list,
316				struct ir3_instruction, node);
317
318	if ((!target) || (target->ip == (instr->ip + 1))) {
319		list_delinit(&instr->node);
320		return true;
321	} else {
322		instr->cat0.immed =
323			(int)target->ip - (int)instr->ip;
324	}
325	return false;
326}
327
328/* resolve jumps, removing jumps/branches to immediately following
329 * instruction which we end up with from earlier stages.  Since
330 * removing an instruction can invalidate earlier instruction's
331 * branch offsets, we need to do this iteratively until no more
332 * branches are removed.
333 */
334static bool
335resolve_jumps(struct ir3 *ir)
336{
337	list_for_each_entry (struct ir3_block, block, &ir->block_list, node)
338		list_for_each_entry (struct ir3_instruction, instr, &block->instr_list, node)
339			if (is_flow(instr) && instr->cat0.target)
340				if (resolve_jump(instr))
341					return true;
342
343	return false;
344}
345
346/* we want to mark points where divergent flow control re-converges
347 * with (jp) flags.  For now, since we don't do any optimization for
348 * things that start out as a 'do {} while()', re-convergence points
349 * will always be a branch or jump target.  Note that this is overly
350 * conservative, since unconditional jump targets are not convergence
351 * points, we are just assuming that the other path to reach the jump
352 * target was divergent.  If we were clever enough to optimize the
353 * jump at end of a loop back to a conditional branch into a single
354 * conditional branch, ie. like:
355 *
356 *    add.f r1.w, r0.x, (neg)(r)c2.x   <= loop start
357 *    mul.f r1.z, r1.z, r0.x
358 *    mul.f r1.y, r1.y, r0.x
359 *    mul.f r0.z, r1.x, r0.x
360 *    mul.f r0.w, r0.y, r0.x
361 *    cmps.f.ge r0.x, (r)c2.y, (r)r1.w
362 *    add.s r0.x, (r)r0.x, (r)-1
363 *    sel.f32 r0.x, (r)c3.y, (r)r0.x, c3.x
364 *    cmps.f.eq p0.x, r0.x, c3.y
365 *    mov.f32f32 r0.x, r1.w
366 *    mov.f32f32 r0.y, r0.w
367 *    mov.f32f32 r1.x, r0.z
368 *    (rpt2)nop
369 *    br !p0.x, #-13
370 *    (jp)mul.f r0.x, c263.y, r1.y
371 *
372 * Then we'd have to be more clever, as the convergence point is no
373 * longer a branch or jump target.
374 */
375static void
376mark_convergence_points(struct ir3 *ir)
377{
378	list_for_each_entry (struct ir3_block, block, &ir->block_list, node) {
379		list_for_each_entry (struct ir3_instruction, instr, &block->instr_list, node) {
380			if (is_flow(instr) && instr->cat0.target) {
381				struct ir3_instruction *target =
382					list_first_entry(&instr->cat0.target->instr_list,
383							struct ir3_instruction, node);
384				target->flags |= IR3_INSTR_JP;
385			}
386		}
387	}
388}
389
390void
391ir3_legalize(struct ir3 *ir, bool *has_samp, int *max_bary)
392{
393	struct ir3_legalize_ctx ctx = {
394			.max_bary = -1,
395	};
396
397	list_for_each_entry (struct ir3_block, block, &ir->block_list, node) {
398		legalize_block(&ctx, block);
399	}
400
401	*has_samp = ctx.has_samp;
402	*max_bary = ctx.max_bary;
403
404	do {
405		ir3_count_instructions(ir);
406	} while(resolve_jumps(ir));
407
408	mark_convergence_points(ir);
409}
410