Check definitions appear in dominator of use

Also address use and def of ID in same instruction

Refactor IDs definition and use tracking

* Creates an ID class which manages definition and use of IDs
* Moved tracking code from validate.cpp to validate_id.cpp
* Rename and combine SsaPass and ProcessIds into IdPass
* Remove module dependency in Function

Fixes segfault for loops without back-edges

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

Start v2016.2.

Finalize v2016.1.

Disassembling: map IDs to friendly names.

Add a FriendlyNameMapper to deduce friendly names for IDs based on
OpName, type structure, etc.

Track changes in SPIRV-Headers for SPIR-V 1.1 rev 2.

* The `Input` StorageClass doesn't require the `Shader` capability
  anymore.
* The `Sampled1D` and `SampledBuffer` capabilities don't require
  the `Shader` capability anymore. So they do not indirectly
  depend on the `Matrix` capability. So are the `Image1D` and
  `ImageBuffer` capabilities, which depend on `Sampled1D` and
  `SampledBuffer`.

A new GLSL grammar file is uploaded for SPIR-V 1.1, but it's the
same as the existing one for SPIR-V 1.0.

Now tracking commit 3814effb879ab5a98a7b9288a4b4c7849d2bc8ac in
SPIRV-Headers.

Turn off ClipDistance CullDistance cap checks for Vulkan

Turn them off until resolution of the debate over how they should be checked.
Fixes https://github.com/KhronosGroup/SPIRV-Tools/issues/261

Mention the steps to pull dependencies when building in README.

Test v1.1 loop dependency support

For DependencyInfinite and DependencyLength, test
that they don't require a capability to be turned on.
Also, that they are assembled, binary parsed, and disassembled
correctly.

Start v2016.1-dev

Finalize v2016.0

DRY file writing code in tools.

DRY file reading code in tools.

Rework CMake configuration for tools.

Add the spirv-opt command line tool.

Add Pass, PassManager, and StripDebugInfoPass.

Avoid capability checks on ID values. They are not literals

Works around issue 248 by weakening the test:
https://github.com/KhronosGroup/SPIRV-Tools/issues/248

The validator should try to track (32-bit) constant values, and then
for capability checks on IDs, check the referenced value, not the
raw ID number.

Add tests for the cpp interface.

Promote ir namespace and create draft libspirv.{h|c}pp.

Add IrBuilder for constructing SPIR-V in-memory representation.

Add an option to spvBinaryToText() to ignore header output.

Fix several violations of the style guide

Add classes for representing SPIR-V language constructs in memory.

Travis CI: bump OS X and XCode version.

Use pseudo entry and pseudo exit blocks for dominance.

For dominance calculations we use an "augmented" CFG
where we always add a pseudo-entry node that is the predecessor
in the augmented CFG to any nodes that have no predecessors in the
regular CFG.  Similarly, we add a pseudo-exit node that is the
predecessor in the augmented CFG that is a successor to any
node that has no successors in the regular CFG.

Pseudo entry and exit blocks live in the Function object.

Fixes a subtle problem where we were implicitly creating
the block_details for the pseudo-exit node since it didn't
appear in the idoms map, and yet we referenced it.  In such a case the
contents of the block details could be garbage, or zero-initialized.
That sometimes caused incorrect calculation of immediate dominators
and post-dominators.  For example, on a debug build where the details
could be zero-initialized, the dominator of an unreachable block would
be given as the pseudo-exit node.  Bizarre.

Also, enforce the rule that you must have an OpFunctionEnd to close off
the last function.

Use arguments for add_spvtools_unittest.

Appveyor: Pull SPIRV-Headers for building and update README link.

Validator structured flow checks: back-edge, constructs

Skip structured control flow chekcs for non-shader capability.

Fix infinite loop in dominator algorithm when there's an
unreachable block.

Ignore Vim swap files.

Fix ExtInst parsing: no IdRef* at end

The operands following the extended instruction literal
number are determined by the extended instruction itself.
So drop the zero-or-more IdRef pattern at the end of OpExtInst.

It's arguable whether this should actually be a grammar fix.  I've
chosen to patch this in SPIRV-Tools instead of in the grammar file.

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

Also fix two test cases for OpenCL extended instructions.  These
errors of supplying too many operands are now detected.

Fix OpenCL pow and pown arguments

