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 
58   bool expandMBB(Block &MBB);
59   bool expandMI(Block &MBB, BlockIt MBBI);
60   template <unsigned OP> bool expand(Block &MBB, BlockIt MBBI);
61 
62   MachineInstrBuilder buildMI(Block &MBB, BlockIt MBBI, unsigned Opcode) {
63     return BuildMI(MBB, MBBI, MBBI->getDebugLoc(), TII->get(Opcode));
64   }
65 
66   MachineInstrBuilder buildMI(Block &MBB, BlockIt MBBI, unsigned Opcode,
67                               Register DstReg) {
68     return BuildMI(MBB, MBBI, MBBI->getDebugLoc(), TII->get(Opcode), DstReg);
69   }
70 
71   MachineRegisterInfo &getRegInfo(Block &MBB) {
72     return MBB.getParent()->getRegInfo();
73   }
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> 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   /// Specific shift implementation for int8.
88   bool expandLSLB7Rd(Block &MBB, BlockIt MBBI);
89   bool expandLSRB7Rd(Block &MBB, BlockIt MBBI);
90   bool expandASRB6Rd(Block &MBB, BlockIt MBBI);
91   bool expandASRB7Rd(Block &MBB, BlockIt MBBI);
92 
93   /// Specific shift implementation for int16.
94   bool expandLSLW4Rd(Block &MBB, BlockIt MBBI);
95   bool expandLSRW4Rd(Block &MBB, BlockIt MBBI);
96   bool expandASRW7Rd(Block &MBB, BlockIt MBBI);
97   bool expandLSLW8Rd(Block &MBB, BlockIt MBBI);
98   bool expandLSRW8Rd(Block &MBB, BlockIt MBBI);
99   bool expandASRW8Rd(Block &MBB, BlockIt MBBI);
100   bool expandLSLW12Rd(Block &MBB, BlockIt MBBI);
101   bool expandLSRW12Rd(Block &MBB, BlockIt MBBI);
102   bool expandASRW14Rd(Block &MBB, BlockIt MBBI);
103   bool expandASRW15Rd(Block &MBB, BlockIt MBBI);
104 
105   // Common implementation of LPMWRdZ and ELPMWRdZ.
106   bool expandLPMWELPMW(Block &MBB, BlockIt MBBI, bool IsExt);
107 
108   /// Scavenges a free GPR8 register for use.
109   Register scavengeGPR8(MachineInstr &MI);
110 };
111 
112 char AVRExpandPseudo::ID = 0;
113 
114 bool AVRExpandPseudo::expandMBB(MachineBasicBlock &MBB) {
115   bool Modified = false;
116 
117   BlockIt MBBI = MBB.begin(), E = MBB.end();
118   while (MBBI != E) {
119     BlockIt NMBBI = std::next(MBBI);
120     Modified |= expandMI(MBB, MBBI);
121     MBBI = NMBBI;
122   }
123 
124   return Modified;
125 }
126 
127 bool AVRExpandPseudo::runOnMachineFunction(MachineFunction &MF) {
128   bool Modified = false;
129 
130   const AVRSubtarget &STI = MF.getSubtarget<AVRSubtarget>();
131   TRI = STI.getRegisterInfo();
132   TII = STI.getInstrInfo();
133 
134   // We need to track liveness in order to use register scavenging.
135   MF.getProperties().set(MachineFunctionProperties::Property::TracksLiveness);
136 
137   for (Block &MBB : MF) {
138     bool ContinueExpanding = true;
139     unsigned ExpandCount = 0;
140 
141     // Continue expanding the block until all pseudos are expanded.
142     do {
143       assert(ExpandCount < 10 && "pseudo expand limit reached");
144       (void)ExpandCount;
145 
146       bool BlockModified = expandMBB(MBB);
147       Modified |= BlockModified;
148       ExpandCount++;
149 
150       ContinueExpanding = BlockModified;
151     } while (ContinueExpanding);
152   }
153 
154   return Modified;
155 }
156 
157 bool AVRExpandPseudo::expandArith(unsigned OpLo, unsigned OpHi, Block &MBB,
158                                   BlockIt MBBI) {
159   MachineInstr &MI = *MBBI;
160   Register SrcLoReg, SrcHiReg, DstLoReg, DstHiReg;
161   Register DstReg = MI.getOperand(0).getReg();
162   Register SrcReg = MI.getOperand(2).getReg();
163   bool DstIsDead = MI.getOperand(0).isDead();
164   bool DstIsKill = MI.getOperand(1).isKill();
165   bool SrcIsKill = MI.getOperand(2).isKill();
166   bool ImpIsDead = MI.getOperand(3).isDead();
167   TRI->splitReg(SrcReg, SrcLoReg, SrcHiReg);
168   TRI->splitReg(DstReg, DstLoReg, DstHiReg);
169 
170   buildMI(MBB, MBBI, OpLo)
171       .addReg(DstLoReg, RegState::Define | getDeadRegState(DstIsDead))
172       .addReg(DstLoReg, getKillRegState(DstIsKill))
173       .addReg(SrcLoReg, getKillRegState(SrcIsKill));
174 
175   auto MIBHI =
176       buildMI(MBB, MBBI, OpHi)
177           .addReg(DstHiReg, RegState::Define | getDeadRegState(DstIsDead))
178           .addReg(DstHiReg, getKillRegState(DstIsKill))
179           .addReg(SrcHiReg, getKillRegState(SrcIsKill));
180 
181   if (ImpIsDead)
182     MIBHI->getOperand(3).setIsDead();
183 
184   // SREG is always implicitly killed
185   MIBHI->getOperand(4).setIsKill();
186 
187   MI.eraseFromParent();
188   return true;
189 }
190 
191 bool AVRExpandPseudo::expandLogic(unsigned Op, Block &MBB, BlockIt MBBI) {
192   MachineInstr &MI = *MBBI;
193   Register SrcLoReg, SrcHiReg, DstLoReg, DstHiReg;
194   Register DstReg = MI.getOperand(0).getReg();
195   Register SrcReg = MI.getOperand(2).getReg();
196   bool DstIsDead = MI.getOperand(0).isDead();
197   bool DstIsKill = MI.getOperand(1).isKill();
198   bool SrcIsKill = MI.getOperand(2).isKill();
199   bool ImpIsDead = MI.getOperand(3).isDead();
200   TRI->splitReg(SrcReg, SrcLoReg, SrcHiReg);
201   TRI->splitReg(DstReg, DstLoReg, DstHiReg);
202 
203   auto MIBLO =
204       buildMI(MBB, MBBI, Op)
205           .addReg(DstLoReg, RegState::Define | getDeadRegState(DstIsDead))
206           .addReg(DstLoReg, getKillRegState(DstIsKill))
207           .addReg(SrcLoReg, getKillRegState(SrcIsKill));
208 
209   // SREG is always implicitly dead
210   MIBLO->getOperand(3).setIsDead();
211 
212   auto MIBHI =
213       buildMI(MBB, MBBI, Op)
214           .addReg(DstHiReg, RegState::Define | getDeadRegState(DstIsDead))
215           .addReg(DstHiReg, getKillRegState(DstIsKill))
216           .addReg(SrcHiReg, getKillRegState(SrcIsKill));
217 
218   if (ImpIsDead)
219     MIBHI->getOperand(3).setIsDead();
220 
221   MI.eraseFromParent();
222   return true;
223 }
224 
225 bool AVRExpandPseudo::isLogicImmOpRedundant(unsigned Op,
226                                             unsigned ImmVal) const {
227 
228   // ANDI Rd, 0xff is redundant.
229   if (Op == AVR::ANDIRdK && ImmVal == 0xff)
230     return true;
231 
232   // ORI Rd, 0x0 is redundant.
233   if (Op == AVR::ORIRdK && ImmVal == 0x0)
234     return true;
235 
236   return false;
237 }
238 
239 bool AVRExpandPseudo::expandLogicImm(unsigned Op, Block &MBB, BlockIt MBBI) {
240   MachineInstr &MI = *MBBI;
241   Register DstLoReg, DstHiReg;
242   Register DstReg = MI.getOperand(0).getReg();
243   bool DstIsDead = MI.getOperand(0).isDead();
244   bool SrcIsKill = MI.getOperand(1).isKill();
245   bool ImpIsDead = MI.getOperand(3).isDead();
246   unsigned Imm = MI.getOperand(2).getImm();
247   unsigned Lo8 = Imm & 0xff;
248   unsigned Hi8 = (Imm >> 8) & 0xff;
249   TRI->splitReg(DstReg, DstLoReg, DstHiReg);
250 
251   if (!isLogicImmOpRedundant(Op, Lo8)) {
252     auto MIBLO =
253         buildMI(MBB, MBBI, Op)
254             .addReg(DstLoReg, RegState::Define | getDeadRegState(DstIsDead))
255             .addReg(DstLoReg, getKillRegState(SrcIsKill))
256             .addImm(Lo8);
257 
258     // SREG is always implicitly dead
259     MIBLO->getOperand(3).setIsDead();
260   }
261 
262   if (!isLogicImmOpRedundant(Op, Hi8)) {
263     auto MIBHI =
264         buildMI(MBB, MBBI, Op)
265             .addReg(DstHiReg, RegState::Define | getDeadRegState(DstIsDead))
266             .addReg(DstHiReg, getKillRegState(SrcIsKill))
267             .addImm(Hi8);
268 
269     if (ImpIsDead)
270       MIBHI->getOperand(3).setIsDead();
271   }
272 
273   MI.eraseFromParent();
274   return true;
275 }
276 
277 template <>
278 bool AVRExpandPseudo::expand<AVR::ADDWRdRr>(Block &MBB, BlockIt MBBI) {
279   return expandArith(AVR::ADDRdRr, AVR::ADCRdRr, MBB, MBBI);
280 }
281 
282 template <>
283 bool AVRExpandPseudo::expand<AVR::ADCWRdRr>(Block &MBB, BlockIt MBBI) {
284   return expandArith(AVR::ADCRdRr, AVR::ADCRdRr, MBB, MBBI);
285 }
286 
287 template <>
288 bool AVRExpandPseudo::expand<AVR::SUBWRdRr>(Block &MBB, BlockIt MBBI) {
289   return expandArith(AVR::SUBRdRr, AVR::SBCRdRr, MBB, MBBI);
290 }
291 
292 template <>
293 bool AVRExpandPseudo::expand<AVR::SUBIWRdK>(Block &MBB, BlockIt MBBI) {
294   MachineInstr &MI = *MBBI;
295   Register DstLoReg, DstHiReg;
296   Register DstReg = MI.getOperand(0).getReg();
297   bool DstIsDead = MI.getOperand(0).isDead();
298   bool SrcIsKill = MI.getOperand(1).isKill();
299   bool ImpIsDead = MI.getOperand(3).isDead();
300   TRI->splitReg(DstReg, DstLoReg, DstHiReg);
301 
302   auto MIBLO =
303       buildMI(MBB, MBBI, AVR::SUBIRdK)
304           .addReg(DstLoReg, RegState::Define | getDeadRegState(DstIsDead))
305           .addReg(DstLoReg, getKillRegState(SrcIsKill));
306 
307   auto MIBHI =
308       buildMI(MBB, MBBI, AVR::SBCIRdK)
309           .addReg(DstHiReg, RegState::Define | getDeadRegState(DstIsDead))
310           .addReg(DstHiReg, getKillRegState(SrcIsKill));
311 
312   switch (MI.getOperand(2).getType()) {
313   case MachineOperand::MO_GlobalAddress: {
314     const GlobalValue *GV = MI.getOperand(2).getGlobal();
315     int64_t Offs = MI.getOperand(2).getOffset();
316     unsigned TF = MI.getOperand(2).getTargetFlags();
317     MIBLO.addGlobalAddress(GV, Offs, TF | AVRII::MO_NEG | AVRII::MO_LO);
318     MIBHI.addGlobalAddress(GV, Offs, TF | AVRII::MO_NEG | AVRII::MO_HI);
319     break;
320   }
321   case MachineOperand::MO_Immediate: {
322     unsigned Imm = MI.getOperand(2).getImm();
323     MIBLO.addImm(Imm & 0xff);
324     MIBHI.addImm((Imm >> 8) & 0xff);
325     break;
326   }
327   default:
328     llvm_unreachable("Unknown operand type!");
329   }
330 
331   if (ImpIsDead)
332     MIBHI->getOperand(3).setIsDead();
333 
334   // SREG is always implicitly killed
335   MIBHI->getOperand(4).setIsKill();
336 
337   MI.eraseFromParent();
338   return true;
339 }
340 
341 template <>
342 bool AVRExpandPseudo::expand<AVR::SBCWRdRr>(Block &MBB, BlockIt MBBI) {
343   return expandArith(AVR::SBCRdRr, AVR::SBCRdRr, MBB, MBBI);
344 }
345 
346 template <>
347 bool AVRExpandPseudo::expand<AVR::SBCIWRdK>(Block &MBB, BlockIt MBBI) {
348   MachineInstr &MI = *MBBI;
349   Register DstLoReg, DstHiReg;
350   Register DstReg = MI.getOperand(0).getReg();
351   bool DstIsDead = MI.getOperand(0).isDead();
352   bool SrcIsKill = MI.getOperand(1).isKill();
353   bool ImpIsDead = MI.getOperand(3).isDead();
354   unsigned Imm = MI.getOperand(2).getImm();
355   unsigned Lo8 = Imm & 0xff;
356   unsigned Hi8 = (Imm >> 8) & 0xff;
357   unsigned OpLo = AVR::SBCIRdK;
358   unsigned OpHi = AVR::SBCIRdK;
359   TRI->splitReg(DstReg, DstLoReg, DstHiReg);
360 
361   auto MIBLO =
362       buildMI(MBB, MBBI, OpLo)
363           .addReg(DstLoReg, RegState::Define | getDeadRegState(DstIsDead))
364           .addReg(DstLoReg, getKillRegState(SrcIsKill))
365           .addImm(Lo8);
366 
367   // SREG is always implicitly killed
368   MIBLO->getOperand(4).setIsKill();
369 
370   auto MIBHI =
371       buildMI(MBB, MBBI, OpHi)
372           .addReg(DstHiReg, RegState::Define | getDeadRegState(DstIsDead))
373           .addReg(DstHiReg, getKillRegState(SrcIsKill))
374           .addImm(Hi8);
375 
376   if (ImpIsDead)
377     MIBHI->getOperand(3).setIsDead();
378 
379   // SREG is always implicitly killed
380   MIBHI->getOperand(4).setIsKill();
381 
382   MI.eraseFromParent();
383   return true;
384 }
385 
386 template <>
387 bool AVRExpandPseudo::expand<AVR::ANDWRdRr>(Block &MBB, BlockIt MBBI) {
388   return expandLogic(AVR::ANDRdRr, MBB, MBBI);
389 }
390 
391 template <>
392 bool AVRExpandPseudo::expand<AVR::ANDIWRdK>(Block &MBB, BlockIt MBBI) {
393   return expandLogicImm(AVR::ANDIRdK, MBB, MBBI);
394 }
395 
396 template <>
397 bool AVRExpandPseudo::expand<AVR::ORWRdRr>(Block &MBB, BlockIt MBBI) {
398   return expandLogic(AVR::ORRdRr, MBB, MBBI);
399 }
400 
401 template <>
402 bool AVRExpandPseudo::expand<AVR::ORIWRdK>(Block &MBB, BlockIt MBBI) {
403   return expandLogicImm(AVR::ORIRdK, MBB, MBBI);
404 }
405 
406 template <>
407 bool AVRExpandPseudo::expand<AVR::EORWRdRr>(Block &MBB, BlockIt MBBI) {
408   return expandLogic(AVR::EORRdRr, MBB, MBBI);
409 }
410 
411 template <>
412 bool AVRExpandPseudo::expand<AVR::COMWRd>(Block &MBB, BlockIt MBBI) {
413   MachineInstr &MI = *MBBI;
414   Register DstLoReg, DstHiReg;
415   Register DstReg = MI.getOperand(0).getReg();
416   bool DstIsDead = MI.getOperand(0).isDead();
417   bool DstIsKill = MI.getOperand(1).isKill();
418   bool ImpIsDead = MI.getOperand(2).isDead();
419   unsigned OpLo = AVR::COMRd;
420   unsigned OpHi = AVR::COMRd;
421   TRI->splitReg(DstReg, DstLoReg, DstHiReg);
422 
423   auto MIBLO =
424       buildMI(MBB, MBBI, OpLo)
425           .addReg(DstLoReg, RegState::Define | getDeadRegState(DstIsDead))
426           .addReg(DstLoReg, getKillRegState(DstIsKill));
427 
428   // SREG is always implicitly dead
429   MIBLO->getOperand(2).setIsDead();
430 
431   auto MIBHI =
432       buildMI(MBB, MBBI, OpHi)
433           .addReg(DstHiReg, RegState::Define | getDeadRegState(DstIsDead))
434           .addReg(DstHiReg, getKillRegState(DstIsKill));
435 
436   if (ImpIsDead)
437     MIBHI->getOperand(2).setIsDead();
438 
439   MI.eraseFromParent();
440   return true;
441 }
442 
443 template <>
444 bool AVRExpandPseudo::expand<AVR::NEGWRd>(Block &MBB, BlockIt MBBI) {
445   MachineInstr &MI = *MBBI;
446   Register DstLoReg, DstHiReg;
447   Register DstReg = MI.getOperand(0).getReg();
448   bool DstIsDead = MI.getOperand(0).isDead();
449   bool DstIsKill = MI.getOperand(1).isKill();
450   bool ImpIsDead = MI.getOperand(2).isDead();
451   TRI->splitReg(DstReg, DstLoReg, DstHiReg);
452 
453   // Do NEG on the upper byte.
454   auto MIBHI =
455       buildMI(MBB, MBBI, AVR::NEGRd)
456           .addReg(DstHiReg, RegState::Define | getDeadRegState(DstIsDead))
457           .addReg(DstHiReg, RegState::Kill);
458   // SREG is always implicitly dead
459   MIBHI->getOperand(2).setIsDead();
460 
461   // Do NEG on the lower byte.
462   buildMI(MBB, MBBI, AVR::NEGRd)
463       .addReg(DstLoReg, RegState::Define | getDeadRegState(DstIsDead))
464       .addReg(DstLoReg, getKillRegState(DstIsKill));
465 
466   // Do an extra SBC.
467   auto MISBCI =
468       buildMI(MBB, MBBI, AVR::SBCRdRr)
469           .addReg(DstHiReg, RegState::Define | getDeadRegState(DstIsDead))
470           .addReg(DstHiReg, getKillRegState(DstIsKill))
471           .addReg(ZERO_REGISTER);
472   if (ImpIsDead)
473     MISBCI->getOperand(3).setIsDead();
474   // SREG is always implicitly killed
475   MISBCI->getOperand(4).setIsKill();
476 
477   MI.eraseFromParent();
478   return true;
479 }
480 
481 template <>
482 bool AVRExpandPseudo::expand<AVR::CPWRdRr>(Block &MBB, BlockIt MBBI) {
483   MachineInstr &MI = *MBBI;
484   Register SrcLoReg, SrcHiReg, DstLoReg, DstHiReg;
485   Register DstReg = MI.getOperand(0).getReg();
486   Register SrcReg = MI.getOperand(1).getReg();
487   bool DstIsKill = MI.getOperand(0).isKill();
488   bool SrcIsKill = MI.getOperand(1).isKill();
489   bool ImpIsDead = MI.getOperand(2).isDead();
490   unsigned OpLo = AVR::CPRdRr;
491   unsigned OpHi = AVR::CPCRdRr;
492   TRI->splitReg(SrcReg, SrcLoReg, SrcHiReg);
493   TRI->splitReg(DstReg, DstLoReg, DstHiReg);
494 
495   // Low part
496   buildMI(MBB, MBBI, OpLo)
497       .addReg(DstLoReg, getKillRegState(DstIsKill))
498       .addReg(SrcLoReg, getKillRegState(SrcIsKill));
499 
500   auto MIBHI = buildMI(MBB, MBBI, OpHi)
501                    .addReg(DstHiReg, getKillRegState(DstIsKill))
502                    .addReg(SrcHiReg, getKillRegState(SrcIsKill));
503 
504   if (ImpIsDead)
505     MIBHI->getOperand(2).setIsDead();
506 
507   // SREG is always implicitly killed
508   MIBHI->getOperand(3).setIsKill();
509 
510   MI.eraseFromParent();
511   return true;
512 }
513 
514 template <>
515 bool AVRExpandPseudo::expand<AVR::CPCWRdRr>(Block &MBB, BlockIt MBBI) {
516   MachineInstr &MI = *MBBI;
517   Register SrcLoReg, SrcHiReg, DstLoReg, DstHiReg;
518   Register DstReg = MI.getOperand(0).getReg();
519   Register SrcReg = MI.getOperand(1).getReg();
520   bool DstIsKill = MI.getOperand(0).isKill();
521   bool SrcIsKill = MI.getOperand(1).isKill();
522   bool ImpIsDead = MI.getOperand(2).isDead();
523   unsigned OpLo = AVR::CPCRdRr;
524   unsigned OpHi = AVR::CPCRdRr;
525   TRI->splitReg(SrcReg, SrcLoReg, SrcHiReg);
526   TRI->splitReg(DstReg, DstLoReg, DstHiReg);
527 
528   auto MIBLO = buildMI(MBB, MBBI, OpLo)
529                    .addReg(DstLoReg, getKillRegState(DstIsKill))
530                    .addReg(SrcLoReg, getKillRegState(SrcIsKill));
531 
532   // SREG is always implicitly killed
533   MIBLO->getOperand(3).setIsKill();
534 
535   auto MIBHI = buildMI(MBB, MBBI, OpHi)
536                    .addReg(DstHiReg, getKillRegState(DstIsKill))
537                    .addReg(SrcHiReg, getKillRegState(SrcIsKill));
538 
539   if (ImpIsDead)
540     MIBHI->getOperand(2).setIsDead();
541 
542   // SREG is always implicitly killed
543   MIBHI->getOperand(3).setIsKill();
544 
545   MI.eraseFromParent();
546   return true;
547 }
548 
549 template <>
550 bool AVRExpandPseudo::expand<AVR::LDIWRdK>(Block &MBB, BlockIt MBBI) {
551   MachineInstr &MI = *MBBI;
552   Register DstLoReg, DstHiReg;
553   Register DstReg = MI.getOperand(0).getReg();
554   bool DstIsDead = MI.getOperand(0).isDead();
555   unsigned OpLo = AVR::LDIRdK;
556   unsigned OpHi = AVR::LDIRdK;
557   TRI->splitReg(DstReg, DstLoReg, DstHiReg);
558 
559   auto MIBLO =
560       buildMI(MBB, MBBI, OpLo)
561           .addReg(DstLoReg, RegState::Define | getDeadRegState(DstIsDead));
562 
563   auto MIBHI =
564       buildMI(MBB, MBBI, OpHi)
565           .addReg(DstHiReg, RegState::Define | getDeadRegState(DstIsDead));
566 
567   switch (MI.getOperand(1).getType()) {
568   case MachineOperand::MO_GlobalAddress: {
569     const GlobalValue *GV = MI.getOperand(1).getGlobal();
570     int64_t Offs = MI.getOperand(1).getOffset();
571     unsigned TF = MI.getOperand(1).getTargetFlags();
572 
573     MIBLO.addGlobalAddress(GV, Offs, TF | AVRII::MO_LO);
574     MIBHI.addGlobalAddress(GV, Offs, TF | AVRII::MO_HI);
575     break;
576   }
577   case MachineOperand::MO_BlockAddress: {
578     const BlockAddress *BA = MI.getOperand(1).getBlockAddress();
579     unsigned TF = MI.getOperand(1).getTargetFlags();
580 
581     MIBLO.add(MachineOperand::CreateBA(BA, TF | AVRII::MO_LO));
582     MIBHI.add(MachineOperand::CreateBA(BA, TF | AVRII::MO_HI));
583     break;
584   }
585   case MachineOperand::MO_Immediate: {
586     unsigned Imm = MI.getOperand(1).getImm();
587 
588     MIBLO.addImm(Imm & 0xff);
589     MIBHI.addImm((Imm >> 8) & 0xff);
590     break;
591   }
592   default:
593     llvm_unreachable("Unknown operand type!");
594   }
595 
596   MI.eraseFromParent();
597   return true;
598 }
599 
600 template <>
601 bool AVRExpandPseudo::expand<AVR::LDSWRdK>(Block &MBB, BlockIt MBBI) {
602   MachineInstr &MI = *MBBI;
603   Register DstLoReg, DstHiReg;
604   Register DstReg = MI.getOperand(0).getReg();
605   bool DstIsDead = MI.getOperand(0).isDead();
606   unsigned OpLo = AVR::LDSRdK;
607   unsigned OpHi = AVR::LDSRdK;
608   TRI->splitReg(DstReg, DstLoReg, DstHiReg);
609 
610   auto MIBLO =
611       buildMI(MBB, MBBI, OpLo)
612           .addReg(DstLoReg, RegState::Define | getDeadRegState(DstIsDead));
613 
614   auto MIBHI =
615       buildMI(MBB, MBBI, OpHi)
616           .addReg(DstHiReg, RegState::Define | getDeadRegState(DstIsDead));
617 
618   switch (MI.getOperand(1).getType()) {
619   case MachineOperand::MO_GlobalAddress: {
620     const GlobalValue *GV = MI.getOperand(1).getGlobal();
621     int64_t Offs = MI.getOperand(1).getOffset();
622     unsigned TF = MI.getOperand(1).getTargetFlags();
623 
624     MIBLO.addGlobalAddress(GV, Offs, TF);
625     MIBHI.addGlobalAddress(GV, Offs + 1, TF);
626     break;
627   }
628   case MachineOperand::MO_Immediate: {
629     unsigned Imm = MI.getOperand(1).getImm();
630 
631     MIBLO.addImm(Imm);
632     MIBHI.addImm(Imm + 1);
633     break;
634   }
635   default:
636     llvm_unreachable("Unknown operand type!");
637   }
638 
639   MIBLO.setMemRefs(MI.memoperands());
640   MIBHI.setMemRefs(MI.memoperands());
641 
642   MI.eraseFromParent();
643   return true;
644 }
645 
646 template <>
647 bool AVRExpandPseudo::expand<AVR::LDWRdPtr>(Block &MBB, BlockIt MBBI) {
648   MachineInstr &MI = *MBBI;
649   Register DstLoReg, DstHiReg;
650   Register DstReg = MI.getOperand(0).getReg();
651   Register TmpReg = 0; // 0 for no temporary register
652   Register SrcReg = MI.getOperand(1).getReg();
653   bool SrcIsKill = MI.getOperand(1).isKill();
654   unsigned OpLo = AVR::LDRdPtr;
655   unsigned OpHi = AVR::LDDRdPtrQ;
656   TRI->splitReg(DstReg, DstLoReg, DstHiReg);
657 
658   // Use a temporary register if src and dst registers are the same.
659   if (DstReg == SrcReg)
660     TmpReg = scavengeGPR8(MI);
661 
662   Register CurDstLoReg = (DstReg == SrcReg) ? TmpReg : DstLoReg;
663   Register CurDstHiReg = (DstReg == SrcReg) ? TmpReg : DstHiReg;
664 
665   // Load low byte.
666   auto MIBLO = buildMI(MBB, MBBI, OpLo)
667                    .addReg(CurDstLoReg, RegState::Define)
668                    .addReg(SrcReg);
669 
670   // Push low byte onto stack if necessary.
671   if (TmpReg)
672     buildMI(MBB, MBBI, AVR::PUSHRr).addReg(TmpReg);
673 
674   // Load high byte.
675   auto MIBHI = buildMI(MBB, MBBI, OpHi)
676                    .addReg(CurDstHiReg, RegState::Define)
677                    .addReg(SrcReg, getKillRegState(SrcIsKill))
678                    .addImm(1);
679 
680   if (TmpReg) {
681     // Move the high byte into the final destination.
682     buildMI(MBB, MBBI, AVR::MOVRdRr, DstHiReg).addReg(TmpReg);
683 
684     // Move the low byte from the scratch space into the final destination.
685     buildMI(MBB, MBBI, AVR::POPRd, DstLoReg);
686   }
687 
688   MIBLO.setMemRefs(MI.memoperands());
689   MIBHI.setMemRefs(MI.memoperands());
690 
691   MI.eraseFromParent();
692   return true;
693 }
694 
695 template <>
696 bool AVRExpandPseudo::expand<AVR::LDWRdPtrPi>(Block &MBB, BlockIt MBBI) {
697   MachineInstr &MI = *MBBI;
698   Register DstLoReg, DstHiReg;
699   Register DstReg = MI.getOperand(0).getReg();
700   Register SrcReg = MI.getOperand(1).getReg();
701   bool DstIsDead = MI.getOperand(0).isDead();
702   bool SrcIsDead = MI.getOperand(1).isKill();
703   unsigned OpLo = AVR::LDRdPtrPi;
704   unsigned OpHi = AVR::LDRdPtrPi;
705   TRI->splitReg(DstReg, DstLoReg, DstHiReg);
706 
707   assert(DstReg != SrcReg && "SrcReg and DstReg cannot be the same");
708 
709   auto MIBLO =
710       buildMI(MBB, MBBI, OpLo)
711           .addReg(DstLoReg, RegState::Define | getDeadRegState(DstIsDead))
712           .addReg(SrcReg, RegState::Define)
713           .addReg(SrcReg, RegState::Kill);
714 
715   auto MIBHI =
716       buildMI(MBB, MBBI, OpHi)
717           .addReg(DstHiReg, 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::LDWRdPtrPd>(Block &MBB, BlockIt MBBI) {
730   MachineInstr &MI = *MBBI;
731   Register DstLoReg, DstHiReg;
732   Register DstReg = MI.getOperand(0).getReg();
733   Register SrcReg = MI.getOperand(1).getReg();
734   bool DstIsDead = MI.getOperand(0).isDead();
735   bool SrcIsDead = MI.getOperand(1).isKill();
736   unsigned OpLo = AVR::LDRdPtrPd;
737   unsigned OpHi = AVR::LDRdPtrPd;
738   TRI->splitReg(DstReg, DstLoReg, DstHiReg);
739 
740   assert(DstReg != SrcReg && "SrcReg and DstReg cannot be the same");
741 
742   auto MIBHI =
743       buildMI(MBB, MBBI, OpHi)
744           .addReg(DstHiReg, RegState::Define | getDeadRegState(DstIsDead))
745           .addReg(SrcReg, RegState::Define)
746           .addReg(SrcReg, RegState::Kill);
747 
748   auto MIBLO =
749       buildMI(MBB, MBBI, OpLo)
750           .addReg(DstLoReg, RegState::Define | getDeadRegState(DstIsDead))
751           .addReg(SrcReg, RegState::Define | getDeadRegState(SrcIsDead))
752           .addReg(SrcReg, RegState::Kill);
753 
754   MIBLO.setMemRefs(MI.memoperands());
755   MIBHI.setMemRefs(MI.memoperands());
756 
757   MI.eraseFromParent();
758   return true;
759 }
760 
761 template <>
762 bool AVRExpandPseudo::expand<AVR::LDDWRdPtrQ>(Block &MBB, BlockIt MBBI) {
763   MachineInstr &MI = *MBBI;
764   Register DstLoReg, DstHiReg;
765   Register DstReg = MI.getOperand(0).getReg();
766   Register TmpReg = 0; // 0 for no temporary register
767   Register SrcReg = MI.getOperand(1).getReg();
768   unsigned Imm = MI.getOperand(2).getImm();
769   bool SrcIsKill = MI.getOperand(1).isKill();
770   unsigned OpLo = AVR::LDDRdPtrQ;
771   unsigned OpHi = AVR::LDDRdPtrQ;
772   TRI->splitReg(DstReg, DstLoReg, DstHiReg);
773 
774   // Since we add 1 to the Imm value for the high byte below, and 63 is the
775   // highest Imm value allowed for the instruction, 62 is the limit here.
776   assert(Imm <= 62 && "Offset is out of range");
777 
778   // Use a temporary register if src and dst registers are the same.
779   if (DstReg == SrcReg)
780     TmpReg = scavengeGPR8(MI);
781 
782   Register CurDstLoReg = (DstReg == SrcReg) ? TmpReg : DstLoReg;
783   Register CurDstHiReg = (DstReg == SrcReg) ? TmpReg : DstHiReg;
784 
785   // Load low byte.
786   auto MIBLO = buildMI(MBB, MBBI, OpLo)
787                    .addReg(CurDstLoReg, RegState::Define)
788                    .addReg(SrcReg)
789                    .addImm(Imm);
790 
791   // Push low byte onto stack if necessary.
792   if (TmpReg)
793     buildMI(MBB, MBBI, AVR::PUSHRr).addReg(TmpReg);
794 
795   // Load high byte.
796   auto MIBHI = buildMI(MBB, MBBI, OpHi)
797                    .addReg(CurDstHiReg, RegState::Define)
798                    .addReg(SrcReg, getKillRegState(SrcIsKill))
799                    .addImm(Imm + 1);
800 
801   if (TmpReg) {
802     // Move the high byte into the final destination.
803     buildMI(MBB, MBBI, AVR::MOVRdRr, DstHiReg).addReg(TmpReg);
804 
805     // Move the low byte from the scratch space into the final destination.
806     buildMI(MBB, MBBI, AVR::POPRd, DstLoReg);
807   }
808 
809   MIBLO.setMemRefs(MI.memoperands());
810   MIBHI.setMemRefs(MI.memoperands());
811 
812   MI.eraseFromParent();
813   return true;
814 }
815 
816 bool AVRExpandPseudo::expandLPMWELPMW(Block &MBB, BlockIt MBBI, bool IsExt) {
817   MachineInstr &MI = *MBBI;
818   Register DstLoReg, DstHiReg;
819   Register DstReg = MI.getOperand(0).getReg();
820   Register TmpReg = 0; // 0 for no temporary register
821   Register SrcReg = MI.getOperand(1).getReg();
822   bool SrcIsKill = MI.getOperand(1).isKill();
823   unsigned OpLo = IsExt ? AVR::ELPMRdZPi : AVR::LPMRdZPi;
824   unsigned OpHi = IsExt ? AVR::ELPMRdZ : AVR::LPMRdZ;
825   TRI->splitReg(DstReg, DstLoReg, DstHiReg);
826 
827   // Set the I/O register RAMPZ for ELPM.
828   if (IsExt) {
829     const AVRSubtarget &STI = MBB.getParent()->getSubtarget<AVRSubtarget>();
830     Register Bank = MI.getOperand(2).getReg();
831     // out RAMPZ, rtmp
832     buildMI(MBB, MBBI, AVR::OUTARr).addImm(STI.getIORegRAMPZ()).addReg(Bank);
833   }
834 
835   // Use a temporary register if src and dst registers are the same.
836   if (DstReg == SrcReg)
837     TmpReg = scavengeGPR8(MI);
838 
839   Register CurDstLoReg = (DstReg == SrcReg) ? TmpReg : DstLoReg;
840   Register CurDstHiReg = (DstReg == SrcReg) ? TmpReg : DstHiReg;
841 
842   // Load low byte.
843   auto MIBLO = buildMI(MBB, MBBI, OpLo)
844                    .addReg(CurDstLoReg, RegState::Define)
845                    .addReg(SrcReg);
846 
847   // Push low byte onto stack if necessary.
848   if (TmpReg)
849     buildMI(MBB, MBBI, AVR::PUSHRr).addReg(TmpReg);
850 
851   // Load high byte.
852   auto MIBHI = buildMI(MBB, MBBI, OpHi)
853                    .addReg(CurDstHiReg, RegState::Define)
854                    .addReg(SrcReg, getKillRegState(SrcIsKill));
855 
856   if (TmpReg) {
857     // Move the high byte into the final destination.
858     buildMI(MBB, MBBI, AVR::MOVRdRr, DstHiReg).addReg(TmpReg);
859 
860     // Move the low byte from the scratch space into the final destination.
861     buildMI(MBB, MBBI, AVR::POPRd, DstLoReg);
862   }
863 
864   MIBLO.setMemRefs(MI.memoperands());
865   MIBHI.setMemRefs(MI.memoperands());
866 
867   MI.eraseFromParent();
868   return true;
869 }
870 
871 template <>
872 bool AVRExpandPseudo::expand<AVR::LPMWRdZ>(Block &MBB, BlockIt MBBI) {
873   return expandLPMWELPMW(MBB, MBBI, false);
874 }
875 
876 template <>
877 bool AVRExpandPseudo::expand<AVR::ELPMWRdZ>(Block &MBB, BlockIt MBBI) {
878   return expandLPMWELPMW(MBB, MBBI, true);
879 }
880 
881 template <>
882 bool AVRExpandPseudo::expand<AVR::ELPMBRdZ>(Block &MBB, BlockIt MBBI) {
883   MachineInstr &MI = *MBBI;
884   Register DstReg = MI.getOperand(0).getReg();
885   Register SrcReg = MI.getOperand(1).getReg();
886   Register BankReg = MI.getOperand(2).getReg();
887   bool SrcIsKill = MI.getOperand(1).isKill();
888   const AVRSubtarget &STI = MBB.getParent()->getSubtarget<AVRSubtarget>();
889 
890   // Set the I/O register RAMPZ for ELPM (out RAMPZ, rtmp).
891   buildMI(MBB, MBBI, AVR::OUTARr).addImm(STI.getIORegRAMPZ()).addReg(BankReg);
892 
893   // Load byte.
894   auto MILB = buildMI(MBB, MBBI, AVR::ELPMRdZ)
895                   .addReg(DstReg, RegState::Define)
896                   .addReg(SrcReg, getKillRegState(SrcIsKill));
897 
898   MILB.setMemRefs(MI.memoperands());
899 
900   MI.eraseFromParent();
901   return true;
902 }
903 
904 template <>
905 bool AVRExpandPseudo::expand<AVR::LPMWRdZPi>(Block &MBB, BlockIt MBBI) {
906   llvm_unreachable("16-bit LPMPi is unimplemented");
907 }
908 
909 template <>
910 bool AVRExpandPseudo::expand<AVR::ELPMBRdZPi>(Block &MBB, BlockIt MBBI) {
911   llvm_unreachable("byte ELPMPi is unimplemented");
912 }
913 
914 template <>
915 bool AVRExpandPseudo::expand<AVR::ELPMWRdZPi>(Block &MBB, BlockIt MBBI) {
916   llvm_unreachable("16-bit ELPMPi is unimplemented");
917 }
918 
919 template <typename Func>
920 bool AVRExpandPseudo::expandAtomic(Block &MBB, BlockIt MBBI, Func f) {
921   MachineInstr &MI = *MBBI;
922   const AVRSubtarget &STI = MBB.getParent()->getSubtarget<AVRSubtarget>();
923 
924   // Store the SREG.
925   buildMI(MBB, MBBI, AVR::INRdA)
926       .addReg(SCRATCH_REGISTER, RegState::Define)
927       .addImm(STI.getIORegSREG());
928 
929   // Disable exceptions.
930   buildMI(MBB, MBBI, AVR::BCLRs).addImm(7); // CLI
931 
932   f(MI);
933 
934   // Restore the status reg.
935   buildMI(MBB, MBBI, AVR::OUTARr)
936       .addImm(STI.getIORegSREG())
937       .addReg(SCRATCH_REGISTER);
938 
939   MI.eraseFromParent();
940   return true;
941 }
942 
943 template <typename Func>
944 bool AVRExpandPseudo::expandAtomicBinaryOp(unsigned Opcode, Block &MBB,
945                                            BlockIt MBBI, Func f) {
946   return expandAtomic(MBB, MBBI, [&](MachineInstr &MI) {
947     auto Op1 = MI.getOperand(0);
948     auto Op2 = MI.getOperand(1);
949 
950     MachineInstr &NewInst =
951         *buildMI(MBB, MBBI, Opcode).add(Op1).add(Op2).getInstr();
952     f(NewInst);
953   });
954 }
955 
956 bool AVRExpandPseudo::expandAtomicBinaryOp(unsigned Opcode, Block &MBB,
957                                            BlockIt MBBI) {
958   return expandAtomicBinaryOp(Opcode, MBB, MBBI, [](MachineInstr &MI) {});
959 }
960 
961 Register AVRExpandPseudo::scavengeGPR8(MachineInstr &MI) {
962   MachineBasicBlock &MBB = *MI.getParent();
963   RegScavenger RS;
964 
965   RS.enterBasicBlock(MBB);
966   RS.forward(MI);
967 
968   BitVector Candidates =
969       TRI->getAllocatableSet(*MBB.getParent(), &AVR::GPR8RegClass);
970 
971   // Exclude all the registers being used by the instruction.
972   for (MachineOperand &MO : MI.operands()) {
973     if (MO.isReg() && MO.getReg() != 0 && !MO.isDef() &&
974         !Register::isVirtualRegister(MO.getReg()))
975       Candidates.reset(MO.getReg());
976   }
977 
978   BitVector Available = RS.getRegsAvailable(&AVR::GPR8RegClass);
979   Available &= Candidates;
980 
981   signed Reg = Available.find_first();
982   assert(Reg != -1 && "ran out of registers");
983   return Reg;
984 }
985 
986 template <>
987 bool AVRExpandPseudo::expand<AVR::AtomicLoad8>(Block &MBB, BlockIt MBBI) {
988   return expandAtomicBinaryOp(AVR::LDRdPtr, MBB, MBBI);
989 }
990 
991 template <>
992 bool AVRExpandPseudo::expand<AVR::AtomicLoad16>(Block &MBB, BlockIt MBBI) {
993   return expandAtomicBinaryOp(AVR::LDWRdPtr, MBB, MBBI);
994 }
995 
996 template <>
997 bool AVRExpandPseudo::expand<AVR::AtomicStore8>(Block &MBB, BlockIt MBBI) {
998   return expandAtomicBinaryOp(AVR::STPtrRr, MBB, MBBI);
999 }
1000 
1001 template <>
1002 bool AVRExpandPseudo::expand<AVR::AtomicStore16>(Block &MBB, BlockIt MBBI) {
1003   return expandAtomicBinaryOp(AVR::STWPtrRr, MBB, MBBI);
1004 }
1005 
1006 template <>
1007 bool AVRExpandPseudo::expand<AVR::AtomicFence>(Block &MBB, BlockIt MBBI) {
1008   // On AVR, there is only one core and so atomic fences do nothing.
1009   MBBI->eraseFromParent();
1010   return true;
1011 }
1012 
1013 template <>
1014 bool AVRExpandPseudo::expand<AVR::STSWKRr>(Block &MBB, BlockIt MBBI) {
1015   MachineInstr &MI = *MBBI;
1016   Register SrcLoReg, SrcHiReg;
1017   Register SrcReg = MI.getOperand(1).getReg();
1018   bool SrcIsKill = MI.getOperand(1).isKill();
1019   unsigned OpLo = AVR::STSKRr;
1020   unsigned OpHi = AVR::STSKRr;
1021   TRI->splitReg(SrcReg, SrcLoReg, SrcHiReg);
1022 
1023   // Write the high byte first in case this address belongs to a special
1024   // I/O address with a special temporary register.
1025   auto MIBHI = buildMI(MBB, MBBI, OpHi);
1026   auto MIBLO = buildMI(MBB, MBBI, OpLo);
1027 
1028   switch (MI.getOperand(0).getType()) {
1029   case MachineOperand::MO_GlobalAddress: {
1030     const GlobalValue *GV = MI.getOperand(0).getGlobal();
1031     int64_t Offs = MI.getOperand(0).getOffset();
1032     unsigned TF = MI.getOperand(0).getTargetFlags();
1033 
1034     MIBLO.addGlobalAddress(GV, Offs, TF);
1035     MIBHI.addGlobalAddress(GV, Offs + 1, TF);
1036     break;
1037   }
1038   case MachineOperand::MO_Immediate: {
1039     unsigned Imm = MI.getOperand(0).getImm();
1040 
1041     MIBLO.addImm(Imm);
1042     MIBHI.addImm(Imm + 1);
1043     break;
1044   }
1045   default:
1046     llvm_unreachable("Unknown operand type!");
1047   }
1048 
1049   MIBLO.addReg(SrcLoReg, getKillRegState(SrcIsKill));
1050   MIBHI.addReg(SrcHiReg, getKillRegState(SrcIsKill));
1051 
1052   MIBLO.setMemRefs(MI.memoperands());
1053   MIBHI.setMemRefs(MI.memoperands());
1054 
1055   MI.eraseFromParent();
1056   return true;
1057 }
1058 
1059 template <>
1060 bool AVRExpandPseudo::expand<AVR::STWPtrRr>(Block &MBB, BlockIt MBBI) {
1061   MachineInstr &MI = *MBBI;
1062   Register SrcLoReg, SrcHiReg;
1063   Register DstReg = MI.getOperand(0).getReg();
1064   Register SrcReg = MI.getOperand(1).getReg();
1065   bool DstIsUndef = MI.getOperand(0).isUndef();
1066   bool SrcIsKill = MI.getOperand(1).isKill();
1067   unsigned OpLo = AVR::STPtrRr;
1068   unsigned OpHi = AVR::STDPtrQRr;
1069   TRI->splitReg(SrcReg, SrcLoReg, SrcHiReg);
1070 
1071   //: TODO: need to reverse this order like inw and stsw?
1072   auto MIBLO = buildMI(MBB, MBBI, OpLo)
1073                    .addReg(DstReg, getUndefRegState(DstIsUndef))
1074                    .addReg(SrcLoReg, getKillRegState(SrcIsKill));
1075 
1076   auto MIBHI = buildMI(MBB, MBBI, OpHi)
1077                    .addReg(DstReg, getUndefRegState(DstIsUndef))
1078                    .addImm(1)
1079                    .addReg(SrcHiReg, getKillRegState(SrcIsKill));
1080 
1081   MIBLO.setMemRefs(MI.memoperands());
1082   MIBHI.setMemRefs(MI.memoperands());
1083 
1084   MI.eraseFromParent();
1085   return true;
1086 }
1087 
1088 template <>
1089 bool AVRExpandPseudo::expand<AVR::STWPtrPiRr>(Block &MBB, BlockIt MBBI) {
1090   MachineInstr &MI = *MBBI;
1091   Register SrcLoReg, SrcHiReg;
1092   Register DstReg = MI.getOperand(0).getReg();
1093   Register SrcReg = MI.getOperand(2).getReg();
1094   unsigned Imm = MI.getOperand(3).getImm();
1095   bool DstIsDead = MI.getOperand(0).isDead();
1096   bool SrcIsKill = MI.getOperand(2).isKill();
1097   unsigned OpLo = AVR::STPtrPiRr;
1098   unsigned OpHi = AVR::STPtrPiRr;
1099   TRI->splitReg(SrcReg, SrcLoReg, SrcHiReg);
1100 
1101   assert(DstReg != SrcReg && "SrcReg and DstReg cannot be the same");
1102 
1103   auto MIBLO = buildMI(MBB, MBBI, OpLo)
1104                    .addReg(DstReg, RegState::Define)
1105                    .addReg(DstReg, RegState::Kill)
1106                    .addReg(SrcLoReg, getKillRegState(SrcIsKill))
1107                    .addImm(Imm);
1108 
1109   auto MIBHI =
1110       buildMI(MBB, MBBI, OpHi)
1111           .addReg(DstReg, RegState::Define | getDeadRegState(DstIsDead))
1112           .addReg(DstReg, RegState::Kill)
1113           .addReg(SrcHiReg, getKillRegState(SrcIsKill))
1114           .addImm(Imm);
1115 
1116   MIBLO.setMemRefs(MI.memoperands());
1117   MIBHI.setMemRefs(MI.memoperands());
1118 
1119   MI.eraseFromParent();
1120   return true;
1121 }
1122 
1123 template <>
1124 bool AVRExpandPseudo::expand<AVR::STWPtrPdRr>(Block &MBB, BlockIt MBBI) {
1125   MachineInstr &MI = *MBBI;
1126   Register SrcLoReg, SrcHiReg;
1127   Register DstReg = MI.getOperand(0).getReg();
1128   Register SrcReg = MI.getOperand(2).getReg();
1129   unsigned Imm = MI.getOperand(3).getImm();
1130   bool DstIsDead = MI.getOperand(0).isDead();
1131   bool SrcIsKill = MI.getOperand(2).isKill();
1132   unsigned OpLo = AVR::STPtrPdRr;
1133   unsigned OpHi = AVR::STPtrPdRr;
1134   TRI->splitReg(SrcReg, SrcLoReg, SrcHiReg);
1135 
1136   assert(DstReg != SrcReg && "SrcReg and DstReg cannot be the same");
1137 
1138   auto MIBHI = buildMI(MBB, MBBI, OpHi)
1139                    .addReg(DstReg, RegState::Define)
1140                    .addReg(DstReg, RegState::Kill)
1141                    .addReg(SrcHiReg, getKillRegState(SrcIsKill))
1142                    .addImm(Imm);
1143 
1144   auto MIBLO =
1145       buildMI(MBB, MBBI, OpLo)
1146           .addReg(DstReg, RegState::Define | getDeadRegState(DstIsDead))
1147           .addReg(DstReg, RegState::Kill)
1148           .addReg(SrcLoReg, getKillRegState(SrcIsKill))
1149           .addImm(Imm);
1150 
1151   MIBLO.setMemRefs(MI.memoperands());
1152   MIBHI.setMemRefs(MI.memoperands());
1153 
1154   MI.eraseFromParent();
1155   return true;
1156 }
1157 
1158 template <>
1159 bool AVRExpandPseudo::expand<AVR::STDWPtrQRr>(Block &MBB, BlockIt MBBI) {
1160   MachineInstr &MI = *MBBI;
1161 
1162   Register DstReg = MI.getOperand(0).getReg();
1163   bool DstIsKill = MI.getOperand(0).isKill();
1164   unsigned Imm = MI.getOperand(1).getImm();
1165   Register SrcReg = MI.getOperand(2).getReg();
1166   bool SrcIsKill = MI.getOperand(2).isKill();
1167 
1168   // STD's maximum displacement is 63, so larger stores have to be split into a
1169   // set of operations
1170   if (Imm >= 63) {
1171     if (!DstIsKill) {
1172       buildMI(MBB, MBBI, AVR::PUSHWRr).addReg(DstReg);
1173     }
1174 
1175     buildMI(MBB, MBBI, AVR::SUBIWRdK)
1176         .addReg(DstReg, RegState::Define)
1177         .addReg(DstReg, RegState::Kill)
1178         .addImm(-Imm);
1179 
1180     buildMI(MBB, MBBI, AVR::STWPtrRr)
1181         .addReg(DstReg, RegState::Kill)
1182         .addReg(SrcReg, getKillRegState(SrcIsKill));
1183 
1184     if (!DstIsKill) {
1185       buildMI(MBB, MBBI, AVR::POPWRd).addDef(DstReg, RegState::Define);
1186     }
1187   } else {
1188     unsigned OpLo = AVR::STDPtrQRr;
1189     unsigned OpHi = AVR::STDPtrQRr;
1190     Register SrcLoReg, SrcHiReg;
1191     TRI->splitReg(SrcReg, SrcLoReg, SrcHiReg);
1192 
1193     auto MIBLO = buildMI(MBB, MBBI, OpLo)
1194                      .addReg(DstReg)
1195                      .addImm(Imm)
1196                      .addReg(SrcLoReg, getKillRegState(SrcIsKill));
1197 
1198     auto MIBHI = buildMI(MBB, MBBI, OpHi)
1199                      .addReg(DstReg, getKillRegState(DstIsKill))
1200                      .addImm(Imm + 1)
1201                      .addReg(SrcHiReg, getKillRegState(SrcIsKill));
1202 
1203     MIBLO.setMemRefs(MI.memoperands());
1204     MIBHI.setMemRefs(MI.memoperands());
1205   }
1206 
1207   MI.eraseFromParent();
1208   return true;
1209 }
1210 
1211 template <>
1212 bool AVRExpandPseudo::expand<AVR::STDSPQRr>(Block &MBB, BlockIt MBBI) {
1213   MachineInstr &MI = *MBBI;
1214   const MachineFunction &MF = *MBB.getParent();
1215   const AVRSubtarget &STI = MF.getSubtarget<AVRSubtarget>();
1216 
1217   assert(MI.getOperand(0).getReg() == AVR::SP &&
1218          "SP is expected as base pointer");
1219 
1220   assert(STI.getFrameLowering()->hasReservedCallFrame(MF) &&
1221          "unexpected STDSPQRr pseudo instruction");
1222   (void)STI;
1223 
1224   MI.setDesc(TII->get(AVR::STDPtrQRr));
1225   MI.getOperand(0).setReg(AVR::R29R28);
1226 
1227   return true;
1228 }
1229 
1230 template <>
1231 bool AVRExpandPseudo::expand<AVR::STDWSPQRr>(Block &MBB, BlockIt MBBI) {
1232   MachineInstr &MI = *MBBI;
1233   const MachineFunction &MF = *MBB.getParent();
1234   const AVRSubtarget &STI = MF.getSubtarget<AVRSubtarget>();
1235 
1236   assert(MI.getOperand(0).getReg() == AVR::SP &&
1237          "SP is expected as base pointer");
1238 
1239   assert(STI.getFrameLowering()->hasReservedCallFrame(MF) &&
1240          "unexpected STDWSPQRr pseudo instruction");
1241   (void)STI;
1242 
1243   MI.setDesc(TII->get(AVR::STDWPtrQRr));
1244   MI.getOperand(0).setReg(AVR::R29R28);
1245 
1246   return true;
1247 }
1248 
1249 template <>
1250 bool AVRExpandPseudo::expand<AVR::INWRdA>(Block &MBB, BlockIt MBBI) {
1251   MachineInstr &MI = *MBBI;
1252   Register DstLoReg, DstHiReg;
1253   unsigned Imm = MI.getOperand(1).getImm();
1254   Register DstReg = MI.getOperand(0).getReg();
1255   bool DstIsDead = MI.getOperand(0).isDead();
1256   unsigned OpLo = AVR::INRdA;
1257   unsigned OpHi = AVR::INRdA;
1258   TRI->splitReg(DstReg, DstLoReg, DstHiReg);
1259 
1260   // Since we add 1 to the Imm value for the high byte below, and 63 is the
1261   // highest Imm value allowed for the instruction, 62 is the limit here.
1262   assert(Imm <= 62 && "Address is out of range");
1263 
1264   auto MIBLO =
1265       buildMI(MBB, MBBI, OpLo)
1266           .addReg(DstLoReg, RegState::Define | getDeadRegState(DstIsDead))
1267           .addImm(Imm);
1268 
1269   auto MIBHI =
1270       buildMI(MBB, MBBI, OpHi)
1271           .addReg(DstHiReg, RegState::Define | getDeadRegState(DstIsDead))
1272           .addImm(Imm + 1);
1273 
1274   MIBLO.setMemRefs(MI.memoperands());
1275   MIBHI.setMemRefs(MI.memoperands());
1276 
1277   MI.eraseFromParent();
1278   return true;
1279 }
1280 
1281 template <>
1282 bool AVRExpandPseudo::expand<AVR::OUTWARr>(Block &MBB, BlockIt MBBI) {
1283   MachineInstr &MI = *MBBI;
1284   Register SrcLoReg, SrcHiReg;
1285   unsigned Imm = MI.getOperand(0).getImm();
1286   Register SrcReg = MI.getOperand(1).getReg();
1287   bool SrcIsKill = MI.getOperand(1).isKill();
1288   unsigned OpLo = AVR::OUTARr;
1289   unsigned OpHi = AVR::OUTARr;
1290   TRI->splitReg(SrcReg, SrcLoReg, SrcHiReg);
1291 
1292   // Since we add 1 to the Imm value for the high byte below, and 63 is the
1293   // highest Imm value allowed for the instruction, 62 is the limit here.
1294   assert(Imm <= 62 && "Address is out of range");
1295 
1296   // 16 bit I/O writes need the high byte first
1297   auto MIBHI = buildMI(MBB, MBBI, OpHi)
1298                    .addImm(Imm + 1)
1299                    .addReg(SrcHiReg, getKillRegState(SrcIsKill));
1300 
1301   auto MIBLO = buildMI(MBB, MBBI, OpLo)
1302                    .addImm(Imm)
1303                    .addReg(SrcLoReg, getKillRegState(SrcIsKill));
1304 
1305   MIBLO.setMemRefs(MI.memoperands());
1306   MIBHI.setMemRefs(MI.memoperands());
1307 
1308   MI.eraseFromParent();
1309   return true;
1310 }
1311 
1312 template <>
1313 bool AVRExpandPseudo::expand<AVR::PUSHWRr>(Block &MBB, BlockIt MBBI) {
1314   MachineInstr &MI = *MBBI;
1315   Register SrcLoReg, SrcHiReg;
1316   Register SrcReg = MI.getOperand(0).getReg();
1317   bool SrcIsKill = MI.getOperand(0).isKill();
1318   unsigned Flags = MI.getFlags();
1319   unsigned OpLo = AVR::PUSHRr;
1320   unsigned OpHi = AVR::PUSHRr;
1321   TRI->splitReg(SrcReg, SrcLoReg, SrcHiReg);
1322 
1323   // Low part
1324   buildMI(MBB, MBBI, OpLo)
1325       .addReg(SrcLoReg, getKillRegState(SrcIsKill))
1326       .setMIFlags(Flags);
1327 
1328   // High part
1329   buildMI(MBB, MBBI, OpHi)
1330       .addReg(SrcHiReg, getKillRegState(SrcIsKill))
1331       .setMIFlags(Flags);
1332 
1333   MI.eraseFromParent();
1334   return true;
1335 }
1336 
1337 template <>
1338 bool AVRExpandPseudo::expand<AVR::POPWRd>(Block &MBB, BlockIt MBBI) {
1339   MachineInstr &MI = *MBBI;
1340   Register DstLoReg, DstHiReg;
1341   Register DstReg = MI.getOperand(0).getReg();
1342   unsigned Flags = MI.getFlags();
1343   unsigned OpLo = AVR::POPRd;
1344   unsigned OpHi = AVR::POPRd;
1345   TRI->splitReg(DstReg, DstLoReg, DstHiReg);
1346 
1347   buildMI(MBB, MBBI, OpHi, DstHiReg).setMIFlags(Flags); // High
1348   buildMI(MBB, MBBI, OpLo, DstLoReg).setMIFlags(Flags); // Low
1349 
1350   MI.eraseFromParent();
1351   return true;
1352 }
1353 
1354 template <>
1355 bool AVRExpandPseudo::expand<AVR::ROLBRd>(Block &MBB, BlockIt MBBI) {
1356   // In AVR, the rotate instructions behave quite unintuitively. They rotate
1357   // bits through the carry bit in SREG, effectively rotating over 9 bits,
1358   // instead of 8. This is useful when we are dealing with numbers over
1359   // multiple registers, but when we actually need to rotate stuff, we have
1360   // to explicitly add the carry bit.
1361 
1362   MachineInstr &MI = *MBBI;
1363   unsigned OpShift, OpCarry;
1364   Register DstReg = MI.getOperand(0).getReg();
1365   bool DstIsDead = MI.getOperand(0).isDead();
1366   bool DstIsKill = MI.getOperand(1).isKill();
1367   OpShift = AVR::ADDRdRr;
1368   OpCarry = AVR::ADCRdRr;
1369 
1370   // add r16, r16
1371   // adc r16, r1
1372 
1373   // Shift part
1374   buildMI(MBB, MBBI, OpShift)
1375       .addReg(DstReg, RegState::Define | getDeadRegState(DstIsDead))
1376       .addReg(DstReg, RegState::Kill)
1377       .addReg(DstReg, RegState::Kill);
1378 
1379   // Add the carry bit
1380   auto MIB = buildMI(MBB, MBBI, OpCarry)
1381                  .addReg(DstReg, RegState::Define | getDeadRegState(DstIsDead))
1382                  .addReg(DstReg, getKillRegState(DstIsKill))
1383                  .addReg(ZERO_REGISTER);
1384 
1385   // SREG is always implicitly killed
1386   MIB->getOperand(2).setIsKill();
1387 
1388   MI.eraseFromParent();
1389   return true;
1390 }
1391 
1392 template <>
1393 bool AVRExpandPseudo::expand<AVR::RORBRd>(Block &MBB, BlockIt MBBI) {
1394   // In AVR, the rotate instructions behave quite unintuitively. They rotate
1395   // bits through the carry bit in SREG, effectively rotating over 9 bits,
1396   // instead of 8. This is useful when we are dealing with numbers over
1397   // multiple registers, but when we actually need to rotate stuff, we have
1398   // to explicitly add the carry bit.
1399 
1400   MachineInstr &MI = *MBBI;
1401   Register DstReg = MI.getOperand(0).getReg();
1402 
1403   // bst r16, 0
1404   // ror r16
1405   // bld r16, 7
1406 
1407   // Move the lowest bit from DstReg into the T bit
1408   buildMI(MBB, MBBI, AVR::BST).addReg(DstReg).addImm(0);
1409 
1410   // Rotate to the right
1411   buildMI(MBB, MBBI, AVR::RORRd, DstReg).addReg(DstReg);
1412 
1413   // Move the T bit into the highest bit of DstReg.
1414   buildMI(MBB, MBBI, AVR::BLD, DstReg).addReg(DstReg).addImm(7);
1415 
1416   MI.eraseFromParent();
1417   return true;
1418 }
1419 
1420 template <>
1421 bool AVRExpandPseudo::expand<AVR::LSLWRd>(Block &MBB, BlockIt MBBI) {
1422   MachineInstr &MI = *MBBI;
1423   Register DstLoReg, DstHiReg;
1424   Register DstReg = MI.getOperand(0).getReg();
1425   bool DstIsDead = MI.getOperand(0).isDead();
1426   bool DstIsKill = MI.getOperand(1).isKill();
1427   bool ImpIsDead = MI.getOperand(2).isDead();
1428   unsigned OpLo = AVR::ADDRdRr; // ADD Rd, Rd <==> LSL Rd
1429   unsigned OpHi = AVR::ADCRdRr; // ADC Rd, Rd <==> ROL Rd
1430   TRI->splitReg(DstReg, DstLoReg, DstHiReg);
1431 
1432   // Low part
1433   buildMI(MBB, MBBI, OpLo)
1434       .addReg(DstLoReg, RegState::Define | getDeadRegState(DstIsDead))
1435       .addReg(DstLoReg, getKillRegState(DstIsKill))
1436       .addReg(DstLoReg, getKillRegState(DstIsKill));
1437 
1438   auto MIBHI =
1439       buildMI(MBB, MBBI, OpHi)
1440           .addReg(DstHiReg, RegState::Define | getDeadRegState(DstIsDead))
1441           .addReg(DstHiReg, getKillRegState(DstIsKill))
1442           .addReg(DstHiReg, getKillRegState(DstIsKill));
1443 
1444   if (ImpIsDead)
1445     MIBHI->getOperand(3).setIsDead();
1446 
1447   // SREG is always implicitly killed
1448   MIBHI->getOperand(4).setIsKill();
1449 
1450   MI.eraseFromParent();
1451   return true;
1452 }
1453 
1454 template <>
1455 bool AVRExpandPseudo::expand<AVR::LSLWHiRd>(Block &MBB, BlockIt MBBI) {
1456   MachineInstr &MI = *MBBI;
1457   Register DstLoReg, DstHiReg;
1458   Register DstReg = MI.getOperand(0).getReg();
1459   bool DstIsDead = MI.getOperand(0).isDead();
1460   bool DstIsKill = MI.getOperand(1).isKill();
1461   bool ImpIsDead = MI.getOperand(2).isDead();
1462   TRI->splitReg(DstReg, DstLoReg, DstHiReg);
1463 
1464   // add hireg, hireg <==> lsl hireg
1465   auto MILSL =
1466       buildMI(MBB, MBBI, AVR::ADDRdRr)
1467           .addReg(DstHiReg, RegState::Define | getDeadRegState(DstIsDead))
1468           .addReg(DstHiReg, getKillRegState(DstIsKill))
1469           .addReg(DstHiReg, getKillRegState(DstIsKill));
1470 
1471   if (ImpIsDead)
1472     MILSL->getOperand(3).setIsDead();
1473 
1474   MI.eraseFromParent();
1475   return true;
1476 }
1477 
1478 bool AVRExpandPseudo::expandLSLW4Rd(Block &MBB, BlockIt MBBI) {
1479   MachineInstr &MI = *MBBI;
1480   Register DstLoReg, DstHiReg;
1481   Register DstReg = MI.getOperand(0).getReg();
1482   bool DstIsDead = MI.getOperand(0).isDead();
1483   bool DstIsKill = MI.getOperand(1).isKill();
1484   bool ImpIsDead = MI.getOperand(3).isDead();
1485   TRI->splitReg(DstReg, DstLoReg, DstHiReg);
1486 
1487   // swap Rh
1488   // swap Rl
1489   buildMI(MBB, MBBI, AVR::SWAPRd)
1490       .addReg(DstHiReg, RegState::Define | getDeadRegState(DstIsDead))
1491       .addReg(DstHiReg, RegState::Kill);
1492   buildMI(MBB, MBBI, AVR::SWAPRd)
1493       .addReg(DstLoReg, RegState::Define | getDeadRegState(DstIsDead))
1494       .addReg(DstLoReg, RegState::Kill);
1495 
1496   // andi Rh, 0xf0
1497   auto MI0 =
1498       buildMI(MBB, MBBI, AVR::ANDIRdK)
1499           .addReg(DstHiReg, RegState::Define | getDeadRegState(DstIsDead))
1500           .addReg(DstHiReg, RegState::Kill)
1501           .addImm(0xf0);
1502   // SREG is implicitly dead.
1503   MI0->getOperand(3).setIsDead();
1504 
1505   // eor Rh, Rl
1506   auto MI1 =
1507       buildMI(MBB, MBBI, AVR::EORRdRr)
1508           .addReg(DstHiReg, RegState::Define | getDeadRegState(DstIsDead))
1509           .addReg(DstHiReg, RegState::Kill)
1510           .addReg(DstLoReg);
1511   // SREG is implicitly dead.
1512   MI1->getOperand(3).setIsDead();
1513 
1514   // andi Rl, 0xf0
1515   auto MI2 =
1516       buildMI(MBB, MBBI, AVR::ANDIRdK)
1517           .addReg(DstLoReg, RegState::Define | getDeadRegState(DstIsDead))
1518           .addReg(DstLoReg, getKillRegState(DstIsKill))
1519           .addImm(0xf0);
1520   // SREG is implicitly dead.
1521   MI2->getOperand(3).setIsDead();
1522 
1523   // eor Rh, Rl
1524   auto MI3 =
1525       buildMI(MBB, MBBI, AVR::EORRdRr)
1526           .addReg(DstHiReg, RegState::Define | getDeadRegState(DstIsDead))
1527           .addReg(DstHiReg, getKillRegState(DstIsKill))
1528           .addReg(DstLoReg);
1529   if (ImpIsDead)
1530     MI3->getOperand(3).setIsDead();
1531 
1532   MI.eraseFromParent();
1533   return true;
1534 }
1535 
1536 bool AVRExpandPseudo::expandLSLW8Rd(Block &MBB, BlockIt MBBI) {
1537   MachineInstr &MI = *MBBI;
1538   Register DstLoReg, DstHiReg;
1539   Register DstReg = MI.getOperand(0).getReg();
1540   bool DstIsDead = MI.getOperand(0).isDead();
1541   bool DstIsKill = MI.getOperand(1).isKill();
1542   bool ImpIsDead = MI.getOperand(3).isDead();
1543   TRI->splitReg(DstReg, DstLoReg, DstHiReg);
1544 
1545   // mov Rh, Rl
1546   buildMI(MBB, MBBI, AVR::MOVRdRr)
1547       .addReg(DstHiReg, RegState::Define | getDeadRegState(DstIsDead))
1548       .addReg(DstLoReg);
1549 
1550   // clr Rl
1551   auto MIBLO =
1552       buildMI(MBB, MBBI, AVR::EORRdRr)
1553           .addReg(DstLoReg, RegState::Define | getDeadRegState(DstIsDead))
1554           .addReg(DstLoReg, getKillRegState(DstIsKill))
1555           .addReg(DstLoReg, getKillRegState(DstIsKill));
1556   if (ImpIsDead)
1557     MIBLO->getOperand(3).setIsDead();
1558 
1559   MI.eraseFromParent();
1560   return true;
1561 }
1562 
1563 bool AVRExpandPseudo::expandLSLW12Rd(Block &MBB, BlockIt MBBI) {
1564   MachineInstr &MI = *MBBI;
1565   Register DstLoReg, DstHiReg;
1566   Register DstReg = MI.getOperand(0).getReg();
1567   bool DstIsDead = MI.getOperand(0).isDead();
1568   bool DstIsKill = MI.getOperand(1).isKill();
1569   bool ImpIsDead = MI.getOperand(3).isDead();
1570   TRI->splitReg(DstReg, DstLoReg, DstHiReg);
1571 
1572   // mov Rh, Rl
1573   buildMI(MBB, MBBI, AVR::MOVRdRr)
1574       .addReg(DstHiReg, RegState::Define | getDeadRegState(DstIsDead))
1575       .addReg(DstLoReg);
1576 
1577   // swap Rh
1578   buildMI(MBB, MBBI, AVR::SWAPRd)
1579       .addReg(DstHiReg, RegState::Define | getDeadRegState(DstIsDead))
1580       .addReg(DstHiReg, RegState::Kill);
1581 
1582   // andi Rh, 0xf0
1583   auto MI0 =
1584       buildMI(MBB, MBBI, AVR::ANDIRdK)
1585           .addReg(DstHiReg, RegState::Define | getDeadRegState(DstIsDead))
1586           .addReg(DstHiReg, getKillRegState(DstIsKill))
1587           .addImm(0xf0);
1588   // SREG is implicitly dead.
1589   MI0->getOperand(3).setIsDead();
1590 
1591   // clr Rl
1592   auto MI1 =
1593       buildMI(MBB, MBBI, AVR::EORRdRr)
1594           .addReg(DstLoReg, RegState::Define | getDeadRegState(DstIsDead))
1595           .addReg(DstLoReg, getKillRegState(DstIsKill))
1596           .addReg(DstLoReg, getKillRegState(DstIsKill));
1597   if (ImpIsDead)
1598     MI1->getOperand(3).setIsDead();
1599 
1600   MI.eraseFromParent();
1601   return true;
1602 }
1603 
1604 template <>
1605 bool AVRExpandPseudo::expand<AVR::LSLWNRd>(Block &MBB, BlockIt MBBI) {
1606   MachineInstr &MI = *MBBI;
1607   unsigned Imm = MI.getOperand(2).getImm();
1608   switch (Imm) {
1609   case 4:
1610     return expandLSLW4Rd(MBB, MBBI);
1611   case 8:
1612     return expandLSLW8Rd(MBB, MBBI);
1613   case 12:
1614     return expandLSLW12Rd(MBB, MBBI);
1615   default:
1616     llvm_unreachable("unimplemented lslwn");
1617     return false;
1618   }
1619 }
1620 
1621 template <>
1622 bool AVRExpandPseudo::expand<AVR::LSRWRd>(Block &MBB, BlockIt MBBI) {
1623   MachineInstr &MI = *MBBI;
1624   Register DstLoReg, DstHiReg;
1625   Register DstReg = MI.getOperand(0).getReg();
1626   bool DstIsDead = MI.getOperand(0).isDead();
1627   bool DstIsKill = MI.getOperand(1).isKill();
1628   bool ImpIsDead = MI.getOperand(2).isDead();
1629   unsigned OpLo = AVR::RORRd;
1630   unsigned OpHi = AVR::LSRRd;
1631   TRI->splitReg(DstReg, DstLoReg, DstHiReg);
1632 
1633   // High part
1634   buildMI(MBB, MBBI, OpHi)
1635       .addReg(DstHiReg, RegState::Define | getDeadRegState(DstIsDead))
1636       .addReg(DstHiReg, getKillRegState(DstIsKill));
1637 
1638   auto MIBLO =
1639       buildMI(MBB, MBBI, OpLo)
1640           .addReg(DstLoReg, RegState::Define | getDeadRegState(DstIsDead))
1641           .addReg(DstLoReg, getKillRegState(DstIsKill));
1642 
1643   if (ImpIsDead)
1644     MIBLO->getOperand(2).setIsDead();
1645 
1646   // SREG is always implicitly killed
1647   MIBLO->getOperand(3).setIsKill();
1648 
1649   MI.eraseFromParent();
1650   return true;
1651 }
1652 
1653 template <>
1654 bool AVRExpandPseudo::expand<AVR::LSRWLoRd>(Block &MBB, BlockIt MBBI) {
1655   MachineInstr &MI = *MBBI;
1656   Register DstLoReg, DstHiReg;
1657   Register DstReg = MI.getOperand(0).getReg();
1658   bool DstIsDead = MI.getOperand(0).isDead();
1659   bool DstIsKill = MI.getOperand(1).isKill();
1660   bool ImpIsDead = MI.getOperand(2).isDead();
1661   TRI->splitReg(DstReg, DstLoReg, DstHiReg);
1662 
1663   // lsr loreg
1664   auto MILSR =
1665       buildMI(MBB, MBBI, AVR::LSRRd)
1666           .addReg(DstLoReg, RegState::Define | getDeadRegState(DstIsDead))
1667           .addReg(DstLoReg, getKillRegState(DstIsKill));
1668 
1669   if (ImpIsDead)
1670     MILSR->getOperand(2).setIsDead();
1671 
1672   MI.eraseFromParent();
1673   return true;
1674 }
1675 
1676 bool AVRExpandPseudo::expandLSRW4Rd(Block &MBB, BlockIt MBBI) {
1677   MachineInstr &MI = *MBBI;
1678   Register DstLoReg, DstHiReg;
1679   Register DstReg = MI.getOperand(0).getReg();
1680   bool DstIsDead = MI.getOperand(0).isDead();
1681   bool DstIsKill = MI.getOperand(1).isKill();
1682   bool ImpIsDead = MI.getOperand(3).isDead();
1683   TRI->splitReg(DstReg, DstLoReg, DstHiReg);
1684 
1685   // swap Rh
1686   // swap Rl
1687   buildMI(MBB, MBBI, AVR::SWAPRd)
1688       .addReg(DstHiReg, RegState::Define | getDeadRegState(DstIsDead))
1689       .addReg(DstHiReg, RegState::Kill);
1690   buildMI(MBB, MBBI, AVR::SWAPRd)
1691       .addReg(DstLoReg, RegState::Define | getDeadRegState(DstIsDead))
1692       .addReg(DstLoReg, RegState::Kill);
1693 
1694   // andi Rl, 0xf
1695   auto MI0 =
1696       buildMI(MBB, MBBI, AVR::ANDIRdK)
1697           .addReg(DstLoReg, RegState::Define | getDeadRegState(DstIsDead))
1698           .addReg(DstLoReg, RegState::Kill)
1699           .addImm(0xf);
1700   // SREG is implicitly dead.
1701   MI0->getOperand(3).setIsDead();
1702 
1703   // eor Rl, Rh
1704   auto MI1 =
1705       buildMI(MBB, MBBI, AVR::EORRdRr)
1706           .addReg(DstLoReg, RegState::Define | getDeadRegState(DstIsDead))
1707           .addReg(DstLoReg, RegState::Kill)
1708           .addReg(DstHiReg);
1709   // SREG is implicitly dead.
1710   MI1->getOperand(3).setIsDead();
1711 
1712   // andi Rh, 0xf
1713   auto MI2 =
1714       buildMI(MBB, MBBI, AVR::ANDIRdK)
1715           .addReg(DstHiReg, RegState::Define | getDeadRegState(DstIsDead))
1716           .addReg(DstHiReg, getKillRegState(DstIsKill))
1717           .addImm(0xf);
1718   // SREG is implicitly dead.
1719   MI2->getOperand(3).setIsDead();
1720 
1721   // eor Rl, Rh
1722   auto MI3 =
1723       buildMI(MBB, MBBI, AVR::EORRdRr)
1724           .addReg(DstLoReg, RegState::Define | getDeadRegState(DstIsDead))
1725           .addReg(DstLoReg, getKillRegState(DstIsKill))
1726           .addReg(DstHiReg);
1727   if (ImpIsDead)
1728     MI3->getOperand(3).setIsDead();
1729 
1730   MI.eraseFromParent();
1731   return true;
1732 }
1733 
1734 bool AVRExpandPseudo::expandLSRW8Rd(Block &MBB, BlockIt MBBI) {
1735   MachineInstr &MI = *MBBI;
1736   Register DstLoReg, DstHiReg;
1737   Register DstReg = MI.getOperand(0).getReg();
1738   bool DstIsDead = MI.getOperand(0).isDead();
1739   bool DstIsKill = MI.getOperand(1).isKill();
1740   bool ImpIsDead = MI.getOperand(3).isDead();
1741   TRI->splitReg(DstReg, DstLoReg, DstHiReg);
1742 
1743   // Move upper byte to lower byte.
1744   buildMI(MBB, MBBI, AVR::MOVRdRr)
1745       .addReg(DstLoReg, RegState::Define | getDeadRegState(DstIsDead))
1746       .addReg(DstHiReg);
1747 
1748   // Clear upper byte.
1749   auto MIBHI =
1750       buildMI(MBB, MBBI, AVR::EORRdRr)
1751           .addReg(DstHiReg, RegState::Define | getDeadRegState(DstIsDead))
1752           .addReg(DstHiReg, getKillRegState(DstIsKill))
1753           .addReg(DstHiReg, getKillRegState(DstIsKill));
1754   if (ImpIsDead)
1755     MIBHI->getOperand(3).setIsDead();
1756 
1757   MI.eraseFromParent();
1758   return true;
1759 }
1760 
1761 bool AVRExpandPseudo::expandLSRW12Rd(Block &MBB, BlockIt MBBI) {
1762   MachineInstr &MI = *MBBI;
1763   Register DstLoReg, DstHiReg;
1764   Register DstReg = MI.getOperand(0).getReg();
1765   bool DstIsDead = MI.getOperand(0).isDead();
1766   bool DstIsKill = MI.getOperand(1).isKill();
1767   bool ImpIsDead = MI.getOperand(3).isDead();
1768   TRI->splitReg(DstReg, DstLoReg, DstHiReg);
1769 
1770   // Move upper byte to lower byte.
1771   buildMI(MBB, MBBI, AVR::MOVRdRr)
1772       .addReg(DstLoReg, RegState::Define | getDeadRegState(DstIsDead))
1773       .addReg(DstHiReg);
1774 
1775   // swap Rl
1776   buildMI(MBB, MBBI, AVR::SWAPRd)
1777       .addReg(DstLoReg, RegState::Define | getDeadRegState(DstIsDead))
1778       .addReg(DstLoReg, RegState::Kill);
1779 
1780   // andi Rl, 0xf
1781   auto MI0 =
1782       buildMI(MBB, MBBI, AVR::ANDIRdK)
1783           .addReg(DstLoReg, RegState::Define | getDeadRegState(DstIsDead))
1784           .addReg(DstLoReg, getKillRegState(DstIsKill))
1785           .addImm(0xf);
1786   // SREG is implicitly dead.
1787   MI0->getOperand(3).setIsDead();
1788 
1789   // Clear upper byte.
1790   auto MIBHI =
1791       buildMI(MBB, MBBI, AVR::EORRdRr)
1792           .addReg(DstHiReg, RegState::Define | getDeadRegState(DstIsDead))
1793           .addReg(DstHiReg, getKillRegState(DstIsKill))
1794           .addReg(DstHiReg, getKillRegState(DstIsKill));
1795   if (ImpIsDead)
1796     MIBHI->getOperand(3).setIsDead();
1797 
1798   MI.eraseFromParent();
1799   return true;
1800 }
1801 
1802 template <>
1803 bool AVRExpandPseudo::expand<AVR::LSRWNRd>(Block &MBB, BlockIt MBBI) {
1804   MachineInstr &MI = *MBBI;
1805   unsigned Imm = MI.getOperand(2).getImm();
1806   switch (Imm) {
1807   case 4:
1808     return expandLSRW4Rd(MBB, MBBI);
1809   case 8:
1810     return expandLSRW8Rd(MBB, MBBI);
1811   case 12:
1812     return expandLSRW12Rd(MBB, MBBI);
1813   default:
1814     llvm_unreachable("unimplemented lsrwn");
1815     return false;
1816   }
1817 }
1818 
1819 template <>
1820 bool AVRExpandPseudo::expand<AVR::RORWRd>(Block &MBB, BlockIt MBBI) {
1821   llvm_unreachable("RORW unimplemented");
1822   return false;
1823 }
1824 
1825 template <>
1826 bool AVRExpandPseudo::expand<AVR::ROLWRd>(Block &MBB, BlockIt MBBI) {
1827   llvm_unreachable("ROLW unimplemented");
1828   return false;
1829 }
1830 
1831 template <>
1832 bool AVRExpandPseudo::expand<AVR::ASRWRd>(Block &MBB, BlockIt MBBI) {
1833   MachineInstr &MI = *MBBI;
1834   Register DstLoReg, DstHiReg;
1835   Register DstReg = MI.getOperand(0).getReg();
1836   bool DstIsDead = MI.getOperand(0).isDead();
1837   bool DstIsKill = MI.getOperand(1).isKill();
1838   bool ImpIsDead = MI.getOperand(2).isDead();
1839   unsigned OpLo = AVR::RORRd;
1840   unsigned OpHi = AVR::ASRRd;
1841   TRI->splitReg(DstReg, DstLoReg, DstHiReg);
1842 
1843   // High part
1844   buildMI(MBB, MBBI, OpHi)
1845       .addReg(DstHiReg, RegState::Define | getDeadRegState(DstIsDead))
1846       .addReg(DstHiReg, getKillRegState(DstIsKill));
1847 
1848   auto MIBLO =
1849       buildMI(MBB, MBBI, OpLo)
1850           .addReg(DstLoReg, RegState::Define | getDeadRegState(DstIsDead))
1851           .addReg(DstLoReg, getKillRegState(DstIsKill));
1852 
1853   if (ImpIsDead)
1854     MIBLO->getOperand(2).setIsDead();
1855 
1856   // SREG is always implicitly killed
1857   MIBLO->getOperand(3).setIsKill();
1858 
1859   MI.eraseFromParent();
1860   return true;
1861 }
1862 
1863 template <>
1864 bool AVRExpandPseudo::expand<AVR::ASRWLoRd>(Block &MBB, BlockIt MBBI) {
1865   MachineInstr &MI = *MBBI;
1866   Register DstLoReg, DstHiReg;
1867   Register DstReg = MI.getOperand(0).getReg();
1868   bool DstIsDead = MI.getOperand(0).isDead();
1869   bool DstIsKill = MI.getOperand(1).isKill();
1870   bool ImpIsDead = MI.getOperand(2).isDead();
1871   TRI->splitReg(DstReg, DstLoReg, DstHiReg);
1872 
1873   // asr loreg
1874   auto MIASR =
1875       buildMI(MBB, MBBI, AVR::ASRRd)
1876           .addReg(DstLoReg, RegState::Define | getDeadRegState(DstIsDead))
1877           .addReg(DstLoReg, getKillRegState(DstIsKill));
1878 
1879   if (ImpIsDead)
1880     MIASR->getOperand(2).setIsDead();
1881 
1882   MI.eraseFromParent();
1883   return true;
1884 }
1885 
1886 bool AVRExpandPseudo::expandASRW7Rd(Block &MBB, BlockIt MBBI) {
1887   MachineInstr &MI = *MBBI;
1888   Register DstLoReg, DstHiReg;
1889   Register DstReg = MI.getOperand(0).getReg();
1890   bool DstIsDead = MI.getOperand(0).isDead();
1891   bool DstIsKill = MI.getOperand(1).isKill();
1892   bool ImpIsDead = MI.getOperand(3).isDead();
1893   TRI->splitReg(DstReg, DstLoReg, DstHiReg);
1894 
1895   // lsl r24
1896   // mov r24,r25
1897   // rol r24
1898   // sbc r25,r25
1899 
1900   // lsl r24 <=> add r24, r24
1901   buildMI(MBB, MBBI, AVR::ADDRdRr)
1902       .addReg(DstLoReg, RegState::Define | getDeadRegState(DstIsDead))
1903       .addReg(DstLoReg, RegState::Kill)
1904       .addReg(DstLoReg, RegState::Kill);
1905 
1906   // mov r24, r25
1907   buildMI(MBB, MBBI, AVR::MOVRdRr)
1908       .addReg(DstLoReg, RegState::Define | getDeadRegState(DstIsDead))
1909       .addReg(DstHiReg);
1910 
1911   // rol r24 <=> adc r24, r24
1912   buildMI(MBB, MBBI, AVR::ADCRdRr)
1913       .addReg(DstLoReg, RegState::Define | getDeadRegState(DstIsDead))
1914       .addReg(DstLoReg, getKillRegState(DstIsKill))
1915       .addReg(DstLoReg, getKillRegState(DstIsKill));
1916 
1917   // sbc r25, r25
1918   auto MISBC =
1919       buildMI(MBB, MBBI, AVR::SBCRdRr)
1920           .addReg(DstHiReg, RegState::Define | getDeadRegState(DstIsDead))
1921           .addReg(DstHiReg, getKillRegState(DstIsKill))
1922           .addReg(DstHiReg, getKillRegState(DstIsKill));
1923 
1924   if (ImpIsDead)
1925     MISBC->getOperand(3).setIsDead();
1926   // SREG is always implicitly killed
1927   MISBC->getOperand(4).setIsKill();
1928 
1929   MI.eraseFromParent();
1930   return true;
1931 }
1932 
1933 bool AVRExpandPseudo::expandASRW8Rd(Block &MBB, BlockIt MBBI) {
1934   MachineInstr &MI = *MBBI;
1935   Register DstLoReg, DstHiReg;
1936   Register DstReg = MI.getOperand(0).getReg();
1937   bool DstIsDead = MI.getOperand(0).isDead();
1938   bool DstIsKill = MI.getOperand(1).isKill();
1939   bool ImpIsDead = MI.getOperand(3).isDead();
1940   TRI->splitReg(DstReg, DstLoReg, DstHiReg);
1941 
1942   // Move upper byte to lower byte.
1943   buildMI(MBB, MBBI, AVR::MOVRdRr)
1944       .addReg(DstLoReg, RegState::Define | getDeadRegState(DstIsDead))
1945       .addReg(DstHiReg);
1946 
1947   // Move the sign bit to the C flag.
1948   buildMI(MBB, MBBI, AVR::ADDRdRr)
1949       .addReg(DstHiReg, RegState::Define | getDeadRegState(DstIsDead))
1950       .addReg(DstHiReg, RegState::Kill)
1951       .addReg(DstHiReg, RegState::Kill);
1952 
1953   // Set upper byte to 0 or -1.
1954   auto MIBHI =
1955       buildMI(MBB, MBBI, AVR::SBCRdRr)
1956           .addReg(DstHiReg, RegState::Define | getDeadRegState(DstIsDead))
1957           .addReg(DstHiReg, getKillRegState(DstIsKill))
1958           .addReg(DstHiReg, getKillRegState(DstIsKill));
1959 
1960   if (ImpIsDead)
1961     MIBHI->getOperand(3).setIsDead();
1962   // SREG is always implicitly killed
1963   MIBHI->getOperand(4).setIsKill();
1964 
1965   MI.eraseFromParent();
1966   return true;
1967 }
1968 bool AVRExpandPseudo::expandASRW14Rd(Block &MBB, BlockIt MBBI) {
1969   MachineInstr &MI = *MBBI;
1970   Register DstLoReg, DstHiReg;
1971   Register DstReg = MI.getOperand(0).getReg();
1972   bool DstIsDead = MI.getOperand(0).isDead();
1973   bool DstIsKill = MI.getOperand(1).isKill();
1974   bool ImpIsDead = MI.getOperand(3).isDead();
1975   TRI->splitReg(DstReg, DstLoReg, DstHiReg);
1976 
1977   // lsl r25
1978   // sbc r24, r24
1979   // lsl r25
1980   // mov r25, r24
1981   // rol r24
1982 
1983   // lsl r25 <=> add r25, r25
1984   buildMI(MBB, MBBI, AVR::ADDRdRr)
1985       .addReg(DstHiReg, RegState::Define | getDeadRegState(DstIsDead))
1986       .addReg(DstHiReg, RegState::Kill)
1987       .addReg(DstHiReg, RegState::Kill);
1988 
1989   // sbc r24, r24
1990   buildMI(MBB, MBBI, AVR::SBCRdRr)
1991       .addReg(DstLoReg, RegState::Define | getDeadRegState(DstIsDead))
1992       .addReg(DstLoReg, RegState::Kill)
1993       .addReg(DstLoReg, RegState::Kill);
1994 
1995   // lsl r25 <=> add r25, r25
1996   buildMI(MBB, MBBI, AVR::ADDRdRr)
1997       .addReg(DstHiReg, RegState::Define | getDeadRegState(DstIsDead))
1998       .addReg(DstHiReg, RegState::Kill)
1999       .addReg(DstHiReg, RegState::Kill);
2000 
2001   // mov r25, r24
2002   buildMI(MBB, MBBI, AVR::MOVRdRr)
2003       .addReg(DstHiReg, RegState::Define | getDeadRegState(DstIsDead))
2004       .addReg(DstLoReg);
2005 
2006   // rol r24 <=> adc r24, r24
2007   auto MIROL =
2008       buildMI(MBB, MBBI, AVR::ADCRdRr)
2009           .addReg(DstLoReg, RegState::Define | getDeadRegState(DstIsDead))
2010           .addReg(DstLoReg, getKillRegState(DstIsKill))
2011           .addReg(DstLoReg, getKillRegState(DstIsKill));
2012 
2013   if (ImpIsDead)
2014     MIROL->getOperand(3).setIsDead();
2015   // SREG is always implicitly killed
2016   MIROL->getOperand(4).setIsKill();
2017 
2018   MI.eraseFromParent();
2019   return false;
2020 }
2021 
2022 bool AVRExpandPseudo::expandASRW15Rd(Block &MBB, BlockIt MBBI) {
2023   MachineInstr &MI = *MBBI;
2024   Register DstLoReg, DstHiReg;
2025   Register DstReg = MI.getOperand(0).getReg();
2026   bool DstIsDead = MI.getOperand(0).isDead();
2027   bool ImpIsDead = MI.getOperand(3).isDead();
2028   TRI->splitReg(DstReg, DstLoReg, DstHiReg);
2029 
2030   // lsl r25
2031   // sbc r25, r25
2032   // mov r24, r25
2033 
2034   // lsl r25 <=> add r25, r25
2035   buildMI(MBB, MBBI, AVR::ADDRdRr)
2036       .addReg(DstHiReg, RegState::Define)
2037       .addReg(DstHiReg, RegState::Kill)
2038       .addReg(DstHiReg, RegState::Kill);
2039 
2040   // sbc r25, r25
2041   auto MISBC =
2042       buildMI(MBB, MBBI, AVR::SBCRdRr)
2043           .addReg(DstHiReg, RegState::Define | getDeadRegState(DstIsDead))
2044           .addReg(DstHiReg, RegState::Kill)
2045           .addReg(DstHiReg, RegState::Kill);
2046   if (ImpIsDead)
2047     MISBC->getOperand(3).setIsDead();
2048   // SREG is always implicitly killed
2049   MISBC->getOperand(4).setIsKill();
2050 
2051   // mov r24, r25
2052   buildMI(MBB, MBBI, AVR::MOVRdRr)
2053       .addReg(DstLoReg, RegState::Define | getDeadRegState(DstIsDead))
2054       .addReg(DstHiReg);
2055 
2056   MI.eraseFromParent();
2057   return true;
2058 }
2059 
2060 template <>
2061 bool AVRExpandPseudo::expand<AVR::ASRWNRd>(Block &MBB, BlockIt MBBI) {
2062   MachineInstr &MI = *MBBI;
2063   unsigned Imm = MI.getOperand(2).getImm();
2064   switch (Imm) {
2065   case 7:
2066     return expandASRW7Rd(MBB, MBBI);
2067   case 8:
2068     return expandASRW8Rd(MBB, MBBI);
2069   case 14:
2070     return expandASRW14Rd(MBB, MBBI);
2071   case 15:
2072     return expandASRW15Rd(MBB, MBBI);
2073   default:
2074     llvm_unreachable("unimplemented asrwn");
2075     return false;
2076   }
2077 }
2078 
2079 bool AVRExpandPseudo::expandLSLB7Rd(Block &MBB, BlockIt MBBI) {
2080   MachineInstr &MI = *MBBI;
2081   Register DstReg = MI.getOperand(0).getReg();
2082   bool DstIsDead = MI.getOperand(0).isDead();
2083   bool DstIsKill = MI.getOperand(1).isKill();
2084   bool ImpIsDead = MI.getOperand(3).isDead();
2085 
2086   // ror r24
2087   // clr r24
2088   // ror r24
2089 
2090   buildMI(MBB, MBBI, AVR::RORRd)
2091       .addReg(DstReg, RegState::Define | getDeadRegState(DstIsDead))
2092       .addReg(DstReg, RegState::Kill)
2093       ->getOperand(3)
2094       .setIsUndef(true);
2095 
2096   buildMI(MBB, MBBI, AVR::EORRdRr)
2097       .addReg(DstReg, RegState::Define | getDeadRegState(DstIsDead))
2098       .addReg(DstReg, RegState::Kill)
2099       .addReg(DstReg, RegState::Kill);
2100 
2101   auto MIRRC =
2102       buildMI(MBB, MBBI, AVR::RORRd)
2103           .addReg(DstReg, RegState::Define | getDeadRegState(DstIsDead))
2104           .addReg(DstReg, getKillRegState(DstIsKill));
2105 
2106   if (ImpIsDead)
2107     MIRRC->getOperand(2).setIsDead();
2108 
2109   // SREG is always implicitly killed
2110   MIRRC->getOperand(3).setIsKill();
2111 
2112   MI.eraseFromParent();
2113   return true;
2114 }
2115 
2116 template <>
2117 bool AVRExpandPseudo::expand<AVR::LSLBNRd>(Block &MBB, BlockIt MBBI) {
2118   MachineInstr &MI = *MBBI;
2119   unsigned Imm = MI.getOperand(2).getImm();
2120   switch (Imm) {
2121   case 7:
2122     return expandLSLB7Rd(MBB, MBBI);
2123   default:
2124     llvm_unreachable("unimplemented lslbn");
2125     return false;
2126   }
2127 }
2128 
2129 bool AVRExpandPseudo::expandLSRB7Rd(Block &MBB, BlockIt MBBI) {
2130   MachineInstr &MI = *MBBI;
2131   Register DstReg = MI.getOperand(0).getReg();
2132   bool DstIsDead = MI.getOperand(0).isDead();
2133   bool DstIsKill = MI.getOperand(1).isKill();
2134   bool ImpIsDead = MI.getOperand(3).isDead();
2135 
2136   // rol r24
2137   // clr r24
2138   // rol r24
2139 
2140   buildMI(MBB, MBBI, AVR::ADCRdRr)
2141       .addReg(DstReg, RegState::Define | getDeadRegState(DstIsDead))
2142       .addReg(DstReg, RegState::Kill)
2143       .addReg(DstReg, RegState::Kill)
2144       ->getOperand(4)
2145       .setIsUndef(true);
2146 
2147   buildMI(MBB, MBBI, AVR::EORRdRr)
2148       .addReg(DstReg, RegState::Define | getDeadRegState(DstIsDead))
2149       .addReg(DstReg, RegState::Kill)
2150       .addReg(DstReg, RegState::Kill);
2151 
2152   auto MIRRC =
2153       buildMI(MBB, MBBI, AVR::ADCRdRr)
2154           .addReg(DstReg, RegState::Define | getDeadRegState(DstIsDead))
2155           .addReg(DstReg, getKillRegState(DstIsKill))
2156           .addReg(DstReg, getKillRegState(DstIsKill));
2157 
2158   if (ImpIsDead)
2159     MIRRC->getOperand(3).setIsDead();
2160 
2161   // SREG is always implicitly killed
2162   MIRRC->getOperand(4).setIsKill();
2163 
2164   MI.eraseFromParent();
2165   return true;
2166 }
2167 
2168 template <>
2169 bool AVRExpandPseudo::expand<AVR::LSRBNRd>(Block &MBB, BlockIt MBBI) {
2170   MachineInstr &MI = *MBBI;
2171   unsigned Imm = MI.getOperand(2).getImm();
2172   switch (Imm) {
2173   case 7:
2174     return expandLSRB7Rd(MBB, MBBI);
2175   default:
2176     llvm_unreachable("unimplemented lsrbn");
2177     return false;
2178   }
2179 }
2180 
2181 bool AVRExpandPseudo::expandASRB6Rd(Block &MBB, BlockIt MBBI) {
2182   MachineInstr &MI = *MBBI;
2183   Register DstReg = MI.getOperand(0).getReg();
2184   bool DstIsDead = MI.getOperand(0).isDead();
2185   bool DstIsKill = MI.getOperand(1).isKill();
2186 
2187   // bst r24, 6
2188   // lsl r24
2189   // sbc r24, r24
2190   // bld r24, 0
2191 
2192   buildMI(MBB, MBBI, AVR::BST)
2193       .addReg(DstReg)
2194       .addImm(6)
2195       ->getOperand(2)
2196       .setIsUndef(true);
2197 
2198   buildMI(MBB, MBBI, AVR::ADDRdRr) // LSL Rd <==> ADD Rd, Rd
2199       .addReg(DstReg, RegState::Define | getDeadRegState(DstIsDead))
2200       .addReg(DstReg, RegState::Kill)
2201       .addReg(DstReg, RegState::Kill);
2202 
2203   buildMI(MBB, MBBI, AVR::SBCRdRr)
2204       .addReg(DstReg, RegState::Define | getDeadRegState(DstIsDead))
2205       .addReg(DstReg, RegState::Kill)
2206       .addReg(DstReg, RegState::Kill);
2207 
2208   buildMI(MBB, MBBI, AVR::BLD)
2209       .addReg(DstReg, RegState::Define | getDeadRegState(DstIsDead))
2210       .addReg(DstReg, getKillRegState(DstIsKill))
2211       .addImm(0)
2212       ->getOperand(3)
2213       .setIsKill();
2214 
2215   MI.eraseFromParent();
2216   return true;
2217 }
2218 
2219 bool AVRExpandPseudo::expandASRB7Rd(Block &MBB, BlockIt MBBI) {
2220   MachineInstr &MI = *MBBI;
2221   Register DstReg = MI.getOperand(0).getReg();
2222   bool DstIsDead = MI.getOperand(0).isDead();
2223   bool DstIsKill = MI.getOperand(1).isKill();
2224   bool ImpIsDead = MI.getOperand(3).isDead();
2225 
2226   // lsl r24
2227   // sbc r24, r24
2228 
2229   buildMI(MBB, MBBI, AVR::ADDRdRr)
2230       .addReg(DstReg, RegState::Define | getDeadRegState(DstIsDead))
2231       .addReg(DstReg, RegState::Kill)
2232       .addReg(DstReg, RegState::Kill);
2233 
2234   auto MIRRC =
2235       buildMI(MBB, MBBI, AVR::SBCRdRr)
2236           .addReg(DstReg, RegState::Define | getDeadRegState(DstIsDead))
2237           .addReg(DstReg, getKillRegState(DstIsKill))
2238           .addReg(DstReg, getKillRegState(DstIsKill));
2239 
2240   if (ImpIsDead)
2241     MIRRC->getOperand(3).setIsDead();
2242 
2243   // SREG is always implicitly killed
2244   MIRRC->getOperand(4).setIsKill();
2245 
2246   MI.eraseFromParent();
2247   return true;
2248 }
2249 
2250 template <>
2251 bool AVRExpandPseudo::expand<AVR::ASRBNRd>(Block &MBB, BlockIt MBBI) {
2252   MachineInstr &MI = *MBBI;
2253   unsigned Imm = MI.getOperand(2).getImm();
2254   switch (Imm) {
2255   case 6:
2256     return expandASRB6Rd(MBB, MBBI);
2257   case 7:
2258     return expandASRB7Rd(MBB, MBBI);
2259   default:
2260     llvm_unreachable("unimplemented asrbn");
2261     return false;
2262   }
2263 }
2264 
2265 template <> bool AVRExpandPseudo::expand<AVR::SEXT>(Block &MBB, BlockIt MBBI) {
2266   MachineInstr &MI = *MBBI;
2267   Register DstLoReg, DstHiReg;
2268   // sext R17:R16, R17
2269   // mov     r16, r17
2270   // lsl     r17
2271   // sbc     r17, r17
2272   // sext R17:R16, R13
2273   // mov     r16, r13
2274   // mov     r17, r13
2275   // lsl     r17
2276   // sbc     r17, r17
2277   // sext R17:R16, R16
2278   // mov     r17, r16
2279   // lsl     r17
2280   // sbc     r17, r17
2281   Register DstReg = MI.getOperand(0).getReg();
2282   Register SrcReg = MI.getOperand(1).getReg();
2283   bool DstIsDead = MI.getOperand(0).isDead();
2284   bool SrcIsKill = MI.getOperand(1).isKill();
2285   bool ImpIsDead = MI.getOperand(2).isDead();
2286   TRI->splitReg(DstReg, DstLoReg, DstHiReg);
2287 
2288   if (SrcReg != DstLoReg)
2289     buildMI(MBB, MBBI, AVR::MOVRdRr)
2290         .addReg(DstLoReg, RegState::Define | getDeadRegState(DstIsDead))
2291         .addReg(SrcReg);
2292 
2293   if (SrcReg != DstHiReg) {
2294     auto MOV = buildMI(MBB, MBBI, AVR::MOVRdRr)
2295                    .addReg(DstHiReg, RegState::Define)
2296                    .addReg(SrcReg);
2297     if (SrcReg != DstLoReg && SrcIsKill)
2298       MOV->getOperand(1).setIsKill();
2299   }
2300 
2301   buildMI(MBB, MBBI, AVR::ADDRdRr) // LSL Rd <==> ADD Rd, Rr
2302       .addReg(DstHiReg, RegState::Define)
2303       .addReg(DstHiReg, RegState::Kill)
2304       .addReg(DstHiReg, RegState::Kill);
2305 
2306   auto SBC =
2307       buildMI(MBB, MBBI, AVR::SBCRdRr)
2308           .addReg(DstHiReg, RegState::Define | getDeadRegState(DstIsDead))
2309           .addReg(DstHiReg, RegState::Kill)
2310           .addReg(DstHiReg, RegState::Kill);
2311 
2312   if (ImpIsDead)
2313     SBC->getOperand(3).setIsDead();
2314 
2315   // SREG is always implicitly killed
2316   SBC->getOperand(4).setIsKill();
2317 
2318   MI.eraseFromParent();
2319   return true;
2320 }
2321 
2322 template <> bool AVRExpandPseudo::expand<AVR::ZEXT>(Block &MBB, BlockIt MBBI) {
2323   MachineInstr &MI = *MBBI;
2324   Register DstLoReg, DstHiReg;
2325   // zext R25:R24, R20
2326   // mov      R24, R20
2327   // eor      R25, R25
2328   // zext R25:R24, R24
2329   // eor      R25, R25
2330   // zext R25:R24, R25
2331   // mov      R24, R25
2332   // eor      R25, R25
2333   Register DstReg = MI.getOperand(0).getReg();
2334   Register SrcReg = MI.getOperand(1).getReg();
2335   bool DstIsDead = MI.getOperand(0).isDead();
2336   bool SrcIsKill = MI.getOperand(1).isKill();
2337   bool ImpIsDead = MI.getOperand(2).isDead();
2338   TRI->splitReg(DstReg, DstLoReg, DstHiReg);
2339 
2340   if (SrcReg != DstLoReg) {
2341     buildMI(MBB, MBBI, AVR::MOVRdRr)
2342         .addReg(DstLoReg, RegState::Define | getDeadRegState(DstIsDead))
2343         .addReg(SrcReg, getKillRegState(SrcIsKill));
2344   }
2345 
2346   auto EOR =
2347       buildMI(MBB, MBBI, AVR::EORRdRr)
2348           .addReg(DstHiReg, RegState::Define | getDeadRegState(DstIsDead))
2349           .addReg(DstHiReg, RegState::Kill | RegState::Undef)
2350           .addReg(DstHiReg, RegState::Kill | RegState::Undef);
2351 
2352   if (ImpIsDead)
2353     EOR->getOperand(3).setIsDead();
2354 
2355   MI.eraseFromParent();
2356   return true;
2357 }
2358 
2359 template <>
2360 bool AVRExpandPseudo::expand<AVR::SPREAD>(Block &MBB, BlockIt MBBI) {
2361   MachineInstr &MI = *MBBI;
2362   Register DstLoReg, DstHiReg;
2363   Register DstReg = MI.getOperand(0).getReg();
2364   bool DstIsDead = MI.getOperand(0).isDead();
2365   unsigned Flags = MI.getFlags();
2366   unsigned OpLo = AVR::INRdA;
2367   unsigned OpHi = AVR::INRdA;
2368   TRI->splitReg(DstReg, DstLoReg, DstHiReg);
2369 
2370   // Low part
2371   buildMI(MBB, MBBI, OpLo)
2372       .addReg(DstLoReg, RegState::Define | getDeadRegState(DstIsDead))
2373       .addImm(0x3d)
2374       .setMIFlags(Flags);
2375 
2376   // High part
2377   buildMI(MBB, MBBI, OpHi)
2378       .addReg(DstHiReg, RegState::Define | getDeadRegState(DstIsDead))
2379       .addImm(0x3e)
2380       .setMIFlags(Flags);
2381 
2382   MI.eraseFromParent();
2383   return true;
2384 }
2385 
2386 template <>
2387 bool AVRExpandPseudo::expand<AVR::SPWRITE>(Block &MBB, BlockIt MBBI) {
2388   const AVRSubtarget &STI = MBB.getParent()->getSubtarget<AVRSubtarget>();
2389   MachineInstr &MI = *MBBI;
2390   Register SrcLoReg, SrcHiReg;
2391   Register SrcReg = MI.getOperand(1).getReg();
2392   bool SrcIsKill = MI.getOperand(1).isKill();
2393   unsigned Flags = MI.getFlags();
2394   TRI->splitReg(SrcReg, SrcLoReg, SrcHiReg);
2395 
2396   buildMI(MBB, MBBI, AVR::INRdA)
2397       .addReg(AVR::R0, RegState::Define)
2398       .addImm(STI.getIORegSREG())
2399       .setMIFlags(Flags);
2400 
2401   buildMI(MBB, MBBI, AVR::BCLRs).addImm(0x07).setMIFlags(Flags);
2402 
2403   buildMI(MBB, MBBI, AVR::OUTARr)
2404       .addImm(0x3e)
2405       .addReg(SrcHiReg, getKillRegState(SrcIsKill))
2406       .setMIFlags(Flags);
2407 
2408   buildMI(MBB, MBBI, AVR::OUTARr)
2409       .addImm(STI.getIORegSREG())
2410       .addReg(AVR::R0, RegState::Kill)
2411       .setMIFlags(Flags);
2412 
2413   buildMI(MBB, MBBI, AVR::OUTARr)
2414       .addImm(0x3d)
2415       .addReg(SrcLoReg, getKillRegState(SrcIsKill))
2416       .setMIFlags(Flags);
2417 
2418   MI.eraseFromParent();
2419   return true;
2420 }
2421 
2422 bool AVRExpandPseudo::expandMI(Block &MBB, BlockIt MBBI) {
2423   MachineInstr &MI = *MBBI;
2424   int Opcode = MBBI->getOpcode();
2425 
2426 #define EXPAND(Op)                                                             \
2427   case Op:                                                                     \
2428     return expand<Op>(MBB, MI)
2429 
2430   switch (Opcode) {
2431     EXPAND(AVR::ADDWRdRr);
2432     EXPAND(AVR::ADCWRdRr);
2433     EXPAND(AVR::SUBWRdRr);
2434     EXPAND(AVR::SUBIWRdK);
2435     EXPAND(AVR::SBCWRdRr);
2436     EXPAND(AVR::SBCIWRdK);
2437     EXPAND(AVR::ANDWRdRr);
2438     EXPAND(AVR::ANDIWRdK);
2439     EXPAND(AVR::ORWRdRr);
2440     EXPAND(AVR::ORIWRdK);
2441     EXPAND(AVR::EORWRdRr);
2442     EXPAND(AVR::COMWRd);
2443     EXPAND(AVR::NEGWRd);
2444     EXPAND(AVR::CPWRdRr);
2445     EXPAND(AVR::CPCWRdRr);
2446     EXPAND(AVR::LDIWRdK);
2447     EXPAND(AVR::LDSWRdK);
2448     EXPAND(AVR::LDWRdPtr);
2449     EXPAND(AVR::LDWRdPtrPi);
2450     EXPAND(AVR::LDWRdPtrPd);
2451   case AVR::LDDWRdYQ: //: FIXME: remove this once PR13375 gets fixed
2452     EXPAND(AVR::LDDWRdPtrQ);
2453     EXPAND(AVR::LPMWRdZ);
2454     EXPAND(AVR::LPMWRdZPi);
2455     EXPAND(AVR::ELPMBRdZ);
2456     EXPAND(AVR::ELPMWRdZ);
2457     EXPAND(AVR::ELPMBRdZPi);
2458     EXPAND(AVR::ELPMWRdZPi);
2459     EXPAND(AVR::AtomicLoad8);
2460     EXPAND(AVR::AtomicLoad16);
2461     EXPAND(AVR::AtomicStore8);
2462     EXPAND(AVR::AtomicStore16);
2463     EXPAND(AVR::AtomicFence);
2464     EXPAND(AVR::STSWKRr);
2465     EXPAND(AVR::STWPtrRr);
2466     EXPAND(AVR::STWPtrPiRr);
2467     EXPAND(AVR::STWPtrPdRr);
2468     EXPAND(AVR::STDWPtrQRr);
2469     EXPAND(AVR::STDSPQRr);
2470     EXPAND(AVR::STDWSPQRr);
2471     EXPAND(AVR::INWRdA);
2472     EXPAND(AVR::OUTWARr);
2473     EXPAND(AVR::PUSHWRr);
2474     EXPAND(AVR::POPWRd);
2475     EXPAND(AVR::ROLBRd);
2476     EXPAND(AVR::RORBRd);
2477     EXPAND(AVR::LSLWRd);
2478     EXPAND(AVR::LSRWRd);
2479     EXPAND(AVR::RORWRd);
2480     EXPAND(AVR::ROLWRd);
2481     EXPAND(AVR::ASRWRd);
2482     EXPAND(AVR::LSLWHiRd);
2483     EXPAND(AVR::LSRWLoRd);
2484     EXPAND(AVR::ASRWLoRd);
2485     EXPAND(AVR::LSLWNRd);
2486     EXPAND(AVR::LSRWNRd);
2487     EXPAND(AVR::ASRWNRd);
2488     EXPAND(AVR::LSLBNRd);
2489     EXPAND(AVR::LSRBNRd);
2490     EXPAND(AVR::ASRBNRd);
2491     EXPAND(AVR::SEXT);
2492     EXPAND(AVR::ZEXT);
2493     EXPAND(AVR::SPREAD);
2494     EXPAND(AVR::SPWRITE);
2495   }
2496 #undef EXPAND
2497   return false;
2498 }
2499 
2500 } // end of anonymous namespace
2501 
2502 INITIALIZE_PASS(AVRExpandPseudo, "avr-expand-pseudo", AVR_EXPAND_PSEUDO_NAME,
2503                 false, false)
2504 namespace llvm {
2505 
2506 FunctionPass *createAVRExpandPseudoPass() { return new AVRExpandPseudo(); }
2507 
2508 } // end of namespace llvm
2509