src/compiler/nir/nir_algebraic.py

   1 #! /usr/bin/env python
   2 #
   3 # Copyright (C) 2014 Intel Corporation
   4 #
   5 # Permission is hereby granted, free of charge, to any person obtaining a
   6 # copy of this software and associated documentation files (the "Software"),
   7 # to deal in the Software without restriction, including without limitation
   8 # the rights to use, copy, modify, merge, publish, distribute, sublicense,
   9 # and/or sell copies of the Software, and to permit persons to whom the
  10 # Software is furnished to do so, subject to the following conditions:
  11 #
  12 # The above copyright notice and this permission notice (including the next
  13 # paragraph) shall be included in all copies or substantial portions of the
  14 # Software.
  15 #
  16 # THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  17 # IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  18 # FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
  19 # THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  20 # LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
  21 # FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
  22 # IN THE SOFTWARE.
  23 #
  24 # Authors:
  25 #    Jason Ekstrand (jason@jlekstrand.net)
  26
  27 import itertools
  28 import struct
  29 import sys
  30 import mako.template
  31 import re
  32
  33 # Represents a set of variables, each with a unique id
  34 class VarSet(object):
  35    def __init__(self):
  36       self.names = {}
  37       self.ids = itertools.count()
  38       self.immutable = False;
  39
  40    def __getitem__(self, name):
  41       if name not in self.names:
  42          assert not self.immutable, "Unknown replacement variable: " + name
  43          self.names[name] = self.ids.next()
  44
  45       return self.names[name]
  46
  47    def lock(self):
  48       self.immutable = True
  49
  50 class Value(object):
  51    @staticmethod
  52    def create(val, name_base, varset):
  53       if isinstance(val, tuple):
  54          return Expression(val, name_base, varset)
  55       elif isinstance(val, Expression):
  56          return val
  57       elif isinstance(val, (str, unicode)):
  58          return Variable(val, name_base, varset)
  59       elif isinstance(val, (bool, int, long, float)):
  60          return Constant(val, name_base)
  61
  62    __template = mako.template.Template("""
  63 static const ${val.c_type} ${val.name} = {
  64    { ${val.type_enum} },
  65 % if isinstance(val, Constant):
  66    { ${hex(val)} /* ${val.value} */ },
  67 % elif isinstance(val, Variable):
  68    ${val.index}, /* ${val.var_name} */
  69    ${'true' if val.is_constant else 'false'},
  70    nir_type_${ val.required_type or 'invalid' },
  71 % elif isinstance(val, Expression):
  72    nir_op_${val.opcode},
  73    { ${', '.join(src.c_ptr for src in val.sources)} },
  74 % endif
  75 };""")
  76
  77    def __init__(self, name, type_str):
  78       self.name = name
  79       self.type_str = type_str
  80
  81    @property
  82    def type_enum(self):
  83       return "nir_search_value_" + self.type_str
  84
  85    @property
  86    def c_type(self):
  87       return "nir_search_" + self.type_str
  88
  89    @property
  90    def c_ptr(self):
  91       return "&{0}.value".format(self.name)
  92
  93    def render(self):
  94       return self.__template.render(val=self,
  95                                     Constant=Constant,
  96                                     Variable=Variable,
  97                                     Expression=Expression)
  98
  99 class Constant(Value):
 100    def __init__(self, val, name):
 101       Value.__init__(self, name, "constant")
 102       self.value = val
 103
 104    def __hex__(self):
 105       # Even if it's an integer, we still need to unpack as an unsigned
 106       # int.  This is because, without C99, we can only assign to the first
 107       # element of a union in an initializer.
 108       if isinstance(self.value, (bool)):
 109          return 'NIR_TRUE' if self.value else 'NIR_FALSE'
 110       if isinstance(self.value, (int, long)):
 111          return hex(struct.unpack('I', struct.pack('i', self.value))[0])
 112       elif isinstance(self.value, float):
 113          return hex(struct.unpack('I', struct.pack('f', self.value))[0])
 114       else:
 115          assert False
 116
 117 _var_name_re = re.compile(r"(?P<const>#)?(?P<name>\w+)(?:@(?P<type>\w+))?")
 118
 119 class Variable(Value):
 120    def __init__(self, val, name, varset):
 121       Value.__init__(self, name, "variable")
 122
 123       m = _var_name_re.match(val)
 124       assert m and m.group('name') is not None
 125
 126       self.var_name = m.group('name')
 127       self.is_constant = m.group('const') is not None
 128       self.required_type = m.group('type')
 129
 130       if self.required_type is not None:
 131          assert self.required_type in ('float', 'bool', 'int', 'unsigned')
 132
 133       self.index = varset[self.var_name]
 134
 135 class Expression(Value):
 136    def __init__(self, expr, name_base, varset):
 137       Value.__init__(self, name_base, "expression")
 138       assert isinstance(expr, tuple)
 139
 140       self.opcode = expr[0]
 141       self.sources = [ Value.create(src, "{0}_{1}".format(name_base, i), varset)
 142                        for (i, src) in enumerate(expr[1:]) ]
 143
 144    def render(self):
 145       srcs = "\n".join(src.render() for src in self.sources)
 146       return srcs + super(Expression, self).render()
 147
 148 _optimization_ids = itertools.count()
 149
 150 condition_list = ['true']
 151
 152 class SearchAndReplace(object):
 153    def __init__(self, transform):
 154       self.id = _optimization_ids.next()
 155
 156       search = transform[0]
 157       replace = transform[1]
 158       if len(transform) > 2:
 159          self.condition = transform[2]
 160       else:
 161          self.condition = 'true'
 162
 163       if self.condition not in condition_list:
 164          condition_list.append(self.condition)
 165       self.condition_index = condition_list.index(self.condition)
 166
 167       varset = VarSet()
 168       if isinstance(search, Expression):
 169          self.search = search
 170       else:
 171          self.search = Expression(search, "search{0}".format(self.id), varset)
 172
 173       varset.lock()
 174
 175       if isinstance(replace, Value):
 176          self.replace = replace
 177       else:
 178          self.replace = Value.create(replace, "replace{0}".format(self.id), varset)
 179
 180 _algebraic_pass_template = mako.template.Template("""
 181 #include "nir.h"
 182 #include "nir_search.h"
 183
 184 #ifndef NIR_OPT_ALGEBRAIC_STRUCT_DEFS
 185 #define NIR_OPT_ALGEBRAIC_STRUCT_DEFS
 186
 187 struct transform {
 188    const nir_search_expression *search;
 189    const nir_search_value *replace;
 190    unsigned condition_offset;
 191 };
 192
 193 struct opt_state {
 194    void *mem_ctx;
 195    bool progress;
 196    const bool *condition_flags;
 197 };
 198
 199 #endif
 200
 201 % for (opcode, xform_list) in xform_dict.iteritems():
 202 % for xform in xform_list:
 203    ${xform.search.render()}
 204    ${xform.replace.render()}
 205 % endfor
 206
 207 static const struct transform ${pass_name}_${opcode}_xforms[] = {
 208 % for xform in xform_list:
 209    { &${xform.search.name}, ${xform.replace.c_ptr}, ${xform.condition_index} },
 210 % endfor
 211 };
 212 % endfor
 213
 214 static bool
 215 ${pass_name}_block(nir_block *block, void *void_state)
 216 {
 217    struct opt_state *state = void_state;
 218
 219    nir_foreach_instr_safe(block, instr) {
 220       if (instr->type != nir_instr_type_alu)
 221          continue;
 222
 223       nir_alu_instr *alu = nir_instr_as_alu(instr);
 224       if (!alu->dest.dest.is_ssa)
 225          continue;
 226
 227       switch (alu->op) {
 228       % for opcode in xform_dict.keys():
 229       case nir_op_${opcode}:
 230          for (unsigned i = 0; i < ARRAY_SIZE(${pass_name}_${opcode}_xforms); i++) {
 231             const struct transform *xform = &${pass_name}_${opcode}_xforms[i];
 232             if (state->condition_flags[xform->condition_offset] &&
 233                 nir_replace_instr(alu, xform->search, xform->replace,
 234                                   state->mem_ctx)) {
 235                state->progress = true;
 236                break;
 237             }
 238          }
 239          break;
 240       % endfor
 241       default:
 242          break;
 243       }
 244    }
 245
 246    return true;
 247 }
 248
 249 static bool
 250 ${pass_name}_impl(nir_function_impl *impl, const bool *condition_flags)
 251 {
 252    struct opt_state state;
 253
 254    state.mem_ctx = ralloc_parent(impl);
 255    state.progress = false;
 256    state.condition_flags = condition_flags;
 257
 258    nir_foreach_block(impl, ${pass_name}_block, &state);
 259
 260    if (state.progress)
 261       nir_metadata_preserve(impl, nir_metadata_block_index |
 262                                   nir_metadata_dominance);
 263
 264    return state.progress;
 265 }
 266
 267
 268 bool
 269 ${pass_name}(nir_shader *shader)
 270 {
 271    bool progress = false;
 272    bool condition_flags[${len(condition_list)}];
 273    const nir_shader_compiler_options *options = shader->options;
 274
 275    % for index, condition in enumerate(condition_list):
 276    condition_flags[${index}] = ${condition};
 277    % endfor
 278
 279    nir_foreach_function(shader, function) {
 280       if (function->impl)
 281          progress |= ${pass_name}_impl(function->impl, condition_flags);
 282    }
 283
 284    return progress;
 285 }
 286 """)
 287
 288 class AlgebraicPass(object):
 289    def __init__(self, pass_name, transforms):
 290       self.xform_dict = {}
 291       self.pass_name = pass_name
 292
 293       for xform in transforms:
 294          if not isinstance(xform, SearchAndReplace):
 295             xform = SearchAndReplace(xform)
 296
 297          if xform.search.opcode not in self.xform_dict:
 298             self.xform_dict[xform.search.opcode] = []
 299
 300          self.xform_dict[xform.search.opcode].append(xform)
 301
 302    def render(self):
 303       return _algebraic_pass_template.render(pass_name=self.pass_name,
 304                                              xform_dict=self.xform_dict,
 305                                              condition_list=condition_list)