Fix dominance calculation

Fixes dominance calculation when there is a forward arc from an
unreachable block A to a reachable block B.  Before this fix, we would
say that B is not dominated by the graph entry node, and instead say
that the immediate dominator of B is the psuedo-entry node of the
augmented CFG.

The fix:

- Dominance is defined in terms of a traversal from the entry block
  of the CFG.  So the forward DFS should start from the function
  entry block, not the pseudo-entry-block.

- When following edges backward during dominance calculations, only go to
  nodes that are actually reachable in the forward traversal.
  Important: the sense of reachability flips around when computing
  post-dominance.

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

Add blurbs for freeze-spec-const pass

Create directory first if not existing and always refresh.

Avoid redefining builtin dir.

Simple Assembly code builder for test uses

AssemblyBuilder contains boilplates.
Adds OpName instructions for all added defining instructions.
Adds OpDecorate SpecId for all spec constants added with OpSpecConstant,
OpSpecConstantTrue and OpSpecConstantFalse instructions.

Only check def dominance of reachable uses

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

Update CHANGES to reflect INotEqual update

Allow OpINotEqual in OpSpecConstantOp inst

Pendding for now until the spec is fixed.

Never generate % for a friendly disassembled Id

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

Add disabled test for phi variable def-use check

Disabled because doing a proper check requires much more
code, and it can wait.

Avoid checking def-use dominance for OpPhi value operands

The def-use dominance checker doesn't have enough info to know
that a particular use is in an OpPhi, so skip tracking those uses
for now.  Add a TODO to do a proper OpPhi variable-argument check
in the future.

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

Optimization: Add def use analysis.

Use default copy/move constructors/assignments for Instruction.

Allow missing memory model instructions in modules.

Fix infinite loop in dominance calculation.

Ensure the dominance calculation visits all nodes in the CFG.
The successor list of the pseudo-entry node is augmented with
a single node in each cycle that otherwise would not be visited.
Similarly, the predecssors list of the pseduo-exit node is augmented
with the a single node in each cycle that otherwise would not
be visited.

Pulls DepthFirstSearch out so it's accessible outside of the dominator
calculation.

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

Merge pull request #284 from Qining/fix-freeze-spec-const-pass-test

Fix a test failure in pass manager test

Fix a test failure in pass manager test

Change "Null" to "null" in pass manager test

Freeze spec constants to their default values

Add a pass to freeze spec constants to their default values. This pass does
not fold the frozen spec constants and does not handle SpecConstantOp
instructions and SpecConstantComposite instructions.

Add an utility: in-place string replacement

Use friendly disassembly output

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.