Move the def-use analysis for single inst to public

Add getter for pointee, element type

Create an iterator class for in-memory representation.

Make the lookup up of type id accepts const arg

Reuse the iterator on Id and type lookup

Add the const version of AsXXtype() interface.

Add GetId(Type* type) API to the type manager

Avoid double-copy of NameMapper object.

Use friendly names for Ids

Add spirv-cfg to dump a GraphViz graph of the CFG

This is experimental, and has not tests.
It's been used to debug validation of structured control flow.

- Has a legend describing special arcs to merge blocks and continue
  targets.
- Labels the function entry block, with the Id of the function.

Add back the missing msg about --eliminate-dead-const

Fix build error about passing initializer-list to constructor.

VS2013 is not happy with using initializer-list to initialize
vector parameters to explicit constructors taking one vector.

Make type manager RAII-like w.r.t. the module to be analyzed.

Optimization: Add type manager.

Type manager will construct a map of types gradually from
instructions.

Optimization: Add type class hierarchy.

Appveyor: also test on Visual Studio 2013.

Fix paths in the README.

Change the interfaces of in-memory representation to use pointers.

Previously we use vectors of objects and move semantics to handle
ownership. That approach has the flaw that inserting an object into
the middle of a vector, which may trigger a vector reallocation,
can invalidate some addresses taken from instructions.

Now the in-memory representation internally uses vector of unique
pointers to handle ownership. Since objects are explicitly heap-
allocated now, pointers to them won't be invalidated by vector
resizing anymore.

Update CHANGES to say issue 288 is fixed

Fixed the build for MSVC.

assembly_builder was missing an include for cstdint.

Manually create move the constructor/assignment for Instruction.

This is because some old visual studio versions (e.g., 2013) do
not support automatically generating move constructors/assignments.

Fix compilation. My bad

The API changed, and I forgot to submit this patch.

Check dominance of OpPhi parent and variable pairs

Removed dead code/const_casts/lists

Separate pass.h from passes.h

Future pass implementations should only need to include pass.h

Use NEW behavior for policy CMP0054.

The NEW behavior is to not dereference variables or interpret keywords
that have been quoted or bracketed.

For more information, see
https://cmake.org/cmake/help/v3.1/policy/CMP0054.html.

This is to suppress a warning when using CMake 3.1.3+.

Refactor Id -> Instruction

Fix minor mistakes in the tests of dead-const-elim

Print the shader when module building failed

Dead constant elimination

A pass to remove dead constants, including both front-end constants and spec
constants.

This pass does not handle dead variables and types.

Remove unnecessary headers

Remove needless copies. Delete copy constructor.

* Deletes the ValidationState_t copy constructor
* Removes needless copies of the copy constructor

Add target envs for OpenCL, OpenGL

Covers: OpenCL 2.1, OpenCL 2.2
Covers: OpenGL 4.0, OpenGL 4.1, OpenGL 4.2, OpenGL 4.3, OpenGL 4.5.
The OpenGL environments assume the use of GL_ARB_gl_spirv, of course.

Start v2016.3-dev

Finalize v2016.2

Document recently fixed bugs.

Hide implementations of BasicBlock::dominates,postdominates

Track a construct by its entry block.

Validator cfg fixes

- Find unreachable continue targets.  Look for back edges
  with a DFS traversal separate from the dominance traversals,
  where we count the OpLoopMerge from the header to the continue
  target as an edge in the graph.

- It's ok for a loop to have multiple back edges, provided
  they are all from the same block, and we call that the latch block.
  This may require a clarification/fix in the SPIR-V spec.

- Compute postdominance correctly for infinite loop:
  Bias *predecessor* traversal root finding so that you use
  a later block in the original list.  This ensures that
  for certain simple infinite loops in the CFG where neither
  block branches to a node without successors, that we'll
  compute the loop header as dominating the latch block, and the
  latch block as postdominating the loop header.

Add BasicBlock methods: dominates postdominates

Rename a variable so it's consistent with spec

In the spec "continue block" is a block with a branch
to the Continue Target.  It's not the Continue Target.

Check configuration and gmock existence when adding unit tests.

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.