[WebAssembly] Use SSAUpdaterBulk in LowerEmscriptenSjLj

[aheejin]

Summary

We update SSA in two steps in Emscripten SjLj:

1. Rewrite uses of setjmpTable and setjmpTableSize variables and place phis where necessary, which are updated where we call saveSetjmp.
2. Do a whole function level SSA update for all variables, because we split BBs where setjmp is called and there are possibly variable uses that are not dominated by a def. (See https://github.com/llvm/llvm-project/blob/955b91c19c00ed4c917559a5d66d14c669dde2e3/llvm/lib/Target/WebAssembly/WebAssemblyLowerEmscriptenEHSjLj.cpp#L1314-L1324)

We have been using SSAUpdater to do this, but SSAUpdaterBulk class
was added after this pass was first created, and for the step 2 it looks
like a better alternative with a possible performance benefit. Not sure
the author is aware of it, but SSAUpdaterBulk seems to have a
limitation: it cannot handle a use within the same BB as a def but
before it. For example:

... = %a + 1
%a = foo();

or

%a = %a + 1

The uses %a in RHS should be rewritten with another SSA variable of
%a, most likely one generated from a phi. But SSAUpdaterBulk
thinks all uses of %a are below the def of %a within the same BB.
(SSAUpdater has two different functions of rewriting because of this:
RewriteUse and RewriteUseAfterInsertions.) This doesn't affect our
usage in the step 2 because that deals with possibly non-dominated uses
by defs after block splitting. But it does in the step 1, which still
uses SSAUpdater.

But this CL also simplifies the step 1 by using make_early_inc_range,
removing the need to advance the iterator before rewriting a use.

This is NFC; the test changes are just the order of PHI nodes.

[aheejin]

llvm/test/CodeGen/WebAssembly/lower-em-sjlj.ll

225

This is just an order change of phi clauses and doesn't mean the number of clause has been increased from 1 to 2. Previously we were only checking the first clause.

[dschuff]

looks like a nice simplification.
It might be worth ccing the author of SSAUpdaterBulk as an FYI

[aheejin]

@mzolotukhin I'm trying to use SSAUpdaterBulk class here, and I'm wondering if this limitation is intended, and if so there is a way to work around that restriction. I'll paste the relevant paragraph in the CL description:

Not sure
the author is aware of it, but SSAUpdaterBulk seems to have a
limitation: it cannot handle a use within the same BB as a def but
before it. For example:

... = %a + 1
%a = foo();

or

%a = %a + 1

The uses %a in RHS should be rewritten with another SSA variable of
%a, most likely one generated from a phi. But SSAUpdaterBulk
thinks all uses of %a are below the def of %a within the same BB.
(SSAUpdater has two different functions of rewriting because of this:
RewriteUse and RewriteUseAfterInsertions.)

llvm/lib/Target/WebAssembly/WebAssemblyLowerEmscriptenEHSjLj.cpp

 #include "llvm/ADT/StringExtras.h"
 #include "llvm/CodeGen/TargetPassConfig.h"
 #include "llvm/IR/DebugInfoMetadata.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/IRBuilder.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
 #include "llvm/Transforms/Utils/SSAUpdater.h"
+#include "llvm/Transforms/Utils/SSAUpdaterBulk.h"
 
 using namespace llvm;
 
 #define DEBUG_TYPE "wasm-lower-em-ehsjlj"
 
 // Emscripten's asm.js-style exception handling
 extern cl::opt<bool> WasmEnableEmEH;
 // Emscripten's asm.js-style setjmp/longjmp handling
void WebAssemblyLowerEmscriptenEHSjLj::wrapTestSetjmp(
   Label = LabelPHI;
   EndBB = EndBB1;
   LongjmpResult = IRB.CreateCall(GetTempRet0F, None, "longjmp_result");
 }
 
 void WebAssemblyLowerEmscriptenEHSjLj::rebuildSSA(Function &F) {
   DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>(F).getDomTree();
   DT.recalculate(F); // CFG has been changed
-  SSAUpdater SSA;
+  SSAUpdaterBulk SSA;
   for (BasicBlock &BB : F) {
     for (Instruction &I : BB) {
-      SSA.Initialize(I.getType(), I.getName());
-      SSA.AddAvailableValue(&BB, &I);
-      for (auto UI = I.use_begin(), UE = I.use_end(); UI != UE;) {
-        Use &U = *UI;
-        ++UI;
+      unsigned VarID = SSA.AddVariable(I.getName(), I.getType());
+      SSA.AddAvailableValue(VarID, &BB, &I);
+      for (auto &U : I.uses()) {
         auto *User = cast<Instruction>(U.getUser());
         if (auto *UserPN = dyn_cast<PHINode>(User))
           if (UserPN->getIncomingBlock(U) == &BB)
             continue;
-
         if (DT.dominates(&I, User))
           continue;
-        SSA.RewriteUseAfterInsertions(U);
+        SSA.AddUse(VarID, &U);
       }
     }
   }
+  SSA.RewriteAllUses(&DT);
 }
 
 // Replace uses of longjmp with emscripten_longjmp. emscripten_longjmp takes
 // arguments of type {i32, i32} (wasm32) / {i64, i32} (wasm64) and longjmp takes
 // {jmp_buf*, i32}, so we need a ptrtoint instruction here to make the type
 // match. jmp_buf* will eventually be lowered to i32/i64 in the wasm backend.
 static void replaceLongjmpWithEmscriptenLongjmp(Function *LongjmpF,
                                                 Function *EmLongjmpF) {
bool WebAssemblyLowerEmscriptenEHSjLj::runSjLjOnFunction(Function &F) {
   SSAUpdater SetjmpTableSizeSSA;
   SetjmpTableSSA.Initialize(Type::getInt32PtrTy(C), "setjmpTable");
   SetjmpTableSizeSSA.Initialize(Type::getInt32Ty(C), "setjmpTableSize");
   for (Instruction *I : SetjmpTableInsts)
     SetjmpTableSSA.AddAvailableValue(I->getParent(), I);
   for (Instruction *I : SetjmpTableSizeInsts)
     SetjmpTableSizeSSA.AddAvailableValue(I->getParent(), I);
 
-  for (auto UI = SetjmpTable->use_begin(), UE = SetjmpTable->use_end();
-       UI != UE;) {
-    // Grab the use before incrementing the iterator.
-    Use &U = *UI;
-    // Increment the iterator before removing the use from the list.
-    ++UI;
+  for (auto &U : make_early_inc_range(SetjmpTable->uses()))
     if (auto *I = dyn_cast<Instruction>(U.getUser()))
       if (I->getParent() != Entry)
         SetjmpTableSSA.RewriteUse(U);
-  }
-  for (auto UI = SetjmpTableSize->use_begin(), UE = SetjmpTableSize->use_end();
-       UI != UE;) {
-    Use &U = *UI;
-    ++UI;
+  for (auto &U : make_early_inc_range(SetjmpTableSize->uses()))
     if (auto *I = dyn_cast<Instruction>(U.getUser()))
       if (I->getParent() != Entry)
         SetjmpTableSizeSSA.RewriteUse(U);
-  }
 
   // Finally, our modifications to the cfg can break dominance of SSA variables.
   // For example, in this code,
   // if (x()) { .. setjmp() .. }
   // if (y()) { .. longjmp() .. }
   // We must split the longjmp block, and it can jump into the block splitted
   // from setjmp one. But that means that when we split the setjmp block, it's
   // first part no longer dominates its second part - there is a theoretically
   // possible control flow path where x() is false, then y() is true and we
   // reach the second part of the setjmp block, without ever reaching the first
   // part. So, we rebuild SSA form here.
   rebuildSSA(F);
   return true;
 }

llvm/test/CodeGen/WebAssembly/lower-em-sjlj.ll

if.then:                                          ; preds = %entry
   store i32 %0, i32* @global_var, align 4
   br label %if.end
 ; CHECK: if.then:
 ; CHECK: %[[VAR0:.*]] = load i32, i32* @global_var, align 4
 ; CHECK: %[[SETJMP_TABLE1:.*]] = call i32* @saveSetjmp(
 ; CHECK-NEXT: %[[SETJMP_TABLE_SIZE1:.*]] = call i32 @getTempRet0()
 
 ; CHECK: if.then.split:
-; CHECK: %[[VAR1:.*]] = phi i32 [ %[[VAR0]], %if.then ], [ %[[VAR2:.*]], %if.end3 ]
+; CHECK: %[[VAR1:.*]] = phi i32 [ %[[VAR2:.*]], %if.end3 ], [ %[[VAR0]], %if.then ]
 ; CHECK: %[[SETJMP_TABLE_SIZE2:.*]] = phi i32 [ %[[SETJMP_TABLE_SIZE1]], %if.then ], [ %[[SETJMP_TABLE_SIZE3:.*]], %if.end3 ]
 ; CHECK: %[[SETJMP_TABLE2:.*]] = phi i32* [ %[[SETJMP_TABLE1]], %if.then ], [ %[[SETJMP_TABLE3:.*]], %if.end3 ]
 ; CHECK: store i32 %[[VAR1]], i32* @global_var, align 4
 
 if.end:                                           ; preds = %if.then, %entry
   %arraydecay1 = getelementptr inbounds [1 x %struct.__jmp_buf_tag], [1 x %struct.__jmp_buf_tag]* %buf, i32 0, i32 0
   call void @longjmp(%struct.__jmp_buf_tag* %arraydecay1, i32 5) #1
   unreachable
for.cond:                                         ; preds = %for.inc, %entry
   %var = add i32 0, 0
   br label %for.inc
 
 for.inc:                                          ; preds = %for.cond
   %call5 = call i32 @setjmp(%struct.__jmp_buf_tag* undef) #0
   br label %for.cond
 
 ; CHECK: for.inc.split:
-  ; CHECK: %var[[VARNO]] = phi i32 [ %var, %for.inc ]
+  ; CHECK: %var[[VARNO]] = phi i32 [ undef, %if.end ], [ %var, %for.inc ]
 }
 
 ; Tests cases where longjmp function pointer is used in other ways than direct
 ; calls. longjmps should be replaced with
 ; (int(*)(jmp_buf*, int))emscripten_longjmp.
 declare void @take_longjmp(void (%struct.__jmp_buf_tag*, i32)* %arg_ptr)
 define void @indirect_longjmp() {
 ; CHECK-LABEL: @indirect_longjmp