LLVM 17.0.0git
WebAssemblyRegStackify.cpp
Go to the documentation of this file.
1//===-- WebAssemblyRegStackify.cpp - Register 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 register stacking pass.
11///
12/// This pass reorders instructions to put register uses and defs in an order
13/// such that they form single-use expression trees. Registers fitting this form
14/// are then marked as "stackified", meaning references to them are replaced by
15/// "push" and "pop" from the value stack.
16///
17/// This is primarily a code size optimization, since temporary values on the
18/// value stack don't need to be named.
19///
20//===----------------------------------------------------------------------===//
21
22#include "MCTargetDesc/WebAssemblyMCTargetDesc.h" // for WebAssembly::ARGUMENT_*
24#include "WebAssembly.h"
36#include "llvm/CodeGen/Passes.h"
37#include "llvm/Support/Debug.h"
39#include <iterator>
40using namespace llvm;
41
42#define DEBUG_TYPE "wasm-reg-stackify"
43
44namespace {
45class WebAssemblyRegStackify final : public MachineFunctionPass {
46 StringRef getPassName() const override {
47 return "WebAssembly Register Stackify";
48 }
49
50 void getAnalysisUsage(AnalysisUsage &AU) const override {
51 AU.setPreservesCFG();
60 }
61
62 bool runOnMachineFunction(MachineFunction &MF) override;
63
64public:
65 static char ID; // Pass identification, replacement for typeid
66 WebAssemblyRegStackify() : MachineFunctionPass(ID) {}
67};
68} // end anonymous namespace
69
70char WebAssemblyRegStackify::ID = 0;
71INITIALIZE_PASS(WebAssemblyRegStackify, DEBUG_TYPE,
72 "Reorder instructions to use the WebAssembly value stack",
73 false, false)
74
76 return new WebAssemblyRegStackify();
77}
78
79// Decorate the given instruction with implicit operands that enforce the
80// expression stack ordering constraints for an instruction which is on
81// the expression stack.
83 // Write the opaque VALUE_STACK register.
84 if (!MI->definesRegister(WebAssembly::VALUE_STACK))
85 MI->addOperand(MachineOperand::CreateReg(WebAssembly::VALUE_STACK,
86 /*isDef=*/true,
87 /*isImp=*/true));
88
89 // Also read the opaque VALUE_STACK register.
90 if (!MI->readsRegister(WebAssembly::VALUE_STACK))
91 MI->addOperand(MachineOperand::CreateReg(WebAssembly::VALUE_STACK,
92 /*isDef=*/false,
93 /*isImp=*/true));
94}
95
96// Convert an IMPLICIT_DEF instruction into an instruction which defines
97// a constant zero value.
100 const TargetInstrInfo *TII,
101 MachineFunction &MF,
102 LiveIntervals &LIS) {
103 assert(MI->getOpcode() == TargetOpcode::IMPLICIT_DEF);
104
105 const auto *RegClass = MRI.getRegClass(MI->getOperand(0).getReg());
106 if (RegClass == &WebAssembly::I32RegClass) {
107 MI->setDesc(TII->get(WebAssembly::CONST_I32));
108 MI->addOperand(MachineOperand::CreateImm(0));
109 } else if (RegClass == &WebAssembly::I64RegClass) {
110 MI->setDesc(TII->get(WebAssembly::CONST_I64));
111 MI->addOperand(MachineOperand::CreateImm(0));
112 } else if (RegClass == &WebAssembly::F32RegClass) {
113 MI->setDesc(TII->get(WebAssembly::CONST_F32));
114 auto *Val = cast<ConstantFP>(Constant::getNullValue(
116 MI->addOperand(MachineOperand::CreateFPImm(Val));
117 } else if (RegClass == &WebAssembly::F64RegClass) {
118 MI->setDesc(TII->get(WebAssembly::CONST_F64));
119 auto *Val = cast<ConstantFP>(Constant::getNullValue(
121 MI->addOperand(MachineOperand::CreateFPImm(Val));
122 } else if (RegClass == &WebAssembly::V128RegClass) {
123 MI->setDesc(TII->get(WebAssembly::CONST_V128_I64x2));
124 MI->addOperand(MachineOperand::CreateImm(0));
125 MI->addOperand(MachineOperand::CreateImm(0));
126 } else {
127 llvm_unreachable("Unexpected reg class");
128 }
129}
130
131// Determine whether a call to the callee referenced by
132// MI->getOperand(CalleeOpNo) reads memory, writes memory, and/or has side
133// effects.
134static void queryCallee(const MachineInstr &MI, bool &Read, bool &Write,
135 bool &Effects, bool &StackPointer) {
136 // All calls can use the stack pointer.
137 StackPointer = true;
138
140 if (MO.isGlobal()) {
141 const Constant *GV = MO.getGlobal();
142 if (const auto *GA = dyn_cast<GlobalAlias>(GV))
143 if (!GA->isInterposable())
144 GV = GA->getAliasee();
145
146 if (const auto *F = dyn_cast<Function>(GV)) {
147 if (!F->doesNotThrow())
148 Effects = true;
149 if (F->doesNotAccessMemory())
150 return;
151 if (F->onlyReadsMemory()) {
152 Read = true;
153 return;
154 }
155 }
156 }
157
158 // Assume the worst.
159 Write = true;
160 Read = true;
161 Effects = true;
162}
163
164// Determine whether MI reads memory, writes memory, has side effects,
165// and/or uses the stack pointer value.
166static void query(const MachineInstr &MI, bool &Read, bool &Write,
167 bool &Effects, bool &StackPointer) {
168 assert(!MI.isTerminator());
169
170 if (MI.isDebugInstr() || MI.isPosition())
171 return;
172
173 // Check for loads.
174 if (MI.mayLoad() && !MI.isDereferenceableInvariantLoad())
175 Read = true;
176
177 // Check for stores.
178 if (MI.mayStore()) {
179 Write = true;
180 } else if (MI.hasOrderedMemoryRef()) {
181 switch (MI.getOpcode()) {
182 case WebAssembly::DIV_S_I32:
183 case WebAssembly::DIV_S_I64:
184 case WebAssembly::REM_S_I32:
185 case WebAssembly::REM_S_I64:
186 case WebAssembly::DIV_U_I32:
187 case WebAssembly::DIV_U_I64:
188 case WebAssembly::REM_U_I32:
189 case WebAssembly::REM_U_I64:
190 case WebAssembly::I32_TRUNC_S_F32:
191 case WebAssembly::I64_TRUNC_S_F32:
192 case WebAssembly::I32_TRUNC_S_F64:
193 case WebAssembly::I64_TRUNC_S_F64:
194 case WebAssembly::I32_TRUNC_U_F32:
195 case WebAssembly::I64_TRUNC_U_F32:
196 case WebAssembly::I32_TRUNC_U_F64:
197 case WebAssembly::I64_TRUNC_U_F64:
198 // These instruction have hasUnmodeledSideEffects() returning true
199 // because they trap on overflow and invalid so they can't be arbitrarily
200 // moved, however hasOrderedMemoryRef() interprets this plus their lack
201 // of memoperands as having a potential unknown memory reference.
202 break;
203 default:
204 // Record volatile accesses, unless it's a call, as calls are handled
205 // specially below.
206 if (!MI.isCall()) {
207 Write = true;
208 Effects = true;
209 }
210 break;
211 }
212 }
213
214 // Check for side effects.
215 if (MI.hasUnmodeledSideEffects()) {
216 switch (MI.getOpcode()) {
217 case WebAssembly::DIV_S_I32:
218 case WebAssembly::DIV_S_I64:
219 case WebAssembly::REM_S_I32:
220 case WebAssembly::REM_S_I64:
221 case WebAssembly::DIV_U_I32:
222 case WebAssembly::DIV_U_I64:
223 case WebAssembly::REM_U_I32:
224 case WebAssembly::REM_U_I64:
225 case WebAssembly::I32_TRUNC_S_F32:
226 case WebAssembly::I64_TRUNC_S_F32:
227 case WebAssembly::I32_TRUNC_S_F64:
228 case WebAssembly::I64_TRUNC_S_F64:
229 case WebAssembly::I32_TRUNC_U_F32:
230 case WebAssembly::I64_TRUNC_U_F32:
231 case WebAssembly::I32_TRUNC_U_F64:
232 case WebAssembly::I64_TRUNC_U_F64:
233 // These instructions have hasUnmodeledSideEffects() returning true
234 // because they trap on overflow and invalid so they can't be arbitrarily
235 // moved, however in the specific case of register stackifying, it is safe
236 // to move them because overflow and invalid are Undefined Behavior.
237 break;
238 default:
239 Effects = true;
240 break;
241 }
242 }
243
244 // Check for writes to __stack_pointer global.
245 if ((MI.getOpcode() == WebAssembly::GLOBAL_SET_I32 ||
246 MI.getOpcode() == WebAssembly::GLOBAL_SET_I64) &&
247 strcmp(MI.getOperand(0).getSymbolName(), "__stack_pointer") == 0)
248 StackPointer = true;
249
250 // Analyze calls.
251 if (MI.isCall()) {
252 queryCallee(MI, Read, Write, Effects, StackPointer);
253 }
254}
255
256// Test whether Def is safe and profitable to rematerialize.
257static bool shouldRematerialize(const MachineInstr &Def,
258 const WebAssemblyInstrInfo *TII) {
259 return Def.isAsCheapAsAMove() && TII->isTriviallyReMaterializable(Def);
260}
261
262// Identify the definition for this register at this point. This is a
263// generalization of MachineRegisterInfo::getUniqueVRegDef that uses
264// LiveIntervals to handle complex cases.
265static MachineInstr *getVRegDef(unsigned Reg, const MachineInstr *Insert,
267 const LiveIntervals &LIS) {
268 // Most registers are in SSA form here so we try a quick MRI query first.
269 if (MachineInstr *Def = MRI.getUniqueVRegDef(Reg))
270 return Def;
271
272 // MRI doesn't know what the Def is. Try asking LIS.
273 if (const VNInfo *ValNo = LIS.getInterval(Reg).getVNInfoBefore(
274 LIS.getInstructionIndex(*Insert)))
275 return LIS.getInstructionFromIndex(ValNo->def);
276
277 return nullptr;
278}
279
280// Test whether Reg, as defined at Def, has exactly one use. This is a
281// generalization of MachineRegisterInfo::hasOneUse that uses LiveIntervals
282// to handle complex cases.
283static bool hasOneUse(unsigned Reg, MachineInstr *Def, MachineRegisterInfo &MRI,
285 // Most registers are in SSA form here so we try a quick MRI query first.
286 if (MRI.hasOneUse(Reg))
287 return true;
288
289 bool HasOne = false;
290 const LiveInterval &LI = LIS.getInterval(Reg);
291 const VNInfo *DefVNI =
293 assert(DefVNI);
294 for (auto &I : MRI.use_nodbg_operands(Reg)) {
295 const auto &Result = LI.Query(LIS.getInstructionIndex(*I.getParent()));
296 if (Result.valueIn() == DefVNI) {
297 if (!Result.isKill())
298 return false;
299 if (HasOne)
300 return false;
301 HasOne = true;
302 }
303 }
304 return HasOne;
305}
306
307// Test whether it's safe to move Def to just before Insert.
308// TODO: Compute memory dependencies in a way that doesn't require always
309// walking the block.
310// TODO: Compute memory dependencies in a way that uses AliasAnalysis to be
311// more precise.
312static bool isSafeToMove(const MachineOperand *Def, const MachineOperand *Use,
313 const MachineInstr *Insert,
314 const WebAssemblyFunctionInfo &MFI,
315 const MachineRegisterInfo &MRI) {
316 const MachineInstr *DefI = Def->getParent();
317 const MachineInstr *UseI = Use->getParent();
318 assert(DefI->getParent() == Insert->getParent());
319 assert(UseI->getParent() == Insert->getParent());
320
321 // The first def of a multivalue instruction can be stackified by moving,
322 // since the later defs can always be placed into locals if necessary. Later
323 // defs can only be stackified if all previous defs are already stackified
324 // since ExplicitLocals will not know how to place a def in a local if a
325 // subsequent def is stackified. But only one def can be stackified by moving
326 // the instruction, so it must be the first one.
327 //
328 // TODO: This could be loosened to be the first *live* def, but care would
329 // have to be taken to ensure the drops of the initial dead defs can be
330 // placed. This would require checking that no previous defs are used in the
331 // same instruction as subsequent defs.
332 if (Def != DefI->defs().begin())
333 return false;
334
335 // If any subsequent def is used prior to the current value by the same
336 // instruction in which the current value is used, we cannot
337 // stackify. Stackifying in this case would require that def moving below the
338 // current def in the stack, which cannot be achieved, even with locals.
339 // Also ensure we don't sink the def past any other prior uses.
340 for (const auto &SubsequentDef : drop_begin(DefI->defs())) {
341 auto I = std::next(MachineBasicBlock::const_iterator(DefI));
342 auto E = std::next(MachineBasicBlock::const_iterator(UseI));
343 for (; I != E; ++I) {
344 for (const auto &PriorUse : I->uses()) {
345 if (&PriorUse == Use)
346 break;
347 if (PriorUse.isReg() && SubsequentDef.getReg() == PriorUse.getReg())
348 return false;
349 }
350 }
351 }
352
353 // If moving is a semantic nop, it is always allowed
354 const MachineBasicBlock *MBB = DefI->getParent();
355 auto NextI = std::next(MachineBasicBlock::const_iterator(DefI));
356 for (auto E = MBB->end(); NextI != E && NextI->isDebugInstr(); ++NextI)
357 ;
358 if (NextI == Insert)
359 return true;
360
361 // 'catch' and 'catch_all' should be the first instruction of a BB and cannot
362 // move.
363 if (WebAssembly::isCatch(DefI->getOpcode()))
364 return false;
365
366 // Check for register dependencies.
367 SmallVector<unsigned, 4> MutableRegisters;
368 for (const MachineOperand &MO : DefI->operands()) {
369 if (!MO.isReg() || MO.isUndef())
370 continue;
371 Register Reg = MO.getReg();
372
373 // If the register is dead here and at Insert, ignore it.
374 if (MO.isDead() && Insert->definesRegister(Reg) &&
375 !Insert->readsRegister(Reg))
376 continue;
377
378 if (Reg.isPhysical()) {
379 // Ignore ARGUMENTS; it's just used to keep the ARGUMENT_* instructions
380 // from moving down, and we've already checked for that.
381 if (Reg == WebAssembly::ARGUMENTS)
382 continue;
383 // If the physical register is never modified, ignore it.
384 if (!MRI.isPhysRegModified(Reg))
385 continue;
386 // Otherwise, it's a physical register with unknown liveness.
387 return false;
388 }
389
390 // If one of the operands isn't in SSA form, it has different values at
391 // different times, and we need to make sure we don't move our use across
392 // a different def.
393 if (!MO.isDef() && !MRI.hasOneDef(Reg))
394 MutableRegisters.push_back(Reg);
395 }
396
397 bool Read = false, Write = false, Effects = false, StackPointer = false;
398 query(*DefI, Read, Write, Effects, StackPointer);
399
400 // If the instruction does not access memory and has no side effects, it has
401 // no additional dependencies.
402 bool HasMutableRegisters = !MutableRegisters.empty();
403 if (!Read && !Write && !Effects && !StackPointer && !HasMutableRegisters)
404 return true;
405
406 // Scan through the intervening instructions between DefI and Insert.
408 for (--I; I != D; --I) {
409 bool InterveningRead = false;
410 bool InterveningWrite = false;
411 bool InterveningEffects = false;
412 bool InterveningStackPointer = false;
413 query(*I, InterveningRead, InterveningWrite, InterveningEffects,
414 InterveningStackPointer);
415 if (Effects && InterveningEffects)
416 return false;
417 if (Read && InterveningWrite)
418 return false;
419 if (Write && (InterveningRead || InterveningWrite))
420 return false;
421 if (StackPointer && InterveningStackPointer)
422 return false;
423
424 for (unsigned Reg : MutableRegisters)
425 for (const MachineOperand &MO : I->operands())
426 if (MO.isReg() && MO.isDef() && MO.getReg() == Reg)
427 return false;
428 }
429
430 return true;
431}
432
433/// Test whether OneUse, a use of Reg, dominates all of Reg's other uses.
434static bool oneUseDominatesOtherUses(unsigned Reg, const MachineOperand &OneUse,
435 const MachineBasicBlock &MBB,
437 const MachineDominatorTree &MDT,
438 LiveIntervals &LIS,
440 const LiveInterval &LI = LIS.getInterval(Reg);
441
442 const MachineInstr *OneUseInst = OneUse.getParent();
443 VNInfo *OneUseVNI = LI.getVNInfoBefore(LIS.getInstructionIndex(*OneUseInst));
444
445 for (const MachineOperand &Use : MRI.use_nodbg_operands(Reg)) {
446 if (&Use == &OneUse)
447 continue;
448
449 const MachineInstr *UseInst = Use.getParent();
450 VNInfo *UseVNI = LI.getVNInfoBefore(LIS.getInstructionIndex(*UseInst));
451
452 if (UseVNI != OneUseVNI)
453 continue;
454
455 if (UseInst == OneUseInst) {
456 // Another use in the same instruction. We need to ensure that the one
457 // selected use happens "before" it.
458 if (&OneUse > &Use)
459 return false;
460 } else {
461 // Test that the use is dominated by the one selected use.
462 while (!MDT.dominates(OneUseInst, UseInst)) {
463 // Actually, dominating is over-conservative. Test that the use would
464 // happen after the one selected use in the stack evaluation order.
465 //
466 // This is needed as a consequence of using implicit local.gets for
467 // uses and implicit local.sets for defs.
468 if (UseInst->getDesc().getNumDefs() == 0)
469 return false;
470 const MachineOperand &MO = UseInst->getOperand(0);
471 if (!MO.isReg())
472 return false;
473 Register DefReg = MO.getReg();
474 if (!DefReg.isVirtual() || !MFI.isVRegStackified(DefReg))
475 return false;
476 assert(MRI.hasOneNonDBGUse(DefReg));
477 const MachineOperand &NewUse = *MRI.use_nodbg_begin(DefReg);
478 const MachineInstr *NewUseInst = NewUse.getParent();
479 if (NewUseInst == OneUseInst) {
480 if (&OneUse > &NewUse)
481 return false;
482 break;
483 }
484 UseInst = NewUseInst;
485 }
486 }
487 }
488 return true;
489}
490
491/// Get the appropriate tee opcode for the given register class.
492static unsigned getTeeOpcode(const TargetRegisterClass *RC) {
493 if (RC == &WebAssembly::I32RegClass)
494 return WebAssembly::TEE_I32;
495 if (RC == &WebAssembly::I64RegClass)
496 return WebAssembly::TEE_I64;
497 if (RC == &WebAssembly::F32RegClass)
498 return WebAssembly::TEE_F32;
499 if (RC == &WebAssembly::F64RegClass)
500 return WebAssembly::TEE_F64;
501 if (RC == &WebAssembly::V128RegClass)
502 return WebAssembly::TEE_V128;
503 if (RC == &WebAssembly::EXTERNREFRegClass)
504 return WebAssembly::TEE_EXTERNREF;
505 if (RC == &WebAssembly::FUNCREFRegClass)
506 return WebAssembly::TEE_FUNCREF;
507 llvm_unreachable("Unexpected register class");
508}
509
510// Shrink LI to its uses, cleaning up LI.
512 if (LIS.shrinkToUses(&LI)) {
514 LIS.splitSeparateComponents(LI, SplitLIs);
515 }
516}
517
518/// A single-use def in the same block with no intervening memory or register
519/// dependencies; move the def down and nest it with the current instruction.
522 MachineInstr *Insert, LiveIntervals &LIS,
525 LLVM_DEBUG(dbgs() << "Move for single use: "; Def->dump());
526
528 MBB.splice(Insert, &MBB, Def);
529 DefDIs.move(Insert);
530 LIS.handleMove(*Def);
531
532 if (MRI.hasOneDef(Reg) && MRI.hasOneUse(Reg)) {
533 // No one else is using this register for anything so we can just stackify
534 // it in place.
535 MFI.stackifyVReg(MRI, Reg);
536 } else {
537 // The register may have unrelated uses or defs; create a new register for
538 // just our one def and use so that we can stackify it.
539 Register NewReg = MRI.createVirtualRegister(MRI.getRegClass(Reg));
540 Def->getOperand(0).setReg(NewReg);
541 Op.setReg(NewReg);
542
543 // Tell LiveIntervals about the new register.
545
546 // Tell LiveIntervals about the changes to the old register.
547 LiveInterval &LI = LIS.getInterval(Reg);
549 LIS.getInstructionIndex(*Op.getParent()).getRegSlot(),
550 /*RemoveDeadValNo=*/true);
551
552 MFI.stackifyVReg(MRI, NewReg);
553
554 DefDIs.updateReg(NewReg);
555
556 LLVM_DEBUG(dbgs() << " - Replaced register: "; Def->dump());
557 }
558
560 return Def;
561}
562
563/// A trivially cloneable instruction; clone it and nest the new copy with the
564/// current instruction.
566 unsigned Reg, MachineOperand &Op, MachineInstr &Def, MachineBasicBlock &MBB,
570 LLVM_DEBUG(dbgs() << "Rematerializing cheap def: "; Def.dump());
571 LLVM_DEBUG(dbgs() << " - for use in "; Op.getParent()->dump());
572
573 WebAssemblyDebugValueManager DefDIs(&Def);
574
575 Register NewReg = MRI.createVirtualRegister(MRI.getRegClass(Reg));
576 TII->reMaterialize(MBB, Insert, NewReg, 0, Def, *TRI);
577 Op.setReg(NewReg);
578 MachineInstr *Clone = &*std::prev(Insert);
579 LIS.InsertMachineInstrInMaps(*Clone);
581 MFI.stackifyVReg(MRI, NewReg);
582 imposeStackOrdering(Clone);
583
584 LLVM_DEBUG(dbgs() << " - Cloned to "; Clone->dump());
585
586 // Shrink the interval.
587 bool IsDead = MRI.use_empty(Reg);
588 if (!IsDead) {
589 LiveInterval &LI = LIS.getInterval(Reg);
590 shrinkToUses(LI, LIS);
592 }
593
594 // If that was the last use of the original, delete the original.
595 // Move or clone corresponding DBG_VALUEs to the 'Insert' location.
596 if (IsDead) {
597 LLVM_DEBUG(dbgs() << " - Deleting original\n");
599 LIS.removePhysRegDefAt(MCRegister::from(WebAssembly::ARGUMENTS), Idx);
600 LIS.removeInterval(Reg);
602 Def.eraseFromParent();
603
604 DefDIs.move(&*Insert);
605 DefDIs.updateReg(NewReg);
606 } else {
607 DefDIs.clone(&*Insert, NewReg);
608 }
609
610 return Clone;
611}
612
613/// A multiple-use def in the same block with no intervening memory or register
614/// dependencies; move the def down, nest it with the current instruction, and
615/// insert a tee to satisfy the rest of the uses. As an illustration, rewrite
616/// this:
617///
618/// Reg = INST ... // Def
619/// INST ..., Reg, ... // Insert
620/// INST ..., Reg, ...
621/// INST ..., Reg, ...
622///
623/// to this:
624///
625/// DefReg = INST ... // Def (to become the new Insert)
626/// TeeReg, Reg = TEE_... DefReg
627/// INST ..., TeeReg, ... // Insert
628/// INST ..., Reg, ...
629/// INST ..., Reg, ...
630///
631/// with DefReg and TeeReg stackified. This eliminates a local.get from the
632/// resulting code.
634 unsigned Reg, MachineOperand &Op, MachineInstr *Def, MachineBasicBlock &MBB,
637 LLVM_DEBUG(dbgs() << "Move and tee for multi-use:"; Def->dump());
638
640
641 // Move Def into place.
642 MBB.splice(Insert, &MBB, Def);
643 LIS.handleMove(*Def);
644
645 // Create the Tee and attach the registers.
646 const auto *RegClass = MRI.getRegClass(Reg);
647 Register TeeReg = MRI.createVirtualRegister(RegClass);
648 Register DefReg = MRI.createVirtualRegister(RegClass);
649 MachineOperand &DefMO = Def->getOperand(0);
650 MachineInstr *Tee = BuildMI(MBB, Insert, Insert->getDebugLoc(),
651 TII->get(getTeeOpcode(RegClass)), TeeReg)
653 .addReg(DefReg, getUndefRegState(DefMO.isDead()));
654 Op.setReg(TeeReg);
655 DefMO.setReg(DefReg);
656 SlotIndex TeeIdx = LIS.InsertMachineInstrInMaps(*Tee).getRegSlot();
657 SlotIndex DefIdx = LIS.getInstructionIndex(*Def).getRegSlot();
658
659 DefDIs.move(Insert);
660
661 // Tell LiveIntervals we moved the original vreg def from Def to Tee.
662 LiveInterval &LI = LIS.getInterval(Reg);
664 VNInfo *ValNo = LI.getVNInfoAt(DefIdx);
665 I->start = TeeIdx;
666 ValNo->def = TeeIdx;
667 shrinkToUses(LI, LIS);
668
669 // Finish stackifying the new regs.
672 MFI.stackifyVReg(MRI, DefReg);
673 MFI.stackifyVReg(MRI, TeeReg);
676
677 DefDIs.clone(Tee, DefReg);
678 DefDIs.clone(Insert, TeeReg);
679
680 LLVM_DEBUG(dbgs() << " - Replaced register: "; Def->dump());
681 LLVM_DEBUG(dbgs() << " - Tee instruction: "; Tee->dump());
682 return Def;
683}
684
685namespace {
686/// A stack for walking the tree of instructions being built, visiting the
687/// MachineOperands in DFS order.
688class TreeWalkerState {
689 using mop_iterator = MachineInstr::mop_iterator;
690 using mop_reverse_iterator = std::reverse_iterator<mop_iterator>;
693
694public:
695 explicit TreeWalkerState(MachineInstr *Insert) {
696 const iterator_range<mop_iterator> &Range = Insert->explicit_uses();
697 if (!Range.empty())
698 Worklist.push_back(reverse(Range));
699 }
700
701 bool done() const { return Worklist.empty(); }
702
703 MachineOperand &pop() {
704 RangeTy &Range = Worklist.back();
705 MachineOperand &Op = *Range.begin();
706 Range = drop_begin(Range);
707 if (Range.empty())
708 Worklist.pop_back();
709 assert((Worklist.empty() || !Worklist.back().empty()) &&
710 "Empty ranges shouldn't remain in the worklist");
711 return Op;
712 }
713
714 /// Push Instr's operands onto the stack to be visited.
715 void pushOperands(MachineInstr *Instr) {
717 if (!Range.empty())
718 Worklist.push_back(reverse(Range));
719 }
720
721 /// Some of Instr's operands are on the top of the stack; remove them and
722 /// re-insert them starting from the beginning (because we've commuted them).
723 void resetTopOperands(MachineInstr *Instr) {
724 assert(hasRemainingOperands(Instr) &&
725 "Reseting operands should only be done when the instruction has "
726 "an operand still on the stack");
727 Worklist.back() = reverse(Instr->explicit_uses());
728 }
729
730 /// Test whether Instr has operands remaining to be visited at the top of
731 /// the stack.
732 bool hasRemainingOperands(const MachineInstr *Instr) const {
733 if (Worklist.empty())
734 return false;
735 const RangeTy &Range = Worklist.back();
736 return !Range.empty() && Range.begin()->getParent() == Instr;
737 }
738
739 /// Test whether the given register is present on the stack, indicating an
740 /// operand in the tree that we haven't visited yet. Moving a definition of
741 /// Reg to a point in the tree after that would change its value.
742 ///
743 /// This is needed as a consequence of using implicit local.gets for
744 /// uses and implicit local.sets for defs.
745 bool isOnStack(unsigned Reg) const {
746 for (const RangeTy &Range : Worklist)
747 for (const MachineOperand &MO : Range)
748 if (MO.isReg() && MO.getReg() == Reg)
749 return true;
750 return false;
751 }
752};
753
754/// State to keep track of whether commuting is in flight or whether it's been
755/// tried for the current instruction and didn't work.
756class CommutingState {
757 /// There are effectively three states: the initial state where we haven't
758 /// started commuting anything and we don't know anything yet, the tentative
759 /// state where we've commuted the operands of the current instruction and are
760 /// revisiting it, and the declined state where we've reverted the operands
761 /// back to their original order and will no longer commute it further.
762 bool TentativelyCommuting = false;
763 bool Declined = false;
764
765 /// During the tentative state, these hold the operand indices of the commuted
766 /// operands.
767 unsigned Operand0, Operand1;
768
769public:
770 /// Stackification for an operand was not successful due to ordering
771 /// constraints. If possible, and if we haven't already tried it and declined
772 /// it, commute Insert's operands and prepare to revisit it.
773 void maybeCommute(MachineInstr *Insert, TreeWalkerState &TreeWalker,
774 const WebAssemblyInstrInfo *TII) {
775 if (TentativelyCommuting) {
776 assert(!Declined &&
777 "Don't decline commuting until you've finished trying it");
778 // Commuting didn't help. Revert it.
779 TII->commuteInstruction(*Insert, /*NewMI=*/false, Operand0, Operand1);
780 TentativelyCommuting = false;
781 Declined = true;
782 } else if (!Declined && TreeWalker.hasRemainingOperands(Insert)) {
785 if (TII->findCommutedOpIndices(*Insert, Operand0, Operand1)) {
786 // Tentatively commute the operands and try again.
787 TII->commuteInstruction(*Insert, /*NewMI=*/false, Operand0, Operand1);
788 TreeWalker.resetTopOperands(Insert);
789 TentativelyCommuting = true;
790 Declined = false;
791 }
792 }
793 }
794
795 /// Stackification for some operand was successful. Reset to the default
796 /// state.
797 void reset() {
798 TentativelyCommuting = false;
799 Declined = false;
800 }
801};
802} // end anonymous namespace
803
804bool WebAssemblyRegStackify::runOnMachineFunction(MachineFunction &MF) {
805 LLVM_DEBUG(dbgs() << "********** Register Stackifying **********\n"
806 "********** Function: "
807 << MF.getName() << '\n');
808
809 bool Changed = false;
812 const auto *TII = MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();
813 const auto *TRI = MF.getSubtarget<WebAssemblySubtarget>().getRegisterInfo();
814 auto &MDT = getAnalysis<MachineDominatorTree>();
815 auto &LIS = getAnalysis<LiveIntervals>();
816
817 // Walk the instructions from the bottom up. Currently we don't look past
818 // block boundaries, and the blocks aren't ordered so the block visitation
819 // order isn't significant, but we may want to change this in the future.
820 for (MachineBasicBlock &MBB : MF) {
821 // Don't use a range-based for loop, because we modify the list as we're
822 // iterating over it and the end iterator may change.
823 for (auto MII = MBB.rbegin(); MII != MBB.rend(); ++MII) {
824 MachineInstr *Insert = &*MII;
825 // Don't nest anything inside an inline asm, because we don't have
826 // constraints for $push inputs.
827 if (Insert->isInlineAsm())
828 continue;
829
830 // Ignore debugging intrinsics.
831 if (Insert->isDebugValue())
832 continue;
833
834 // Iterate through the inputs in reverse order, since we'll be pulling
835 // operands off the stack in LIFO order.
836 CommutingState Commuting;
837 TreeWalkerState TreeWalker(Insert);
838 while (!TreeWalker.done()) {
839 MachineOperand &Use = TreeWalker.pop();
840
841 // We're only interested in explicit virtual register operands.
842 if (!Use.isReg())
843 continue;
844
845 Register Reg = Use.getReg();
846 assert(Use.isUse() && "explicit_uses() should only iterate over uses");
847 assert(!Use.isImplicit() &&
848 "explicit_uses() should only iterate over explicit operands");
849 if (Reg.isPhysical())
850 continue;
851
852 // Identify the definition for this register at this point.
853 MachineInstr *DefI = getVRegDef(Reg, Insert, MRI, LIS);
854 if (!DefI)
855 continue;
856
857 // Don't nest an INLINE_ASM def into anything, because we don't have
858 // constraints for $pop outputs.
859 if (DefI->isInlineAsm())
860 continue;
861
862 // Argument instructions represent live-in registers and not real
863 // instructions.
865 continue;
866
868 assert(Def != nullptr);
869
870 // Decide which strategy to take. Prefer to move a single-use value
871 // over cloning it, and prefer cloning over introducing a tee.
872 // For moving, we require the def to be in the same block as the use;
873 // this makes things simpler (LiveIntervals' handleMove function only
874 // supports intra-block moves) and it's MachineSink's job to catch all
875 // the sinking opportunities anyway.
876 bool SameBlock = DefI->getParent() == &MBB;
877 bool CanMove = SameBlock && isSafeToMove(Def, &Use, Insert, MFI, MRI) &&
878 !TreeWalker.isOnStack(Reg);
879 if (CanMove && hasOneUse(Reg, DefI, MRI, MDT, LIS)) {
880 Insert = moveForSingleUse(Reg, Use, DefI, MBB, Insert, LIS, MFI, MRI);
881
882 // If we are removing the frame base reg completely, remove the debug
883 // info as well.
884 // TODO: Encode this properly as a stackified value.
885 if (MFI.isFrameBaseVirtual() && MFI.getFrameBaseVreg() == Reg)
886 MFI.clearFrameBaseVreg();
887 } else if (shouldRematerialize(*DefI, TII)) {
888 Insert =
889 rematerializeCheapDef(Reg, Use, *DefI, MBB, Insert->getIterator(),
890 LIS, MFI, MRI, TII, TRI);
891 } else if (CanMove && oneUseDominatesOtherUses(Reg, Use, MBB, MRI, MDT,
892 LIS, MFI)) {
893 Insert = moveAndTeeForMultiUse(Reg, Use, DefI, MBB, Insert, LIS, MFI,
894 MRI, TII);
895 } else {
896 // We failed to stackify the operand. If the problem was ordering
897 // constraints, Commuting may be able to help.
898 if (!CanMove && SameBlock)
899 Commuting.maybeCommute(Insert, TreeWalker, TII);
900 // Proceed to the next operand.
901 continue;
902 }
903
904 // Stackifying a multivalue def may unlock in-place stackification of
905 // subsequent defs. TODO: Handle the case where the consecutive uses are
906 // not all in the same instruction.
907 auto *SubsequentDef = Insert->defs().begin();
908 auto *SubsequentUse = &Use;
909 while (SubsequentDef != Insert->defs().end() &&
910 SubsequentUse != Use.getParent()->uses().end()) {
911 if (!SubsequentDef->isReg() || !SubsequentUse->isReg())
912 break;
913 Register DefReg = SubsequentDef->getReg();
914 Register UseReg = SubsequentUse->getReg();
915 // TODO: This single-use restriction could be relaxed by using tees
916 if (DefReg != UseReg || !MRI.hasOneUse(DefReg))
917 break;
918 MFI.stackifyVReg(MRI, DefReg);
919 ++SubsequentDef;
920 ++SubsequentUse;
921 }
922
923 // If the instruction we just stackified is an IMPLICIT_DEF, convert it
924 // to a constant 0 so that the def is explicit, and the push/pop
925 // correspondence is maintained.
926 if (Insert->getOpcode() == TargetOpcode::IMPLICIT_DEF)
927 convertImplicitDefToConstZero(Insert, MRI, TII, MF, LIS);
928
929 // We stackified an operand. Add the defining instruction's operands to
930 // the worklist stack now to continue to build an ever deeper tree.
931 Commuting.reset();
932 TreeWalker.pushOperands(Insert);
933 }
934
935 // If we stackified any operands, skip over the tree to start looking for
936 // the next instruction we can build a tree on.
937 if (Insert != &*MII) {
938 imposeStackOrdering(&*MII);
940 Changed = true;
941 }
942 }
943 }
944
945 // If we used VALUE_STACK anywhere, add it to the live-in sets everywhere so
946 // that it never looks like a use-before-def.
947 if (Changed) {
948 MF.getRegInfo().addLiveIn(WebAssembly::VALUE_STACK);
949 for (MachineBasicBlock &MBB : MF)
950 MBB.addLiveIn(WebAssembly::VALUE_STACK);
951 }
952
953#ifndef NDEBUG
954 // Verify that pushes and pops are performed in LIFO order.
956 for (MachineBasicBlock &MBB : MF) {
957 for (MachineInstr &MI : MBB) {
958 if (MI.isDebugInstr())
959 continue;
960 for (MachineOperand &MO : reverse(MI.explicit_uses())) {
961 if (!MO.isReg())
962 continue;
963 Register Reg = MO.getReg();
964 if (MFI.isVRegStackified(Reg))
965 assert(Stack.pop_back_val() == Reg &&
966 "Register stack pop should be paired with a push");
967 }
968 for (MachineOperand &MO : MI.defs()) {
969 if (!MO.isReg())
970 continue;
971 Register Reg = MO.getReg();
972 if (MFI.isVRegStackified(Reg))
973 Stack.push_back(MO.getReg());
974 }
975 }
976 // TODO: Generalize this code to support keeping values on the stack across
977 // basic block boundaries.
978 assert(Stack.empty() &&
979 "Register stack pushes and pops should be balanced");
980 }
981#endif
982
983 return Changed;
984}
unsigned const MachineRegisterInfo * MRI
MachineBasicBlock & MBB
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
Returns the sub type a function will return at a given Idx Should correspond to the result type of an ExtractValue instruction executed with just that one unsigned Idx
#define LLVM_DEBUG(X)
Definition: Debug.h:101
static Register UseReg(const MachineOperand &MO)
const HexagonInstrInfo * TII
IRTranslator LLVM IR MI
#define F(x, y, z)
Definition: MD5.cpp:55
#define I(x, y, z)
Definition: MD5.cpp:58
unsigned const TargetRegisterInfo * TRI
#define INITIALIZE_PASS(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:38
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
bool IsDead
This file defines the SmallPtrSet class.
This file contains the declaration of the WebAssembly-specific manager for DebugValues associated wit...
This file provides WebAssembly-specific target descriptions.
This file declares WebAssembly-specific per-machine-function information.
static MachineInstr * rematerializeCheapDef(unsigned Reg, MachineOperand &Op, MachineInstr &Def, MachineBasicBlock &MBB, MachineBasicBlock::instr_iterator Insert, LiveIntervals &LIS, WebAssemblyFunctionInfo &MFI, MachineRegisterInfo &MRI, const WebAssemblyInstrInfo *TII, const WebAssemblyRegisterInfo *TRI)
A trivially cloneable instruction; clone it and nest the new copy with the current instruction.
static unsigned getTeeOpcode(const TargetRegisterClass *RC)
Get the appropriate tee opcode for the given register class.
static bool hasOneUse(unsigned Reg, MachineInstr *Def, MachineRegisterInfo &MRI, MachineDominatorTree &MDT, LiveIntervals &LIS)
static MachineInstr * getVRegDef(unsigned Reg, const MachineInstr *Insert, const MachineRegisterInfo &MRI, const LiveIntervals &LIS)
static void convertImplicitDefToConstZero(MachineInstr *MI, MachineRegisterInfo &MRI, const TargetInstrInfo *TII, MachineFunction &MF, LiveIntervals &LIS)
static bool isSafeToMove(const MachineOperand *Def, const MachineOperand *Use, const MachineInstr *Insert, const WebAssemblyFunctionInfo &MFI, const MachineRegisterInfo &MRI)
static MachineInstr * moveForSingleUse(unsigned Reg, MachineOperand &Op, MachineInstr *Def, MachineBasicBlock &MBB, MachineInstr *Insert, LiveIntervals &LIS, WebAssemblyFunctionInfo &MFI, MachineRegisterInfo &MRI)
A single-use def in the same block with no intervening memory or register dependencies; move the def ...
static void imposeStackOrdering(MachineInstr *MI)
static void query(const MachineInstr &MI, bool &Read, bool &Write, bool &Effects, bool &StackPointer)
static void shrinkToUses(LiveInterval &LI, LiveIntervals &LIS)
static bool shouldRematerialize(const MachineInstr &Def, const WebAssemblyInstrInfo *TII)
#define DEBUG_TYPE
static MachineInstr * moveAndTeeForMultiUse(unsigned Reg, MachineOperand &Op, MachineInstr *Def, MachineBasicBlock &MBB, MachineInstr *Insert, LiveIntervals &LIS, WebAssemblyFunctionInfo &MFI, MachineRegisterInfo &MRI, const WebAssemblyInstrInfo *TII)
A multiple-use def in the same block with no intervening memory or register dependencies; move the de...
static bool oneUseDominatesOtherUses(unsigned Reg, const MachineOperand &OneUse, const MachineBasicBlock &MBB, const MachineRegisterInfo &MRI, const MachineDominatorTree &MDT, LiveIntervals &LIS, WebAssemblyFunctionInfo &MFI)
Test whether OneUse, a use of Reg, dominates all of Reg's other uses.
static void queryCallee(const MachineInstr &MI, bool &Read, bool &Write, bool &Effects, bool &StackPointer)
This file declares the WebAssembly-specific subclass of TargetSubtarget.
This file contains the declaration of the WebAssembly-specific utility functions.
This file contains the entry points for global functions defined in the LLVM WebAssembly back-end.
Represent the analysis usage information of a pass.
AnalysisUsage & addPreservedID(const void *ID)
AnalysisUsage & addRequired()
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
void setPreservesCFG()
This function should be called by the pass, iff they do not:
Definition: Pass.cpp:265
This is an important base class in LLVM.
Definition: Constant.h:41
static Constant * getNullValue(Type *Ty)
Constructor to create a '0' constant of arbitrary type.
Definition: Constants.cpp:356
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:308
LLVMContext & getContext() const
getContext - Return a reference to the LLVMContext associated with this function.
Definition: Function.cpp:319
LiveInterval - This class represents the liveness of a register, or stack slot.
Definition: LiveInterval.h:686
MachineInstr * getInstructionFromIndex(SlotIndex index) const
Returns the instruction associated with the given index.
SlotIndex InsertMachineInstrInMaps(MachineInstr &MI)
void handleMove(MachineInstr &MI, bool UpdateFlags=false)
Call this method to notify LiveIntervals that instruction MI has been moved within a basic block.
SlotIndex getInstructionIndex(const MachineInstr &Instr) const
Returns the base index of the given instruction.
void RemoveMachineInstrFromMaps(MachineInstr &MI)
LiveInterval & getInterval(Register Reg)
void removeInterval(Register Reg)
Interval removal.
bool shrinkToUses(LiveInterval *li, SmallVectorImpl< MachineInstr * > *dead=nullptr)
After removing some uses of a register, shrink its live range to just the remaining uses.
void removePhysRegDefAt(MCRegister Reg, SlotIndex Pos)
Remove value numbers and related live segments starting at position Pos that are part of any liverang...
void splitSeparateComponents(LiveInterval &LI, SmallVectorImpl< LiveInterval * > &SplitLIs)
Split separate components in LiveInterval LI into separate intervals.
LiveInterval & createAndComputeVirtRegInterval(Register Reg)
bool liveAt(SlotIndex index) const
Definition: LiveInterval.h:401
LiveQueryResult Query(SlotIndex Idx) const
Query Liveness at Idx.
Definition: LiveInterval.h:541
VNInfo * getVNInfoBefore(SlotIndex Idx) const
getVNInfoBefore - Return the VNInfo that is live up to but not necessarilly including Idx,...
Definition: LiveInterval.h:429
iterator FindSegmentContaining(SlotIndex Idx)
Return an iterator to the segment that contains the specified index, or end() if there is none.
Definition: LiveInterval.h:436
void removeSegment(SlotIndex Start, SlotIndex End, bool RemoveDeadValNo=false)
Remove the specified segment from this range.
VNInfo * getVNInfoAt(SlotIndex Idx) const
getVNInfoAt - Return the VNInfo that is live at Idx, or NULL.
Definition: LiveInterval.h:421
unsigned getNumDefs() const
Return the number of MachineOperands that are register definitions.
Definition: MCInstrDesc.h:247
static MCRegister from(unsigned Val)
Check the provided unsigned value is a valid MCRegister.
Definition: MCRegister.h:67
reverse_iterator rend()
void addLiveIn(MCRegister PhysReg, LaneBitmask LaneMask=LaneBitmask::getAll())
Adds the specified register as a live in.
reverse_iterator rbegin()
void splice(iterator Where, MachineBasicBlock *Other, iterator From)
Take an instruction from MBB 'Other' at the position From, and insert it into this MBB right before '...
MachineInstrBundleIterator< MachineInstr > iterator
MachineBlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate machine basic b...
DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to compute a normal dominat...
bool dominates(const MachineDomTreeNode *A, const MachineDomTreeNode *B) const
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
virtual bool runOnMachineFunction(MachineFunction &MF)=0
runOnMachineFunction - This method must be overloaded to perform the desired machine code transformat...
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
StringRef getName() const
getName - Return the name of the corresponding LLVM function.
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
Function & getFunction()
Return the LLVM function that this machine code represents.
Ty * getInfo()
getInfo - Keep track of various per-function pieces of information for backends that would like to do...
const MachineInstrBuilder & addReg(Register RegNo, unsigned flags=0, unsigned SubReg=0) const
Add a new virtual register operand.
reverse_iterator getReverse() const
Get a reverse iterator to the same node.
Representation of each machine instruction.
Definition: MachineInstr.h:68
unsigned getOpcode() const
Returns the opcode of this MachineInstr.
Definition: MachineInstr.h:516
iterator_range< mop_iterator > explicit_uses()
Definition: MachineInstr.h:696
const MachineBasicBlock * getParent() const
Definition: MachineInstr.h:313
bool isInlineAsm() const
const MCInstrDesc & getDesc() const
Returns the target instruction descriptor of this MachineInstr.
Definition: MachineInstr.h:513
iterator_range< mop_iterator > operands()
Definition: MachineInstr.h:641
iterator_range< mop_iterator > defs()
Returns a range over all explicit operands that are register definitions.
Definition: MachineInstr.h:678
MachineOperand * mop_iterator
iterator/begin/end - Iterate over all operands of a machine instruction.
Definition: MachineInstr.h:632
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:526
MachineOperand * findRegisterDefOperand(Register Reg, bool isDead=false, bool Overlap=false, const TargetRegisterInfo *TRI=nullptr)
Wrapper for findRegisterDefOperandIdx, it returns a pointer to the MachineOperand rather than an inde...
MachineOperand class - Representation of each machine instruction operand.
const GlobalValue * getGlobal() const
static MachineOperand CreateFPImm(const ConstantFP *CFP)
bool isReg() const
isReg - Tests if this is a MO_Register operand.
void setReg(Register Reg)
Change the register this operand corresponds to.
MachineInstr * getParent()
getParent - Return the instruction that this operand belongs to.
static MachineOperand CreateImm(int64_t Val)
bool isGlobal() const
isGlobal - Tests if this is a MO_GlobalAddress operand.
Register getReg() const
getReg - Returns the register number.
static MachineOperand CreateReg(Register Reg, bool isDef, bool isImp=false, bool isKill=false, bool isDead=false, bool isUndef=false, bool isEarlyClobber=false, unsigned SubReg=0, bool isDebug=false, bool isInternalRead=false, bool isRenamable=false)
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
virtual StringRef getPassName() const
getPassName - Return a nice clean name for a pass.
Definition: Pass.cpp:81
Wrapper class representing virtual and physical registers.
Definition: Register.h:19
bool isVirtual() const
Return true if the specified register number is in the virtual register namespace.
Definition: Register.h:91
SlotIndex - An opaque wrapper around machine indexes.
Definition: SlotIndexes.h:82
SlotIndex getDeadSlot() const
Returns the dead def kill slot for the current instruction.
Definition: SlotIndexes.h:264
SlotIndex getRegSlot(bool EC=false) const
Returns the register use/def slot in the current instruction for a normal or early-clobber def.
Definition: SlotIndexes.h:259
SlotIndexes pass.
Definition: SlotIndexes.h:319
bool empty() const
Definition: SmallVector.h:94
void push_back(const T &Elt)
Definition: SmallVector.h:416
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1200
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:50
TargetInstrInfo - Interface to description of machine instruction set.
static const unsigned CommuteAnyOperandIndex
static Type * getDoubleTy(LLVMContext &C)
static Type * getFloatTy(LLVMContext &C)
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43
VNInfo - Value Number Information.
Definition: LiveInterval.h:53
SlotIndex def
The index of the defining instruction.
Definition: LiveInterval.h:61
iterator_range< use_iterator > uses()
Definition: Value.h:376
void clone(MachineInstr *Insert, unsigned NewReg)
This class is derived from MachineFunctionInfo and contains private WebAssembly-specific information ...
void stackifyVReg(MachineRegisterInfo &MRI, unsigned VReg)
Iterator for intrusive lists based on ilist_node.
A range adaptor for a pair of iterators.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
@ Define
Register definition.
bool isArgument(unsigned Opc)
const MachineOperand & getCalleeOp(const MachineInstr &MI)
Returns the operand number of a callee, assuming the argument is a call instruction.
bool isCatch(unsigned Opc)
Reg
All possible values of the reg field in the ModR/M byte.
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
auto drop_begin(T &&RangeOrContainer, size_t N=1)
Return a range covering RangeOrContainer with the first N elements excluded.
Definition: STLExtras.h:397
void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)
MachineInstrBuilder BuildMI(MachineFunction &MF, const MIMetadata &MIMD, const MCInstrDesc &MCID)
Builder interface. Specify how to create the initial instruction itself.
auto reverse(ContainerTy &&C)
Definition: STLExtras.h:495
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
unsigned getUndefRegState(bool B)
char & LiveVariablesID
LiveVariables pass - This pass computes the set of blocks in which each variable is life and sets mac...
FunctionPass * createWebAssemblyRegStackify()