[Mesa-dev] [PATCH 00/12] nir: Add an integer divide by constant optimization

[Jason Ekstrand]

It's reasonably well-known that you can replace an unsigned integer
division by a constant with a sequence of multiply (by constant), adds, and
shifts.  This little series implements such an optimization for NIR.  This
second version of the series is based on the integer division by constant
code by rediculousfish.  I've tried to keep authorship of the various bits
as accurate as I can hence the rather eclectic collection of patches.

Ian Romanick (2):
  nir: Add a saturated unsigned integer add opcode
  i965/fs: Implement nir_op_uadd_sat

Jason Ekstrand (7):
  util: Add a simple big math library
  util: Generalize fast integer division to be variable bit-width
  util: Add tests for fast integer division by constants
  nir: Allow [iu]mul_high on non-32-bit types
  nir/lower_int64: Add support for [iu]mul_high
  nir: Add a pass for lowering integer division by constants
  i965: Enable nir_opt_idiv_const for all bit sizes

Marek Olšák (3):
  util: import public domain code for integer division by a constant
  util: Add fast division helpers
  util: Add power-of-two divisor support to compute_fast_udiv_info

 configure.ac                                  |   1 +
 src/compiler/Makefile.sources                 |   1 +
 src/compiler/nir/meson.build                  |   1 +
 src/compiler/nir/nir.h                        |   3 +
 src/compiler/nir/nir_constant_expressions.py  |   1 +
 src/compiler/nir/nir_lower_int64.c            |  54 ++
 src/compiler/nir/nir_opcodes.py               |  45 +-
 src/compiler/nir/nir_opt_idiv_const.c         | 215 ++++++++
 src/intel/compiler/brw_fs_nir.cpp             |   5 +
 src/intel/compiler/brw_nir.c                  |   4 +-
 src/util/Makefile.am                          |   4 +-
 src/util/Makefile.sources                     |   3 +
 src/util/bigmath.h                            | 112 +++++
 src/util/fast_idiv_by_const.c                 | 243 +++++++++
 src/util/fast_idiv_by_const.h                 | 178 +++++++
 src/util/meson.build                          |   4 +
 src/util/tests/fast_idiv_by_const/Makefile.am |  43 ++
 .../fast_idiv_by_const_test.cpp               | 472 ++++++++++++++++++
 src/util/tests/fast_idiv_by_const/meson.build |  30 ++
 19 files changed, 1413 insertions(+), 6 deletions(-)
 create mode 100644 src/compiler/nir/nir_opt_idiv_const.c
 create mode 100644 src/util/bigmath.h
 create mode 100644 src/util/fast_idiv_by_const.c
 create mode 100644 src/util/fast_idiv_by_const.h
 create mode 100644 src/util/tests/fast_idiv_by_const/Makefile.am
 create mode 100644 src/util/tests/fast_idiv_by_const/fast_idiv_by_const_test.cpp
 create mode 100644 src/util/tests/fast_idiv_by_const/meson.build

-- 
2.19.0