Initial implementation of merge return pass.

Works with current DefUseManager infrastructure.

Added merge return to the standard opts.

Added validation to passes.

Disabled pass for shader capabilty.

Appveyor: skip building tags

Appveyor: Stop testing VS 2013/2015 Debug

VS2017 Debug tests should suffice for intresting Debug cases.
This will save us ~30min of waiting time for each build job.

Add analysis to compute mappings between instructions and basic blocks.

This analysis builds a map from instructions to the basic block that
contains them.  It is accessed via get_instr_block().  Once built, it is kept
up-to-date by the IRContext, as long as instructions are removed via
KillInst.

I have not yet marked passes that preserve this analysis. I will do it
in a separate change.

Other changes:

- Add documentation about analysis values requirement to be powers of 2.
- Force a re-build of the def-use manager in tests.
- Fix AllPreserveFirstOnlyAfterPassWithChange to use the
  DummyPassPreservesFirst pass.
- Fix sentinel value for IRContext::Analysis enum.

- Fix logic for checking if the instr<->block mapping is valid in KillInst.

Fix decorations of inlined functions.

Fixes issue #728.  Currently the inliner is not generating decorations for
inlined code which corresponds to function code which has decorations. An
example of decorations that are relevant: RelaxedPrecision, NoContraction.

The solution is to replicate the decoration during inlining.

Tests: Add optional dependency on Effcee stateful matcher

Add Effcee as an optional dependency for use in tests.  In future it will
be a required dependency.

Effcee is a stateful pattern matcher that has much of the functionality
of LLVM's FileCheck, except in library form.  Effcee makes it much easier
to write tests for optimization passes.

Demonstrate its use in a test for the strength-reduction pass.

Update README.md with example commands of how to get sources.

Update Appveyor and Travis-CI build rules.

Also: Include test libraries if not SPIRV_SKIP_TESTS
- SPIRV_SKIP_TESTS is implied by SPIRV_SKIP_EXECUTABLES

Have all MemPasses preserve the def-use manager.

Originally the passes that extended from MemPass were those that are
of the def-use manager.  I am assuming they would be able to preserve
it because of that.

Added a check to verify consistency of the IRContext. The IRContext
relies on the pass to tell it if something is invalidated.
It is possible that the pass lied.  To help identify those situations,
we will check if the valid analyses are correct after each pass.

This will be enabled by default for the debug build, and disabled in the
production build.  It can be disabled in the debug build by adding
"-DSPIRV_CHECK_CONTEXT=OFF" to the cmake command.

Travis: auto deploy build artifacts to GitHub Releases

Pushing a commit to the master branch will trigger a build on
Travis. If the build is successful, the artifacts will be
collected and pushed to GitHub Releases, under the "master-tot"
release.

Appveyor: auto deploy build artifacts to GitHub Releases

Pushing a commit to the master branch will trigger a build on
Appveyor. If the build is successful, the artifacts will be
collected and pushed to GitHub Releases, under the "master-tot"
release.

Re-format files in source, source/opt, source/util, source/val and tools.

NFC. This just makes sure every file is formatted following the
formatting definition in .clang-format.

Re-formatted with:

$ clang-format -i $(find source tools include -name '*.cpp')
$ clang-format -i $(find source tools include -name '*.h')

Add the IRContext (part 2): Add def-use manager

This change will move the instances of the def-use manager to the
IRContext.  This allows it to persists across optimization, and does
not have to be rebuilt multiple times.

Added test to ensure that the IRContext is validating and invalidating
the analyses correctly.

Opt: Fix HasLoads to not report decoration as load.

Opt: Remove CommonUniformElimination from -O and -Os (for now)

It is causing crashes for some drivers. Will try to re-enable it once
existing drivers are able to deal better with it.

Describe public_spirv_tools_dev@khronos.org mailing list

Validate storage class of target pointer for OpStore

Move class CFG from namespace opt to namespace ir.

It makes more sense to have the CFG inside the ir name space, as it is
descriptive of the representation.

Add a new class opt::CFG to represent the CFG for the module.

This class moves some of the CFG-related functionality into a new
class opt::CFG.  There is some other code related to the CFG in the
inliner and in opt::LocalSingleStoreElimPass that should also be moved,
but that require more changes than this pure restructuring.

