[WebAssembly] Fix subregion relationship in CFGSort

[aheejin]

Summary

The previous code for determining the innermost region in CFGSort was
not correct. We determine subregion relationship by domination of their
headers, i.e., if region A's header dominates region B's header, B is a
subregion of A. Previously we assumed that if a BB belongs to both a
loop and an exception, the region with fewer number of BBs is the
innermost one. This may not be true, because while WebAssemblyException
contains BBs in all its subregions (loops or exceptions), MachineLoop
may not, because MachineLoop does not contain BBs that don't have a path
to its header even if they are dominated by its header.

  Loop header  <---|
      |            |
Exception header   |
      | \          |
      A  B         |
      |   \        |
      |    C       |
      |            |
  Loop latch       |
      |            |
      -------------|

For example, in this CFG, the loop does not contain B and C, because
they don't have a path back to the loops header. But for CFGSort we
consider the exception here belongs to the loop and the exception should
be a subregion of the loop and scheduled together.

So here we should use WE->contains(ML->getHeader()) (but not
ML->contains(WE->getHeader()), for the stated region above).

This also fixes some comments and deletes Regions vector in
RegionInfo class, which was not used anywere.

[aheejin]

• Test fix

[dschuff]

llvm/lib/Target/WebAssembly/WebAssemblyCFGSort.cpp

99

do you mean "path" instead of "pass" here and in the commit message?

[aheejin]

llvm/lib/Target/WebAssembly/WebAssemblyCFGSort.cpp

99

Thanks, fixed.

