Skip to content

Commit 53bd975

Browse files
jfbastienjfbastien
committedOct 16, 2015
WebAssembly: relooper analysis pass
Summary: Make the relooper an analysis pass, to convert CFG to AST. Reviewers: sunfish Subscribers: jfb, dschuff Differential Revision: http://reviews.llvm.org/D12744 llvm-svn: 250524
·
llvmorg-21-initllvmorg-3.8.0-rc1
1 parent 2918904 commit 53bd975

File tree

3 files changed

+109
-56
lines changed

3 files changed

+109
-56
lines changed
 

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

+103-24
Original file line numberDiff line numberDiff line change
@@ -20,10 +20,15 @@
2020
//===-------------------------------------------------------------------===//
2121

2222
#include "Relooper.h"
23+
#include "WebAssembly.h"
2324

24-
#include <llvm/ADT/STLExtras.h>
25-
#include <llvm/Support/raw_ostream.h>
26-
#include <llvm/Support/CommandLine.h>
25+
#include "llvm/ADT/STLExtras.h"
26+
#include "llvm/IR/CFG.h"
27+
#include "llvm/IR/Function.h"
28+
#include "llvm/Pass.h"
29+
#include "llvm/Support/CommandLine.h"
30+
#include "llvm/Support/Debug.h"
31+
#include "llvm/Support/raw_ostream.h"
2732

2833
#include <cstring>
2934
#include <cstdlib>
@@ -32,7 +37,10 @@
3237
#include <stack>
3338
#include <string>
3439

40+
#define DEBUG_TYPE "relooper"
41+
3542
using namespace llvm;
43+
using namespace Relooper;
3644

3745
static cl::opt<int> RelooperSplittingFactor(
3846
"relooper-splitting-factor",
@@ -52,15 +60,89 @@ static cl::opt<unsigned> RelooperNestingLimit(
5260
"How much nesting is acceptable"),
5361
cl::init(20));
5462

