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

Opt: Fix implementation and comment of AreDecorationsTheSame
Target should not be ignored when comparing decorations in RemoveDuplicates
Opt: Remove unused code in RemoveDuplicateDecorations

Allow pointers to pointers in logical addressing mode.

A few optimizations are updates to handle code that is suppose to be
using the logical addressing mode, but still has variables that contain
pointers as long as the pointer are to opaque objects.  This is called
"relaxed logical addressing".

|Instruction::GetBaseAddress| will check that pointers that are use meet
the relaxed logical addressing rules.  Optimization that now handle
relaxed logical addressing instead of logical addressing are:

 - aggressive dead-code elimination
 - local access chain convert
 - local store elimination passes.

Convert private variables to function scope.

When a private variable is used in a single function, it can be
converted to a function scope variable in that function.  This adds a
pass that does that.  The pass can be enabled using the option
`--private-to-local`.

This transformation allows other transformations to act on these
variables.

Also moved `FindPointerToType` from the inline class to the type manager.

More validation on primitive instructions

- Test validation success for OpEmitVertex OpEndPrimitive
- Test missing capabilities for primitive instructions
- Primitive instructions require Geometry execution model

validate & test of literal's upper bits

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

Opt: Remove commented out duplicated type_id function

This code was wrongly added by #693.

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