Fix comment in primitives validation

Also refactor type query for efficiency.

Image Operand Sample allows sparse image opcodes

@ehsannas had filed an issue against SPIR-V spec, concerning
Image Operands section (3.14):
Sample
A following operand is the sample number of the sample to use. Only
valid with OpImageFetch, OpImageRead, and OpImageWrite.

Relaxing the check to allow OpImageSparseRead and
OpImageSparseFetch to fix failing tests.

Export a config file for pkg-config

Fixes #1031

Extracts the current version from the file CHANGES

The -dev suffix maps to a minor version number of .0
No -dev suffix maps to a minor version number of .1

Uses a first class target spirv-tools-pkg-config

Remove concept of FIRST_CONCRETE_* operand types

Improving the usability of the type manager. The type manager hashes
types. This allows the lookup of type declaration ids from arbitrarily
constructed types. Users should be cautious when dealing with non-unique
types (structs and potentially pointers) to get the exact id if
necessary.

* Changed the spec composite constant folder to handle ambiguous composites
* Added functionality to create necessary instructions for a type
* Added ability to remove ids from the type manager

Start v2017.3-dev

Finalize v2017.2

ADCE: Only mark true breaks and continues of live loops

This fixes issue #1075

- Mark continue when conditional branch with merge block.
  Only mark if merge block is not continue block.

- Handle conditional branch break with preceding merge

Add primitive instruction validation pass

Refactor include of latest spir-v header versions

Add validation rules for atomic instructions

Validates all OpAtomicXXX instructions.

Fix uninitialized warning at -Os.

ADCE: Empty Loop Elimination

This entirely eliminates loops which do not contain live code.

Set the parent for basic blocks during inlining.

Inlining is not setting the parent (function) for each basic block.
This can cause problems for later optimizations.  The solution is to set
the parent for each new block just before it is linked into the
function.

Appveyor: stop testing on VS 2013

re2 requires VS2015 or later since:

https://github.com/google/re2/commit/97957299d1c9f7617cfe653f344536d733582d9e

Add validator checks for sparse image opcodes

Support OpenCL 1.2 and 2.0 target environments

include: Add target environment enums for OpenCL 1.2 and 2.0

Validator: Validate OpenCL capabilities

Update validate capabilities to handle embedded profiles

Add test for OpenCL capabilities validation

Update messages to mention the OpenCL profile used

Re-format val_capability_test.cpp

AppVeyor: Put VS 2017 first

VS 2017 is the newest compiler, with the most interesting feedback.
Place it first so we get its feedback first.

Force gtest to expose ::testing::Combine

Work around faulty logic in googletest, where ::testing::Combine
is accidentally disabled for VS 2017.
See https://github.com/google/googletest/issues/1352

Reenable OpCopyObject validation rules

Vulkan CTS fix has been submitted.

Add scalar replacement

Adds a scalar replacement pass. The pass considers all function scope
variables of composite type. If there are accesses to individual
elements (and it is legal) the pass replaces the variable with a
variable for each composite element and updates all the uses.

Added the pass to -O
Added NumUses and NumUsers to DefUseManager
Added some helper methods for the inst to block mapping in context
Added some helper methods for specific constant types

No longer generate duplicate pointer types.

* Now searches for an existing pointer of the appropriate type instead
of failing validation
* Fixed spec constant extracts
* Addressed changes for review
* Changed RunSinglePassAndMatch to be able to run validation
 * current users do not enable it

Added handling of acceptable decorations.

* Decorations are also transfered where appropriate

Refactored extension checking into FeatureManager

* Context now owns a feature manager
 * consciously NOT an analysis
 * added some test
* fixed some minor issues related to decorates
* added some decorate related tests for scalar replacement

MultiStore: Support OpVariable Initialization

Treat an OpVariable with initialization as if it was an OpStore.
With PR #1073, this completes work for issue #1017.

Add external/SPIRV-Headers to .gitignore

b93c066b allowed for both SPIRV-Headers and spirv-headers as valid
paths, but only the latter is being ignored by Git.

SingleStore: Support OpVariable Initialization

Treat an OpVariable with initialization as if it was an OpStore.
This fixes issue #1017.

Add option to spirv-opt to skip the validator.

The option --skip-validation is added.  When used it will skip the
validation step.

