nir: Add a pass for lowering copy instructions

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

nir/vars_to_ssa: Refactor get_deref_node

This refactor allows you to more easily get the deref node associated with
a given variable.  We then use that new functionality in the
deref_may_be_aliased function instead of creating a 1-element deref chain.

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

nir: Rename lower_variables to lower_vars_to_ssa

The original name wasn't particularly descriptive.  This one indicates that
it actually gives you SSA values as opposed to the old pass which lowered
variables to registers.

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

nir/tex_instr: Add a nir_tex_src struct and dynamically allocate the src array

This solves a number of problems.  First is the ability to change the
number of sources that a texture instruction has.  Second, it solves the
delema that may occur if a texture instruction has more than 4 sources.

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

nir/validate: Only build in debug mode

Reviewed-by: Kenneth Graunke <kenneth@whitecape.org>
Reviewed-by: Matt Turner <mattst88@gmail.com>
Reviewed-by: Connor Abbott <cwabbott0@gmail.com>

nir/lower_variables: Improve documentation

Additional description was added to a variety of places.  Also, we no
longer use the term "leaf" to describe fully-qualified direct derefs.
Instead, we simply use the term "direct" or spell it out completely.

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

nir/lower_variables: Use a for loop for get_deref_node

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

nir: Use the actual FNV-1a hash for hashing derefs

We also switch to using loops rather than recursion.

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

util/hash_table: Pull the details of the FNV-1a into helpers

This way the basics of the FNV-1a hash can be reused to easily create other
hashing functions.

Reviewed-by: Eric Anholt <eric@anholt.net>

nir: Make intrinsic flags into an enum

This should be much better for debugging as GDB will pick up on the fact
that it's an enum and actually tell you what you're looking at instead of
giving you some arbitrary hex value you have to go look up.

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

nir: Use static inlines instead of macros for list getters

This should make debugging a lot easier as GDB handles static inlines much
better than macros.  Also, static inlines are typesafe.

Reviewed-By: Glenn Kennard <glenn.kennard@gmail.com>
Reviewed-by: Connor Abbott <cwabbott0@gmail.com>

nir/variable: Remove the constant_value field

This was a left-over relic of GLSL IR that we aren't using for anything.
If we ever want that value again, we can add it back, but NIR constant
folding should be just as good as GLSL IR's if not better pretty soon, so
I'm not worried about it.

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

nir: Add some documentation

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

nir/lower_variables: Follow the Cytron paper more closely

Previously, our variable renaming algorithm, while similar to the one in
the Cytron paper, was not the same.  While I'm pretty sure it was correct,
it will be easier for readers of the code in the variable renaming pass if
it follows more closely.  This commit removes the automatic stack popping
we were doing and replaces it with explicit popping like Cytron does.

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

nir/print: Various cleanups recommended by Eric

Cc: Eric Anholt <eric@anholt.net>
Reviewed-by: Connor Abbott <cwabbott0@gmail.com>

nir/lower_variables: Add a bunch of comments and re-arrange a few things

This commit seeks to make the lower_variables pass much more clear by
adding a pile of comments and re-arranging a few things.  There are no
functional or algorithmic changes.

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

nir: Rename parallel_copy_copy to parallel_copy_entry and add a foreach macro

parallel_copy_copy was a silly name.  Also, things were getting long and
annoying, so I added a foreach macro.  For historical reasons, several of
the original iterations over parallel copy entries in from_ssa used the
_safe variants of the loop.  However, all of these no longer ever remove an
entry so it's ok to make them all use the normal iterator.

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

nir/from_ssa: Clean up parallel copy handling and document it better

Previously, we were doing a lazy creation of the parallel copy
instructions.  This is confusing, hard to get right, and involves some
extra state tracking of the copies.  This commit adds an extra walk over
the basic blocks to add the block-end parallel copies up front.  This
should be much less confusing and, consequently, easier to get right.  This
commit also adds more comments about parallel copies to help explain what
all is going on.

As a consequence of these changes, we can now remove the at_end parameter
from nir_parallel_copy_instr.

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

nir: Rename nir_block_following_if to nir_block_get_following_if

The new name is a little longer but less confusing.

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

i965/fs_nir: Handle sample ID, position, and mask better

Before, we were emitting the full pile of setup instructions for sample_id
and sample_pos every time they were used.  With this commit, we emit them
in their own pass once at the beginning of the shader and simply emit uses
later on.  When it comes time for setting up VS, we can put setup for its
special values in the same pass.

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

nir/opcodes: Remove the per_component info field

Originally, this field was intended for determining if the given
instruction acted per-component or if it had mismatching source and
destination sizes that would have to be interpreted specially.  However, we
can easily derive this from output_size == 0, so it's not really that
useful.  Also, the values we were setting in nir_opcodes.h for this field
were completely bogus and it was never used.

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

nir/search: Use nir_op_infos to determine if an operation is commutative

Prior to this commit, we had a big switch statement for this.  Now it's
baked into the opcode metadata so we can just use that.

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

nir/opcodes: Add algebraic properties metadata

