nir: Add an algebraic optimization pass

This pass uses the previously built algebraic transformations framework and
should act as an example for anyone else wanting to make an algebraic
transformation pass for NIR.

Reviewed-by: Matt Turner <mattst88@gmail.com>
Reviewed-by: Connor Abbott <cwabbott0@gmail.com>

nir: Add infastructure for generating algebraic transformation passes

This commit builds on the nir_search.h infastructure by adding a bit of
python code that makes it stupid easy to write an algebraic transformation
pass.  The nir_algebraic.py file contains four python classes that
correspond directly to the datastructures in nir_search.c and allow you to
easily generate the C code to represent them.  Given a list of
search-and-replace operations, it can then generate a function that applies
those transformations to a shader.

The transformations can be specified manually, or they can be specified
using nested tuples.  The nested tuples make a neat little language for
specifying expression trees and search-and-replace operations in a very
readable and easy-to-edit fasion.

The generated code is also fairly efficient.  Insteady of blindly calling
nir_replace_instr with every single transformation and on every single
instruction, it uses a switch statement on the instruction opcode to do a
first-order culling and only calls nir_replace_instr if the opcode is known
to match the first opcode in the search expression.

Reviewed-by: Connor Abbott <cwabbott0@gmail.com>

nir: Add an expression matching framework

This framework provides a simple way to do simple search-and-replace
operations on NIR code.  The nir_search.h header provides four simple data
structures for representing expressions:  nir_value and four subtypes:
nir_variable, nir_constant, and nir_expression.  An expression tree can
then be represented by nesting these data structures as needed.  The
nir_replace_instr function takes an instruction, an expression, and a
value; if the instruction matches the expression, it is replaced with a new
chain of instructions to generate the given replacement value.  The
framework keeps track of swizzles on sources and automatically generates
the currect swizzles for the replacement value.

Reviewed-by: Connor Abbott <cwabbott0@gmail.com>

nir/glsl: Emit abs, neg, and sat operations instead of source modifiers

Reviewed-by: Connor Abbott <cwabbott0@gmail.com>

nir: Make the type casting operations static inline functions

Previously, the casting operations were macros.  While this is usually
fine, the casting macro used the input parameter twice leading to strange
behavior when you passed the result of another function into it.  Since we
know the source and destination types explicitly, we don't loose anything
by making it a function.

Also, this gives us a nice little macro for creating cast function that
will hopefully prevent mistyping.

Reviewed-by: Connor Abbott <cwabbott0@gmail.com>

nir: Add a lowering pass for adding source modifiers where possible

Reviewed-by: Connor Abbott <cwabbott0@gmail.com>

nir: Add neg, abs, and sat opcodes

Reviewed-by: Connor Abbott <cwabbott0@gmail.com>

i965/fs_nir: Implement the ARB_gpu_shader5 interpolation intrinsics

Reviewed-by: Chris Forbes <chrisf@ijw.co.nz>

i965/fs_nir: Add a has_indirect flag and clean up some of the input/output code

Reviewed-by: Connor Abbott <cwabbott0@gmail.com>

nir: Add a helper for getting a constant value from an SSA source

Reviewed-by: Connor Abbott <cwabbott0@gmail.com>

nir/glsl: Add support for gpu_shader5 interpolation instrinsics

Reviewed-by: Connor Abbott <cwabbott0@gmail.com>

nir: Add gpu_shader5 interpolation intrinsics

Reviewed-by: Connor Abbott <cwabbott0@gmail.com>

nir/validate: Validate intrinsic source/destination sizes

Reviewed-by: Connor Abbott <cwabbott0@gmail.com>

nir: Vectorize intrinsics

We used to have the number of components built into the intrinsic.  This
meant that all of our load/store intrinsics had vec1, vec2, vec3, and vec4
variants.  This lead to piles of switch statements to generate the correct
intrinsic names, and introspection to figure out the number of components.
We can make things much nicer by allowing "vectorized" intrinsics.

Reviewed-by: Connor Abbott <cwabbott0@gmail.com>

nir: Remove the old variable lowering code

Reviewed-by: Connor Abbott <cwabbott0@gmail.com>

nir/validate: Ensure that outputs are write-only and inputs are read-only

Reviewed-by: Connor Abbott <cwabbott0@gmail.com>

i965/fs_nir: Use the new variable lowering code

This commit switches us over to the new variable lowering code which is
capable of properly handling lowering indirects as we go.

Reviewed-by: Connor Abbott <cwabbott0@gmail.com>

