LLVM 20.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_*
23#include "WebAssembly.h"
35#include "llvm/CodeGen/Passes.h"
36#include "llvm/IR/GlobalAlias.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, /*TRI=*/nullptr))
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, /*TRI=*/nullptr))
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::hasOneNonDBGUse that uses
282// LiveIntervals to handle complex cases.
283static bool hasOneNonDBGUse(unsigned Reg, MachineInstr *Def,
285 LiveIntervals &LIS) {
286 // Most registers are in SSA form here so we try a quick MRI query first.
287 if (MRI.hasOneNonDBGUse(Reg))
288 return true;
289
290 bool HasOne = false;
291 const LiveInterval &LI = LIS.getInterval(Reg);
292 const VNInfo *DefVNI =
294 assert(DefVNI);
295 for (auto &I : MRI.use_nodbg_operands(Reg)) {
296 const auto &Result = LI.Query(LIS.getInstructionIndex(*I.getParent()));
297 if (Result.valueIn() == DefVNI) {
298 if (!Result.isKill())
299 return false;
300 if (HasOne)
301 return false;
302 HasOne = true;
303 }
304 }
305 return HasOne;
306}
307
308// Test whether it's safe to move Def to just before Insert.
309// TODO: Compute memory dependencies in a way that doesn't require always
310// walking the block.
311// TODO: Compute memory dependencies in a way that uses AliasAnalysis to be
312// more precise.
313static bool isSafeToMove(const MachineOperand *Def, const MachineOperand *Use,
314 const MachineInstr *Insert,
315 const WebAssemblyFunctionInfo &MFI,
316 const MachineRegisterInfo &MRI) {
317 const MachineInstr *DefI = Def->getParent();
318 const MachineInstr *UseI = Use->getParent();
319 assert(DefI->getParent() == Insert->getParent());
320 assert(UseI->getParent() == Insert->getParent());
321
322 // The first def of a multivalue instruction can be stackified by moving,
323 // since the later defs can always be placed into locals if necessary. Later
324 // defs can only be stackified if all previous defs are already stackified
325 // since ExplicitLocals will not know how to place a def in a local if a
326 // subsequent def is stackified. But only one def can be stackified by moving
327 // the instruction, so it must be the first one.
328 //
329 // TODO: This could be loosened to be the first *live* def, but care would
330 // have to be taken to ensure the drops of the initial dead defs can be
331 // placed. This would require checking that no previous defs are used in the
332 // same instruction as subsequent defs.
333 if (Def != DefI->defs().begin())
334 return false;
335
336 // If any subsequent def is used prior to the current value by the same
337 // instruction in which the current value is used, we cannot
338 // stackify. Stackifying in this case would require that def moving below the
339 // current def in the stack, which cannot be achieved, even with locals.
340 // Also ensure we don't sink the def past any other prior uses.
341 for (const auto &SubsequentDef : drop_begin(DefI->defs())) {
342 auto I = std::next(MachineBasicBlock::const_iterator(DefI));
343 auto E = std::next(MachineBasicBlock::const_iterator(UseI));
344 for (; I != E; ++I) {
345 for (const auto &PriorUse : I->uses()) {
346 if (&PriorUse == Use)
347 break;
348 if (PriorUse.isReg() && SubsequentDef.getReg() == PriorUse.getReg())
349 return false;
350 }
351 }
352 }
353
354 // If moving is a semantic nop, it is always allowed
355 const MachineBasicBlock *MBB = DefI->getParent();
356 auto NextI = std::next(MachineBasicBlock::const_iterator(DefI));
357 for (auto E = MBB->end(); NextI != E && NextI->isDebugInstr(); ++NextI)
358 ;
359 if (NextI == Insert)
360 return true;
361
362 // 'catch' and 'catch_all' should be the first instruction of a BB and cannot
363 // move.
364 if (WebAssembly::isCatch(DefI->getOpcode()))
365 return false;
366
367 // Check for register dependencies.
368 SmallVector<unsigned, 4> MutableRegisters;
369 for (const MachineOperand &MO : DefI->operands()) {
370 if (!MO.isReg() || MO.isUndef())
371 continue;
372 Register Reg = MO.getReg();
373
374 // If the register is dead here and at Insert, ignore it.
375 if (MO.isDead() && Insert->definesRegister(Reg, /*TRI=*/nullptr) &&
376 !Insert->readsRegister(Reg, /*TRI=*/nullptr))
377 continue;
378
379 if (Reg.isPhysical()) {
380 // Ignore ARGUMENTS; it's just used to keep the ARGUMENT_* instructions
381 // from moving down, and we've already checked for that.
382 if (Reg == WebAssembly::ARGUMENTS)
383 continue;
384 // If the physical register is never modified, ignore it.
385 if (!MRI.isPhysRegModified(Reg))
386 continue;
387 // Otherwise, it's a physical register with unknown liveness.
388 return false;
389 }
390
391 // If one of the operands isn't in SSA form, it has different values at
392 // different times, and we need to make sure we don't move our use across
393 // a different def.
394 if (!MO.isDef() && !MRI.hasOneDef(Reg))
395 MutableRegisters.push_back(Reg);
396 }
397
398 bool Read = false, Write = false, Effects = false, StackPointer = false;
399 query(*DefI, Read, Write, Effects, StackPointer);
400
401 // If the instruction does not access memory and has no side effects, it has
402 // no additional dependencies.
403 bool HasMutableRegisters = !MutableRegisters.empty();
404 if (!Read && !Write && !Effects && !StackPointer && !HasMutableRegisters)
405 return true;
406
407 // Scan through the intervening instructions between DefI and Insert.
409 for (--I; I != D; --I) {
410 bool InterveningRead = false;
411 bool InterveningWrite = false;
412 bool InterveningEffects = false;
413 bool InterveningStackPointer = false;
414 query(*I, InterveningRead, InterveningWrite, InterveningEffects,
415 InterveningStackPointer);
416 if (Effects && InterveningEffects)
417 return false;
418 if (Read && InterveningWrite)
419 return false;
420 if (Write && (InterveningRead || InterveningWrite))
421 return false;
422 if (StackPointer && InterveningStackPointer)
423 return false;
424
425 for (unsigned Reg : MutableRegisters)
426 for (const MachineOperand &MO : I->operands())
427 if (MO.isReg() && MO.isDef() && MO.getReg() == Reg)
428 return false;
429 }
430
431 return true;
432}
433
434/// Test whether OneUse, a use of Reg, dominates all of Reg's other uses.
435static bool oneUseDominatesOtherUses(unsigned Reg, const MachineOperand &OneUse,
436 const MachineBasicBlock &MBB,
438 const MachineDominatorTree &MDT,
439 LiveIntervals &LIS,
441 const LiveInterval &LI = LIS.getInterval(Reg);
442
443 const MachineInstr *OneUseInst = OneUse.getParent();
444 VNInfo *OneUseVNI = LI.getVNInfoBefore(LIS.getInstructionIndex(*OneUseInst));
445
446 for (const MachineOperand &Use : MRI.use_nodbg_operands(Reg)) {
447 if (&Use == &OneUse)
448 continue;
449
450 const MachineInstr *UseInst = Use.getParent();
451 VNInfo *UseVNI = LI.getVNInfoBefore(LIS.getInstructionIndex(*UseInst));
452
453 if (UseVNI != OneUseVNI)
454 continue;
455
456 if (UseInst == OneUseInst) {
457 // Another use in the same instruction. We need to ensure that the one
458 // selected use happens "before" it.
459 if (&OneUse > &Use)
460 return false;
461 } else {
462 // Test that the use is dominated by the one selected use.
463 while (!MDT.dominates(OneUseInst, UseInst)) {
464 // Actually, dominating is over-conservative. Test that the use would
465 // happen after the one selected use in the stack evaluation order.
466 //
467 // This is needed as a consequence of using implicit local.gets for
468 // uses and implicit local.sets for defs.
469 if (UseInst->getDesc().getNumDefs() == 0)
470 return false;
471 const MachineOperand &MO = UseInst->getOperand(0);
472 if (!MO.isReg())
473 return false;
474 Register DefReg = MO.getReg();
475 if (!DefReg.isVirtual() || !MFI.isVRegStackified(DefReg))
476 return false;
477 assert(MRI.hasOneNonDBGUse(DefReg));
478 const MachineOperand &NewUse = *MRI.use_nodbg_begin(DefReg);
479 const MachineInstr *NewUseInst = NewUse.getParent();
480 if (NewUseInst == OneUseInst) {
481 if (&OneUse > &NewUse)
482 return false;
483 break;
484 }
485 UseInst = NewUseInst;
486 }
487 }
488 }
489 return true;
490}
491
492/// Get the appropriate tee opcode for the given register class.
493static unsigned getTeeOpcode(const TargetRegisterClass *RC) {
494 if (RC == &WebAssembly::I32RegClass)
495 return WebAssembly::TEE_I32;
496 if (RC == &WebAssembly::I64RegClass)
497 return WebAssembly::TEE_I64;
498 if (RC == &WebAssembly::F32RegClass)
499 return WebAssembly::TEE_F32;
500 if (RC == &WebAssembly::F64RegClass)
501 return WebAssembly::TEE_F64;
502 if (RC == &WebAssembly::V128RegClass)
503 return WebAssembly::TEE_V128;
504 if (RC == &WebAssembly::EXTERNREFRegClass)
505 return WebAssembly::TEE_EXTERNREF;
506 if (RC == &WebAssembly::FUNCREFRegClass)
507 return WebAssembly::TEE_FUNCREF;
508 if (RC == &WebAssembly::EXNREFRegClass)
509 return WebAssembly::TEE_EXNREF;
510 llvm_unreachable("Unexpected register class");
511}
512
513// Shrink LI to its uses, cleaning up LI.
515 if (LIS.shrinkToUses(&LI)) {
517 LIS.splitSeparateComponents(LI, SplitLIs);
518 }
519}
520
521/// A single-use def in the same block with no intervening memory or register
522/// dependencies; move the def down and nest it with the current instruction.
525 MachineInstr *Insert, LiveIntervals &LIS,
528 LLVM_DEBUG(dbgs() << "Move for single use: "; Def->dump());
529
531 DefDIs.sink(Insert);
532 LIS.handleMove(*Def);
533
534 if (MRI.hasOneDef(Reg) && MRI.hasOneNonDBGUse(Reg)) {
535 // No one else is using this register for anything so we can just stackify
536 // it in place.
537 MFI.stackifyVReg(MRI, Reg);
538 } else {
539 // The register may have unrelated uses or defs; create a new register for
540 // just our one def and use so that we can stackify it.
541 Register NewReg = MRI.createVirtualRegister(MRI.getRegClass(Reg));
542 Op.setReg(NewReg);
543 DefDIs.updateReg(NewReg);
544
545 // Tell LiveIntervals about the new register.
547
548 // Tell LiveIntervals about the changes to the old register.
549 LiveInterval &LI = LIS.getInterval(Reg);
551 LIS.getInstructionIndex(*Op.getParent()).getRegSlot(),
552 /*RemoveDeadValNo=*/true);
553
554 MFI.stackifyVReg(MRI, NewReg);
555
556 LLVM_DEBUG(dbgs() << " - Replaced register: "; Def->dump());
557 }
558
560 return Def;
561}
562
564 for (auto *I = MI->getPrevNode(); I; I = I->getPrevNode())
565 if (!I->isDebugInstr())
566 return I;
567 return nullptr;
568}
569
570/// A trivially cloneable instruction; clone it and nest the new copy with the
571/// current instruction.
573 unsigned Reg, MachineOperand &Op, MachineInstr &Def, MachineBasicBlock &MBB,
577 LLVM_DEBUG(dbgs() << "Rematerializing cheap def: "; Def.dump());
578 LLVM_DEBUG(dbgs() << " - for use in "; Op.getParent()->dump());
579
580 WebAssemblyDebugValueManager DefDIs(&Def);
581
582 Register NewReg = MRI.createVirtualRegister(MRI.getRegClass(Reg));
583 DefDIs.cloneSink(&*Insert, NewReg);
584 Op.setReg(NewReg);
585 MachineInstr *Clone = getPrevNonDebugInst(&*Insert);
586 assert(Clone);
587 LIS.InsertMachineInstrInMaps(*Clone);
589 MFI.stackifyVReg(MRI, NewReg);
590 imposeStackOrdering(Clone);
591
592 LLVM_DEBUG(dbgs() << " - Cloned to "; Clone->dump());
593
594 // Shrink the interval.
595 bool IsDead = MRI.use_empty(Reg);
596 if (!IsDead) {
597 LiveInterval &LI = LIS.getInterval(Reg);
598 shrinkToUses(LI, LIS);
600 }
601
602 // If that was the last use of the original, delete the original.
603 if (IsDead) {
604 LLVM_DEBUG(dbgs() << " - Deleting original\n");
606 LIS.removePhysRegDefAt(MCRegister::from(WebAssembly::ARGUMENTS), Idx);
607 LIS.removeInterval(Reg);
609 DefDIs.removeDef();
610 }
611
612 return Clone;
613}
614
615/// A multiple-use def in the same block with no intervening memory or register
616/// dependencies; move the def down, nest it with the current instruction, and
617/// insert a tee to satisfy the rest of the uses. As an illustration, rewrite
618/// this:
619///
620/// Reg = INST ... // Def
621/// INST ..., Reg, ... // Insert
622/// INST ..., Reg, ...
623/// INST ..., Reg, ...
624///
625/// to this:
626///
627/// DefReg = INST ... // Def (to become the new Insert)
628/// TeeReg, Reg = TEE_... DefReg
629/// INST ..., TeeReg, ... // Insert
630/// INST ..., Reg, ...
631/// INST ..., Reg, ...
632///
633/// with DefReg and TeeReg stackified. This eliminates a local.get from the
634/// resulting code.
636 unsigned Reg, MachineOperand &Op, MachineInstr *Def, MachineBasicBlock &MBB,
639 LLVM_DEBUG(dbgs() << "Move and tee for multi-use:"; Def->dump());
640
641 const auto *RegClass = MRI.getRegClass(Reg);
642 Register TeeReg = MRI.createVirtualRegister(RegClass);
643 Register DefReg = MRI.createVirtualRegister(RegClass);
644
645 // Move Def into place.
647 DefDIs.sink(Insert);
648 LIS.handleMove(*Def);
649
650 // Create the Tee and attach the registers.
651 MachineOperand &DefMO = Def->getOperand(0);
652 MachineInstr *Tee = BuildMI(MBB, Insert, Insert->getDebugLoc(),
653 TII->get(getTeeOpcode(RegClass)), TeeReg)
655 .addReg(DefReg, getUndefRegState(DefMO.isDead()));
656 Op.setReg(TeeReg);
657 DefDIs.updateReg(DefReg);
658 SlotIndex TeeIdx = LIS.InsertMachineInstrInMaps(*Tee).getRegSlot();
659 SlotIndex DefIdx = LIS.getInstructionIndex(*Def).getRegSlot();
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 // Even though 'TeeReg, Reg = TEE ...', has two defs, we don't need to clone
678 // DBG_VALUEs for both of them, given that the latter will cancel the former
679 // anyway. Here we only clone DBG_VALUEs for TeeReg, which will be converted
680 // to a local index in ExplicitLocals pass.
681 DefDIs.cloneSink(Insert, TeeReg, /* CloneDef */ false);
682
683 LLVM_DEBUG(dbgs() << " - Replaced register: "; Def->dump());
684 LLVM_DEBUG(dbgs() << " - Tee instruction: "; Tee->dump());
685 return Def;
686}
687
688namespace {
689/// A stack for walking the tree of instructions being built, visiting the
690/// MachineOperands in DFS order.
691class TreeWalkerState {
692 using mop_iterator = MachineInstr::mop_iterator;
693 using mop_reverse_iterator = std::reverse_iterator<mop_iterator>;
696
697public:
698 explicit TreeWalkerState(MachineInstr *Insert) {
699 const iterator_range<mop_iterator> &Range = Insert->explicit_uses();
700 if (!Range.empty())
701 Worklist.push_back(reverse(Range));
702 }
703
704 bool done() const { return Worklist.empty(); }
705
706 MachineOperand &pop() {
707 RangeTy &Range = Worklist.back();
708 MachineOperand &Op = *Range.begin();
710 if (Range.empty())
711 Worklist.pop_back();
712 assert((Worklist.empty() || !Worklist.back().empty()) &&
713 "Empty ranges shouldn't remain in the worklist");
714 return Op;
715 }
716
717 /// Push Instr's operands onto the stack to be visited.
718 void pushOperands(MachineInstr *Instr) {
719 const iterator_range<mop_iterator> &Range(Instr->explicit_uses());
720 if (!Range.empty())
721 Worklist.push_back(reverse(Range));
722 }
723
724 /// Some of Instr's operands are on the top of the stack; remove them and
725 /// re-insert them starting from the beginning (because we've commuted them).
726 void resetTopOperands(MachineInstr *Instr) {
727 assert(hasRemainingOperands(Instr) &&
728 "Reseting operands should only be done when the instruction has "
729 "an operand still on the stack");
730 Worklist.back() = reverse(Instr->explicit_uses());
731 }
732
733 /// Test whether Instr has operands remaining to be visited at the top of
734 /// the stack.
735 bool hasRemainingOperands(const MachineInstr *Instr) const {
736 if (Worklist.empty())
737 return false;
738 const RangeTy &Range = Worklist.back();
739 return !Range.empty() && Range.begin()->getParent() == Instr;
740 }
741
742 /// Test whether the given register is present on the stack, indicating an
743 /// operand in the tree that we haven't visited yet. Moving a definition of
744 /// Reg to a point in the tree after that would change its value.
745 ///
746 /// This is needed as a consequence of using implicit local.gets for
747 /// uses and implicit local.sets for defs.
748 bool isOnStack(unsigned Reg) const {
749 for (const RangeTy &Range : Worklist)
750 for (const MachineOperand &MO : Range)
751 if (MO.isReg() && MO.getReg() == Reg)
752 return true;
753 return false;
754 }
755};
756
757/// State to keep track of whether commuting is in flight or whether it's been
758/// tried for the current instruction and didn't work.
759class CommutingState {
760 /// There are effectively three states: the initial state where we haven't
761 /// started commuting anything and we don't know anything yet, the tentative
762 /// state where we've commuted the operands of the current instruction and are
763 /// revisiting it, and the declined state where we've reverted the operands
764 /// back to their original order and will no longer commute it further.
765 bool TentativelyCommuting = false;
766 bool Declined = false;
767
768 /// During the tentative state, these hold the operand indices of the commuted
769 /// operands.
770 unsigned Operand0, Operand1;
771
772public:
773 /// Stackification for an operand was not successful due to ordering
774 /// constraints. If possible, and if we haven't already tried it and declined
775 /// it, commute Insert's operands and prepare to revisit it.
776 void maybeCommute(MachineInstr *Insert, TreeWalkerState &TreeWalker,
777 const WebAssemblyInstrInfo *TII) {
778 if (TentativelyCommuting) {
779 assert(!Declined &&
780 "Don't decline commuting until you've finished trying it");
781 // Commuting didn't help. Revert it.
782 TII->commuteInstruction(*Insert, /*NewMI=*/false, Operand0, Operand1);
783 TentativelyCommuting = false;
784 Declined = true;
785 } else if (!Declined && TreeWalker.hasRemainingOperands(Insert)) {
788 if (TII->findCommutedOpIndices(*Insert, Operand0, Operand1)) {
789 // Tentatively commute the operands and try again.
790 TII->commuteInstruction(*Insert, /*NewMI=*/false, Operand0, Operand1);
791 TreeWalker.resetTopOperands(Insert);
792 TentativelyCommuting = true;
793 Declined = false;
794 }
795 }
796 }
797
798 /// Stackification for some operand was successful. Reset to the default
799 /// state.
800 void reset() {
801 TentativelyCommuting = false;
802 Declined = false;
803 }
804};
805} // end anonymous namespace
806
807bool WebAssemblyRegStackify::runOnMachineFunction(MachineFunction &MF) {
808 LLVM_DEBUG(dbgs() << "********** Register Stackifying **********\n"
809 "********** Function: "
810 << MF.getName() << '\n');
811
812 bool Changed = false;
815 const auto *TII = MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();
816 const auto *TRI = MF.getSubtarget<WebAssemblySubtarget>().getRegisterInfo();
817 auto &MDT = getAnalysis<MachineDominatorTreeWrapperPass>().getDomTree();
818 auto &LIS = getAnalysis<LiveIntervalsWrapperPass>().getLIS();
819
820 // Walk the instructions from the bottom up. Currently we don't look past
821 // block boundaries, and the blocks aren't ordered so the block visitation
822 // order isn't significant, but we may want to change this in the future.
823 for (MachineBasicBlock &MBB : MF) {
824 // Don't use a range-based for loop, because we modify the list as we're
825 // iterating over it and the end iterator may change.
826 for (auto MII = MBB.rbegin(); MII != MBB.rend(); ++MII) {
827 MachineInstr *Insert = &*MII;
828 // Don't nest anything inside an inline asm, because we don't have
829 // constraints for $push inputs.
830 if (Insert->isInlineAsm())
831 continue;
832
833 // Ignore debugging intrinsics.
834 if (Insert->isDebugValue())
835 continue;
836
837 // Iterate through the inputs in reverse order, since we'll be pulling
838 // operands off the stack in LIFO order.
839 CommutingState Commuting;
840 TreeWalkerState TreeWalker(Insert);
841 while (!TreeWalker.done()) {
842 MachineOperand &Use = TreeWalker.pop();
843
844 // We're only interested in explicit virtual register operands.
845 if (!Use.isReg())
846 continue;
847
848 Register Reg = Use.getReg();
849 assert(Use.isUse() && "explicit_uses() should only iterate over uses");
850 assert(!Use.isImplicit() &&
851 "explicit_uses() should only iterate over explicit operands");
852 if (Reg.isPhysical())
853 continue;
854
855 // Identify the definition for this register at this point.
856 MachineInstr *DefI = getVRegDef(Reg, Insert, MRI, LIS);
857 if (!DefI)
858 continue;
859
860 // Don't nest an INLINE_ASM def into anything, because we don't have
861 // constraints for $pop outputs.
862 if (DefI->isInlineAsm())
863 continue;
864
865 // Argument instructions represent live-in registers and not real
866 // instructions.
868 continue;
869
871 DefI->findRegisterDefOperand(Reg, /*TRI=*/nullptr);
872 assert(Def != nullptr);
873
874 // Decide which strategy to take. Prefer to move a single-use value
875 // over cloning it, and prefer cloning over introducing a tee.
876 // For moving, we require the def to be in the same block as the use;
877 // this makes things simpler (LiveIntervals' handleMove function only
878 // supports intra-block moves) and it's MachineSink's job to catch all
879 // the sinking opportunities anyway.
880 bool SameBlock = DefI->getParent() == &MBB;
881 bool CanMove = SameBlock && isSafeToMove(Def, &Use, Insert, MFI, MRI) &&
882 !TreeWalker.isOnStack(Reg);
883 if (CanMove && hasOneNonDBGUse(Reg, DefI, MRI, MDT, LIS)) {
884 Insert = moveForSingleUse(Reg, Use, DefI, MBB, Insert, LIS, MFI, MRI);
885
886 // If we are removing the frame base reg completely, remove the debug
887 // info as well.
888 // TODO: Encode this properly as a stackified value.
889 if (MFI.isFrameBaseVirtual() && MFI.getFrameBaseVreg() == Reg)
890 MFI.clearFrameBaseVreg();
891 } else if (shouldRematerialize(*DefI, TII)) {
892 Insert =
893 rematerializeCheapDef(Reg, Use, *DefI, MBB, Insert->getIterator(),
894 LIS, MFI, MRI, TII, TRI);
895 } else if (CanMove && oneUseDominatesOtherUses(Reg, Use, MBB, MRI, MDT,
896 LIS, MFI)) {
897 Insert = moveAndTeeForMultiUse(Reg, Use, DefI, MBB, Insert, LIS, MFI,
898 MRI, TII);
899 } else {
900 // We failed to stackify the operand. If the problem was ordering
901 // constraints, Commuting may be able to help.
902 if (!CanMove && SameBlock)
903 Commuting.maybeCommute(Insert, TreeWalker, TII);
904 // Proceed to the next operand.
905 continue;
906 }
907
908 // Stackifying a multivalue def may unlock in-place stackification of
909 // subsequent defs. TODO: Handle the case where the consecutive uses are
910 // not all in the same instruction.
911 auto *SubsequentDef = Insert->defs().begin();
912 auto *SubsequentUse = &Use;
913 while (SubsequentDef != Insert->defs().end() &&
914 SubsequentUse != Use.getParent()->uses().end()) {
915 if (!SubsequentDef->isReg() || !SubsequentUse->isReg())
916 break;
917 Register DefReg = SubsequentDef->getReg();
918 Register UseReg = SubsequentUse->getReg();
919 // TODO: This single-use restriction could be relaxed by using tees
920 if (DefReg != UseReg || !MRI.hasOneNonDBGUse(DefReg))
921 break;
922 MFI.stackifyVReg(MRI, DefReg);
923 ++SubsequentDef;
924 ++SubsequentUse;
925 }
926
927 // If the instruction we just stackified is an IMPLICIT_DEF, convert it
928 // to a constant 0 so that the def is explicit, and the push/pop
929 // correspondence is maintained.
930 if (Insert->getOpcode() == TargetOpcode::IMPLICIT_DEF)
931 convertImplicitDefToConstZero(Insert, MRI, TII, MF, LIS);
932
933 // We stackified an operand. Add the defining instruction's operands to
934 // the worklist stack now to continue to build an ever deeper tree.
935 Commuting.reset();
936 TreeWalker.pushOperands(Insert);
937 }
938
939 // If we stackified any operands, skip over the tree to start looking for
940 // the next instruction we can build a tree on.
941 if (Insert != &*MII) {
942 imposeStackOrdering(&*MII);
944 Changed = true;
945 }
946 }
947 }
948
949 // If we used VALUE_STACK anywhere, add it to the live-in sets everywhere so
950 // that it never looks like a use-before-def.
951 if (Changed) {
952 MF.getRegInfo().addLiveIn(WebAssembly::VALUE_STACK);
953 for (MachineBasicBlock &MBB : MF)
954 MBB.addLiveIn(WebAssembly::VALUE_STACK);
955 }
956
957#ifndef NDEBUG
958 // Verify that pushes and pops are performed in LIFO order.
960 for (MachineBasicBlock &MBB : MF) {
961 for (MachineInstr &MI : MBB) {
962 if (MI.isDebugInstr())
963 continue;
964 for (MachineOperand &MO : reverse(MI.explicit_uses())) {
965 if (!MO.isReg())
966 continue;
967 Register Reg = MO.getReg();
968 if (MFI.isVRegStackified(Reg))
969 assert(Stack.pop_back_val() == Reg &&
970 "Register stack pop should be paired with a push");
971 }
972 for (MachineOperand &MO : MI.defs()) {
973 if (!MO.isReg())
974 continue;
975 Register Reg = MO.getReg();
976 if (MFI.isVRegStackified(Reg))
977 Stack.push_back(MO.getReg());
978 }
979 }
980 // TODO: Generalize this code to support keeping values on the stack across
981 // basic block boundaries.
982 assert(Stack.empty() &&
983 "Register stack pushes and pops should be balanced");
984 }
985#endif
986
987 return Changed;
988}
unsigned const MachineRegisterInfo * MRI
MachineBasicBlock & MBB
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
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
ConstantRange Range(APInt(BitWidth, Low), APInt(BitWidth, High))
#define INITIALIZE_PASS(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:38
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
bool IsDead
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 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 hasOneNonDBGUse(unsigned Reg, MachineInstr *Def, MachineRegisterInfo &MRI, MachineDominatorTree &MDT, 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 MachineInstr * getPrevNonDebugInst(MachineInstr *MI)
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:256
This is an important base class in LLVM.
Definition: Constant.h:42
static Constant * getNullValue(Type *Ty)
Constructor to create a '0' constant of arbitrary type.
Definition: Constants.cpp:370
This class represents an Operation in the Expression.
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:310
LLVMContext & getContext() const
getContext - Return a reference to the LLVMContext associated with this function.
Definition: Function.cpp:380
LiveInterval - This class represents the liveness of a register, or stack slot.
Definition: LiveInterval.h:687
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:542
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 interval from this live 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:248
static MCRegister from(unsigned Val)
Check the provided unsigned value is a valid MCRegister.
Definition: MCRegister.h:74
reverse_iterator rend()
Instructions::iterator instr_iterator
void addLiveIn(MCRegister PhysReg, LaneBitmask LaneMask=LaneBitmask::getAll())
Adds the specified register as a live in.
reverse_iterator rbegin()
MachineInstrBundleIterator< MachineInstr > iterator
Analysis pass which computes a MachineDominatorTree.
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:69
unsigned getOpcode() const
Returns the opcode of this MachineInstr.
Definition: MachineInstr.h:569
const MachineBasicBlock * getParent() const
Definition: MachineInstr.h:346
bool isInlineAsm() const
const MCInstrDesc & getDesc() const
Returns the target instruction descriptor of this MachineInstr.
Definition: MachineInstr.h:566
iterator_range< mop_iterator > operands()
Definition: MachineInstr.h:685
iterator_range< mop_iterator > defs()
Returns a range over all explicit operands that are register definitions.
Definition: MachineInstr.h:722
MachineOperand * mop_iterator
iterator/begin/end - Iterate over all operands of a machine instruction.
Definition: MachineInstr.h:676
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:579
MachineOperand * findRegisterDefOperand(Register Reg, const TargetRegisterInfo *TRI, bool isDead=false, bool Overlap=false)
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.
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
constexpr 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:65
SlotIndex getDeadSlot() const
Returns the dead def kill slot for the current instruction.
Definition: SlotIndexes.h:242
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:237
bool empty() const
Definition: SmallVector.h:95
void push_back(const T &Elt)
Definition: SmallVector.h:427
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1210
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 cloneSink(MachineInstr *Insert, Register NewReg=Register(), bool CloneDef=true) const
This class is derived from MachineFunctionInfo and contains private WebAssembly-specific information ...
void stackifyVReg(MachineRegisterInfo &MRI, unsigned VReg)
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.
NodeAddr< InstrNode * > Instr
Definition: RDFGraph.h:389
NodeAddr< DefNode * > Def
Definition: RDFGraph.h:384
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:329
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:419
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
unsigned getUndefRegState(bool B)
DWARFExpression::Operation Op
char & LiveVariablesID
LiveVariables pass - This pass computes the set of blocks in which each variable is life and sets mac...
FunctionPass * createWebAssemblyRegStackify()