aboutsummaryrefslogtreecommitdiff
path: root/contrib/llvm/lib/Target/WebAssembly/WebAssemblyCFGStackify.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'contrib/llvm/lib/Target/WebAssembly/WebAssemblyCFGStackify.cpp')
-rw-r--r--contrib/llvm/lib/Target/WebAssembly/WebAssemblyCFGStackify.cpp148
1 files changed, 96 insertions, 52 deletions
diff --git a/contrib/llvm/lib/Target/WebAssembly/WebAssemblyCFGStackify.cpp b/contrib/llvm/lib/Target/WebAssembly/WebAssemblyCFGStackify.cpp
index 33166f5b554f..49b9754e6b62 100644
--- a/contrib/llvm/lib/Target/WebAssembly/WebAssemblyCFGStackify.cpp
+++ b/contrib/llvm/lib/Target/WebAssembly/WebAssemblyCFGStackify.cpp
@@ -27,6 +27,7 @@
#include "MCTargetDesc/WebAssemblyMCTargetDesc.h"
#include "WebAssemblyMachineFunctionInfo.h"
#include "WebAssemblySubtarget.h"
+#include "WebAssemblyUtilities.h"
#include "llvm/ADT/PriorityQueue.h"
#include "llvm/ADT/SetVector.h"
#include "llvm/CodeGen/MachineDominators.h"
@@ -43,9 +44,7 @@ using namespace llvm;
namespace {
class WebAssemblyCFGStackify final : public MachineFunctionPass {
- const char *getPassName() const override {
- return "WebAssembly CFG Stackify";
- }
+ StringRef getPassName() const override { return "WebAssembly CFG Stackify"; }
void getAnalysisUsage(AnalysisUsage &AU) const override {
AU.setPreservesCFG();
@@ -294,26 +293,16 @@ static bool ExplicitlyBranchesTo(MachineBasicBlock *Pred,
return false;
}
-/// Test whether MI is a child of some other node in an expression tree.
-static bool IsChild(const MachineInstr &MI,
- const WebAssemblyFunctionInfo &MFI) {
- if (MI.getNumOperands() == 0)
- return false;
- const MachineOperand &MO = MI.getOperand(0);
- if (!MO.isReg() || MO.isImplicit() || !MO.isDef())
- return false;
- unsigned Reg = MO.getReg();
- return TargetRegisterInfo::isVirtualRegister(Reg) &&
- MFI.isVRegStackified(Reg);
-}
-
/// Insert a BLOCK marker for branches to MBB (if needed).
-static void PlaceBlockMarker(MachineBasicBlock &MBB, MachineFunction &MF,
- SmallVectorImpl<MachineBasicBlock *> &ScopeTops,
- const WebAssemblyInstrInfo &TII,
- const MachineLoopInfo &MLI,
- MachineDominatorTree &MDT,
- WebAssemblyFunctionInfo &MFI) {
+static void PlaceBlockMarker(
+ MachineBasicBlock &MBB, MachineFunction &MF,
+ SmallVectorImpl<MachineBasicBlock *> &ScopeTops,
+ DenseMap<const MachineInstr *, MachineInstr *> &BlockTops,
+ DenseMap<const MachineInstr *, MachineInstr *> &LoopTops,
+ const WebAssemblyInstrInfo &TII,
+ const MachineLoopInfo &MLI,
+ MachineDominatorTree &MDT,
+ WebAssemblyFunctionInfo &MFI) {
// First compute the nearest common dominator of all forward non-fallthrough
// predecessors so that we minimize the time that the BLOCK is on the stack,
// which reduces overall stack height.
@@ -332,7 +321,7 @@ static void PlaceBlockMarker(MachineBasicBlock &MBB, MachineFunction &MF,
return;
assert(&MBB != &MF.front() && "Header blocks shouldn't have predecessors");
- MachineBasicBlock *LayoutPred = &*prev(MachineFunction::iterator(&MBB));
+ MachineBasicBlock *LayoutPred = &*std::prev(MachineFunction::iterator(&MBB));
// If the nearest common dominator is inside a more deeply nested context,
// walk out to the nearest scope which isn't more deeply nested.
@@ -340,7 +329,7 @@ static void PlaceBlockMarker(MachineBasicBlock &MBB, MachineFunction &MF,
if (MachineBasicBlock *ScopeTop = ScopeTops[I->getNumber()]) {
if (ScopeTop->getNumber() > Header->getNumber()) {
// Skip over an intervening scope.
- I = next(MachineFunction::iterator(ScopeTop));
+ I = std::next(MachineFunction::iterator(ScopeTop));
} else {
// We found a scope level at an appropriate depth.
Header = ScopeTop;
@@ -349,13 +338,6 @@ static void PlaceBlockMarker(MachineBasicBlock &MBB, MachineFunction &MF,
}
}
- // If there's a loop which ends just before MBB which contains Header, we can
- // reuse its label instead of inserting a new BLOCK.
- for (MachineLoop *Loop = MLI.getLoopFor(LayoutPred);
- Loop && Loop->contains(LayoutPred); Loop = Loop->getParentLoop())
- if (Loop && LoopBottom(Loop) == LayoutPred && Loop->contains(Header))
- return;
-
// Decide where in Header to put the BLOCK.
MachineBasicBlock::iterator InsertPos;
MachineLoop *HeaderLoop = MLI.getLoopFor(Header);
@@ -363,28 +345,35 @@ static void PlaceBlockMarker(MachineBasicBlock &MBB, MachineFunction &MF,
// Header is the header of a loop that does not lexically contain MBB, so
// the BLOCK needs to be above the LOOP, after any END constructs.
InsertPos = Header->begin();
- while (InsertPos->getOpcode() != WebAssembly::LOOP)
+ while (InsertPos->getOpcode() == WebAssembly::END_BLOCK ||
+ InsertPos->getOpcode() == WebAssembly::END_LOOP)
++InsertPos;
} else {
// Otherwise, insert the BLOCK as late in Header as we can, but before the
// beginning of the local expression tree and any nested BLOCKs.
InsertPos = Header->getFirstTerminator();
- while (InsertPos != Header->begin() && IsChild(*prev(InsertPos), MFI) &&
- prev(InsertPos)->getOpcode() != WebAssembly::LOOP &&
- prev(InsertPos)->getOpcode() != WebAssembly::END_BLOCK &&
- prev(InsertPos)->getOpcode() != WebAssembly::END_LOOP)
+ while (InsertPos != Header->begin() &&
+ WebAssembly::isChild(*std::prev(InsertPos), MFI) &&
+ std::prev(InsertPos)->getOpcode() != WebAssembly::LOOP &&
+ std::prev(InsertPos)->getOpcode() != WebAssembly::END_BLOCK &&
+ std::prev(InsertPos)->getOpcode() != WebAssembly::END_LOOP)
--InsertPos;
}
// Add the BLOCK.
- BuildMI(*Header, InsertPos, DebugLoc(), TII.get(WebAssembly::BLOCK));
+ MachineInstr *Begin = BuildMI(*Header, InsertPos, DebugLoc(),
+ TII.get(WebAssembly::BLOCK))
+ .addImm(int64_t(WebAssembly::ExprType::Void));
// Mark the end of the block.
InsertPos = MBB.begin();
while (InsertPos != MBB.end() &&
- InsertPos->getOpcode() == WebAssembly::END_LOOP)
+ InsertPos->getOpcode() == WebAssembly::END_LOOP &&
+ LoopTops[&*InsertPos]->getParent()->getNumber() >= Header->getNumber())
++InsertPos;
- BuildMI(MBB, InsertPos, DebugLoc(), TII.get(WebAssembly::END_BLOCK));
+ MachineInstr *End = BuildMI(MBB, InsertPos, DebugLoc(),
+ TII.get(WebAssembly::END_BLOCK));
+ BlockTops[End] = Begin;
// Track the farthest-spanning scope that ends at this point.
int Number = MBB.getNumber();
@@ -397,7 +386,7 @@ static void PlaceBlockMarker(MachineBasicBlock &MBB, MachineFunction &MF,
static void PlaceLoopMarker(
MachineBasicBlock &MBB, MachineFunction &MF,
SmallVectorImpl<MachineBasicBlock *> &ScopeTops,
- DenseMap<const MachineInstr *, const MachineBasicBlock *> &LoopTops,
+ DenseMap<const MachineInstr *, MachineInstr *> &LoopTops,
const WebAssemblyInstrInfo &TII, const MachineLoopInfo &MLI) {
MachineLoop *Loop = MLI.getLoopFor(&MBB);
if (!Loop || Loop->getHeader() != &MBB)
@@ -406,13 +395,13 @@ static void PlaceLoopMarker(
// The operand of a LOOP is the first block after the loop. If the loop is the
// bottom of the function, insert a dummy block at the end.
MachineBasicBlock *Bottom = LoopBottom(Loop);
- auto Iter = next(MachineFunction::iterator(Bottom));
+ auto Iter = std::next(MachineFunction::iterator(Bottom));
if (Iter == MF.end()) {
MachineBasicBlock *Label = MF.CreateMachineBasicBlock();
// Give it a fake predecessor so that AsmPrinter prints its label.
Label->addSuccessor(Label);
MF.push_back(Label);
- Iter = next(MachineFunction::iterator(Bottom));
+ Iter = std::next(MachineFunction::iterator(Bottom));
}
MachineBasicBlock *AfterLoop = &*Iter;
@@ -422,12 +411,14 @@ static void PlaceLoopMarker(
while (InsertPos != MBB.end() &&
InsertPos->getOpcode() == WebAssembly::END_LOOP)
++InsertPos;
- BuildMI(MBB, InsertPos, DebugLoc(), TII.get(WebAssembly::LOOP));
+ MachineInstr *Begin = BuildMI(MBB, InsertPos, DebugLoc(),
+ TII.get(WebAssembly::LOOP))
+ .addImm(int64_t(WebAssembly::ExprType::Void));
// Mark the end of the loop.
MachineInstr *End = BuildMI(*AfterLoop, AfterLoop->begin(), DebugLoc(),
TII.get(WebAssembly::END_LOOP));
- LoopTops[End] = &MBB;
+ LoopTops[End] = Begin;
assert((!ScopeTops[AfterLoop->getNumber()] ||
ScopeTops[AfterLoop->getNumber()]->getNumber() < MBB.getNumber()) &&
@@ -449,6 +440,54 @@ GetDepth(const SmallVectorImpl<const MachineBasicBlock *> &Stack,
return Depth;
}
+/// In normal assembly languages, when the end of a function is unreachable,
+/// because the function ends in an infinite loop or a noreturn call or similar,
+/// it isn't necessary to worry about the function return type at the end of
+/// the function, because it's never reached. However, in WebAssembly, blocks
+/// that end at the function end need to have a return type signature that
+/// matches the function signature, even though it's unreachable. This function
+/// checks for such cases and fixes up the signatures.
+static void FixEndsAtEndOfFunction(
+ MachineFunction &MF,
+ const WebAssemblyFunctionInfo &MFI,
+ DenseMap<const MachineInstr *, MachineInstr *> &BlockTops,
+ DenseMap<const MachineInstr *, MachineInstr *> &LoopTops) {
+ assert(MFI.getResults().size() <= 1);
+
+ if (MFI.getResults().empty())
+ return;
+
+ WebAssembly::ExprType retType;
+ switch (MFI.getResults().front().SimpleTy) {
+ case MVT::i32: retType = WebAssembly::ExprType::I32; break;
+ case MVT::i64: retType = WebAssembly::ExprType::I64; break;
+ case MVT::f32: retType = WebAssembly::ExprType::F32; break;
+ case MVT::f64: retType = WebAssembly::ExprType::F64; break;
+ case MVT::v16i8: retType = WebAssembly::ExprType::I8x16; break;
+ case MVT::v8i16: retType = WebAssembly::ExprType::I16x8; break;
+ case MVT::v4i32: retType = WebAssembly::ExprType::I32x4; break;
+ case MVT::v4f32: retType = WebAssembly::ExprType::F32x4; break;
+ default: llvm_unreachable("unexpected return type");
+ }
+
+ for (MachineBasicBlock &MBB : reverse(MF)) {
+ for (MachineInstr &MI : reverse(MBB)) {
+ if (MI.isPosition() || MI.isDebugValue())
+ continue;
+ if (MI.getOpcode() == WebAssembly::END_BLOCK) {
+ BlockTops[&MI]->getOperand(0).setImm(int32_t(retType));
+ continue;
+ }
+ if (MI.getOpcode() == WebAssembly::END_LOOP) {
+ LoopTops[&MI]->getOperand(0).setImm(int32_t(retType));
+ continue;
+ }
+ // Something other than an `end`. We're done.
+ return;
+ }
+ }
+}
+
/// Insert LOOP and BLOCK markers at appropriate places.
static void PlaceMarkers(MachineFunction &MF, const MachineLoopInfo &MLI,
const WebAssemblyInstrInfo &TII,
@@ -461,15 +500,18 @@ static void PlaceMarkers(MachineFunction &MF, const MachineLoopInfo &MLI,
// we may insert at the end.
SmallVector<MachineBasicBlock *, 8> ScopeTops(MF.getNumBlockIDs() + 1);
- // For eacn LOOP_END, the corresponding LOOP.
- DenseMap<const MachineInstr *, const MachineBasicBlock *> LoopTops;
+ // For each LOOP_END, the corresponding LOOP.
+ DenseMap<const MachineInstr *, MachineInstr *> LoopTops;
+
+ // For each END_BLOCK, the corresponding BLOCK.
+ DenseMap<const MachineInstr *, MachineInstr *> BlockTops;
for (auto &MBB : MF) {
// Place the LOOP for MBB if MBB is the header of a loop.
PlaceLoopMarker(MBB, MF, ScopeTops, LoopTops, TII, MLI);
// Place the BLOCK for MBB if MBB is branched to from above.
- PlaceBlockMarker(MBB, MF, ScopeTops, TII, MLI, MDT, MFI);
+ PlaceBlockMarker(MBB, MF, ScopeTops, BlockTops, LoopTops, TII, MLI, MDT, MFI);
}
// Now rewrite references to basic blocks to be depth immediates.
@@ -478,21 +520,19 @@ static void PlaceMarkers(MachineFunction &MF, const MachineLoopInfo &MLI,
for (auto &MI : reverse(MBB)) {
switch (MI.getOpcode()) {
case WebAssembly::BLOCK:
- assert(ScopeTops[Stack.back()->getNumber()] == &MBB &&
+ assert(ScopeTops[Stack.back()->getNumber()]->getNumber() <= MBB.getNumber() &&
"Block should be balanced");
Stack.pop_back();
break;
case WebAssembly::LOOP:
assert(Stack.back() == &MBB && "Loop top should be balanced");
Stack.pop_back();
- Stack.pop_back();
break;
case WebAssembly::END_BLOCK:
Stack.push_back(&MBB);
break;
case WebAssembly::END_LOOP:
- Stack.push_back(&MBB);
- Stack.push_back(LoopTops[&MI]);
+ Stack.push_back(LoopTops[&MI]->getParent());
break;
default:
if (MI.isTerminator()) {
@@ -511,6 +551,10 @@ static void PlaceMarkers(MachineFunction &MF, const MachineLoopInfo &MLI,
}
}
assert(Stack.empty() && "Control flow should be balanced");
+
+ // Fix up block/loop signatures at the end of the function to conform to
+ // WebAssembly's rules.
+ FixEndsAtEndOfFunction(MF, MFI, BlockTops, LoopTops);
}
bool WebAssemblyCFGStackify::runOnMachineFunction(MachineFunction &MF) {
@@ -520,7 +564,7 @@ bool WebAssemblyCFGStackify::runOnMachineFunction(MachineFunction &MF) {
const auto &MLI = getAnalysis<MachineLoopInfo>();
auto &MDT = getAnalysis<MachineDominatorTree>();
- // Liveness is not tracked for EXPR_STACK physreg.
+ // Liveness is not tracked for VALUE_STACK physreg.
const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();
WebAssemblyFunctionInfo &MFI = *MF.getInfo<WebAssemblyFunctionInfo>();
MF.getRegInfo().invalidateLiveness();
generated by cgit v1.2.3 (git 2.25.1) at 2025-03-01 14:30:57 +0000