llvm/lib/Target/WebAssembly/WebAssemblyCFGSort.cpp

 
 template <> bool ConcreteRegion<MachineLoop>::isLoop() const { return true; }
 
 // This class has information of nested Regions; this is analogous to what
 // LoopInfo is for loops.
 class RegionInfo {
   const MachineLoopInfo &MLI;
   const WebAssemblyExceptionInfo &WEI;
-  std::vector<const Region *> Regions;
   DenseMap<const MachineLoop *, std::unique_ptr<Region>> LoopMap;
   DenseMap<const WebAssemblyException *, std::unique_ptr<Region>> ExceptionMap;
 
 public:
   RegionInfo(const MachineLoopInfo &MLI, const WebAssemblyExceptionInfo &WEI)
       : MLI(MLI), WEI(WEI) {}
 
   // Returns a smallest loop or exception that contains MBB
   const Region *getRegionFor(const MachineBasicBlock *MBB) {
     const auto *ML = MLI.getLoopFor(MBB);
     const auto *WE = WEI.getExceptionFor(MBB);
     if (!ML && !WE)
       return nullptr;
-    if ((ML && !WE) || (ML && WE && ML->getNumBlocks() < WE->getNumBlocks())) {
+    // We determine subregion relationship by domination of their headers, i.e.,
+    // if region A's header dominates region B's header, B is a subregion of A.
+    // WebAssemblyException contains BBs in all its subregions (loops or
+    // exceptions), but MachineLoop may not, because MachineLoop does not contain
+    // BBs that don't have a path to its header even if they are dominated by
+    // its header. So here we should use WE->contains(ML->getHeader()), but not
+    // ML->contains(WE->getHeader()).
+    if ((ML && !WE) || (ML && WE && WE->contains(ML->getHeader()))) {
       // If the smallest region containing MBB is a loop
       if (LoopMap.count(ML))
         return LoopMap[ML].get();
       LoopMap[ML] = std::make_unique<ConcreteRegion<MachineLoop>>(ML);
       return LoopMap[ML].get();
     } else {
       // If the smallest region containing MBB is an exception
       if (ExceptionMap.count(WE))
#ifndef NDEBUG
   // executes once.
   OnStack.insert(nullptr);
 
   for (auto &MBB : MF) {
     assert(MBB.getNumber() >= 0 && "Renumbered blocks should be non-negative.");
     const Region *Region = RI.getRegionFor(&MBB);
 
     if (Region && &MBB == Region->getHeader()) {
+      // Region header.
       if (Region->isLoop()) {
         // Loop header. The loop predecessor should be sorted above, and the
         // other predecessors should be backedges below.
         for (auto Pred : MBB.predecessors())
           assert(
               (Pred->getNumber() < MBB.getNumber() || Region->contains(Pred)) &&
               "Loop header predecessors must be loop predecessors or "
               "backedges");
       } else {
-        // Not a loop header. All predecessors should be sorted above.
+        // Exception header. All predecessors should be sorted above.
         for (auto Pred : MBB.predecessors())
           assert(Pred->getNumber() < MBB.getNumber() &&
                  "Non-loop-header predecessors should be topologically sorted");
       }
       assert(OnStack.insert(Region) &&
              "Regions should be declared at most once.");
 
     } else {
-      // Not a loop header. All predecessors should be sorted above.
+      // Not a region header. All predecessors should be sorted above.
       for (auto Pred : MBB.predecessors())
         assert(Pred->getNumber() < MBB.getNumber() &&
                "Non-loop-header predecessors should be topologically sorted");
       assert(OnStack.count(RI.getRegionFor(&MBB)) &&
              "Blocks must be nested in their regions");
     }
     while (OnStack.size() > 1 && &MBB == WebAssembly::getBottom(OnStack.back()))
       OnStack.pop_back();

llvm/test/CodeGen/WebAssembly/cfg-stackify-eh.ll

 
 terminate:                                        ; preds = %entry
   %0 = cleanuppad within none []
   %1 = tail call i8* @llvm.wasm.get.exception(token %0)
   call void @__clang_call_terminate(i8* %1) [ "funclet"(token %0) ]
   unreachable
 }
 
+%class.MyClass = type { i32 }
+
+; This crashed on debug mode (= when NDEBUG is not defined) when the logic for
+; computing the innermost region was not correct, in which a loop region
+; contains an exception region. This should pass CFGSort without crashing.
+define void @test12() personality i8* bitcast (i32 (...)* @__gxx_wasm_personality_v0 to i8*) {
+entry:
+  %e = alloca %class.MyClass, align 4
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc, %entry
+  %i.0 = phi i32 [ 0, %entry ], [ %inc, %for.inc ]
+  %cmp = icmp slt i32 %i.0, 9
+  br i1 %cmp, label %for.body, label %for.end
+
+for.body:                                         ; preds = %for.cond
+  invoke void @quux(i32 %i.0)
+          to label %for.inc unwind label %catch.dispatch
+
+catch.dispatch:                                   ; preds = %for.body
+  %0 = catchswitch within none [label %catch.start] unwind to caller
+
+catch.start:                                      ; preds = %catch.dispatch
+  %1 = catchpad within %0 [i8* bitcast ({ i8*, i8* }* @_ZTI7MyClass 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*, i8* }* @_ZTI7MyClass to i8*)) #3
+  %matches = icmp eq i32 %3, %4
+  br i1 %matches, label %catch, label %rethrow
+
+catch:                                            ; preds = %catch.start
+  %5 = call i8* @__cxa_get_exception_ptr(i8* %2) #3 [ "funclet"(token %1) ]
+  %6 = bitcast i8* %5 to %class.MyClass*
+  %call = call %class.MyClass* @_ZN7MyClassC2ERKS_(%class.MyClass* %e, %class.MyClass* dereferenceable(4) %6) [ "funclet"(token %1) ]
+  %7 = call i8* @__cxa_begin_catch(i8* %2) #3 [ "funclet"(token %1) ]
+  %x = getelementptr inbounds %class.MyClass, %class.MyClass* %e, i32 0, i32 0
+  %8 = load i32, i32* %x, align 4
+  invoke void @quux(i32 %8) [ "funclet"(token %1) ]
+          to label %invoke.cont2 unwind label %ehcleanup
+
+invoke.cont2:                                     ; preds = %catch
+  %call3 = call %class.MyClass* @_ZN7MyClassD2Ev(%class.MyClass* %e) #3 [ "funclet"(token %1) ]
+  call void @__cxa_end_catch() [ "funclet"(token %1) ]
+  catchret from %1 to label %for.inc
+
+rethrow:                                          ; preds = %catch.start
+  call void @llvm.wasm.rethrow.in.catch() #6 [ "funclet"(token %1) ]
+  unreachable
+
+for.inc:                                          ; preds = %invoke.cont2, %for.body
+  %inc = add nsw i32 %i.0, 1
+  br label %for.cond
+
+ehcleanup:                                        ; preds = %catch
+  %9 = cleanuppad within %1 []
+  %call4 = call %class.MyClass* @_ZN7MyClassD2Ev(%class.MyClass* %e) #3 [ "funclet"(token %9) ]
+  invoke void @__cxa_end_catch() [ "funclet"(token %9) ]
+          to label %invoke.cont6 unwind label %terminate7
+
+invoke.cont6:                                     ; preds = %ehcleanup
+  cleanupret from %9 unwind to caller
+
+for.end:                                          ; preds = %for.cond
+  ret void
+
+terminate7:                                       ; preds = %ehcleanup
+  %10 = cleanuppad within %9 []
+  %11 = call i8* @llvm.wasm.get.exception(token %10)
+  call void @__clang_call_terminate(i8* %11) #7 [ "funclet"(token %10) ]
+  unreachable
+}
+
 ; Check if the unwind destination mismatch stats are correct
-; NOSORT-STAT: 11 wasm-cfg-stackify    - Number of EH pad unwind mismatches found
+; NOSORT-STAT: 14 wasm-cfg-stackify    - Number of EH pad unwind mismatches found
 
 declare void @foo()
 declare void @bar()
 declare i32 @baz()
+declare void @quux(i32)
 declare void @fun(i32)
 ; Function Attrs: nounwind
 declare void @nothrow(i32) #0
 declare i32 @nothrow_i32() #0
+
 ; Function Attrs: nounwind
 declare %class.Object* @_ZN6ObjectD2Ev(%class.Object* returned) #0
+@_ZTI7MyClass = external constant { i8*, i8* }, align 4
+; Function Attrs: nounwind
+declare %class.MyClass* @_ZN7MyClassD2Ev(%class.MyClass* returned) #0
+; Function Attrs: nounwind
+declare %class.MyClass* @_ZN7MyClassC2ERKS_(%class.MyClass* returned, %class.MyClass* dereferenceable(4)) #0
+
 declare i32 @__gxx_wasm_personality_v0(...)
 declare i8* @llvm.wasm.get.exception(token)
 declare i32 @llvm.wasm.get.ehselector(token)
 declare void @llvm.wasm.rethrow.in.catch()
 declare i32 @llvm.eh.typeid.for(i8*)
 declare i8* @__cxa_begin_catch(i8*)
 declare void @__cxa_end_catch()
+declare i8* @__cxa_get_exception_ptr(i8*)
 declare void @__clang_call_terminate(i8*)
 declare void @_ZSt9terminatev()
 ; Function Attrs: nounwind
 declare void @llvm.memcpy.p0i8.p0i8.i32(i8* noalias nocapture writeonly, i8* noalias nocapture readonly, i32, i1 immarg) #0
 ; Function Attrs: nounwind
 declare void @llvm.memmove.p0i8.p0i8.i32(i8* nocapture, i8* nocapture readonly, i32, i1 immarg) #0
 ; Function Attrs: nounwind
 declare void @llvm.memset.p0i8.i32(i8* nocapture writeonly, i8, i32, i1 immarg) #0
 
 attributes #0 = { nounwind }