This commit adds some algebraic properties to the metadata of each opcode
in NIR.  In particular, you now know, just from the metadata, if a given
opcode is commutative or associative.  This will be useful for algebraic
transformation passes that want to be able to match a + b as well as b + a
in one go.

v2: Make algebraic properties all caps.  This was more consistent with the
    intrinsics flags and seems better for flags in general.

    Also, the enums are now declared with (1 << n) rather then hex values.

v3: fmin and fmax technically aren't commutative or associative.  Things
    get funny when one of the arguments is a NaN.

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

nir: Make load_const SSA-only

As it was, we weren't ever using load_const in a non-SSA way.  This allows
us to substantially simplify the load_const instruction.  If we ever need a
non-SSA constant load, we can do a load_const and an imov.

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

nir: Make nir_ssa_undef_instr_create initialize the destination

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

i965/nir: Move the other lowering passes to before out-of-SSA

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

nir/lower_system_values: Handle SSA destinations

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

nir/lower_atomics: Use/support SSA

Previously, lower_atomics was non-SSA only.  We assert-failed if the
destination of an atomic operation intrinsic was an SSA def and we used
temporary registers for computing offsets.  This commit changes both of
these behaviors.  We now use SSA values for computing offsets (so we can
optimize them) and we handle SSA destinations.  We also move the pass to
run before we go out of SSA on i965 as it now generates SSA values.

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

nir/live_variables: Use the new ssa_def iterator

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

nir: Use nir_foreach_ssa_def for setting up ssa destinations

Before, we were using foreach_dest and switching on whether the destination
was an SSA value.  This works, except not all destinations are SSA values
so we have to special-case ssa_undef instructions.  Now that we have a
foreach_ssa_def function, we can iterate over all of the register
destinations in one pass and iterate over the SSA destinations in a second.
This way, if we add other ssa-only instructions, we won't have to worry
about adding them to the special case we have for ssa_undef.

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

nir: Add a foreach_ssa_def function

There are some functions whose destinations are SSA-only and so aren't a
nir_dest.  This provides a function that is capable of iterating over the
SSA definitions defined by those functions.  If you want registers, you
should use the old iterator.

v2: Kenneth Graunke <kenneth@whitecape.org>:
 - Fix nir_foreach_ssa_def's return value.

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

nir/lower_variables: Use a real dominance DFS for variable renaming

Previously, we were just iterating over the program "in order" which
kind-of approximates a DFS, but not really.  In particular, we got the
following case wrong:

loop {
   a = 3;
   if (foo) {
      a = 5;
   } else {
      break;
   }
   use(a);
}

where use(a) would get 3 instead of 5 because of premature popping of the
SSA def stack.  Now, since we do an actaul DFS, we should evaluate use(a)
immediately after a = 5 and we should be ok.

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

nir: Remove predication

We stopped generating predicates in glsl_to_nir some time ago.  Right now,
it's all dead untested code that I'm not convinced always worked in the
first place.  If we decide we want them back, we can revert this patch.

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

nir: Make bcsel a fully vector operation

Previously, the condition was a scalar that applied to all components
simultaneously.  As of this commit, the condition is a vector and each
component is switched seperately.

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

nir: Call nir_metadata_preserve more places

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

nir/metadata: Rename metadata_dirty to metadata_preserve

nir_metadata_dirty was a terrible name because the parameter it takes is
the metadata to be preserved.  This is really confusing because it looks
like it's doing the opposite of what it is actually doing.  Now it's named
sensibly.

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

i965/fs_nir: Add support for indirect texture arrays

v2 Jason Ekstrand <jason.ekstrand@intel.com>:
 - Use the nir_tex_src_sampler_offset source type instead of the
   sampler_indirect thing that I cooked up before.

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

nir: Rework the way samplers are lowered

v2 Jason Ekstrand <jason.ekstrand@intel.com>:
 - Use the nir_tex_src_sampler_offset source type instead of the
   sampler_indirect thing that I cooked up before.

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

nir/tex_instr_create: Initialize all 4 sources

This helps a lot with things like lowering passes that may need to add
sources.

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

nir/tex_instr: Rename the indirect source type and add an array size

In particular, we rename nir_tex_src_sampler_index to _sampler_offset and
add a sampler_array_size field to nir_tex_instr.  This way we can pass the
size of sampler arrays through to backends even after removing the variable
information and, with it, the type.

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

nir: Use a source for uniform buffer indices instead of an index

In GLSL-to-NIR we were just setting the base index to 0 whenever there was
an indirect so having it expressed as a sum makes no sense.  Also, while a
base offset may make sense for the memory location (first element in the
array, etc.) it makes less sense for the actual uniform buffer index.  This
may change later, but it seems to make more sense for now.

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

nir: Constant fold array indirects

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

nir: Make texture instruction names more consistent

This commit renames nir_instr_as_texture to nir_instr_as_tex and renames
nir_instr_type_texture to nir_instr_type_tex to be consistent with
nir_tex_instr.

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

nir: Remove the ffma peephole

This is no longer needed because it's now part of the algebraic
optimization pass

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

nir: Add a basic constant folding pass

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

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>