Add Vulkan-specific validation rules for atomics

Added atomic instructions validation rules from
https://www.khronos.org/registry/vulkan/specs/1.0/html/vkspec.html#spirvenv-module-validation

Build SPIRV-Tools as shared library

Add pkg-config file for shared libraries

Properly build SPIRV-Tools DLL

Test C interface with shared library

Set PATH to shared library file for c_interface_shared test

Otherwise, the test won't find SPIRV-Tools-shared.dll.

Do not use private functions when testing with shared library

Make all symbols hidden by default for shared library target

Enable Visual Studio 2013 again

Disable use of Effcee and RE2 with MSVC compilers older than Visual
Studio 2015 since RE2 doesn't support them.

Fix test inclusion when Effcee is absent

Update CHANGES

Registering a type now rebuilds it out of memory owned by the manager.

* Added TypeManager::RebuildType
 * rebuilds the type and its constituent types in terms of memory owned
 by the manager.
 * Used by TypeManager::RegisterType to properly allocate memory
* Adding an unit test to expose the issue
* Added some tests to provide coverage of RebuildType
* Added an accessor to the target pointer for a forward pointer

ADCE: Fix combinator initialization

The combinator initialization was only looking at the capabilities
in the shader and not the inferred capabilities. Geometry and tessellation
shaders were not setting the Shader capability which is inferred. So the
combinator set was not initialized correctly causing problems for ADCE.

VS2013: LoopDescriptor LoopContainerType can't contain unique_ptr

The loop descriptor must explicitly manage the storage for contained
Loop objects.

Fixes #1262

Add barrier instructions validation pass

Avoid vector copies in range-for loops in opt/types.cpp

Also be more explicit about iterated types in other range-for loops.

Disambiguate between const and nonconst ForEachSuccessorLabel

This helps VisualStudio 2013 compile the code.

Contributes to #1262

Add general folding infrastructure.

Create the folding engine that will

1) attempt to fold an instruction.
2) iterates on the folding so small folding rules can be easily combined.
3) insert new instructions when needed.

I've added the minimum number of rules needed to test the features above.

Start v2018.1-dev

Finalize v2018.0

Update CHANGES

Reordering performance passes ordering to produce better opts

* Moved initial insert/extract passes later to cover more opportunities
* Added an extra set of passes to clean up opportunities exposed later
in the pipeline

Add LoopUtils class to gather some loop transformation support.

This patch adds LoopUtils class to handle some loop related transformations. For now it has 2 transformations that simplifies other transformations such as loop unroll or unswitch:
 - Dedicate exit blocks: this ensure that all exit basic block
   (out-of-loop basic blocks that have a predecessor in the loop)
   have all their predecessors in the loop;
 - Loop Closed SSA (LCSSA): this ensure that all definitions in a loop are used inside the loop
   or in a phi instruction in an exit basic block.

It also adds the following capabilities:
 - Loop::IsLCSSA to test if the loop is in a LCSSA form
 - Loop::GetOrCreatePreHeaderBlock that can build a loop preheader if required;
 - New methods to allow on the fly updates of the loop descriptors.
 - New methods to allow on the fly updates of the CFG analysis.
 - Instruction::SetOperand to allow expression of the index relative to Instruction::NumOperands (to be compatible with the index returned by DefUseManager::ForEachUse)

Add pass to reaplce invalid opcodes

Creates a pass that will remove instructions that are invalid for the
current shader stage.  For the instruction to be considered for replacement

1) The opcode must be valid for a shader modules.
2) The opcode must be invalid for the current shader stage.
3) All entry points to the module must be for the same shader stage.
4) The function containing the instruction must be reachable from an entry point.

Fixes #1247.

Added OpenCL ExtInst validation rules

Add adjacency validation pass

Validate OpPhi predecessors.
Validate OpLoopMerge successors.
Validate OpSelectionMerge successors.
Fix collateral damage to existing tests.
Remove ValidateIdWithMessage.OpSampledImageUsedInOpPhiBad.

Fixed harmless uninit var warning

Use SPIR-V headers from "unified1" directory

Remove constexpr from Analysis operators

* Had to remove templating from InstructionBuilder as a result
 * now preserved analyses are specified as a constructor argument