55-
namespace llvm {
5663

57-
namespace Relooper {
64+
namespace {
65+
///
66+
/// Implements the relooper algorithm for a function's blocks.
67+
///
68+
/// Implementation details: The Relooper instance has
69+
/// ownership of the blocks and shapes, and frees them when done.
70+
///
71+
struct RelooperAlgorithm {
72+
std::deque<Block *> Blocks;
73+
std::deque<Shape *> Shapes;
74+
Shape *Root;
75+
bool MinSize;
76+
int BlockIdCounter;
77+
int ShapeIdCounter;
78+
79+
RelooperAlgorithm();
80+
~RelooperAlgorithm();
81+
82+
void AddBlock(Block *New, int Id = -1);
83+
84+
// Calculates the shapes
85+
void Calculate(Block *Entry);
86+
87+
// Sets us to try to minimize size
88+
void SetMinSize(bool MinSize_) { MinSize = MinSize_; }
89+
};
90+
91+
struct RelooperAnalysis final : public FunctionPass {
92+
static char ID;
93+
RelooperAnalysis() : FunctionPass(ID) {}
94+
const char *getPassName() const override { return "relooper"; }
95+
void getAnalysisUsage(AnalysisUsage &AU) const override {
96+
AU.setPreservesAll();
97+
}
98+
bool runOnFunction(Function &F) override;
99+
};
100+
}
101+
102+
// RelooperAnalysis
103+
104+
char RelooperAnalysis::ID = 0;
105+
FunctionPass *llvm::createWebAssemblyRelooper() {
106+
return new RelooperAnalysis();
107+
}
108+
109+
bool RelooperAnalysis::runOnFunction(Function &F) {
110+
DEBUG(dbgs() << "Relooping function '" << F.getName() << "'\n");
111+
RelooperAlgorithm R;
112+
// FIXME: remove duplication between relooper's and LLVM's BBs.
113+
std::map<const BasicBlock *, Block *> BB2B;
114+
std::map<const Block *, const BasicBlock *> B2BB;
115+
for (const BasicBlock &BB : F) {
116+
// FIXME: getName is wrong here, Code is meant to represent amount of code.
117+
// FIXME: use BranchVarInit for switch.
118+
Block *B = new Block(BB.getName().str().data(), /*BranchVarInit=*/nullptr);
119+
R.AddBlock(B);
120+
assert(BB2B.find(&BB) == BB2B.end() && "Inserting the same block twice");
121+
assert(B2BB.find(B) == B2BB.end() && "Inserting the same block twice");
122+
BB2B[&BB] = B;
123+
B2BB[B] = &BB;
124+
}
125+
for (Block *B : R.Blocks) {
126+
const BasicBlock *BB = B2BB[B];
127+
for (const BasicBlock *Successor : successors(BB))
128+
// FIXME: add branch's Condition and Code below.
129+
B->AddBranchTo(BB2B[Successor], /*Condition=*/nullptr, /*Code=*/nullptr);
130+
}
131+
R.Calculate(BB2B[&F.getEntryBlock()]);
132+
return false; // Analysis passes don't modify anything.
133+
}
134+
135+
// Helpers
136+
137+
typedef MapVector<Block *, BlockSet> BlockBlockSetMap;
138+
typedef std::list<Block *> BlockList;
58139

59140
template <class T, class U>
60141
static bool contains(const T &container, const U &contained) {
61142
return container.count(contained);
62143
}
63144

145+
64146
// Branch
65147

66148
Branch::Branch(const char *ConditionInit, const char *CodeInit)
@@ -93,42 +175,39 @@ Block::~Block() {
93175

94176
void Block::AddBranchTo(Block *Target, const char *Condition,
95177
const char *Code) {
96-
assert(
97-
!contains(BranchesOut,
98-
Target)); // cannot add more than one branch to the same target
178+
assert(!contains(BranchesOut, Target) &&
179+
"cannot add more than one branch to the same target");
99180
BranchesOut[Target] = make_unique<Branch>(Condition, Code);
100181
}
101182

102183
// Relooper
103184

104-
Relooper::Relooper()
185+
RelooperAlgorithm::RelooperAlgorithm()
105186
: Root(nullptr), MinSize(false), BlockIdCounter(1),
106187
ShapeIdCounter(0) { // block ID 0 is reserved for clearings
107188
}
108189

109-
Relooper::~Relooper() {
190+
RelooperAlgorithm::~RelooperAlgorithm() {
110191
for (auto Curr : Blocks)
111192
delete Curr;
112193
for (auto Curr : Shapes)
113194
delete Curr;
114195
}
115196

116-
void Relooper::AddBlock(Block *New, int Id) {
197+
void RelooperAlgorithm::AddBlock(Block *New, int Id) {
117198
New->Id = Id == -1 ? BlockIdCounter++ : Id;
118199
Blocks.push_back(New);
119200
}
120201

121202
struct RelooperRecursor {
122-
Relooper *Parent;
123-
RelooperRecursor(Relooper *ParentInit) : Parent(ParentInit) {}
203+
RelooperAlgorithm *Parent;
204+
RelooperRecursor(RelooperAlgorithm *ParentInit) : Parent(ParentInit) {}
124205
};
125206

126-
typedef std::list<Block *> BlockList;
127-
128-
void Relooper::Calculate(Block *Entry) {
207+
void RelooperAlgorithm::Calculate(Block *Entry) {
129208
// Scan and optimize the input
130209
struct PreOptimizer : public RelooperRecursor {
131-
PreOptimizer(Relooper *Parent) : RelooperRecursor(Parent) {}
210+
PreOptimizer(RelooperAlgorithm *Parent) : RelooperRecursor(Parent) {}
132211
BlockSet Live;
133212

134213
void FindLive(Block *Root) {
@@ -169,6 +248,7 @@ void Relooper::Calculate(Block *Entry) {
169248
// amount, abort
170249
// Split the node (for simplicity, we replace all the blocks, even
171250
// though we could have reused the original)
251+
DEBUG(dbgs() << " Splitting '" << Original->Code << "'\n");
172252
for (const auto &Prior : Original->BranchesIn) {
173253
Block *Split = new Block(Original->Code, Original->BranchVar);
174254
Parent->AddBlock(Split, Original->Id);
@@ -216,7 +296,7 @@ void Relooper::Calculate(Block *Entry) {
216296
// Recursively process the graph
217297

218298
struct Analyzer : public RelooperRecursor {
219-
Analyzer(Relooper *Parent) : RelooperRecursor(Parent) {}
299+
Analyzer(RelooperAlgorithm *Parent) : RelooperRecursor(Parent) {}
220300

221301
// Add a shape to the list of shapes in this Relooper calculation
222302
void Notice(Shape *New) {
@@ -236,6 +316,8 @@ void Relooper::Calculate(Block *Entry) {
236316
// Converts/processes all branchings to a specific target
237317
void Solipsize(Block *Target, Branch::FlowType Type, Shape *Ancestor,
238318
BlockSet &From) {
319+
DEBUG(dbgs() << " Solipsize '" << Target->Code << "' type " << Type
320+
<< "\n");
239321
for (auto iter = Target->BranchesIn.begin();
240322
iter != Target->BranchesIn.end();) {
241323
Block *Prior = *iter;
@@ -258,6 +340,7 @@ void Relooper::Calculate(Block *Entry) {
258340
}
259341

260342
Shape *MakeSimple(BlockSet &Blocks, Block *Inner, BlockSet &NextEntries) {
343+
DEBUG(dbgs() << " MakeSimple inner block '" << Inner->Code << "'\n");
261344
SimpleShape *Simple = new SimpleShape;
262345
Notice(Simple);
263346
Simple->Inner = Inner;
@@ -649,10 +732,10 @@ void Relooper::Calculate(Block *Entry) {
649732
/// Relooper post-optimizer
650733
///
651734
struct PostOptimizer {
652-
Relooper *Parent;
735+
RelooperAlgorithm *Parent;
653736
std::stack<Shape *> LoopStack;
654737

655-
PostOptimizer(Relooper *ParentInit) : Parent(ParentInit) {}
738+
PostOptimizer(RelooperAlgorithm *ParentInit) : Parent(ParentInit) {}
656739

657740
void ShapeSwitch(Shape* var,
658741
std::function<void (SimpleShape*)> simple,
@@ -900,7 +983,3 @@ void Relooper::Calculate(Block *Entry) {
900983

901984
PostOptimizer(this).Process(Root);
902985
}
903-
904-
} // namespace Relooper
905-
906-
} // namespace llvm

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

+4-32
Original file line numberDiff line numberDiff line change
@@ -14,13 +14,13 @@
1414
///
1515
//===-------------------------------------------------------------------===//
1616

17-
#include <llvm/ADT/MapVector.h>
18-
#include <llvm/ADT/SetVector.h>
19-
#include <llvm/Support/Casting.h>
17+
#include "llvm/ADT/MapVector.h"
18+
#include "llvm/ADT/SetVector.h"
19+
#include "llvm/Support/Casting.h"
2020

2121
#include <cassert>
22-
#include <cstdio>
2322
#include <cstdarg>
23+
#include <cstdio>
2424
#include <deque>
2525
#include <list>
2626
#include <map>
@@ -181,34 +181,6 @@ struct LoopShape : public LabeledShape {
181181
static bool classof(const Shape *S) { return S->getKind() == SK_Loop; }
182182
};
183183

184-
///
185-
/// Implements the relooper algorithm for a function's blocks.
186-
///
187-
/// Implementation details: The Relooper instance has
188-
/// ownership of the blocks and shapes, and frees them when done.
189-
///
190-
struct Relooper {
191-
std::deque<Block *> Blocks;
192-
std::deque<Shape *> Shapes;
193-
Shape *Root;
194-
bool MinSize;
195-
int BlockIdCounter;
196-
int ShapeIdCounter;
197-
198-
Relooper();
199-
~Relooper();
200-
201-
void AddBlock(Block *New, int Id = -1);
202-
203-
// Calculates the shapes
204-
void Calculate(Block *Entry);
205-
206-
// Sets us to try to minimize size
207-
void SetMinSize(bool MinSize_) { MinSize = MinSize_; }
208-
};
209-
210-
typedef MapVector<Block *, BlockSet> BlockBlockSetMap;
211-
212184
} // namespace Relooper
213185

214186
} // namespace llvm

‎llvm/lib/Target/WebAssembly/WebAssembly.h

+2
Original file line numberDiff line numberDiff line change
@@ -28,6 +28,8 @@ FunctionPass *createWebAssemblyISelDag(WebAssemblyTargetMachine &TM,
2828

2929
FunctionPass *createWebAssemblyCFGStackify();
3030

31+
FunctionPass *createWebAssemblyRelooper();
32+
3133
} // end namespace llvm
3234

3335
#endif

0 commit comments

Comments
 (0)
Please sign in to comment.