File: | llvm/lib/Target/WebAssembly/WebAssemblyCFGStackify.cpp |
Warning: | line 735, column 11 Value stored to 'ErasedUncondBr' is never read |
Press '?' to see keyboard shortcuts
Keyboard shortcuts:
1 | //===-- WebAssemblyCFGStackify.cpp - CFG Stackification -------------------===// |
2 | // |
3 | // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
4 | // See https://llvm.org/LICENSE.txt for license information. |
5 | // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
6 | // |
7 | //===----------------------------------------------------------------------===// |
8 | /// |
9 | /// \file |
10 | /// This file implements a CFG stacking pass. |
11 | /// |
12 | /// This pass inserts BLOCK, LOOP, and TRY markers to mark the start of scopes, |
13 | /// since scope boundaries serve as the labels for WebAssembly's control |
14 | /// transfers. |
15 | /// |
16 | /// This is sufficient to convert arbitrary CFGs into a form that works on |
17 | /// WebAssembly, provided that all loops are single-entry. |
18 | /// |
19 | /// In case we use exceptions, this pass also fixes mismatches in unwind |
20 | /// destinations created during transforming CFG into wasm structured format. |
21 | /// |
22 | //===----------------------------------------------------------------------===// |
23 | |
24 | #include "Utils/WebAssemblyTypeUtilities.h" |
25 | #include "Utils/WebAssemblyUtilities.h" |
26 | #include "WebAssembly.h" |
27 | #include "WebAssemblyExceptionInfo.h" |
28 | #include "WebAssemblyMachineFunctionInfo.h" |
29 | #include "WebAssemblySortRegion.h" |
30 | #include "WebAssemblySubtarget.h" |
31 | #include "llvm/ADT/Statistic.h" |
32 | #include "llvm/CodeGen/MachineDominators.h" |
33 | #include "llvm/CodeGen/MachineInstrBuilder.h" |
34 | #include "llvm/CodeGen/MachineLoopInfo.h" |
35 | #include "llvm/CodeGen/WasmEHFuncInfo.h" |
36 | #include "llvm/MC/MCAsmInfo.h" |
37 | #include "llvm/Target/TargetMachine.h" |
38 | using namespace llvm; |
39 | using WebAssembly::SortRegionInfo; |
40 | |
41 | #define DEBUG_TYPE"wasm-cfg-stackify" "wasm-cfg-stackify" |
42 | |
43 | STATISTIC(NumCallUnwindMismatches, "Number of call unwind mismatches found")static llvm::Statistic NumCallUnwindMismatches = {"wasm-cfg-stackify" , "NumCallUnwindMismatches", "Number of call unwind mismatches found" }; |
44 | STATISTIC(NumCatchUnwindMismatches, "Number of catch unwind mismatches found")static llvm::Statistic NumCatchUnwindMismatches = {"wasm-cfg-stackify" , "NumCatchUnwindMismatches", "Number of catch unwind mismatches found" }; |
45 | |
46 | namespace { |
47 | class WebAssemblyCFGStackify final : public MachineFunctionPass { |
48 | StringRef getPassName() const override { return "WebAssembly CFG Stackify"; } |
49 | |
50 | void getAnalysisUsage(AnalysisUsage &AU) const override { |
51 | AU.addRequired<MachineDominatorTree>(); |
52 | AU.addRequired<MachineLoopInfo>(); |
53 | AU.addRequired<WebAssemblyExceptionInfo>(); |
54 | MachineFunctionPass::getAnalysisUsage(AU); |
55 | } |
56 | |
57 | bool runOnMachineFunction(MachineFunction &MF) override; |
58 | |
59 | // For each block whose label represents the end of a scope, record the block |
60 | // which holds the beginning of the scope. This will allow us to quickly skip |
61 | // over scoped regions when walking blocks. |
62 | SmallVector<MachineBasicBlock *, 8> ScopeTops; |
63 | void updateScopeTops(MachineBasicBlock *Begin, MachineBasicBlock *End) { |
64 | int EndNo = End->getNumber(); |
65 | if (!ScopeTops[EndNo] || ScopeTops[EndNo]->getNumber() > Begin->getNumber()) |
66 | ScopeTops[EndNo] = Begin; |
67 | } |
68 | |
69 | // Placing markers. |
70 | void placeMarkers(MachineFunction &MF); |
71 | void placeBlockMarker(MachineBasicBlock &MBB); |
72 | void placeLoopMarker(MachineBasicBlock &MBB); |
73 | void placeTryMarker(MachineBasicBlock &MBB); |
74 | |
75 | // Exception handling related functions |
76 | bool fixCallUnwindMismatches(MachineFunction &MF); |
77 | bool fixCatchUnwindMismatches(MachineFunction &MF); |
78 | void addTryDelegate(MachineInstr *RangeBegin, MachineInstr *RangeEnd, |
79 | MachineBasicBlock *DelegateDest); |
80 | void recalculateScopeTops(MachineFunction &MF); |
81 | void removeUnnecessaryInstrs(MachineFunction &MF); |
82 | |
83 | // Wrap-up |
84 | using EndMarkerInfo = |
85 | std::pair<const MachineBasicBlock *, const MachineInstr *>; |
86 | unsigned getBranchDepth(const SmallVectorImpl<EndMarkerInfo> &Stack, |
87 | const MachineBasicBlock *MBB); |
88 | unsigned getDelegateDepth(const SmallVectorImpl<EndMarkerInfo> &Stack, |
89 | const MachineBasicBlock *MBB); |
90 | unsigned |
91 | getRethrowDepth(const SmallVectorImpl<EndMarkerInfo> &Stack, |
92 | const SmallVectorImpl<const MachineBasicBlock *> &EHPadStack); |
93 | void rewriteDepthImmediates(MachineFunction &MF); |
94 | void fixEndsAtEndOfFunction(MachineFunction &MF); |
95 | void cleanupFunctionData(MachineFunction &MF); |
96 | |
97 | // For each BLOCK|LOOP|TRY, the corresponding END_(BLOCK|LOOP|TRY) or DELEGATE |
98 | // (in case of TRY). |
99 | DenseMap<const MachineInstr *, MachineInstr *> BeginToEnd; |
100 | // For each END_(BLOCK|LOOP|TRY) or DELEGATE, the corresponding |
101 | // BLOCK|LOOP|TRY. |
102 | DenseMap<const MachineInstr *, MachineInstr *> EndToBegin; |
103 | // <TRY marker, EH pad> map |
104 | DenseMap<const MachineInstr *, MachineBasicBlock *> TryToEHPad; |
105 | // <EH pad, TRY marker> map |
106 | DenseMap<const MachineBasicBlock *, MachineInstr *> EHPadToTry; |
107 | |
108 | // We need an appendix block to place 'end_loop' or 'end_try' marker when the |
109 | // loop / exception bottom block is the last block in a function |
110 | MachineBasicBlock *AppendixBB = nullptr; |
111 | MachineBasicBlock *getAppendixBlock(MachineFunction &MF) { |
112 | if (!AppendixBB) { |
113 | AppendixBB = MF.CreateMachineBasicBlock(); |
114 | // Give it a fake predecessor so that AsmPrinter prints its label. |
115 | AppendixBB->addSuccessor(AppendixBB); |
116 | MF.push_back(AppendixBB); |
117 | } |
118 | return AppendixBB; |
119 | } |
120 | |
121 | // Before running rewriteDepthImmediates function, 'delegate' has a BB as its |
122 | // destination operand. getFakeCallerBlock() returns a fake BB that will be |
123 | // used for the operand when 'delegate' needs to rethrow to the caller. This |
124 | // will be rewritten as an immediate value that is the number of block depths |
125 | // + 1 in rewriteDepthImmediates, and this fake BB will be removed at the end |
126 | // of the pass. |
127 | MachineBasicBlock *FakeCallerBB = nullptr; |
128 | MachineBasicBlock *getFakeCallerBlock(MachineFunction &MF) { |
129 | if (!FakeCallerBB) |
130 | FakeCallerBB = MF.CreateMachineBasicBlock(); |
131 | return FakeCallerBB; |
132 | } |
133 | |
134 | // Helper functions to register / unregister scope information created by |
135 | // marker instructions. |
136 | void registerScope(MachineInstr *Begin, MachineInstr *End); |
137 | void registerTryScope(MachineInstr *Begin, MachineInstr *End, |
138 | MachineBasicBlock *EHPad); |
139 | void unregisterScope(MachineInstr *Begin); |
140 | |
141 | public: |
142 | static char ID; // Pass identification, replacement for typeid |
143 | WebAssemblyCFGStackify() : MachineFunctionPass(ID) {} |
144 | ~WebAssemblyCFGStackify() override { releaseMemory(); } |
145 | void releaseMemory() override; |
146 | }; |
147 | } // end anonymous namespace |
148 | |
149 | char WebAssemblyCFGStackify::ID = 0; |
150 | INITIALIZE_PASS(WebAssemblyCFGStackify, DEBUG_TYPE,static void *initializeWebAssemblyCFGStackifyPassOnce(PassRegistry &Registry) { PassInfo *PI = new PassInfo( "Insert BLOCK/LOOP/TRY markers for WebAssembly scopes" , "wasm-cfg-stackify", &WebAssemblyCFGStackify::ID, PassInfo ::NormalCtor_t(callDefaultCtor<WebAssemblyCFGStackify>) , false, false); Registry.registerPass(*PI, true); return PI; } static llvm::once_flag InitializeWebAssemblyCFGStackifyPassFlag ; void llvm::initializeWebAssemblyCFGStackifyPass(PassRegistry &Registry) { llvm::call_once(InitializeWebAssemblyCFGStackifyPassFlag , initializeWebAssemblyCFGStackifyPassOnce, std::ref(Registry )); } |
151 | "Insert BLOCK/LOOP/TRY markers for WebAssembly scopes", false,static void *initializeWebAssemblyCFGStackifyPassOnce(PassRegistry &Registry) { PassInfo *PI = new PassInfo( "Insert BLOCK/LOOP/TRY markers for WebAssembly scopes" , "wasm-cfg-stackify", &WebAssemblyCFGStackify::ID, PassInfo ::NormalCtor_t(callDefaultCtor<WebAssemblyCFGStackify>) , false, false); Registry.registerPass(*PI, true); return PI; } static llvm::once_flag InitializeWebAssemblyCFGStackifyPassFlag ; void llvm::initializeWebAssemblyCFGStackifyPass(PassRegistry &Registry) { llvm::call_once(InitializeWebAssemblyCFGStackifyPassFlag , initializeWebAssemblyCFGStackifyPassOnce, std::ref(Registry )); } |
152 | false)static void *initializeWebAssemblyCFGStackifyPassOnce(PassRegistry &Registry) { PassInfo *PI = new PassInfo( "Insert BLOCK/LOOP/TRY markers for WebAssembly scopes" , "wasm-cfg-stackify", &WebAssemblyCFGStackify::ID, PassInfo ::NormalCtor_t(callDefaultCtor<WebAssemblyCFGStackify>) , false, false); Registry.registerPass(*PI, true); return PI; } static llvm::once_flag InitializeWebAssemblyCFGStackifyPassFlag ; void llvm::initializeWebAssemblyCFGStackifyPass(PassRegistry &Registry) { llvm::call_once(InitializeWebAssemblyCFGStackifyPassFlag , initializeWebAssemblyCFGStackifyPassOnce, std::ref(Registry )); } |
153 | |
154 | FunctionPass *llvm::createWebAssemblyCFGStackify() { |
155 | return new WebAssemblyCFGStackify(); |
156 | } |
157 | |
158 | /// Test whether Pred has any terminators explicitly branching to MBB, as |
159 | /// opposed to falling through. Note that it's possible (eg. in unoptimized |
160 | /// code) for a branch instruction to both branch to a block and fallthrough |
161 | /// to it, so we check the actual branch operands to see if there are any |
162 | /// explicit mentions. |
163 | static bool explicitlyBranchesTo(MachineBasicBlock *Pred, |
164 | MachineBasicBlock *MBB) { |
165 | for (MachineInstr &MI : Pred->terminators()) |
166 | for (MachineOperand &MO : MI.explicit_operands()) |
167 | if (MO.isMBB() && MO.getMBB() == MBB) |
168 | return true; |
169 | return false; |
170 | } |
171 | |
172 | // Returns an iterator to the earliest position possible within the MBB, |
173 | // satisfying the restrictions given by BeforeSet and AfterSet. BeforeSet |
174 | // contains instructions that should go before the marker, and AfterSet contains |
175 | // ones that should go after the marker. In this function, AfterSet is only |
176 | // used for sanity checking. |
177 | template <typename Container> |
178 | static MachineBasicBlock::iterator |
179 | getEarliestInsertPos(MachineBasicBlock *MBB, const Container &BeforeSet, |
180 | const Container &AfterSet) { |
181 | auto InsertPos = MBB->end(); |
182 | while (InsertPos != MBB->begin()) { |
183 | if (BeforeSet.count(&*std::prev(InsertPos))) { |
184 | #ifndef NDEBUG1 |
185 | // Sanity check |
186 | for (auto Pos = InsertPos, E = MBB->begin(); Pos != E; --Pos) |
187 | assert(!AfterSet.count(&*std::prev(Pos)))(static_cast<void> (0)); |
188 | #endif |
189 | break; |
190 | } |
191 | --InsertPos; |
192 | } |
193 | return InsertPos; |
194 | } |
195 | |
196 | // Returns an iterator to the latest position possible within the MBB, |
197 | // satisfying the restrictions given by BeforeSet and AfterSet. BeforeSet |
198 | // contains instructions that should go before the marker, and AfterSet contains |
199 | // ones that should go after the marker. In this function, BeforeSet is only |
200 | // used for sanity checking. |
201 | template <typename Container> |
202 | static MachineBasicBlock::iterator |
203 | getLatestInsertPos(MachineBasicBlock *MBB, const Container &BeforeSet, |
204 | const Container &AfterSet) { |
205 | auto InsertPos = MBB->begin(); |
206 | while (InsertPos != MBB->end()) { |
207 | if (AfterSet.count(&*InsertPos)) { |
208 | #ifndef NDEBUG1 |
209 | // Sanity check |
210 | for (auto Pos = InsertPos, E = MBB->end(); Pos != E; ++Pos) |
211 | assert(!BeforeSet.count(&*Pos))(static_cast<void> (0)); |
212 | #endif |
213 | break; |
214 | } |
215 | ++InsertPos; |
216 | } |
217 | return InsertPos; |
218 | } |
219 | |
220 | void WebAssemblyCFGStackify::registerScope(MachineInstr *Begin, |
221 | MachineInstr *End) { |
222 | BeginToEnd[Begin] = End; |
223 | EndToBegin[End] = Begin; |
224 | } |
225 | |
226 | // When 'End' is not an 'end_try' but 'delegate, EHPad is nullptr. |
227 | void WebAssemblyCFGStackify::registerTryScope(MachineInstr *Begin, |
228 | MachineInstr *End, |
229 | MachineBasicBlock *EHPad) { |
230 | registerScope(Begin, End); |
231 | TryToEHPad[Begin] = EHPad; |
232 | EHPadToTry[EHPad] = Begin; |
233 | } |
234 | |
235 | void WebAssemblyCFGStackify::unregisterScope(MachineInstr *Begin) { |
236 | assert(BeginToEnd.count(Begin))(static_cast<void> (0)); |
237 | MachineInstr *End = BeginToEnd[Begin]; |
238 | assert(EndToBegin.count(End))(static_cast<void> (0)); |
239 | BeginToEnd.erase(Begin); |
240 | EndToBegin.erase(End); |
241 | MachineBasicBlock *EHPad = TryToEHPad.lookup(Begin); |
242 | if (EHPad) { |
243 | assert(EHPadToTry.count(EHPad))(static_cast<void> (0)); |
244 | TryToEHPad.erase(Begin); |
245 | EHPadToTry.erase(EHPad); |
246 | } |
247 | } |
248 | |
249 | /// Insert a BLOCK marker for branches to MBB (if needed). |
250 | // TODO Consider a more generalized way of handling block (and also loop and |
251 | // try) signatures when we implement the multi-value proposal later. |
252 | void WebAssemblyCFGStackify::placeBlockMarker(MachineBasicBlock &MBB) { |
253 | assert(!MBB.isEHPad())(static_cast<void> (0)); |
254 | MachineFunction &MF = *MBB.getParent(); |
255 | auto &MDT = getAnalysis<MachineDominatorTree>(); |
256 | const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo(); |
257 | const auto &MFI = *MF.getInfo<WebAssemblyFunctionInfo>(); |
258 | |
259 | // First compute the nearest common dominator of all forward non-fallthrough |
260 | // predecessors so that we minimize the time that the BLOCK is on the stack, |
261 | // which reduces overall stack height. |
262 | MachineBasicBlock *Header = nullptr; |
263 | bool IsBranchedTo = false; |
264 | int MBBNumber = MBB.getNumber(); |
265 | for (MachineBasicBlock *Pred : MBB.predecessors()) { |
266 | if (Pred->getNumber() < MBBNumber) { |
267 | Header = Header ? MDT.findNearestCommonDominator(Header, Pred) : Pred; |
268 | if (explicitlyBranchesTo(Pred, &MBB)) |
269 | IsBranchedTo = true; |
270 | } |
271 | } |
272 | if (!Header) |
273 | return; |
274 | if (!IsBranchedTo) |
275 | return; |
276 | |
277 | assert(&MBB != &MF.front() && "Header blocks shouldn't have predecessors")(static_cast<void> (0)); |
278 | MachineBasicBlock *LayoutPred = MBB.getPrevNode(); |
279 | |
280 | // If the nearest common dominator is inside a more deeply nested context, |
281 | // walk out to the nearest scope which isn't more deeply nested. |
282 | for (MachineFunction::iterator I(LayoutPred), E(Header); I != E; --I) { |
283 | if (MachineBasicBlock *ScopeTop = ScopeTops[I->getNumber()]) { |
284 | if (ScopeTop->getNumber() > Header->getNumber()) { |
285 | // Skip over an intervening scope. |
286 | I = std::next(ScopeTop->getIterator()); |
287 | } else { |
288 | // We found a scope level at an appropriate depth. |
289 | Header = ScopeTop; |
290 | break; |
291 | } |
292 | } |
293 | } |
294 | |
295 | // Decide where in Header to put the BLOCK. |
296 | |
297 | // Instructions that should go before the BLOCK. |
298 | SmallPtrSet<const MachineInstr *, 4> BeforeSet; |
299 | // Instructions that should go after the BLOCK. |
300 | SmallPtrSet<const MachineInstr *, 4> AfterSet; |
301 | for (const auto &MI : *Header) { |
302 | // If there is a previously placed LOOP marker and the bottom block of the |
303 | // loop is above MBB, it should be after the BLOCK, because the loop is |
304 | // nested in this BLOCK. Otherwise it should be before the BLOCK. |
305 | if (MI.getOpcode() == WebAssembly::LOOP) { |
306 | auto *LoopBottom = BeginToEnd[&MI]->getParent()->getPrevNode(); |
307 | if (MBB.getNumber() > LoopBottom->getNumber()) |
308 | AfterSet.insert(&MI); |
309 | #ifndef NDEBUG1 |
310 | else |
311 | BeforeSet.insert(&MI); |
312 | #endif |
313 | } |
314 | |
315 | // If there is a previously placed BLOCK/TRY marker and its corresponding |
316 | // END marker is before the current BLOCK's END marker, that should be |
317 | // placed after this BLOCK. Otherwise it should be placed before this BLOCK |
318 | // marker. |
319 | if (MI.getOpcode() == WebAssembly::BLOCK || |
320 | MI.getOpcode() == WebAssembly::TRY) { |
321 | if (BeginToEnd[&MI]->getParent()->getNumber() <= MBB.getNumber()) |
322 | AfterSet.insert(&MI); |
323 | #ifndef NDEBUG1 |
324 | else |
325 | BeforeSet.insert(&MI); |
326 | #endif |
327 | } |
328 | |
329 | #ifndef NDEBUG1 |
330 | // All END_(BLOCK|LOOP|TRY) markers should be before the BLOCK. |
331 | if (MI.getOpcode() == WebAssembly::END_BLOCK || |
332 | MI.getOpcode() == WebAssembly::END_LOOP || |
333 | MI.getOpcode() == WebAssembly::END_TRY) |
334 | BeforeSet.insert(&MI); |
335 | #endif |
336 | |
337 | // Terminators should go after the BLOCK. |
338 | if (MI.isTerminator()) |
339 | AfterSet.insert(&MI); |
340 | } |
341 | |
342 | // Local expression tree should go after the BLOCK. |
343 | for (auto I = Header->getFirstTerminator(), E = Header->begin(); I != E; |
344 | --I) { |
345 | if (std::prev(I)->isDebugInstr() || std::prev(I)->isPosition()) |
346 | continue; |
347 | if (WebAssembly::isChild(*std::prev(I), MFI)) |
348 | AfterSet.insert(&*std::prev(I)); |
349 | else |
350 | break; |
351 | } |
352 | |
353 | // Add the BLOCK. |
354 | WebAssembly::BlockType ReturnType = WebAssembly::BlockType::Void; |
355 | auto InsertPos = getLatestInsertPos(Header, BeforeSet, AfterSet); |
356 | MachineInstr *Begin = |
357 | BuildMI(*Header, InsertPos, Header->findDebugLoc(InsertPos), |
358 | TII.get(WebAssembly::BLOCK)) |
359 | .addImm(int64_t(ReturnType)); |
360 | |
361 | // Decide where in Header to put the END_BLOCK. |
362 | BeforeSet.clear(); |
363 | AfterSet.clear(); |
364 | for (auto &MI : MBB) { |
365 | #ifndef NDEBUG1 |
366 | // END_BLOCK should precede existing LOOP and TRY markers. |
367 | if (MI.getOpcode() == WebAssembly::LOOP || |
368 | MI.getOpcode() == WebAssembly::TRY) |
369 | AfterSet.insert(&MI); |
370 | #endif |
371 | |
372 | // If there is a previously placed END_LOOP marker and the header of the |
373 | // loop is above this block's header, the END_LOOP should be placed after |
374 | // the BLOCK, because the loop contains this block. Otherwise the END_LOOP |
375 | // should be placed before the BLOCK. The same for END_TRY. |
376 | if (MI.getOpcode() == WebAssembly::END_LOOP || |
377 | MI.getOpcode() == WebAssembly::END_TRY) { |
378 | if (EndToBegin[&MI]->getParent()->getNumber() >= Header->getNumber()) |
379 | BeforeSet.insert(&MI); |
380 | #ifndef NDEBUG1 |
381 | else |
382 | AfterSet.insert(&MI); |
383 | #endif |
384 | } |
385 | } |
386 | |
387 | // Mark the end of the block. |
388 | InsertPos = getEarliestInsertPos(&MBB, BeforeSet, AfterSet); |
389 | MachineInstr *End = BuildMI(MBB, InsertPos, MBB.findPrevDebugLoc(InsertPos), |
390 | TII.get(WebAssembly::END_BLOCK)); |
391 | registerScope(Begin, End); |
392 | |
393 | // Track the farthest-spanning scope that ends at this point. |
394 | updateScopeTops(Header, &MBB); |
395 | } |
396 | |
397 | /// Insert a LOOP marker for a loop starting at MBB (if it's a loop header). |
398 | void WebAssemblyCFGStackify::placeLoopMarker(MachineBasicBlock &MBB) { |
399 | MachineFunction &MF = *MBB.getParent(); |
400 | const auto &MLI = getAnalysis<MachineLoopInfo>(); |
401 | const auto &WEI = getAnalysis<WebAssemblyExceptionInfo>(); |
402 | SortRegionInfo SRI(MLI, WEI); |
403 | const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo(); |
404 | |
405 | MachineLoop *Loop = MLI.getLoopFor(&MBB); |
406 | if (!Loop || Loop->getHeader() != &MBB) |
407 | return; |
408 | |
409 | // The operand of a LOOP is the first block after the loop. If the loop is the |
410 | // bottom of the function, insert a dummy block at the end. |
411 | MachineBasicBlock *Bottom = SRI.getBottom(Loop); |
412 | auto Iter = std::next(Bottom->getIterator()); |
413 | if (Iter == MF.end()) { |
414 | getAppendixBlock(MF); |
415 | Iter = std::next(Bottom->getIterator()); |
416 | } |
417 | MachineBasicBlock *AfterLoop = &*Iter; |
418 | |
419 | // Decide where in Header to put the LOOP. |
420 | SmallPtrSet<const MachineInstr *, 4> BeforeSet; |
421 | SmallPtrSet<const MachineInstr *, 4> AfterSet; |
422 | for (const auto &MI : MBB) { |
423 | // LOOP marker should be after any existing loop that ends here. Otherwise |
424 | // we assume the instruction belongs to the loop. |
425 | if (MI.getOpcode() == WebAssembly::END_LOOP) |
426 | BeforeSet.insert(&MI); |
427 | #ifndef NDEBUG1 |
428 | else |
429 | AfterSet.insert(&MI); |
430 | #endif |
431 | } |
432 | |
433 | // Mark the beginning of the loop. |
434 | auto InsertPos = getEarliestInsertPos(&MBB, BeforeSet, AfterSet); |
435 | MachineInstr *Begin = BuildMI(MBB, InsertPos, MBB.findDebugLoc(InsertPos), |
436 | TII.get(WebAssembly::LOOP)) |
437 | .addImm(int64_t(WebAssembly::BlockType::Void)); |
438 | |
439 | // Decide where in Header to put the END_LOOP. |
440 | BeforeSet.clear(); |
441 | AfterSet.clear(); |
442 | #ifndef NDEBUG1 |
443 | for (const auto &MI : MBB) |
444 | // Existing END_LOOP markers belong to parent loops of this loop |
445 | if (MI.getOpcode() == WebAssembly::END_LOOP) |
446 | AfterSet.insert(&MI); |
447 | #endif |
448 | |
449 | // Mark the end of the loop (using arbitrary debug location that branched to |
450 | // the loop end as its location). |
451 | InsertPos = getEarliestInsertPos(AfterLoop, BeforeSet, AfterSet); |
452 | DebugLoc EndDL = AfterLoop->pred_empty() |
453 | ? DebugLoc() |
454 | : (*AfterLoop->pred_rbegin())->findBranchDebugLoc(); |
455 | MachineInstr *End = |
456 | BuildMI(*AfterLoop, InsertPos, EndDL, TII.get(WebAssembly::END_LOOP)); |
457 | registerScope(Begin, End); |
458 | |
459 | assert((!ScopeTops[AfterLoop->getNumber()] ||(static_cast<void> (0)) |
460 | ScopeTops[AfterLoop->getNumber()]->getNumber() < MBB.getNumber()) &&(static_cast<void> (0)) |
461 | "With block sorting the outermost loop for a block should be first.")(static_cast<void> (0)); |
462 | updateScopeTops(&MBB, AfterLoop); |
463 | } |
464 | |
465 | void WebAssemblyCFGStackify::placeTryMarker(MachineBasicBlock &MBB) { |
466 | assert(MBB.isEHPad())(static_cast<void> (0)); |
467 | MachineFunction &MF = *MBB.getParent(); |
468 | auto &MDT = getAnalysis<MachineDominatorTree>(); |
469 | const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo(); |
470 | const auto &MLI = getAnalysis<MachineLoopInfo>(); |
471 | const auto &WEI = getAnalysis<WebAssemblyExceptionInfo>(); |
472 | SortRegionInfo SRI(MLI, WEI); |
473 | const auto &MFI = *MF.getInfo<WebAssemblyFunctionInfo>(); |
474 | |
475 | // Compute the nearest common dominator of all unwind predecessors |
476 | MachineBasicBlock *Header = nullptr; |
477 | int MBBNumber = MBB.getNumber(); |
478 | for (auto *Pred : MBB.predecessors()) { |
479 | if (Pred->getNumber() < MBBNumber) { |
480 | Header = Header ? MDT.findNearestCommonDominator(Header, Pred) : Pred; |
481 | assert(!explicitlyBranchesTo(Pred, &MBB) &&(static_cast<void> (0)) |
482 | "Explicit branch to an EH pad!")(static_cast<void> (0)); |
483 | } |
484 | } |
485 | if (!Header) |
486 | return; |
487 | |
488 | // If this try is at the bottom of the function, insert a dummy block at the |
489 | // end. |
490 | WebAssemblyException *WE = WEI.getExceptionFor(&MBB); |
491 | assert(WE)(static_cast<void> (0)); |
492 | MachineBasicBlock *Bottom = SRI.getBottom(WE); |
493 | |
494 | auto Iter = std::next(Bottom->getIterator()); |
495 | if (Iter == MF.end()) { |
496 | getAppendixBlock(MF); |
497 | Iter = std::next(Bottom->getIterator()); |
498 | } |
499 | MachineBasicBlock *Cont = &*Iter; |
500 | |
501 | assert(Cont != &MF.front())(static_cast<void> (0)); |
502 | MachineBasicBlock *LayoutPred = Cont->getPrevNode(); |
503 | |
504 | // If the nearest common dominator is inside a more deeply nested context, |
505 | // walk out to the nearest scope which isn't more deeply nested. |
506 | for (MachineFunction::iterator I(LayoutPred), E(Header); I != E; --I) { |
507 | if (MachineBasicBlock *ScopeTop = ScopeTops[I->getNumber()]) { |
508 | if (ScopeTop->getNumber() > Header->getNumber()) { |
509 | // Skip over an intervening scope. |
510 | I = std::next(ScopeTop->getIterator()); |
511 | } else { |
512 | // We found a scope level at an appropriate depth. |
513 | Header = ScopeTop; |
514 | break; |
515 | } |
516 | } |
517 | } |
518 | |
519 | // Decide where in Header to put the TRY. |
520 | |
521 | // Instructions that should go before the TRY. |
522 | SmallPtrSet<const MachineInstr *, 4> BeforeSet; |
523 | // Instructions that should go after the TRY. |
524 | SmallPtrSet<const MachineInstr *, 4> AfterSet; |
525 | for (const auto &MI : *Header) { |
526 | // If there is a previously placed LOOP marker and the bottom block of the |
527 | // loop is above MBB, it should be after the TRY, because the loop is nested |
528 | // in this TRY. Otherwise it should be before the TRY. |
529 | if (MI.getOpcode() == WebAssembly::LOOP) { |
530 | auto *LoopBottom = BeginToEnd[&MI]->getParent()->getPrevNode(); |
531 | if (MBB.getNumber() > LoopBottom->getNumber()) |
532 | AfterSet.insert(&MI); |
533 | #ifndef NDEBUG1 |
534 | else |
535 | BeforeSet.insert(&MI); |
536 | #endif |
537 | } |
538 | |
539 | // All previously inserted BLOCK/TRY markers should be after the TRY because |
540 | // they are all nested trys. |
541 | if (MI.getOpcode() == WebAssembly::BLOCK || |
542 | MI.getOpcode() == WebAssembly::TRY) |
543 | AfterSet.insert(&MI); |
544 | |
545 | #ifndef NDEBUG1 |
546 | // All END_(BLOCK/LOOP/TRY) markers should be before the TRY. |
547 | if (MI.getOpcode() == WebAssembly::END_BLOCK || |
548 | MI.getOpcode() == WebAssembly::END_LOOP || |
549 | MI.getOpcode() == WebAssembly::END_TRY) |
550 | BeforeSet.insert(&MI); |
551 | #endif |
552 | |
553 | // Terminators should go after the TRY. |
554 | if (MI.isTerminator()) |
555 | AfterSet.insert(&MI); |
556 | } |
557 | |
558 | // If Header unwinds to MBB (= Header contains 'invoke'), the try block should |
559 | // contain the call within it. So the call should go after the TRY. The |
560 | // exception is when the header's terminator is a rethrow instruction, in |
561 | // which case that instruction, not a call instruction before it, is gonna |
562 | // throw. |
563 | MachineInstr *ThrowingCall = nullptr; |
564 | if (MBB.isPredecessor(Header)) { |
565 | auto TermPos = Header->getFirstTerminator(); |
566 | if (TermPos == Header->end() || |
567 | TermPos->getOpcode() != WebAssembly::RETHROW) { |
568 | for (auto &MI : reverse(*Header)) { |
569 | if (MI.isCall()) { |
570 | AfterSet.insert(&MI); |
571 | ThrowingCall = &MI; |
572 | // Possibly throwing calls are usually wrapped by EH_LABEL |
573 | // instructions. We don't want to split them and the call. |
574 | if (MI.getIterator() != Header->begin() && |
575 | std::prev(MI.getIterator())->isEHLabel()) { |
576 | AfterSet.insert(&*std::prev(MI.getIterator())); |
577 | ThrowingCall = &*std::prev(MI.getIterator()); |
578 | } |
579 | break; |
580 | } |
581 | } |
582 | } |
583 | } |
584 | |
585 | // Local expression tree should go after the TRY. |
586 | // For BLOCK placement, we start the search from the previous instruction of a |
587 | // BB's terminator, but in TRY's case, we should start from the previous |
588 | // instruction of a call that can throw, or a EH_LABEL that precedes the call, |
589 | // because the return values of the call's previous instructions can be |
590 | // stackified and consumed by the throwing call. |
591 | auto SearchStartPt = ThrowingCall ? MachineBasicBlock::iterator(ThrowingCall) |
592 | : Header->getFirstTerminator(); |
593 | for (auto I = SearchStartPt, E = Header->begin(); I != E; --I) { |
594 | if (std::prev(I)->isDebugInstr() || std::prev(I)->isPosition()) |
595 | continue; |
596 | if (WebAssembly::isChild(*std::prev(I), MFI)) |
597 | AfterSet.insert(&*std::prev(I)); |
598 | else |
599 | break; |
600 | } |
601 | |
602 | // Add the TRY. |
603 | auto InsertPos = getLatestInsertPos(Header, BeforeSet, AfterSet); |
604 | MachineInstr *Begin = |
605 | BuildMI(*Header, InsertPos, Header->findDebugLoc(InsertPos), |
606 | TII.get(WebAssembly::TRY)) |
607 | .addImm(int64_t(WebAssembly::BlockType::Void)); |
608 | |
609 | // Decide where in Header to put the END_TRY. |
610 | BeforeSet.clear(); |
611 | AfterSet.clear(); |
612 | for (const auto &MI : *Cont) { |
613 | #ifndef NDEBUG1 |
614 | // END_TRY should precede existing LOOP and BLOCK markers. |
615 | if (MI.getOpcode() == WebAssembly::LOOP || |
616 | MI.getOpcode() == WebAssembly::BLOCK) |
617 | AfterSet.insert(&MI); |
618 | |
619 | // All END_TRY markers placed earlier belong to exceptions that contains |
620 | // this one. |
621 | if (MI.getOpcode() == WebAssembly::END_TRY) |
622 | AfterSet.insert(&MI); |
623 | #endif |
624 | |
625 | // If there is a previously placed END_LOOP marker and its header is after |
626 | // where TRY marker is, this loop is contained within the 'catch' part, so |
627 | // the END_TRY marker should go after that. Otherwise, the whole try-catch |
628 | // is contained within this loop, so the END_TRY should go before that. |
629 | if (MI.getOpcode() == WebAssembly::END_LOOP) { |
630 | // For a LOOP to be after TRY, LOOP's BB should be after TRY's BB; if they |
631 | // are in the same BB, LOOP is always before TRY. |
632 | if (EndToBegin[&MI]->getParent()->getNumber() > Header->getNumber()) |
633 | BeforeSet.insert(&MI); |
634 | #ifndef NDEBUG1 |
635 | else |
636 | AfterSet.insert(&MI); |
637 | #endif |
638 | } |
639 | |
640 | // It is not possible for an END_BLOCK to be already in this block. |
641 | } |
642 | |
643 | // Mark the end of the TRY. |
644 | InsertPos = getEarliestInsertPos(Cont, BeforeSet, AfterSet); |
645 | MachineInstr *End = |
646 | BuildMI(*Cont, InsertPos, Bottom->findBranchDebugLoc(), |
647 | TII.get(WebAssembly::END_TRY)); |
648 | registerTryScope(Begin, End, &MBB); |
649 | |
650 | // Track the farthest-spanning scope that ends at this point. We create two |
651 | // mappings: (BB with 'end_try' -> BB with 'try') and (BB with 'catch' -> BB |
652 | // with 'try'). We need to create 'catch' -> 'try' mapping here too because |
653 | // markers should not span across 'catch'. For example, this should not |
654 | // happen: |
655 | // |
656 | // try |
657 | // block --| (X) |
658 | // catch | |
659 | // end_block --| |
660 | // end_try |
661 | for (auto *End : {&MBB, Cont}) |
662 | updateScopeTops(Header, End); |
663 | } |
664 | |
665 | void WebAssemblyCFGStackify::removeUnnecessaryInstrs(MachineFunction &MF) { |
666 | const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo(); |
667 | |
668 | // When there is an unconditional branch right before a catch instruction and |
669 | // it branches to the end of end_try marker, we don't need the branch, because |
670 | // it there is no exception, the control flow transfers to that point anyway. |
671 | // bb0: |
672 | // try |
673 | // ... |
674 | // br bb2 <- Not necessary |
675 | // bb1 (ehpad): |
676 | // catch |
677 | // ... |
678 | // bb2: <- Continuation BB |
679 | // end |
680 | // |
681 | // A more involved case: When the BB where 'end' is located is an another EH |
682 | // pad, the Cont (= continuation) BB is that EH pad's 'end' BB. For example, |
683 | // bb0: |
684 | // try |
685 | // try |
686 | // ... |
687 | // br bb3 <- Not necessary |
688 | // bb1 (ehpad): |
689 | // catch |
690 | // bb2 (ehpad): |
691 | // end |
692 | // catch |
693 | // ... |
694 | // bb3: <- Continuation BB |
695 | // end |
696 | // |
697 | // When the EH pad at hand is bb1, its matching end_try is in bb2. But it is |
698 | // another EH pad, so bb0's continuation BB becomes bb3. So 'br bb3' in the |
699 | // code can be deleted. This is why we run 'while' until 'Cont' is not an EH |
700 | // pad. |
701 | for (auto &MBB : MF) { |
702 | if (!MBB.isEHPad()) |
703 | continue; |
704 | |
705 | MachineBasicBlock *TBB = nullptr, *FBB = nullptr; |
706 | SmallVector<MachineOperand, 4> Cond; |
707 | MachineBasicBlock *EHPadLayoutPred = MBB.getPrevNode(); |
708 | |
709 | MachineBasicBlock *Cont = &MBB; |
710 | while (Cont->isEHPad()) { |
711 | MachineInstr *Try = EHPadToTry[Cont]; |
712 | MachineInstr *EndTry = BeginToEnd[Try]; |
713 | // We started from an EH pad, so the end marker cannot be a delegate |
714 | assert(EndTry->getOpcode() != WebAssembly::DELEGATE)(static_cast<void> (0)); |
715 | Cont = EndTry->getParent(); |
716 | } |
717 | |
718 | bool Analyzable = !TII.analyzeBranch(*EHPadLayoutPred, TBB, FBB, Cond); |
719 | // This condition means either |
720 | // 1. This BB ends with a single unconditional branch whose destinaion is |
721 | // Cont. |
722 | // 2. This BB ends with a conditional branch followed by an unconditional |
723 | // branch, and the unconditional branch's destination is Cont. |
724 | // In both cases, we want to remove the last (= unconditional) branch. |
725 | if (Analyzable && ((Cond.empty() && TBB && TBB == Cont) || |
726 | (!Cond.empty() && FBB && FBB == Cont))) { |
727 | bool ErasedUncondBr = false; |
728 | (void)ErasedUncondBr; |
729 | for (auto I = EHPadLayoutPred->end(), E = EHPadLayoutPred->begin(); |
730 | I != E; --I) { |
731 | auto PrevI = std::prev(I); |
732 | if (PrevI->isTerminator()) { |
733 | assert(PrevI->getOpcode() == WebAssembly::BR)(static_cast<void> (0)); |
734 | PrevI->eraseFromParent(); |
735 | ErasedUncondBr = true; |
Value stored to 'ErasedUncondBr' is never read | |
736 | break; |
737 | } |
738 | } |
739 | assert(ErasedUncondBr && "Unconditional branch not erased!")(static_cast<void> (0)); |
740 | } |
741 | } |
742 | |
743 | // When there are block / end_block markers that overlap with try / end_try |
744 | // markers, and the block and try markers' return types are the same, the |
745 | // block /end_block markers are not necessary, because try / end_try markers |
746 | // also can serve as boundaries for branches. |
747 | // block <- Not necessary |
748 | // try |
749 | // ... |
750 | // catch |
751 | // ... |
752 | // end |
753 | // end <- Not necessary |
754 | SmallVector<MachineInstr *, 32> ToDelete; |
755 | for (auto &MBB : MF) { |
756 | for (auto &MI : MBB) { |
757 | if (MI.getOpcode() != WebAssembly::TRY) |
758 | continue; |
759 | MachineInstr *Try = &MI, *EndTry = BeginToEnd[Try]; |
760 | if (EndTry->getOpcode() == WebAssembly::DELEGATE) |
761 | continue; |
762 | |
763 | MachineBasicBlock *TryBB = Try->getParent(); |
764 | MachineBasicBlock *Cont = EndTry->getParent(); |
765 | int64_t RetType = Try->getOperand(0).getImm(); |
766 | for (auto B = Try->getIterator(), E = std::next(EndTry->getIterator()); |
767 | B != TryBB->begin() && E != Cont->end() && |
768 | std::prev(B)->getOpcode() == WebAssembly::BLOCK && |
769 | E->getOpcode() == WebAssembly::END_BLOCK && |
770 | std::prev(B)->getOperand(0).getImm() == RetType; |
771 | --B, ++E) { |
772 | ToDelete.push_back(&*std::prev(B)); |
773 | ToDelete.push_back(&*E); |
774 | } |
775 | } |
776 | } |
777 | for (auto *MI : ToDelete) { |
778 | if (MI->getOpcode() == WebAssembly::BLOCK) |
779 | unregisterScope(MI); |
780 | MI->eraseFromParent(); |
781 | } |
782 | } |
783 | |
784 | // Get the appropriate copy opcode for the given register class. |
785 | static unsigned getCopyOpcode(const TargetRegisterClass *RC) { |
786 | if (RC == &WebAssembly::I32RegClass) |
787 | return WebAssembly::COPY_I32; |
788 | if (RC == &WebAssembly::I64RegClass) |
789 | return WebAssembly::COPY_I64; |
790 | if (RC == &WebAssembly::F32RegClass) |
791 | return WebAssembly::COPY_F32; |
792 | if (RC == &WebAssembly::F64RegClass) |
793 | return WebAssembly::COPY_F64; |
794 | if (RC == &WebAssembly::V128RegClass) |
795 | return WebAssembly::COPY_V128; |
796 | if (RC == &WebAssembly::FUNCREFRegClass) |
797 | return WebAssembly::COPY_FUNCREF; |
798 | if (RC == &WebAssembly::EXTERNREFRegClass) |
799 | return WebAssembly::COPY_EXTERNREF; |
800 | llvm_unreachable("Unexpected register class")__builtin_unreachable(); |
801 | } |
802 | |
803 | // When MBB is split into MBB and Split, we should unstackify defs in MBB that |
804 | // have their uses in Split. |
805 | static void unstackifyVRegsUsedInSplitBB(MachineBasicBlock &MBB, |
806 | MachineBasicBlock &Split) { |
807 | MachineFunction &MF = *MBB.getParent(); |
808 | const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo(); |
809 | auto &MFI = *MF.getInfo<WebAssemblyFunctionInfo>(); |
810 | auto &MRI = MF.getRegInfo(); |
811 | |
812 | for (auto &MI : Split) { |
813 | for (auto &MO : MI.explicit_uses()) { |
814 | if (!MO.isReg() || Register::isPhysicalRegister(MO.getReg())) |
815 | continue; |
816 | if (MachineInstr *Def = MRI.getUniqueVRegDef(MO.getReg())) |
817 | if (Def->getParent() == &MBB) |
818 | MFI.unstackifyVReg(MO.getReg()); |
819 | } |
820 | } |
821 | |
822 | // In RegStackify, when a register definition is used multiple times, |
823 | // Reg = INST ... |
824 | // INST ..., Reg, ... |
825 | // INST ..., Reg, ... |
826 | // INST ..., Reg, ... |
827 | // |
828 | // we introduce a TEE, which has the following form: |
829 | // DefReg = INST ... |
830 | // TeeReg, Reg = TEE_... DefReg |
831 | // INST ..., TeeReg, ... |
832 | // INST ..., Reg, ... |
833 | // INST ..., Reg, ... |
834 | // with DefReg and TeeReg stackified but Reg not stackified. |
835 | // |
836 | // But the invariant that TeeReg should be stackified can be violated while we |
837 | // unstackify registers in the split BB above. In this case, we convert TEEs |
838 | // into two COPYs. This COPY will be eventually eliminated in ExplicitLocals. |
839 | // DefReg = INST ... |
840 | // TeeReg = COPY DefReg |
841 | // Reg = COPY DefReg |
842 | // INST ..., TeeReg, ... |
843 | // INST ..., Reg, ... |
844 | // INST ..., Reg, ... |
845 | for (auto I = MBB.begin(), E = MBB.end(); I != E;) { |
846 | MachineInstr &MI = *I++; |
847 | if (!WebAssembly::isTee(MI.getOpcode())) |
848 | continue; |
849 | Register TeeReg = MI.getOperand(0).getReg(); |
850 | Register Reg = MI.getOperand(1).getReg(); |
851 | Register DefReg = MI.getOperand(2).getReg(); |
852 | if (!MFI.isVRegStackified(TeeReg)) { |
853 | // Now we are not using TEE anymore, so unstackify DefReg too |
854 | MFI.unstackifyVReg(DefReg); |
855 | unsigned CopyOpc = getCopyOpcode(MRI.getRegClass(DefReg)); |
856 | BuildMI(MBB, &MI, MI.getDebugLoc(), TII.get(CopyOpc), TeeReg) |
857 | .addReg(DefReg); |
858 | BuildMI(MBB, &MI, MI.getDebugLoc(), TII.get(CopyOpc), Reg).addReg(DefReg); |
859 | MI.eraseFromParent(); |
860 | } |
861 | } |
862 | } |
863 | |
864 | // Wrap the given range of instruction with try-delegate. RangeBegin and |
865 | // RangeEnd are inclusive. |
866 | void WebAssemblyCFGStackify::addTryDelegate(MachineInstr *RangeBegin, |
867 | MachineInstr *RangeEnd, |
868 | MachineBasicBlock *DelegateDest) { |
869 | auto *BeginBB = RangeBegin->getParent(); |
870 | auto *EndBB = RangeEnd->getParent(); |
871 | MachineFunction &MF = *BeginBB->getParent(); |
872 | const auto &MFI = *MF.getInfo<WebAssemblyFunctionInfo>(); |
873 | const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo(); |
874 | |
875 | // Local expression tree before the first call of this range should go |
876 | // after the nested TRY. |
877 | SmallPtrSet<const MachineInstr *, 4> AfterSet; |
878 | AfterSet.insert(RangeBegin); |
879 | for (auto I = MachineBasicBlock::iterator(RangeBegin), E = BeginBB->begin(); |
880 | I != E; --I) { |
881 | if (std::prev(I)->isDebugInstr() || std::prev(I)->isPosition()) |
882 | continue; |
883 | if (WebAssembly::isChild(*std::prev(I), MFI)) |
884 | AfterSet.insert(&*std::prev(I)); |
885 | else |
886 | break; |
887 | } |
888 | |
889 | // Create the nested try instruction. |
890 | auto TryPos = getLatestInsertPos( |
891 | BeginBB, SmallPtrSet<const MachineInstr *, 4>(), AfterSet); |
892 | MachineInstr *Try = BuildMI(*BeginBB, TryPos, RangeBegin->getDebugLoc(), |
893 | TII.get(WebAssembly::TRY)) |
894 | .addImm(int64_t(WebAssembly::BlockType::Void)); |
895 | |
896 | // Create a BB to insert the 'delegate' instruction. |
897 | MachineBasicBlock *DelegateBB = MF.CreateMachineBasicBlock(); |
898 | // If the destination of 'delegate' is not the caller, adds the destination to |
899 | // the BB's successors. |
900 | if (DelegateDest != FakeCallerBB) |
901 | DelegateBB->addSuccessor(DelegateDest); |
902 | |
903 | auto SplitPos = std::next(RangeEnd->getIterator()); |
904 | if (SplitPos == EndBB->end()) { |
905 | // If the range's end instruction is at the end of the BB, insert the new |
906 | // delegate BB after the current BB. |
907 | MF.insert(std::next(EndBB->getIterator()), DelegateBB); |
908 | EndBB->addSuccessor(DelegateBB); |
909 | |
910 | } else { |
911 | // When the split pos is in the middle of a BB, we split the BB into two and |
912 | // put the 'delegate' BB in between. We normally create a split BB and make |
913 | // it a successor of the original BB (PostSplit == true), but in case the BB |
914 | // is an EH pad and the split pos is before 'catch', we should preserve the |
915 | // BB's property, including that it is an EH pad, in the later part of the |
916 | // BB, where 'catch' is. In this case we set PostSplit to false. |
917 | bool PostSplit = true; |
918 | if (EndBB->isEHPad()) { |
919 | for (auto I = MachineBasicBlock::iterator(SplitPos), E = EndBB->end(); |
920 | I != E; ++I) { |
921 | if (WebAssembly::isCatch(I->getOpcode())) { |
922 | PostSplit = false; |
923 | break; |
924 | } |
925 | } |
926 | } |
927 | |
928 | MachineBasicBlock *PreBB = nullptr, *PostBB = nullptr; |
929 | if (PostSplit) { |
930 | // If the range's end instruction is in the middle of the BB, we split the |
931 | // BB into two and insert the delegate BB in between. |
932 | // - Before: |
933 | // bb: |
934 | // range_end |
935 | // other_insts |
936 | // |
937 | // - After: |
938 | // pre_bb: (previous 'bb') |
939 | // range_end |
940 | // delegate_bb: (new) |
941 | // delegate |
942 | // post_bb: (new) |
943 | // other_insts |
944 | PreBB = EndBB; |
945 | PostBB = MF.CreateMachineBasicBlock(); |
946 | MF.insert(std::next(PreBB->getIterator()), PostBB); |
947 | MF.insert(std::next(PreBB->getIterator()), DelegateBB); |
948 | PostBB->splice(PostBB->end(), PreBB, SplitPos, PreBB->end()); |
949 | PostBB->transferSuccessors(PreBB); |
950 | } else { |
951 | // - Before: |
952 | // ehpad: |
953 | // range_end |
954 | // catch |
955 | // ... |
956 | // |
957 | // - After: |
958 | // pre_bb: (new) |
959 | // range_end |
960 | // delegate_bb: (new) |
961 | // delegate |
962 | // post_bb: (previous 'ehpad') |
963 | // catch |
964 | // ... |
965 | assert(EndBB->isEHPad())(static_cast<void> (0)); |
966 | PreBB = MF.CreateMachineBasicBlock(); |
967 | PostBB = EndBB; |
968 | MF.insert(PostBB->getIterator(), PreBB); |
969 | MF.insert(PostBB->getIterator(), DelegateBB); |
970 | PreBB->splice(PreBB->end(), PostBB, PostBB->begin(), SplitPos); |
971 | // We don't need to transfer predecessors of the EH pad to 'PreBB', |
972 | // because an EH pad's predecessors are all through unwind edges and they |
973 | // should still unwind to the EH pad, not PreBB. |
974 | } |
975 | unstackifyVRegsUsedInSplitBB(*PreBB, *PostBB); |
976 | PreBB->addSuccessor(DelegateBB); |
977 | PreBB->addSuccessor(PostBB); |
978 | } |
979 | |
980 | // Add 'delegate' instruction in the delegate BB created above. |
981 | MachineInstr *Delegate = BuildMI(DelegateBB, RangeEnd->getDebugLoc(), |
982 | TII.get(WebAssembly::DELEGATE)) |
983 | .addMBB(DelegateDest); |
984 | registerTryScope(Try, Delegate, nullptr); |
985 | } |
986 | |
987 | bool WebAssemblyCFGStackify::fixCallUnwindMismatches(MachineFunction &MF) { |
988 | // Linearizing the control flow by placing TRY / END_TRY markers can create |
989 | // mismatches in unwind destinations for throwing instructions, such as calls. |
990 | // |
991 | // We use the 'delegate' instruction to fix the unwind mismatches. 'delegate' |
992 | // instruction delegates an exception to an outer 'catch'. It can target not |
993 | // only 'catch' but all block-like structures including another 'delegate', |
994 | // but with slightly different semantics than branches. When it targets a |
995 | // 'catch', it will delegate the exception to that catch. It is being |
996 | // discussed how to define the semantics when 'delegate''s target is a non-try |
997 | // block: it will either be a validation failure or it will target the next |
998 | // outer try-catch. But anyway our LLVM backend currently does not generate |
999 | // such code. The example below illustrates where the 'delegate' instruction |
1000 | // in the middle will delegate the exception to, depending on the value of N. |
1001 | // try |
1002 | // try |
1003 | // block |
1004 | // try |
1005 | // try |
1006 | // call @foo |
1007 | // delegate N ;; Where will this delegate to? |
1008 | // catch ;; N == 0 |
1009 | // end |
1010 | // end ;; N == 1 (invalid; will not be generated) |
1011 | // delegate ;; N == 2 |
1012 | // catch ;; N == 3 |
1013 | // end |
1014 | // ;; N == 4 (to caller) |
1015 | |
1016 | // 1. When an instruction may throw, but the EH pad it will unwind to can be |
1017 | // different from the original CFG. |
1018 | // |
1019 | // Example: we have the following CFG: |
1020 | // bb0: |
1021 | // call @foo ; if it throws, unwind to bb2 |
1022 | // bb1: |
1023 | // call @bar ; if it throws, unwind to bb3 |
1024 | // bb2 (ehpad): |
1025 | // catch |
1026 | // ... |
1027 | // bb3 (ehpad) |
1028 | // catch |
1029 | // ... |
1030 | // |
1031 | // And the CFG is sorted in this order. Then after placing TRY markers, it |
1032 | // will look like: (BB markers are omitted) |
1033 | // try |
1034 | // try |
1035 | // call @foo |
1036 | // call @bar ;; if it throws, unwind to bb3 |
1037 | // catch ;; ehpad (bb2) |
1038 | // ... |
1039 | // end_try |
1040 | // catch ;; ehpad (bb3) |
1041 | // ... |
1042 | // end_try |
1043 | // |
1044 | // Now if bar() throws, it is going to end up ip in bb2, not bb3, where it |
1045 | // is supposed to end up. We solve this problem by wrapping the mismatching |
1046 | // call with an inner try-delegate that rethrows the exception to the right |
1047 | // 'catch'. |
1048 | // |
1049 | // try |
1050 | // try |
1051 | // call @foo |
1052 | // try ;; (new) |
1053 | // call @bar |
1054 | // delegate 1 (bb3) ;; (new) |
1055 | // catch ;; ehpad (bb2) |
1056 | // ... |
1057 | // end_try |
1058 | // catch ;; ehpad (bb3) |
1059 | // ... |
1060 | // end_try |
1061 | // |
1062 | // --- |
1063 | // 2. The same as 1, but in this case an instruction unwinds to a caller |
1064 | // function and not another EH pad. |
1065 | // |
1066 | // Example: we have the following CFG: |
1067 | // bb0: |
1068 | // call @foo ; if it throws, unwind to bb2 |
1069 | // bb1: |
1070 | // call @bar ; if it throws, unwind to caller |
1071 | // bb2 (ehpad): |
1072 | // catch |
1073 | // ... |
1074 | // |
1075 | // And the CFG is sorted in this order. Then after placing TRY markers, it |
1076 | // will look like: |
1077 | // try |
1078 | // call @foo |
1079 | // call @bar ;; if it throws, unwind to caller |
1080 | // catch ;; ehpad (bb2) |
1081 | // ... |
1082 | // end_try |
1083 | // |
1084 | // Now if bar() throws, it is going to end up ip in bb2, when it is supposed |
1085 | // throw up to the caller. We solve this problem in the same way, but in this |
1086 | // case 'delegate's immediate argument is the number of block depths + 1, |
1087 | // which means it rethrows to the caller. |
1088 | // try |
1089 | // call @foo |
1090 | // try ;; (new) |
1091 | // call @bar |
1092 | // delegate 1 (caller) ;; (new) |
1093 | // catch ;; ehpad (bb2) |
1094 | // ... |
1095 | // end_try |
1096 | // |
1097 | // Before rewriteDepthImmediates, delegate's argument is a BB. In case of the |
1098 | // caller, it will take a fake BB generated by getFakeCallerBlock(), which |
1099 | // will be converted to a correct immediate argument later. |
1100 | // |
1101 | // In case there are multiple calls in a BB that may throw to the caller, they |
1102 | // can be wrapped together in one nested try-delegate scope. (In 1, this |
1103 | // couldn't happen, because may-throwing instruction there had an unwind |
1104 | // destination, i.e., it was an invoke before, and there could be only one |
1105 | // invoke within a BB.) |
1106 | |
1107 | SmallVector<const MachineBasicBlock *, 8> EHPadStack; |
1108 | // Range of intructions to be wrapped in a new nested try/catch. A range |
1109 | // exists in a single BB and does not span multiple BBs. |
1110 | using TryRange = std::pair<MachineInstr *, MachineInstr *>; |
1111 | // In original CFG, <unwind destination BB, a vector of try ranges> |
1112 | DenseMap<MachineBasicBlock *, SmallVector<TryRange, 4>> UnwindDestToTryRanges; |
1113 | |
1114 | // Gather possibly throwing calls (i.e., previously invokes) whose current |
1115 | // unwind destination is not the same as the original CFG. (Case 1) |
1116 | |
1117 | for (auto &MBB : reverse(MF)) { |
1118 | bool SeenThrowableInstInBB = false; |
1119 | for (auto &MI : reverse(MBB)) { |
1120 | if (MI.getOpcode() == WebAssembly::TRY) |
1121 | EHPadStack.pop_back(); |
1122 | else if (WebAssembly::isCatch(MI.getOpcode())) |
1123 | EHPadStack.push_back(MI.getParent()); |
1124 | |
1125 | // In this loop we only gather calls that have an EH pad to unwind. So |
1126 | // there will be at most 1 such call (= invoke) in a BB, so after we've |
1127 | // seen one, we can skip the rest of BB. Also if MBB has no EH pad |
1128 | // successor or MI does not throw, this is not an invoke. |
1129 | if (SeenThrowableInstInBB || !MBB.hasEHPadSuccessor() || |
1130 | !WebAssembly::mayThrow(MI)) |
1131 | continue; |
1132 | SeenThrowableInstInBB = true; |
1133 | |
1134 | // If the EH pad on the stack top is where this instruction should unwind |
1135 | // next, we're good. |
1136 | MachineBasicBlock *UnwindDest = getFakeCallerBlock(MF); |
1137 | for (auto *Succ : MBB.successors()) { |
1138 | // Even though semantically a BB can have multiple successors in case an |
1139 | // exception is not caught by a catchpad, in our backend implementation |
1140 | // it is guaranteed that a BB can have at most one EH pad successor. For |
1141 | // details, refer to comments in findWasmUnwindDestinations function in |
1142 | // SelectionDAGBuilder.cpp. |
1143 | if (Succ->isEHPad()) { |
1144 | UnwindDest = Succ; |
1145 | break; |
1146 | } |
1147 | } |
1148 | if (EHPadStack.back() == UnwindDest) |
1149 | continue; |
1150 | |
1151 | // Include EH_LABELs in the range before and afer the invoke |
1152 | MachineInstr *RangeBegin = &MI, *RangeEnd = &MI; |
1153 | if (RangeBegin->getIterator() != MBB.begin() && |
1154 | std::prev(RangeBegin->getIterator())->isEHLabel()) |
1155 | RangeBegin = &*std::prev(RangeBegin->getIterator()); |
1156 | if (std::next(RangeEnd->getIterator()) != MBB.end() && |
1157 | std::next(RangeEnd->getIterator())->isEHLabel()) |
1158 | RangeEnd = &*std::next(RangeEnd->getIterator()); |
1159 | |
1160 | // If not, record the range. |
1161 | UnwindDestToTryRanges[UnwindDest].push_back( |
1162 | TryRange(RangeBegin, RangeEnd)); |
1163 | LLVM_DEBUG(dbgs() << "- Call unwind mismatch: MBB = " << MBB.getName()do { } while (false) |
1164 | << "\nCall = " << MIdo { } while (false) |
1165 | << "\nOriginal dest = " << UnwindDest->getName()do { } while (false) |
1166 | << " Current dest = " << EHPadStack.back()->getName()do { } while (false) |
1167 | << "\n\n")do { } while (false); |
1168 | } |
1169 | } |
1170 | |
1171 | assert(EHPadStack.empty())(static_cast<void> (0)); |
1172 | |
1173 | // Gather possibly throwing calls that are supposed to unwind up to the caller |
1174 | // if they throw, but currently unwind to an incorrect destination. Unlike the |
1175 | // loop above, there can be multiple calls within a BB that unwind to the |
1176 | // caller, which we should group together in a range. (Case 2) |
1177 | |
1178 | MachineInstr *RangeBegin = nullptr, *RangeEnd = nullptr; // inclusive |
1179 | |
1180 | // Record the range. |
1181 | auto RecordCallerMismatchRange = [&](const MachineBasicBlock *CurrentDest) { |
1182 | UnwindDestToTryRanges[getFakeCallerBlock(MF)].push_back( |
1183 | TryRange(RangeBegin, RangeEnd)); |
1184 | LLVM_DEBUG(dbgs() << "- Call unwind mismatch: MBB = "do { } while (false) |
1185 | << RangeBegin->getParent()->getName()do { } while (false) |
1186 | << "\nRange begin = " << *RangeBegindo { } while (false) |
1187 | << "Range end = " << *RangeEnddo { } while (false) |
1188 | << "\nOriginal dest = caller Current dest = "do { } while (false) |
1189 | << CurrentDest->getName() << "\n\n")do { } while (false); |
1190 | RangeBegin = RangeEnd = nullptr; // Reset range pointers |
1191 | }; |
1192 | |
1193 | for (auto &MBB : reverse(MF)) { |
1194 | bool SeenThrowableInstInBB = false; |
1195 | for (auto &MI : reverse(MBB)) { |
1196 | bool MayThrow = WebAssembly::mayThrow(MI); |
1197 | |
1198 | // If MBB has an EH pad successor and this is the last instruction that |
1199 | // may throw, this instruction unwinds to the EH pad and not to the |
1200 | // caller. |
1201 | if (MBB.hasEHPadSuccessor() && MayThrow && !SeenThrowableInstInBB) |
1202 | SeenThrowableInstInBB = true; |
1203 | |
1204 | // We wrap up the current range when we see a marker even if we haven't |
1205 | // finished a BB. |
1206 | else if (RangeEnd && WebAssembly::isMarker(MI.getOpcode())) |
1207 | RecordCallerMismatchRange(EHPadStack.back()); |
1208 | |
1209 | // If EHPadStack is empty, that means it correctly unwinds to the caller |
1210 | // if it throws, so we're good. If MI does not throw, we're good too. |
1211 | else if (EHPadStack.empty() || !MayThrow) { |
1212 | } |
1213 | |
1214 | // We found an instruction that unwinds to the caller but currently has an |
1215 | // incorrect unwind destination. Create a new range or increment the |
1216 | // currently existing range. |
1217 | else { |
1218 | if (!RangeEnd) |
1219 | RangeBegin = RangeEnd = &MI; |
1220 | else |
1221 | RangeBegin = &MI; |
1222 | } |
1223 | |
1224 | // Update EHPadStack. |
1225 | if (MI.getOpcode() == WebAssembly::TRY) |
1226 | EHPadStack.pop_back(); |
1227 | else if (WebAssembly::isCatch(MI.getOpcode())) |
1228 | EHPadStack.push_back(MI.getParent()); |
1229 | } |
1230 | |
1231 | if (RangeEnd) |
1232 | RecordCallerMismatchRange(EHPadStack.back()); |
1233 | } |
1234 | |
1235 | assert(EHPadStack.empty())(static_cast<void> (0)); |
1236 | |
1237 | // We don't have any unwind destination mismatches to resolve. |
1238 | if (UnwindDestToTryRanges.empty()) |
1239 | return false; |
1240 | |
1241 | // Now we fix the mismatches by wrapping calls with inner try-delegates. |
1242 | for (auto &P : UnwindDestToTryRanges) { |
1243 | NumCallUnwindMismatches += P.second.size(); |
1244 | MachineBasicBlock *UnwindDest = P.first; |
1245 | auto &TryRanges = P.second; |
1246 | |
1247 | for (auto Range : TryRanges) { |
1248 | MachineInstr *RangeBegin = nullptr, *RangeEnd = nullptr; |
1249 | std::tie(RangeBegin, RangeEnd) = Range; |
1250 | auto *MBB = RangeBegin->getParent(); |
1251 | |
1252 | // If this BB has an EH pad successor, i.e., ends with an 'invoke', now we |
1253 | // are going to wrap the invoke with try-delegate, making the 'delegate' |
1254 | // BB the new successor instead, so remove the EH pad succesor here. The |
1255 | // BB may not have an EH pad successor if calls in this BB throw to the |
1256 | // caller. |
1257 | MachineBasicBlock *EHPad = nullptr; |
1258 | for (auto *Succ : MBB->successors()) { |
1259 | if (Succ->isEHPad()) { |
1260 | EHPad = Succ; |
1261 | break; |
1262 | } |
1263 | } |
1264 | if (EHPad) |
1265 | MBB->removeSuccessor(EHPad); |
1266 | |
1267 | addTryDelegate(RangeBegin, RangeEnd, UnwindDest); |
1268 | } |
1269 | } |
1270 | |
1271 | return true; |
1272 | } |
1273 | |
1274 | bool WebAssemblyCFGStackify::fixCatchUnwindMismatches(MachineFunction &MF) { |
1275 | // There is another kind of unwind destination mismatches besides call unwind |
1276 | // mismatches, which we will call "catch unwind mismatches". See this example |
1277 | // after the marker placement: |
1278 | // try |
1279 | // try |
1280 | // call @foo |
1281 | // catch __cpp_exception ;; ehpad A (next unwind dest: caller) |
1282 | // ... |
1283 | // end_try |
1284 | // catch_all ;; ehpad B |
1285 | // ... |
1286 | // end_try |
1287 | // |
1288 | // 'call @foo's unwind destination is the ehpad A. But suppose 'call @foo' |
1289 | // throws a foreign exception that is not caught by ehpad A, and its next |
1290 | // destination should be the caller. But after control flow linearization, |
1291 | // another EH pad can be placed in between (e.g. ehpad B here), making the |
1292 | // next unwind destination incorrect. In this case, the foreign exception |
1293 | // will instead go to ehpad B and will be caught there instead. In this |
1294 | // example the correct next unwind destination is the caller, but it can be |
1295 | // another outer catch in other cases. |
1296 | // |
1297 | // There is no specific 'call' or 'throw' instruction to wrap with a |
1298 | // try-delegate, so we wrap the whole try-catch-end with a try-delegate and |
1299 | // make it rethrow to the right destination, as in the example below: |
1300 | // try |
1301 | // try ;; (new) |
1302 | // try |
1303 | // call @foo |
1304 | // catch __cpp_exception ;; ehpad A (next unwind dest: caller) |
1305 | // ... |
1306 | // end_try |
1307 | // delegate 1 (caller) ;; (new) |
1308 | // catch_all ;; ehpad B |
1309 | // ... |
1310 | // end_try |
1311 | |
1312 | const auto *EHInfo = MF.getWasmEHFuncInfo(); |
1313 | SmallVector<const MachineBasicBlock *, 8> EHPadStack; |
1314 | // For EH pads that have catch unwind mismatches, a map of <EH pad, its |
1315 | // correct unwind destination>. |
1316 | DenseMap<MachineBasicBlock *, MachineBasicBlock *> EHPadToUnwindDest; |
1317 | |
1318 | for (auto &MBB : reverse(MF)) { |
1319 | for (auto &MI : reverse(MBB)) { |
1320 | if (MI.getOpcode() == WebAssembly::TRY) |
1321 | EHPadStack.pop_back(); |
1322 | else if (MI.getOpcode() == WebAssembly::DELEGATE) |
1323 | EHPadStack.push_back(&MBB); |
1324 | else if (WebAssembly::isCatch(MI.getOpcode())) { |
1325 | auto *EHPad = &MBB; |
1326 | |
1327 | // catch_all always catches an exception, so we don't need to do |
1328 | // anything |
1329 | if (MI.getOpcode() == WebAssembly::CATCH_ALL) { |
1330 | } |
1331 | |
1332 | // This can happen when the unwind dest was removed during the |
1333 | // optimization, e.g. because it was unreachable. |
1334 | else if (EHPadStack.empty() && EHInfo->hasUnwindDest(EHPad)) { |
1335 | LLVM_DEBUG(dbgs() << "EHPad (" << EHPad->getName()do { } while (false) |
1336 | << "'s unwind destination does not exist anymore"do { } while (false) |
1337 | << "\n\n")do { } while (false); |
1338 | } |
1339 | |
1340 | // The EHPad's next unwind destination is the caller, but we incorrectly |
1341 | // unwind to another EH pad. |
1342 | else if (!EHPadStack.empty() && !EHInfo->hasUnwindDest(EHPad)) { |
1343 | EHPadToUnwindDest[EHPad] = getFakeCallerBlock(MF); |
1344 | LLVM_DEBUG(dbgs()do { } while (false) |
1345 | << "- Catch unwind mismatch:\nEHPad = " << EHPad->getName()do { } while (false) |
1346 | << " Original dest = caller Current dest = "do { } while (false) |
1347 | << EHPadStack.back()->getName() << "\n\n")do { } while (false); |
1348 | } |
1349 | |
1350 | // The EHPad's next unwind destination is an EH pad, whereas we |
1351 | // incorrectly unwind to another EH pad. |
1352 | else if (!EHPadStack.empty() && EHInfo->hasUnwindDest(EHPad)) { |
1353 | auto *UnwindDest = EHInfo->getUnwindDest(EHPad); |
1354 | if (EHPadStack.back() != UnwindDest) { |
1355 | EHPadToUnwindDest[EHPad] = UnwindDest; |
1356 | LLVM_DEBUG(dbgs() << "- Catch unwind mismatch:\nEHPad = "do { } while (false) |
1357 | << EHPad->getName() << " Original dest = "do { } while (false) |
1358 | << UnwindDest->getName() << " Current dest = "do { } while (false) |
1359 | << EHPadStack.back()->getName() << "\n\n")do { } while (false); |
1360 | } |
1361 | } |
1362 | |
1363 | EHPadStack.push_back(EHPad); |
1364 | } |
1365 | } |
1366 | } |
1367 | |
1368 | assert(EHPadStack.empty())(static_cast<void> (0)); |
1369 | if (EHPadToUnwindDest.empty()) |
1370 | return false; |
1371 | NumCatchUnwindMismatches += EHPadToUnwindDest.size(); |
1372 | SmallPtrSet<MachineBasicBlock *, 4> NewEndTryBBs; |
1373 | |
1374 | for (auto &P : EHPadToUnwindDest) { |
1375 | MachineBasicBlock *EHPad = P.first; |
1376 | MachineBasicBlock *UnwindDest = P.second; |
1377 | MachineInstr *Try = EHPadToTry[EHPad]; |
1378 | MachineInstr *EndTry = BeginToEnd[Try]; |
1379 | addTryDelegate(Try, EndTry, UnwindDest); |
1380 | NewEndTryBBs.insert(EndTry->getParent()); |
1381 | } |
1382 | |
1383 | // Adding a try-delegate wrapping an existing try-catch-end can make existing |
1384 | // branch destination BBs invalid. For example, |
1385 | // |
1386 | // - Before: |
1387 | // bb0: |
1388 | // block |
1389 | // br bb3 |
1390 | // bb1: |
1391 | // try |
1392 | // ... |
1393 | // bb2: (ehpad) |
1394 | // catch |
1395 | // bb3: |
1396 | // end_try |
1397 | // end_block ;; 'br bb3' targets here |
1398 | // |
1399 | // Suppose this try-catch-end has a catch unwind mismatch, so we need to wrap |
1400 | // this with a try-delegate. Then this becomes: |
1401 | // |
1402 | // - After: |
1403 | // bb0: |
1404 | // block |
1405 | // br bb3 ;; invalid destination! |
1406 | // bb1: |
1407 | // try ;; (new instruction) |
1408 | // try |
1409 | // ... |
1410 | // bb2: (ehpad) |
1411 | // catch |
1412 | // bb3: |
1413 | // end_try ;; 'br bb3' still incorrectly targets here! |
1414 | // delegate_bb: ;; (new BB) |
1415 | // delegate ;; (new instruction) |
1416 | // split_bb: ;; (new BB) |
1417 | // end_block |
1418 | // |
1419 | // Now 'br bb3' incorrectly branches to an inner scope. |
1420 | // |
1421 | // As we can see in this case, when branches target a BB that has both |
1422 | // 'end_try' and 'end_block' and the BB is split to insert a 'delegate', we |
1423 | // have to remap existing branch destinations so that they target not the |
1424 | // 'end_try' BB but the new 'end_block' BB. There can be multiple 'delegate's |
1425 | // in between, so we try to find the next BB with 'end_block' instruction. In |
1426 | // this example, the 'br bb3' instruction should be remapped to 'br split_bb'. |
1427 | for (auto &MBB : MF) { |
1428 | for (auto &MI : MBB) { |
1429 | if (MI.isTerminator()) { |
1430 | for (auto &MO : MI.operands()) { |
1431 | if (MO.isMBB() && NewEndTryBBs.count(MO.getMBB())) { |
1432 | auto *BrDest = MO.getMBB(); |
1433 | bool FoundEndBlock = false; |
1434 | for (; std::next(BrDest->getIterator()) != MF.end(); |
1435 | BrDest = BrDest->getNextNode()) { |
1436 | for (const auto &MI : *BrDest) { |
1437 | if (MI.getOpcode() == WebAssembly::END_BLOCK) { |
1438 | FoundEndBlock = true; |
1439 | break; |
1440 | } |
1441 | } |
1442 | if (FoundEndBlock) |
1443 | break; |
1444 | } |
1445 | assert(FoundEndBlock)(static_cast<void> (0)); |
1446 | MO.setMBB(BrDest); |
1447 | } |
1448 | } |
1449 | } |
1450 | } |
1451 | } |
1452 | |
1453 | return true; |
1454 | } |
1455 | |
1456 | void WebAssemblyCFGStackify::recalculateScopeTops(MachineFunction &MF) { |
1457 | // Renumber BBs and recalculate ScopeTop info because new BBs might have been |
1458 | // created and inserted during fixing unwind mismatches. |
1459 | MF.RenumberBlocks(); |
1460 | ScopeTops.clear(); |
1461 | ScopeTops.resize(MF.getNumBlockIDs()); |
1462 | for (auto &MBB : reverse(MF)) { |
1463 | for (auto &MI : reverse(MBB)) { |
1464 | if (ScopeTops[MBB.getNumber()]) |
1465 | break; |
1466 | switch (MI.getOpcode()) { |
1467 | case WebAssembly::END_BLOCK: |
1468 | case WebAssembly::END_LOOP: |
1469 | case WebAssembly::END_TRY: |
1470 | case WebAssembly::DELEGATE: |
1471 | updateScopeTops(EndToBegin[&MI]->getParent(), &MBB); |
1472 | break; |
1473 | case WebAssembly::CATCH: |
1474 | case WebAssembly::CATCH_ALL: |
1475 | updateScopeTops(EHPadToTry[&MBB]->getParent(), &MBB); |
1476 | break; |
1477 | } |
1478 | } |
1479 | } |
1480 | } |
1481 | |
1482 | /// In normal assembly languages, when the end of a function is unreachable, |
1483 | /// because the function ends in an infinite loop or a noreturn call or similar, |
1484 | /// it isn't necessary to worry about the function return type at the end of |
1485 | /// the function, because it's never reached. However, in WebAssembly, blocks |
1486 | /// that end at the function end need to have a return type signature that |
1487 | /// matches the function signature, even though it's unreachable. This function |
1488 | /// checks for such cases and fixes up the signatures. |
1489 | void WebAssemblyCFGStackify::fixEndsAtEndOfFunction(MachineFunction &MF) { |
1490 | const auto &MFI = *MF.getInfo<WebAssemblyFunctionInfo>(); |
1491 | |
1492 | if (MFI.getResults().empty()) |
1493 | return; |
1494 | |
1495 | // MCInstLower will add the proper types to multivalue signatures based on the |
1496 | // function return type |
1497 | WebAssembly::BlockType RetType = |
1498 | MFI.getResults().size() > 1 |
1499 | ? WebAssembly::BlockType::Multivalue |
1500 | : WebAssembly::BlockType( |
1501 | WebAssembly::toValType(MFI.getResults().front())); |
1502 | |
1503 | SmallVector<MachineBasicBlock::reverse_iterator, 4> Worklist; |
1504 | Worklist.push_back(MF.rbegin()->rbegin()); |
1505 | |
1506 | auto Process = [&](MachineBasicBlock::reverse_iterator It) { |
1507 | auto *MBB = It->getParent(); |
1508 | while (It != MBB->rend()) { |
1509 | MachineInstr &MI = *It++; |
1510 | if (MI.isPosition() || MI.isDebugInstr()) |
1511 | continue; |
1512 | switch (MI.getOpcode()) { |
1513 | case WebAssembly::END_TRY: { |
1514 | // If a 'try''s return type is fixed, both its try body and catch body |
1515 | // should satisfy the return type, so we need to search 'end' |
1516 | // instructions before its corresponding 'catch' too. |
1517 | auto *EHPad = TryToEHPad.lookup(EndToBegin[&MI]); |
1518 | assert(EHPad)(static_cast<void> (0)); |
1519 | auto NextIt = |
1520 | std::next(WebAssembly::findCatch(EHPad)->getReverseIterator()); |
1521 | if (NextIt != EHPad->rend()) |
1522 | Worklist.push_back(NextIt); |
1523 | LLVM_FALLTHROUGH[[gnu::fallthrough]]; |
1524 | } |
1525 | case WebAssembly::END_BLOCK: |
1526 | case WebAssembly::END_LOOP: |
1527 | case WebAssembly::DELEGATE: |
1528 | EndToBegin[&MI]->getOperand(0).setImm(int32_t(RetType)); |
1529 | continue; |
1530 | default: |
1531 | // Something other than an `end`. We're done for this BB. |
1532 | return; |
1533 | } |
1534 | } |
1535 | // We've reached the beginning of a BB. Continue the search in the previous |
1536 | // BB. |
1537 | Worklist.push_back(MBB->getPrevNode()->rbegin()); |
1538 | }; |
1539 | |
1540 | while (!Worklist.empty()) |
1541 | Process(Worklist.pop_back_val()); |
1542 | } |
1543 | |
1544 | // WebAssembly functions end with an end instruction, as if the function body |
1545 | // were a block. |
1546 | static void appendEndToFunction(MachineFunction &MF, |
1547 | const WebAssemblyInstrInfo &TII) { |
1548 | BuildMI(MF.back(), MF.back().end(), |
1549 | MF.back().findPrevDebugLoc(MF.back().end()), |
1550 | TII.get(WebAssembly::END_FUNCTION)); |
1551 | } |
1552 | |
1553 | /// Insert LOOP/TRY/BLOCK markers at appropriate places. |
1554 | void WebAssemblyCFGStackify::placeMarkers(MachineFunction &MF) { |
1555 | // We allocate one more than the number of blocks in the function to |
1556 | // accommodate for the possible fake block we may insert at the end. |
1557 | ScopeTops.resize(MF.getNumBlockIDs() + 1); |
1558 | // Place the LOOP for MBB if MBB is the header of a loop. |
1559 | for (auto &MBB : MF) |
1560 | placeLoopMarker(MBB); |
1561 | |
1562 | const MCAsmInfo *MCAI = MF.getTarget().getMCAsmInfo(); |
1563 | for (auto &MBB : MF) { |
1564 | if (MBB.isEHPad()) { |
1565 | // Place the TRY for MBB if MBB is the EH pad of an exception. |
1566 | if (MCAI->getExceptionHandlingType() == ExceptionHandling::Wasm && |
1567 | MF.getFunction().hasPersonalityFn()) |
1568 | placeTryMarker(MBB); |
1569 | } else { |
1570 | // Place the BLOCK for MBB if MBB is branched to from above. |
1571 | placeBlockMarker(MBB); |
1572 | } |
1573 | } |
1574 | // Fix mismatches in unwind destinations induced by linearizing the code. |
1575 | if (MCAI->getExceptionHandlingType() == ExceptionHandling::Wasm && |
1576 | MF.getFunction().hasPersonalityFn()) { |
1577 | bool Changed = fixCallUnwindMismatches(MF); |
1578 | Changed |= fixCatchUnwindMismatches(MF); |
1579 | if (Changed) |
1580 | recalculateScopeTops(MF); |
1581 | } |
1582 | } |
1583 | |
1584 | unsigned WebAssemblyCFGStackify::getBranchDepth( |
1585 | const SmallVectorImpl<EndMarkerInfo> &Stack, const MachineBasicBlock *MBB) { |
1586 | unsigned Depth = 0; |
1587 | for (auto X : reverse(Stack)) { |
1588 | if (X.first == MBB) |
1589 | break; |
1590 | ++Depth; |
1591 | } |
1592 | assert(Depth < Stack.size() && "Branch destination should be in scope")(static_cast<void> (0)); |
1593 | return Depth; |
1594 | } |
1595 | |
1596 | unsigned WebAssemblyCFGStackify::getDelegateDepth( |
1597 | const SmallVectorImpl<EndMarkerInfo> &Stack, const MachineBasicBlock *MBB) { |
1598 | if (MBB == FakeCallerBB) |
1599 | return Stack.size(); |
1600 | // Delegate's destination is either a catch or a another delegate BB. When the |
1601 | // destination is another delegate, we can compute the argument in the same |
1602 | // way as branches, because the target delegate BB only contains the single |
1603 | // delegate instruction. |
1604 | if (!MBB->isEHPad()) // Target is a delegate BB |
1605 | return getBranchDepth(Stack, MBB); |
1606 | |
1607 | // When the delegate's destination is a catch BB, we need to use its |
1608 | // corresponding try's end_try BB because Stack contains each marker's end BB. |
1609 | // Also we need to check if the end marker instruction matches, because a |
1610 | // single BB can contain multiple end markers, like this: |
1611 | // bb: |
1612 | // END_BLOCK |
1613 | // END_TRY |
1614 | // END_BLOCK |
1615 | // END_TRY |
1616 | // ... |
1617 | // |
1618 | // In case of branches getting the immediate that targets any of these is |
1619 | // fine, but delegate has to exactly target the correct try. |
1620 | unsigned Depth = 0; |
1621 | const MachineInstr *EndTry = BeginToEnd[EHPadToTry[MBB]]; |
1622 | for (auto X : reverse(Stack)) { |
1623 | if (X.first == EndTry->getParent() && X.second == EndTry) |
1624 | break; |
1625 | ++Depth; |
1626 | } |
1627 | assert(Depth < Stack.size() && "Delegate destination should be in scope")(static_cast<void> (0)); |
1628 | return Depth; |
1629 | } |
1630 | |
1631 | unsigned WebAssemblyCFGStackify::getRethrowDepth( |
1632 | const SmallVectorImpl<EndMarkerInfo> &Stack, |
1633 | const SmallVectorImpl<const MachineBasicBlock *> &EHPadStack) { |
1634 | unsigned Depth = 0; |
1635 | // In our current implementation, rethrows always rethrow the exception caught |
1636 | // by the innermost enclosing catch. This means while traversing Stack in the |
1637 | // reverse direction, when we encounter END_TRY, we should check if the |
1638 | // END_TRY corresponds to the current innermost EH pad. For example: |
1639 | // try |
1640 | // ... |
1641 | // catch ;; (a) |
1642 | // try |
1643 | // rethrow 1 ;; (b) |
1644 | // catch ;; (c) |
1645 | // rethrow 0 ;; (d) |
1646 | // end ;; (e) |
1647 | // end ;; (f) |
1648 | // |
1649 | // When we are at 'rethrow' (d), while reversely traversing Stack the first |
1650 | // 'end' we encounter is the 'end' (e), which corresponds to the 'catch' (c). |
1651 | // And 'rethrow' (d) rethrows the exception caught by 'catch' (c), so we stop |
1652 | // there and the depth should be 0. But when we are at 'rethrow' (b), it |
1653 | // rethrows the exception caught by 'catch' (a), so when traversing Stack |
1654 | // reversely, we should skip the 'end' (e) and choose 'end' (f), which |
1655 | // corresponds to 'catch' (a). |
1656 | for (auto X : reverse(Stack)) { |
1657 | const MachineInstr *End = X.second; |
1658 | if (End->getOpcode() == WebAssembly::END_TRY) { |
1659 | auto *EHPad = TryToEHPad[EndToBegin[End]]; |
1660 | if (EHPadStack.back() == EHPad) |
1661 | break; |
1662 | } |
1663 | ++Depth; |
1664 | } |
1665 | assert(Depth < Stack.size() && "Rethrow destination should be in scope")(static_cast<void> (0)); |
1666 | return Depth; |
1667 | } |
1668 | |
1669 | void WebAssemblyCFGStackify::rewriteDepthImmediates(MachineFunction &MF) { |
1670 | // Now rewrite references to basic blocks to be depth immediates. |
1671 | SmallVector<EndMarkerInfo, 8> Stack; |
1672 | SmallVector<const MachineBasicBlock *, 8> EHPadStack; |
1673 | for (auto &MBB : reverse(MF)) { |
1674 | for (auto I = MBB.rbegin(), E = MBB.rend(); I != E; ++I) { |
1675 | MachineInstr &MI = *I; |
1676 | switch (MI.getOpcode()) { |
1677 | case WebAssembly::BLOCK: |
1678 | case WebAssembly::TRY: |
1679 | assert(ScopeTops[Stack.back().first->getNumber()]->getNumber() <=(static_cast<void> (0)) |
1680 | MBB.getNumber() &&(static_cast<void> (0)) |
1681 | "Block/try marker should be balanced")(static_cast<void> (0)); |
1682 | Stack.pop_back(); |
1683 | break; |
1684 | |
1685 | case WebAssembly::LOOP: |
1686 | assert(Stack.back().first == &MBB && "Loop top should be balanced")(static_cast<void> (0)); |
1687 | Stack.pop_back(); |
1688 | break; |
1689 | |
1690 | case WebAssembly::END_BLOCK: |
1691 | Stack.push_back(std::make_pair(&MBB, &MI)); |
1692 | break; |
1693 | |
1694 | case WebAssembly::END_TRY: { |
1695 | // We handle DELEGATE in the default level, because DELEGATE has |
1696 | // immediate operands to rewrite. |
1697 | Stack.push_back(std::make_pair(&MBB, &MI)); |
1698 | auto *EHPad = TryToEHPad[EndToBegin[&MI]]; |
1699 | EHPadStack.push_back(EHPad); |
1700 | break; |
1701 | } |
1702 | |
1703 | case WebAssembly::END_LOOP: |
1704 | Stack.push_back(std::make_pair(EndToBegin[&MI]->getParent(), &MI)); |
1705 | break; |
1706 | |
1707 | case WebAssembly::CATCH: |
1708 | case WebAssembly::CATCH_ALL: |
1709 | EHPadStack.pop_back(); |
1710 | break; |
1711 | |
1712 | case WebAssembly::RETHROW: |
1713 | MI.getOperand(0).setImm(getRethrowDepth(Stack, EHPadStack)); |
1714 | break; |
1715 | |
1716 | default: |
1717 | if (MI.isTerminator()) { |
1718 | // Rewrite MBB operands to be depth immediates. |
1719 | SmallVector<MachineOperand, 4> Ops(MI.operands()); |
1720 | while (MI.getNumOperands() > 0) |
1721 | MI.RemoveOperand(MI.getNumOperands() - 1); |
1722 | for (auto MO : Ops) { |
1723 | if (MO.isMBB()) { |
1724 | if (MI.getOpcode() == WebAssembly::DELEGATE) |
1725 | MO = MachineOperand::CreateImm( |
1726 | getDelegateDepth(Stack, MO.getMBB())); |
1727 | else |
1728 | MO = MachineOperand::CreateImm( |
1729 | getBranchDepth(Stack, MO.getMBB())); |
1730 | } |
1731 | MI.addOperand(MF, MO); |
1732 | } |
1733 | } |
1734 | |
1735 | if (MI.getOpcode() == WebAssembly::DELEGATE) |
1736 | Stack.push_back(std::make_pair(&MBB, &MI)); |
1737 | break; |
1738 | } |
1739 | } |
1740 | } |
1741 | assert(Stack.empty() && "Control flow should be balanced")(static_cast<void> (0)); |
1742 | } |
1743 | |
1744 | void WebAssemblyCFGStackify::cleanupFunctionData(MachineFunction &MF) { |
1745 | if (FakeCallerBB) |
1746 | MF.DeleteMachineBasicBlock(FakeCallerBB); |
1747 | AppendixBB = FakeCallerBB = nullptr; |
1748 | } |
1749 | |
1750 | void WebAssemblyCFGStackify::releaseMemory() { |
1751 | ScopeTops.clear(); |
1752 | BeginToEnd.clear(); |
1753 | EndToBegin.clear(); |
1754 | TryToEHPad.clear(); |
1755 | EHPadToTry.clear(); |
1756 | } |
1757 | |
1758 | bool WebAssemblyCFGStackify::runOnMachineFunction(MachineFunction &MF) { |
1759 | LLVM_DEBUG(dbgs() << "********** CFG Stackifying **********\n"do { } while (false) |
1760 | "********** Function: "do { } while (false) |
1761 | << MF.getName() << '\n')do { } while (false); |
1762 | const MCAsmInfo *MCAI = MF.getTarget().getMCAsmInfo(); |
1763 | |
1764 | releaseMemory(); |
1765 | |
1766 | // Liveness is not tracked for VALUE_STACK physreg. |
1767 | MF.getRegInfo().invalidateLiveness(); |
1768 | |
1769 | // Place the BLOCK/LOOP/TRY markers to indicate the beginnings of scopes. |
1770 | placeMarkers(MF); |
1771 | |
1772 | // Remove unnecessary instructions possibly introduced by try/end_trys. |
1773 | if (MCAI->getExceptionHandlingType() == ExceptionHandling::Wasm && |
1774 | MF.getFunction().hasPersonalityFn()) |
1775 | removeUnnecessaryInstrs(MF); |
1776 | |
1777 | // Convert MBB operands in terminators to relative depth immediates. |
1778 | rewriteDepthImmediates(MF); |
1779 | |
1780 | // Fix up block/loop/try signatures at the end of the function to conform to |
1781 | // WebAssembly's rules. |
1782 | fixEndsAtEndOfFunction(MF); |
1783 | |
1784 | // Add an end instruction at the end of the function body. |
1785 | const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo(); |
1786 | if (!MF.getSubtarget<WebAssemblySubtarget>() |
1787 | .getTargetTriple() |
1788 | .isOSBinFormatELF()) |
1789 | appendEndToFunction(MF, TII); |
1790 | |
1791 | cleanupFunctionData(MF); |
1792 | |
1793 | MF.getInfo<WebAssemblyFunctionInfo>()->setCFGStackified(); |
1794 | return true; |
1795 | } |