Android.mk: add source/opt/fold.cpp

Merge pull request #885 from dnovillo/const-prop

Re-factor generic constant folding code out of fold spec constants pass

Re-factor generic constant folding code out of FoldSpecConstantOpAndCompositePass

There are no functional changes in this patch.  The generic folding
routines in FoldSpecConstantOpAndCompositePass are now inside opt/fold.{cpp,h}.
This code will be used by the upcoming constant propagation pass.  In
time, we'll add more expression folding and simplification into these
two files.

ADCE: Treat privates like locals in entry point with no calls

This is needed for ongoing legalization of HLSL. It allows removal
of accesses to textures/buffers that are not used.

Opt: Move *NextId functionality into MemPass

Validator: Test OpReturnValue type check

The check already existed.  I added a test for it.

Fixes https://github.com/KhronosGroup/SPIRV-Tools/issues/876

Reenable validate type unique pass

Vulkan CTS patch fixing the instances of non-unique type declaration in
autogenerated code has recently been submitted.

Refactored MARK-V API

- switched from C to C++
- moved MARK-V model creation from backend to frontend
- The same MARK-V model object can be used to encode/decode multiple
files
- Added MARK-V model factory (currently only one option)
- Added --validate option to spirv-markv (run validation while
encoding/decoding)

Validator checks OpReturn called from void func

Added check into validate_cfg which checks that OpReturn is not called
from functions which are supposed to return a value.

Generic intrusive linked list class.

This commit is the initial implementation of the intrusive linked list
class.  It includes the implementation in the header files, and unit
test.

The iterators are circular: incrementing end() gives begin() and
decrementing begin() gives end().  Also made it valid to
decrement end().

Expliticly defines move constructor and move assignment
- Visual Studio 2013 does not implicitly generate the move constructor or
  move assignments.  So they need to be explicit, otherwise it will try to
  use the copy constructor, which we explicitly deleted.
- Can't use "= default" either.
  Seems like VS2013 does not support explicitly using the default move
  constructors and move assignments, so I wrote them out.

DeadBranchElim: Add dead case elimination

Expands dead branch elimination to eliminate dead switch cases. It also
changes dbe to eliminate orphaned merge blocks and recursively eliminate
any blocks thereby orphaned.

Add Android.mk to SPIRV-Tools

Android.mk was migrated from shaderc/third_party.

android_test is a stub, only builds spirv-tools libs.h to test build.

Add -O, -Os and -Oconfig flags.

These flags are expanded to a series of spirv-opt flags with the
following semantics:

-O: expands to passes that attempt to improve the performance of the
    generated code.

-Os: expands to passes that attempt to reduce the size of the generated
     code.

-Oconfig=<file> expands to the sequence of passes determined by the
                flags specified in the user-provided file.

Set cmake-policy CMP0048 to NEW

Implement Linker (module combiner)

Add extra iterators for ir::Module's sections
Add extra getters to ir::Function
Add a const version of BasicBlock::GetLabelInst()

Use the max of all inputs' version as version

Split debug in debug1 and debug2
- Debug1 instructions have to be placed before debug2 instructions.

Error out if different addressing or memory models are found

Exit early if no binaries were given

Error out if entry points are redeclared

Implement copy ctors for Function and BasicBlock
- Visual Studio ends up generating copy constructors that call deleted
  functions while compiling the linker code, while GCC and clang do not.
  So explicitly write those functions to avoid Visual Studio messing up.

Move removing duplicate capabilities to its own pass

Add functions running on all IDs present in an instruction

Remove duplicate SpvOpExtInstImport

Give default options value for link functions

Remove linkage capability if not making a library

Check types before allowing to link

Detect if two types/variables/functions have different decorations

Remove decorations of imported variables/functions and their types

Add a DecorationManager

Add a method for removing all decorations of id

Add methods for removing operands from instructions

Error out if one of the modules has a non-zero schema

Update README.md to talk about the linker

Do not freak out if an imported built-in variable has no export

Remove duplicate dead branch elim pass declaration

The function had two declarations in the same header with somewhat
different comments.

Hack around bug in gcc-4.8.1 templates.

This keeps the previous behavior for other compilers that will
throw warnings on a negative shift operation, but works around
the internal compiler error in GCC.

AggressiveDCE: Fix to not treat parameter memory refs as local

