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