OSDN Git Service

Merge branch 'wip/nir-vtn' into vulkan
[android-x86/external-mesa.git] / src / mesa / drivers / dri / i965 / brw_vec4_cse.cpp
1 /*
2  * Copyright © 2012, 2013, 2014 Intel Corporation
3  *
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:
10  *
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
13  * Software.
14  *
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
21  * IN THE SOFTWARE.
22  */
23
24 #include "brw_vec4.h"
25 #include "brw_vec4_live_variables.h"
26 #include "brw_cfg.h"
27
28 using namespace brw;
29
30 /** @file brw_vec4_cse.cpp
31  *
32  * Support for local common subexpression elimination.
33  *
34  * See Muchnick's Advanced Compiler Design and Implementation, section
35  * 13.1 (p378).
36  */
37
38 namespace {
39 struct aeb_entry : public exec_node {
40    /** The instruction that generates the expression value. */
41    vec4_instruction *generator;
42
43    /** The temporary where the value is stored. */
44    src_reg tmp;
45 };
46 }
47
48 static bool
49 is_expression(const vec4_instruction *const inst)
50 {
51    switch (inst->opcode) {
52    case BRW_OPCODE_MOV:
53    case BRW_OPCODE_SEL:
54    case BRW_OPCODE_NOT:
55    case BRW_OPCODE_AND:
56    case BRW_OPCODE_OR:
57    case BRW_OPCODE_XOR:
58    case BRW_OPCODE_SHR:
59    case BRW_OPCODE_SHL:
60    case BRW_OPCODE_ASR:
61    case BRW_OPCODE_CMP:
62    case BRW_OPCODE_CMPN:
63    case BRW_OPCODE_ADD:
64    case BRW_OPCODE_MUL:
65    case BRW_OPCODE_FRC:
66    case BRW_OPCODE_RNDU:
67    case BRW_OPCODE_RNDD:
68    case BRW_OPCODE_RNDE:
69    case BRW_OPCODE_RNDZ:
70    case BRW_OPCODE_LINE:
71    case BRW_OPCODE_PLN:
72    case BRW_OPCODE_MAD:
73    case BRW_OPCODE_LRP:
74    case VEC4_OPCODE_UNPACK_UNIFORM:
75    case SHADER_OPCODE_FIND_LIVE_CHANNEL:
76    case SHADER_OPCODE_BROADCAST:
77       return true;
78    case SHADER_OPCODE_RCP:
79    case SHADER_OPCODE_RSQ:
80    case SHADER_OPCODE_SQRT:
81    case SHADER_OPCODE_EXP2:
82    case SHADER_OPCODE_LOG2:
83    case SHADER_OPCODE_POW:
84    case SHADER_OPCODE_INT_QUOTIENT:
85    case SHADER_OPCODE_INT_REMAINDER:
86    case SHADER_OPCODE_SIN:
87    case SHADER_OPCODE_COS:
88       return inst->mlen == 0;
89    default:
90       return false;
91    }
92 }
93
94 static bool
95 operands_match(const vec4_instruction *a, const vec4_instruction *b)
96 {
97    const src_reg *xs = a->src;
98    const src_reg *ys = b->src;
99
100    if (a->opcode == BRW_OPCODE_MAD) {
101       return xs[0].equals(ys[0]) &&
102              ((xs[1].equals(ys[1]) && xs[2].equals(ys[2])) ||
103               (xs[2].equals(ys[1]) && xs[1].equals(ys[2])));
104    } else if (!a->is_commutative()) {
105       return xs[0].equals(ys[0]) && xs[1].equals(ys[1]) && xs[2].equals(ys[2]);
106    } else {
107       return (xs[0].equals(ys[0]) && xs[1].equals(ys[1])) ||
108              (xs[1].equals(ys[0]) && xs[0].equals(ys[1]));
109    }
110 }
111
112 static bool
113 instructions_match(vec4_instruction *a, vec4_instruction *b)
114 {
115    return a->opcode == b->opcode &&
116           a->saturate == b->saturate &&
117           a->predicate == b->predicate &&
118           a->predicate_inverse == b->predicate_inverse &&
119           a->conditional_mod == b->conditional_mod &&
120           a->flag_subreg == b->flag_subreg &&
121           a->dst.type == b->dst.type &&
122           a->offset == b->offset &&
123           a->mlen == b->mlen &&
124           a->base_mrf == b->base_mrf &&
125           a->header_size == b->header_size &&
126           a->shadow_compare == b->shadow_compare &&
127           a->dst.writemask == b->dst.writemask &&
128           a->force_writemask_all == b->force_writemask_all &&
129           a->regs_written == b->regs_written &&
130           operands_match(a, b);
131 }
132
133 bool
134 vec4_visitor::opt_cse_local(bblock_t *block)
135 {
136    bool progress = false;
137    exec_list aeb;
138
139    void *cse_ctx = ralloc_context(NULL);
140
141    int ip = block->start_ip;
142    foreach_inst_in_block (vec4_instruction, inst, block) {
143       /* Skip some cases. */
144       if (is_expression(inst) && !inst->predicate && inst->mlen == 0 &&
145           (inst->dst.file != HW_REG || inst->dst.is_null()))
146       {
147          bool found = false;
148
149          foreach_in_list_use_after(aeb_entry, entry, &aeb) {
150             /* Match current instruction's expression against those in AEB. */
151             if (!(entry->generator->dst.is_null() && !inst->dst.is_null()) &&
152                 instructions_match(inst, entry->generator)) {
153                found = true;
154                progress = true;
155                break;
156             }
157          }
158
159          if (!found) {
160             if (inst->opcode != BRW_OPCODE_MOV ||
161                 (inst->opcode == BRW_OPCODE_MOV &&
162                  inst->src[0].file == IMM &&
163                  inst->src[0].type == BRW_REGISTER_TYPE_VF)) {
164                /* Our first sighting of this expression.  Create an entry. */
165                aeb_entry *entry = ralloc(cse_ctx, aeb_entry);
166                entry->tmp = src_reg(); /* file will be BAD_FILE */
167                entry->generator = inst;
168                aeb.push_tail(entry);
169             }
170          } else {
171             /* This is at least our second sighting of this expression.
172              * If we don't have a temporary already, make one.
173              */
174             bool no_existing_temp = entry->tmp.file == BAD_FILE;
175             if (no_existing_temp && !entry->generator->dst.is_null()) {
176                entry->tmp = retype(src_reg(GRF, alloc.allocate(
177                                               entry->generator->regs_written),
178                                            NULL), inst->dst.type);
179
180                for (unsigned i = 0; i < entry->generator->regs_written; ++i) {
181                   vec4_instruction *copy = MOV(offset(entry->generator->dst, i),
182                                                offset(entry->tmp, i));
183                   copy->force_writemask_all =
184                      entry->generator->force_writemask_all;
185                   entry->generator->insert_after(block, copy);
186                }
187
188                entry->generator->dst = dst_reg(entry->tmp);
189             }
190
191             /* dest <- temp */
192             if (!inst->dst.is_null()) {
193                assert(inst->dst.type == entry->tmp.type);
194
195                for (unsigned i = 0; i < inst->regs_written; ++i) {
196                   vec4_instruction *copy = MOV(offset(inst->dst, i),
197                                                offset(entry->tmp, i));
198                   copy->force_writemask_all = inst->force_writemask_all;
199                   inst->insert_before(block, copy);
200                }
201             }
202
203             /* Set our iterator so that next time through the loop inst->next
204              * will get the instruction in the basic block after the one we've
205              * removed.
206              */
207             vec4_instruction *prev = (vec4_instruction *)inst->prev;
208
209             inst->remove(block);
210             inst = prev;
211          }
212       }
213
214       foreach_in_list_safe(aeb_entry, entry, &aeb) {
215          /* Kill all AEB entries that write a different value to or read from
216           * the flag register if we just wrote it.
217           */
218          if (inst->writes_flag()) {
219             if (entry->generator->reads_flag() ||
220                 (entry->generator->writes_flag() &&
221                  !instructions_match(inst, entry->generator))) {
222                entry->remove();
223                ralloc_free(entry);
224                continue;
225             }
226          }
227
228          for (int i = 0; i < 3; i++) {
229             src_reg *src = &entry->generator->src[i];
230
231             /* Kill all AEB entries that use the destination we just
232              * overwrote.
233              */
234             if (inst->dst.file == entry->generator->src[i].file &&
235                 inst->dst.reg == entry->generator->src[i].reg) {
236                entry->remove();
237                ralloc_free(entry);
238                break;
239             }
240
241             /* Kill any AEB entries using registers that don't get reused any
242              * more -- a sure sign they'll fail operands_match().
243              */
244             if (src->file == GRF) {
245                if (var_range_end(var_from_reg(alloc, *src), 4) < ip) {
246                   entry->remove();
247                   ralloc_free(entry);
248                   break;
249                }
250             }
251          }
252       }
253
254       ip++;
255    }
256
257    ralloc_free(cse_ctx);
258
259    return progress;
260 }
261
262 bool
263 vec4_visitor::opt_cse()
264 {
265    bool progress = false;
266
267    calculate_live_intervals();
268
269    foreach_block (block, cfg) {
270       progress = opt_cse_local(block) || progress;
271    }
272
273    if (progress)
274       invalidate_live_intervals();
275
276    return progress;
277 }