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))
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))
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) &&
375 !Insert->readsRegister(Reg))
376 continue;
377
378 if (Reg.isPhysical()) {
379 // Ignore ARGUMENTS; it's just used to keep the ARGUMENT_* instructions
380 // from moving down, and we've already checked for that.
381 if (Reg == WebAssembly::ARGUMENTS)
382 continue;
383 // If the physical register is never modified, ignore it.
384 if (!MRI.isPhysRegModified(Reg))
385 continue;
386 // Otherwise, it's a physical register with unknown liveness.
387 return false;
388 }
389
390 // If one of the operands isn't in SSA form, it has different values at
391 // different times, and we need to make sure we don't move our use across
392 // a different def.
393 if (!MO.isDef() && !MRI.hasOneDef(Reg))
394 MutableRegisters.push_back(Reg);
395 }
396
397 bool Read = false, Write = false, Effects = false, StackPointer = false;
398 query(*DefI, Read, Write, Effects, StackPointer);
399
400 // If the instruction does not access memory and has no side effects, it has
401 // no additional dependencies.
402 bool HasMutableRegisters = !MutableRegisters.empty();
403 if (!Read && !Write && !Effects && !StackPointer && !HasMutableRegisters)
404 return true;
405
406 // Scan through the intervening instructions between DefI and Insert.
408 for (--I; I != D; --I) {
409 bool InterveningRead = false;
410 bool InterveningWrite = false;
411 bool InterveningEffects = false;
412 bool InterveningStackPointer = false;
413 query(*I, InterveningRead, InterveningWrite, InterveningEffects,
414 InterveningStackPointer);
415 if (Effects && InterveningEffects)
416 return false;
417 if (Read && InterveningWrite)
418 return false;
419 if (Write && (InterveningRead || InterveningWrite))
420 return false;
421 if (StackPointer && InterveningStackPointer)
422 return false;
423
424 for (unsigned Reg : MutableRegisters)
425 for (const MachineOperand &MO : I->operands())
426 if (MO.isReg() && MO.isDef() && MO.getReg() == Reg)
427 return false;
428 }
429
430 return true;
431}
432
433/// Test whether OneUse, a use of Reg, dominates all of Reg's other uses.
434static bool oneUseDominatesOtherUses(unsigned Reg, const MachineOperand &OneUse,
435 const MachineBasicBlock &MBB,
437 const MachineDominatorTree &MDT,
438 LiveIntervals &LIS,
440 const LiveInterval &LI = LIS.getInterval(Reg);
441
442 const MachineInstr *OneUseInst = OneUse.getParent();
443 VNInfo *OneUseVNI = LI.getVNInfoBefore(LIS.getInstructionIndex(*OneUseInst));
444
445 for (const MachineOperand &Use : MRI.use_nodbg_operands(Reg)) {
446 if (&Use == &OneUse)
447 continue;
448
449 const MachineInstr *UseInst = Use.getParent();
450 VNInfo *UseVNI = LI.getVNInfoBefore(LIS.getInstructionIndex(*UseInst));
451
452 if (UseVNI != OneUseVNI)
453 continue;
454
455 if (UseInst == OneUseInst) {
456 // Another use in the same instruction. We need to ensure that the one
457 // selected use happens "before" it.
458 if (&OneUse > &Use)
459 return false;
460 } else {
461 // Test that the use is dominated by the one selected use.
462 while (!MDT.dominates(OneUseInst, UseInst)) {
463 // Actually, dominating is over-conservative. Test that the use would
464 // happen after the one selected use in the stack evaluation order.
465 //
466 // This is needed as a consequence of using implicit local.gets for
467 // uses and implicit local.sets for defs.
468 if (UseInst->getDesc().getNumDefs() == 0)
469 return false;
470 const MachineOperand &MO = UseInst->getOperand(0);
471 if (!MO.isReg())
472 return false;
473 Register DefReg = MO.getReg();
474 if (!DefReg.isVirtual() || !MFI.isVRegStackified(DefReg))
475 return false;
476 assert(MRI.hasOneNonDBGUse(DefReg));
477 const MachineOperand &NewUse = *MRI.use_nodbg_begin(DefReg);
478 const MachineInstr *NewUseInst = NewUse.getParent();
479 if (NewUseInst == OneUseInst) {
480 if (&OneUse > &NewUse)
481 return false;
482 break;
483 }
484 UseInst = NewUseInst;
485 }
486 }
487 }
488 return true;
489}
490
491/// Get the appropriate tee opcode for the given register class.
492static unsigned getTeeOpcode(const TargetRegisterClass *RC) {
493 if (RC == &WebAssembly::I32RegClass)
494 return WebAssembly::TEE_I32;
495 if (RC == &WebAssembly::I64RegClass)
496 return WebAssembly::TEE_I64;
497 if (RC == &WebAssembly::F32RegClass)
498 return WebAssembly::TEE_F32;
499 if (RC == &WebAssembly::F64RegClass)
500 return WebAssembly::TEE_F64;
501 if (RC == &WebAssembly::V128RegClass)
502 return WebAssembly::TEE_V128;
503 if (RC == &WebAssembly::EXTERNREFRegClass)
504 return WebAssembly::TEE_EXTERNREF;
505 if (RC == &WebAssembly::FUNCREFRegClass)
506 return WebAssembly::TEE_FUNCREF;
507 llvm_unreachable("Unexpected register class");
508}
509
510// Shrink LI to its uses, cleaning up LI.
512 if (LIS.shrinkToUses(&LI)) {
514 LIS.splitSeparateComponents(LI, SplitLIs);
515 }
516}
517
518/// A single-use def in the same block with no intervening memory or register
519/// dependencies; move the def down and nest it with the current instruction.
522 MachineInstr *Insert, LiveIntervals &LIS,
525 LLVM_DEBUG(dbgs() << "Move for single use: "; Def->dump());
526
528 DefDIs.sink(Insert);
529 LIS.handleMove(*Def);
530
531 if (MRI.hasOneDef(Reg) && MRI.hasOneNonDBGUse(Reg)) {
532 // No one else is using this register for anything so we can just stackify
533 // it in place.
534 MFI.stackifyVReg(MRI, Reg);
535 } else {
536 // The register may have unrelated uses or defs; create a new register for
537 // just our one def and use so that we can stackify it.
538 Register NewReg = MRI.createVirtualRegister(MRI.getRegClass(Reg));
539 Op.setReg(NewReg);
540 DefDIs.updateReg(NewReg);
541
542 // Tell LiveIntervals about the new register.
544
545 // Tell LiveIntervals about the changes to the old register.
546 LiveInterval &LI = LIS.getInterval(Reg);
548 LIS.getInstructionIndex(*Op.getParent()).getRegSlot(),
549 /*RemoveDeadValNo=*/true);
550
551 MFI.stackifyVReg(MRI, NewReg);
552
553 LLVM_DEBUG(dbgs() << " - Replaced register: "; Def->dump());
554 }
555
557 return Def;
558}
559
561 for (auto *I = MI->getPrevNode(); I; I = I->getPrevNode())
562 if (!I->isDebugInstr())
563 return I;
564 return nullptr;
565}
566
567/// A trivially cloneable instruction; clone it and nest the new copy with the
568/// current instruction.
570 unsigned Reg, MachineOperand &Op, MachineInstr &Def, MachineBasicBlock &MBB,
574 LLVM_DEBUG(dbgs() << "Rematerializing cheap def: "; Def.dump());
575 LLVM_DEBUG(dbgs() << " - for use in "; Op.getParent()->dump());
576
577 WebAssemblyDebugValueManager DefDIs(&Def);
578
579 Register NewReg = MRI.createVirtualRegister(MRI.getRegClass(Reg));
580 DefDIs.cloneSink(&*Insert, NewReg);
581 Op.setReg(NewReg);
582 MachineInstr *Clone = getPrevNonDebugInst(&*Insert);
583 assert(Clone);
584 LIS.InsertMachineInstrInMaps(*Clone);
586 MFI.stackifyVReg(MRI, NewReg);
587 imposeStackOrdering(Clone);
588
589 LLVM_DEBUG(dbgs() << " - Cloned to "; Clone->dump());
590
591 // Shrink the interval.
592 bool IsDead = MRI.use_empty(Reg);
593 if (!IsDead) {
594 LiveInterval &LI = LIS.getInterval(Reg);
595 shrinkToUses(LI, LIS);
597 }
598
599 // If that was the last use of the original, delete the original.
600 if (IsDead) {
601 LLVM_DEBUG(dbgs() << " - Deleting original\n");
603 LIS.removePhysRegDefAt(MCRegister::from(WebAssembly::ARGUMENTS), Idx);
604 LIS.removeInterval(Reg);
606 DefDIs.removeDef();
607 }
608
609 return Clone;
610}
611
612/// A multiple-use def in the same block with no intervening memory or register
613/// dependencies; move the def down, nest it with the current instruction, and
614/// insert a tee to satisfy the rest of the uses. As an illustration, rewrite
615/// this:
616///
617/// Reg = INST ... // Def
618/// INST ..., Reg, ... // Insert
619/// INST ..., Reg, ...
620/// INST ..., Reg, ...
621///
622/// to this:
623///
624/// DefReg = INST ... // Def (to become the new Insert)
625/// TeeReg, Reg = TEE_... DefReg
626/// INST ..., TeeReg, ... // Insert
627/// INST ..., Reg, ...
628/// INST ..., Reg, ...
629///
630/// with DefReg and TeeReg stackified. This eliminates a local.get from the
631/// resulting code.
633 unsigned Reg, MachineOperand &Op, MachineInstr *Def, MachineBasicBlock &MBB,
636 LLVM_DEBUG(dbgs() << "Move and tee for multi-use:"; Def->dump());
637
638 const auto *RegClass = MRI.getRegClass(Reg);
639 Register TeeReg = MRI.createVirtualRegister(RegClass);
640 Register DefReg = MRI.createVirtualRegister(RegClass);
641
642 // Move Def into place.
644 DefDIs.sink(Insert);
645 LIS.handleMove(*Def);
646
647 // Create the Tee and attach the registers.
648 MachineOperand &DefMO = Def->getOperand(0);
649 MachineInstr *Tee = BuildMI(MBB, Insert, Insert->getDebugLoc(),
650 TII->get(getTeeOpcode(RegClass)), TeeReg)
652 .addReg(DefReg, getUndefRegState(DefMO.isDead()));
653 Op.setReg(TeeReg);
654 DefDIs.updateReg(DefReg);
655 SlotIndex TeeIdx = LIS.InsertMachineInstrInMaps(*Tee).getRegSlot();
656 SlotIndex DefIdx = LIS.getInstructionIndex(*Def).getRegSlot();
657
658 // Tell LiveIntervals we moved the original vreg def from Def to Tee.
659 LiveInterval &LI = LIS.getInterval(Reg);
661 VNInfo *ValNo = LI.getVNInfoAt(DefIdx);
662 I->start = TeeIdx;
663 ValNo->def = TeeIdx;
664 shrinkToUses(LI, LIS);
665
666 // Finish stackifying the new regs.
669 MFI.stackifyVReg(MRI, DefReg);
670 MFI.stackifyVReg(MRI, TeeReg);
673
674 // Even though 'TeeReg, Reg = TEE ...', has two defs, we don't need to clone
675 // DBG_VALUEs for both of them, given that the latter will cancel the former
676 // anyway. Here we only clone DBG_VALUEs for TeeReg, which will be converted
677 // to a local index in ExplicitLocals pass.
678 DefDIs.cloneSink(Insert, TeeReg, /* CloneDef */ false);
679
680 LLVM_DEBUG(dbgs() << " - Replaced register: "; Def->dump());
681 LLVM_DEBUG(dbgs() << " - Tee instruction: "; Tee->dump());
682 return Def;
683}
684
685namespace {
686/// A stack for walking the tree of instructions being built, visiting the
687/// MachineOperands in DFS order.
688class TreeWalkerState {
689 using mop_iterator = MachineInstr::mop_iterator;
690 using mop_reverse_iterator = std::reverse_iterator<mop_iterator>;
693
694public:
695 explicit TreeWalkerState(MachineInstr *Insert) {
696 const iterator_range<mop_iterator> &Range = Insert->explicit_uses();
697 if (!Range.empty())
698 Worklist.push_back(reverse(Range));
699 }
700
701 bool done() const { return Worklist.empty(); }
702
703 MachineOperand &pop() {
704 RangeTy &Range = Worklist.back();
705 MachineOperand &Op = *Range.begin();
706 Range = drop_begin(Range);
707 if (Range.empty())
708 Worklist.pop_back();
709 assert((Worklist.empty() || !Worklist.back().empty()) &&
710 "Empty ranges shouldn't remain in the worklist");
711 return Op;
712 }
713
714 /// Push Instr's operands onto the stack to be visited.
715 void pushOperands(MachineInstr *Instr) {
716 const iterator_range<mop_iterator> &Range(Instr->explicit_uses());
717 if (!Range.empty())
718 Worklist.push_back(reverse(Range));
719 }
720
721 /// Some of Instr's operands are on the top of the stack; remove them and
722 /// re-insert them starting from the beginning (because we've commuted them).
723 void resetTopOperands(MachineInstr *Instr) {
724 assert(hasRemainingOperands(Instr) &&
725 "Reseting operands should only be done when the instruction has "
726 "an operand still on the stack");
727 Worklist.back() = reverse(Instr->explicit_uses());
728 }
729
730 /// Test whether Instr has operands remaining to be visited at the top of
731 /// the stack.
732 bool hasRemainingOperands(const MachineInstr *Instr) const {
733 if (Worklist.empty())
734 return false;
735 const RangeTy &Range = Worklist.back();
736 return !Range.empty() && Range.begin()->getParent() == Instr;
737 }
738
739 /// Test whether the given register is present on the stack, indicating an
740 /// operand in the tree that we haven't visited yet. Moving a definition of
741 /// Reg to a point in the tree after that would change its value.
742 ///
743 /// This is needed as a consequence of using implicit local.gets for
744 /// uses and implicit local.sets for defs.
745 bool isOnStack(unsigned Reg) const {
746 for (const RangeTy &Range : Worklist)
747 for (const MachineOperand &MO : Range)
748 if (MO.isReg() && MO.getReg() == Reg)
749 return true;
750 return false;
751 }
752};
753
754/// State to keep track of whether commuting is in flight or whether it's been
755/// tried for the current instruction and didn't work.
756class CommutingState {
757 /// There are effectively three states: the initial state where we haven't
758 /// started commuting anything and we don't know anything yet, the tentative
759 /// state where we've commuted the operands of the current instruction and are
760 /// revisiting it, and the declined state where we've reverted the operands
761 /// back to their original order and will no longer commute it further.
762 bool TentativelyCommuting = false;
763 bool Declined = false;
764
765 /// During the tentative state, these hold the operand indices of the commuted
766 /// operands.
767 unsigned Operand0, Operand1;
768
769public:
770 /// Stackification for an operand was not successful due to ordering
771 /// constraints. If possible, and if we haven't already tried it and declined
772 /// it, commute Insert's operands and prepare to revisit it.
773 void maybeCommute(MachineInstr *Insert, TreeWalkerState &TreeWalker,
774 const WebAssemblyInstrInfo *TII) {
775 if (TentativelyCommuting) {
776 assert(!Declined &&
777 "Don't decline commuting until you've finished trying it");
778 // Commuting didn't help. Revert it.
779 TII->commuteInstruction(*Insert, /*NewMI=*/false, Operand0, Operand1);
780 TentativelyCommuting = false;
781 Declined = true;
782 } else if (!Declined && TreeWalker.hasRemainingOperands(Insert)) {
785 if (TII->findCommutedOpIndices(*Insert, Operand0, Operand1)) {
786 // Tentatively commute the operands and try again.
787 TII->commuteInstruction(*Insert, /*NewMI=*/false, Operand0, Operand1);
788 TreeWalker.resetTopOperands(Insert);
789 TentativelyCommuting = true;
790 Declined = false;
791 }
792 }
793 }
794
795 /// Stackification for some operand was successful. Reset to the default
796 /// state.
797 void reset() {
798 TentativelyCommuting = false;
799 Declined = false;
800 }
801};
802} // end anonymous namespace
803
804bool WebAssemblyRegStackify::runOnMachineFunction(MachineFunction &MF) {
805 LLVM_DEBUG(dbgs() << "********** Register Stackifying **********\n"
806 "********** Function: "
807 << MF.getName() << '\n');
808
809 bool Changed = false;
812 const auto *TII = MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();
813 const auto *TRI = MF.getSubtarget<WebAssemblySubtarget>().getRegisterInfo();
814 auto &MDT = getAnalysis<MachineDominatorTree>();
815 auto &LIS = getAnalysis<LiveIntervals>();
816
817 // Walk the instructions from the bottom up. Currently we don't look past
818 // block boundaries, and the blocks aren't ordered so the block visitation
819 // order isn't significant, but we may want to change this in the future.
820 for (MachineBasicBlock &MBB : MF) {
821 // Don't use a range-based for loop, because we modify the list as we're
822 // iterating over it and the end iterator may change.
823 for (auto MII = MBB.rbegin(); MII != MBB.rend(); ++MII) {
824 MachineInstr *Insert = &*MII;
825 // Don't nest anything inside an inline asm, because we don't have
826 // constraints for $push inputs.
827 if (Insert->isInlineAsm())
828 continue;
829
830 // Ignore debugging intrinsics.
831 if (Insert->isDebugValue())
832 continue;
833
834 // Iterate through the inputs in reverse order, since we'll be pulling
835 // operands off the stack in LIFO order.
836 CommutingState Commuting;
837 TreeWalkerState TreeWalker(Insert);
838 while (!TreeWalker.done()) {
839 MachineOperand &Use = TreeWalker.pop();
840
841 // We're only interested in explicit virtual register operands.
842 if (!Use.isReg())
843 continue;
844
845 Register Reg = Use.getReg();
846 assert(Use.isUse() && "explicit_uses() should only iterate over uses");
847 assert(!Use.isImplicit() &&
848 "explicit_uses() should only iterate over explicit operands");
849 if (Reg.isPhysical())
850 continue;
851
852 // Identify the definition for this register at this point.
853 MachineInstr *DefI = getVRegDef(Reg, Insert, MRI, LIS);
854 if (!DefI)
855 continue;
856
857 // Don't nest an INLINE_ASM def into anything, because we don't have
858 // constraints for $pop outputs.
859 if (DefI->isInlineAsm())
860 continue;
861
862 // Argument instructions represent live-in registers and not real
863 // instructions.
865 continue;
866
868 assert(Def != nullptr);
869
870 // Decide which strategy to take. Prefer to move a single-use value
871 // over cloning it, and prefer cloning over introducing a tee.
872 // For moving, we require the def to be in the same block as the use;
873 // this makes things simpler (LiveIntervals' handleMove function only
874 // supports intra-block moves) and it's MachineSink's job to catch all
875 // the sinking opportunities anyway.
876 bool SameBlock = DefI->getParent() == &MBB;
877 bool CanMove = SameBlock && isSafeToMove(Def, &Use, Insert, MFI, MRI) &&
878 !TreeWalker.isOnStack(Reg);
879 if (CanMove && hasOneNonDBGUse(Reg, DefI, MRI, MDT, LIS)) {
880 Insert = moveForSingleUse(Reg, Use, DefI, MBB, Insert, LIS, MFI, MRI);
881
882 // If we are removing the frame base reg completely, remove the debug
883 // info as well.
884 // TODO: Encode this properly as a stackified value.
885 if (MFI.isFrameBaseVirtual() && MFI.getFrameBaseVreg() == Reg)
886 MFI.clearFrameBaseVreg();
887 } else if (shouldRematerialize(*DefI, TII)) {
888 Insert =
889 rematerializeCheapDef(Reg, Use, *DefI, MBB, Insert->getIterator(),
890 LIS, MFI, MRI, TII, TRI);
891 } else if (CanMove && oneUseDominatesOtherUses(Reg, Use, MBB, MRI, MDT,
892 LIS, MFI)) {
893 Insert = moveAndTeeForMultiUse(Reg, Use, DefI, MBB, Insert, LIS, MFI,
894 MRI, TII);
895 } else {
896 // We failed to stackify the operand. If the problem was ordering
897 // constraints, Commuting may be able to help.
898 if (!CanMove && SameBlock)
899 Commuting.maybeCommute(Insert, TreeWalker, TII);
900 // Proceed to the next operand.
901 continue;
902 }
903
904 // Stackifying a multivalue def may unlock in-place stackification of
905 // subsequent defs. TODO: Handle the case where the consecutive uses are
906 // not all in the same instruction.
907 auto *SubsequentDef = Insert->defs().begin();
908 auto *SubsequentUse = &Use;
909 while (SubsequentDef != Insert->defs().end() &&
910 SubsequentUse != Use.getParent()->uses().end()) {
911 if (!SubsequentDef->isReg() || !SubsequentUse->isReg())
912 break;
913 Register DefReg = SubsequentDef->getReg();
914 Register UseReg = SubsequentUse->getReg();
915 // TODO: This single-use restriction could be relaxed by using tees
916 if (DefReg != UseReg || !MRI.hasOneNonDBGUse(DefReg))
917 break;
918 MFI.stackifyVReg(MRI, DefReg);
919 ++SubsequentDef;
920 ++SubsequentUse;
921 }
922
923 // If the instruction we just stackified is an IMPLICIT_DEF, convert it
924 // to a constant 0 so that the def is explicit, and the push/pop
925 // correspondence is maintained.
926 if (Insert->getOpcode() == TargetOpcode::IMPLICIT_DEF)
927 convertImplicitDefToConstZero(Insert, MRI, TII, MF, LIS);
928
929 // We stackified an operand. Add the defining instruction's operands to
930 // the worklist stack now to continue to build an ever deeper tree.
931 Commuting.reset();
932 TreeWalker.pushOperands(Insert);
933 }
934
935 // If we stackified any operands, skip over the tree to start looking for
936 // the next instruction we can build a tree on.
937 if (Insert != &*MII) {
938 imposeStackOrdering(&*MII);
940 Changed = true;
941 }
942 }
943 }
944
945 // If we used VALUE_STACK anywhere, add it to the live-in sets everywhere so
946 // that it never looks like a use-before-def.
947 if (Changed) {
948 MF.getRegInfo().addLiveIn(WebAssembly::VALUE_STACK);
949 for (MachineBasicBlock &MBB : MF)
950 MBB.addLiveIn(WebAssembly::VALUE_STACK);
951 }
952
953#ifndef NDEBUG
954 // Verify that pushes and pops are performed in LIFO order.
956 for (MachineBasicBlock &MBB : MF) {
957 for (MachineInstr &MI : MBB) {
958 if (MI.isDebugInstr())
959 continue;
960 for (MachineOperand &MO : reverse(MI.explicit_uses())) {
961 if (!MO.isReg())
962 continue;
963 Register Reg = MO.getReg();
964 if (MFI.isVRegStackified(Reg))
965 assert(Stack.pop_back_val() == Reg &&
966 "Register stack pop should be paired with a push");
967 }
968 for (MachineOperand &MO : MI.defs()) {
969 if (!MO.isReg())
970 continue;
971 Register Reg = MO.getReg();
972 if (MFI.isVRegStackified(Reg))
973 Stack.push_back(MO.getReg());
974 }
975 }
976 // TODO: Generalize this code to support keeping values on the stack across
977 // basic block boundaries.
978 assert(Stack.empty() &&
979 "Register stack pushes and pops should be balanced");
980 }
981#endif
982
983 return Changed;
984}
unsigned const MachineRegisterInfo * MRI
MachineBasicBlock & MBB
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
Returns the sub type a function will return at a given Idx Should correspond to the result type of an ExtractValue instruction executed with just that one unsigned Idx
#define LLVM_DEBUG(X)
Definition: Debug.h:101
static Register UseReg(const MachineOperand &MO)
const HexagonInstrInfo * TII
IRTranslator LLVM IR MI
#define F(x, y, z)
Definition: MD5.cpp:55
#define I(x, y, z)
Definition: MD5.cpp:58
unsigned const TargetRegisterInfo * TRI
#define INITIALIZE_PASS(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:38
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
bool IsDead
This file 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:342
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...
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:544
const MachineBasicBlock * getParent() const
Definition: MachineInstr.h:327
bool isInlineAsm() const
const MCInstrDesc & getDesc() const
Returns the target instruction descriptor of this MachineInstr.
Definition: MachineInstr.h:541
iterator_range< mop_iterator > operands()
Definition: MachineInstr.h:660
iterator_range< mop_iterator > defs()
Returns a range over all explicit operands that are register definitions.
Definition: MachineInstr.h:697
MachineOperand * mop_iterator
iterator/begin/end - Iterate over all operands of a machine instruction.
Definition: MachineInstr.h:651
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:554
MachineOperand * findRegisterDefOperand(Register Reg, bool isDead=false, bool Overlap=false, const TargetRegisterInfo *TRI=nullptr)
Wrapper for findRegisterDefOperandIdx, it returns a pointer to the MachineOperand rather than an inde...
MachineOperand class - Representation of each machine instruction operand.
const GlobalValue * getGlobal() const
static MachineOperand CreateFPImm(const ConstantFP *CFP)
bool isReg() const
isReg - Tests if this is a MO_Register operand.
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:428
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()