Generic value propagation engine. by dnovillo · Pull Request #985 · KhronosGroup/SPIRV-Tools

dnovillo · 2017-11-20T15:49:01Z

NOTE: I am adding tests and debugging at the moment. I'm sending this initial version for review and discussion. This will be used as the basis for SSA-CCP, copy propagation and range propagation (if we decide to add it).

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.

atgoo · 2017-11-20T15:56:04Z

source/opt/instruction.h

 #ifndef LIBSPIRV_OPT_INSTRUCTION_H_
 #define LIBSPIRV_OPT_INSTRUCTION_H_

+#include <opcode.h>


Not needed.

atgoo · 2017-11-20T16:18:18Z

source/opt/instruction.h


-inline void Instruction::AddOperand(Operand &&operand) {
+inline void Instruction::AddOperand(Operand&& operand) {
  operands_.push_back(operand);


This probably was supposed to be
operands_.push_back(std::move(operand));

atgoo · 2017-11-20T16:33:54Z

source/opt/propagator.cpp

+
+template <typename ValueType>
+void SSAPropagator<ValueType>::AddControlEdge(const Edge& edge) {
+  const ir::BasicBlock *dest_bb = edge.dst;


const ir::BasicBlock*

s-perron · 2017-11-20T18:00:36Z

source/opt/propagator.h

+namespace opt {
+
+// Represents a CFG control edge. TODO(dnovillo): Move it to ir::CFG and always
+// build it. Alternately, move it to IRContext and build it on-demand.


The TODO is not clear what is being built. This is just a CFG edge.

Moved to the spot we actually build preds/succs.

atgoo · 2017-11-20T18:41:42Z

source/opt/propagator.h

+// Hashing operator for Edge. Needed to instantiate unordered sets of Edges.
+namespace std {
+template <>
+struct std::hash<spvtools::opt::Edge> {


You are already in the namespace.
std::hash -> hash

s-perron

Lots of changes, but mostly in the comments. You seem to be mixing terminology from the paper with that of the specific implementation, which gets confusing at times.

s-perron · 2017-11-20T18:03:25Z

source/opt/propagator.h

+  explicit Edge(const ir::BasicBlock* b1, const ir::BasicBlock* b2)
+      : src(b1), dst(b2) {}
+  const ir::BasicBlock* src;
+  const ir::BasicBlock* dst;


For classes (or variables) that will be used in many places, are abbreviations like this a good idea? The style guide says not to abbreviate: https://google.github.io/styleguide/cppguide.html#Naming

s-perron · 2017-11-20T18:04:58Z

source/opt/propagator.h

+// Hashing operator for Edge. Needed to instantiate unordered sets of Edges.
+namespace std {
+template <>
+struct std::hash<spvtools::opt::Edge> {


https://google.github.io/styleguide/cppguide.html#std_hash

Don't define specializations of std::hash.

I've taken the easy way out and I'm using std::set for edges.

s-perron · 2017-11-20T18:13:24Z

source/opt/propagator.h

+//             at compile time.  Further simulation of I is not required.
+//             If I is a conditional jump, all the outgoing edges for the
+//             block are considered executable and added to the work
+//             list.


Not clear who is responsible for adding to the work list. This seems like |visit_fn| is doing this because you are describing the results of |vistit_fn| right?

Not really. The simulate_fn callback simply needs to return the indication that the instruction was interesting for the propagator to add SSA edges out of it. The actual tracking of values needs to be done by the simulate_fn itself. I've added this to the documentation.

s-perron · 2017-11-20T18:15:28Z

source/opt/propagator.h

+//             the instructions that feed from I.  Furthermore, if I is a
+//             conditional jump, only the edge known to be taken is added
+//             to the work list.  Edges that are known not to execute are
+//             never simulated.


Same as above.

Clarified and added sample code.

s-perron · 2017-11-20T18:16:29Z

source/opt/propagator.h

+//             Blocks are added to this queue if their incoming edges are
+//             executable.
+//
+//      Edges: contains the list of statements that we need to revisit.


This naming seem odd. "Edges" is a "list of statements"?

Fixed. This was referring to SSA edges (def-use edges).

s-perron · 2017-11-20T18:45:49Z

source/opt/propagator.h

+  // Function that visit instructions during simulation. The output of this
+  // function is used to determine if the simulated instruction produced a value
+  // interesting for propagation. The actual value produced by the instruction
+  // must be stored in the |values_| map.


Should we mention "SetValue" at the method of storing the value?

Not needed anymore. This was the only thing that was forcing the whole class to be a template. It's unnecessary, so I moved this as a requirement for the user-provided callback.

s-perron · 2017-11-20T18:47:08Z

source/opt/propagator.h

+
+  // SSA def-use edges to traverse. Each entry is a destination statement for an
+  // SSA def-use edge as returned by |def_use_manager_|.
+  std::queue<ir::Instruction*> ssa_edges_;


How can a single instruction be an edge? I find this very confusing.

Renamed to ssa_edge_uses_

s-perron · 2017-11-20T19:04:33Z

source/opt/propagator.cpp

+      AddSSAEdges(instr->result_id());
+    }
+
+    /* If STMT transfers control out of its basic block, add


s-perron · 2017-11-20T19:07:10Z

source/opt/propagator.cpp

+
+  ir::BasicBlock* dest_bb = nullptr;
+  uint32_t result_id = 0;
+  PropStatus status = visit_fn_(instr, &dest_bb, &result_id);


You pass in the address |result_id|, but |result_id| is not used afterward. Why do you need it?

s-perron · 2017-11-20T19:19:04Z

source/opt/propagator.cpp

+  // before. We do this because Phi instructions receive their inputs from
+  // incoming edges. When those edges are marked executable, the corresponding
+  // operand can be evaluated.
+  block->ForEachPhiInst([this](ir::Instruction* instr) { Simulate(instr); });


I don't understand why this is necessary. Won't the phi nodes get added to "sss_edges_" when its operands are simulated. So the phi nodes will get processed anyway if they need to. Is that right?

Phi nodes get operands enabled not only by SSA edges, a Phi operand becomes available also when the incoming CFG edge is marked executable. That's why this code checks which operands have an executable predecessor.

alan-baker · 2017-11-20T20:23:48Z

source/opt/instruction.h

  // Returns true if the instruction annotates an id with a decoration.
  inline bool IsDecoration();

+  // Returns true if this instruction is a branch instruction (either


Mention switch support.

alan-baker · 2017-11-20T20:28:33Z

source/opt/propagator.cpp

+  // operand can be evaluated.
+  block->ForEachPhiInst([this](ir::Instruction* instr) { Simulate(instr); });
+
+  // If this is the frist time this block is being simulated, evaluate every


frist -> first

alan-baker · 2017-11-20T21:09:03Z

source/opt/propagator.h

+
+  using VisitFunction = std::function<PropStatus(ir::Instruction*)>;
+
+  SSAPropagator(ir::IRContext* context, ir::CFG* cfg, VisitFunction& visit_fn)


const VisitFunction&

alan-baker · 2017-11-20T21:14:51Z

source/opt/propagator.h

+  std::unordered_set<ir::Instruction*> do_not_simulate_;
+
+  // Map between a basic block and its predecessor edges.
+  std::unordered_map<ir::BasicBlock*, std::list<Edge>> bb_preds_;


Please repeat the todo about moving these into CFG (which is to be moved into IRContext).

alan-baker

Small changes.

atgoo · 2017-11-20T20:21:43Z

source/opt/propagator.h

+#include <functional>
+#include <unordered_map>
+#include <unordered_set>
+#include <queue>


Please list headers in alphabetical order.

atgoo · 2017-11-20T21:29:49Z

source/opt/propagator.h

+
+  using VisitFunction = std::function<PropStatus(ir::Instruction*)>;
+
+  SSAPropagator(ir::IRContext* context, ir::CFG* cfg, VisitFunction& visit_fn)


Consider passing the function by value, const-reference or rvalue reference. Passing by non-const reference will disallow in-place definition of a lambda.

atgoo · 2017-11-20T21:50:46Z

source/opt/propagator.h

+  void SetValue(uint32_t id, ValueType value) { values_[id] = value; }
+
+  // Gets the value for |id|. If |id| has not been assigned a value, it
+  // throws a runtime assertion.


It would raise SIGABRT since we build with -fno-exceptions.

atgoo · 2017-11-20T21:55:21Z

source/opt/propagator.cpp

+  }
+
+  // Add the edges out of the entry block to seed the propagator.
+  std::list<Edge> entry_succs = bb_succs_[fn->entry()];


const std::list&

atgoo · 2017-11-20T21:57:11Z

source/opt/propagator.cpp

+
+  // Add the edges out of the entry block to seed the propagator.
+  std::list<Edge> entry_succs = bb_succs_[fn->entry()];
+  for (const auto& e : bb_succs_[fn->entry()]) {


for (const auto& e : entry_succs) {

atgoo · 2017-11-20T22:10:11Z

source/opt/propagator.h

+struct std::hash<spvtools::opt::Edge> {
+  size_t operator()(const spvtools::opt::Edge& e) const {
+    return std::hash<const spvtools::ir::BasicBlock*>()(e.src) ^
+           std::hash<const spvtools::ir::BasicBlock*>()(e.dst);


Unless the hash is supposed to be symmetric I would prefer
hash1 * kConst + hash2.

Removed. Using std::set.

dnovillo

Thanks for the feedback. I've addressed all the comments and added new tests. I'm adding more tests now, but the code is now ready for more reviewing.

PTAL. Thanks.

dnovillo · 2017-11-21T19:58:33Z

source/opt/propagator.h

+ public:
+  // Lattice values used for propagation. See class documentation for
+  // a description.
+  enum PropStatus { NotInteresting, Interesting, Varying };


dnovillo · 2017-11-21T20:00:44Z

source/opt/propagator.h

+  // Initialize processing.
+  void Initialize(ir::Function* fn);
+
+  // Simulate the execution of |block| by evaluating every instruction in it.


They are. Changed to use 'simulate' everywhere.

dnovillo · 2017-11-21T20:01:34Z

source/opt/propagator.h

+  }
+
+  // Returns true if |block| has been simulated already.
+  bool IsBlockSimulated(ir::BasicBlock* block) {


I'm not sure how else to say this. The predicate does precisely that. If every instruction has been simulated, it returns true.

dnovillo · 2017-11-21T20:02:03Z

source/opt/propagator.h

+  }
+
+  // Returns true if |block| has been simulated already.
+  bool IsBlockSimulated(ir::BasicBlock* block) {


May be BlockHasBeenSimulated?

dnovillo · 2017-11-21T20:03:01Z

source/opt/propagator.h

+
+  // Marks |edge| as executable.  Returns false if the edge was already marked
+  // as executable. Otherwise, the edge is marked executable for the first time
+  // and it returns true.


dnovillo · 2017-11-21T20:03:38Z

source/opt/propagator.h

+    return executable_edges_.find(edge) != executable_edges_.end();
+  }
+
+  // Return a pointer to the def-use manager for this context.


dnovillo · 2017-11-21T20:04:50Z

source/opt/propagator.h

+  }
+
+  // Add the destination block of the CFG edge |e| to the work list.  If |e|
+  // had already been executed, do nothing.


dnovillo · 2017-11-21T20:05:34Z

source/opt/propagator.h

+  void AddControlEdge(const Edge& e);
+
+  // Add all the use statements at the end of SSA edges coming out the
+  // definition for |id|.


Paper terminology. Fixed.

dnovillo · 2017-11-21T20:07:09Z

source/opt/propagator.h

+  // Function that visit instructions during simulation. The output of this
+  // function is used to determine if the simulated instruction produced a value
+  // interesting for propagation. The actual value produced by the instruction
+  // must be stored in the |values_| map.


Not needed anymore. This was the only thing that was forcing the whole class to be a template. It's unnecessary, so I moved this as a requirement for the user-provided callback.

dnovillo · 2017-11-21T20:39:19Z

source/opt/instruction.h

  // Returns true if the instruction annotates an id with a decoration.
  inline bool IsDecoration();

+  // Returns true if this instruction is a branch instruction (either


atgoo · 2017-11-21T23:15:10Z

source/opt/propagator.cpp

+      ir::BasicBlock* succ_bb =
+          ctx_->get_instr_block(get_def_use_mgr()->GetDef(label_id));
+      bb_succs_[&block].push_back(Edge(&block, succ_bb));
+      bb_preds_[succ_bb].push_back(Edge(succ_bb, &block));


I don't see bb_preds_ being used anywhere. Should bb_preds_ also feature pseudo-blocks?

Good point. Added. Predecessors are not really used in the propagator, but I'm thinking of moving this into ir::CFG and I think I may need it in SSA-CCP itself.

dnovillo · 2017-11-22T19:27:34Z

@s-perron, @alan-baker with the new tests, this PR is ready for more reviews. PTAL. Thanks.

alan-baker · 2017-11-22T20:21:06Z

source/opt/aggressive_dead_code_elim_pass.cpp

    for (auto ii = (*bi)->begin(); ii != (*bi)->end(); ++ii) {
      if (IsLive(&*ii)) continue;
-      if (IsBranch(ii->opcode()) &&
+      if (ii->IsBranch() &&


You've extended the functionality of this pass. You should test it with an OpSwitch.

I recommend not changing this right now. Pottery barn rules...

In particular, the lines at 223 and 224 specifically check for OpBranch and OpBranchConditional. So who knows if that also needs OpSwitch to be there too if you change this line.

(Good catch @alan-baker )

Added a new test, but it fails because ADCE does not seem to handle OpSwitch at all (#1021)

Restored the original test. I had filed #1021 for lack of OpSwitch support. I've added an open-coded test for Branch and BranchConditional to avoid having two flavours of IsBranch().

alan-baker · 2017-11-22T20:23:01Z

source/opt/basic_block.h


+  // Returns true if this basic block exits this function and returns to its
+  // caller.
+  bool IsReturn() const { return insts_.back().IsReturn(); }


return tail()->IsReturn(). Fewer restrictions on the underlying implementation of insts_.

alan-baker · 2017-11-22T20:27:14Z

source/opt/instruction.h

+
+  // Returns true if this instruction is a basic block terminator.
+  bool IsBlockTerminator() const {
+    return IsBranch() || IsReturn() || opcode() == SpvOpKill ||


Consider making this congruent with the other tests.

alan-baker

Most important is to extend the tests for adce.

s-perron · 2017-11-23T17:00:17Z

source/opt/propagator.h

+//
+// EXAMPLE: Basic constant store propagator.
+//
+// Suppose we want to propagate all constant assignments of the form "OpStore


I don't know if this is a good example. No propagating seems to be going on, and it is unclear what should happen if there are two store to the same variable with different constants. If I was trying to figure out how my |value_fn| function is suppose to work so I can use the propagator, I would be confused.

s-perron

I'm still unclear about the requirements that the visit function has the meet. For example, what happens if it returns that all branch instructions are not interesting? Looking at the implementation of the propagator, it seems like a whole lot of blocks will not be visited. Is that intended? If so, more explanation is needed. If not it needs to be fixed up.

dnovillo · 2017-11-23T17:47:25Z

On Thu, Nov 23, 2017 at 12:00 PM, Steven Perron ***@***.***> wrote: ***@***.**** commented on this pull request. ------------------------------ In source/opt/propagator.h <#985 (comment)> : > +// CFG blocks: contains the queue of blocks to be simulated. +// Blocks are added to this queue if their incoming edges are +// executable. +// +// SSA Edges: An SSA edge is a def-use edge between a value-producing +// instruction and its use instruction. The SSA edges list +// contains the statements at the end of a def-use edge that need +// to be re-visited when an instruction produces a kVarying or +// kInteresting result. +// +// 4- Simulation terminates when all work queues are drained. +// +// +// EXAMPLE: Basic constant store propagator. +// +// Suppose we want to propagate all constant assignments of the form "OpStore I don't know if this is a good example. No propagating seems to be going on, and it is unclear what should happen if there are two store to the same variable with different constants. If I was trying to figure out how my |value_fn| function is suppose to work so I can use the propagator, I would be confused.

I have to balance between a very detailed example vs an example that gives a brief idea of how it works. I'll try to add a more complete example. But, in the end, the paper references are the ones to go read when implementing your own propagation.

dnovillo · 2017-11-23T17:48:54Z

On Thu, Nov 23, 2017 at 12:13 PM, Steven Perron ***@***.***> wrote: ***@***.**** requested changes on this pull request. I'm still unclear about the requirements that the visit function has the meet. For example, what happens if it returns that all branch instructions are not interesting? Looking at the implementation of the propagator, it seems like a whole lot of blocks will not be visited. Is that intended? If so, more explanation is needed. If not it needs to be fixed up.

Yes, that's exactly what happens. I'll rephrase and re-arrange to make it more clear. All the requirements are there now. I'll re-arrange.

dnovillo · 2017-11-23T22:03:10Z

@s-perron added more details on the user-provided visit function. I decided against creating a more detailed example in the docs. I prefer to have the tests be that example. The tests have the advantage that they will be updated with any API changes.

Will address the comments from @alan-baker

s-perron · 2017-11-24T15:38:35Z

Need to make the build bots happy, but otherwise LGTM.

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.

dnovillo · 2017-11-28T04:34:29Z

Re-based, re-tested and pushed to master as 7432784

dneto0 · 2017-11-29T16:24:04Z

This MR is proximate cause of Windows debug build failure. PTAL @dnovillo

dneto0

Ugh. I reviewed this last year but failed to hit "submit review". :-(
Looks like the OpKill issue came up as #1153

dneto0 · 2017-11-24T02:41:08Z

source/opt/aggressive_dead_code_elim_pass.cpp

    for (auto ii = (*bi)->begin(); ii != (*bi)->end(); ++ii) {
      if (IsLive(&*ii)) continue;
-      if (IsBranch(ii->opcode()) &&
+      if (ii->IsBranch() &&


I recommend not changing this right now. Pottery barn rules...

In particular, the lines at 223 and 224 specifically check for OpBranch and OpBranchConditional. So who knows if that also needs OpSwitch to be there too if you change this line.

(Good catch @alan-baker )

dneto0 · 2017-11-24T02:42:13Z

source/opt/basic_block.h

  // this block, if any.  If none, returns zero.
  uint32_t ContinueBlockIdIfAny() const;

+  // Returns true if this basic block exits this function and returns to its


This begs the question: Do you need to do something special for OpKill or OpUnreachable?
(OpKill is weird...)

Should be fixed with #1156 which added IsReturnOrAbort.

dneto0 · 2017-11-24T02:45:25Z

source/opt/propagator.h

+
+// Represents a CFG control edge.
+struct Edge {
+  explicit Edge(ir::BasicBlock* b1, ir::BasicBlock* b2)


Does explicit mean anything when the constructor has two parameters?

Also, are you requiring both blocks to be null? If not, then would it be better to make the members references?

We use BasicBlock pointers all over the place (particularly when doing things like testing whether a block is one of the pseudos in the CFG). I've added a test for non-null in the constructor.

dnovillo

Thanks for the review. I've created a new PR to handle them (#1163).

dnovillo · 2018-01-04T17:12:10Z

source/opt/aggressive_dead_code_elim_pass.cpp

    for (auto ii = (*bi)->begin(); ii != (*bi)->end(); ++ii) {
      if (IsLive(&*ii)) continue;
-      if (IsBranch(ii->opcode()) &&
+      if (ii->IsBranch() &&


Restored the original test. I had filed #1021 for lack of OpSwitch support. I've added an open-coded test for Branch and BranchConditional to avoid having two flavours of IsBranch().

dnovillo · 2018-01-04T17:14:25Z

source/opt/basic_block.h

  // this block, if any.  If none, returns zero.
  uint32_t ContinueBlockIdIfAny() const;

+  // Returns true if this basic block exits this function and returns to its


Should be fixed with #1156 which added IsReturnOrAbort.

dnovillo · 2018-01-04T17:58:27Z

source/opt/propagator.h

+
+// Represents a CFG control edge.
+struct Edge {
+  explicit Edge(ir::BasicBlock* b1, ir::BasicBlock* b2)


We use BasicBlock pointers all over the place (particularly when doing things like testing whether a block is one of the pseudos in the CFG). I've added a test for non-null in the constructor.

Changelist: ce5941a ce5941a Fixes GPUOpen-Drivers#1357. Support null constants better in folding bdaf8d5 Opt: Add constant folding for FToI and IToF 9457cab Fixes GPUOpen-Drivers#1354. Do not merge integer division. 588f4fc Add more folding rules for vector shuffle. 90e1637 Remove Function::GetBlocks pushed by accident 2cb589c Remove uses DCEInst and call ADCE 0c13467 Consistently include latest spirv.h header file. 802cf05 Merge arithmetic with non-trivial constant operands 20b8cdb Make IR builder use the type manager for constants 9394272 linker: merge debug annotations from category c) bdd6617 linker: Allow modules to be partially linked 64298bf tools/linker: Allow setting --verify-ids on the command line b08b94e Update CHANGES 3497a94 Add loop unswitch pass. e354984 Unroller support for multiple induction variables 94af58a Clean up variables before sroa 3f19c20 Preserve analysies in the simplification pass 432dc40 Appveyor: remove VS2015 configuration to reduce build time 46a9ec9 Opt: Check for side-effects in DCEInst() 01760d2 Fixes GPUOpen-Drivers#1338. Handle OpConstantNull in branch/switch conditions 51ecc73 Reduce instruction create and deletion during inlining. c1b9366 Add Insert-extract elimination back into legalization passes. 309be42 Add folding for redundant add/sub/mul/div/mix operations fa3ac3c Revert "Preserve analysies in the simplification pass" ec3bbf0 Preserve analysies in the simplification pass 6c75050 Speed up Phi insertion. ac9ab0d Travis: require MacOS to build and test again 9d95a91 Fix folding insert feeding extract c3f34d8 Fixes GPUOpen-Drivers#1300. Adding checks for bad CCP transitions and unsettled values e543b19 Removed warnings from hex_float.h 04cd63e Make better use of simplification pass 1054413 Add constant folding rules for floating-point comparison 27d23a9 Remove constants from constant manager in KillInst 50f307f Simplify OpPhi instructions referencing unreachable continues 3756b38 Get CCP to use the constant floating point rules. efe286c SubgroupBallotKHR can enable SubgroupSize & SubgroupLocalInvocationId 5d442fa fix typo d2c0fce Invoke cmake via CMAKE_COMMAND variable f3a1047 Avoid using static unordered_map (GPUOpen-Drivers#1304) 32a8e04 Add folding of redundant OpSelect insns 0e9f2f9 Add id to name map 6669d81 Fold binary floating point operators. dd8400e Initial support for loop unrolling. 229ebc0 Fixes GPUOpen-Drivers#1295. Mark undef values as varying in ccp. 0869992 Cleanup. Use proper #include guard. NFC. 06b437d Avoid using the def-use manager during inlining. 70bf351 Fix spirv.h include to rely on include paths 1d7b142 Add folding of OpCompositeExtract and OpConstantComposite constant instructions. 8868591 Fix generation of Vim syntax file 4e4a254 Do not hardcode libdir and includedir in pkg config files 1a849ff Add header files missing from CMakeLists.txt 84ccd0b Loop invariant code motion initial implementation ca4457b SROA: Do replacement on structs with no partial references. 06cdb96 Make use of the instruction folder. a61e4c1 Disable check which fails Vulkan CTS 2f0c3aa Add Vulkan-specific validation rules for atomics 3013897 Build SPIRV-Tools as shared library b1c9c4e Enable Visual Studio 2013 again e7fafda Fix test inclusion when Effcee is absent c452bfd Update CHANGES 8710227 Registering a type now rebuilds it out of memory owned by the manager. 860b2ee ADCE: Fix combinator initialization 9e19fc0 VS2013: LoopDescriptor LoopContainerType can't contain unique_ptr 12e6860 Add barrier instructions validation pass 3ef4bb6 Avoid vector copies in range-for loops in opt/types.cpp 87f9cfa Disambiguate between const and nonconst ForEachSuccessorLabel bc1ec94 Add general folding infrastructure. 1c0056c Start v2018.1-dev c430a41 Finalize v2018.0 bcd4f23 Update CHANGES abe1132 Reordering performance passes ordering to produce better opts 50e85c8 Add LoopUtils class to gather some loop transformation support. 61d8c03 Add pass to reaplce invalid opcodes d37869c Added OpenCL ExtInst validation rules cd68f2b Add adjacency validation pass 905536c Fixed harmless uninit var warning ac537c7 Use SPIR-V headers from "unified1" directory 2735e08 Remove constexpr from Analysis operators 0aa0ac5 Opt: Add ScalarReplacement to RegisterSizePasses 44d88c8 Add memory semantics checks to validate atomics 38f297c Update CHANGES 1694923 Prevent unnecessary changes to the IR in dead branch elim c86cb76 Improved error message in val capabilities e661da7 Enhancements to block merging 6704233 Fix dereference of possibly nullptr f28b106 InsertExtractElim: Split out DeadInsertElim as separate pass 1b46f7e Fixes in CCP for GPUOpen-Drivers#1228 6018de8 Add LoopDescriptor as an IRContext analysis. 684997e DeadInsertElim: Detect and DCE dead Inserts 2e93e80 Initial implementation of if conversion b2eb840 Validator: restricted some atomic ops for shaders bdc7837 Added Vulkan-specifc checks to image validation c4835e1 Use id_map in Fold*ToConstant 6c409e3 Add generic folding function and use in CCP 3b780db Fixes infinite loop in ADCE cf3b2a5 Introduce an instruction builder helper class. 73940ab Simplifying code for adding instructions to worklist 34d4294 Create a pass to work around a driver bug related to OpUnreachable. 1861806 Adding testcase for GPUOpen-Drivers#1210 0b1372a CFG: force the creation of a predecessor entry for all basic block. 3604c0b spirv-dis: Add --color option to force color disassembly 5e70d20 Fixing missing early exit from break identification 80b743a Adding support for switch removal in ADCE 3a0eb44 Capturing value table by reference in local redundancy elim ae6daee Update CHANGES 5ffe862 Fixes missing increment in common uniform elim 6cc772c Skip SpecConstants in CCP. ba017f7 Update CHANGES c2aadb0 Add MatrixConstant 8cb0aec Remove redundant passes from legalization passes 6587d3f Adding early exit versions of several ForEach* methods 24f9947 Move initialization of the const mgr to the constructor. 86dec64 Start v2018.0-dev 902ed46 Finalize v2017.3 672494d Adding ostream operators for IR structures eb0c73d Maintain instruction to block mapping in phi insertion 5eafc00 InsertExtractElim: Optimize through VectorShuffle, Mix 1ebd860 Add generic folding function and use in CCP 3a054e1 Adding additional functionality to ADCE. d54a286 Fix validation rules for GLSL pack/unpack 2x32 1b6cfd3 Rewriting dead branch elimination. e5560d6 Fix constant propagation of induction variables. a82a0ea Fix method comment for BasicBlock::MegeBlockIdIfAny 44f27f9 Allow relaxing validation of pointers in logical addressing mode e8ad02f Add loop descriptors and some required dominator tree extensions. 6e9ea2e AnalyzeInstUse: Reuse the instruction lookup 3fbbd3c Remove CCP from size and performance recipes, pending bugfixes 7183ad5 Linker code cleanups ccb921d Allow getting the base pointer of an image load/store. 716718a Fix infinite simulation cycles in SSA propagator. 120ddff Ignore clang-format-diff.py from copyrights check ac9a828 dead branch elim: Track killed backedges c32e79e Add --print-all optimizer option 702852b Opt: Make DecorationManager::HaveTheSameDecorations symmetric a376b19 Validator checks out of bounds composite access 5b52626 Address review comments from KhronosGroup/SPIRV-Tools#985. 7834bee Update legalization passes e8f2890 Replace calls to `ToNop` by `KillInst`. 5f10078 Handle execution termination instructions when building edges. 135150a Do not insert Phi nodes in CCP propagator. 25d396b Add ExtInst validation pass (GLSL only for now) 226f263 Test: Fix linux/gcc defined-but-not-used warnings/errors b185a3d utils/generate_grammar_tables.py: use spaces for indentation 1acce99 Fix KhronosGroup/SPIRV-Tools#1130 a91aa53 Disallow Dim=SubpassData for OpImageSparseRead 59de610 Add asm, dis support for DebugInfo extended instruction set a27d673 CONTRIBUTING: If you fixed a bug, say so 4ba9dcc Implement SSA CCP (SSA Conditional Constant Propagation). 756b277 Store all enabled capabilities in the feature manger. 8e0051c Update CHANGES 1ab8ad6 Fixing bugs in type manager memory management 7505d24 Update the legalization passes. c9a881e Make a string parameter const ref 88409b7 Fix CHANGES: there is no OpImageSparseWrite 2e5672d Update CHANGES for recent changes 424f744 Opt: Fix implementation and comment of AreDecorationsTheSame Target should not be ignored when comparing decorations in RemoveDuplicates Opt: Remove unused code in RemoveDuplicateDecorations 79a0064 Allow pointers to pointers in logical addressing mode. b86eb68 Convert private variables to function scope. 8135dd6 More validation on primitive instructions 4dbcef6 validate & test of literal's upper bits f359635 Opt: Remove commented out duplicated type_id function 0d8ea48 Fix comment in primitives validation dbc3a66 Image Operand Sample allows sparse image opcodes 8c05012 Export a config file for pkg-config 0dbe184 Remove concept of FIRST_CONCRETE_* operand types 6169085 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. 7361034 Start v2017.3-dev 1ccfb58 Finalize v2017.2 0f80406 ADCE: Only mark true breaks and continues of live loops cdfbf26 Add primitive instruction validation pass af7d579 Refactor include of latest spir-v header versions 532b327 Add validation rules for atomic instructions 853a3d6 Fix uninitialized warning at -Os. 22faa2b ADCE: Empty Loop Elimination 07ce16d Set the parent for basic blocks during inlining. 2fc1221 Appveyor: stop testing on VS 2013 c520d43 Add validator checks for sparse image opcodes 12447d8 Support OpenCL 1.2 and 2.0 target environments 059fe08 AppVeyor: Put VS 2017 first 7ba59ac Force gtest to expose ::testing::Combine dbd8d0e Reenable OpCopyObject validation rules 867451f Add scalar replacement 78c025a MultiStore: Support OpVariable Initialization 70f88f5 Add external/SPIRV-Headers to .gitignore c6fdf68 SingleStore: Support OpVariable Initialization a05ad01 Add option to spirv-opt to skip the validator. 241dcac Add a new constant manager class. 5d602ab Add global redundancy elimination 851e1ad Kill names and decoration in inlining. 731d189 Add depth first iterator for trees 0c2396d Revert extraneous changes from commit 8ec62deb2. 8ba68fa Dominator Tree Analysis (GPUOpen-Drivers#3) 692a22c Sort flags in help message - NFC. b93c066 CMake: allow both SPIRV-Headers and spirv-headers 94e3e7b Add composite instruction validation pass 3b6c4f1 Do not zip and deploy for check formatting adb9396 Go back to root directory 235ef34 Travis CI: add clang-format check 1af6c4a Update .appveyor.yml bf18431 Fix some of the known issues in image validation fd3a220 DCEInst kill the same instruction twice. 726573a Change Release builds to Release with debug info on Linux e9ecc0c Remove cfg_ field from SSAPropagator class - NFC. 65046ec Change IRContext::KillInst to delete instructions. b35b52f Compute value number when the value table is constructed. b98254b Fixed typo that leaked to the binary 9996173 Add simplified instructions for pushing a reviewed PR. 22582fa Travis: mark MacOS builds as optional 2885c65 Re-format CONTRIBUTING.md - NFC. 0dd4ee2 Fix Dref type check in validator b8aeab8 Appveyor: use ninja instead of MSBuild 6904396 Opt: Remove unused lambda captures 1379535 Support outputting ANSI color escape sequences in library 188cd37 Erase decorations removed from internal collections 3c2e4c7 Fix validation of group ops in SPV_AMD_shader_ballot 8cfa0c4 Fix GPUOpen-Drivers#1034 - Give Edge::operator<() weak ordering semantics. e1ceff9 Validate OpTypeImage and OpTypeSampleImage 4c58086 Linker: Fix incorrect exit status. d78e11c Create CONTRIBUTING.md 8dd3d93 AggressiveDCE: Add merge and continue branches for live loop. 5f2589f Update README about the automatic master-tot relase 9f20799 Convert the CFG to an on-demand analysis - NFC. 8ffed97 Fix windows build. unsigned vs signed comparison in EXPECT_EQ. 7432784 Generic value propagation engine. 491b112 Fix windows build. 8322813 Re-format source tree - NFC. d8b2013 Derivative opcodes require Fragment exec model c170afd Relaxed OpImageWrite texel type check e1a6f8d Update CHANGES to mention fixes for 1007 and 1009 f84f266 Relaxed OpImageRead validation rules 0cae89e Notify the context of instructions that are being erased. 3e08a3f Add validation checks for Execution Model d9129f0 Test for pollution of the global namespace 0b1cb27 Remove derivative instructions from the list of combinators. b0a7037 Start v2017.2-dev 493c088 Finalize 2017.1 aec60b8 Add RegisterLegalizationPasses() into the interface 746bfd2 Adding new def -> use mapping container b02c9a5 Allow derived access chain without uses in access chain conversion ab892f7 Add derivatives validation pass c299927 Move SetContextMessageConsumer into libspirv namespace 28c4155 Create a local value numbering pass f407ae2 Validator pass for image instructions e28edd4 Optimize loads/stores on nested structs b142915 Fix move semantics in iterator make_range 250a235 Add new compression algorithm and models a771713 Adding an unique id to Instruction generated by IRContext 3214c3b Add dead function elimination to -O and -Os 4019bcf Fix hard-coded header path dbf9b37 Git should ignore external repos eb4653a Add the decoration manager to the IRContext. a92d69b Initial implementation of merge return pass. 0126ad9 Appveyor: skip building tags 919c990 Appveyor: Stop testing VS 2013/2015 Debug 98281ed Add analysis to compute mappings between instructions and basic blocks. a76d097 Fix decorations of inlined functions. 76555bd Tests: Add optional dependency on Effcee stateful matcher efe12ff Have all MemPasses preserve the def-use manager. 039c12f Travis: auto deploy build artifacts to GitHub Releases 651ba75 Appveyor: auto deploy build artifacts to GitHub Releases d2938e4 Re-format files in source, source/opt, source/util, source/val and tools. f32d11f Add the IRContext (part 2): Add def-use manager ac04b2f Opt: Fix HasLoads to not report decoration as load. d86c7ce Opt: Remove CommonUniformElimination from -O and -Os (for now) 1affe5a Describe public_spirv_tools_dev@khronos.org mailing list 2dddb81 Validate storage class of target pointer for OpStore 9d6cc26 Move class CFG from namespace opt to namespace ir. fef669f Add a new class opt::CFG to represent the CFG for the module. 476cae6 Add the IRContext (part 1) d861cef Add validation for OpBranchConditional 7299fb5 Lowered initial capacity of move-to-front sequence b1b4948 Fix copyright check when the build directory is in the source directory. 94bec26 ADCE: Dead if elimination 632e206 More re-factoring to simplify pass initialization. 716138e Add option to relax validation of store types. 6724c27 Compression: removed 'presumed index' feature f063f91 Use std::lower_bound for opcode lookup 1040a95 Re-factor Phi insertion code out of LocalMultiStoreElimPass 94dc66b Change the sections in the module to use the InstructionList class. 063dbea Turn all function static non-POD variables into global POD variables git-pf-change: stg@1521268

dnovillo self-assigned this Nov 20, 2017

dnovillo requested review from alan-baker and s-perron November 20, 2017 15:49

atgoo reviewed Nov 20, 2017

View reviewed changes

s-perron reviewed Nov 20, 2017

View reviewed changes

atgoo reviewed Nov 20, 2017

View reviewed changes

s-perron requested changes Nov 20, 2017

View reviewed changes

alan-baker reviewed Nov 20, 2017

View reviewed changes

atgoo reviewed Nov 20, 2017

View reviewed changes

dnovillo force-pushed the const-prop branch from 8186ab8 to 1ba34a7 Compare November 21, 2017 19:14

dnovillo commented Nov 21, 2017

View reviewed changes

atgoo reviewed Nov 21, 2017

View reviewed changes

alan-baker reviewed Nov 22, 2017

View reviewed changes

alan-baker requested changes Nov 22, 2017

View reviewed changes

s-perron reviewed Nov 23, 2017

View reviewed changes

s-perron requested changes Nov 23, 2017

View reviewed changes

dnovillo force-pushed the const-prop branch from aa774ab to b0d1dd3 Compare November 23, 2017 21:59

s-perron approved these changes Nov 24, 2017

View reviewed changes

dnovillo force-pushed the const-prop branch from 881f65e to 8828813 Compare November 27, 2017 18:19

dnovillo mentioned this pull request Nov 27, 2017

OpSwitch not removed by ADCE #1021

Closed

dnovillo force-pushed the const-prop branch 2 times, most recently from c15be81 to e6d2efd Compare November 27, 2017 22:01

alan-baker approved these changes Nov 28, 2017

View reviewed changes

dnovillo force-pushed the const-prop branch from e6d2efd to 7432784 Compare November 28, 2017 04:32

dnovillo merged commit 7432784 into KhronosGroup:master Nov 28, 2017

This was referenced Nov 28, 2017

Unify computation of CFG edges #1025

Closed

Implement a propagation engine #895

Closed

Add CFG edge data structure #894

Closed

dnovillo mentioned this pull request Dec 15, 2017

Implement SSA CCP (SSA Conditional Constant Propagation) #1102

Merged

dneto0 reviewed Jan 3, 2018

View reviewed changes

dnovillo added a commit to dnovillo/SPIRV-Tools that referenced this pull request Jan 4, 2018

Address review comments from KhronosGroup#985.

5b52626

dnovillo mentioned this pull request Jan 4, 2018

Address review comments from #985 #1163

Merged

dnovillo commented Jan 4, 2018

View reviewed changes

dneto0 pushed a commit to dneto0/SPIRV-Tools that referenced this pull request Sep 14, 2024

Add newline to logging messages to make them readable (KhronosGroup#985)

738f165


		using VisitFunction = std::function<PropStatus(ir::Instruction*)>;

		SSAPropagator(ir::IRContext* context, ir::CFG* cfg, VisitFunction& visit_fn)

Conversation

dnovillo commented Nov 20, 2017

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

s-perron left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!