1
2
3
4
5
6 #include <cmajor/binder/ControlFlowAnalyzer.hpp>
7 #include <cmajor/binder/BoundCompileUnit.hpp>
8 #include <cmajor/binder/BoundClass.hpp>
9 #include <cmajor/binder/BoundFunction.hpp>
10 #include <cmajor/binder/BoundStatement.hpp>
11 #include <cmajor/binder/BoundNodeVisitor.hpp>
12 #include <cmajor/symbols/Module.hpp>
13 #include <soulng/util/Unicode.hpp>
14
15 namespace cmajor { namespace binder {
16
17 using namespace soulng::unicode;
18
19 class ControlFlowAnalyzer : public BoundNodeVisitor
20 {
21 public:
22 ControlFlowAnalyzer();
23 void Visit(BoundCompileUnit& boundCompileUnit) override;
24 void Visit(BoundClass& boundClass) override;
25 void Visit(BoundFunction& boundFunction) override;
26 void Visit(BoundSequenceStatement& boundSequenceStatement) override;
27 void Visit(BoundCompoundStatement& boundCompoundStatement) override;
28 void Visit(BoundReturnStatement& boundReturnStatement) override;
29 void Visit(BoundIfStatement& boundIfStatement) override;
30 void Visit(BoundWhileStatement& boundWhileStatement) override;
31 void Visit(BoundDoStatement& boundDoStatement) override;
32 void Visit(BoundForStatement& boundForStatement) override;
33 void Visit(BoundSwitchStatement& boundSwitchStatement) override;
34 void Visit(BoundCaseStatement& boundCaseStatement) override;
35 void Visit(BoundDefaultStatement& boundDefaultStatement) override;
36 void Visit(BoundGotoCaseStatement& boundGotoCaseStatement) override;
37 void Visit(BoundGotoDefaultStatement& boundGotoDefaultStatement) override;
38 void Visit(BoundBreakStatement& boundBreakStatement) override;
39 void Visit(BoundContinueStatement& boundContinueStatement) override;
40 void Visit(BoundGotoStatement& boundGotoStatement) override;
41 void Visit(BoundConstructionStatement& boundConstructionStatement) override;
42 void Visit(BoundAssignmentStatement& boundAssignmentStatement) override;
43 void Visit(BoundExpressionStatement& boundExpressionStatement) override;
44 void Visit(BoundInitializationStatement& boundInitializationStatement) override;
45 void Visit(BoundEmptyStatement& boundEmptyStatement) override;
46 void Visit(BoundSetVmtPtrStatement& boundSetVmtPtrStatement) override;
47 void Visit(BoundThrowStatement& boundThrowStatement) override;
48 void Visit(BoundRethrowStatement& boundRethrowStatement) override;
49 void Visit(BoundTryStatement& boundTryStatement) override;
50 void Visit(BoundCatchStatement& boundCatchStatement) override;
51 private:
52 Module* module;
53 BoundFunction* currentFunction;
54 bool collectLabels;
55 bool resolveGotos;
56 std::unordered_map<std::u32string, BoundStatement*> labelStatementMap;
57 void CollectLabel(BoundStatement& statement);
58 void ResolveGoto(BoundGotoStatement& boundGotoStatement);
59 };
60
61 ControlFlowAnalyzer::ControlFlowAnalyzer() : module(nullptr), currentFunction(nullptr), collectLabels(false), resolveGotos(false)
62 {
63 }
64
65 void ControlFlowAnalyzer::CollectLabel(BoundStatement& statement)
66 {
67 if (!statement.Label().empty())
68 {
69 currentFunction->AddLabeledStatement(&statement);
70 auto it = labelStatementMap.find(statement.Label());
71 if (it == labelStatementMap.cend())
72 {
73 labelStatementMap[statement.Label()] = &statement;
74 }
75 else
76 {
77 throw Exception("duplicate label '" + ToUtf8(statement.Label()) + "'", statement.GetSpan(), statement.ModuleId(), it->second->GetSpan(), it->second->ModuleId());
78 }
79 }
80 }
81
82 void ControlFlowAnalyzer::ResolveGoto(BoundGotoStatement& boundGotoStatement)
83 {
84 const std::u32string& target = boundGotoStatement.Target();
85 auto it = labelStatementMap.find(target);
86 if (it != labelStatementMap.cend())
87 {
88 BoundStatement* targetStatement = it->second;
89 BoundCompoundStatement* targetBlock = targetStatement->Block();
90 Assert(targetBlock, "target block not found");
91 boundGotoStatement.SetTargetStatement(targetStatement);
92 boundGotoStatement.SetTargetBlock(targetBlock);
93 BoundCompoundStatement* gotoBlock = boundGotoStatement.Block();
94 Assert(gotoBlock, "goto block not found");
95 while (gotoBlock && gotoBlock != targetBlock)
96 {
97 if (gotoBlock->Parent())
98 {
99 gotoBlock = gotoBlock->Parent()->Block();
100 }
101 else
102 {
103 gotoBlock = nullptr;
104 }
105 }
106 if (!gotoBlock)
107 {
108 throw Exception("goto target '" + ToUtf8(target) + "' not in enclosing block", boundGotoStatement.GetSpan(), boundGotoStatement.ModuleId(), targetStatement->GetSpan(), targetStatement->ModuleId());
109 }
110 }
111 else
112 {
113 throw Exception("goto target '" + ToUtf8(target) + "' not found", boundGotoStatement.GetSpan(), boundGotoStatement.ModuleId());
114 }
115 }
116
117 void ControlFlowAnalyzer::Visit(BoundCompileUnit& boundCompileUnit)
118 {
119 module = &boundCompileUnit.GetModule();
120 int n = boundCompileUnit.BoundNodes().size();
121 for (int i = 0; i < n; ++i)
122 {
123 BoundNode* boundNode = boundCompileUnit.BoundNodes()[i].get();
124 boundNode->Accept(*this);
125 }
126 }
127
128 void ControlFlowAnalyzer::Visit(BoundClass& boundClass)
129 {
130 int n = boundClass.Members().size();
131 for (int i = 0; i < n; ++i)
132 {
133 BoundNode* boundNode = boundClass.Members()[i].get();
134 boundNode->Accept(*this);
135 }
136 }
137
138 void ControlFlowAnalyzer::Visit(BoundFunction& boundFunction)
139 {
140 if (!boundFunction.HasGotos()) return;
141 BoundFunction* prevFunction = currentFunction;
142 currentFunction = &boundFunction;
143 bool prevCollectLabels = collectLabels;
144 collectLabels = true;
145 boundFunction.Body()->Accept(*this);
146 collectLabels = prevCollectLabels;
147 bool prevResolveGotos = resolveGotos;
148 resolveGotos = true;
149 boundFunction.Body()->Accept(*this);
150 resolveGotos = prevResolveGotos;
151 currentFunction = prevFunction;
152 }
153
154 void ControlFlowAnalyzer::Visit(BoundSequenceStatement& boundSequenceStatement)
155 {
156 if (collectLabels)
157 {
158 CollectLabel(boundSequenceStatement);
159 }
160 boundSequenceStatement.First()->Accept(*this);
161 boundSequenceStatement.Second()->Accept(*this);
162 }
163
164 void ControlFlowAnalyzer::Visit(BoundCompoundStatement& boundCompoundStatement)
165 {
166 if (collectLabels)
167 {
168 CollectLabel(boundCompoundStatement);
169 }
170 int n = boundCompoundStatement.Statements().size();
171 for (int i = 0; i < n; ++i)
172 {
173 BoundStatement* statement = boundCompoundStatement.Statements()[i].get();
174 statement->Accept(*this);
175 }
176 }
177
178 void ControlFlowAnalyzer::Visit(BoundReturnStatement& boundReturnStatement)
179 {
180 if (collectLabels)
181 {
182 CollectLabel(boundReturnStatement);
183 }
184 }
185
186 void ControlFlowAnalyzer::Visit(BoundIfStatement& boundIfStatement)
187 {
188 if (collectLabels)
189 {
190 CollectLabel(boundIfStatement);
191 }
192 boundIfStatement.ThenS()->Accept(*this);
193 if (boundIfStatement.ElseS())
194 {
195 boundIfStatement.ElseS()->Accept(*this);
196 }
197 }
198
199 void ControlFlowAnalyzer::Visit(BoundWhileStatement& boundWhileStatement)
200 {
201 if (collectLabels)
202 {
203 CollectLabel(boundWhileStatement);
204 }
205 boundWhileStatement.Statement()->Accept(*this);
206 }
207
208 void ControlFlowAnalyzer::Visit(BoundDoStatement& boundDoStatement)
209 {
210 if (collectLabels)
211 {
212 CollectLabel(boundDoStatement);
213 }
214 boundDoStatement.Statement()->Accept(*this);
215
216 }
217
218 void ControlFlowAnalyzer::Visit(BoundForStatement& boundForStatement)
219 {
220 if (collectLabels)
221 {
222 CollectLabel(boundForStatement);
223 }
224 boundForStatement.InitS()->Accept(*this);
225 boundForStatement.LoopS()->Accept(*this);
226 boundForStatement.ActionS()->Accept(*this);
227 }
228
229 void ControlFlowAnalyzer::Visit(BoundSwitchStatement& boundSwitchStatement)
230 {
231 if (collectLabels)
232 {
233 CollectLabel(boundSwitchStatement);
234 }
235 int n = boundSwitchStatement.CaseStatements().size();
236 for (int i = 0; i < n; ++i)
237 {
238 BoundCaseStatement* caseStatement = boundSwitchStatement.CaseStatements()[i].get();
239 caseStatement->Accept(*this);
240 }
241 if (boundSwitchStatement.DefaultStatement())
242 {
243 boundSwitchStatement.DefaultStatement()->Accept(*this);
244 }
245 }
246
247 void ControlFlowAnalyzer::Visit(BoundCaseStatement& boundCaseStatement)
248 {
249 if (collectLabels)
250 {
251 CollectLabel(boundCaseStatement);
252 }
253 if (boundCaseStatement.CompoundStatement())
254 {
255 boundCaseStatement.CompoundStatement()->Accept(*this);
256 }
257 }
258
259 void ControlFlowAnalyzer::Visit(BoundDefaultStatement& boundDefaultStatement)
260 {
261 if (collectLabels)
262 {
263 CollectLabel(boundDefaultStatement);
264 }
265 if (boundDefaultStatement.CompoundStatement())
266 {
267 boundDefaultStatement.CompoundStatement()->Accept(*this);
268 }
269 }
270
271 void ControlFlowAnalyzer::Visit(BoundGotoCaseStatement& boundGotoCaseStatement)
272 {
273 if (collectLabels)
274 {
275 CollectLabel(boundGotoCaseStatement);
276 }
277 }
278
279 void ControlFlowAnalyzer::Visit(BoundGotoDefaultStatement& boundGotoDefaultStatement)
280 {
281 if (collectLabels)
282 {
283 CollectLabel(boundGotoDefaultStatement);
284 }
285 }
286
287 void ControlFlowAnalyzer::Visit(BoundBreakStatement& boundBreakStatement)
288 {
289 if (collectLabels)
290 {
291 CollectLabel(boundBreakStatement);
292 }
293 }
294
295 void ControlFlowAnalyzer::Visit(BoundContinueStatement& boundContinueStatement)
296 {
297 if (collectLabels)
298 {
299 CollectLabel(boundContinueStatement);
300 }
301 }
302
303 void ControlFlowAnalyzer::Visit(BoundGotoStatement& boundGotoStatement)
304 {
305 if (collectLabels)
306 {
307 CollectLabel(boundGotoStatement);
308 }
309 if (resolveGotos)
310 {
311 ResolveGoto(boundGotoStatement);
312 }
313 }
314
315 void ControlFlowAnalyzer::Visit(BoundConstructionStatement& boundConstructionStatement)
316 {
317 if (collectLabels)
318 {
319 CollectLabel(boundConstructionStatement);
320 }
321 }
322
323 void ControlFlowAnalyzer::Visit(BoundAssignmentStatement& boundAssignmentStatement)
324 {
325 if (collectLabels)
326 {
327 CollectLabel(boundAssignmentStatement);
328 }
329 }
330
331 void ControlFlowAnalyzer::Visit(BoundExpressionStatement& boundExpressionStatement)
332 {
333 if (collectLabels)
334 {
335 CollectLabel(boundExpressionStatement);
336 }
337 }
338
339 void ControlFlowAnalyzer::Visit(BoundInitializationStatement& boundInitializationStatement)
340 {
341 if (collectLabels)
342 {
343 CollectLabel(boundInitializationStatement);
344 }
345 }
346
347 void ControlFlowAnalyzer::Visit(BoundEmptyStatement& boundEmptyStatement)
348 {
349 if (collectLabels)
350 {
351 CollectLabel(boundEmptyStatement);
352 }
353 }
354
355 void ControlFlowAnalyzer::Visit(BoundSetVmtPtrStatement& boundSetVmtPtrStatement)
356 {
357 if (collectLabels)
358 {
359 CollectLabel(boundSetVmtPtrStatement);
360 }
361 }
362
363 void ControlFlowAnalyzer::Visit(BoundThrowStatement& boundThrowStatement)
364 {
365 if (collectLabels)
366 {
367 CollectLabel(boundThrowStatement);
368 }
369 }
370
371 void ControlFlowAnalyzer::Visit(BoundRethrowStatement& boundRethrowStatement)
372 {
373 if (collectLabels)
374 {
375 CollectLabel(boundRethrowStatement);
376 }
377 }
378
379 void ControlFlowAnalyzer::Visit(BoundTryStatement& boundTryStatement)
380 {
381 if (collectLabels)
382 {
383 CollectLabel(boundTryStatement);
384 }
385 boundTryStatement.TryBlock()->Accept(*this);
386 }
387
388 void ControlFlowAnalyzer::Visit(BoundCatchStatement& boundCatchStatement)
389 {
390 if (collectLabels)
391 {
392 CollectLabel(boundCatchStatement);
393 }
394 boundCatchStatement.CatchBlock()->Accept(*this);
395 }
396
397 void AnalyzeControlFlow(BoundCompileUnit& boundCompileUUnit)
398 {
399 ControlFlowAnalyzer controlFlowAnalyzer;
400 boundCompileUUnit.Accept(controlFlowAnalyzer);
401 }
402
403 } }