diff --git a/llvm/lib/CodeGen/WasmEHPrepare.cpp b/llvm/lib/CodeGen/WasmEHPrepare.cpp --- a/llvm/lib/CodeGen/WasmEHPrepare.cpp +++ b/llvm/lib/CodeGen/WasmEHPrepare.cpp @@ -77,6 +77,7 @@ // //===----------------------------------------------------------------------===// +#include "llvm/ADT/BreadthFirstIterator.h" #include "llvm/ADT/SetVector.h" #include "llvm/ADT/Statistic.h" #include "llvm/ADT/Triple.h" @@ -118,14 +119,25 @@ bool prepareEHPads(Function &F); bool prepareThrows(Function &F); - void prepareEHPad(BasicBlock *BB, bool NeedLSDA, unsigned Index = 0); + void setupEHPadFunctions(Function &F); + void prepareEHPad(BasicBlock *BB, bool NeedPersonality, bool NeedLSDA = false, + unsigned Index = 0); void prepareTerminateCleanupPad(BasicBlock *BB); + // This set includes EH pad instructions for EH pads that have wasm.lsda() + // call either in the current EH pad or any of its parent EH pads that + // dominates the current one. + // + // Keys are CatchSwitchInsts, CatchPadInsts, and CleanupPadInsts, but the key + // type is Value* to reduce unnecssary castings. + // (FuncletPadInst::getParentPad() returns a Value*) + DenseSet ExecutedLSDA; + public: static char ID; // Pass identification, replacement for typeid WasmEHPrepare() : FunctionPass(ID) {} - + void getAnalysisUsage(AnalysisUsage &AU) const override; bool doInitialization(Module &M) override; bool runOnFunction(Function &F) override; @@ -136,11 +148,18 @@ } // end anonymous namespace char WasmEHPrepare::ID = 0; -INITIALIZE_PASS(WasmEHPrepare, DEBUG_TYPE, "Prepare WebAssembly exceptions", - false, false) +INITIALIZE_PASS_BEGIN(WasmEHPrepare, DEBUG_TYPE, + "Prepare WebAssembly exceptions", false, false) +INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) +INITIALIZE_PASS_END(WasmEHPrepare, DEBUG_TYPE, "Prepare WebAssembly exceptions", + false, false) FunctionPass *llvm::createWasmEHPass() { return new WasmEHPrepare(); } +void WasmEHPrepare::getAnalysisUsage(AnalysisUsage &AU) const { + AU.addRequired(); +} + bool WasmEHPrepare::doInitialization(Module &M) { IRBuilder<> IRB(M.getContext()); LPadContextTy = StructType::get(IRB.getInt32Ty(), // lpad_index @@ -201,23 +220,94 @@ } bool WasmEHPrepare::prepareEHPads(Function &F) { - Module &M = *F.getParent(); - IRBuilder<> IRB(F.getContext()); + auto &DT = getAnalysis().getDomTree(); + bool Changed = false; - SmallVector CatchPads; - SmallVector CleanupPads; - for (BasicBlock &BB : F) { - if (!BB.isEHPad()) + // There are two things to decide: whether we need a personality function call + // and whether we need a `wasm.lsda()` call and its store. + // + // For the personality function call, catchpads with `catch (...)` and + // cleanuppads don't need it, because exceptions are always caught. Others all + // need it. + // + // For `wasm.lsda()` and its store, in order to minimize the number of them, + // we need a way to figure out whether we have encountered `wasm.lsda()` call + // in any of EH pads that dominates the current EH pad. To figure that out, we + // now visit EH pads in BFS order in the dominator tree so that we visit + // parent BBs first before visiting its child BBs in the domtree. + // + // We keep a set named `ExecutedLSDA`, which basically means "Do we have + // `wasm.lsda() either in the current EH pad or any of its parent EH pads in + // the dominator tree?". This is to prevent scanning the domtree up to the + // root every time we examine an EH pad, in the worst case: each EH pad only + // needs to check its immediate parent EH pad. + // + // - If any of its parent EH pads in the domtree has `wasm.lsda`, this means + // we don't need `wasm.lsda()` in the current EH pad. We also insert the + // current EH pad in `ExecutedLSDA` set. + // - If none of its parent EH pad has `wasm.lsda()`, + // - If the current EH pad is a `catch (...)` or a cleanuppad, done. + // - If the current EH pad is neither a `catch (...)` nor a cleanuppad, + // add `wasm.lsda()` and the store in the current EH pad, and add the + // current EH pad to `ExecutedLSDA` set. + // + // TODO Can we not store LSDA address in user function but make libcxxabi + // compute it? + unsigned Index = 0; + for (auto DomNode : breadth_first(&DT)) { + auto *BB = DomNode->getBlock(); + auto *Pad = BB->getFirstNonPHI(); + if (!Pad || (!isa(Pad) && !isa(Pad))) continue; - auto *Pad = BB.getFirstNonPHI(); - if (isa(Pad)) - CatchPads.push_back(&BB); - else if (isa(Pad)) - CleanupPads.push_back(&BB); + Changed = true; + + Value *ParentPad = nullptr; + if (CatchPadInst *CPI = dyn_cast(Pad)) { + ParentPad = CPI->getCatchSwitch()->getParentPad(); + if (ExecutedLSDA.count(ParentPad)) { + ExecutedLSDA.insert(CPI); + // We insert its associated catchswitch too, because + // FuncletPadInst::getParentPad() returns a CatchSwitchInst if the child + // FuncletPadInst is a CleanupPadInst. + ExecutedLSDA.insert(CPI->getCatchSwitch()); + } + } else { // CleanupPadInst + ParentPad = cast(Pad)->getParentPad(); + if (ExecutedLSDA.count(ParentPad)) + ExecutedLSDA.insert(Pad); + } + + if (CatchPadInst *CPI = dyn_cast(Pad)) { + if (CPI->getNumArgOperands() == 1 && + cast(CPI->getArgOperand(0))->isNullValue()) + // In case of a single catch (...), we need neither personality call nor + // wasm.lsda() call + prepareEHPad(BB, false); + else { + if (ExecutedLSDA.count(CPI)) + // catch (type), but one of parents already has wasm.lsda() call + prepareEHPad(BB, true, false, Index++); + else { + // catch (type), and none of parents has wasm.lsda() call. We have to + // add the call in this EH pad, and record this EH pad in + // ExecutedLSDA. + ExecutedLSDA.insert(CPI); + ExecutedLSDA.insert(CPI->getCatchSwitch()); + prepareEHPad(BB, true, true, Index++); + } + } + } else if (isa(Pad)) { + // Cleanup pads need neither personality call nor wasm.lsda() call + prepareEHPad(BB, false); + } } - if (CatchPads.empty() && CleanupPads.empty()) - return false; + return Changed; +} + +void WasmEHPrepare::setupEHPadFunctions(Function &F) { + Module &M = *F.getParent(); + IRBuilder<> IRB(F.getContext()); assert(F.hasPersonalityFn() && "Personality function not found"); // __wasm_lpad_context global variable @@ -252,29 +342,17 @@ "_Unwind_CallPersonality", IRB.getInt32Ty(), IRB.getInt8PtrTy()); if (Function *F = dyn_cast(CallPersonalityF.getCallee())) F->setDoesNotThrow(); - - unsigned Index = 0; - for (auto *BB : CatchPads) { - auto *CPI = cast(BB->getFirstNonPHI()); - // In case of a single catch (...), we don't need to emit LSDA - if (CPI->getNumArgOperands() == 1 && - cast(CPI->getArgOperand(0))->isNullValue()) - prepareEHPad(BB, false); - else - prepareEHPad(BB, true, Index++); - } - - // Cleanup pads don't need LSDA. - for (auto *BB : CleanupPads) - prepareEHPad(BB, false); - - return true; } -// Prepare an EH pad for Wasm EH handling. If NeedLSDA is false, Index is +// Prepare an EH pad for Wasm EH handling. If NeedPersonality is false, Index is // ignored. -void WasmEHPrepare::prepareEHPad(BasicBlock *BB, bool NeedLSDA, - unsigned Index) { +void WasmEHPrepare::prepareEHPad(BasicBlock *BB, bool NeedPersonality, + bool NeedLSDA, unsigned Index) { + static bool init = false; + if (!init) { + init = true; + setupEHPadFunctions(*BB->getParent()); + } assert(BB->isEHPad() && "BB is not an EHPad!"); IRBuilder<> IRB(BB->getContext()); IRB.SetInsertPoint(&*BB->getFirstInsertionPt()); @@ -304,7 +382,7 @@ // In case it is a catchpad with single catch (...) or a cleanuppad, we don't // need to call personality function because we don't need a selector. - if (!NeedLSDA) { + if (!NeedPersonality) { if (GetSelectorCI) { assert(GetSelectorCI->use_empty() && "wasm.get.ehselector() still has uses!"); @@ -322,14 +400,8 @@ // Pseudocode: __wasm_lpad_context.lpad_index = index; IRB.CreateStore(IRB.getInt32(Index), LPadIndexField); - // Store LSDA address only if this catchpad belongs to a top-level - // catchswitch. If there is another catchpad that dominates this pad, we don't - // need to store LSDA address again, because they are the same throughout the - // function and have been already stored before. - // TODO Can we not store LSDA address in user function but make libcxxabi - // compute it? auto *CPI = cast(FPI); - if (isa(CPI->getCatchSwitch()->getParentPad())) + if (NeedLSDA) // Pseudocode: __wasm_lpad_context.lsda = wasm.lsda(); IRB.CreateStore(IRB.CreateCall(LSDAF), LSDAField); diff --git a/llvm/test/CodeGen/WebAssembly/wasmehprepare.ll b/llvm/test/CodeGen/WebAssembly/wasmehprepare.ll --- a/llvm/test/CodeGen/WebAssembly/wasmehprepare.ll +++ b/llvm/test/CodeGen/WebAssembly/wasmehprepare.ll @@ -132,7 +132,7 @@ ret void } -; A nested try-catch within a catch. +; A nested try-catch within a catch. The outer catch catches 'int'. ; ; void foo(); ; void test2() { @@ -219,19 +219,223 @@ unreachable } +; A nested try-catch within a catch. The outer catch is (...). +; +; void foo(); +; void test2() { +; try { +; foo(); +; } catch (...) { +; try { +; foo(); +; } catch (int) { +; } +; } +; } +; Within the innermost catchpad, wasm.lsda() call should be generated, because +; the outer catch is 'catch (...)', which does not need wasm.lsda() call. +define void @test3() personality i8* bitcast (i32 (...)* @__gxx_wasm_personality_v0 to i8*) { +; CHECK-LABEL: @test3() +entry: + invoke void @foo() + to label %try.cont8 unwind label %catch.dispatch + +catch.dispatch: ; preds = %entry + %0 = catchswitch within none [label %catch.start] unwind to caller + +catch.start: ; preds = %catch.dispatch + %1 = catchpad within %0 [i8* null] + %2 = call i8* @llvm.wasm.get.exception(token %1) + %3 = call i32 @llvm.wasm.get.ehselector(token %1) + %4 = call i8* @__cxa_begin_catch(i8* %2) [ "funclet"(token %1) ] + invoke void @foo() [ "funclet"(token %1) ] + to label %try.cont unwind label %catch.dispatch2 +; CHECK: catch.start: +; CHECK-NOT: call i8* @llvm.wasm.lsda() + +catch.dispatch2: ; preds = %catch.start + %5 = catchswitch within %1 [label %catch.start3] unwind label %ehcleanup + +catch.start3: ; preds = %catch.dispatch2 + %6 = catchpad within %5 [i8* bitcast (i8** @_ZTIi to i8*)] + %7 = call i8* @llvm.wasm.get.exception(token %6) + %8 = call i32 @llvm.wasm.get.ehselector(token %6) + %9 = call i32 @llvm.eh.typeid.for(i8* bitcast (i8** @_ZTIi to i8*)) + %matches = icmp eq i32 %8, %9 + br i1 %matches, label %catch4, label %rethrow +; CHECK: catch.start3: +; CHECK: call i8* @llvm.wasm.lsda() + +catch4: ; preds = %catch.start3 + %10 = call i8* @__cxa_begin_catch(i8* %7) [ "funclet"(token %6) ] + %11 = bitcast i8* %10 to i32* + %12 = load i32, i32* %11, align 4 + call void @__cxa_end_catch() [ "funclet"(token %6) ] + catchret from %6 to label %try.cont + +rethrow: ; preds = %catch.start3 + invoke void @llvm.wasm.rethrow.in.catch() [ "funclet"(token %6) ] + to label %unreachable unwind label %ehcleanup + +try.cont: ; preds = %catch.start, %catch4 + call void @__cxa_end_catch() [ "funclet"(token %1) ] + catchret from %1 to label %try.cont8 + +try.cont8: ; preds = %entry, %try.cont + ret void + +ehcleanup: ; preds = %rethrow, %catch.dispatch2 + %13 = cleanuppad within %1 [] + invoke void @__cxa_end_catch() [ "funclet"(token %13) ] + to label %invoke.cont6 unwind label %terminate + +invoke.cont6: ; preds = %ehcleanup + cleanupret from %13 unwind to caller + +unreachable: ; preds = %rethrow + unreachable + +terminate: ; preds = %ehcleanup + %14 = cleanuppad within %13 [] + %15 = call i8* @llvm.wasm.get.exception(token %14) + call void @__clang_call_terminate(i8* %15) [ "funclet"(token %14) ] + unreachable +} + +; void foo(); +; void test4() { +; try { +; foo(); +; } catch (int) { +; try { +; foo(); +; } catch (...) { +; try { +; foo(); +; } catch (int) { +; } +; } +; } +; } +; wasm.lsda() call should be generated only once in the outermost catchpad. The +; innermost 'catch (int)' can reuse the wasm.lsda() generated in the outermost +; catch. +define void @test4() personality i8* bitcast (i32 (...)* @__gxx_wasm_personality_v0 to i8*) { +; CHECK-LABEL: @test4() +entry: + invoke void @foo() + to label %try.cont19 unwind label %catch.dispatch + +catch.dispatch: ; preds = %entry + %0 = catchswitch within none [label %catch.start] unwind to caller + +catch.start: ; preds = %catch.dispatch + %1 = catchpad within %0 [i8* bitcast (i8** @_ZTIi to i8*)] + %2 = call i8* @llvm.wasm.get.exception(token %1) + %3 = call i32 @llvm.wasm.get.ehselector(token %1) + %4 = call i32 @llvm.eh.typeid.for(i8* bitcast (i8** @_ZTIi to i8*)) + %matches = icmp eq i32 %3, %4 + br i1 %matches, label %catch, label %rethrow +; CHECK: catch.start: +; CHECK: call i8* @llvm.wasm.lsda() + +catch: ; preds = %catch.start + %5 = call i8* @__cxa_begin_catch(i8* %2) [ "funclet"(token %1) ] + %6 = bitcast i8* %5 to i32* + %7 = load i32, i32* %6, align 4 + invoke void @foo() [ "funclet"(token %1) ] + to label %try.cont16 unwind label %catch.dispatch2 + +catch.dispatch2: ; preds = %catch + %8 = catchswitch within %1 [label %catch.start3] unwind label %ehcleanup17 + +catch.start3: ; preds = %catch.dispatch2 + %9 = catchpad within %8 [i8* null] + %10 = call i8* @llvm.wasm.get.exception(token %9) + %11 = call i32 @llvm.wasm.get.ehselector(token %9) + %12 = call i8* @__cxa_begin_catch(i8* %10) [ "funclet"(token %9) ] + invoke void @foo() [ "funclet"(token %9) ] + to label %try.cont unwind label %catch.dispatch7 +; CHECK: catch.start3: +; CHECK-NOT: call i8* @llvm.wasm.lsda() + +catch.dispatch7: ; preds = %catch.start3 + %13 = catchswitch within %9 [label %catch.start8] unwind label %ehcleanup + +catch.start8: ; preds = %catch.dispatch7 + %14 = catchpad within %13 [i8* bitcast (i8** @_ZTIi to i8*)] + %15 = call i8* @llvm.wasm.get.exception(token %14) + %16 = call i32 @llvm.wasm.get.ehselector(token %14) + %17 = call i32 @llvm.eh.typeid.for(i8* bitcast (i8** @_ZTIi to i8*)) + %matches9 = icmp eq i32 %16, %17 + br i1 %matches9, label %catch11, label %rethrow10 +; CHECK: catch.start8: +; CHECK-NOT: call i8* @llvm.wasm.lsda() + +catch11: ; preds = %catch.start8 + %18 = call i8* @__cxa_begin_catch(i8* %15) [ "funclet"(token %14) ] + %19 = bitcast i8* %18 to i32* + %20 = load i32, i32* %19, align 4 + call void @__cxa_end_catch() [ "funclet"(token %14) ] + catchret from %14 to label %try.cont + +rethrow10: ; preds = %catch.start8 + invoke void @llvm.wasm.rethrow.in.catch() [ "funclet"(token %14) ] + to label %unreachable unwind label %ehcleanup + +try.cont: ; preds = %catch.start3, %catch11 + invoke void @__cxa_end_catch() [ "funclet"(token %9) ] + to label %invoke.cont13 unwind label %ehcleanup17 + +invoke.cont13: ; preds = %try.cont + catchret from %9 to label %try.cont16 + +try.cont16: ; preds = %catch, %invoke.cont13 + call void @__cxa_end_catch() [ "funclet"(token %1) ] + catchret from %1 to label %try.cont19 + +rethrow: ; preds = %catch.start + call void @llvm.wasm.rethrow.in.catch() [ "funclet"(token %1) ] + unreachable + +try.cont19: ; preds = %entry, %try.cont16 + ret void + +ehcleanup: ; preds = %rethrow10, %catch.dispatch7 + %21 = cleanuppad within %9 [] + invoke void @__cxa_end_catch() [ "funclet"(token %21) ] + to label %invoke.cont14 unwind label %terminate + +invoke.cont14: ; preds = %ehcleanup + cleanupret from %21 unwind label %ehcleanup17 + +ehcleanup17: ; preds = %invoke.cont14, %try.cont, %catch.dispatch2 + %22 = cleanuppad within %1 [] + call void @__cxa_end_catch() [ "funclet"(token %22) ] + cleanupret from %22 unwind to caller + +unreachable: ; preds = %rethrow10 + unreachable + +terminate: ; preds = %ehcleanup + %23 = cleanuppad within %21 [] + %24 = call i8* @llvm.wasm.get.exception(token %23) + call void @__clang_call_terminate(i8* %24) [ "funclet"(token %23) ] + unreachable +} + ; A cleanuppad with a call to __clang_call_terminate(). -; A call to wasm.catch() should be generated after the cleanuppad. ; ; void foo(); -; void test3() { +; void test5() { ; try { ; foo(); ; } catch (...) { ; foo(); ; } ; } -define void @test3() personality i8* bitcast (i32 (...)* @__gxx_wasm_personality_v0 to i8*) { -; CHECK-LABEL: @test3 +define void @test5() personality i8* bitcast (i32 (...)* @__gxx_wasm_personality_v0 to i8*) { +; CHECK-LABEL: @test5 entry: invoke void @foo() to label %try.cont unwind label %catch.dispatch @@ -282,7 +486,7 @@ ; ~Temp() {} ; }; ; -; void test4() { +; void test6() { ; int num; ; try { ; Temp t; @@ -302,8 +506,8 @@ ; bar(num); ; } ; } -define void @test4() personality i8* bitcast (i32 (...)* @__gxx_wasm_personality_v0 to i8*) { -; CHECK-LABEL: @test4 +define void @test6() personality i8* bitcast (i32 (...)* @__gxx_wasm_personality_v0 to i8*) { +; CHECK-LABEL: @test6 entry: %t = alloca %struct.Temp, align 1 invoke void @foo() @@ -367,8 +571,8 @@ ; Tests if instructions after a call to @llvm.wasm.throw are deleted and the ; BB's dead children are deleted. -; CHECK-LABEL: @test5 -define i32 @test5(i1 %b, i8* %p) { +; CHECK-LABEL: @test7 +define i32 @test7(i1 %b, i8* %p) { entry: br i1 %b, label %bb.true, label %bb.false