This fixes a bug that incorrectly deletes stores to parameters, which
can be used to return values from functions.

Compact-ids pass should update the header ID bound

DiagnosticStream move ctor moves output duties to new object

- Take over contents of the expiring message stream
- Prevent the expiring object from emitting anything during destruction

Cache end iterators for speed

Helps scaling of DefUseManager on modules with many thousands
of instructions.

No use to check OpBitCount result width

Skip checking copyright if SPIRV_SKIP_TESTS is enabled

Update CHANGES to reflect fix for #827

Compact-ids pass should update instruction's result_id member

Also update the result type field.

Fixes https://github.com/KhronosGroup/SPIRV-Tools/issues/827

Remove duplicated declaration of CreateAggressiveDCEPass().

Add bitwise operations validator pass

The pass checks correctness of operand types of all bitwise instructions
(opcode range from SpvOpShiftRightLogical to SpvOpBitCount).

Add remaining opcodes to arithmetics validation

Add validation rules for:
- OpIAddCarry
- OpISubBorrow
- OpUMulExtended
- OpSMulExtended

Includes some refactoring of old code.

Update CHANGES with recent news

Create the dead function elimination pass

Creates a pass called eliminate dead functions that looks for functions
that could never be called, and deletes them from the module.

To support this change a new function was added to the Pass class to
traverse the call trees from diffent starting points.

Includes a test to ensure that annotations are removed when deleting a
dead function.  They were not, so fixed that up as well.

Did some cleanup of the assembly for the test in pass_test.cpp.  Trying
to make them smaller and easier to read.

Detach MARK-V from the validator

MARK-V codec was previously dependent on the validation state.
Now it doesn't need the validator to function, but can still optionally
create it and validate every instruction once it's decoded.

Avoid using global static variables

Previously we have several grammar tables defined as global static
variables and these grammar table entries contains non-POD struct
fields (CapabilitySet/ExtensionSet). The initialization of these
non-POD struct fields may require calling operator new. If used
as a library and the caller defines its own operator new, things
can screw up.

This pull request changes all global static variables into
function static variables, which is lazy evaluated in a thread
safe way as guaranteed by C++11.

Add SPIRV_SPIRV_COMPRESSION option to cmake

The option is off by default.
cmake -DSPIRV_BUILD_COMPRESSION=ON ..
enables the compression lib, executable, and test build.

Fixes https://github.com/KhronosGroup/SPIRV-Tools/issues/834

Merge pull request #829 from atgoo/fix_val_logicals

Validator: fix logicals pass for OpSelect pointers

Validator: fix logicals pass for OpSelect pointers

OpSelect works with pointers also when capability
VariablePointersStorageBuffer is declared (before worked only with
capability VariablePointers).

elim-multi-store: only patch loop header phis that we created

There can already be OpPhi instructions in a loop header that
are unrelated to the optimization.  We should not be patching those.

Fixes https://github.com/KhronosGroup/SPIRV-Tools/issues/826

Add validate logicals pass to the validator

New pass checks operands of all instructions listed under
3.32.15. Relational and Logical Instructions

Refactored validate_aritmetics.cpp

Improved error messages and readability.

Updated markv_autogen

- now includes a table of all descriptors with coding scheme
(improves performance by 5% by allowing to avoid creation of
move-to-front sequences which will never be used)
- increased the size of markv_autogen.inc, clang doesn't seem
to have the long compilation time problem now
(probably was inadvertently fixed by using Huffman codec
serialization)

ElimLocalMultiStore: Reset structured successors for each function

Add strength reduction; for now replace multiply by power of 2

Create a new optimization pass, strength reduction, which will replace
integer multiplication by a constant power of 2 with an equivalent bit
shift.  More changes could be added later.

- Does not duplicate constants

- Adds vector |Concat| utility function to a common test header.

ExtractInsert: Handle rudimentary CompositeConstruct and ConstantComposite

This optimizes a single index extract whose composite value terminates with a
CompositeConstruct (or ConstantComposite) by evaluating to the correct
component. This was needed for opaque legalization.

This highlights the need/opportunity to improve this optimization to deal
with more complex composite expressions including currently handled ops
plus Null ops and special vector composition. A TODO has been added.

Recognize SPV_AMD_shader_fragment_mask

Add new checks to validate arithmetics pass