I will move those bits in a follow-up PR.

Currently, the CFG is computed every time a pass is instantiated, but
this should be later moved to the new IRContext class that @s-perron is
working on.

Other re-factoring:

- Add BasicBlock::ContinueBlockIdIfAny. Re-factored out of MergeBlockIdIfAny
- Rewrite IsLoopHeader in terms of GetLoopMergeInst.
- Run clang-format on some files.

Add the IRContext (part 1)

This is the first part of adding the IRContext.  This class is meant to
hold the extra data that is build on top of the module that it
owns.

The first part will simply create the IRContext class and get it passed
to the passes in place of the module.  For now it does not have any
functionality of its own, but it acts more as a wrapper for the module.

The functions that I added to the IRContext are those that either
traverse the headers or add to them.  I did this because we may decide
to have other ways of dealing with these sections (for example adding a
type pool, or use the decoration manager).

I also added the function that add to the header because the IRContext
needs to know when an instruction is added to update other data
structures appropriately.

Note that there is still lots of work that needs to be done.  There are
still many places that change the module, and do not inform the context.
That will be the next step.

Add validation for OpBranchConditional

Lowered initial capacity of move-to-front sequence

Also fixed outdated comments.

Fix copyright check when the build directory is in the source directory.

The IDE I am using places the cmake build directory inside the source
directory.  When that happens the copyright check fails because the
build process creates a file CMakeCXXCompilerId.cpp.  That file does
not have the copyright information, so the test fails.

I want this file to be ignored, so I added its directory, CompilerIdCXX,
to the list of directories to be ignored.

ADCE: Dead if elimination

Mark structured conditional branches live only if one or more instructions
in their associated construct is marked live. After closure, replace dead
structured conditional branches with a branch to its merge and remove
dead blocks.

ADCE: Dead If Elim: Remove duplicate StructuredOrder code

Also generalize ComputeStructuredOrder so that the caller can specify the
root block for the order. Phi insertion uses pseudo_entry_block and adce and
dead branch elim use the first block of the function.

ADCE: Dead If Elim: Pull redundant code out of InsertPhiInstructions

ADCE: Dead If Elim: Encapsulate CFG Cleanup Initialization

ADCE: Dead If Elim: Remove redundant code from ADCE initialization

ADCE: Dead If: Use CFGCleanup to eliminate newly dead blocks

Moved bulk of CFG Cleanup code into MemPass.

More re-factoring to simplify pass initialization.

