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 from __future__ import print_function
  28 import itertools
  29 import struct
  30 import sys
  31 import mako.template
  32 import re
  33 import traceback
  34
  35 # Represents a set of variables, each with a unique id
  36 class VarSet(object):
  37    def __init__(self):
  38       self.names = {}
  39       self.ids = itertools.count()
  40       self.immutable = False;
  41
  42    def __getitem__(self, name):
  43       if name not in self.names:
  44          assert not self.immutable, "Unknown replacement variable: " + name
  45          self.names[name] = self.ids.next()
  46
  47       return self.names[name]
  48
  49    def lock(self):
  50       self.immutable = True
  51
  52 class Value(object):
  53    @staticmethod
  54    def create(val, name_base, varset):
  55       if isinstance(val, tuple):
  56          return Expression(val, name_base, varset)
  57       elif isinstance(val, Expression):
  58          return val
  59       elif isinstance(val, (str, unicode)):
  60          return Variable(val, name_base, varset)
  61       elif isinstance(val, (bool, int, long, float)):
  62          return Constant(val, name_base)
  63
  64    __template = mako.template.Template("""
  65 static const ${val.c_type} ${val.name} = {
  66    { ${val.type_enum} },
  67 % if isinstance(val, Constant):
  68    ${val.type()}, { ${hex(val)} /* ${val.value} */ },
  69 % elif isinstance(val, Variable):
  70    ${val.index}, /* ${val.var_name} */
  71    ${'true' if val.is_constant else 'false'},
  72    ${val.type() or 'nir_type_invalid' },
  73 % elif isinstance(val, Expression):
  74    ${'true' if val.inexact else 'false'},
  75    nir_op_${val.opcode},
  76    { ${', '.join(src.c_ptr for src in val.sources)} },
  77 % endif
  78 };""")
  79
  80    def __init__(self, name, type_str):
  81       self.name = name
  82       self.type_str = type_str
  83
  84    @property
  85    def type_enum(self):
  86       return "nir_search_value_" + self.type_str
  87
  88    @property
  89    def c_type(self):
  90       return "nir_search_" + self.type_str
  91
  92    @property
  93    def c_ptr(self):
  94       return "&{0}.value".format(self.name)
  95
  96    def render(self):
  97       return self.__template.render(val=self,
  98                                     Constant=Constant,
  99                                     Variable=Variable,
 100                                     Expression=Expression)
 101
 102 class Constant(Value):
 103    def __init__(self, val, name):
 104       Value.__init__(self, name, "constant")
 105       self.value = val
 106
 107    def __hex__(self):
 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(self.value)
 112       elif isinstance(self.value, float):
 113          return hex(struct.unpack('Q', struct.pack('d', self.value))[0])
 114       else:
 115          assert False
 116
 117    def type(self):
 118       if isinstance(self.value, (bool)):
 119          return "nir_type_bool32"
 120       elif isinstance(self.value, (int, long)):
 121          return "nir_type_int"
 122       elif isinstance(self.value, float):
 123          return "nir_type_float"
 124
 125 _var_name_re = re.compile(r"(?P<const>#)?(?P<name>\w+)(?:@(?P<type>\w+))?")
 126
 127 class Variable(Value):
 128    def __init__(self, val, name, varset):
 129       Value.__init__(self, name, "variable")
 130
 131       m = _var_name_re.match(val)
 132       assert m and m.group('name') is not None
 133
 134       self.var_name = m.group('name')
 135       self.is_constant = m.group('const') is not None
 136       self.required_type = m.group('type')
 137
 138       if self.required_type is not None:
 139          assert self.required_type in ('float', 'bool', 'int', 'uint')
 140
 141       self.index = varset[self.var_name]
 142
 143    def type(self):
 144       if self.required_type == 'bool':
 145          return "nir_type_bool32"
 146       elif self.required_type in ('int', 'uint'):
 147          return "nir_type_int"
 148       elif self.required_type == 'float':
 149          return "nir_type_float"
 150
 151 _opcode_re = re.compile(r"(?P<inexact>~)?(?P<opcode>\w+)")
 152
 153 class Expression(Value):
 154    def __init__(self, expr, name_base, varset):
 155       Value.__init__(self, name_base, "expression")
 156       assert isinstance(expr, tuple)
 157
 158       m = _opcode_re.match(expr[0])
 159       assert m and m.group('opcode') is not None
 160
 161       self.opcode = m.group('opcode')
 162       self.inexact = m.group('inexact') is not None
 163       self.sources = [ Value.create(src, "{0}_{1}".format(name_base, i), varset)
 164                        for (i, src) in enumerate(expr[1:]) ]
 165
 166    def render(self):
 167       srcs = "\n".join(src.render() for src in self.sources)
 168       return srcs + super(Expression, self).render()
 169
 170 _optimization_ids = itertools.count()
 171
 172 condition_list = ['true']
 173
 174 class SearchAndReplace(object):
 175    def __init__(self, transform):
 176       self.id = _optimization_ids.next()
 177
 178       search = transform[0]
 179       replace = transform[1]
 180       if len(transform) > 2:
 181          self.condition = transform[2]
 182       else:
 183          self.condition = 'true'
 184
 185       if self.condition not in condition_list:
 186          condition_list.append(self.condition)
 187       self.condition_index = condition_list.index(self.condition)
 188
 189       varset = VarSet()
 190       if isinstance(search, Expression):
 191          self.search = search
 192       else:
 193          self.search = Expression(search, "search{0}".format(self.id), varset)
 194
 195       varset.lock()
 196
 197       if isinstance(replace, Value):
 198          self.replace = replace
 199       else:
 200          self.replace = Value.create(replace, "replace{0}".format(self.id), varset)
 201
 202 _algebraic_pass_template = mako.template.Template("""
 203 #include "nir.h"
 204 #include "nir_search.h"
 205
 206 #ifndef NIR_OPT_ALGEBRAIC_STRUCT_DEFS
 207 #define NIR_OPT_ALGEBRAIC_STRUCT_DEFS
 208
 209 struct transform {
 210    const nir_search_expression *search;
 211    const nir_search_value *replace;
 212    unsigned condition_offset;
 213 };
 214
 215 struct opt_state {
 216    void *mem_ctx;
 217    bool progress;
 218    const bool *condition_flags;
 219 };
 220
 221 #endif
 222
 223 % for (opcode, xform_list) in xform_dict.iteritems():
 224 % for xform in xform_list:
 225    ${xform.search.render()}
 226    ${xform.replace.render()}
 227 % endfor
 228
 229 static const struct transform ${pass_name}_${opcode}_xforms[] = {
 230 % for xform in xform_list:
 231    { &${xform.search.name}, ${xform.replace.c_ptr}, ${xform.condition_index} },
 232 % endfor
 233 };
 234 % endfor
 235
 236 static bool
 237 ${pass_name}_block(nir_block *block, void *void_state)
 238 {
 239    struct opt_state *state = void_state;
 240
 241    nir_foreach_instr_reverse_safe(block, instr) {
 242       if (instr->type != nir_instr_type_alu)
 243          continue;
 244
 245       nir_alu_instr *alu = nir_instr_as_alu(instr);
 246       if (!alu->dest.dest.is_ssa)
 247          continue;
 248
 249       switch (alu->op) {
 250       % for opcode in xform_dict.keys():
 251       case nir_op_${opcode}:
 252          for (unsigned i = 0; i < ARRAY_SIZE(${pass_name}_${opcode}_xforms); i++) {
 253             const struct transform *xform = &${pass_name}_${opcode}_xforms[i];
 254             if (state->condition_flags[xform->condition_offset] &&
 255                 nir_replace_instr(alu, xform->search, xform->replace,
 256                                   state->mem_ctx)) {
 257                state->progress = true;
 258                break;
 259             }
 260          }
 261          break;
 262       % endfor
 263       default:
 264          break;
 265       }
 266    }
 267
 268    return true;
 269 }
 270
 271 static bool
 272 ${pass_name}_impl(nir_function_impl *impl, const bool *condition_flags)
 273 {
 274    struct opt_state state;
 275
 276    state.mem_ctx = ralloc_parent(impl);
 277    state.progress = false;
 278    state.condition_flags = condition_flags;
 279
 280    nir_foreach_block_reverse_call(impl, ${pass_name}_block, &state);
 281
 282    if (state.progress)
 283       nir_metadata_preserve(impl, nir_metadata_block_index |
 284                                   nir_metadata_dominance);
 285
 286    return state.progress;
 287 }
 288
 289
 290 bool
 291 ${pass_name}(nir_shader *shader)
 292 {
 293    bool progress = false;
 294    bool condition_flags[${len(condition_list)}];
 295    const nir_shader_compiler_options *options = shader->options;
 296    (void) options;
 297
 298    % for index, condition in enumerate(condition_list):
 299    condition_flags[${index}] = ${condition};
 300    % endfor
 301
 302    nir_foreach_function(shader, function) {
 303       if (function->impl)
 304          progress |= ${pass_name}_impl(function->impl, condition_flags);
 305    }
 306
 307    return progress;
 308 }
 309 """)
 310
 311 class AlgebraicPass(object):
 312    def __init__(self, pass_name, transforms):
 313       self.xform_dict = {}
 314       self.pass_name = pass_name
 315
 316       error = False
 317
 318       for xform in transforms:
 319          if not isinstance(xform, SearchAndReplace):
 320             try:
 321                xform = SearchAndReplace(xform)
 322             except:
 323                print("Failed to parse transformation:", file=sys.stderr)
 324                print("  " + str(xform), file=sys.stderr)
 325                traceback.print_exc(file=sys.stderr)
 326                print('', file=sys.stderr)
 327                error = True
 328                continue
 329
 330          if xform.search.opcode not in self.xform_dict:
 331             self.xform_dict[xform.search.opcode] = []
 332
 333          self.xform_dict[xform.search.opcode].append(xform)
 334
 335       if error:
 336          sys.exit(1)
 337
 338    def render(self):
 339       return _algebraic_pass_template.render(pass_name=self.pass_name,
 340                                              xform_dict=self.xform_dict,
 341                                              condition_list=condition_list)