Spec fix appeared in SPIR-V 1.0 Rev 2:
https://www.khronos.org/registry/spir-v/specs/1.0/OpenCL.ExtendedInstructionSet.100.html#_changes_from_version_1_0_revision_1

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

In physical addressing, functions can return pointers

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

Use SPIR-V headers from the KhronosGroup/SPIRV-Headers repo.

std::function needs <functional>. Fixes Android build

Avoid copy of work list argument: make it const ref

Refactor depth first traversal to be more generic

Refactor the way the post order vector is created. This new method
will allow for the extraction of backedges and create the post order
vector in one pass.

Fix diagnostic message for layout errors

Split validate_types file into multiple classes

Creates separate files for the ValidationState, Function and
BasicBlock classes.

Remove redundant in_block function from Function

Same test can be done through the get_current_block function

Avoid accessing invalid iterator.

Additional CFG tests

* Empty function
* Single block loops
* Nested loops
* Nested selection

Fix CHANGES file version parsing. -dev is optional

Make googletest regexes portable.

On Windows, test::MatchesRegex() doesn't support brackets.  On Linux, \d
doesn't work. :(

Control Flow Graph Validation

Create a function for adding unittests in CMake.

Also remove unnecessary main() function for unittests.

Travis CI: Use ctest to run all the tests.

Add Appveyor configuration for Windows build.

Test ABGR in both 1.0 and 1.1.

Remove needless include dir for spirv-dis.

Test ABGR image channel order.

Update include/spirv/spirv.h from SPIRV-Headers.

Test OpModuleProcessed.

Remove done TODOs in OpNameTest.

Simplify the instantiation by using Values() instead of ValuesIn().

Run clang-format.

Test SpecId validation.

Add --target-env.

commit 7648187c344cfc7847607acb2a6fa5606a3d10c1
Author: Dejan Mircevski <deki@google.com>
Date:   Thu Apr 21 15:44:07 2016 -0400

    Turn --vulkan into --target-env.

Add tests for MaxByteOffset.

Add PipeStorage tests.

Fix several warnings exposed in MSVS 2015.

diagnostic.cpp:
- unreachable code

operand.cpp
- conversion between int and uint32_t
- unreachable code

hex_float.h:
- conversion from 'const int' to 'unsigned int'
- unreachable code

validate_id.cpp
- forcing value to bool 'true' or 'false'

validate_types.cpp:
- forcing value to bool 'true' or 'false'