Also rearranged the help text to fix two options that are out of order.

Add a new constant manager class.

This patch adds a new constant manager class to interface with
analysis::Constant.  The new constant manager lives in ir::IRContext
together with the type manager (analysis::TypeManager).

The new analysis::ConstantManager is used by the spec constant folder
and the constant propagator (in progress).

Another cleanup introduced by this patch removes the ID management from
the fold spec constant pass, and ir::IRContext and moves it to
ir::Module. SSA IDs were maintained by IRContext and Module.  That's
pointless and leads to mismatch IDs. Fixed by moving all the bookkeeping
to ir::Module.

Add global redundancy elimination

Adds a pass that looks for redundant instruction in a function, and
removes them.  The algorithm is a hash table based value numbering
algorithm that traverses the dominator tree.

This pass removes completely redundant instructions, not partially
redundant ones.

Kill names and decoration in inlining.

Currently when inlining a call, the name and decorations for the result of the
call is not deleted.  This should be changed.  Added a test for this as well.

This fixes issue #622.

Add depth first iterator for trees

 - Add generic depth first iterator
 - Update the dominator tree to use this iterator instead of "randomly"
   iterate over the nodes

Revert extraneous changes from commit 8ec62deb2.

Commit 8ec62deb2 merged the code from PR #810, but it also re-introduces
code that had been removed in #885.

This patch removes the (now superfluous code).

