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