bitcast fixes

 * ValidationState_t and idUsage now store the addressing model and memory model of the SPIR-V module (this is necessary for certain instructions that need different checks depending on if the logical or physical addressing model is used)
 * removed SpvOpPtrAccessChain and SpvOpInBoundsPtrAccessChain from spvOpcodeIsPointer again as these are disallowed in logical addressing mode and only allowed in physical addressing mode (which doesn't use/need spvOpcodeIsPointer in the first place)
 * added SpvOpImageTexelPointer and SpvOpCopyObject to spvOpcodeIsPointer
 * OpLoad/OpStore now only check if the used pointer operand originated from a valid pointer producing opcode in logical addressing mode (as per 2.16.1)
 * moved bitcast pointer tests to the kernel / physical addressing model part (+cleanup)
 * renamed spvOpcodeIsPointer to spvOpcodeReturnsLogicalPointer to clarify this function is only meant to be used with the logical addressing model

Add v1.1 tests for OpLoopMerge.

Add v1.1 capabilities validation.

Refactor the ValidateCapability test fixture.

Explain the meaning of test parameters.  Factor out methods for
convenience and readability.  DRY v1.0 and v1.1 tests.

Add basic Initializer/Finalizer tests.

Use a single definition of ARRAY_SIZE to simplify code.

Add OpSizeOf tests.

Refactor OpExecutionModeTest and apply it on v1.1.

Previously v1.1 testing was dead.

Refactor v1.1 tests and turn them on.

Previously, the "V11" text fixture was empty.

Add CHANGES file with high level software history

Add a high level version number for SPIRV-Tools, beginning
with v2016.0-dev.  The README describes the format of the
version number.

The high level version number is extracted from the CHANGES
file.  That works around:
 - stale-bait for when we don't add tags to the repository
 - our inability to add tags to the repository

Option --version causes spirv-as, spirv-dis, and spirv-val to
show the high level version number.

Add spvSoftwareVersionString to return the C-string for
the high level version number.

Add spvSoftwareVersionDetailsString() so that clients can get
more information if they want to.
Also allows us to clean up the uses in the tool executables files,
so now only one file includes build-version.inc.

Move the update-build-version logic to the only
CMakeLists file that needs it.

The update build version script takes a new argument
to name the output file.

Make grammar-generation fail if over 64 capabilities.

Eliminate kCapabilitiesMin/Max.

Turn module_capabilities_ into a spv_capability_mask_t.

Bump kCapabilitiesMaxValue for v1.1.

Fix Windows build.

Replace `#ifdef 0` with comment inside a macro call.

Avoid going out of bound in advanceLine() and refine comments.

Add tests for SubgroupDispatch.

Introduced in v1.1, SubgroupDispatch adds the following:
- two new execution modes
- one new capability
- two new opcodes

Extend ValidateBase methods to take a spv_target_env.  Replace the
context_ member with ScopedContext inside the said methods.  Give
ScopedContext wider visibility by moving it outside
TextToBinaryTestBase.

Mention 1.1 support in the README.

First tests for SPIR-V v1.1.

Add test for named-barrier instructions and capability.

Add spv_target_env as an optional argument to CompileSuccessfully() and
CompileFailure().  Currently defaults to UNIVERSAL_1_0, though that
could change in the future.

Make spv_context a local variable in test methods instead of a
TextToBinaryTestBase member.  Introduce ScopedContext to make temp
contexts easier.

Fix wrong grammar .inc file dependency introduced by copy-paste.

Rework CMake rules for building grammar tables.

Use add_custom_command() to generate all .inc files and manage
dependency with set_source_files_properties().

Update cmake files to support Android as a build target.

This enables cross-compiling to Android using scripts like
cmake-android that update the system name to reflect the build
target.

Make directories more safely.

Avoid a race on check-for-dir vs. make-dir
when running the inc-file generation script concurrently.

Add SPIR-V 1.1 grammar.

Switch to SPIR-V 1.1 as default.
Introduce SPV_ENV_UNIVERSAL_1_1.
Add "1_0" to the internal variable names.
Add spv_target_env to spv*GetTable().

Mark SPIR-V grammar files as 1.0.

Factor the CMake generate_grammar_tables invocation into a function
parameterized on the version.

GLSL grammar update.

* Add names to operands.
* Fix capability requirements for UnpackDouble2x32.
* Fix operands list error for NClamp.

Merge pull request #181 from antiagainst/readme

Use footnotes for links in README.md.

Use footnotes for links in README.md.

Grammar update: OpPhi now uses PairIdRefIdRef as the last operand.

Update the core grammar.

* IdType is renamed to IdResultType.
* version is splitted into major_version and minor_version.
* Seperate Scope and IdScope operand kinds. Same for MemorySemantics.

Make paths to grammar output files

The directory for a grammar output file will be created if
it doesn't already exist.

This is required to make the Android.mk build work.

Remove revision from SPV_ENV_*.

Revisions proliferate quickly and we don't promise to retain extra
grammar copies for every historical one.

Allow to only build certain grammar tables.

Remove the outdated patch file.

Now we use the JSON grammar and the generate_grammar_tables.py
script to maintain various info tables. That patch file will not
be needed anymore.

Fix MSVC error C2797.

Use JSON grammar files to generate extended instruction sets.

Rname grammar.json to spirv.core.grammar.json and add version info.

Fix validation of array length.

Remove dependency on SPIR-V headers in libspirv.h.

For fulfilling this purpose, the |opcode| field in the
|spv_parsed_instruction_t| struct is changed to of type uint16_t.

Also add functions to query the information of a given SPIR-V
target environment.

Enable linking against libSPIRV-Tools from linux shared libraries

Required for linking against libSPIRV-Tools from LVL's
libVkLayer_core_validation.so.

Signed-off-by: Chris Forbes <chrisforbes@google.com>

Fix spelling mistakes

Use the JSON grammar file to generate various info tables.

This patch uses a Python script to parse the JSON grammar file to
generate the opcode table and operand kind tables.

Now we don't need to do the post-processing (from OperandClass
to spv_operand_type_t) and copying of the opcode info table is
not required anymore!

Handle CRLF in assembly text.