nir/glsl: Generate SSA NIR

With this commit, the GLSL IR -> NIR pass generates NIR in more-or-less SSA
form.  It's SSA in the sense that it doesn't have any registers, but it
isn't really useful SSA because it still has a pile of load/store
intrinsics that we will need to get rid of.

Reviewed-by: Connor Abbott <cwabbott0@gmail.com>

nir: Add a pass to lower global variables to local variables

Reviewed-by: Connor Abbott <cwabbott0@gmail.com>

nir: Add a pass for lowering input/output loads/stores

Reviewed-by: Connor Abbott <cwabbott0@gmail.com>

nir: Add a pass to lower local variables to registers

Reviewed-by: Connor Abbott <cwabbott0@gmail.com>

nir: Add a pass to lower local variable accesses to SSA values

This pass analizes all of the load/store operations and, when a variable is
never aliased (potentially used by an indirect operation), it is lowered
directly to an SSA value.  This pass translates to SSA directly and does
not require any fixup by the original to-SSA pass.

Reviewed-by: Connor Abbott <cwabbott0@gmail.com>

nir: Add a copy splitting pass

Reviewed-by: Connor Abbott <cwabbott0@gmail.com>

nir: Automatically update SSA if uses

Reviewed-by: Connor Abbott <cwabbott0@gmail.com>

i965/fs_nir: Don't dump the shader.

This is killing piglit.  I'll leave the logging local

Reviewed-by: Connor Abbott <cwabbott0@gmail.com>

nir/glsl: Don't allocate a state_slots array for 0 state slots

Reviewed-by: Connor Abbott <cwabbott0@gmail.com>

nir: Validate that the sources of a phi have the same size as the destination

Reviewed-by: Connor Abbott <cwabbott0@gmail.com>

nir/copy_propagate: Don't cause size mismatches on phi node sources

Reviewed-by: Connor Abbott <cwabbott0@gmail.com>

nir: Don't require a function in ssa_def_init

Instead, we give SSA definitions a temporary index of 0xFFFFFFFF if the
instruction does not have a block and a proper index when it actually gets
added to the list.

Reviewed-by: Connor Abbott <cwabbott0@gmail.com>

nir: Use an integer index for specifying structure fields

Previously, we used a string name.  It was nice for translating out of GLSL
IR (which also does that) but cumbersome the rest of the time.

Reviewed-by: Connor Abbott <cwabbott0@gmail.com>

nir: Add a concept of a wildcard array dereference

Reviewed-by: Connor Abbott <cwabbott0@gmail.com>

nir: Make array deref direct vs. indirect an enum

Reviewed-by: Connor Abbott <cwabbott0@gmail.com>

nir: Clean up nir_deref helper functions

Reviewed-by: Connor Abbott <cwabbott0@gmail.com>

nir/lower_samplers: Use the nir_instr_rewrite_src function

Reviewed-by: Connor Abbott <cwabbott0@gmail.com>

nir: Add a helper for rewriting an instruction source

Reviewed-by: Connor Abbott <cwabbott0@gmail.com>

i965/fs_nir: Properly saturate multiplies

Reviewed-by: Connor Abbott <cwabbott0@gmail.com>

nir/from_ssa: Don't lower constant SSA values to registers

Backends want to be able to do special things with constant values such as
put them into immediates or make decisions based on whether or not a value
is constant.  Before, constants always got lowered to a load_const into a
register and then a register use.  Now we leave constants as SSA values so
backends can special-case them if they want.  Since handling constant SSA
values is trivial, this shouldn't be a problem for backends.

Reviewed-by: Connor Abbott <cwabbott0@gmail.com>

i965/fs_nir: Handle SSA constants

Reviewed-by: Connor Abbott <cwabbott0@gmail.com>

i965/fs_nir: Use an array rather than a hash table for register lookup

Reviewed-by: Connor Abbott <cwabbott0@gmail.com>

i965/fs_nir: Add the CSE pass and actually run in a loop

Reviewed-by: Connor Abbott <cwabbott0@gmail.com>

nir: Add a basic CSE pass

This pass is still fairly basic.  It only handles ALU operations, constant
loads, and phi nodes.  No texture ops or intrinsics yet.

Reviewed-by: Connor Abbott <cwabbott0@gmail.com>

nir: Add a fused multiply-add peephole

nir: Validate that the SSA def and register indices are unique

Reviewed-by: Connor Abbott <cwabbott0@gmail.com>