* updated tests and uses
* changed static_assert to a runtime assert
 * this should probably get further changes in the future

Opt: Add ScalarReplacement to RegisterSizePasses

Add memory semantics checks to validate atomics

Update CHANGES

Prevent unnecessary changes to the IR in dead branch elim

* When handling unreachable merges and continues, do not optimize to the
same IR
 * pass did not check whether the unreachable blocks were in the
 optimized form before transforming them
* added a test to catch this issue

Improved error message in val capabilities

Enhancements to block merging

* Should handle all possibilities
 * Stricter checks for what is disallowed:
  * header and header
  * merge and merge
 * Allow header and merge blocks to be merged
  * Erases the structured control declaration if merging header and
    merge blocks together.

Fix dereference of possibly nullptr

* If the dead branch elim is performed on a module without structured
control flow, the OpSelectionMerge may not be present
 * Add a check for pointer validity before dereferencing
* Added a test to catch the bug

InsertExtractElim: Split out DeadInsertElim as separate pass

Fixes in CCP for #1228

* Forces traversal of phis if the def has changed to varying
* Mark a phi as varying if all incoming values are varying
* added a test to catch the bug

Add LoopDescriptor as an IRContext analysis.

Move some function definitions from header to source to avoid circular definition.

DeadInsertElim: Detect and DCE dead Inserts

This adds Dead Insert Elimination to the end of the
--eliminate-insert-extract pass. See the new tests for examples of code
that will benefit.

Essentially, this removes OpCompositeInsert instructions which are not
used, either because there is no instruction which uses the value at the
index it is inserted, or because a subsequent insert intercepts any such
use.

This code has been seen to remove significant amounts of dead code from
real-life HLSL shaders being ported to Vulkan. In fact, it is needed to
remove dead texture samples which cause Vulkan validation layer errors
(unbound textures and samplers) if not removed . Such DCE is thus
required for fxc equivalence and legalization.

This analysis operates across "chains" of Inserts which can also contain
Phi instructions.

Initial implementation of if conversion

