1/*
2 * Copyright © 2018 Red Hat
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 * Authors:
24 *    Rob Clark (robdclark@gmail.com>
25 *
26 */
27
28#include "nir.h"
29
30
31/*
32 * A simple pass that moves load_const's into consuming block if
33 * they are only consumed in a single block, to try to counter-
34 * act nir's tendency to move all load_const to the top of the
35 * first block.
36 */
37
38/* iterate a ssa def's use's and try to find a more optimal block to
39 * move it to, using the dominance tree.  In short, if all of the uses
40 * are contained in a single block, the load will be moved there,
41 * otherwise it will be move to the least common ancestor block of all
42 * the uses
43 */
44static nir_block *
45get_preferred_block(nir_ssa_def *def)
46{
47   nir_block *lca = NULL;
48
49   /* hmm, probably ignore if-uses: */
50   if (!list_empty(&def->if_uses))
51      return NULL;
52
53   nir_foreach_use(use, def) {
54      nir_instr *instr = use->parent_instr;
55      nir_block *use_block = instr->block;
56
57      /*
58       * Kind of an ugly special-case, but phi instructions
59       * need to appear first in the block, so by definition
60       * we can't move a load_immed into a block where it is
61       * consumed by a phi instruction.  We could conceivably
62       * move it into a dominator block.
63       */
64      if (instr->type == nir_instr_type_phi) {
65         nir_phi_instr *phi = nir_instr_as_phi(instr);
66         nir_block *phi_lca = NULL;
67         nir_foreach_phi_src(src, phi)
68            phi_lca = nir_dominance_lca(phi_lca, src->pred);
69         use_block = phi_lca;
70      }
71
72      lca = nir_dominance_lca(lca, use_block);
73   }
74
75   return lca;
76}
77
78/* insert before first non-phi instruction: */
79static void
80insert_after_phi(nir_instr *instr, nir_block *block)
81{
82   nir_foreach_instr(instr2, block) {
83      if (instr2->type == nir_instr_type_phi)
84         continue;
85
86      exec_node_insert_node_before(&instr2->node,
87                                   &instr->node);
88
89      return;
90   }
91
92   /* if haven't inserted it, push to tail (ie. empty block or possibly
93    * a block only containing phi's?)
94    */
95   exec_list_push_tail(&block->instr_list, &instr->node);
96}
97
98bool
99nir_move_load_const(nir_shader *shader)
100{
101   bool progress = false;
102
103   nir_foreach_function(function, shader) {
104      if (!function->impl)
105         continue;
106
107      nir_foreach_block(block, function->impl) {
108         nir_metadata_require(function->impl,
109                              nir_metadata_block_index | nir_metadata_dominance);
110
111         nir_foreach_instr_safe(instr, block) {
112            if (instr->type != nir_instr_type_load_const)
113               continue;
114
115            nir_load_const_instr *load =
116                  nir_instr_as_load_const(instr);
117            nir_block *use_block =
118                  get_preferred_block(&load->def);
119
120            if (!use_block)
121               continue;
122
123            if (use_block == load->instr.block)
124               continue;
125
126            exec_node_remove(&load->instr.node);
127
128            insert_after_phi(&load->instr, use_block);
129
130            load->instr.block = use_block;
131
132            progress = true;
133         }
134      }
135
136      nir_metadata_preserve(function->impl,
137                            nir_metadata_block_index | nir_metadata_dominance);
138   }
139
140   return progress;
141}
142