New operations:
- OpDot
- OpVectorTimesScalar
- OpMatrixTimesScalar
- OpVectorTimesMatrix
- OpMatrixTimesVector
- OpMatrixTimesMatrix
- OpOuterProduct

Update CHANGES for OpModuleProcessed validation rule

validator: OpModuleProcessed allowed in layout section 7c

Recent spec fix from SPIR Working group:
  Allow OpModuleProcessed after debug names, but before any
  annotation instructions.

Update MARK-V to version 1.01

Includes:
- Multi-sequence move-to-front
- Coding by id descriptor
- Statistical coding of non-id words
- Joint coding of opcode and num_operands

Removed explicit form Huffman codec constructor
- The standard use case for it is to be constructed from initializer list.

Using serialization for Huffman codecs

spirv-as: Fail for unrecognized long option

Fixes https://github.com/KhronosGroup/SPIRV-Tools/issues/798

Inliner: Fix LoopMerge when inline into loop header of multi block loop

This adapts the fix for the single-block loop.  Split the loop like
before.  But when we move the OpLoopMerge back to the loop header,
redirect the continue target only when the original loop was a single
block loop.

Fixes https://github.com/KhronosGroup/SPIRV-Tools/issues/800

Add validation pass for arithmetic operations

The pass checks if arithmetic operations (such as OpFMul) receive
correct operands.

Make enums for all currently published extensions

Use the list from the SPIR-V registry page.  Also, capture it as
a string so it's much easier to update via copy-paste.

The validator will accept modules that declare these known
extensions.  However, we might not know about new tokens or
instructions declared in them.  For that we need grammar updates
applied to SPIRV-Headers.

Starge v2017.1-dev

Create v2017.0

Update README to describe that we understand SPIR-V syntax based on the
grammar files included from the SPIRV-Headers repo.