This implements two cleanups suggested by @s-perron
(https://github.com/KhronosGroup/SPIRV-Tools/pull/921):

- Move FindNamedOrDecoratedIds() into MemPass::InitializeProcessing().
- Remove FinalizeNextId(). Always call SetIdBound() from
  Pass::TakeNextId().

Add option to relax validation of store types.

There are a number of users of spriv-opt that are hitting errors
because of stores with different types.  In general, this is wrong, but,
in these cases, the types are the exact same except for decorations.

The options is "--relax-store-struct", and it can be used with the
validator or the optimizer.

We assume that if layout information is missing it is consistent.  For
example if one struct has a offset of one of its members, and the other
one does not, we will still consider them as being layout compatible.
The problem will be if both struct has and offset decoration for
corresponding members, and the offset are different.

Compression: removed 'presumed index' feature

The feature used to improve compression of const integers which were
presumed to be indices. Now obsolete as descriptor-based compression
does this in a more generalized way.

Use std::lower_bound for opcode lookup

Use std::lower_bound for opcode-to-string

Stable sort the generated instruction table.

Re-factor Phi insertion code out of LocalMultiStoreElimPass

Including a re-factor of common behaviour into class Pass:

The following functions are now in class Pass:

- IsLoopHeader.
- ComputeStructuredOrder
- ComputeStructuredSuccessors (annoyingly, I could not re-factor all
  instances of this function, the copy in common_uniform_elim_pass.cpp
  is slightly different and fails with the common implementation).
- GetPointeeTypeId
- TakeNextId
- FinalizeNextId
- MergeBlockIdIfAny

This is a NFC (non-functional change)

Change the sections in the module to use the InstructionList class.

This change will replace a number of the
std::vector<std::unique_ptr<Instruction>> member of the module to
InstructionList.  This is for consistency and to make it easier to
delete instructions that are no longer needed.

Turn all function static non-POD variables into global POD variables

Function static non-POD data causes problems with DLL lifetime.
This pull request turns all static info tables into strict POD
tables. Specifically, the capabilities/extensions field of
opcode/operand/extended-instruction table are turned into two
fields, one for the count and the other a pointer to an array of
capabilities/extensions. CapabilitySet/EnumSet are not used in
the static table anymore, but they are still used for checking
inclusion by constructing on the fly, which should be cheap for
the majority cases.

Also moves all these tables into the global namespace to avoid
C++11 function static thread-safe initialization overhead.

Validate SpvOpVectorShuffle

restrict opcodes targeting OpDecorationGroup

Fixed --eliminate-common-uniform so that it does not eliminate loads of volatile variables.

Optimizer: Line and NoLine are not debug1 or debug2

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

Refactored compression debugger

Markv codec now receives two optional callbacks:
LogConsumer for internal codec logging
DebugConsumer for testing if encoding->decoding produces the original
results.

Run dead variable elimination when using -O and -Os

We want to run the optimization when using -O and -Os, but it was not
added at part of https://github.com/KhronosGroup/SPIRV-Tools/pull/905.
This change will add that a well as some minor formatting changes
requested in that same pull request.

DeadBranchElim: Fix dead block elimination

The previous algorithm would leave invalid code in the case of unreachable
blocks pointing into a dead branch. It would leave the unreachable blocks
branching to labels that no longer exist. The previous algorithm also left
unreachable blocks in some cases (a loop following an orphaned merge block).
This fix also addresses that.

This code will soon be replaced with the coming CFG cleanup.

Add pass to remove dead variables at the module level.

There does not seem to be any pass that remove global variables.  I
think we could use one.  This pass will look specifically for global
variables that are not referenced and are not exported.  Any decoration
associated with the variable will also be removed.  However, this could
cause types or constants to become unreferenced.  They will not be
removed.  Another pass will have to be called to remove those.

Optimizer: OpModuleProcessed is in its own layout section

This is a recent decision from the SPIR WG.  The spec update
has not yet been published.
Khronos SPIR-V internal issue 199

Add Android.mk build to Travis CI

Added NDK_LIBS_OUT

Added dummy android test application

The application is needed to test Android.mk build.

Fix cfg_cleanup.cpp.  My bad.

Remove coding redundancy in cfg_cleanup_pass.cpp

Add instruction_list to Android.mk

Add validation pass for conversion instructions

The pass checks correctness of operands of instruction in opcode range
OpConvertFToU - OpBitset.

Disabled invalid tests

Disabled UConvert validation until Vulkan CTS can catch up.

Add validate_conversion to Android.mk

Also remove duplicate entry in CMakeLists.txt.

Change BasicBlock to use InstructionList to hold instructions.

This is the first step in replacing the std::vector of Instruction
pointers to using and intrusive linked list.

To this end, we created the InstructionList class.  It inherites from
the IntrusiveList class, but add the extra concept of ownership.  An
InstructionList owns the instruction that are in it.  This is to be
consistent with the current ownership rules where the vector owns the
instruction that are in it.

The other larger change is that the inst_ member of the BasicBlock class
was changed to using the InstructionList class.

Added test for the InsertBefore functions, and making sure that the
InstructionList destructor will delete the elements that it contains.

I've also add extra comments to explain ownership a little better.

Removed todos from validate_id.cpp

Removed todos for validation of opcodes handles in other passes.

DeadBranchElim: Slightly more defensive coding

The reviewed cfg_cleanup optimize pass

CFG cleanup pass - Remove unreachable blocks.

- Adds a new pass CFGCleanupPass.  This serves as an umbrella pass to
  remove unnecessary cruft from a CFG.
- Currently, the only cleanup operation done is the removal of
  unreachable basic blocks.
- Adds unit tests.
- Adds a flag to spirvopt to execute the pass (--cfg-cleanup).

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.