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.

Opt: LocalBlockElim: Add HasOnlySupportedRefs

Verifies that targeted variables have only access chain and direct
loads and stores as references.

Fix handling of CopyObject in GetPtr and its call sites

Fix Visual Studio size_t cast compiler warning

Visual Studio was complaining about possible loss of data on 64-bit
builds, due to an implicit cast from size_t to int. This changes the
data to use an int with no cast.

LocalMultiStore: Always put varId for backedge on loop phi function.

And always patch the backedge operand when patching phi functions. This
approach is more correct and cleaner. The previous code was generating
incorrect phis when the backedge block had no predecessors.

DeadBranchElim: Improve algorithm to only remove blocks with no predecessors

Must be careful not to remove blocks pointed at by unreachable blocks

Minor code review feedback on AggressiveDCE

Add AggressiveDCEPass

Create aggressive dead code elimination pass
This pass eliminates unused code from functions. In addition,
it detects and eliminates code which may have spurious uses but which do
not contribute to the output of the function. The most common cause of
such code sequences is summations in loops whose result is no longer used
due to dead code elimination. This optimization has additional compile
time cost over standard dead code elimination.

This pass only processes entry point functions. It also only processes
shaders with logical addressing. It currently will not process functions
with function calls. It currently only supports the GLSL.std.450 extended
instruction set. It currently does not support any extensions.

This pass will be made more effective by first running passes that remove
dead control flow and inlines function calls.

This pass can be especially useful after running Local Access Chain
Conversion, which tends to cause cycles of dead code to be left after
Store/Load elimination passes are completed. These cycles cannot be
eliminated with standard dead code elimination.

Additionally: This transform uses a whitelist of instructions that it
knows do have side effects, (a.k.a. combinators).  It assumes other
instructions have side effects: it will not remove them, and assumes
they have side effects via their ID operands.

Add LocalMultiStoreElim pass

A SSA local variable load/store elimination pass.
For every entry point function, eliminate all loads and stores of function
scope variables only referenced with non-access-chain loads and stores.
Eliminate the variables as well.

The presence of access chain references and function calls can inhibit
the above optimization.

Only shader modules with logical addressing are currently processed.
Currently modules with any extensions enabled are not processed. This
is left for future work.

This pass is most effective if preceeded by Inlining and
LocalAccessChainConvert. LocalSingleStoreElim and LocalSingleBlockElim
will reduce the work that this pass has to do.

DeadBranchElim: Add DeadBranchElimPass

Include memory and semantics IDs when iterating over inbound IDs

Fixes Instruction::ForEachInId so it covers
SPV_OPERAND_TYPE_MEMORY_SEMANTICS_ID and SPV_OPERAND_TYPE_SCOPE_ID.
Future proof a bit by using the common spvIsIdType routine.

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

MARK-V decoder supports extended instructions

Update CHANGES to say we use GNUIntallDirs

Define variable to skip installation

If this is used as a static library in another project, this does not
need to be installed, and otherwise will just clutter the application's install.
To use, define SKIP_SPIRV_TOOLS_INSTALL which internally defines
ENABLE_SPIRV_TOOLS_INSTALL to control installation.

Also include GNUInstallDirs to get standard output 'lib' directory which is sometimes 'lib64' and not 'lib'

Convert pattern stack from deque to vector, and share it

Also move various vector::reserve calls to State ctor
Negligible perf benefit, but more tidy.

Added fixed width encoding to bit_stream

Fixed width encoding is intended to be used for small unsigned integers
when the upper bound is known both to the encoder and the decoder
(for example move-to-front rank).

Added compression tool tools/spirv-markv. Work in progress.

Command line application is located at tools/spirv-markv
API at include/spirv-tools/markv.h

At the moment only very basic compression is implemented, mostly varint.
Scope of supported SPIR-V opcodes is also limited.

Using a simple move-to-front implementation instead of encoding mapped
ids.

Work in progress:
- Does not cover all of SPIR-V
- Does not promise compatibility of compression/decompression across
  different versions of the code.