(Also, it's high time we issue a v2017 release!

Finalize v2016.7

Update CHANGES for recent inliner fixes

Fix mingw build (source/print.cpp)

source/print.cpp doesn't compile due to integer conversion.

Tested by @dneto0 on a Windows machine.

Inliner: Remap callee entry block id to single-trip loop header

Otherwise cloned phis can be invalid.

Fixes https://github.com/KhronosGroup/SPIRV-Tools/issues/790

Inline: Fix single-block loop caller cases

If the caller block is a single-block loop and inlining will
replace the caller block by several blocks, then:
- The original OpLoopMerge instruction will end up in the *last*
  such block.  That's the wrong place to put it.
- Move it back to the end of the first block.
- Update its Continue Target ID to point to the last block

We also have to take care of cases where the inlined code
begins with a structured header block.  In this case
we need to ensure the restored OpLoopMerge does not appear
in the same block as the merge instruction from the callee's
first block.

Fixes https://github.com/KhronosGroup/SPIRV-Tools/issues/787

BasicBlock: add ctail, GetMergeInst, GetLoopMergeInst

Update tests for new preferred name as ShaderViewportIndexLayerEXT

This reacts to a recent update to SPIRV-Headers

Update CHANGES for fix to 781

Extension allows multiple same OpTypePointer types

SPV_KHR_variable_pointers allows OpTypePointer to declare multiple
pointer identical types.

https://github.com/KhronosGroup/SPIRV-Tools/issues/781

Update CHANGES for fix to 776

DeadBranchElim: Fix dead block detection to ignore backedges

- DeadBranchElim: Make sure to mark orphan'd merge blocks and continue
targets as live.
- Add test with loop in dead branch
- Add test that orphan'd merge block is handled.

Fixes https://github.com/KhronosGroup/SPIRV-Tools/issues/776

InlineOpaque: Remove from usage until complete Opaque policy is designed.

Update changes for fix to issue 782

Inline: Fix remapping of non-label forward references in callee phi

Disassembler: Print colour codes only when writing to a terminal

Fix encode zero bits on word boundary bug

Bit stream writer was manifesting incorrect behaviour when the following
two conditions were met:
- writer was on 64-bit word boundary
- WriteBits was invoked with num_bits=0 (can happen when a Huffman codec has only one
value)

The bug was causing very rare sporadic corruption which was detected by
tests after a random experimental change in MARK-V model.

Show result id for CompositeInsert validation failure

README: Add reference to SPIR-V size reduction white paper

Windows: Increase intensity of blue text

Fix: background color was erroneously reset on Win32 platform.

Fix: background color was erroneously reset on Win32 platform.

Updated capabilites for SampleMask

SPIRV-Headers recently fixed the capability dependency
for SampleMask.  It depends on Shader, not SampleRateShading

Opt: Create InlineOpaquePass

Only inline calls to functions with opaque params or return

TODO: Handle parameter type or return type where the opqaue
type is buried within an array.

Opt: Have "size" passes process full entry point call tree.

Includes code to deal correctly with OpFunctionParameter. This
is needed by opaque propagation which may not exhaustively inline
entry point functions.

Adds ProcessEntryPointCallTree: a method to do work on the
functions in the entry point call trees in a deterministic order.

Support supplying extra definitions via CMAKE variable

Huffman codec can serialize to text

Refactored the Huffman codec implementation and added ability to
serialize to C++-like text format. This would reduce the time-complexity
if loading hard-coded codecs.

Opt: Add opaque tests

Add id descriptor feature to SPIR-V

Id descriptors are computed as a recursive hash of all instructions used
to define an id. Descriptors are invarint of actual id values and
the similar code in different files would produce the same descriptors.

Multiple ids can have the same descriptor. For example
%1 = OpConstant %u32 1
%2 = OpConstant %u32 1
would produce two ids with the same descriptor. But
%3 = OpConstant %s32 1
%4 = OpConstant %u32 2
would have descriptors different from %1 and %2.

Descriptors will be used as handles of move-to-front sequences in SPIR-V
compression.

ADCE: Add support for function calls

ADCE will now generate correct code in the presence of function calls.
This is needed for opaque type optimization needed by glslang. Currently
all function calls are marked as live. TODO: mark calls live only if they
write a non-local.

Update CHANGE to list fix for issue 755

Inliner: callee can have early return that isn't multi-return

Avoid generating an invalid OpLabel.
Create the continue target for the single-trip loop only if
you actually created the header for the single-trip loop.

Fixes https://github.com/KhronosGroup/SPIRV-Tools/issues/755

AccessChainConvert: Add HasOnlySupportedRefs()

This avoids conversion on variables which will not ultimately be optimized.
Also removed an obsolete restriction from FindTargetVars(). Also added
decorates to supported refs (eg. RelaxedPrecision). Also fixed name to
IsNonTypeDecorate().

Inline: Split out InlineExhaustivePass from InlinePass

Mem2Reg: Allow Image and Sampler types as base target types.

Update CHANGES with common uniform loads pass

Update README.md with new code-reduction passes

Add CommonUniformElim pass

- UniformElim: Only process reachable blocks

- UniformElim: Don't reuse loads of samplers and images across blocks.
  Added a second phase which only reuses loads within a block for samplers
  and images.

- UniformElim: Upgrade CopyObject skipping in GetPtr

- UniformElim: Add extensions whitelist
  Currently disallowing SPV_KHR_variable_pointers because it doesn't
  handle extended pointer forms.

- UniformElim: Do not process shaders with GroupDecorate

- UniformElim: Bail on shaders with non-32-bit ints.

- UniformElim: Document support for only single index and add TODO.

Add MemPass, move all shared functions to it.

Add multi-sequence move-to-front implementation

Add MultiMoveToFront class which supports multiple move-to-front
sequences and allows to promote value in all sequences at once.

Added caching for last accessed sequence handle and last accessed value
in each sequence.

Update CHANGES with recently added optimizations

Opt: Add new size-reduction passes to usage message.

Added C++ code generation to spirv-stats

The tool can now generate C++ code returning some of the historgrams and
Huffman codecs generated from those historgrams.

Add Appveyor config that uses VS 2017

Opt: Delete names and decorations of dead instructions

Opt: HasOnlySupportedRefs should consider OpCopyObject

This fixes test failure after merging the previous pull request.

Revert "Revert "Opt: LocalBlockElim: Add HasOnlySupportedRefs""

This reverts commit df96e243c633b939690a42d89904e04f50126e86.

Add extension whitelists to size-reduction passes.

Currently only SPV_KHR_variable_pointers is disallowed in passes which
do pointer analysis. Positive and negative tests of the general extensions
mechanism were added to aggressive_dce but cover all passes.

Revert "Opt: LocalBlockElim: Add HasOnlySupportedRefs"

This reverts commit 2d0f7fbc1151004c4cf111b947f1070a03dfe092.