* Handles simple cases only
* Identifies phis in blocks with two predecessors and attempts to
convert the phi to an select
 * does not perform code motion currently so the converted values must
 dominate the join point (e.g. can't be defined in the branches)
 * limited for now to two predecessors, but can be extended to handle
 more cases
* Adding if conversion to -O and -Os

Validator: restricted some atomic ops for shaders

Ban floating point case for OpAtomicLoad, OpAtomicExchange,
OpAtomicCompareExchange. In graphics (Shader) environments, these
instructions only operate on scalar integers. Ban the floating point
case. OpenCL supports atomic_float.

Added Vulkan-specifc checks to image validation

Implemented Vulkan-specific rules:
- OpTypeImage must declare a scalar 32-bit float or 32-bit integer type
for the “Sampled Type”.
- OpSampledImage must only consume an “Image” operand whose type has its
“Sampled” operand set to 1.

Use id_map in Fold*ToConstant

The folding routines are suppose to use the id_map provided to map the
ids in the instruction.  The ones I just added are missing it.

Add generic folding function and use in CCP

The current folding routines have a very cumbersome interface, make them
harder to use, and not a obvious how to extend.

This change is to create a new interface for the folding routines, and
show how it can be used by calling it from CCP.

This does not make a significant change to the behaviour of CCP.  In
general it should produce the same code as before; however it is
possible that an instruction that takes 32-bit integers as inputs and
the result is not a 32-bit integer or bool will not be folded as before.

It seems like andriod has a problem with INT32_MAX and the like.  I'll
explicitly define those if the are not already defined.

Fixes infinite loop in ADCE

* Addresses how breaks are indentified to prevent infinite loops when
back to back loop share a merge and header
* Added test to catch the bug

Introduce an instruction builder helper class.

The class factorize the instruction building process.
Def-use manager analysis can be updated on the fly to maintain coherency.
To be updated to take into account more analysis.

Simplifying code for adding instructions to worklist

* AddToWorklist can now be called unconditionally
 * It will only add instructions that have not already been marked as
 live
 * Fixes a case where a merge was not added to the worklist because the
 branch was already marked as live
* Added two similar tests that fail without the fix

Create a pass to work around a driver bug related to OpUnreachable.

We have come across a driver bug where and OpUnreachable inside a loop
is causing the shader to go into an infinite loop.  This commit will try
to avoid this bug by turning OpUnreachable instructions that are
contained in a loop into branches to the loop merge block.

This is not added to "-O" and "-Os" because it should only be used if
the driver being targeted has this problem.

Fixes #1209.

Adding testcase for #1210

CFG: force the creation of a predecessor entry for all basic block.

This ensure that all basic blocks in a function have a valid entry the CFG object.

The entry block has no predecessors but remains a valid basic block
for which we might want to query the number of predecessors.
Some unreachable basic blocks may not have predecessors as well.

spirv-dis: Add --color option to force color disassembly

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

Fixing missing early exit from break identification

Adding support for switch removal in ADCE

* Updated code to handle switches
* Enabled disabled test and added a couple new ones

Capturing value table by reference in local redundancy elim

Update CHANGES

Fixes missing increment in common uniform elim

* Addresses #1203
* Increments inIdx in IsConstantIndexAccessChain
 * added test to catch the bug

Skip SpecConstants in CCP.

At the moment specialization constants look like constants to ccp.  This
causes a problem because they are handled differently by the constant
manager.

I choose to simply skip over them, and not try to add them to the value
table.  We can do specialization before ccp if we want to be able to
propagate these values.

Fixes #1199.

Update CHANGES

Add MatrixConstant

Remove redundant passes from legalization passes

With work that Alan has done, some passes have become redundant.  ADCE
now removed unused variables.  Dead branch elimination removes
unreachable blocks.  This means we can remove CFG Cleanup and dead
variable elimination.

Adding early exit versions of several ForEach* methods

* Looked through code for instances where code would benefit from early
exit
 * Added a corresponding WhileEach* method and updated the code

Move initialization of the const mgr to the constructor.

The current code expects the users of the constant manager to initialize
it with all of the constants in the module.  The problem is that you do
not want to redo the work multiple times.  So I decided to move that
code to the constructor of the constant manager.  This way it will
always be initialized on first use.

I also removed an assert that expects all constant instructions to be
successfully mapped.  This is because not all OpConstant* instruction
can map to a constant, and neither do the OpSpecConstant* instructions.

The real problem is that an OpConstantComposite can contain a member
that is OpUndef.  I tried to treat OpUndef like OpConstantNull, but this
failed because an OpSpecConstantComposite with an OpUndef cannot be
changed to an OpConstantComposite.  Since I feel this case will not be
common, I decided to not complicate the code.

Fixes #1193.

Start v2018.0-dev

Finalize v2017.3

Adding ostream operators for IR structures

* Added for Instruction, BasicBlock, Function and Module
* Uses new disassembly functionality that can disassemble individual
instructions
 * For debug use only (no caching is done)
 * Each output converts module to binary, parses and outputs an
 individual instruction
* Added a test for whole module output
* Disabling Microsoft checked iterator warnings
* Updated check_copyright.py to accept 2018

Maintain instruction to block mapping in phi insertion

* Changed MemPass::InsertPhiInstructions to set basic blocks for new
phis
* Local SSA elim now maintains instr to block mapping
 * Added a test and confirmed it fails without the updated phis
* IRContext::set_instr_block no longer builds the map if the analysis is
invalid
* Added instruction to block mapping verification to
IRContext::IsConsistent()

InsertExtractElim: Optimize through VectorShuffle, Mix

This improves Extract replacement to continue through VectorShuffle.
It will also handle Mix with 0.0 or 1.0 in the a-value of the desired
component.

To facilitate optimization of VectorShuffle, the algorithm was refactored
to pass around the indices of the extract in a vector rather than pass the
extract instruction itself. This allows the indices to be modified as the
algorithm progresses.

Add generic folding function and use in CCP

The current folding routines have a very cumbersome interface, make them
harder to use, and not a obvious how to extend.

This change is to create a new interface for the folding routines, and
show how it can be used by calling it from CCP.

This does not make a significant change to the behaviour of CCP.  In
general it should produce the same code as before; however it is
possible that an instruction that takes 32-bit integers as inputs and
the result is not a 32-bit integer or bool will not be folded as before.

Adding additional functionality to ADCE.

Modified ADCE to remove dead globals.
* Entry point and execution mode instructions are marked as alive
* Reachable functions and their parameters are marked as alive
* Instruction deletion now deferred until the end of the pass
* Eliminated dead insts set, added IsDead to calculate that value
instead
* Ported applicable dead variable elimination tests
* Ported dead constant elim tests

Added dead function elimination to ADCE
* ported dead function elim tests

Added handling of decoration groups in ADCE
* Uses a custom sorter to traverse decorations in a specific order
* Simplifies necessary checks

Updated -O and -Os pass lists.

Fix validation rules for GLSL pack/unpack 2x32

Rewriting dead branch elimination.

Pass now paints live blocks and fixes constant branches and switches as
it goes. No longer requires structured control flow. It also removes
unreachable blocks as a side effect. It fixes the IR (phis) before doing
any code removal (other than terminator changes).

Added several unit tests for updated/new functionality.

Does not remove dead edge from a phi node:
* Checks that incoming edges are live in order to retain them
* Added BasicBlock::IsSuccessor
* added test

Fixing phi updates in the presence of extra backedge blocks

* Added tests to catch bug

Reworked how phis are updated

* Instead of creating a new Phi and RAUW'ing the old phi with it, I now
replace the phi operands, but maintain the def/use manager correctly.

For unreachable merge:

* When considering unreachable continue blocks the code now properly
checks whether the incoming edge will continue to be live.

Major refactoring for review

* Broke into 4 major functions
 * marking live blocks
 * marking structured targets
 * fixing phis
 * deleting blocks

Fix constant propagation of induction variables.

This fixes https://github.com/KhronosGroup/SPIRV-Tools/issues/1143.
When an instruction transitions from constant to bottom (varying) in the
lattice, we were telling the propagator that the instruction was
varying, but never updating the actual value in the values table.

This led to incorrect value substitutions at the end of propagation.

The patch also re-enables CCP in -O and -Os.

Fix method comment for BasicBlock::MegeBlockIdIfAny

Fixes #1177

Allow relaxing validation of pointers in logical addressing mode

In HLSL structured buffer legalization, pointer to pointer types
are emitted to indicate a structured buffer variable should be
treated as an alias of some other variable. We need an option to
relax the check of pointer types in logical addressing mode to
catch other validation errors.

Add loop descriptors and some required dominator tree extensions.

Add post-order tree iterator.

Add DominatorTreeNode extensions:
 - Add begin/end methods to do pre-order and post-order tree traversal from a given DominatorTreeNode

Add DominatorTree extensions:
  - Add begin/end methods to do pre-order and post-order tree traversal
  - Tree traversal ignore by default the pseudo entry block
  - Retrieve a DominatorTreeNode from a basic block

Add loop descriptor:
  - Add a LoopDescriptor class to register all loops in a given function.
  - Add a Loop class to describe a loop:
    - Loop parent
    - Nested loops
    - Loop depth
    - Loop header, merge, continue and preheader
    - Basic blocks that belong to the loop

Correct a bug that forced dominator tree to be constantly rebuilt.

AnalyzeInstUse: Reuse the instruction lookup

Remove CCP from size and performance recipes, pending bugfixes

Currently CCP is incorrectly optimizing loops.
See https://github.com/KhronosGroup/SPIRV-Tools/issues/1143

Linker code cleanups

Turn `Linker::Link()` into free functions

  As very little information was kept in the Linker class, we can get rid
  of the whole class and have the `Link()` as free functions instead; the
  environment target as well as the consumer are passed along through an
  `spv_context` object.
  The resulting linked_binary is passed as a pointer rather than a
  reference to follow the Google C++ Style guidelines.

  Addresses remaining comments from
  https://github.com/KhronosGroup/SPIRV-Tools/pull/693 about the SPIR-V
  linker.

Fix variable naming in the linker

  Some of the variables were using mixed case, which did not follow the
  Google C++ Style guidelines.

Linker: Use EXPECT_EQ when possible and update some test

* Replace occurrences of ASSERT_EQ by EXPECT_EQ when possible;
* Reformulated some of the error messages;
* Added the symbol name in the error message when there is a type or
  decoration mismatch between the imported and exported declarations.

Opt: List all duplicates removed by RemoveDuplicatePass in the header

Opt: Make the const version of GetLabelInst() return a pointer

  For consistency with the non-const version, as well as other similar
  functions.

Opt: Rename function_end to EndInst()

  As pointed out by dneto0 the previous name was quite confusing and could
  be mistaken with a function returning an end iterator.
  Also change the return type of the const version to a pointer rather
  than a reference, for consistency.

Opt: Add performance comment to RemoveDuplicateTypes and decorations

  This comment was requested during the review of
  https://github.com/KhronosGroup/SPIRV-Tools/pull/693.

Opt: Add comments and fix variable naming in RemoveDuplicatePass

* Add missing comments to private functions;
* Rename variables that were using mixed case;
* Add TODO for moving AreTypesEqual out.

Linker: Remove commented out code and add TODOs

Linker: Merged together strings that were too much splitted

Implement a C++ RAII wrapper around spv_context

Allow getting the base pointer of an image load/store.

In value numbering, we treat loads and stores of images, ie OpImageLoad,
as a memory operation where it is interested in the "base address" of
the instruction.  In those cases, it is an image instruction.

The problem is that `Instruction::GetBaseAddress()` does not account for
the image instructions, so the assert at the end to make sure it found
a valid base address for its addressing mode fails.

The solution is to look at the load/store instruction to determine how
the assertion should be done.

Fixes #1160.

Fix infinite simulation cycles in SSA propagator.

This fixes https://github.com/KhronosGroup/SPIRV-Tools/issues/1159.  I
had missed a nuance in the original algorithm.  When simulating Phi
instructions, the SSA edges out of a Phi instruction should never be
added to the list of edges to simulate.

Phi instructions can be in SSA def-use cycles with other Phi
instructions.  This was causing the propagator to fall into an infinite
loop when the same def-use edge kept being added to the queue.

The original algorithm in the paper specifically separates the visit of
a Phi instruction vs the visit of a regular instruction.  This fix makes
the implementation match the original algorithm.

Ignore clang-format-diff.py from copyrights check

Having that script locally, for example to run check_code_format.sh
before sending a pull request, would cause the copyright notices check
to fail.

dead branch elim: Track killed backedges

When deleting branches and blocks, also remove them from
the backedges set, in case they were there.

This prevents us from keeping stale pointers to deleted Instruction
objects.  That memory could be used later by another instruction,
incorrectly signaling that something has a backedge reference, and
the dead branch eliminator could end up deleting live blocks.

Adds accessor method ir::BasicBlock::terminator

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

Add --print-all optimizer option

Adds optimizer API to write disassembly to a given output stream
before each pass, and after the last pass.

Adds spirv-opt --print-all option to write disassembly to stderr
before each pass, and after the last pass.

Opt: Make DecorationManager::HaveTheSameDecorations symmetric

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

Also: Add SpvOpDecorateId to IsAnnotationInst()

Validator checks out of bounds composite access

1. Added OpCompositeExtract/Insert out of bounds checks where possible
(everything except RuntimeArray)
2. Moved validation of OpCompositeExtract/Insert from validate_id.cpp to
validate_composites.cpp.

Address review comments from https://github.com/KhronosGroup/SPIRV-Tools/pull/985.

Update legalization passes

I've a few passes the legalization passes.  The first is to add the
more specialized load-store removal passes to help improve the compile
time, as was suggested in #1118.

I've also added dead branch elimination while we wait for the behaviour
of dead branch elimination to be folded into CFG cleanup.

I did not add CCP because it seems like most of the constant propagation
what is needed is already being done by the load-store removal passes,
which call `ReplaceAllUsesWith`.  We can reconsider this if needed.

Replace calls to `ToNop` by `KillInst`.

Calling `ToNop` leaves around instructions that are pointless.  In
general it is better to remove the instruction completely.  That way
other optimizations will not need to look at them.

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

Handle execution termination instructions when building edges.

This fixes issue https://github.com/KhronosGroup/SPIRV-Tools/issues/1153.

When building CFG edges, edges out of a OpKill and OpUnreachable
instruction should be directed to the CFG's pseudo exit block.

Do not insert Phi nodes in CCP propagator.

In CCP we should not need to insert Phi nodes because CCP never looks at
loads/stores.  This required adjusting two tests that relied on Phi
instructions being inserted.  I changed the tests to have the Phi
instructions pre-inserted.

I also added a new test to make sure that CCP does not try to look
through stores and loads.

Finally, given that CCP does not handle loads/stores, it's better to run
mem2reg before it.  I've changed the -O/-Os schedules to run local
multi-store elimination before CCP.

Although this is just an efficiency fix for CCP, it is
also working around a bug in Phi insertion.  When Phi instructions are
inserted, they are never associated a basic block.  This causes a
segfault when the propagator tries to lookup CFG edges when analyzing
Phi instructions.

Add ExtInst validation pass (GLSL only for now)

Validates all GLSL.std.450 extended instructions.

Test: Fix linux/gcc defined-but-not-used warnings/errors

utils/generate_grammar_tables.py: use spaces for indentation

One part of this file had indented using tabs. This causes newer
versions of python to complain. This changes the indentation to
consistently use four spaces throughout the file, to be consistent
with the rest of the file and the rest of the project.

Fix https://github.com/KhronosGroup/SPIRV-Tools/issues/1130

This addresses review feedback for the CCP implementation (which fixes
https://github.com/KhronosGroup/SPIRV-Tools/issues/889).

This adds more protection around the folding of instructions that would
not be supported by the folder.

Disallow Dim=SubpassData for OpImageSparseRead

Add asm, dis support for DebugInfo extended instruction set

Add grammar file for DebugInfo extended instruction set
- Each new operand enum kind in extinst.debuginfo.grammar.json maps
  to a new value in spv_operand_type_t.
- Add new concrete enum operand types for DebugInfo

Generate a C header for the DebugInfo extended instruction set

Add table lookup of DebugInfo extended instrutions

Handle the debug info operand types in binary parser,
disassembler, and assembler.

Add DebugInfo round trip tests for assembler, disassembler

Android.mk: Support DebugInfo extended instruction set

The extinst.debuginfo.grammar.json file is currently part of
SPIRV-Tools source.

It contributes operand type enums, so it has to be processed
along with the core grammar files.

We also generate a C header DebugInfo.h.

Add necessary grammar file processing to Android.mk.

CONTRIBUTING: If you fixed a bug, say so

Implement SSA CCP (SSA Conditional Constant Propagation).

This implements the conditional constant propagation pass proposed in

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

The main logic resides in CCPPass::VisitInstruction.  Instruction that
may produce a constant value are evaluated with the constant folder. If
they produce a new constant, the instruction is considered interesting.
Otherwise, it's considered varying (for unfoldable instructions) or
just not interesting (when not enough operands have a constant value).

The other main piece of logic is in CCPPass::VisitBranch.  This
evaluates the selector of the branch.  When it's found to be a known
value, it computes the destination basic block and sets it.  This tells
the propagator which branches to follow.

The patch required extensions to the constant manager as well. Instead
of hashing the Constant pointers, this patch changes the constant pool
to hash the contents of the Constant.  This allows the lookups to be
done using the actual values of the Constant, preventing duplicate
definitions.

Store all enabled capabilities in the feature manger.

In order to keep track of all of the implicit capabilities as well as
the explicit ones, we will add them all to the feature manager.  That is
the object that needs to be queried when checking if a capability is
enabled.

The name of the "HasCapability" function in the module was changed to
make it more obvious that it does not check for implied capabilities.

Keep an spv_context and AssemblyGrammar in IRContext

Update CHANGES

Fixing bugs in type manager memory management

* changed the way duplicate types are removed to stop copying
instructions
* Reworked RemoveDuplicatesPass::AreTypesSame to use type manager and
type equality
* Reworked TypeManager memory management to store a pool of unique
pointers of types
 * removed unique pointers from id map
 * fixed instances where free'd memory could be accessed

Update the legalization passes.

Changes the set of optimizations done for legalization.  While doing
this, I added documentation to explain why we want each optimization.

A new option "--legalize-hlsl" is added so the legalization passes can
be easily run from the command line.
The legalize option implies skip-validation.

Make a string parameter const ref

Fix CHANGES: there is no OpImageSparseWrite

Update CHANGES for recent changes