1 //===-- AVRExpandPseudoInsts.cpp - Expand pseudo instructions -------------===//
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 // This file contains a pass that expands pseudo instructions into target
10 // instructions. This pass should be run after register allocation but before
11 // the post-regalloc scheduling pass.
12 //
13 //===----------------------------------------------------------------------===//
14 
15 #include "AVR.h"
16 #include "AVRInstrInfo.h"
17 #include "AVRTargetMachine.h"
18 #include "MCTargetDesc/AVRMCTargetDesc.h"
19 
20 #include "llvm/CodeGen/MachineFunctionPass.h"
21 #include "llvm/CodeGen/MachineInstrBuilder.h"
22 #include "llvm/CodeGen/MachineRegisterInfo.h"
23 #include "llvm/CodeGen/RegisterScavenging.h"
24 #include "llvm/CodeGen/TargetRegisterInfo.h"
25 
26 using namespace llvm;
27 
28 #define AVR_EXPAND_PSEUDO_NAME "AVR pseudo instruction expansion pass"
29 
30 namespace {
31 
32 /// Expands "placeholder" instructions marked as pseudo into
33 /// actual AVR instructions.
34 class AVRExpandPseudo : public MachineFunctionPass {
35 public:
36   static char ID;
37 
38   AVRExpandPseudo() : MachineFunctionPass(ID) {
39     initializeAVRExpandPseudoPass(*PassRegistry::getPassRegistry());
40   }
41 
42   bool runOnMachineFunction(MachineFunction &MF) override;
43 
44   StringRef getPassName() const override { return AVR_EXPAND_PSEUDO_NAME; }
45 
46 private:
47   typedef MachineBasicBlock Block;
48   typedef Block::iterator BlockIt;
49 
50   const AVRRegisterInfo *TRI;
51   const TargetInstrInfo *TII;
52 
53   /// The register to be used for temporary storage.
54   const unsigned SCRATCH_REGISTER = AVR::R0;
55   /// The IO address of the status register.
56   const unsigned SREG_ADDR = 0x3f;
57 
58   bool expandMBB(Block &MBB);
59   bool expandMI(Block &MBB, BlockIt MBBI);
60   template <unsigned OP> bool expand(Block &MBB, BlockIt MBBI);
61 
62   MachineInstrBuilder buildMI(Block &MBB, BlockIt MBBI, unsigned Opcode) {
63     return BuildMI(MBB, MBBI, MBBI->getDebugLoc(), TII->get(Opcode));
64   }
65 
66   MachineInstrBuilder buildMI(Block &MBB, BlockIt MBBI, unsigned Opcode,
67                               unsigned DstReg) {
68     return BuildMI(MBB, MBBI, MBBI->getDebugLoc(), TII->get(Opcode), DstReg);
69   }
70 
71   MachineRegisterInfo &getRegInfo(Block &MBB) { return MBB.getParent()->getRegInfo(); }
72 
73   bool expandArith(unsigned OpLo, unsigned OpHi, Block &MBB, BlockIt MBBI);
74   bool expandLogic(unsigned Op, Block &MBB, BlockIt MBBI);
75   bool expandLogicImm(unsigned Op, Block &MBB, BlockIt MBBI);
76   bool isLogicImmOpRedundant(unsigned Op, unsigned ImmVal) const;
77 
78   template<typename Func>
79   bool expandAtomic(Block &MBB, BlockIt MBBI, Func f);
80 
81   template<typename Func>
82   bool expandAtomicBinaryOp(unsigned Opcode, Block &MBB, BlockIt MBBI, Func f);
83 
84   bool expandAtomicBinaryOp(unsigned Opcode, Block &MBB, BlockIt MBBI);
85 
86   bool expandAtomicArithmeticOp(unsigned MemOpcode,
87                                 unsigned ArithOpcode,
88                                 Block &MBB,
89                                 BlockIt MBBI);
90 
91   /// Scavenges a free GPR8 register for use.
92   unsigned scavengeGPR8(MachineInstr &MI);
93 };
94 
95 char AVRExpandPseudo::ID = 0;
96 
97 bool AVRExpandPseudo::expandMBB(MachineBasicBlock &MBB) {
98   bool Modified = false;
99 
100   BlockIt MBBI = MBB.begin(), E = MBB.end();
101   while (MBBI != E) {
102     BlockIt NMBBI = std::next(MBBI);
103     Modified |= expandMI(MBB, MBBI);
104     MBBI = NMBBI;
105   }
106 
107   return Modified;
108 }
109 
110 bool AVRExpandPseudo::runOnMachineFunction(MachineFunction &MF) {
111   bool Modified = false;
112 
113   const AVRSubtarget &STI = MF.getSubtarget<AVRSubtarget>();
114   TRI = STI.getRegisterInfo();
115   TII = STI.getInstrInfo();
116 
117   // We need to track liveness in order to use register scavenging.
118   MF.getProperties().set(MachineFunctionProperties::Property::TracksLiveness);
119 
120   for (Block &MBB : MF) {
121     bool ContinueExpanding = true;
122     unsigned ExpandCount = 0;
123 
124     // Continue expanding the block until all pseudos are expanded.
125     do {
126       assert(ExpandCount < 10 && "pseudo expand limit reached");
127 
128       bool BlockModified = expandMBB(MBB);
129       Modified |= BlockModified;
130       ExpandCount++;
131 
132       ContinueExpanding = BlockModified;
133     } while (ContinueExpanding);
134   }
135 
136   return Modified;
137 }
138 
139 bool AVRExpandPseudo::
140 expandArith(unsigned OpLo, unsigned OpHi, Block &MBB, BlockIt MBBI) {
141   MachineInstr &MI = *MBBI;
142   unsigned SrcLoReg, SrcHiReg, DstLoReg, DstHiReg;
143   unsigned DstReg = MI.getOperand(0).getReg();
144   unsigned SrcReg = MI.getOperand(2).getReg();
145   bool DstIsDead = MI.getOperand(0).isDead();
146   bool DstIsKill = MI.getOperand(1).isKill();
147   bool SrcIsKill = MI.getOperand(2).isKill();
148   bool ImpIsDead = MI.getOperand(3).isDead();
149   TRI->splitReg(SrcReg, SrcLoReg, SrcHiReg);
150   TRI->splitReg(DstReg, DstLoReg, DstHiReg);
151 
152   buildMI(MBB, MBBI, OpLo)
153     .addReg(DstLoReg, RegState::Define | getDeadRegState(DstIsDead))
154     .addReg(DstLoReg, getKillRegState(DstIsKill))
155     .addReg(SrcLoReg, getKillRegState(SrcIsKill));
156 
157   auto MIBHI = buildMI(MBB, MBBI, OpHi)
158     .addReg(DstHiReg, RegState::Define | getDeadRegState(DstIsDead))
159     .addReg(DstHiReg, getKillRegState(DstIsKill))
160     .addReg(SrcHiReg, getKillRegState(SrcIsKill));
161 
162   if (ImpIsDead)
163     MIBHI->getOperand(3).setIsDead();
164 
165   // SREG is always implicitly killed
166   MIBHI->getOperand(4).setIsKill();
167 
168   MI.eraseFromParent();
169   return true;
170 }
171 
172 bool AVRExpandPseudo::
173 expandLogic(unsigned Op, Block &MBB, BlockIt MBBI) {
174   MachineInstr &MI = *MBBI;
175   unsigned SrcLoReg, SrcHiReg, DstLoReg, DstHiReg;
176   unsigned DstReg = MI.getOperand(0).getReg();
177   unsigned SrcReg = MI.getOperand(2).getReg();
178   bool DstIsDead = MI.getOperand(0).isDead();
179   bool DstIsKill = MI.getOperand(1).isKill();
180   bool SrcIsKill = MI.getOperand(2).isKill();
181   bool ImpIsDead = MI.getOperand(3).isDead();
182   TRI->splitReg(SrcReg, SrcLoReg, SrcHiReg);
183   TRI->splitReg(DstReg, DstLoReg, DstHiReg);
184 
185   auto MIBLO = buildMI(MBB, MBBI, Op)
186     .addReg(DstLoReg, RegState::Define | getDeadRegState(DstIsDead))
187     .addReg(DstLoReg, getKillRegState(DstIsKill))
188     .addReg(SrcLoReg, getKillRegState(SrcIsKill));
189 
190   // SREG is always implicitly dead
191   MIBLO->getOperand(3).setIsDead();
192 
193   auto MIBHI = buildMI(MBB, MBBI, Op)
194     .addReg(DstHiReg, RegState::Define | getDeadRegState(DstIsDead))
195     .addReg(DstHiReg, getKillRegState(DstIsKill))
196     .addReg(SrcHiReg, getKillRegState(SrcIsKill));
197 
198   if (ImpIsDead)
199     MIBHI->getOperand(3).setIsDead();
200 
201   MI.eraseFromParent();
202   return true;
203 }
204 
205 bool AVRExpandPseudo::
206   isLogicImmOpRedundant(unsigned Op, unsigned ImmVal) const {
207 
208   // ANDI Rd, 0xff is redundant.
209   if (Op == AVR::ANDIRdK && ImmVal == 0xff)
210     return true;
211 
212   // ORI Rd, 0x0 is redundant.
213   if (Op == AVR::ORIRdK && ImmVal == 0x0)
214     return true;
215 
216   return false;
217 }
218 
219 bool AVRExpandPseudo::
220 expandLogicImm(unsigned Op, Block &MBB, BlockIt MBBI) {
221   MachineInstr &MI = *MBBI;
222   unsigned DstLoReg, DstHiReg;
223   unsigned DstReg = MI.getOperand(0).getReg();
224   bool DstIsDead = MI.getOperand(0).isDead();
225   bool SrcIsKill = MI.getOperand(1).isKill();
226   bool ImpIsDead = MI.getOperand(3).isDead();
227   unsigned Imm = MI.getOperand(2).getImm();
228   unsigned Lo8 = Imm & 0xff;
229   unsigned Hi8 = (Imm >> 8) & 0xff;
230   TRI->splitReg(DstReg, DstLoReg, DstHiReg);
231 
232   if (!isLogicImmOpRedundant(Op, Lo8)) {
233     auto MIBLO = buildMI(MBB, MBBI, Op)
234       .addReg(DstLoReg, RegState::Define | getDeadRegState(DstIsDead))
235       .addReg(DstLoReg, getKillRegState(SrcIsKill))
236       .addImm(Lo8);
237 
238     // SREG is always implicitly dead
239     MIBLO->getOperand(3).setIsDead();
240   }
241 
242   if (!isLogicImmOpRedundant(Op, Hi8)) {
243     auto MIBHI = buildMI(MBB, MBBI, Op)
244       .addReg(DstHiReg, RegState::Define | getDeadRegState(DstIsDead))
245       .addReg(DstHiReg, getKillRegState(SrcIsKill))
246       .addImm(Hi8);
247 
248     if (ImpIsDead)
249       MIBHI->getOperand(3).setIsDead();
250   }
251 
252   MI.eraseFromParent();
253   return true;
254 }
255 
256 template <>
257 bool AVRExpandPseudo::expand<AVR::ADDWRdRr>(Block &MBB, BlockIt MBBI) {
258   return expandArith(AVR::ADDRdRr, AVR::ADCRdRr, MBB, MBBI);
259 }
260 
261 template <>
262 bool AVRExpandPseudo::expand<AVR::ADCWRdRr>(Block &MBB, BlockIt MBBI) {
263   return expandArith(AVR::ADCRdRr, AVR::ADCRdRr, MBB, MBBI);
264 }
265 
266 template <>
267 bool AVRExpandPseudo::expand<AVR::SUBWRdRr>(Block &MBB, BlockIt MBBI) {
268   return expandArith(AVR::SUBRdRr, AVR::SBCRdRr, MBB, MBBI);
269 }
270 
271 template <>
272 bool AVRExpandPseudo::expand<AVR::SUBIWRdK>(Block &MBB, BlockIt MBBI) {
273   MachineInstr &MI = *MBBI;
274   unsigned DstLoReg, DstHiReg;
275   unsigned DstReg = MI.getOperand(0).getReg();
276   bool DstIsDead = MI.getOperand(0).isDead();
277   bool SrcIsKill = MI.getOperand(1).isKill();
278   bool ImpIsDead = MI.getOperand(3).isDead();
279   TRI->splitReg(DstReg, DstLoReg, DstHiReg);
280 
281   auto MIBLO = buildMI(MBB, MBBI, AVR::SUBIRdK)
282     .addReg(DstLoReg, RegState::Define | getDeadRegState(DstIsDead))
283     .addReg(DstLoReg, getKillRegState(SrcIsKill));
284 
285   auto MIBHI = buildMI(MBB, MBBI, AVR::SBCIRdK)
286     .addReg(DstHiReg, RegState::Define | getDeadRegState(DstIsDead))
287     .addReg(DstHiReg, getKillRegState(SrcIsKill));
288 
289   switch (MI.getOperand(2).getType()) {
290   case MachineOperand::MO_GlobalAddress: {
291     const GlobalValue *GV = MI.getOperand(2).getGlobal();
292     int64_t Offs = MI.getOperand(2).getOffset();
293     unsigned TF = MI.getOperand(2).getTargetFlags();
294     MIBLO.addGlobalAddress(GV, Offs, TF | AVRII::MO_NEG | AVRII::MO_LO);
295     MIBHI.addGlobalAddress(GV, Offs, TF | AVRII::MO_NEG | AVRII::MO_HI);
296     break;
297   }
298   case MachineOperand::MO_Immediate: {
299     unsigned Imm = MI.getOperand(2).getImm();
300     MIBLO.addImm(Imm & 0xff);
301     MIBHI.addImm((Imm >> 8) & 0xff);
302     break;
303   }
304   default:
305     llvm_unreachable("Unknown operand type!");
306   }
307 
308   if (ImpIsDead)
309     MIBHI->getOperand(3).setIsDead();
310 
311   // SREG is always implicitly killed
312   MIBHI->getOperand(4).setIsKill();
313 
314   MI.eraseFromParent();
315   return true;
316 }
317 
318 template <>
319 bool AVRExpandPseudo::expand<AVR::SBCWRdRr>(Block &MBB, BlockIt MBBI) {
320   return expandArith(AVR::SBCRdRr, AVR::SBCRdRr, MBB, MBBI);
321 }
322 
323 template <>
324 bool AVRExpandPseudo::expand<AVR::SBCIWRdK>(Block &MBB, BlockIt MBBI) {
325   MachineInstr &MI = *MBBI;
326   unsigned OpLo, OpHi, DstLoReg, DstHiReg;
327   unsigned DstReg = MI.getOperand(0).getReg();
328   bool DstIsDead = MI.getOperand(0).isDead();
329   bool SrcIsKill = MI.getOperand(1).isKill();
330   bool ImpIsDead = MI.getOperand(3).isDead();
331   unsigned Imm = MI.getOperand(2).getImm();
332   unsigned Lo8 = Imm & 0xff;
333   unsigned Hi8 = (Imm >> 8) & 0xff;
334   OpLo = AVR::SBCIRdK;
335   OpHi = AVR::SBCIRdK;
336   TRI->splitReg(DstReg, DstLoReg, DstHiReg);
337 
338   auto MIBLO = buildMI(MBB, MBBI, OpLo)
339     .addReg(DstLoReg, RegState::Define | getDeadRegState(DstIsDead))
340     .addReg(DstLoReg, getKillRegState(SrcIsKill))
341     .addImm(Lo8);
342 
343   // SREG is always implicitly killed
344   MIBLO->getOperand(4).setIsKill();
345 
346   auto MIBHI = buildMI(MBB, MBBI, OpHi)
347     .addReg(DstHiReg, RegState::Define | getDeadRegState(DstIsDead))
348     .addReg(DstHiReg, getKillRegState(SrcIsKill))
349     .addImm(Hi8);
350 
351   if (ImpIsDead)
352     MIBHI->getOperand(3).setIsDead();
353 
354   // SREG is always implicitly killed
355   MIBHI->getOperand(4).setIsKill();
356 
357   MI.eraseFromParent();
358   return true;
359 }
360 
361 template <>
362 bool AVRExpandPseudo::expand<AVR::ANDWRdRr>(Block &MBB, BlockIt MBBI) {
363   return expandLogic(AVR::ANDRdRr, MBB, MBBI);
364 }
365 
366 template <>
367 bool AVRExpandPseudo::expand<AVR::ANDIWRdK>(Block &MBB, BlockIt MBBI) {
368   return expandLogicImm(AVR::ANDIRdK, MBB, MBBI);
369 }
370 
371 template <>
372 bool AVRExpandPseudo::expand<AVR::ORWRdRr>(Block &MBB, BlockIt MBBI) {
373   return expandLogic(AVR::ORRdRr, MBB, MBBI);
374 }
375 
376 template <>
377 bool AVRExpandPseudo::expand<AVR::ORIWRdK>(Block &MBB, BlockIt MBBI) {
378   return expandLogicImm(AVR::ORIRdK, MBB, MBBI);
379 }
380 
381 template <>
382 bool AVRExpandPseudo::expand<AVR::EORWRdRr>(Block &MBB, BlockIt MBBI) {
383   return expandLogic(AVR::EORRdRr, MBB, MBBI);
384 }
385 
386 template <>
387 bool AVRExpandPseudo::expand<AVR::COMWRd>(Block &MBB, BlockIt MBBI) {
388   MachineInstr &MI = *MBBI;
389   unsigned OpLo, OpHi, DstLoReg, DstHiReg;
390   unsigned DstReg = MI.getOperand(0).getReg();
391   bool DstIsDead = MI.getOperand(0).isDead();
392   bool DstIsKill = MI.getOperand(1).isKill();
393   bool ImpIsDead = MI.getOperand(2).isDead();
394   OpLo = AVR::COMRd;
395   OpHi = AVR::COMRd;
396   TRI->splitReg(DstReg, DstLoReg, DstHiReg);
397 
398   auto MIBLO = buildMI(MBB, MBBI, OpLo)
399     .addReg(DstLoReg, RegState::Define | getDeadRegState(DstIsDead))
400     .addReg(DstLoReg, getKillRegState(DstIsKill));
401 
402   // SREG is always implicitly dead
403   MIBLO->getOperand(2).setIsDead();
404 
405   auto MIBHI = buildMI(MBB, MBBI, OpHi)
406     .addReg(DstHiReg, RegState::Define | getDeadRegState(DstIsDead))
407     .addReg(DstHiReg, getKillRegState(DstIsKill));
408 
409   if (ImpIsDead)
410     MIBHI->getOperand(2).setIsDead();
411 
412   MI.eraseFromParent();
413   return true;
414 }
415 
416 template <>
417 bool AVRExpandPseudo::expand<AVR::CPWRdRr>(Block &MBB, BlockIt MBBI) {
418   MachineInstr &MI = *MBBI;
419   unsigned OpLo, OpHi, SrcLoReg, SrcHiReg, DstLoReg, DstHiReg;
420   unsigned DstReg = MI.getOperand(0).getReg();
421   unsigned SrcReg = MI.getOperand(1).getReg();
422   bool DstIsKill = MI.getOperand(0).isKill();
423   bool SrcIsKill = MI.getOperand(1).isKill();
424   bool ImpIsDead = MI.getOperand(2).isDead();
425   OpLo = AVR::CPRdRr;
426   OpHi = AVR::CPCRdRr;
427   TRI->splitReg(SrcReg, SrcLoReg, SrcHiReg);
428   TRI->splitReg(DstReg, DstLoReg, DstHiReg);
429 
430   // Low part
431   buildMI(MBB, MBBI, OpLo)
432     .addReg(DstLoReg, getKillRegState(DstIsKill))
433     .addReg(SrcLoReg, getKillRegState(SrcIsKill));
434 
435   auto MIBHI = buildMI(MBB, MBBI, OpHi)
436     .addReg(DstHiReg, getKillRegState(DstIsKill))
437     .addReg(SrcHiReg, getKillRegState(SrcIsKill));
438 
439   if (ImpIsDead)
440     MIBHI->getOperand(2).setIsDead();
441 
442   // SREG is always implicitly killed
443   MIBHI->getOperand(3).setIsKill();
444 
445   MI.eraseFromParent();
446   return true;
447 }
448 
449 template <>
450 bool AVRExpandPseudo::expand<AVR::CPCWRdRr>(Block &MBB, BlockIt MBBI) {
451   MachineInstr &MI = *MBBI;
452   unsigned OpLo, OpHi, SrcLoReg, SrcHiReg, DstLoReg, DstHiReg;
453   unsigned DstReg = MI.getOperand(0).getReg();
454   unsigned SrcReg = MI.getOperand(1).getReg();
455   bool DstIsKill = MI.getOperand(0).isKill();
456   bool SrcIsKill = MI.getOperand(1).isKill();
457   bool ImpIsDead = MI.getOperand(2).isDead();
458   OpLo = AVR::CPCRdRr;
459   OpHi = AVR::CPCRdRr;
460   TRI->splitReg(SrcReg, SrcLoReg, SrcHiReg);
461   TRI->splitReg(DstReg, DstLoReg, DstHiReg);
462 
463   auto MIBLO = buildMI(MBB, MBBI, OpLo)
464     .addReg(DstLoReg, getKillRegState(DstIsKill))
465     .addReg(SrcLoReg, getKillRegState(SrcIsKill));
466 
467   // SREG is always implicitly killed
468   MIBLO->getOperand(3).setIsKill();
469 
470   auto MIBHI = buildMI(MBB, MBBI, OpHi)
471     .addReg(DstHiReg, getKillRegState(DstIsKill))
472     .addReg(SrcHiReg, getKillRegState(SrcIsKill));
473 
474   if (ImpIsDead)
475     MIBHI->getOperand(2).setIsDead();
476 
477   // SREG is always implicitly killed
478   MIBHI->getOperand(3).setIsKill();
479 
480   MI.eraseFromParent();
481   return true;
482 }
483 
484 template <>
485 bool AVRExpandPseudo::expand<AVR::LDIWRdK>(Block &MBB, BlockIt MBBI) {
486   MachineInstr &MI = *MBBI;
487   unsigned OpLo, OpHi, DstLoReg, DstHiReg;
488   unsigned DstReg = MI.getOperand(0).getReg();
489   bool DstIsDead = MI.getOperand(0).isDead();
490   OpLo = AVR::LDIRdK;
491   OpHi = AVR::LDIRdK;
492   TRI->splitReg(DstReg, DstLoReg, DstHiReg);
493 
494   auto MIBLO = buildMI(MBB, MBBI, OpLo)
495     .addReg(DstLoReg, RegState::Define | getDeadRegState(DstIsDead));
496 
497   auto MIBHI = buildMI(MBB, MBBI, OpHi)
498     .addReg(DstHiReg, RegState::Define | getDeadRegState(DstIsDead));
499 
500   switch (MI.getOperand(1).getType()) {
501   case MachineOperand::MO_GlobalAddress: {
502     const GlobalValue *GV = MI.getOperand(1).getGlobal();
503     int64_t Offs = MI.getOperand(1).getOffset();
504     unsigned TF = MI.getOperand(1).getTargetFlags();
505 
506     MIBLO.addGlobalAddress(GV, Offs, TF | AVRII::MO_LO);
507     MIBHI.addGlobalAddress(GV, Offs, TF | AVRII::MO_HI);
508     break;
509   }
510   case MachineOperand::MO_BlockAddress: {
511     const BlockAddress *BA = MI.getOperand(1).getBlockAddress();
512     unsigned TF = MI.getOperand(1).getTargetFlags();
513 
514     MIBLO.add(MachineOperand::CreateBA(BA, TF | AVRII::MO_LO));
515     MIBHI.add(MachineOperand::CreateBA(BA, TF | AVRII::MO_HI));
516     break;
517   }
518   case MachineOperand::MO_Immediate: {
519     unsigned Imm = MI.getOperand(1).getImm();
520 
521     MIBLO.addImm(Imm & 0xff);
522     MIBHI.addImm((Imm >> 8) & 0xff);
523     break;
524   }
525   default:
526     llvm_unreachable("Unknown operand type!");
527   }
528 
529   MI.eraseFromParent();
530   return true;
531 }
532 
533 template <>
534 bool AVRExpandPseudo::expand<AVR::LDSWRdK>(Block &MBB, BlockIt MBBI) {
535   MachineInstr &MI = *MBBI;
536   unsigned OpLo, OpHi, DstLoReg, DstHiReg;
537   unsigned DstReg = MI.getOperand(0).getReg();
538   bool DstIsDead = MI.getOperand(0).isDead();
539   OpLo = AVR::LDSRdK;
540   OpHi = AVR::LDSRdK;
541   TRI->splitReg(DstReg, DstLoReg, DstHiReg);
542 
543   auto MIBLO = buildMI(MBB, MBBI, OpLo)
544     .addReg(DstLoReg, RegState::Define | getDeadRegState(DstIsDead));
545 
546   auto MIBHI = buildMI(MBB, MBBI, OpHi)
547     .addReg(DstHiReg, RegState::Define | getDeadRegState(DstIsDead));
548 
549   switch (MI.getOperand(1).getType()) {
550   case MachineOperand::MO_GlobalAddress: {
551     const GlobalValue *GV = MI.getOperand(1).getGlobal();
552     int64_t Offs = MI.getOperand(1).getOffset();
553     unsigned TF = MI.getOperand(1).getTargetFlags();
554 
555     MIBLO.addGlobalAddress(GV, Offs, TF);
556     MIBHI.addGlobalAddress(GV, Offs + 1, TF);
557     break;
558   }
559   case MachineOperand::MO_Immediate: {
560     unsigned Imm = MI.getOperand(1).getImm();
561 
562     MIBLO.addImm(Imm);
563     MIBHI.addImm(Imm + 1);
564     break;
565   }
566   default:
567     llvm_unreachable("Unknown operand type!");
568   }
569 
570   MIBLO.setMemRefs(MI.memoperands());
571   MIBHI.setMemRefs(MI.memoperands());
572 
573   MI.eraseFromParent();
574   return true;
575 }
576 
577 template <>
578 bool AVRExpandPseudo::expand<AVR::LDWRdPtr>(Block &MBB, BlockIt MBBI) {
579   MachineInstr &MI = *MBBI;
580   unsigned OpLo, OpHi, DstLoReg, DstHiReg;
581   unsigned DstReg = MI.getOperand(0).getReg();
582   unsigned TmpReg = 0; // 0 for no temporary register
583   unsigned SrcReg = MI.getOperand(1).getReg();
584   bool SrcIsKill = MI.getOperand(1).isKill();
585   OpLo = AVR::LDRdPtr;
586   OpHi = AVR::LDDRdPtrQ;
587   TRI->splitReg(DstReg, DstLoReg, DstHiReg);
588 
589   // Use a temporary register if src and dst registers are the same.
590   if (DstReg == SrcReg)
591     TmpReg = scavengeGPR8(MI);
592 
593   unsigned CurDstLoReg = (DstReg == SrcReg) ? TmpReg : DstLoReg;
594   unsigned CurDstHiReg = (DstReg == SrcReg) ? TmpReg : DstHiReg;
595 
596   // Load low byte.
597   auto MIBLO = buildMI(MBB, MBBI, OpLo)
598     .addReg(CurDstLoReg, RegState::Define)
599     .addReg(SrcReg, RegState::Define);
600 
601   // Push low byte onto stack if necessary.
602   if (TmpReg)
603     buildMI(MBB, MBBI, AVR::PUSHRr).addReg(TmpReg);
604 
605   // Load high byte.
606   auto MIBHI = buildMI(MBB, MBBI, OpHi)
607     .addReg(CurDstHiReg, RegState::Define)
608     .addReg(SrcReg, getKillRegState(SrcIsKill))
609     .addImm(1);
610 
611   if (TmpReg) {
612     // Move the high byte into the final destination.
613     buildMI(MBB, MBBI, AVR::MOVRdRr).addReg(DstHiReg).addReg(TmpReg);
614 
615     // Move the low byte from the scratch space into the final destination.
616     buildMI(MBB, MBBI, AVR::POPRd).addReg(DstLoReg);
617   }
618 
619   MIBLO.setMemRefs(MI.memoperands());
620   MIBHI.setMemRefs(MI.memoperands());
621 
622   MI.eraseFromParent();
623   return true;
624 }
625 
626 template <>
627 bool AVRExpandPseudo::expand<AVR::LDWRdPtrPi>(Block &MBB, BlockIt MBBI) {
628   MachineInstr &MI = *MBBI;
629   unsigned OpLo, OpHi, DstLoReg, DstHiReg;
630   unsigned DstReg = MI.getOperand(0).getReg();
631   unsigned SrcReg = MI.getOperand(1).getReg();
632   bool DstIsDead = MI.getOperand(0).isDead();
633   bool SrcIsDead = MI.getOperand(1).isKill();
634   OpLo = AVR::LDRdPtrPi;
635   OpHi = AVR::LDRdPtrPi;
636   TRI->splitReg(DstReg, DstLoReg, DstHiReg);
637 
638   assert(DstReg != SrcReg && "SrcReg and DstReg cannot be the same");
639 
640   auto MIBLO = buildMI(MBB, MBBI, OpLo)
641     .addReg(DstLoReg, RegState::Define | getDeadRegState(DstIsDead))
642     .addReg(SrcReg, RegState::Define)
643     .addReg(SrcReg, RegState::Kill);
644 
645   auto MIBHI = buildMI(MBB, MBBI, OpHi)
646     .addReg(DstHiReg, RegState::Define | getDeadRegState(DstIsDead))
647     .addReg(SrcReg, RegState::Define | getDeadRegState(SrcIsDead))
648     .addReg(SrcReg, RegState::Kill);
649 
650   MIBLO.setMemRefs(MI.memoperands());
651   MIBHI.setMemRefs(MI.memoperands());
652 
653   MI.eraseFromParent();
654   return true;
655 }
656 
657 template <>
658 bool AVRExpandPseudo::expand<AVR::LDWRdPtrPd>(Block &MBB, BlockIt MBBI) {
659   MachineInstr &MI = *MBBI;
660   unsigned OpLo, OpHi, DstLoReg, DstHiReg;
661   unsigned DstReg = MI.getOperand(0).getReg();
662   unsigned SrcReg = MI.getOperand(1).getReg();
663   bool DstIsDead = MI.getOperand(0).isDead();
664   bool SrcIsDead = MI.getOperand(1).isKill();
665   OpLo = AVR::LDRdPtrPd;
666   OpHi = AVR::LDRdPtrPd;
667   TRI->splitReg(DstReg, DstLoReg, DstHiReg);
668 
669   assert(DstReg != SrcReg && "SrcReg and DstReg cannot be the same");
670 
671   auto MIBHI = buildMI(MBB, MBBI, OpHi)
672     .addReg(DstHiReg, RegState::Define | getDeadRegState(DstIsDead))
673     .addReg(SrcReg, RegState::Define)
674     .addReg(SrcReg, RegState::Kill);
675 
676   auto MIBLO = buildMI(MBB, MBBI, OpLo)
677     .addReg(DstLoReg, RegState::Define | getDeadRegState(DstIsDead))
678     .addReg(SrcReg, RegState::Define | getDeadRegState(SrcIsDead))
679     .addReg(SrcReg, RegState::Kill);
680 
681   MIBLO.setMemRefs(MI.memoperands());
682   MIBHI.setMemRefs(MI.memoperands());
683 
684   MI.eraseFromParent();
685   return true;
686 }
687 
688 template <>
689 bool AVRExpandPseudo::expand<AVR::LDDWRdPtrQ>(Block &MBB, BlockIt MBBI) {
690   MachineInstr &MI = *MBBI;
691   unsigned OpLo, OpHi, DstLoReg, DstHiReg;
692   unsigned DstReg = MI.getOperand(0).getReg();
693   unsigned TmpReg = 0; // 0 for no temporary register
694   unsigned SrcReg = MI.getOperand(1).getReg();
695   unsigned Imm = MI.getOperand(2).getImm();
696   bool SrcIsKill = MI.getOperand(1).isKill();
697   OpLo = AVR::LDDRdPtrQ;
698   OpHi = AVR::LDDRdPtrQ;
699   TRI->splitReg(DstReg, DstLoReg, DstHiReg);
700 
701   // Since we add 1 to the Imm value for the high byte below, and 63 is the highest Imm value
702   // allowed for the instruction, 62 is the limit here.
703   assert(Imm <= 62 && "Offset is out of range");
704 
705   // Use a temporary register if src and dst registers are the same.
706   if (DstReg == SrcReg)
707     TmpReg = scavengeGPR8(MI);
708 
709   unsigned CurDstLoReg = (DstReg == SrcReg) ? TmpReg : DstLoReg;
710   unsigned CurDstHiReg = (DstReg == SrcReg) ? TmpReg : DstHiReg;
711 
712   // Load low byte.
713   auto MIBLO = buildMI(MBB, MBBI, OpLo)
714     .addReg(CurDstLoReg, RegState::Define)
715     .addReg(SrcReg)
716     .addImm(Imm);
717 
718   // Push low byte onto stack if necessary.
719   if (TmpReg)
720     buildMI(MBB, MBBI, AVR::PUSHRr).addReg(TmpReg);
721 
722   // Load high byte.
723   auto MIBHI = buildMI(MBB, MBBI, OpHi)
724     .addReg(CurDstHiReg, RegState::Define)
725     .addReg(SrcReg, getKillRegState(SrcIsKill))
726     .addImm(Imm + 1);
727 
728   if (TmpReg) {
729     // Move the high byte into the final destination.
730     buildMI(MBB, MBBI, AVR::MOVRdRr).addReg(DstHiReg).addReg(TmpReg);
731 
732     // Move the low byte from the scratch space into the final destination.
733     buildMI(MBB, MBBI, AVR::POPRd).addReg(DstLoReg);
734   }
735 
736   MIBLO.setMemRefs(MI.memoperands());
737   MIBHI.setMemRefs(MI.memoperands());
738 
739   MI.eraseFromParent();
740   return true;
741 }
742 
743 template <>
744 bool AVRExpandPseudo::expand<AVR::LPMWRdZ>(Block &MBB, BlockIt MBBI) {
745   MachineInstr &MI = *MBBI;
746   unsigned OpLo, OpHi, DstLoReg, DstHiReg;
747   unsigned DstReg = MI.getOperand(0).getReg();
748   unsigned TmpReg = 0; // 0 for no temporary register
749   unsigned SrcReg = MI.getOperand(1).getReg();
750   bool SrcIsKill = MI.getOperand(1).isKill();
751   OpLo = AVR::LPMRdZPi;
752   OpHi = AVR::LPMRdZ;
753   TRI->splitReg(DstReg, DstLoReg, DstHiReg);
754 
755   // Use a temporary register if src and dst registers are the same.
756   if (DstReg == SrcReg)
757     TmpReg = scavengeGPR8(MI);
758 
759   unsigned CurDstLoReg = (DstReg == SrcReg) ? TmpReg : DstLoReg;
760   unsigned CurDstHiReg = (DstReg == SrcReg) ? TmpReg : DstHiReg;
761 
762   // Load low byte.
763   auto MIBLO = buildMI(MBB, MBBI, OpLo)
764       .addReg(CurDstLoReg, RegState::Define)
765       .addReg(SrcReg);
766 
767   // Push low byte onto stack if necessary.
768   if (TmpReg)
769     buildMI(MBB, MBBI, AVR::PUSHRr).addReg(TmpReg);
770 
771   // Load high byte.
772   auto MIBHI = buildMI(MBB, MBBI, OpHi)
773       .addReg(CurDstHiReg, RegState::Define)
774       .addReg(SrcReg, getKillRegState(SrcIsKill));
775 
776   if (TmpReg) {
777     // Move the high byte into the final destination.
778     buildMI(MBB, MBBI, AVR::MOVRdRr).addReg(DstHiReg).addReg(TmpReg);
779 
780     // Move the low byte from the scratch space into the final destination.
781     buildMI(MBB, MBBI, AVR::POPRd).addReg(DstLoReg);
782   }
783 
784   MIBLO.setMemRefs(MI.memoperands());
785   MIBHI.setMemRefs(MI.memoperands());
786 
787   MI.eraseFromParent();
788   return true;
789 }
790 
791 template <>
792 bool AVRExpandPseudo::expand<AVR::LPMWRdZPi>(Block &MBB, BlockIt MBBI) {
793   llvm_unreachable("wide LPMPi is unimplemented");
794 }
795 
796 template<typename Func>
797 bool AVRExpandPseudo::expandAtomic(Block &MBB, BlockIt MBBI, Func f) {
798   // Remove the pseudo instruction.
799   MachineInstr &MI = *MBBI;
800 
801   // Store the SREG.
802   buildMI(MBB, MBBI, AVR::INRdA)
803     .addReg(SCRATCH_REGISTER, RegState::Define)
804     .addImm(SREG_ADDR);
805 
806   // Disable exceptions.
807   buildMI(MBB, MBBI, AVR::BCLRs).addImm(7); // CLI
808 
809   f(MI);
810 
811   // Restore the status reg.
812   buildMI(MBB, MBBI, AVR::OUTARr)
813     .addImm(SREG_ADDR)
814     .addReg(SCRATCH_REGISTER);
815 
816   MI.eraseFromParent();
817   return true;
818 }
819 
820 template<typename Func>
821 bool AVRExpandPseudo::expandAtomicBinaryOp(unsigned Opcode,
822                                            Block &MBB,
823                                            BlockIt MBBI,
824                                            Func f) {
825   return expandAtomic(MBB, MBBI, [&](MachineInstr &MI) {
826       auto Op1 = MI.getOperand(0);
827       auto Op2 = MI.getOperand(1);
828 
829       MachineInstr &NewInst =
830           *buildMI(MBB, MBBI, Opcode).add(Op1).add(Op2).getInstr();
831       f(NewInst);
832   });
833 }
834 
835 bool AVRExpandPseudo::expandAtomicBinaryOp(unsigned Opcode,
836                                            Block &MBB,
837                                            BlockIt MBBI) {
838   return expandAtomicBinaryOp(Opcode, MBB, MBBI, [](MachineInstr &MI) {});
839 }
840 
841 bool AVRExpandPseudo::expandAtomicArithmeticOp(unsigned Width,
842                                                unsigned ArithOpcode,
843                                                Block &MBB,
844                                                BlockIt MBBI) {
845   return expandAtomic(MBB, MBBI, [&](MachineInstr &MI) {
846       auto Op1 = MI.getOperand(0);
847       auto Op2 = MI.getOperand(1);
848 
849       unsigned LoadOpcode = (Width == 8) ? AVR::LDRdPtr : AVR::LDWRdPtr;
850       unsigned StoreOpcode = (Width == 8) ? AVR::STPtrRr : AVR::STWPtrRr;
851 
852       // Create the load
853       buildMI(MBB, MBBI, LoadOpcode).add(Op1).add(Op2);
854 
855       // Create the arithmetic op
856       buildMI(MBB, MBBI, ArithOpcode).add(Op1).add(Op1).add(Op2);
857 
858       // Create the store
859       buildMI(MBB, MBBI, StoreOpcode).add(Op2).add(Op1);
860   });
861 }
862 
863 unsigned AVRExpandPseudo::scavengeGPR8(MachineInstr &MI) {
864   MachineBasicBlock &MBB = *MI.getParent();
865   RegScavenger RS;
866 
867   RS.enterBasicBlock(MBB);
868   RS.forward(MI);
869 
870   BitVector Candidates =
871       TRI->getAllocatableSet
872       (*MBB.getParent(), &AVR::GPR8RegClass);
873 
874   // Exclude all the registers being used by the instruction.
875   for (MachineOperand &MO : MI.operands()) {
876     if (MO.isReg() && MO.getReg() != 0 && !MO.isDef() &&
877         !TargetRegisterInfo::isVirtualRegister(MO.getReg()))
878       Candidates.reset(MO.getReg());
879   }
880 
881   BitVector Available = RS.getRegsAvailable(&AVR::GPR8RegClass);
882   Available &= Candidates;
883 
884   signed Reg = Available.find_first();
885   assert(Reg != -1 && "ran out of registers");
886   return Reg;
887 }
888 
889 template<>
890 bool AVRExpandPseudo::expand<AVR::AtomicLoad8>(Block &MBB, BlockIt MBBI) {
891   return expandAtomicBinaryOp(AVR::LDRdPtr, MBB, MBBI);
892 }
893 
894 template<>
895 bool AVRExpandPseudo::expand<AVR::AtomicLoad16>(Block &MBB, BlockIt MBBI) {
896   return expandAtomicBinaryOp(AVR::LDWRdPtr, MBB, MBBI);
897 }
898 
899 template<>
900 bool AVRExpandPseudo::expand<AVR::AtomicStore8>(Block &MBB, BlockIt MBBI) {
901   return expandAtomicBinaryOp(AVR::STPtrRr, MBB, MBBI);
902 }
903 
904 template<>
905 bool AVRExpandPseudo::expand<AVR::AtomicStore16>(Block &MBB, BlockIt MBBI) {
906   return expandAtomicBinaryOp(AVR::STWPtrRr, MBB, MBBI);
907 }
908 
909 template<>
910 bool AVRExpandPseudo::expand<AVR::AtomicLoadAdd8>(Block &MBB, BlockIt MBBI) {
911   return expandAtomicArithmeticOp(8, AVR::ADDRdRr, MBB, MBBI);
912 }
913 
914 template<>
915 bool AVRExpandPseudo::expand<AVR::AtomicLoadAdd16>(Block &MBB, BlockIt MBBI) {
916   return expandAtomicArithmeticOp(16, AVR::ADDWRdRr, MBB, MBBI);
917 }
918 
919 template<>
920 bool AVRExpandPseudo::expand<AVR::AtomicLoadSub8>(Block &MBB, BlockIt MBBI) {
921   return expandAtomicArithmeticOp(8, AVR::SUBRdRr, MBB, MBBI);
922 }
923 
924 template<>
925 bool AVRExpandPseudo::expand<AVR::AtomicLoadSub16>(Block &MBB, BlockIt MBBI) {
926   return expandAtomicArithmeticOp(16, AVR::SUBWRdRr, MBB, MBBI);
927 }
928 
929 template<>
930 bool AVRExpandPseudo::expand<AVR::AtomicLoadAnd8>(Block &MBB, BlockIt MBBI) {
931   return expandAtomicArithmeticOp(8, AVR::ANDRdRr, MBB, MBBI);
932 }
933 
934 template<>
935 bool AVRExpandPseudo::expand<AVR::AtomicLoadAnd16>(Block &MBB, BlockIt MBBI) {
936   return expandAtomicArithmeticOp(16, AVR::ANDWRdRr, MBB, MBBI);
937 }
938 
939 template<>
940 bool AVRExpandPseudo::expand<AVR::AtomicLoadOr8>(Block &MBB, BlockIt MBBI) {
941   return expandAtomicArithmeticOp(8, AVR::ORRdRr, MBB, MBBI);
942 }
943 
944 template<>
945 bool AVRExpandPseudo::expand<AVR::AtomicLoadOr16>(Block &MBB, BlockIt MBBI) {
946   return expandAtomicArithmeticOp(16, AVR::ORWRdRr, MBB, MBBI);
947 }
948 
949 template<>
950 bool AVRExpandPseudo::expand<AVR::AtomicLoadXor8>(Block &MBB, BlockIt MBBI) {
951   return expandAtomicArithmeticOp(8, AVR::EORRdRr, MBB, MBBI);
952 }
953 
954 template<>
955 bool AVRExpandPseudo::expand<AVR::AtomicLoadXor16>(Block &MBB, BlockIt MBBI) {
956   return expandAtomicArithmeticOp(16, AVR::EORWRdRr, MBB, MBBI);
957 }
958 
959 template<>
960 bool AVRExpandPseudo::expand<AVR::AtomicFence>(Block &MBB, BlockIt MBBI) {
961   // On AVR, there is only one core and so atomic fences do nothing.
962   MBBI->eraseFromParent();
963   return true;
964 }
965 
966 template <>
967 bool AVRExpandPseudo::expand<AVR::STSWKRr>(Block &MBB, BlockIt MBBI) {
968   MachineInstr &MI = *MBBI;
969   unsigned OpLo, OpHi, SrcLoReg, SrcHiReg;
970   unsigned SrcReg = MI.getOperand(1).getReg();
971   bool SrcIsKill = MI.getOperand(1).isKill();
972   OpLo = AVR::STSKRr;
973   OpHi = AVR::STSKRr;
974   TRI->splitReg(SrcReg, SrcLoReg, SrcHiReg);
975 
976   // Write the high byte first in case this address belongs to a special
977   // I/O address with a special temporary register.
978   auto MIBHI = buildMI(MBB, MBBI, OpHi);
979   auto MIBLO = buildMI(MBB, MBBI, OpLo);
980 
981   switch (MI.getOperand(0).getType()) {
982   case MachineOperand::MO_GlobalAddress: {
983     const GlobalValue *GV = MI.getOperand(0).getGlobal();
984     int64_t Offs = MI.getOperand(0).getOffset();
985     unsigned TF = MI.getOperand(0).getTargetFlags();
986 
987     MIBLO.addGlobalAddress(GV, Offs, TF);
988     MIBHI.addGlobalAddress(GV, Offs + 1, TF);
989     break;
990   }
991   case MachineOperand::MO_Immediate: {
992     unsigned Imm = MI.getOperand(0).getImm();
993 
994     MIBLO.addImm(Imm);
995     MIBHI.addImm(Imm + 1);
996     break;
997   }
998   default:
999     llvm_unreachable("Unknown operand type!");
1000   }
1001 
1002   MIBLO.addReg(SrcLoReg, getKillRegState(SrcIsKill));
1003   MIBHI.addReg(SrcHiReg, getKillRegState(SrcIsKill));
1004 
1005   MIBLO.setMemRefs(MI.memoperands());
1006   MIBHI.setMemRefs(MI.memoperands());
1007 
1008   MI.eraseFromParent();
1009   return true;
1010 }
1011 
1012 template <>
1013 bool AVRExpandPseudo::expand<AVR::STWPtrRr>(Block &MBB, BlockIt MBBI) {
1014   MachineInstr &MI = *MBBI;
1015   unsigned OpLo, OpHi, SrcLoReg, SrcHiReg;
1016   unsigned DstReg = MI.getOperand(0).getReg();
1017   unsigned SrcReg = MI.getOperand(1).getReg();
1018   bool SrcIsKill = MI.getOperand(1).isKill();
1019   OpLo = AVR::STPtrRr;
1020   OpHi = AVR::STDPtrQRr;
1021   TRI->splitReg(SrcReg, SrcLoReg, SrcHiReg);
1022 
1023   //:TODO: need to reverse this order like inw and stsw?
1024   auto MIBLO = buildMI(MBB, MBBI, OpLo)
1025     .addReg(DstReg)
1026     .addReg(SrcLoReg, getKillRegState(SrcIsKill));
1027 
1028   auto MIBHI = buildMI(MBB, MBBI, OpHi)
1029     .addReg(DstReg)
1030     .addImm(1)
1031     .addReg(SrcHiReg, getKillRegState(SrcIsKill));
1032 
1033   MIBLO.setMemRefs(MI.memoperands());
1034   MIBHI.setMemRefs(MI.memoperands());
1035 
1036   MI.eraseFromParent();
1037   return true;
1038 }
1039 
1040 template <>
1041 bool AVRExpandPseudo::expand<AVR::STWPtrPiRr>(Block &MBB, BlockIt MBBI) {
1042   MachineInstr &MI = *MBBI;
1043   unsigned OpLo, OpHi, SrcLoReg, SrcHiReg;
1044   unsigned DstReg = MI.getOperand(0).getReg();
1045   unsigned SrcReg = MI.getOperand(2).getReg();
1046   unsigned Imm = MI.getOperand(3).getImm();
1047   bool DstIsDead = MI.getOperand(0).isDead();
1048   bool SrcIsKill = MI.getOperand(2).isKill();
1049   OpLo = AVR::STPtrPiRr;
1050   OpHi = AVR::STPtrPiRr;
1051   TRI->splitReg(SrcReg, SrcLoReg, SrcHiReg);
1052 
1053   assert(DstReg != SrcReg && "SrcReg and DstReg cannot be the same");
1054 
1055   auto MIBLO = buildMI(MBB, MBBI, OpLo)
1056     .addReg(DstReg, RegState::Define)
1057     .addReg(DstReg, RegState::Kill)
1058     .addReg(SrcLoReg, getKillRegState(SrcIsKill))
1059     .addImm(Imm);
1060 
1061   auto MIBHI = buildMI(MBB, MBBI, OpHi)
1062     .addReg(DstReg, RegState::Define | getDeadRegState(DstIsDead))
1063     .addReg(DstReg, RegState::Kill)
1064     .addReg(SrcHiReg, getKillRegState(SrcIsKill))
1065     .addImm(Imm);
1066 
1067   MIBLO.setMemRefs(MI.memoperands());
1068   MIBHI.setMemRefs(MI.memoperands());
1069 
1070   MI.eraseFromParent();
1071   return true;
1072 }
1073 
1074 template <>
1075 bool AVRExpandPseudo::expand<AVR::STWPtrPdRr>(Block &MBB, BlockIt MBBI) {
1076   MachineInstr &MI = *MBBI;
1077   unsigned OpLo, OpHi, SrcLoReg, SrcHiReg;
1078   unsigned DstReg = MI.getOperand(0).getReg();
1079   unsigned SrcReg = MI.getOperand(2).getReg();
1080   unsigned Imm = MI.getOperand(3).getImm();
1081   bool DstIsDead = MI.getOperand(0).isDead();
1082   bool SrcIsKill = MI.getOperand(2).isKill();
1083   OpLo = AVR::STPtrPdRr;
1084   OpHi = AVR::STPtrPdRr;
1085   TRI->splitReg(SrcReg, SrcLoReg, SrcHiReg);
1086 
1087   assert(DstReg != SrcReg && "SrcReg and DstReg cannot be the same");
1088 
1089   auto MIBHI = buildMI(MBB, MBBI, OpHi)
1090     .addReg(DstReg, RegState::Define)
1091     .addReg(DstReg, RegState::Kill)
1092     .addReg(SrcHiReg, getKillRegState(SrcIsKill))
1093     .addImm(Imm);
1094 
1095   auto MIBLO = buildMI(MBB, MBBI, OpLo)
1096     .addReg(DstReg, RegState::Define | getDeadRegState(DstIsDead))
1097     .addReg(DstReg, RegState::Kill)
1098     .addReg(SrcLoReg, getKillRegState(SrcIsKill))
1099     .addImm(Imm);
1100 
1101   MIBLO.setMemRefs(MI.memoperands());
1102   MIBHI.setMemRefs(MI.memoperands());
1103 
1104   MI.eraseFromParent();
1105   return true;
1106 }
1107 
1108 template <>
1109 bool AVRExpandPseudo::expand<AVR::STDWPtrQRr>(Block &MBB, BlockIt MBBI) {
1110   MachineInstr &MI = *MBBI;
1111   unsigned OpLo, OpHi, SrcLoReg, SrcHiReg;
1112   unsigned DstReg = MI.getOperand(0).getReg();
1113   unsigned SrcReg = MI.getOperand(2).getReg();
1114   unsigned Imm = MI.getOperand(1).getImm();
1115   bool DstIsKill = MI.getOperand(0).isKill();
1116   bool SrcIsKill = MI.getOperand(2).isKill();
1117   OpLo = AVR::STDPtrQRr;
1118   OpHi = AVR::STDPtrQRr;
1119   TRI->splitReg(SrcReg, SrcLoReg, SrcHiReg);
1120 
1121   // Since we add 1 to the Imm value for the high byte below, and 63 is the highest Imm value
1122   // allowed for the instruction, 62 is the limit here.
1123   assert(Imm <= 62 && "Offset is out of range");
1124 
1125   auto MIBLO = buildMI(MBB, MBBI, OpLo)
1126     .addReg(DstReg)
1127     .addImm(Imm)
1128     .addReg(SrcLoReg, getKillRegState(SrcIsKill));
1129 
1130   auto MIBHI = buildMI(MBB, MBBI, OpHi)
1131     .addReg(DstReg, getKillRegState(DstIsKill))
1132     .addImm(Imm + 1)
1133     .addReg(SrcHiReg, getKillRegState(SrcIsKill));
1134 
1135   MIBLO.setMemRefs(MI.memoperands());
1136   MIBHI.setMemRefs(MI.memoperands());
1137 
1138   MI.eraseFromParent();
1139   return true;
1140 }
1141 
1142 template <>
1143 bool AVRExpandPseudo::expand<AVR::INWRdA>(Block &MBB, BlockIt MBBI) {
1144   MachineInstr &MI = *MBBI;
1145   unsigned OpLo, OpHi, DstLoReg, DstHiReg;
1146   unsigned Imm = MI.getOperand(1).getImm();
1147   unsigned DstReg = MI.getOperand(0).getReg();
1148   bool DstIsDead = MI.getOperand(0).isDead();
1149   OpLo = AVR::INRdA;
1150   OpHi = AVR::INRdA;
1151   TRI->splitReg(DstReg, DstLoReg, DstHiReg);
1152 
1153   // Since we add 1 to the Imm value for the high byte below, and 63 is the highest Imm value
1154   // allowed for the instruction, 62 is the limit here.
1155   assert(Imm <= 62 && "Address is out of range");
1156 
1157   auto MIBLO = buildMI(MBB, MBBI, OpLo)
1158     .addReg(DstLoReg, RegState::Define | getDeadRegState(DstIsDead))
1159     .addImm(Imm);
1160 
1161   auto MIBHI = buildMI(MBB, MBBI, OpHi)
1162     .addReg(DstHiReg, RegState::Define | getDeadRegState(DstIsDead))
1163     .addImm(Imm + 1);
1164 
1165   MIBLO.setMemRefs(MI.memoperands());
1166   MIBHI.setMemRefs(MI.memoperands());
1167 
1168   MI.eraseFromParent();
1169   return true;
1170 }
1171 
1172 template <>
1173 bool AVRExpandPseudo::expand<AVR::OUTWARr>(Block &MBB, BlockIt MBBI) {
1174   MachineInstr &MI = *MBBI;
1175   unsigned OpLo, OpHi, SrcLoReg, SrcHiReg;
1176   unsigned Imm = MI.getOperand(0).getImm();
1177   unsigned SrcReg = MI.getOperand(1).getReg();
1178   bool SrcIsKill = MI.getOperand(1).isKill();
1179   OpLo = AVR::OUTARr;
1180   OpHi = AVR::OUTARr;
1181   TRI->splitReg(SrcReg, SrcLoReg, SrcHiReg);
1182 
1183   // Since we add 1 to the Imm value for the high byte below, and 63 is the highest Imm value
1184   // allowed for the instruction, 62 is the limit here.
1185   assert(Imm <= 62 && "Address is out of range");
1186 
1187   // 16 bit I/O writes need the high byte first
1188   auto MIBHI = buildMI(MBB, MBBI, OpHi)
1189     .addImm(Imm + 1)
1190     .addReg(SrcHiReg, getKillRegState(SrcIsKill));
1191 
1192   auto MIBLO = buildMI(MBB, MBBI, OpLo)
1193     .addImm(Imm)
1194     .addReg(SrcLoReg, getKillRegState(SrcIsKill));
1195 
1196   MIBLO.setMemRefs(MI.memoperands());
1197   MIBHI.setMemRefs(MI.memoperands());
1198 
1199   MI.eraseFromParent();
1200   return true;
1201 }
1202 
1203 template <>
1204 bool AVRExpandPseudo::expand<AVR::PUSHWRr>(Block &MBB, BlockIt MBBI) {
1205   MachineInstr &MI = *MBBI;
1206   unsigned OpLo, OpHi, SrcLoReg, SrcHiReg;
1207   unsigned SrcReg = MI.getOperand(0).getReg();
1208   bool SrcIsKill = MI.getOperand(0).isKill();
1209   unsigned Flags = MI.getFlags();
1210   OpLo = AVR::PUSHRr;
1211   OpHi = AVR::PUSHRr;
1212   TRI->splitReg(SrcReg, SrcLoReg, SrcHiReg);
1213 
1214   // Low part
1215   buildMI(MBB, MBBI, OpLo)
1216     .addReg(SrcLoReg, getKillRegState(SrcIsKill))
1217     .setMIFlags(Flags);
1218 
1219   // High part
1220   buildMI(MBB, MBBI, OpHi)
1221     .addReg(SrcHiReg, getKillRegState(SrcIsKill))
1222     .setMIFlags(Flags);
1223 
1224   MI.eraseFromParent();
1225   return true;
1226 }
1227 
1228 template <>
1229 bool AVRExpandPseudo::expand<AVR::POPWRd>(Block &MBB, BlockIt MBBI) {
1230   MachineInstr &MI = *MBBI;
1231   unsigned OpLo, OpHi, DstLoReg, DstHiReg;
1232   unsigned DstReg = MI.getOperand(0).getReg();
1233   unsigned Flags = MI.getFlags();
1234   OpLo = AVR::POPRd;
1235   OpHi = AVR::POPRd;
1236   TRI->splitReg(DstReg, DstLoReg, DstHiReg);
1237 
1238   buildMI(MBB, MBBI, OpHi, DstHiReg).setMIFlags(Flags); // High
1239   buildMI(MBB, MBBI, OpLo, DstLoReg).setMIFlags(Flags); // Low
1240 
1241   MI.eraseFromParent();
1242   return true;
1243 }
1244 
1245 template <>
1246 bool AVRExpandPseudo::expand<AVR::LSLWRd>(Block &MBB, BlockIt MBBI) {
1247   MachineInstr &MI = *MBBI;
1248   unsigned OpLo, OpHi, DstLoReg, DstHiReg;
1249   unsigned DstReg = MI.getOperand(0).getReg();
1250   bool DstIsDead = MI.getOperand(0).isDead();
1251   bool DstIsKill = MI.getOperand(1).isKill();
1252   bool ImpIsDead = MI.getOperand(2).isDead();
1253   OpLo = AVR::ADDRdRr; // ADD Rd, Rd <==> LSL Rd
1254   OpHi = AVR::ADCRdRr; // ADC Rd, Rd <==> ROL Rd
1255   TRI->splitReg(DstReg, DstLoReg, DstHiReg);
1256 
1257   // Low part
1258   buildMI(MBB, MBBI, OpLo)
1259     .addReg(DstLoReg, RegState::Define | getDeadRegState(DstIsDead))
1260     .addReg(DstLoReg)
1261     .addReg(DstLoReg, getKillRegState(DstIsKill));
1262 
1263   auto MIBHI = buildMI(MBB, MBBI, OpHi)
1264     .addReg(DstHiReg, RegState::Define | getDeadRegState(DstIsDead))
1265     .addReg(DstHiReg)
1266     .addReg(DstHiReg, getKillRegState(DstIsKill));
1267 
1268   if (ImpIsDead)
1269     MIBHI->getOperand(3).setIsDead();
1270 
1271   // SREG is always implicitly killed
1272   MIBHI->getOperand(4).setIsKill();
1273 
1274   MI.eraseFromParent();
1275   return true;
1276 }
1277 
1278 template <>
1279 bool AVRExpandPseudo::expand<AVR::LSRWRd>(Block &MBB, BlockIt MBBI) {
1280   MachineInstr &MI = *MBBI;
1281   unsigned OpLo, OpHi, DstLoReg, DstHiReg;
1282   unsigned DstReg = MI.getOperand(0).getReg();
1283   bool DstIsDead = MI.getOperand(0).isDead();
1284   bool DstIsKill = MI.getOperand(1).isKill();
1285   bool ImpIsDead = MI.getOperand(2).isDead();
1286   OpLo = AVR::RORRd;
1287   OpHi = AVR::LSRRd;
1288   TRI->splitReg(DstReg, DstLoReg, DstHiReg);
1289 
1290   // High part
1291   buildMI(MBB, MBBI, OpHi)
1292     .addReg(DstHiReg, RegState::Define | getDeadRegState(DstIsDead))
1293     .addReg(DstHiReg, getKillRegState(DstIsKill));
1294 
1295   auto MIBLO = buildMI(MBB, MBBI, OpLo)
1296     .addReg(DstLoReg, RegState::Define | getDeadRegState(DstIsDead))
1297     .addReg(DstLoReg, getKillRegState(DstIsKill));
1298 
1299   if (ImpIsDead)
1300     MIBLO->getOperand(2).setIsDead();
1301 
1302   // SREG is always implicitly killed
1303   MIBLO->getOperand(3).setIsKill();
1304 
1305   MI.eraseFromParent();
1306   return true;
1307 }
1308 
1309 template <>
1310 bool AVRExpandPseudo::expand<AVR::RORWRd>(Block &MBB, BlockIt MBBI) {
1311   llvm_unreachable("RORW unimplemented");
1312   return false;
1313 }
1314 
1315 template <>
1316 bool AVRExpandPseudo::expand<AVR::ROLWRd>(Block &MBB, BlockIt MBBI) {
1317   llvm_unreachable("ROLW unimplemented");
1318   return false;
1319 }
1320 
1321 template <>
1322 bool AVRExpandPseudo::expand<AVR::ASRWRd>(Block &MBB, BlockIt MBBI) {
1323   MachineInstr &MI = *MBBI;
1324   unsigned OpLo, OpHi, DstLoReg, DstHiReg;
1325   unsigned DstReg = MI.getOperand(0).getReg();
1326   bool DstIsDead = MI.getOperand(0).isDead();
1327   bool DstIsKill = MI.getOperand(1).isKill();
1328   bool ImpIsDead = MI.getOperand(2).isDead();
1329   OpLo = AVR::RORRd;
1330   OpHi = AVR::ASRRd;
1331   TRI->splitReg(DstReg, DstLoReg, DstHiReg);
1332 
1333   // High part
1334   buildMI(MBB, MBBI, OpHi)
1335     .addReg(DstHiReg, RegState::Define | getDeadRegState(DstIsDead))
1336     .addReg(DstHiReg, getKillRegState(DstIsKill));
1337 
1338   auto MIBLO = buildMI(MBB, MBBI, OpLo)
1339     .addReg(DstLoReg, RegState::Define | getDeadRegState(DstIsDead))
1340     .addReg(DstLoReg, getKillRegState(DstIsKill));
1341 
1342   if (ImpIsDead)
1343     MIBLO->getOperand(2).setIsDead();
1344 
1345   // SREG is always implicitly killed
1346   MIBLO->getOperand(3).setIsKill();
1347 
1348   MI.eraseFromParent();
1349   return true;
1350 }
1351 
1352 template <> bool AVRExpandPseudo::expand<AVR::SEXT>(Block &MBB, BlockIt MBBI) {
1353   MachineInstr &MI = *MBBI;
1354   unsigned DstLoReg, DstHiReg;
1355   // sext R17:R16, R17
1356   // mov     r16, r17
1357   // lsl     r17
1358   // sbc     r17, r17
1359   // sext R17:R16, R13
1360   // mov     r16, r13
1361   // mov     r17, r13
1362   // lsl     r17
1363   // sbc     r17, r17
1364   // sext R17:R16, R16
1365   // mov     r17, r16
1366   // lsl     r17
1367   // sbc     r17, r17
1368   unsigned DstReg = MI.getOperand(0).getReg();
1369   unsigned SrcReg = MI.getOperand(1).getReg();
1370   bool DstIsDead = MI.getOperand(0).isDead();
1371   bool SrcIsKill = MI.getOperand(1).isKill();
1372   bool ImpIsDead = MI.getOperand(2).isDead();
1373   TRI->splitReg(DstReg, DstLoReg, DstHiReg);
1374 
1375   if (SrcReg != DstLoReg) {
1376     auto MOV = buildMI(MBB, MBBI, AVR::MOVRdRr)
1377       .addReg(DstLoReg, RegState::Define | getDeadRegState(DstIsDead))
1378       .addReg(SrcReg);
1379 
1380     if (SrcReg == DstHiReg) {
1381       MOV->getOperand(1).setIsKill();
1382     }
1383   }
1384 
1385   if (SrcReg != DstHiReg) {
1386     buildMI(MBB, MBBI, AVR::MOVRdRr)
1387       .addReg(DstHiReg, RegState::Define)
1388       .addReg(SrcReg, getKillRegState(SrcIsKill));
1389   }
1390 
1391   buildMI(MBB, MBBI, AVR::ADDRdRr) // LSL Rd <==> ADD Rd, Rr
1392     .addReg(DstHiReg, RegState::Define)
1393     .addReg(DstHiReg)
1394     .addReg(DstHiReg, RegState::Kill);
1395 
1396   auto SBC = buildMI(MBB, MBBI, AVR::SBCRdRr)
1397     .addReg(DstHiReg, RegState::Define | getDeadRegState(DstIsDead))
1398     .addReg(DstHiReg, RegState::Kill)
1399     .addReg(DstHiReg, RegState::Kill);
1400 
1401   if (ImpIsDead)
1402     SBC->getOperand(3).setIsDead();
1403 
1404   // SREG is always implicitly killed
1405   SBC->getOperand(4).setIsKill();
1406 
1407   MI.eraseFromParent();
1408   return true;
1409 }
1410 
1411 template <> bool AVRExpandPseudo::expand<AVR::ZEXT>(Block &MBB, BlockIt MBBI) {
1412   MachineInstr &MI = *MBBI;
1413   unsigned DstLoReg, DstHiReg;
1414   // zext R25:R24, R20
1415   // mov      R24, R20
1416   // eor      R25, R25
1417   // zext R25:R24, R24
1418   // eor      R25, R25
1419   // zext R25:R24, R25
1420   // mov      R24, R25
1421   // eor      R25, R25
1422   unsigned DstReg = MI.getOperand(0).getReg();
1423   unsigned SrcReg = MI.getOperand(1).getReg();
1424   bool DstIsDead = MI.getOperand(0).isDead();
1425   bool SrcIsKill = MI.getOperand(1).isKill();
1426   bool ImpIsDead = MI.getOperand(2).isDead();
1427   TRI->splitReg(DstReg, DstLoReg, DstHiReg);
1428 
1429   if (SrcReg != DstLoReg) {
1430     buildMI(MBB, MBBI, AVR::MOVRdRr)
1431       .addReg(DstLoReg, RegState::Define | getDeadRegState(DstIsDead))
1432       .addReg(SrcReg, getKillRegState(SrcIsKill));
1433   }
1434 
1435   auto EOR = buildMI(MBB, MBBI, AVR::EORRdRr)
1436     .addReg(DstHiReg, RegState::Define | getDeadRegState(DstIsDead))
1437     .addReg(DstHiReg, RegState::Kill)
1438     .addReg(DstHiReg, RegState::Kill);
1439 
1440   if (ImpIsDead)
1441     EOR->getOperand(3).setIsDead();
1442 
1443   MI.eraseFromParent();
1444   return true;
1445 }
1446 
1447 template <>
1448 bool AVRExpandPseudo::expand<AVR::SPREAD>(Block &MBB, BlockIt MBBI) {
1449   MachineInstr &MI = *MBBI;
1450   unsigned OpLo, OpHi, DstLoReg, DstHiReg;
1451   unsigned DstReg = MI.getOperand(0).getReg();
1452   bool DstIsDead = MI.getOperand(0).isDead();
1453   unsigned Flags = MI.getFlags();
1454   OpLo = AVR::INRdA;
1455   OpHi = AVR::INRdA;
1456   TRI->splitReg(DstReg, DstLoReg, DstHiReg);
1457 
1458   // Low part
1459   buildMI(MBB, MBBI, OpLo)
1460     .addReg(DstLoReg, RegState::Define | getDeadRegState(DstIsDead))
1461     .addImm(0x3d)
1462     .setMIFlags(Flags);
1463 
1464   // High part
1465   buildMI(MBB, MBBI, OpHi)
1466     .addReg(DstHiReg, RegState::Define | getDeadRegState(DstIsDead))
1467     .addImm(0x3e)
1468     .setMIFlags(Flags);
1469 
1470   MI.eraseFromParent();
1471   return true;
1472 }
1473 
1474 template <>
1475 bool AVRExpandPseudo::expand<AVR::SPWRITE>(Block &MBB, BlockIt MBBI) {
1476   MachineInstr &MI = *MBBI;
1477   unsigned SrcLoReg, SrcHiReg;
1478   unsigned SrcReg = MI.getOperand(1).getReg();
1479   bool SrcIsKill = MI.getOperand(1).isKill();
1480   unsigned Flags = MI.getFlags();
1481   TRI->splitReg(SrcReg, SrcLoReg, SrcHiReg);
1482 
1483   buildMI(MBB, MBBI, AVR::INRdA)
1484     .addReg(AVR::R0, RegState::Define)
1485     .addImm(SREG_ADDR)
1486     .setMIFlags(Flags);
1487 
1488   buildMI(MBB, MBBI, AVR::BCLRs).addImm(0x07).setMIFlags(Flags);
1489 
1490   buildMI(MBB, MBBI, AVR::OUTARr)
1491     .addImm(0x3e)
1492     .addReg(SrcHiReg, getKillRegState(SrcIsKill))
1493     .setMIFlags(Flags);
1494 
1495   buildMI(MBB, MBBI, AVR::OUTARr)
1496     .addImm(SREG_ADDR)
1497     .addReg(AVR::R0, RegState::Kill)
1498     .setMIFlags(Flags);
1499 
1500   buildMI(MBB, MBBI, AVR::OUTARr)
1501     .addImm(0x3d)
1502     .addReg(SrcLoReg, getKillRegState(SrcIsKill))
1503     .setMIFlags(Flags);
1504 
1505   MI.eraseFromParent();
1506   return true;
1507 }
1508 
1509 bool AVRExpandPseudo::expandMI(Block &MBB, BlockIt MBBI) {
1510   MachineInstr &MI = *MBBI;
1511   int Opcode = MBBI->getOpcode();
1512 
1513 #define EXPAND(Op)               \
1514   case Op:                       \
1515     return expand<Op>(MBB, MI)
1516 
1517   switch (Opcode) {
1518     EXPAND(AVR::ADDWRdRr);
1519     EXPAND(AVR::ADCWRdRr);
1520     EXPAND(AVR::SUBWRdRr);
1521     EXPAND(AVR::SUBIWRdK);
1522     EXPAND(AVR::SBCWRdRr);
1523     EXPAND(AVR::SBCIWRdK);
1524     EXPAND(AVR::ANDWRdRr);
1525     EXPAND(AVR::ANDIWRdK);
1526     EXPAND(AVR::ORWRdRr);
1527     EXPAND(AVR::ORIWRdK);
1528     EXPAND(AVR::EORWRdRr);
1529     EXPAND(AVR::COMWRd);
1530     EXPAND(AVR::CPWRdRr);
1531     EXPAND(AVR::CPCWRdRr);
1532     EXPAND(AVR::LDIWRdK);
1533     EXPAND(AVR::LDSWRdK);
1534     EXPAND(AVR::LDWRdPtr);
1535     EXPAND(AVR::LDWRdPtrPi);
1536     EXPAND(AVR::LDWRdPtrPd);
1537   case AVR::LDDWRdYQ: //:FIXME: remove this once PR13375 gets fixed
1538     EXPAND(AVR::LDDWRdPtrQ);
1539     EXPAND(AVR::LPMWRdZ);
1540     EXPAND(AVR::LPMWRdZPi);
1541     EXPAND(AVR::AtomicLoad8);
1542     EXPAND(AVR::AtomicLoad16);
1543     EXPAND(AVR::AtomicStore8);
1544     EXPAND(AVR::AtomicStore16);
1545     EXPAND(AVR::AtomicLoadAdd8);
1546     EXPAND(AVR::AtomicLoadAdd16);
1547     EXPAND(AVR::AtomicLoadSub8);
1548     EXPAND(AVR::AtomicLoadSub16);
1549     EXPAND(AVR::AtomicLoadAnd8);
1550     EXPAND(AVR::AtomicLoadAnd16);
1551     EXPAND(AVR::AtomicLoadOr8);
1552     EXPAND(AVR::AtomicLoadOr16);
1553     EXPAND(AVR::AtomicLoadXor8);
1554     EXPAND(AVR::AtomicLoadXor16);
1555     EXPAND(AVR::AtomicFence);
1556     EXPAND(AVR::STSWKRr);
1557     EXPAND(AVR::STWPtrRr);
1558     EXPAND(AVR::STWPtrPiRr);
1559     EXPAND(AVR::STWPtrPdRr);
1560     EXPAND(AVR::STDWPtrQRr);
1561     EXPAND(AVR::INWRdA);
1562     EXPAND(AVR::OUTWARr);
1563     EXPAND(AVR::PUSHWRr);
1564     EXPAND(AVR::POPWRd);
1565     EXPAND(AVR::LSLWRd);
1566     EXPAND(AVR::LSRWRd);
1567     EXPAND(AVR::RORWRd);
1568     EXPAND(AVR::ROLWRd);
1569     EXPAND(AVR::ASRWRd);
1570     EXPAND(AVR::SEXT);
1571     EXPAND(AVR::ZEXT);
1572     EXPAND(AVR::SPREAD);
1573     EXPAND(AVR::SPWRITE);
1574   }
1575 #undef EXPAND
1576   return false;
1577 }
1578 
1579 } // end of anonymous namespace
1580 
1581 INITIALIZE_PASS(AVRExpandPseudo, "avr-expand-pseudo",
1582                 AVR_EXPAND_PSEUDO_NAME, false, false)
1583 namespace llvm {
1584 
1585 FunctionPass *createAVRExpandPseudoPass() { return new AVRExpandPseudo(); }
1586 
1587 } // end of namespace llvm
1588