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