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" |
24 | #include "WebAssemblyDebugValueManager.h" |
25 | #include "WebAssemblyMachineFunctionInfo.h" |
26 | #include "WebAssemblySubtarget.h" |
27 | #include "WebAssemblyUtilities.h" |
28 | #include "llvm/Analysis/AliasAnalysis.h" |
29 | #include "llvm/CodeGen/LiveIntervals.h" |
30 | #include "llvm/CodeGen/MachineBlockFrequencyInfo.h" |
31 | #include "llvm/CodeGen/MachineDominators.h" |
32 | #include "llvm/CodeGen/MachineInstrBuilder.h" |
33 | #include "llvm/CodeGen/MachineModuleInfoImpls.h" |
34 | #include "llvm/CodeGen/MachineRegisterInfo.h" |
35 | #include "llvm/CodeGen/Passes.h" |
36 | #include "llvm/Support/Debug.h" |
37 | #include "llvm/Support/raw_ostream.h" |
38 | #include <iterator> |
39 | using namespace llvm; |
40 | |
41 | #define DEBUG_TYPE "wasm-reg-stackify" |
42 | |
43 | namespace { |
44 | class 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(); |
51 | AU.addRequired<MachineDominatorTree>(); |
52 | AU.addRequired<LiveIntervals>(); |
53 | AU.addPreserved<MachineBlockFrequencyInfo>(); |
54 | AU.addPreserved<SlotIndexes>(); |
55 | AU.addPreserved<LiveIntervals>(); |
56 | AU.addPreservedID(ID&: LiveVariablesID); |
57 | AU.addPreserved<MachineDominatorTree>(); |
58 | MachineFunctionPass::getAnalysisUsage(AU); |
59 | } |
60 | |
61 | bool runOnMachineFunction(MachineFunction &MF) override; |
62 | |
63 | public: |
64 | static char ID; // Pass identification, replacement for typeid |
65 | WebAssemblyRegStackify() : MachineFunctionPass(ID) {} |
66 | }; |
67 | } // end anonymous namespace |
68 | |
69 | char WebAssemblyRegStackify::ID = 0; |
70 | INITIALIZE_PASS(WebAssemblyRegStackify, DEBUG_TYPE, |
71 | "Reorder instructions to use the WebAssembly value stack" , |
72 | false, false) |
73 | |
74 | FunctionPass *llvm::createWebAssemblyRegStackify() { |
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. |
81 | static void imposeStackOrdering(MachineInstr *MI) { |
82 | // Write the opaque VALUE_STACK register. |
83 | if (!MI->definesRegister(WebAssembly::Reg: VALUE_STACK, /*TRI=*/nullptr)) |
84 | MI->addOperand(MachineOperand::CreateReg(WebAssembly::Reg: VALUE_STACK, |
85 | /*isDef=*/true, |
86 | /*isImp=*/true)); |
87 | |
88 | // Also read the opaque VALUE_STACK register. |
89 | if (!MI->readsRegister(WebAssembly::Reg: VALUE_STACK, /*TRI=*/nullptr)) |
90 | MI->addOperand(MachineOperand::CreateReg(WebAssembly::Reg: 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. |
97 | static void convertImplicitDefToConstZero(MachineInstr *MI, |
98 | MachineRegisterInfo &MRI, |
99 | const TargetInstrInfo *TII, |
100 | MachineFunction &MF, |
101 | LiveIntervals &LIS) { |
102 | assert(MI->getOpcode() == TargetOpcode::IMPLICIT_DEF); |
103 | |
104 | const auto *RegClass = MRI.getRegClass(Reg: MI->getOperand(i: 0).getReg()); |
105 | if (RegClass == &WebAssembly::I32RegClass) { |
106 | MI->setDesc(TII->get(WebAssembly::Opcode: CONST_I32)); |
107 | MI->addOperand(Op: MachineOperand::CreateImm(Val: 0)); |
108 | } else if (RegClass == &WebAssembly::I64RegClass) { |
109 | MI->setDesc(TII->get(WebAssembly::Opcode: CONST_I64)); |
110 | MI->addOperand(Op: MachineOperand::CreateImm(Val: 0)); |
111 | } else if (RegClass == &WebAssembly::F32RegClass) { |
112 | MI->setDesc(TII->get(WebAssembly::Opcode: CONST_F32)); |
113 | auto *Val = cast<ConstantFP>(Val: Constant::getNullValue( |
114 | Ty: Type::getFloatTy(C&: MF.getFunction().getContext()))); |
115 | MI->addOperand(Op: MachineOperand::CreateFPImm(CFP: Val)); |
116 | } else if (RegClass == &WebAssembly::F64RegClass) { |
117 | MI->setDesc(TII->get(WebAssembly::Opcode: CONST_F64)); |
118 | auto *Val = cast<ConstantFP>(Val: Constant::getNullValue( |
119 | Ty: Type::getDoubleTy(C&: MF.getFunction().getContext()))); |
120 | MI->addOperand(Op: MachineOperand::CreateFPImm(CFP: Val)); |
121 | } else if (RegClass == &WebAssembly::V128RegClass) { |
122 | MI->setDesc(TII->get(WebAssembly::Opcode: CONST_V128_I64x2)); |
123 | MI->addOperand(Op: MachineOperand::CreateImm(Val: 0)); |
124 | MI->addOperand(Op: MachineOperand::CreateImm(Val: 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. |
133 | static 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 | |
138 | const MachineOperand &MO = WebAssembly::getCalleeOp(MI); |
139 | if (MO.isGlobal()) { |
140 | const Constant *GV = MO.getGlobal(); |
141 | if (const auto *GA = dyn_cast<GlobalAlias>(Val: GV)) |
142 | if (!GA->isInterposable()) |
143 | GV = GA->getAliasee(); |
144 | |
145 | if (const auto *F = dyn_cast<Function>(Val: 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. |
165 | static 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. |
256 | static 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. |
264 | static MachineInstr *getVRegDef(unsigned Reg, const MachineInstr *Insert, |
265 | const MachineRegisterInfo &MRI, |
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 | Idx: LIS.getInstructionIndex(Instr: *Insert))) |
274 | return LIS.getInstructionFromIndex(index: 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. |
282 | static bool hasOneNonDBGUse(unsigned Reg, MachineInstr *Def, |
283 | MachineRegisterInfo &MRI, MachineDominatorTree &MDT, |
284 | LiveIntervals &LIS) { |
285 | // Most registers are in SSA form here so we try a quick MRI query first. |
286 | if (MRI.hasOneNonDBGUse(RegNo: Reg)) |
287 | return true; |
288 | |
289 | bool HasOne = false; |
290 | const LiveInterval &LI = LIS.getInterval(Reg); |
291 | const VNInfo *DefVNI = |
292 | LI.getVNInfoAt(Idx: LIS.getInstructionIndex(Instr: *Def).getRegSlot()); |
293 | assert(DefVNI); |
294 | for (auto &I : MRI.use_nodbg_operands(Reg)) { |
295 | const auto &Result = LI.Query(Idx: LIS.getInstructionIndex(Instr: *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. |
312 | static 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(RangeOrContainer: DefI->defs())) { |
341 | auto I = std::next(x: MachineBasicBlock::const_iterator(DefI)); |
342 | auto E = std::next(x: 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(x: 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(Opc: 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(PhysReg: 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(RegNo: Reg)) |
394 | MutableRegisters.push_back(Elt: Reg); |
395 | } |
396 | |
397 | bool Read = false, Write = false, Effects = false, StackPointer = false; |
398 | query(MI: *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. |
407 | MachineBasicBlock::const_iterator D(DefI), I(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(MI: *I, Read&: InterveningRead, Write&: InterveningWrite, Effects&: InterveningEffects, |
414 | StackPointer&: 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. |
434 | static bool oneUseDominatesOtherUses(unsigned Reg, const MachineOperand &OneUse, |
435 | const MachineBasicBlock &MBB, |
436 | const MachineRegisterInfo &MRI, |
437 | const MachineDominatorTree &MDT, |
438 | LiveIntervals &LIS, |
439 | WebAssemblyFunctionInfo &MFI) { |
440 | const LiveInterval &LI = LIS.getInterval(Reg); |
441 | |
442 | const MachineInstr *OneUseInst = OneUse.getParent(); |
443 | VNInfo *OneUseVNI = LI.getVNInfoBefore(Idx: LIS.getInstructionIndex(Instr: *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(Idx: LIS.getInstructionIndex(Instr: *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(A: OneUseInst, B: 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(i: 0); |
471 | if (!MO.isReg()) |
472 | return false; |
473 | Register DefReg = MO.getReg(); |
474 | if (!DefReg.isVirtual() || !MFI.isVRegStackified(VReg: DefReg)) |
475 | return false; |
476 | assert(MRI.hasOneNonDBGUse(DefReg)); |
477 | const MachineOperand &NewUse = *MRI.use_nodbg_begin(RegNo: 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. |
492 | static 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. |
511 | static void shrinkToUses(LiveInterval &LI, LiveIntervals &LIS) { |
512 | if (LIS.shrinkToUses(li: &LI)) { |
513 | SmallVector<LiveInterval *, 4> SplitLIs; |
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. |
520 | static MachineInstr *moveForSingleUse(unsigned Reg, MachineOperand &Op, |
521 | MachineInstr *Def, MachineBasicBlock &MBB, |
522 | MachineInstr *Insert, LiveIntervals &LIS, |
523 | WebAssemblyFunctionInfo &MFI, |
524 | MachineRegisterInfo &MRI) { |
525 | LLVM_DEBUG(dbgs() << "Move for single use: " ; Def->dump()); |
526 | |
527 | WebAssemblyDebugValueManager DefDIs(Def); |
528 | DefDIs.sink(Insert); |
529 | LIS.handleMove(MI&: *Def); |
530 | |
531 | if (MRI.hasOneDef(RegNo: Reg) && MRI.hasOneNonDBGUse(RegNo: Reg)) { |
532 | // No one else is using this register for anything so we can just stackify |
533 | // it in place. |
534 | MFI.stackifyVReg(MRI, VReg: 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(RegClass: MRI.getRegClass(Reg)); |
539 | Op.setReg(NewReg); |
540 | DefDIs.updateReg(Reg: NewReg); |
541 | |
542 | // Tell LiveIntervals about the new register. |
543 | LIS.createAndComputeVirtRegInterval(Reg: NewReg); |
544 | |
545 | // Tell LiveIntervals about the changes to the old register. |
546 | LiveInterval &LI = LIS.getInterval(Reg); |
547 | LI.removeSegment(Start: LIS.getInstructionIndex(Instr: *Def).getRegSlot(), |
548 | End: LIS.getInstructionIndex(Instr: *Op.getParent()).getRegSlot(), |
549 | /*RemoveDeadValNo=*/true); |
550 | |
551 | MFI.stackifyVReg(MRI, VReg: NewReg); |
552 | |
553 | LLVM_DEBUG(dbgs() << " - Replaced register: " ; Def->dump()); |
554 | } |
555 | |
556 | imposeStackOrdering(MI: Def); |
557 | return Def; |
558 | } |
559 | |
560 | static MachineInstr *getPrevNonDebugInst(MachineInstr *MI) { |
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. |
569 | static MachineInstr *rematerializeCheapDef( |
570 | unsigned Reg, MachineOperand &Op, MachineInstr &Def, MachineBasicBlock &MBB, |
571 | MachineBasicBlock::instr_iterator Insert, LiveIntervals &LIS, |
572 | WebAssemblyFunctionInfo &MFI, MachineRegisterInfo &MRI, |
573 | const WebAssemblyInstrInfo *TII, const WebAssemblyRegisterInfo *TRI) { |
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(RegClass: MRI.getRegClass(Reg)); |
580 | DefDIs.cloneSink(Insert: &*Insert, NewReg); |
581 | Op.setReg(NewReg); |
582 | MachineInstr *Clone = getPrevNonDebugInst(MI: &*Insert); |
583 | assert(Clone); |
584 | LIS.InsertMachineInstrInMaps(MI&: *Clone); |
585 | LIS.createAndComputeVirtRegInterval(Reg: NewReg); |
586 | MFI.stackifyVReg(MRI, VReg: NewReg); |
587 | imposeStackOrdering(MI: Clone); |
588 | |
589 | LLVM_DEBUG(dbgs() << " - Cloned to " ; Clone->dump()); |
590 | |
591 | // Shrink the interval. |
592 | bool IsDead = MRI.use_empty(RegNo: Reg); |
593 | if (!IsDead) { |
594 | LiveInterval &LI = LIS.getInterval(Reg); |
595 | shrinkToUses(LI, LIS); |
596 | IsDead = !LI.liveAt(index: LIS.getInstructionIndex(Instr: Def).getDeadSlot()); |
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" ); |
602 | SlotIndex Idx = LIS.getInstructionIndex(Instr: Def).getRegSlot(); |
603 | LIS.removePhysRegDefAt(MCRegister::from(WebAssembly::ARGUMENTS), Idx); |
604 | LIS.removeInterval(Reg); |
605 | LIS.RemoveMachineInstrFromMaps(MI&: Def); |
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. |
632 | static MachineInstr *moveAndTeeForMultiUse( |
633 | unsigned Reg, MachineOperand &Op, MachineInstr *Def, MachineBasicBlock &MBB, |
634 | MachineInstr *Insert, LiveIntervals &LIS, WebAssemblyFunctionInfo &MFI, |
635 | MachineRegisterInfo &MRI, const WebAssemblyInstrInfo *TII) { |
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. |
643 | WebAssemblyDebugValueManager DefDIs(Def); |
644 | DefDIs.sink(Insert); |
645 | LIS.handleMove(MI&: *Def); |
646 | |
647 | // Create the Tee and attach the registers. |
648 | MachineOperand &DefMO = Def->getOperand(i: 0); |
649 | MachineInstr *Tee = BuildMI(MBB, Insert, Insert->getDebugLoc(), |
650 | TII->get(getTeeOpcode(RC: RegClass)), TeeReg) |
651 | .addReg(Reg, RegState::Define) |
652 | .addReg(DefReg, getUndefRegState(B: DefMO.isDead())); |
653 | Op.setReg(TeeReg); |
654 | DefDIs.updateReg(Reg: DefReg); |
655 | SlotIndex TeeIdx = LIS.InsertMachineInstrInMaps(MI&: *Tee).getRegSlot(); |
656 | SlotIndex DefIdx = LIS.getInstructionIndex(Instr: *Def).getRegSlot(); |
657 | |
658 | // Tell LiveIntervals we moved the original vreg def from Def to Tee. |
659 | LiveInterval &LI = LIS.getInterval(Reg); |
660 | LiveInterval::iterator I = LI.FindSegmentContaining(Idx: DefIdx); |
661 | VNInfo *ValNo = LI.getVNInfoAt(Idx: DefIdx); |
662 | I->start = TeeIdx; |
663 | ValNo->def = TeeIdx; |
664 | shrinkToUses(LI, LIS); |
665 | |
666 | // Finish stackifying the new regs. |
667 | LIS.createAndComputeVirtRegInterval(Reg: TeeReg); |
668 | LIS.createAndComputeVirtRegInterval(Reg: DefReg); |
669 | MFI.stackifyVReg(MRI, VReg: DefReg); |
670 | MFI.stackifyVReg(MRI, VReg: TeeReg); |
671 | imposeStackOrdering(MI: Def); |
672 | imposeStackOrdering(MI: Tee); |
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, NewReg: 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 | |
685 | namespace { |
686 | /// A stack for walking the tree of instructions being built, visiting the |
687 | /// MachineOperands in DFS order. |
688 | class TreeWalkerState { |
689 | using mop_iterator = MachineInstr::mop_iterator; |
690 | using mop_reverse_iterator = std::reverse_iterator<mop_iterator>; |
691 | using RangeTy = iterator_range<mop_reverse_iterator>; |
692 | SmallVector<RangeTy, 4> Worklist; |
693 | |
694 | public: |
695 | explicit TreeWalkerState(MachineInstr *Insert) { |
696 | const iterator_range<mop_iterator> &Range = Insert->explicit_uses(); |
697 | if (!Range.empty()) |
698 | Worklist.push_back(Elt: reverse(C: 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(RangeOrContainer&: 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(Elt: reverse(C: 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(C: 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. |
756 | class 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 | |
769 | public: |
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(Instr: Insert)) { |
783 | Operand0 = TargetInstrInfo::CommuteAnyOperandIndex; |
784 | Operand1 = TargetInstrInfo::CommuteAnyOperandIndex; |
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(Instr: 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 | |
804 | bool WebAssemblyRegStackify::runOnMachineFunction(MachineFunction &MF) { |
805 | LLVM_DEBUG(dbgs() << "********** Register Stackifying **********\n" |
806 | "********** Function: " |
807 | << MF.getName() << '\n'); |
808 | |
809 | bool Changed = false; |
810 | MachineRegisterInfo &MRI = MF.getRegInfo(); |
811 | WebAssemblyFunctionInfo &MFI = *MF.getInfo<WebAssemblyFunctionInfo>(); |
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. |
864 | if (WebAssembly::isArgument(Opc: DefI->getOpcode())) |
865 | continue; |
866 | |
867 | MachineOperand *Def = |
868 | DefI->findRegisterDefOperand(Reg, /*TRI=*/nullptr); |
869 | assert(Def != nullptr); |
870 | |
871 | // Decide which strategy to take. Prefer to move a single-use value |
872 | // over cloning it, and prefer cloning over introducing a tee. |
873 | // For moving, we require the def to be in the same block as the use; |
874 | // this makes things simpler (LiveIntervals' handleMove function only |
875 | // supports intra-block moves) and it's MachineSink's job to catch all |
876 | // the sinking opportunities anyway. |
877 | bool SameBlock = DefI->getParent() == &MBB; |
878 | bool CanMove = SameBlock && isSafeToMove(Def, Use: &Use, Insert, MFI, MRI) && |
879 | !TreeWalker.isOnStack(Reg); |
880 | if (CanMove && hasOneNonDBGUse(Reg, Def: DefI, MRI, MDT, LIS)) { |
881 | Insert = moveForSingleUse(Reg, Op&: Use, Def: DefI, MBB, Insert, LIS, MFI, MRI); |
882 | |
883 | // If we are removing the frame base reg completely, remove the debug |
884 | // info as well. |
885 | // TODO: Encode this properly as a stackified value. |
886 | if (MFI.isFrameBaseVirtual() && MFI.getFrameBaseVreg() == Reg) |
887 | MFI.clearFrameBaseVreg(); |
888 | } else if (shouldRematerialize(Def: *DefI, TII)) { |
889 | Insert = |
890 | rematerializeCheapDef(Reg, Op&: Use, Def&: *DefI, MBB, Insert: Insert->getIterator(), |
891 | LIS, MFI, MRI, TII, TRI); |
892 | } else if (CanMove && oneUseDominatesOtherUses(Reg, OneUse: Use, MBB, MRI, MDT, |
893 | LIS, MFI)) { |
894 | Insert = moveAndTeeForMultiUse(Reg, Op&: Use, Def: DefI, MBB, Insert, LIS, MFI, |
895 | MRI, TII); |
896 | } else { |
897 | // We failed to stackify the operand. If the problem was ordering |
898 | // constraints, Commuting may be able to help. |
899 | if (!CanMove && SameBlock) |
900 | Commuting.maybeCommute(Insert, TreeWalker, TII); |
901 | // Proceed to the next operand. |
902 | continue; |
903 | } |
904 | |
905 | // Stackifying a multivalue def may unlock in-place stackification of |
906 | // subsequent defs. TODO: Handle the case where the consecutive uses are |
907 | // not all in the same instruction. |
908 | auto *SubsequentDef = Insert->defs().begin(); |
909 | auto *SubsequentUse = &Use; |
910 | while (SubsequentDef != Insert->defs().end() && |
911 | SubsequentUse != Use.getParent()->uses().end()) { |
912 | if (!SubsequentDef->isReg() || !SubsequentUse->isReg()) |
913 | break; |
914 | Register DefReg = SubsequentDef->getReg(); |
915 | Register UseReg = SubsequentUse->getReg(); |
916 | // TODO: This single-use restriction could be relaxed by using tees |
917 | if (DefReg != UseReg || !MRI.hasOneNonDBGUse(RegNo: DefReg)) |
918 | break; |
919 | MFI.stackifyVReg(MRI, VReg: DefReg); |
920 | ++SubsequentDef; |
921 | ++SubsequentUse; |
922 | } |
923 | |
924 | // If the instruction we just stackified is an IMPLICIT_DEF, convert it |
925 | // to a constant 0 so that the def is explicit, and the push/pop |
926 | // correspondence is maintained. |
927 | if (Insert->getOpcode() == TargetOpcode::IMPLICIT_DEF) |
928 | convertImplicitDefToConstZero(Insert, MRI, TII, MF, LIS); |
929 | |
930 | // We stackified an operand. Add the defining instruction's operands to |
931 | // the worklist stack now to continue to build an ever deeper tree. |
932 | Commuting.reset(); |
933 | TreeWalker.pushOperands(Instr: Insert); |
934 | } |
935 | |
936 | // If we stackified any operands, skip over the tree to start looking for |
937 | // the next instruction we can build a tree on. |
938 | if (Insert != &*MII) { |
939 | imposeStackOrdering(MI: &*MII); |
940 | MII = MachineBasicBlock::iterator(Insert).getReverse(); |
941 | Changed = true; |
942 | } |
943 | } |
944 | } |
945 | |
946 | // If we used VALUE_STACK anywhere, add it to the live-in sets everywhere so |
947 | // that it never looks like a use-before-def. |
948 | if (Changed) { |
949 | MF.getRegInfo().addLiveIn(WebAssembly::VALUE_STACK); |
950 | for (MachineBasicBlock &MBB : MF) |
951 | MBB.addLiveIn(WebAssembly::VALUE_STACK); |
952 | } |
953 | |
954 | #ifndef NDEBUG |
955 | // Verify that pushes and pops are performed in LIFO order. |
956 | SmallVector<unsigned, 0> Stack; |
957 | for (MachineBasicBlock &MBB : MF) { |
958 | for (MachineInstr &MI : MBB) { |
959 | if (MI.isDebugInstr()) |
960 | continue; |
961 | for (MachineOperand &MO : reverse(C: MI.explicit_uses())) { |
962 | if (!MO.isReg()) |
963 | continue; |
964 | Register Reg = MO.getReg(); |
965 | if (MFI.isVRegStackified(VReg: Reg)) |
966 | assert(Stack.pop_back_val() == Reg && |
967 | "Register stack pop should be paired with a push" ); |
968 | } |
969 | for (MachineOperand &MO : MI.defs()) { |
970 | if (!MO.isReg()) |
971 | continue; |
972 | Register Reg = MO.getReg(); |
973 | if (MFI.isVRegStackified(VReg: Reg)) |
974 | Stack.push_back(Elt: MO.getReg()); |
975 | } |
976 | } |
977 | // TODO: Generalize this code to support keeping values on the stack across |
978 | // basic block boundaries. |
979 | assert(Stack.empty() && |
980 | "Register stack pushes and pops should be balanced" ); |
981 | } |
982 | #endif |
983 | |
984 | return Changed; |
985 | } |
986 | |