Make use of the instruction folder.

Implementation of the simplification pass.

- Create pass that calls the instruction folder on each instruction and
  propagate instructions that fold to a copy.  This will do copy
  propagation as well.

- Did not use the propagator engine because I want to modify the instruction
  as we go along.

- Change folding to not allocate new instructions, but make changes in
  place.  This change had a big impact on compile time.

- Add simplification pass to the legalization passes in place of
  insert-extract elimination.

- Added test cases for new folding rules.

- Added tests for the simplification pass

- Added a method to the CFG to apply a function to the basic blocks in
  reverse post order.

Contributes to #1164.

1 files changed, 14 insertions, 0 deletions

diff --git a/source/opt/cfg.h b/source/opt/cfg.h
index 138aa0a6..53dddd23 100644
--- a/source/opt/cfg.h
+++ b/source/opt/cfg.h
@@ -19,6 +19,7 @@
 
 #include <list>
 #include <unordered_map>
+#include <unordered_set>
 
 namespace spvtools {
 namespace ir {
@@ -68,6 +69,12 @@ class CFG {
   void ComputeStructuredOrder(ir::Function* func, ir::BasicBlock* root,
                               std::list<ir::BasicBlock*>* order);
 
+  // Applies |f| to the basic block in reverse post order starting with |bb|.
+  // Note that basic blocks that cannot be reached from |bb| node will not be
+  // processed.
+  void ForEachBlockInReversePostOrder(
+      BasicBlock* bb, const std::function<void(BasicBlock*)>& f);
+
   // Registers |blk| as a basic block in the cfg, this also updates the
   // predecessor lists of each successor of |blk|.
   void RegisterBlock(ir::BasicBlock* blk) {
@@ -101,6 +108,13 @@ class CFG {
   // ignored by DFS.
   void ComputeStructuredSuccessors(ir::Function* func);
 
+  // Computes the post-order traversal of the cfg starting at |bb| skipping
+  // nodes in |seen|.  The order of the traversal is appended to |order|, and
+  // all nodes in the traversal are added to |seen|.
+  void ComputePostOrderTraversal(BasicBlock* bb,
+                                 std::vector<BasicBlock*>* order,
+                                 std::unordered_set<BasicBlock*>* seen);
+
   // Module for this CFG.
   ir::Module* module_;