From 64e5a99ee014af3a138a36f5a87addfacfc95f0c Mon Sep 17 00:00:00 2001
From: Thomas Lively <tlively@google.com>
Date: Fri, 12 May 2023 11:27:29 -0500
Subject: [analysis] Add a new iterable CFG utility (#5712)

Add a new "analysis" source directory that will contain the source for a new
static program analysis framework. To start the framework, add a CFG utility
that provides convenient iterators for iterating through the basic blocks of the
CFG as well as the predecessors, successors, and contents of each block.

The new CFGs are constructed using the existing CFGWalker, but they are
different in that the new utility is meant to provide a usable representation of
a CFG whereas CFGWalker is meant to allow collecting arbitrary information about
each basic block in a CFG.

For testing and debugging purposes, add `print` methods to CFGs and basic
blocks. This requires exposing the ability to print expression contents
excluding children, which was something we previously did only for StackIR.

Also add a new gtest file with a test for constructing and printing a CFG. The
test reveals some strange properties of the current CFG construction, including
empty blocks and strange placement of `loop` instructions, but fixing these
problems is left as future work.
---
 src/analysis/cfg.cpp | 106 +++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 106 insertions(+)
 create mode 100644 src/analysis/cfg.cpp

(limited to 'src/analysis/cfg.cpp')

diff --git a/src/analysis/cfg.cpp b/src/analysis/cfg.cpp
new file mode 100644
index 000000000..7d770776d
--- /dev/null
+++ b/src/analysis/cfg.cpp
@@ -0,0 +1,106 @@
+/*
+ * Copyright 2023 WebAssembly Community Group participants
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include <unordered_map>
+
+#include "analysis/cfg.h"
+#include "cfg/cfg-traversal.h"
+#include "wasm-stack.h"
+
+namespace wasm::analysis {
+
+CFG CFG::fromFunction(Function* func) {
+  struct CFGBuilder : CFGWalker<CFGBuilder,
+                                UnifiedExpressionVisitor<CFGBuilder>,
+                                std::vector<Expression*>> {
+    void visitExpression(Expression* curr) {
+      if (currBasicBlock) {
+        currBasicBlock->contents.push_back(curr);
+      }
+    }
+  };
+
+  CFGBuilder builder;
+  builder.walkFunction(func);
+
+  size_t numBlocks = builder.basicBlocks.size();
+
+  CFG cfg;
+  cfg.blocks = std::vector<BasicBlock>(numBlocks);
+
+  // From here the addresses of the new basic blocks are stable.
+  std::unordered_map<CFGBuilder::BasicBlock*, BasicBlock*> oldToNewBlocks;
+  for (size_t i = 0; i < numBlocks; ++i) {
+    oldToNewBlocks[builder.basicBlocks[i].get()] = &cfg.blocks[i];
+  }
+
+  for (size_t i = 0; i < numBlocks; ++i) {
+    auto& oldBlock = *builder.basicBlocks[i];
+    auto& newBlock = cfg.blocks[i];
+    newBlock.index = i;
+    newBlock.insts = std::move(oldBlock.contents);
+    newBlock.predecessors.reserve(oldBlock.in.size());
+    for (auto* oldPred : oldBlock.in) {
+      newBlock.predecessors.push_back(oldToNewBlocks.at(oldPred));
+    }
+    newBlock.successors.reserve(oldBlock.out.size());
+    for (auto* oldSucc : oldBlock.out) {
+      newBlock.successors.push_back(oldToNewBlocks.at(oldSucc));
+    }
+  }
+
+  // Move-construct a new CFG to get mandatory copy elision, preserving basic
+  // block addresses through the return.
+  return CFG(std::move(cfg));
+}
+
+void CFG::print(std::ostream& os, Module* wasm) const {
+  size_t start = 0;
+  for (auto& block : *this) {
+    if (&block != &*begin()) {
+      os << '\n';
+    }
+    block.print(os, wasm, start);
+    start += block.size();
+  }
+}
+
+void BasicBlock::print(std::ostream& os, Module* wasm, size_t start) const {
+  os << ";; preds: [";
+  for (auto& pred : preds()) {
+    if (&pred != &*preds().begin()) {
+      os << ", ";
+    }
+    os << pred.index;
+  }
+  os << "], succs: [";
+
+  for (auto& succ : succs()) {
+    if (&succ != &*succs().begin()) {
+      os << ", ";
+    }
+    os << succ.index;
+  }
+  os << "]\n";
+
+  os << index << ":\n";
+  size_t instIndex = start;
+  for (auto* inst : *this) {
+    os << "  " << instIndex++ << ": " << ShallowExpression{inst, wasm} << '\n';
+  }
+}
+
+} // namespace wasm::analysis
-- 
cgit v1.2.3