WebAssembly: relooper analysis pass

[jfb]

Summary

Make the relooper an analysis pass, to convert CFG to AST.

[jfb]

This isn't meant for review as it's currently broken. @sunfish is working on a separate approach in D12735, which we may decide to go with instead.

[jfb]

• Unhook.

[jfb]

@sunfish and I discussed moving the relooper and his stackifier forward (D12735). We'll first use the stackifier, and may fill in with the relooper where it makes sense, or at least perform Science and compare their results. This patch moves us ever-so-slightly in that direction, so I'll commit as is, and we'll come back to the relooper when needed (we're trying to get basics up and running first!).

[jfb]

I just realized that I hadn't committed this. We may not go forward with the relooper, but we do want to compare our options so I'd rather at least get this small patch in.

llvm/trunk/lib/Target/WebAssembly/Relooper.h

 //===-- Relooper.h - Top-level interface for WebAssembly  ----*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===-------------------------------------------------------------------===//
 ///
 /// \file
 /// \brief This defines an optimized C++ implemention of the Relooper
 /// algorithm, originally developed as part of Emscripten, which
 /// generates a structured AST from arbitrary control flow.
 ///
 //===-------------------------------------------------------------------===//
 
-#include <llvm/ADT/MapVector.h>
-#include <llvm/ADT/SetVector.h>
-#include <llvm/Support/Casting.h>
+#include "llvm/ADT/MapVector.h"
+#include "llvm/ADT/SetVector.h"
+#include "llvm/Support/Casting.h"
 
 #include <cassert>
-#include <cstdio>
 #include <cstdarg>
+#include <cstdio>
 #include <deque>
 #include <list>
 #include <map>
 #include <memory>
 #include <set>
 
 namespace llvm {
 

 struct LoopShape : public LabeledShape {
   Shape *Inner;
 
   LoopShape() : LabeledShape(SK_Loop), Inner(nullptr) {}
 
   static bool classof(const Shape *S) { return S->getKind() == SK_Loop; }
 };
 
-///
-/// Implements the relooper algorithm for a function's blocks.
-///
-/// Implementation details: The Relooper instance has
-/// ownership of the blocks and shapes, and frees them when done.
-///
-struct Relooper {
-  std::deque<Block *> Blocks;
-  std::deque<Shape *> Shapes;
-  Shape *Root;
-  bool MinSize;
-  int BlockIdCounter;
-  int ShapeIdCounter;
-
-  Relooper();
-  ~Relooper();
-
-  void AddBlock(Block *New, int Id = -1);
-
-  // Calculates the shapes
-  void Calculate(Block *Entry);
-
-  // Sets us to try to minimize size
-  void SetMinSize(bool MinSize_) { MinSize = MinSize_; }
-};
-
-typedef MapVector<Block *, BlockSet> BlockBlockSetMap;
-
 } // namespace Relooper
 
 } // namespace llvm

llvm/trunk/lib/Target/WebAssembly/Relooper.cpp

 /// Proceedings of the ACM international conference companion on Object
 /// oriented programming systems languages and applications companion
 /// (SPLASH '11). ACM, New York, NY, USA, 301-312. DOI=10.1145/2048147.2048224
 /// http://doi.acm.org/10.1145/2048147.2048224
 ///
 //===-------------------------------------------------------------------===//
 
 #include "Relooper.h"
+#include "WebAssembly.h"
 
-#include <llvm/ADT/STLExtras.h>
-#include <llvm/Support/raw_ostream.h>
-#include <llvm/Support/CommandLine.h>
+#include "llvm/ADT/STLExtras.h"
+#include "llvm/IR/CFG.h"
+#include "llvm/IR/Function.h"
+#include "llvm/Pass.h"
+#include "llvm/Support/CommandLine.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/Support/raw_ostream.h"
 
 #include <cstring>
 #include <cstdlib>
 #include <functional>
 #include <list>
 #include <stack>
 #include <string>
 
+#define DEBUG_TYPE "relooper"
+
 using namespace llvm;
