LLVM 19.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/Support/Debug.h"
38#include <iterator>
39using namespace llvm;
40
41#define DEBUG_TYPE "wasm-reg-stackify"
42
43namespace {
44class WebAssemblyRegStackify final : public MachineFunctionPass {
45 StringRef getPassName() const override {
46 return "WebAssembly Register Stackify";
47 }
48
49 void getAnalysisUsage(AnalysisUsage &AU) const override {
50 AU.setPreservesCFG();
59 }
60
61 bool runOnMachineFunction(MachineFunction &MF) override;
62
63public:
64 static char ID; // Pass identification, replacement for typeid
65 WebAssemblyRegStackify() : MachineFunctionPass(ID) {}
66};
67} // end anonymous namespace
68
69char WebAssemblyRegStackify::ID = 0;
70INITIALIZE_PASS(WebAssemblyRegStackify, DEBUG_TYPE,
71 "Reorder instructions to use the WebAssembly value stack",
72 false, false)
73
75 return new WebAssemblyRegStackify();
76}
77
78// Decorate the given instruction with implicit operands that enforce the
79// expression stack ordering constraints for an instruction which is on
80// the expression stack.
82 // Write the opaque VALUE_STACK register.
83 if (!MI->definesRegister(WebAssembly::VALUE_STACK, /*TRI=*/nullptr))
84 MI->addOperand(MachineOperand::CreateReg(WebAssembly::VALUE_STACK,
85 /*isDef=*/true,
86 /*isImp=*/true));
87
88 // Also read the opaque VALUE_STACK register.
89 if (!MI->readsRegister(WebAssembly::VALUE_STACK, /*TRI=*/nullptr))
90 MI->addOperand(MachineOperand::CreateReg(WebAssembly::VALUE_STACK,
91 /*isDef=*/false,
92 /*isImp=*/true));
93}
94
95// Convert an IMPLICIT_DEF instruction into an instruction which defines
96// a constant zero value.
99 const TargetInstrInfo *TII,
100 MachineFunction &MF,
101 LiveIntervals &LIS) {
102 assert(MI->getOpcode() == TargetOpcode::IMPLICIT_DEF);
103
104 const auto *RegClass = MRI.getRegClass(MI->getOperand(0).getReg());
105 if (RegClass == &WebAssembly::I32RegClass) {
106 MI->setDesc(TII->get(WebAssembly::CONST_I32));
107 MI->addOperand(MachineOperand::CreateImm(0));
108 } else if (RegClass == &WebAssembly::I64RegClass) {
109 MI->setDesc(TII->get(WebAssembly::CONST_I64));
110 MI->addOperand(MachineOperand::CreateImm(0));
111 } else if (RegClass == &WebAssembly::F32RegClass) {
112 MI->setDesc(TII->get(WebAssembly::CONST_F32));
113 auto *Val = cast<ConstantFP>(Constant::getNullValue(
115 MI->addOperand(MachineOperand::CreateFPImm(Val));
116 } else if (RegClass == &WebAssembly::F64RegClass) {
117 MI->setDesc(TII->get(WebAssembly::CONST_F64));
118 auto *Val = cast<ConstantFP>(Constant::getNullValue(
120 MI->addOperand(MachineOperand::CreateFPImm(Val));
121 } else if (RegClass == &WebAssembly::V128RegClass) {
122 MI->setDesc(TII->get(WebAssembly::CONST_V128_I64x2));
123 MI->addOperand(MachineOperand::CreateImm(0));
124 MI->addOperand(MachineOperand::CreateImm(0));
125 } else {
126 llvm_unreachable("Unexpected reg class");
127 }
128}
129
130// Determine whether a call to the callee referenced by
131// MI->getOperand(CalleeOpNo) reads memory, writes memory, and/or has side
132// effects.
133static void queryCallee(const MachineInstr &MI, bool &Read, bool &Write,
134 bool &Effects, bool &StackPointer) {
135 // All calls can use the stack pointer.
136 StackPointer = true;
137
139 if (MO.isGlobal()) {
140 const Constant *GV = MO.getGlobal();
141 if (const auto *GA = dyn_cast<GlobalAlias>(GV))
142 if (!GA->isInterposable())
143 GV = GA->getAliasee();
144
145 if (const auto *F = dyn_cast<Function>(GV)) {
146 if (!F->doesNotThrow())
147 Effects = true;
148 if (F->doesNotAccessMemory())
149 return;
150 if (F->onlyReadsMemory()) {
151 Read = true;
152 return;
153 }
154 }
155 }
156
157 // Assume the worst.
158 Write = true;
159 Read = true;
160 Effects = true;
161}
162
163// Determine whether MI reads memory, writes memory, has side effects,
164// and/or uses the stack pointer value.
165static void query(const MachineInstr &MI, bool &Read, bool &Write,
166 bool &Effects, bool &StackPointer) {
167 assert(!MI.isTerminator());
168
169 if (MI.isDebugInstr() || MI.isPosition())
170 return;
171
172 // Check for loads.
173 if (MI.mayLoad() && !MI.isDereferenceableInvariantLoad())
174 Read = true;
175
176 // Check for stores.
177 if (MI.mayStore()) {
178 Write = true;
179 } else if (MI.hasOrderedMemoryRef()) {
180 switch (MI.getOpcode()) {
181 case WebAssembly::DIV_S_I32:
182 case WebAssembly::DIV_S_I64:
183 case WebAssembly::REM_S_I32:
184 case WebAssembly::REM_S_I64:
185 case WebAssembly::DIV_U_I32:
186 case WebAssembly::DIV_U_I64:
187 case WebAssembly::REM_U_I32:
188 case WebAssembly::REM_U_I64:
189 case WebAssembly::I32_TRUNC_S_F32:
190 case WebAssembly::I64_TRUNC_S_F32:
191 case WebAssembly::I32_TRUNC_S_F64:
192 case WebAssembly::I64_TRUNC_S_F64:
193 case WebAssembly::I32_TRUNC_U_F32:
194 case WebAssembly::I64_TRUNC_U_F32:
195 case WebAssembly::I32_TRUNC_U_F64:
196 case WebAssembly::I64_TRUNC_U_F64:
197 // These instruction have hasUnmodeledSideEffects() returning true
198 // because they trap on overflow and invalid so they can't be arbitrarily
199 // moved, however hasOrderedMemoryRef() interprets this plus their lack
200 // of memoperands as having a potential unknown memory reference.
201 break;
202 default:
203 // Record volatile accesses, unless it's a call, as calls are handled
204 // specially below.
205 if (!MI.isCall()) {
206 Write = true;
207 Effects = true;
208 }
209 break;
210 }
211 }
212
213 // Check for side effects.
214 if (MI.hasUnmodeledSideEffects()) {
215 switch (MI.getOpcode()) {
216 case WebAssembly::DIV_S_I32:
217 case WebAssembly::DIV_S_I64:
218 case WebAssembly::REM_S_I32:
219 case WebAssembly::REM_S_I64:
220 case WebAssembly::DIV_U_I32:
221 case WebAssembly::DIV_U_I64:
222 case WebAssembly::REM_U_I32:
223 case WebAssembly::REM_U_I64:
224 case WebAssembly::I32_TRUNC_S_F32:
225 case WebAssembly::I64_TRUNC_S_F32:
226 case WebAssembly::I32_TRUNC_S_F64:
227 case WebAssembly::I64_TRUNC_S_F64:
228 case WebAssembly::I32_TRUNC_U_F32:
229 case WebAssembly::I64_TRUNC_U_F32:
230 case WebAssembly::I32_TRUNC_U_F64:
231 case WebAssembly::I64_TRUNC_U_F64:
232 // These instructions have hasUnmodeledSideEffects() returning true
233 // because they trap on overflow and invalid so they can't be arbitrarily
234 // moved, however in the specific case of register stackifying, it is safe
235 // to move them because overflow and invalid are Undefined Behavior.
236 break;
237 default:
238 Effects = true;
239 break;
240 }
241 }
242
243 // Check for writes to __stack_pointer global.
244 if ((MI.getOpcode() == WebAssembly::GLOBAL_SET_I32 ||
245 MI.getOpcode() == WebAssembly::GLOBAL_SET_I64) &&
246 strcmp(MI.getOperand(0).getSymbolName(), "__stack_pointer") == 0)
247 StackPointer = true;
248
249 // Analyze calls.
250 if (MI.isCall()) {
251 queryCallee(MI, Read, Write, Effects, StackPointer);
252 }
253}
254
255// Test whether Def is safe and profitable to rematerialize.
256static bool shouldRematerialize(const MachineInstr &Def,
257 const WebAssemblyInstrInfo *TII) {
258 return Def.isAsCheapAsAMove() && TII->isTriviallyReMaterializable(Def);
259}
260
261// Identify the definition for this register at this point. This is a
262// generalization of MachineRegisterInfo::getUniqueVRegDef that uses
263// LiveIntervals to handle complex cases.
264static MachineInstr *getVRegDef(unsigned Reg, const MachineInstr *Insert,
266 const LiveIntervals &LIS) {
267 // Most registers are in SSA form here so we try a quick MRI query first.
268 if (MachineInstr *Def = MRI.getUniqueVRegDef(Reg))
269 return Def;
270
271 // MRI doesn't know what the Def is. Try asking LIS.
272 if (const VNInfo *ValNo = LIS.getInterval(Reg).getVNInfoBefore(
273 LIS.getInstructionIndex(*Insert)))
274 return LIS.getInstructionFromIndex(ValNo->def);
275
276 return nullptr;
277}
278
279// Test whether Reg, as defined at Def, has exactly one use. This is a
280// generalization of MachineRegisterInfo::hasOneNonDBGUse that uses
281// LiveIntervals to handle complex cases.
282static bool hasOneNonDBGUse(unsigned Reg, MachineInstr *Def,
284 LiveIntervals &LIS) {
285 // Most registers are in SSA form here so we try a quick MRI query first.
286 if (MRI.hasOneNonDBGUse(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, /*TRI=*/nullptr) &&
375 !Insert->readsRegister(Reg, /*TRI=*/nullptr))
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 if (RC == &WebAssembly::EXNREFRegClass)
508 return WebAssembly::TEE_EXNREF;
509 llvm_unreachable("Unexpected register class");
510}
511
512// Shrink LI to its uses, cleaning up LI.
514 if (LIS.shrinkToUses(&LI)) {
516 LIS.splitSeparateComponents(LI, SplitLIs);
517 }
518}
519
520/// A single-use def in the same block with no intervening memory or register
521/// dependencies; move the def down and nest it with the current instruction.
524 MachineInstr *Insert, LiveIntervals &LIS,
527 LLVM_DEBUG(dbgs() << "Move for single use: "; Def->dump());
528
530 DefDIs.sink(Insert);
531 LIS.handleMove(*Def);
532
533 if (MRI.hasOneDef(Reg) && MRI.hasOneNonDBGUse(Reg)) {
534 // No one else is using this register for anything so we can just stackify
535 // it in place.
536 MFI.stackifyVReg(MRI, Reg);
537 } else {
538 // The register may have unrelated uses or defs; create a new register for
539 // just our one def and use so that we can stackify it.
540 Register NewReg = MRI.createVirtualRegister(MRI.getRegClass(Reg));
541 Op.setReg(NewReg);
542 DefDIs.updateReg(NewReg);
543
544 // Tell LiveIntervals about the new register.
546
547 // Tell LiveIntervals about the changes to the old register.
548 LiveInterval &LI = LIS.getInterval(Reg);
550 LIS.getInstructionIndex(*Op.getParent()).getRegSlot(),
551 /*RemoveDeadValNo=*/true);
552
553 MFI.stackifyVReg(MRI, NewReg);
554
555 LLVM_DEBUG(dbgs() << " - Replaced register: "; Def->dump());
556 }
557
559 return Def;
560}
561
563 for (auto *I = MI->getPrevNode(); I; I = I->getPrevNode())
564 if (!I->isDebugInstr())
565 return I;
566 return nullptr;
567}
568
569/// A trivially cloneable instruction; clone it and nest the new copy with the
570/// current instruction.
572 unsigned Reg, MachineOperand &Op, MachineInstr &Def, MachineBasicBlock &MBB,
576 LLVM_DEBUG(dbgs() << "Rematerializing cheap def: "; Def.dump());
577 LLVM_DEBUG(dbgs() << " - for use in "; Op.getParent()->dump());
578
579 WebAssemblyDebugValueManager DefDIs(&Def);
580
581 Register NewReg = MRI.createVirtualRegister(MRI.getRegClass(Reg));
582 DefDIs.cloneSink(&*Insert, NewReg);
583 Op.setReg(NewReg);
584 MachineInstr *Clone = getPrevNonDebugInst(&*Insert);
585 assert(Clone);
586 LIS.InsertMachineInstrInMaps(*Clone);
588 MFI.stackifyVReg(MRI, NewReg);
589 imposeStackOrdering(Clone);
590
591 LLVM_DEBUG(dbgs() << " - Cloned to "; Clone->dump());
592
593 // Shrink the interval.
594 bool IsDead = MRI.use_empty(Reg);
595 if (!IsDead) {
596 LiveInterval &LI = LIS.getInterval(Reg);
597 shrinkToUses(LI, LIS);
599 }
600
601 // If that was the last use of the original, delete the original.
602 if (IsDead) {
603 LLVM_DEBUG(dbgs() << " - Deleting original\n");
605 LIS.removePhysRegDefAt(MCRegister::from(WebAssembly::ARGUMENTS), Idx);
606 LIS.removeInterval(Reg);
608 DefDIs.removeDef();
609 }
610
611 return Clone;
612}
613
614/// A multiple-use def in the same block with no intervening memory or register
615/// dependencies; move the def down, nest it with the current instruction, and
616/// insert a tee to satisfy the rest of the uses. As an illustration, rewrite
617/// this:
618///
619/// Reg = INST ... // Def
620/// INST ..., Reg, ... // Insert
621/// INST ..., Reg, ...
622/// INST ..., Reg, ...
623///
624/// to this:
625///
626/// DefReg = INST ... // Def (to become the new Insert)
627/// TeeReg, Reg = TEE_... DefReg
628/// INST ..., TeeReg, ... // Insert
629/// INST ..., Reg, ...
630/// INST ..., Reg, ...
631///
632/// with DefReg and TeeReg stackified. This eliminates a local.get from the
633/// resulting code.
635 unsigned Reg, MachineOperand &Op, MachineInstr *Def, MachineBasicBlock &MBB,
638 LLVM_DEBUG(dbgs() << "Move and tee for multi-use:"; Def->dump());
639
640 const auto *RegClass = MRI.getRegClass(Reg);
641 Register TeeReg = MRI.createVirtualRegister(RegClass);
642 Register DefReg = MRI.createVirtualRegister(RegClass);
643
644 // Move Def into place.
646 DefDIs.sink(Insert);
647 LIS.handleMove(*Def);
648
649 // Create the Tee and attach the registers.
650 MachineOperand &DefMO = Def->getOperand(0);
651 MachineInstr *Tee = BuildMI(MBB, Insert, Insert->getDebugLoc(),
652 TII->get(getTeeOpcode(RegClass)), TeeReg)
654 .addReg(DefReg, getUndefRegState(DefMO.isDead()));
655 Op.setReg(TeeReg);
656 DefDIs.updateReg(DefReg);
657 SlotIndex TeeIdx = LIS.InsertMachineInstrInMaps(*Tee).getRegSlot();
658 SlotIndex DefIdx = LIS.getInstructionIndex(*Def).getRegSlot();
659
660 // Tell LiveIntervals we moved the original vreg def from Def to Tee.
661 LiveInterval &LI = LIS.getInterval(Reg);
663 VNInfo *ValNo = LI.getVNInfoAt(DefIdx);
664 I->start = TeeIdx;
665 ValNo->def = TeeIdx;
666 shrinkToUses(LI, LIS);
667
668 // Finish stackifying the new regs.
671 MFI.stackifyVReg(MRI, DefReg);
672 MFI.stackifyVReg(MRI, TeeReg);
675
676 // Even though 'TeeReg, Reg = TEE ...', has two defs, we don't need to clone
677 // DBG_VALUEs for both of them, given that the latter will cancel the former
678 // anyway. Here we only clone DBG_VALUEs for TeeReg, which will be converted
679 // to a local index in ExplicitLocals pass.
680 DefDIs.cloneSink(Insert, TeeReg, /* CloneDef */ false);
681
682 LLVM_DEBUG(dbgs() << " - Replaced register: "; Def->dump());
683 LLVM_DEBUG(dbgs() << " - Tee instruction: "; Tee->dump());
684 return Def;
685}
686
687namespace {
688/// A stack for walking the tree of instructions being built, visiting the
689/// MachineOperands in DFS order.
690class TreeWalkerState {
691 using mop_iterator = MachineInstr::mop_iterator;
692 using mop_reverse_iterator = std::reverse_iterator<mop_iterator>;
695
696public:
697 explicit TreeWalkerState(MachineInstr *Insert) {
698 const iterator_range<mop_iterator> &Range = Insert->explicit_uses();
699 if (!Range.empty())
700 Worklist.push_back(reverse(Range));
701 }
702
703 bool done() const { return Worklist.empty(); }
704
705 MachineOperand &pop() {
706 RangeTy &Range = Worklist.back();
707 MachineOperand &Op = *Range.begin();
709 if (Range.empty())
710 Worklist.pop_back();
711 assert((Worklist.empty() || !Worklist.back().empty()) &&
712 "Empty ranges shouldn't remain in the worklist");
713 return Op;
714 }
715
716 /// Push Instr's operands onto the stack to be visited.
717 void pushOperands(MachineInstr *Instr) {
718 const iterator_range<mop_iterator> &Range(Instr->explicit_uses());
719 if (!Range.empty())
720 Worklist.push_back(reverse(Range));
721 }
722
723 /// Some of Instr's operands are on the top of the stack; remove them and
724 /// re-insert them starting from the beginning (because we've commuted them).
725 void resetTopOperands(MachineInstr *Instr) {
726 assert(hasRemainingOperands(Instr) &&
727 "Reseting operands should only be done when the instruction has "
728 "an operand still on the stack");
729 Worklist.back() = reverse(Instr->explicit_uses());
730 }
731
732 /// Test whether Instr has operands remaining to be visited at the top of
733 /// the stack.
734 bool hasRemainingOperands(const MachineInstr *Instr) const {
735 if (Worklist.empty())
736 return false;
737 const RangeTy &Range = Worklist.back();
738 return !Range.empty() && Range.begin()->getParent() == Instr;
739 }
740
741 /// Test whether the given register is present on the stack, indicating an
742 /// operand in the tree that we haven't visited yet. Moving a definition of
743 /// Reg to a point in the tree after that would change its value.
744 ///
745 /// This is needed as a consequence of using implicit local.gets for
746 /// uses and implicit local.sets for defs.
747 bool isOnStack(unsigned Reg) const {
748 for (const RangeTy &Range : Worklist)
749 for (const MachineOperand &MO : Range)
750 if (MO.isReg() && MO.getReg() == Reg)
751 return true;
752 return false;
753 }
754};
755
756/// State to keep track of whether commuting is in flight or whether it's been
757/// tried for the current instruction and didn't work.
758class CommutingState {
759 /// There are effectively three states: the initial state where we haven't
760 /// started commuting anything and we don't know anything yet, the tentative
761 /// state where we've commuted the operands of the current instruction and are
762 /// revisiting it, and the declined state where we've reverted the operands
763 /// back to their original order and will no longer commute it further.
764 bool TentativelyCommuting = false;
765 bool Declined = false;
766
767 /// During the tentative state, these hold the operand indices of the commuted
768 /// operands.
769 unsigned Operand0, Operand1;
770
771public:
772 /// Stackification for an operand was not successful due to ordering
773 /// constraints. If possible, and if we haven't already tried it and declined
774 /// it, commute Insert's operands and prepare to revisit it.
775 void maybeCommute(MachineInstr *Insert, TreeWalkerState &TreeWalker,
776 const WebAssemblyInstrInfo *TII) {
777 if (TentativelyCommuting) {
778 assert(!Declined &&
779 "Don't decline commuting until you've finished trying it");
780 // Commuting didn't help. Revert it.
781 TII->commuteInstruction(*Insert, /*NewMI=*/false, Operand0, Operand1);
782 TentativelyCommuting = false;
783 Declined = true;
784 } else if (!Declined && TreeWalker.hasRemainingOperands(Insert)) {
787 if (TII->findCommutedOpIndices(*Insert, Operand0, Operand1)) {
788 // Tentatively commute the operands and try again.
789 TII->commuteInstruction(*Insert, /*NewMI=*/false, Operand0, Operand1);
790 TreeWalker.resetTopOperands(Insert);
791 TentativelyCommuting = true;
792 Declined = false;
793 }
794 }
795 }
796
797 /// Stackification for some operand was successful. Reset to the default
798 /// state.
799 void reset() {
800 TentativelyCommuting = false;
801 Declined = false;
802 }
803};
804} // end anonymous namespace
805
806bool WebAssemblyRegStackify::runOnMachineFunction(MachineFunction &MF) {
807 LLVM_DEBUG(dbgs() << "********** Register Stackifying **********\n"
808 "********** Function: "
809 << MF.getName() << '\n');
810
811 bool Changed = false;
814 const auto *TII = MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();
815 const auto *TRI = MF.getSubtarget<WebAssemblySubtarget>().getRegisterInfo();
816 auto &MDT = getAnalysis<MachineDominatorTreeWrapperPass>().getDomTree();
817 auto &LIS = getAnalysis<LiveIntervals>();
818
819 // Walk the instructions from the bottom up. Currently we don't look past
820 // block boundaries, and the blocks aren't ordered so the block visitation
821 // order isn't significant, but we may want to change this in the future.
822 for (MachineBasicBlock &MBB : MF) {
823 // Don't use a range-based for loop, because we modify the list as we're
824 // iterating over it and the end iterator may change.
825 for (auto MII = MBB.rbegin(); MII != MBB.rend(); ++MII) {
826 MachineInstr *Insert = &*MII;
827 // Don't nest anything inside an inline asm, because we don't have
828 // constraints for $push inputs.
829 if (Insert->isInlineAsm())
830 continue;
831
832 // Ignore debugging intrinsics.
833 if (Insert->isDebugValue())
834 continue;
835
836 // Iterate through the inputs in reverse order, since we'll be pulling
837 // operands off the stack in LIFO order.
838 CommutingState Commuting;
839 TreeWalkerState TreeWalker(Insert);
840 while (!TreeWalker.done()) {
841 MachineOperand &Use = TreeWalker.pop();
842
843 // We're only interested in explicit virtual register operands.
844 if (!Use.isReg())
845 continue;
846
847 Register Reg = Use.getReg();
848 assert(Use.isUse() && "explicit_uses() should only iterate over uses");
849 assert(!Use.isImplicit() &&
850 "explicit_uses() should only iterate over explicit operands");
851 if (Reg.isPhysical())
852 continue;
853
854 // Identify the definition for this register at this point.
855 MachineInstr *DefI = getVRegDef(Reg, Insert, MRI, LIS);
856 if (!DefI)
857 continue;
858
859 // Don't nest an INLINE_ASM def into anything, because we don't have
860 // constraints for $pop outputs.
861 if (DefI->isInlineAsm())
862 continue;
863
864 // Argument instructions represent live-in registers and not real
865 // instructions.
867 continue;
868
870 DefI->findRegisterDefOperand(Reg, /*TRI=*/nullptr);
871 assert(Def != nullptr);
872
873 // Decide which strategy to take. Prefer to move a single-use value
874 // over cloning it, and prefer cloning over introducing a tee.
875 // For moving, we require the def to be in the same block as the use;
876 // this makes things simpler (LiveIntervals' handleMove function only
877 // supports intra-block moves) and it's MachineSink's job to catch all
878 // the sinking opportunities anyway.
879 bool SameBlock = DefI->getParent() == &MBB;
880 bool CanMove = SameBlock && isSafeToMove(Def, &Use, Insert, MFI, MRI) &&
881 !TreeWalker.isOnStack(Reg);
882 if (CanMove && hasOneNonDBGUse(Reg, DefI, MRI, MDT, LIS)) {
883 Insert = moveForSingleUse(Reg, Use, DefI, MBB, Insert, LIS, MFI, MRI);
884
885 // If we are removing the frame base reg completely, remove the debug
886 // info as well.
887 // TODO: Encode this properly as a stackified value.
888 if (MFI.isFrameBaseVirtual() && MFI.getFrameBaseVreg() == Reg)
889 MFI.clearFrameBaseVreg();
890 } else if (shouldRematerialize(*DefI, TII)) {
891 Insert =
892 rematerializeCheapDef(Reg, Use, *DefI, MBB, Insert->getIterator(),
893 LIS, MFI, MRI, TII, TRI);
894 } else if (CanMove && oneUseDominatesOtherUses(Reg, Use, MBB, MRI, MDT,
895 LIS, MFI)) {
896 Insert = moveAndTeeForMultiUse(Reg, Use, DefI, MBB, Insert, LIS, MFI,
897 MRI, TII);
898 } else {
899 // We failed to stackify the operand. If the problem was ordering
900 // constraints, Commuting may be able to help.
901 if (!CanMove && SameBlock)
902 Commuting.maybeCommute(Insert, TreeWalker, TII);
903 // Proceed to the next operand.
904 continue;
905 }
906
907 // Stackifying a multivalue def may unlock in-place stackification of
908 // subsequent defs. TODO: Handle the case where the consecutive uses are
909 // not all in the same instruction.
910 auto *SubsequentDef = Insert->defs().begin();
911 auto *SubsequentUse = &Use;
912 while (SubsequentDef != Insert->defs().end() &&
913 SubsequentUse != Use.getParent()->uses().end()) {
914 if (!SubsequentDef->isReg() || !SubsequentUse->isReg())
915 break;
916 Register DefReg = SubsequentDef->getReg();
917 Register UseReg = SubsequentUse->getReg();
918 // TODO: This single-use restriction could be relaxed by using tees
919 if (DefReg != UseReg || !MRI.hasOneNonDBGUse(DefReg))
920 break;
921 MFI.stackifyVReg(MRI, DefReg);
922 ++SubsequentDef;
923 ++SubsequentUse;
924 }
925
926 // If the instruction we just stackified is an IMPLICIT_DEF, convert it
927 // to a constant 0 so that the def is explicit, and the push/pop
928 // correspondence is maintained.
929 if (Insert->getOpcode() == TargetOpcode::IMPLICIT_DEF)
930 convertImplicitDefToConstZero(Insert, MRI, TII, MF, LIS);
931
932 // We stackified an operand. Add the defining instruction's operands to
933 // the worklist stack now to continue to build an ever deeper tree.
934 Commuting.reset();
935 TreeWalker.pushOperands(Insert);
936 }
937
938 // If we stackified any operands, skip over the tree to start looking for
939 // the next instruction we can build a tree on.
940 if (Insert != &*MII) {
941 imposeStackOrdering(&*MII);
943 Changed = true;
944 }
945 }
946 }
947
948 // If we used VALUE_STACK anywhere, add it to the live-in sets everywhere so
949 // that it never looks like a use-before-def.
950 if (Changed) {
951 MF.getRegInfo().addLiveIn(WebAssembly::VALUE_STACK);
952 for (MachineBasicBlock &MBB : MF)
953 MBB.addLiveIn(WebAssembly::VALUE_STACK);
954 }
955
956#ifndef NDEBUG
957 // Verify that pushes and pops are performed in LIFO order.
959 for (MachineBasicBlock &MBB : MF) {
960 for (MachineInstr &MI : MBB) {
961 if (MI.isDebugInstr())
962 continue;
963 for (MachineOperand &MO : reverse(MI.explicit_uses())) {
964 if (!MO.isReg())
965 continue;
966 Register Reg = MO.getReg();
967 if (MFI.isVRegStackified(Reg))
968 assert(Stack.pop_back_val() == Reg &&
969 "Register stack pop should be paired with a push");
970 }
971 for (MachineOperand &MO : MI.defs()) {
972 if (!MO.isReg())
973 continue;
974 Register Reg = MO.getReg();
975 if (MFI.isVRegStackified(Reg))
976 Stack.push_back(MO.getReg());
977 }
978 }
979 // TODO: Generalize this code to support keeping values on the stack across
980 // basic block boundaries.
981 assert(Stack.empty() &&
982 "Register stack pushes and pops should be balanced");
983 }
984#endif
985
986 return Changed;
987}
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:269
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:370
This class represents an Operation in the Expression.
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:311
LLVMContext & getContext() const
getContext - Return a reference to the LLVMContext associated with this function.
Definition: Function.cpp:358
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
MachineBlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate machine basic b...
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:566
const MachineBasicBlock * getParent() const
Definition: MachineInstr.h:343
bool isInlineAsm() const
const MCInstrDesc & getDesc() const
Returns the target instruction descriptor of this MachineInstr.
Definition: MachineInstr.h:563
iterator_range< mop_iterator > operands()
Definition: MachineInstr.h:682
iterator_range< mop_iterator > defs()
Returns a range over all explicit operands that are register definitions.
Definition: MachineInstr.h:719
MachineOperand * mop_iterator
iterator/begin/end - Iterate over all operands of a machine instruction.
Definition: MachineInstr.h:673
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:576
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:68
SlotIndex getDeadSlot() const
Returns the dead def kill slot for the current instruction.
Definition: SlotIndexes.h:245
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:240
SlotIndexes pass.
Definition: SlotIndexes.h:300
bool empty() const
Definition: SmallVector.h:94
void push_back(const T &Elt)
Definition: SmallVector.h:426
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1209
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()