i965/fs_nir: Turn on the peephole select optimization

Reviewed-by: Connor Abbott <cwabbott0@gmail.com>

nir: Add a peephole select optimization

Reviewed-by: Connor Abbott <cwabbott0@gmail.com>

nir/nir: Patch up phi predecessors in move_successors

Reviewed-by: Connor Abbott <cwabbott0@gmail.com>

nir/nir: Use safe iterators when iterating over the CFG

Reviewed-by: Connor Abbott <cwabbott0@gmail.com>

glsl/list: Add a foreach_list_typed_safe_reverse macro

Reviewed-by: Connor Abbott <cwabbott0@gmail.com>

nir/nir: Fix a bug in move_successors

The unlink_blocks function moves successors around to make sure that, if
there is a remaining successor, it is in the first successors slot and not
the second.  To fix this, we simply get both successors up front.

Reviewed-by: Connor Abbott <cwabbott0@gmail.com>

i965/fs_nir: Validate optimization passes

Reviewed-by: Connor Abbott <cwabbott0@gmail.com>

nir: Differentiate between signed and unsigned versions of find_msb

We also make the return types match GLSL.  The GLSL spec specifies that
findMSB and findLSB return a signed integer.  Previously, nir had them
return unsigned.  This updates nir's behavior to match what GLSL expects.

We also update the nir-to-fs generator to take the new instructions.  While
we're at it, we fix the case where the input to findMSB is zero.

Reviewed-by: Connor Abbott <cwabbott0@gmail.com>

nir/print: Don't reindex things

These indices should now be reasonably stable/consistent.  Redoing the
indices in the print functions makes it harder to debug problems.

Reviewed-by: Connor Abbott <cwabbott0@gmail.com>

nir: Validate all lists in the validator

Reviewed-by: Connor Abbott <cwabbott0@gmail.com>

glsl/list: Fix the exec_list_validate function

Some time while refactoring things to make it look nicer before pushing to
master, I completely broke the function.  This fixes it to be correct.
Just goes to show you why you souldn't push code that has no users yet...

Signed-off-by: Jason Ekstrand <jason.ekstrand@intel.com>
Reviewed-by: Connor Abbott <cwabbott0@gmail.com>
Reviewed-by: Matt Turner <mattst88@gmail.com>

i965/fs_nir: Do retyping for ALU srouces in get_nir_alu_src

Reviewed-by: Connor Abbott <cwabbott0@gmail.com>

nir: Add a better out-of-SSA pass

This commit rewrites the out-of-SSA pass to not be nearly as naieve.  It's
based on "Revisiting Out-of-SSA Translation for Correctness, Code Quality,
and Efficiency" by Boissinot et. al.  It should be fairly close to
state-of-the art.

Reviewed-by: Connor Abbott <cwabbott0@gmail.com>

nir: Add a function for comparing two sources

Reviewed-by: Connor Abbott <cwabbott0@gmail.com>

nir: Add a parallel copy instruction type

Reviewed-by: Connor Abbott <cwabbott0@gmail.com>

nir: Add a function for rewriting all the uses of a SSA def

Reviewed-by: Connor Abbott <cwabbott0@gmail.com>

nir: Automatically handle SSA uses when an instruction is inserted

Reviewed-by: Connor Abbott <cwabbott0@gmail.com>

nir: Add an initialization function for SSA definitions

Reviewed-by: Connor Abbott <cwabbott0@gmail.com>

nir: Add an SSA-based liveness analysis pass.

Reviewed-by: Connor Abbott <cwabbott0@gmail.com>

nir: set reg_alloc and ssa_alloc when indexing registers and SSA values

Reviewed-by: Connor Abbott <cwabbott0@gmail.com>

nir: Add a function to detect if a block is immediately followed by an if

Since we don't actually have an "if" instruction, this is a very common
pattern when iterating over instructions.  This adds a helper function for
it to make things a little less painful.

Reviewed-by: Connor Abbott <cwabbott0@gmail.com>

nir: Add a foreach_block_reverse function

Reviewed-by: Connor Abbott <cwabbott0@gmail.com>

nir/foreach_block: Return false if the callback on the last block fails

Reviewed-by: Connor Abbott <cwabbott0@gmail.com>

nir: Add a basic metadata management system

Reviewed-by: Connor Abbott <cwabbott0@gmail.com>

nir/lower_variables_scalar: Silence a compiler warning

Reviewed-by: Connor Abbott <cwabbott0@gmail.com>