+using namespace Relooper;
 
 static cl::opt<int> RelooperSplittingFactor(
     "relooper-splitting-factor",
     cl::desc(
         "How much to discount code size when deciding whether to split a node"),
     cl::init(5));
 
 static cl::opt<unsigned> RelooperMultipleSwitchThreshold(
     "relooper-multiple-switch-threshold",
     cl::desc(
         "How many entries to allow in a multiple before we use a switch"),
     cl::init(10));
 
 static cl::opt<unsigned> RelooperNestingLimit(
     "relooper-nesting-limit",
     cl::desc(
         "How much nesting is acceptable"),
     cl::init(20));
 
-namespace llvm {
 
-namespace Relooper {
+namespace {
+///
+/// Implements the relooper algorithm for a function's blocks.
+///
+/// Implementation details: The Relooper instance has
+/// ownership of the blocks and shapes, and frees them when done.
+///
+struct RelooperAlgorithm {
+  std::deque<Block *> Blocks;
+  std::deque<Shape *> Shapes;
+  Shape *Root;
+  bool MinSize;
+  int BlockIdCounter;
+  int ShapeIdCounter;
+
+  RelooperAlgorithm();
+  ~RelooperAlgorithm();
+
+  void AddBlock(Block *New, int Id = -1);
+
+  // Calculates the shapes
+  void Calculate(Block *Entry);
+
+  // Sets us to try to minimize size
+  void SetMinSize(bool MinSize_) { MinSize = MinSize_; }
+};
+
+struct RelooperAnalysis final : public FunctionPass {
+  static char ID;
+  RelooperAnalysis() : FunctionPass(ID) {}
+  const char *getPassName() const override { return "relooper"; }
+  void getAnalysisUsage(AnalysisUsage &AU) const override {
+    AU.setPreservesAll();
+  }
+  bool runOnFunction(Function &F) override;
+};
+}
+
+// RelooperAnalysis
+
+char RelooperAnalysis::ID = 0;
+FunctionPass *llvm::createWebAssemblyRelooper() {
+  return new RelooperAnalysis();
+}
+
+bool RelooperAnalysis::runOnFunction(Function &F) {
+  DEBUG(dbgs() << "Relooping function '" << F.getName() << "'\n");
+  RelooperAlgorithm R;
+  // FIXME: remove duplication between relooper's and LLVM's BBs.
+  std::map<const BasicBlock *, Block *> BB2B;
+  std::map<const Block *, const BasicBlock *> B2BB;
+  for (const BasicBlock &BB : F) {
+    // FIXME: getName is wrong here, Code is meant to represent amount of code.
+    // FIXME: use BranchVarInit for switch.
+    Block *B = new Block(BB.getName().str().data(), /*BranchVarInit=*/nullptr);
+    R.AddBlock(B);
+    assert(BB2B.find(&BB) == BB2B.end() && "Inserting the same block twice");
+    assert(B2BB.find(B) == B2BB.end() && "Inserting the same block twice");
+    BB2B[&BB] = B;
+    B2BB[B] = &BB;
+  }
+  for (Block *B : R.Blocks) {
+    const BasicBlock *BB = B2BB[B];
+    for (const BasicBlock *Successor : successors(BB))
+      // FIXME: add branch's Condition and Code below.
+      B->AddBranchTo(BB2B[Successor], /*Condition=*/nullptr, /*Code=*/nullptr);
+  }
+  R.Calculate(BB2B[&F.getEntryBlock()]);
+  return false; // Analysis passes don't modify anything.
+}
+
+// Helpers
+
+typedef MapVector<Block *, BlockSet> BlockBlockSetMap;
+typedef std::list<Block *> BlockList;
 
 template <class T, class U>
 static bool contains(const T &container, const U &contained) {
   return container.count(contained);
 }
 
+
 // Branch
 
 Branch::Branch(const char *ConditionInit, const char *CodeInit)
     : Ancestor(nullptr), Labeled(true) {
   // FIXME: move from char* to LLVM data structures
   Condition = ConditionInit ? strdup(ConditionInit) : nullptr;
   Code = CodeInit ? strdup(CodeInit) : nullptr;
 }

 Block::~Block() {
   // FIXME: move from char* to LLVM data structures
   free(static_cast<void *>(const_cast<char *>(Code)));
   free(static_cast<void *>(const_cast<char *>(BranchVar)));
 }
 
 void Block::AddBranchTo(Block *Target, const char *Condition,
                         const char *Code) {
-  assert(
-      !contains(BranchesOut,
-                Target)); // cannot add more than one branch to the same target
+  assert(!contains(BranchesOut, Target) &&
+         "cannot add more than one branch to the same target");
   BranchesOut[Target] = make_unique<Branch>(Condition, Code);
 }
 
 // Relooper
 
-Relooper::Relooper()
+RelooperAlgorithm::RelooperAlgorithm()
     : Root(nullptr), MinSize(false), BlockIdCounter(1),
       ShapeIdCounter(0) { // block ID 0 is reserved for clearings
 }
 
-Relooper::~Relooper() {
+RelooperAlgorithm::~RelooperAlgorithm() {
   for (auto Curr : Blocks)
     delete Curr;
   for (auto Curr : Shapes)
     delete Curr;
 }
 
-void Relooper::AddBlock(Block *New, int Id) {
+void RelooperAlgorithm::AddBlock(Block *New, int Id) {
   New->Id = Id == -1 ? BlockIdCounter++ : Id;
   Blocks.push_back(New);
 }
 
 struct RelooperRecursor {
-  Relooper *Parent;
-  RelooperRecursor(Relooper *ParentInit) : Parent(ParentInit) {}
+  RelooperAlgorithm *Parent;
+  RelooperRecursor(RelooperAlgorithm *ParentInit) : Parent(ParentInit) {}
 };
 
-typedef std::list<Block *> BlockList;
-
-void Relooper::Calculate(Block *Entry) {
+void RelooperAlgorithm::Calculate(Block *Entry) {
   // Scan and optimize the input
   struct PreOptimizer : public RelooperRecursor {
-    PreOptimizer(Relooper *Parent) : RelooperRecursor(Parent) {}
+    PreOptimizer(RelooperAlgorithm *Parent) : RelooperRecursor(Parent) {}
     BlockSet Live;
 
     void FindLive(Block *Root) {
       BlockList ToInvestigate;
       ToInvestigate.push_back(Root);
       while (!ToInvestigate.empty()) {
         Block *Curr = ToInvestigate.front();
         ToInvestigate.pop_front();
void SplitDeadEnds() {
         if (contains(Original->BranchesOut, Original))
           continue; // cannot split a looping node
         if (strlen(Original->Code) * (Original->BranchesIn.size() - 1) >
             TotalCodeSize / RelooperSplittingFactor)
           continue; // if splitting increases raw code size by a significant
                     // amount, abort
         // Split the node (for simplicity, we replace all the blocks, even
         // though we could have reused the original)
+        DEBUG(dbgs() << "  Splitting '" << Original->Code << "'\n");
         for (const auto &Prior : Original->BranchesIn) {
           Block *Split = new Block(Original->Code, Original->BranchVar);
           Parent->AddBlock(Split, Original->Id);
           Split->BranchesIn.insert(Prior);
           std::unique_ptr<Branch> Details;
           Details.swap(Prior->BranchesOut[Original]);
           Prior->BranchesOut[Split] = make_unique<Branch>(Details->Condition,
                                                           Details->Code);
void RelooperAlgorithm::Calculate(Block *Entry) {
   }
 
   if (!MinSize)
     Pre.SplitDeadEnds();
 
   // Recursively process the graph
 
   struct Analyzer : public RelooperRecursor {
-    Analyzer(Relooper *Parent) : RelooperRecursor(Parent) {}
+    Analyzer(RelooperAlgorithm *Parent) : RelooperRecursor(Parent) {}
 
     // Add a shape to the list of shapes in this Relooper calculation
     void Notice(Shape *New) {
       New->Id = Parent->ShapeIdCounter++;
       Parent->Shapes.push_back(New);
     }
 
     // Create a list of entries from a block. If LimitTo is provided, only
     // results in that set will appear
     void GetBlocksOut(Block *Source, BlockSet &Entries,
                       BlockSet *LimitTo = nullptr) {
       for (const auto &iter : Source->BranchesOut)
         if (!LimitTo || contains(*LimitTo, iter.first))
           Entries.insert(iter.first);
     }
 
     // Converts/processes all branchings to a specific target
     void Solipsize(Block *Target, Branch::FlowType Type, Shape *Ancestor,
                    BlockSet &From) {
+      DEBUG(dbgs() << "  Solipsize '" << Target->Code << "' type " << Type
+                   << "\n");
       for (auto iter = Target->BranchesIn.begin();
            iter != Target->BranchesIn.end();) {
         Block *Prior = *iter;
         if (!contains(From, Prior)) {
           iter++;
           continue;
         }
         std::unique_ptr<Branch> PriorOut;
         PriorOut.swap(Prior->BranchesOut[Target]);
         PriorOut->Ancestor = Ancestor;
         PriorOut->Type = Type;
         if (MultipleShape *Multiple = dyn_cast<MultipleShape>(Ancestor))
           Multiple->Breaks++; // We are breaking out of this Multiple, so need a
                               // loop
         iter++; // carefully increment iter before erasing
         Target->BranchesIn.remove(Prior);
         Target->ProcessedBranchesIn.insert(Prior);
         Prior->ProcessedBranchesOut[Target].swap(PriorOut);
       }
     }
 
     Shape *MakeSimple(BlockSet &Blocks, Block *Inner, BlockSet &NextEntries) {
+      DEBUG(dbgs() << "  MakeSimple inner block '" << Inner->Code << "'\n");
       SimpleShape *Simple = new SimpleShape;
       Notice(Simple);
       Simple->Inner = Inner;
       Inner->Parent = Simple;
       if (Blocks.size() > 1) {
         Blocks.remove(Inner);
         GetBlocksOut(Inner, NextEntries, &Blocks);
         BlockSet JustInner;
void RelooperAlgorithm::Calculate(Block *Entry) {
   Entries.insert(Entry);
   Root = Analyzer(this).Process(AllBlocks, Entries, nullptr);
   assert(Root);
 
   ///
   /// Relooper post-optimizer
   ///
   struct PostOptimizer {
-    Relooper *Parent;
+    RelooperAlgorithm *Parent;
     std::stack<Shape *> LoopStack;
 
-    PostOptimizer(Relooper *ParentInit) : Parent(ParentInit) {}
+    PostOptimizer(RelooperAlgorithm *ParentInit) : Parent(ParentInit) {}
 
     void ShapeSwitch(Shape* var,
                      std::function<void (SimpleShape*)> simple,
                      std::function<void (MultipleShape*)> multiple,
                      std::function<void (LoopShape*)> loop) {
       switch (var->getKind()) {
         case Shape::SK_Simple: {
           simple(cast<SimpleShape>(var));
void Process(Shape * Root) {
       FindNaturals(Root);
       RemoveUnneededFlows(Root);
       FindLabeledLoops(Root);
     }
   };
 
   PostOptimizer(this).Process(Root);
 }
-
-} // namespace Relooper
-
-} // namespace llvm

llvm/trunk/lib/Target/WebAssembly/WebAssembly.h

 class WebAssemblyTargetMachine;
 class FunctionPass;
 
 FunctionPass *createWebAssemblyISelDag(WebAssemblyTargetMachine &TM,
                                        CodeGenOpt::Level OptLevel);
 
 FunctionPass *createWebAssemblyCFGStackify();
 
+FunctionPass *createWebAssemblyRelooper();
+
 } // end namespace llvm
 
 #endif