Added log(n) move-to-front implementation

The implementation is based on AVL and order statistic tree.

It accepts all kinds of values and the implementation
doesn't expect the behaviour to be consistent with id coding.

Intended by SPIR-V compression algorithms.

Added Huffman codec to utils

Attached ids to Huffman nodes for deterministic internal node
comparison.

Travis CI: stop requiring sudo and use make instead of ninja

This gives us shorter testing time since we can use the container
based testing environment, which starts faster. Also using make
means we don't need to install ninja separately.

Don't do hash lookup twice in FindDef

Move spv_instruction_t's into vector

No need to incur another copy here. These guys have embedded vectors
we'd rather not copy.

Reserve expected length of instructions vector

Move some temp vectors into parser state

We don't need to churn the allocations for these every instruction.

BlockMerge: Add BlockMergePass

Also, add BasicBlock::tail()

Update CHANGES

- Describe support for AMD extensions
- Describe recently added optimizer passes

Add support for SPV AMD extensions

mem2reg: Add InsertExtractElimPass

Transform multiple entry points

Don't stop just after one because of short-circuiting logical-or.

mem2reg: Add LocalSingleStoreElimPass

Eliminate function scope variables with one store, if possible.

mem2reg: Add pass to eliminate local loads and stores in single block.

Don't install googletest and googlemock

Mem2Reg: Add Local Access Chain Convert pass

- Supports OpAccessChain and OpInBoundsAccessChain
- Does not process modules with non-32-bit integer types.

Fix memory leak in ValidateBinaryUsingContextAndValidationState

Bots print output from timed out tests

Timeout set to 300 seconds. If no timeout, then ctest itself will be
timed out and terminated leaving no output.

Fixed misspelled ctest flag --output_on_failure

Support building on FreeBSD

CFA: Move TraversalRoots and ComputeAugmentedCFG into CFA

CFA: Pull in CalculateDominators

DefUseManager: Fix ReplaceAllUsesWith() to update inst_to_used_ids_

Added extension SPV_VALIDATOR_ignore_type_decl_unique

If extension is present in the module, validator will ignore the "type
declaration must be unique" rule.

Remove unused this in lambda capture

Add SPIR-V 1.2 support, for OpenCL 2.2

Fix size_t conversion error on MinGW

Update CHANGES: note fix of issue 629

Inline: Inline early return function if no returns in loop.

Added bit stream utils

Also added generalized zigzag coding.
- Due to signed integers being mostly non-negative, improved zigzag coding
  to favor positive values.

Stats analyzer aggregates OpConstant usage

Stats analyzer uses validator

Stats analyzer calls validator to check the instruction and update
validator state.

Fixed unit tests (validator was failing).

Avoid snprintf warning in GCC 7.1

Tries to fix https://github.com/KhronosGroup/SPIRV-Tools/issues/642
See also https://gcc.gnu.org/bugzilla/show_bug.cgi?id=80655

Inline: Create CFA class

Create class to encapsulate control flow analysis and share across
validator and optimizer. A WIP. Start with DepthFirstTraversal. Next
pull in CalculateDominators.

Update set_spec_const_default_value_test.cpp

Work around warning of dangling else

Added Markov chain analysis to stats

Added data structure to SpirvStats which is used to collect statistics
on opcodes following other opcodes.

Added a simple analysis print-out to spirv-stats.

Inline: Change "--inline-entry-points-all" to "-exhaustive"

Inline: Fix inliner description in usage message to reflect exceptions.

Inline: Do not inline functions with multiple returns (for now)

Add bit pattern interface for setting default value for spec constants

Update CHANGES with recent news

Added --compact-ids to /tools/opt

The pass remaps ids to a compact set which starts with %1 and
has no gaps.

Added option --preserve-numeric-ids to tools/spirv-as

Added options to tools::Assemble

Added statistical analysis tool (tool/stats)