Dominator Tree Analysis (#3)

Support for dominator and post dominator analysis on ir::Functions. This patch contains a DominatorTree class for building the tree and DominatorAnalysis and DominatorAnalysisPass classes for interfacing and caching the built trees.

Sort flags in help message - NFC.

It's slightly easier to read flags from --help if they're sorted.

CMake: allow both SPIRV-Headers and spirv-headers

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

Add composite instruction validation pass

Validates instructions in the opcode range from OpVectorExtractDynamic
to OpTranspose.

Do not zip and deploy for check formatting

Go back to root directory

Travis CI: add clang-format check

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

Update .appveyor.yml

Fix some of the known issues in image validation

Applied some of the spec clarifications made in conversation with
@johnkslang.

DCEInst kill the same instruction twice.

In DCEInst, it is possible that the same instruction ends up in the
queue multiple times, if the same id is used multiple times in the
same instruction.

The solution is to keep the ids in a set, to ensure no duplication in
the list.

Change Release builds to Release with debug info on Linux

For Linux builds, we want to add debug information on the generated binary (for timing and profiling purposes).  This patch changes Release builds to RelWithDebInfo.

Remove cfg_ field from SSAPropagator class - NFC.

When I moved the CFG into IRContext
(https://github.com/KhronosGroup/SPIRV-Tools/pull/1019), I forgot to
update SSAPropagator to stop requiring one.

Fixed with this patch.

Change IRContext::KillInst to delete instructions.

The current method of removing an instruction is to call ToNop.  The
problem with this is that it leaves around an instruction that later
passes will look at.  We should just delete the instruction.

In MemPass there is a utility routine called DCEInst.  It can delete
essentially any instruction, which can invalidate pointers now that they
are actually deleted.  The interface was changed to add a call back that
can be used to update any local data structures that contain
ir::Intruction*.

Compute value number when the value table is constructed.

Computing the value numbers on demand, as we do now, can lead to
different results depending on the order in which the users asks for
the value numbers.  To make things more stable, we compute them ahead
of time.

Fixed typo that leaked to the binary

The typo was found by lintian when I was packaging glslang

Add simplified instructions for pushing a reviewed PR.

Travis: mark MacOS builds as optional

MacOS support in Travis is flakey right now. MacOS build jobs
take a long time to start.

We have extensive checks for Linux and Windows, which should give
us confidence.

Re-format CONTRIBUTING.md - NFC.

I'm about to change this file.  I re-formatted it for easier editing.

Fix Dref type check in validator

Dref should be of 32-bit scalar floating type.

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

Appveyor: use ninja instead of MSBuild

Opt: Remove unused lambda captures

Those are reported as errors by clang 5.0.0, due to the flags -Werror
and -Wunused-lambda-capture.

Support outputting ANSI color escape sequences in library

Previously we required _PRINT to enable _COLOR, which forbids
outputting colored disassembly into a string in library.

This commit will allow library users to request enabling
ANSI color escape sequences.

Erase decorations removed from internal collections

Fixes Android arm-64-v8a build with NDK r14.  That's because
we no longer ignore the result of the std::remove.

Fix validation of group ops in SPV_AMD_shader_ballot

This needs custom code since the rules from the extension
are not encoded in the grammar.

Changes are:
- The new group instructions don't require Group capability
  when the extension is declared.
- The Reduce, InclusiveScan, ExclusiveScan normally require the Kernel
  capability, but don't when the extension is declared.

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

Fix #1034 - Give Edge::operator<() weak ordering semantics.

This should fix #1034.  It changes the predicate on operator< to use
label IDs from each block and compares them as std:pair to define a weak
ordering for std::set.

Validate OpTypeImage and OpTypeSampleImage

Added new validation rules to the validate image pass.

Linker: Fix incorrect exit status.

Create CONTRIBUTING.md

This is intended to be a document that people who want to help the project
can get a quick overview of how things are done.  Please comment and suggest
any changes.

AggressiveDCE: Add merge and continue branches for live loop.

This ensures that an if-break is not eliminated from a loop.

This fixes issue #989

Update README about the automatic master-tot relase

Convert the CFG to an on-demand analysis - NFC.

This fixes some TODOs by moving the CFG into the IRContext as an
analysis.

Fix windows build. unsigned vs signed comparison in EXPECT_EQ.

Generic value propagation engine.

This class implements a generic value propagation algorithm based on the
conditional constant propagation algorithm proposed in

     Constant propagation with conditional branches,
     Wegman and Zadeck, ACM TOPLAS 13(2):181-210.

The implementation is based on

     A Propagation Engine for GCC
     Diego Novillo, GCC Summit 2005
     http://ols.fedoraproject.org/GCC/Reprints-2005/novillo-Reprint.pdf

The purpose of this implementation is to act as a common framework for any
transformation that needs to propagate values from statements producing new
values to statements using those values.

Fix windows build.

This fixes the lack of uint32_t definition in source/val/decoration.h.

Re-format source tree - NFC.

Re-formatted the source tree with the command:

$ /usr/bin/clang-format -style=file -i \
    $(find include source tools test utils -name '*.cpp' -or -name '*.h')

This required a fix to source/val/decoration.h.  It was not including
spirv.h, which broke builds when the #include headers were re-ordered by
clang-format.

Derivative opcodes require Fragment exec model

Added validator check that all derivative opcodes require Fragment
execution model.

Relaxed OpImageWrite texel type check

Update CHANGES to mention fixes for 1007 and 1009

Relaxed OpImageRead validation rules

Removed the check that result type of OpImageRead should be a vector4.
Will reenable/adapt once the spec is clarified on what the right
dimension should be.

Notify the context of instructions that are being erased.

Fixes use-after-free error in RemoveDuplicatesPass

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

Add validation checks for Execution Model

Currently checks that these instructions are called from entry points
with Fragment execution model.
OpImageImplicit*
OpImageQueryLod
OpKill

Test for pollution of the global namespace

Works on Linux only for now.  That's a good start.

Move ValidateBinaryUsingContextAndValidationState into anonymous
namespace in source/validate.cpp.

Remove derivative instructions from the list of combinators.

These instructions compute their value based the value of the immediate
neighbours of the current fragment.  This means the result is not
defined purely by the operands of the instruction.

Start v2017.2-dev

Finalize 2017.1

Updated CHANGES to cover main updates since 2017.0

Add RegisterLegalizationPasses() into the interface

Add note to mention the use scenario.  The original list came
from Glslang.

Adding new def -> use mapping container

Replaced representation of uses

* Changed uses from unordered_map<uint32_t, UseList> to
set<pairInstruction*, Instruction*>>
* Replaced GetUses with ForEachUser and ForEachUse functions
* updated passes to use new functions
* partially updated tests
* lots of cleanup still todo

Adding an unique id to Instruction generated by IRContext

Each instruction is given an unique id that can be used for ordering
purposes. The ids are generated via the IRContext.

Major changes:
* Instructions now contain a uint32_t for unique id and a cached context
pointer
 * Most constructors have been modified to take a context as input
 * unfortunately I cannot remove the default and copy constructors, but
 developers should avoid these
* Added accessors to parents of basic block and function
* Removed the copy constructors for BasicBlock and Function and replaced
them with Clone functions
* Reworked BuildModule to return an IRContext owning the built module
 * Since all instructions require a context, the context now becomes the
basic unit for IR
* Added a constructor to context to create an owned module internally
* Replaced uses of Instruction's copy constructor with Clone whereever I
found them
* Reworked the linker functionality to perform clones into a different
context instead of moves
* Updated many tests to be consistent with the above changes
 * Still need to add new tests to cover added functionality
* Added comparison operators to Instruction

Adding tests for Instruction, IRContext and IR loading

Fixed some header comments for BuildModule

Fixes to get tests passing again

* Reordered two linker steps to avoid use/def problems
* Fixed def/use manager uses in merge return pass
* Added early return for GetAnnotations
* Changed uses of Instruction::ToNop in passes to IRContext::KillInst

Simplifying the uses for some contexts in passes

Allow derived access chain without uses in access chain conversion

Add derivatives validation pass

Checks operands of instructions in opcode range from OpDPdx to
OpFwidthCoarse.

Move SetContextMessageConsumer into libspirv namespace

Avoid polluting the global namespace.

Create a local value numbering pass

Creates a pass that removes redundant instructions within the same basic
block.  This will be implemented using a hash based value numbering
algorithm.

Added a number of functions that check for the Vulkan descriptor types.
These are used to determine if we are variables are read-only or not.

Implemented a function to check if loads and variables are read-only.
Implemented kernel specific and shader specific versions.

A big change is that the Combinator analysis in ADCE is factored out
into the IRContext as an analysis. This was done because it is being
reused in the value number table.

Validator pass for image instructions

Includes validation rules for OpImageXXX and ImageOperand.

Doesn't include OpTypeImage and OpImageSparseXXX.

Disabled an invalid test.

Optimize loads/stores on nested structs

Also fix LocalAccessChainConvert test: nested structs now convert

Add InsertExtractElim test for nested struct

Fix move semantics in iterator make_range

Add new compression algorithm and models

Add new "short descriptor" algorithm to MARK-V codec.

Add three shader compression models:
lite - fast, poor compression
mid - balanced
max - best compression

Adding an unique id to Instruction generated by IRContext

Each instruction is given an unique id that can be used for ordering
purposes. The ids are generated via the IRContext.

Major changes:
* Instructions now contain a uint32_t for unique id and a cached context
pointer
 * Most constructors have been modified to take a context as input
 * unfortunately I cannot remove the default and copy constructors, but
 developers should avoid these
* Added accessors to parents of basic block and function
* Removed the copy constructors for BasicBlock and Function and replaced
them with Clone functions
* Reworked BuildModule to return an IRContext owning the built module
 * Since all instructions require a context, the context now becomes the
basic unit for IR
* Added a constructor to context to create an owned module internally
* Replaced uses of Instruction's copy constructor with Clone whereever I
found them
* Reworked the linker functionality to perform clones into a different
context instead of moves
* Updated many tests to be consistent with the above changes
 * Still need to add new tests to cover added functionality
* Added comparison operators to Instruction
* Added an internal option to LinkerOptions to verify merged ids are
unique
* Added a test for the linker to verify merged ids are unique

* Updated MergeReturnPass to supply a context
* Updated DecorationManager to supply a context for cloned decorations

* Reworked several portions of the def use tests in anticipation of next
set of changes

Add dead function elimination to -O and -Os

This pass is very useful in reducing the size of the code, and reducing
the amount of work done by other optimizations.

Fix hard-coded header path

If SPIRV-Tools is used as an external project and have
googletest being kept in the same directory as it, we
won't have gmock-matchers.h in external/. This will
result in a compilation error.

Use gmock.h instead.

Git should ignore external repos

Ignore googletest, spirv-headers, effcee, and re2

Add the decoration manager to the IRContext.

To make the decoration manger available everywhere, and to reduce the
number of times it needs to be build, I add one the IRContext.

As the same time, I move code that modifies decoration instruction into
the IRContext from mempass and the decoration manager.  This will make
it easier to keep everything up to date.

This should take care of issue #928.

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')