i965/fs_nir: Convert the shader to/from SSA

Reviewed-by: Connor Abbott <cwabbott0@gmail.com>

nir: Add a lower_vec_to_movs pass

Reviewed-by: Connor Abbott <cwabbott0@gmail.com>

nir: Add a naieve from-SSA pass

This pass is kind of stupidly implemented but it should be enough to get us
up and going.  We probably want something better that doesn't generate all
of the redundant moves eventually.  However, the i965 backend should be
able to handle the movs, so I'm not too worried about it in the short term.

i965/fs_nir: Don't duplicate emit_general_interpolation

Reviewed-by: Connor Abbott <cwabbott0@gmail.com>

i965/fs: Don't take an ir_variable for emit_general_interpolation

Previously, emit_general_interpolation took an ir_variable and pulled the
information it needed from that.  This meant that in fs_fp, we were
constructing a dummy ir_variable just to pass into it.  This commit makes
emit_general_interpolation take only the information it needs and gets rid
of the fs_fp cruft.

Reviewed-by: Connor Abbott <cwabbott0@gmail.com>

nir: Add intrinsics to do alternate interpolation on inputs

Reviewed-by: Connor Abbott <cwabbott0@gmail.com>

nir: Add NIR_TRUE and NIR_FALSE constants and use them for boolean immediates

Reviewed-by: Connor Abbott <cwabbott0@gmail.com>

i965/fs_nir: Add atomic counters support

Reviewed-by: Connor Abbott <cwabbott0@gmail.com>

nir/lower_atomics: Multiply array offsets by ATOMIC_COUNTER_SIZE

Reviewed-by: Connor Abbott <cwabbott0@gmail.com>

i965/fs_nir: Handle coarse/fine derivatives

Reviewed-by: Connor Abbott <cwabbott0@gmail.com>

nir/glsl: Add support for coarse and fine derivatives

Reviewed-by: Connor Abbott <cwabbott0@gmail.com>

nir: Add fine and coarse derivative opcodes

Reviewed-by: Connor Abbott <cwabbott0@gmail.com>

nir/glsl: Add support for saturate

Reviewed-by: Connor Abbott <cwabbott0@gmail.com>

i965/fs_nir: Add support for sample_pos and sample_id

Fix up varying pull constants

Reviewed-by: Connor Abbott <cwabbott0@gmail.com>

Fix what I think are a few NIR typos

Reviewed-by: Connor Abbott <cwabbott0@gmail.com>

i965/fs_nir: Use the correct texture offset immediate

Reviewed-by: Connor Abbott <cwabbott0@gmail.com>

i965/fs_nir: Use the correct types for texture inputs

Reviewed-by: Connor Abbott <cwabbott0@gmail.com>

i965/fs_nir: Make the sampler register always unsigned

Reviewed-by: Connor Abbott <cwabbott0@gmail.com>

i965/fs: Only use nir for 8-wide non-fast-clear shaders.

Reviewed-by: Connor Abbott <cwabbott0@gmail.com>

i965/fs: add a NIR frontend

This is similar to the GLSL IR frontend, except consuming NIR. This lets
us test NIR as part of an actual compiler.

v2: Jason Ekstrand <jason.ekstrand@intel.com>:
   Make brw_fs_nir build again
   Only use NIR of INTEL_USE_NIR is set
   whitespace fixes

i965/fs: Don't pass through the coordinate type

All we really need is the number of components.

i965/fs: make emit_fragcoord_interpolation() not take an ir_variable

nir: add an SSA-based dead code elimination pass

v2: Jason Ekstrand <jason.ekstrand@intel.com>:
   whitespace fixes

nir: add an SSA-based copy propagation pass

nir: add a pass to convert to SSA

v2: Jason Ekstrand <jason.ekstrand@intel.com>:
   whitespace fixes

nir: calculate dominance information

nir: add an optimization to turn global registers into local registers

After linking and inlining, this allows us to convert these registers
into SSA values and optimise more code.

nir: add a pass to lower atomics

v2: Jason Ekstrand <jason.ekstrand@intel.com>
   whitespace fixes

nir: add a pass to lower system value reads

v2: Jason Ekstrand <jason.ekstrand@intel.com>:
   whitespace fixes

nir: add a pass to lower sampler instructions

nir: add a pass to remove unused variables

After we lower variables, we want to delete them in order to free up
some memory.

v2: Jason Ekstrand <jason.ekstrand@intel.com>:
    whitespace fixes