Currently analyzes percentages of the following:
- version (how many 1.0 or 1.1)
- generator
- extension
- capability
- opcode prevalence

Test source language HLSL

Support SPV_KHR_storage_buffer_storage_class

Includes interaction with SPV_KHR_variable_pointers

TODO: Update capabilitly dependency tests for new capabilities.

Validator support for Variable Pointer extension.

If the variable_pointer extension is used:

* OpLoad's pointer argument may be the result of any of the following:
 * OpSelect
 * OpPhi
 * OpFunctionCall
 * OpPtrAccessChain
 * OpCopyObject
 * OpLoad
 * OpConstantNull

* Return value of a function may be a pointer.

* It is valid to use a pointer as the return value of a function.

* OpStore should allow a variable pointer argument.

Update cap tests for SPV_KHR_16bit_storage

Test asm,dis support for SPV_KHR_variable_pointers

Add FlattenDecoration transform

Add --flatten-decorations to spirv-opt

Flattens decoration groups.  That is, replace OpDecorationGroup
and its uses in OpGroupDecorate and OpGroupMemberDecorate with
ordinary OpDecorate and OpMemberDecorate instructions.

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

Group targets into folders

This plays nicer with IDEs.

Update spirv-opt to use spvtools::Optimizer

Exercises our public APIs more, and avoid including most
internal headers.  It also shortens the processing part
of the code, but does make adding passes look more complex.

Doing this exposed issue 611, a bug in spvtools::Optimizer.

Fix optimizer on when to write the binary

The spvtools::Optimizer::Run method should also write the output binary
if optimization succeeds without changes but the output binary vector
does not have exactly the same contents as the input binary.
We have to check both the base pointer of the storage and the size of
the vector

Added a test for this too.

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

Add /EHs for targets for MSVC

Fix spelling in SPV_AMD_gcn_shader support

Fix typo in method name Struct::AddMemberName

Also add a method comment for it.

Avoid inlining calls to external functions

External functions don't have bodies to inline anyway.
Fixes https://github.com/KhronosGroup/SPIRV-Tools/issues/605

opt::Function::cbegin and cend are const

Mention inliner in CHANGES

Add low priority test suggestions for inliner

Add exhaustive function call inlining to spirv-opt

Inlining is done for all functions designated as entry points.

Add optional validation to test fixture method SinglePassRunAndCheck.

Add various accessors needed to read and edit SPIRV code.

Support SPV_AMD_gcn_shader

Supported in assembler, disassembler, and binary parser.

The validator does not check SPV_AMD_gcn_shader validation rules
beyond parsing the extension.

Adds generic support for generating instruction tables for vendor
extensions.

Adds generic support for extensions the validator should recognize
(but not check) but which aren't derived from the SPIR-V core
grammar file.

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

Fix validator message for bad logical pointer

Affects OpLoad and OpStore validation.

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

Update capability tests for SPV_KHR_16bit_storage rev 7

The SPIR-V core grammar file in a recent SPIRV-Headers
applied the fix from Rev 7 of SPV_KHR_16bit_storage:
FPRoundingMode enums are now enabled by the capabilities
introduced by that extension.

Update the SPIRV-Tools tests accordingly.

Do nothing if trying to make the current dir

spirv-val prints warnings

Warnings and info messages go to stdout.
Errors still go to stderr.

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

Add SpirvTools::Validate that takes an options object

Add spvtools::ValidatorOptions RAII wrapper around
a spv_validator_options value.

Validator dissallows unsupported Vulkan capability

If environment is SPV_ENV_VULKAN_1_0, disallow OpCapability operands
which are not supported by Vulkan 1.0.

See https://github.com/KhronosGroup/SPIRV-Tools/issues/572

Autogenererating enum-string mappings from grammar

Autogenerating the following code:
- extension enum
- extension-to-string
- string-to-extension
- capability-to-string

Capability mapping table will not compile if incomplete.
TODO: Use "spirv-latest-version.h" instead of 1.1.

Added function to generate capability tables for tests.