1 //===-- LanaiInstrInfo.cpp - Lanai Instruction Information ------*- C++ -*-===//
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 the Lanai implementation of the TargetInstrInfo class.
10 //
11 //===----------------------------------------------------------------------===//
12 
13 #include "LanaiInstrInfo.h"
14 #include "LanaiAluCode.h"
15 #include "LanaiCondCode.h"
16 #include "MCTargetDesc/LanaiBaseInfo.h"
17 #include "llvm/ADT/STLExtras.h"
18 #include "llvm/ADT/SmallVector.h"
19 #include "llvm/CodeGen/MachineFunctionPass.h"
20 #include "llvm/CodeGen/MachineInstrBuilder.h"
21 #include "llvm/CodeGen/MachineRegisterInfo.h"
22 #include "llvm/MC/TargetRegistry.h"
23 #include "llvm/Support/ErrorHandling.h"
24 
25 using namespace llvm;
26 
27 #define GET_INSTRINFO_CTOR_DTOR
28 #include "LanaiGenInstrInfo.inc"
29 
30 LanaiInstrInfo::LanaiInstrInfo()
31     : LanaiGenInstrInfo(Lanai::ADJCALLSTACKDOWN, Lanai::ADJCALLSTACKUP),
32       RegisterInfo() {}
33 
34 void LanaiInstrInfo::copyPhysReg(MachineBasicBlock &MBB,
35                                  MachineBasicBlock::iterator Position,
36                                  const DebugLoc &DL,
37                                  MCRegister DestinationRegister,
38                                  MCRegister SourceRegister,
39                                  bool KillSource) const {
40   if (!Lanai::GPRRegClass.contains(DestinationRegister, SourceRegister)) {
41     llvm_unreachable("Impossible reg-to-reg copy");
42   }
43 
44   BuildMI(MBB, Position, DL, get(Lanai::OR_I_LO), DestinationRegister)
45       .addReg(SourceRegister, getKillRegState(KillSource))
46       .addImm(0);
47 }
48 
49 void LanaiInstrInfo::storeRegToStackSlot(
50     MachineBasicBlock &MBB, MachineBasicBlock::iterator Position,
51     Register SourceRegister, bool IsKill, int FrameIndex,
52     const TargetRegisterClass *RegisterClass,
53     const TargetRegisterInfo * /*RegisterInfo*/, Register /*VReg*/) const {
54   DebugLoc DL;
55   if (Position != MBB.end()) {
56     DL = Position->getDebugLoc();
57   }
58 
59   if (!Lanai::GPRRegClass.hasSubClassEq(RegisterClass)) {
60     llvm_unreachable("Can't store this register to stack slot");
61   }
62   BuildMI(MBB, Position, DL, get(Lanai::SW_RI))
63       .addReg(SourceRegister, getKillRegState(IsKill))
64       .addFrameIndex(FrameIndex)
65       .addImm(0)
66       .addImm(LPAC::ADD);
67 }
68 
69 void LanaiInstrInfo::loadRegFromStackSlot(
70     MachineBasicBlock &MBB, MachineBasicBlock::iterator Position,
71     Register DestinationRegister, int FrameIndex,
72     const TargetRegisterClass *RegisterClass,
73     const TargetRegisterInfo * /*RegisterInfo*/, Register /*VReg*/) const {
74   DebugLoc DL;
75   if (Position != MBB.end()) {
76     DL = Position->getDebugLoc();
77   }
78 
79   if (!Lanai::GPRRegClass.hasSubClassEq(RegisterClass)) {
80     llvm_unreachable("Can't load this register from stack slot");
81   }
82   BuildMI(MBB, Position, DL, get(Lanai::LDW_RI), DestinationRegister)
83       .addFrameIndex(FrameIndex)
84       .addImm(0)
85       .addImm(LPAC::ADD);
86 }
87 
88 bool LanaiInstrInfo::areMemAccessesTriviallyDisjoint(
89     const MachineInstr &MIa, const MachineInstr &MIb) const {
90   assert(MIa.mayLoadOrStore() && "MIa must be a load or store.");
91   assert(MIb.mayLoadOrStore() && "MIb must be a load or store.");
92 
93   if (MIa.hasUnmodeledSideEffects() || MIb.hasUnmodeledSideEffects() ||
94       MIa.hasOrderedMemoryRef() || MIb.hasOrderedMemoryRef())
95     return false;
96 
97   // Retrieve the base register, offset from the base register and width. Width
98   // is the size of memory that is being loaded/stored (e.g. 1, 2, 4).  If
99   // base registers are identical, and the offset of a lower memory access +
100   // the width doesn't overlap the offset of a higher memory access,
101   // then the memory accesses are different.
102   const TargetRegisterInfo *TRI = &getRegisterInfo();
103   const MachineOperand *BaseOpA = nullptr, *BaseOpB = nullptr;
104   int64_t OffsetA = 0, OffsetB = 0;
105   unsigned int WidthA = 0, WidthB = 0;
106   if (getMemOperandWithOffsetWidth(MIa, BaseOpA, OffsetA, WidthA, TRI) &&
107       getMemOperandWithOffsetWidth(MIb, BaseOpB, OffsetB, WidthB, TRI)) {
108     if (BaseOpA->isIdenticalTo(*BaseOpB)) {
109       int LowOffset = std::min(OffsetA, OffsetB);
110       int HighOffset = std::max(OffsetA, OffsetB);
111       int LowWidth = (LowOffset == OffsetA) ? WidthA : WidthB;
112       if (LowOffset + LowWidth <= HighOffset)
113         return true;
114     }
115   }
116   return false;
117 }
118 
119 bool LanaiInstrInfo::expandPostRAPseudo(MachineInstr & /*MI*/) const {
120   return false;
121 }
122 
123 static LPCC::CondCode getOppositeCondition(LPCC::CondCode CC) {
124   switch (CC) {
125   case LPCC::ICC_T: //  true
126     return LPCC::ICC_F;
127   case LPCC::ICC_F: //  false
128     return LPCC::ICC_T;
129   case LPCC::ICC_HI: //  high
130     return LPCC::ICC_LS;
131   case LPCC::ICC_LS: //  low or same
132     return LPCC::ICC_HI;
133   case LPCC::ICC_CC: //  carry cleared
134     return LPCC::ICC_CS;
135   case LPCC::ICC_CS: //  carry set
136     return LPCC::ICC_CC;
137   case LPCC::ICC_NE: //  not equal
138     return LPCC::ICC_EQ;
139   case LPCC::ICC_EQ: //  equal
140     return LPCC::ICC_NE;
141   case LPCC::ICC_VC: //  oVerflow cleared
142     return LPCC::ICC_VS;
143   case LPCC::ICC_VS: //  oVerflow set
144     return LPCC::ICC_VC;
145   case LPCC::ICC_PL: //  plus (note: 0 is "minus" too here)
146     return LPCC::ICC_MI;
147   case LPCC::ICC_MI: //  minus
148     return LPCC::ICC_PL;
149   case LPCC::ICC_GE: //  greater than or equal
150     return LPCC::ICC_LT;
151   case LPCC::ICC_LT: //  less than
152     return LPCC::ICC_GE;
153   case LPCC::ICC_GT: //  greater than
154     return LPCC::ICC_LE;
155   case LPCC::ICC_LE: //  less than or equal
156     return LPCC::ICC_GT;
157   default:
158     llvm_unreachable("Invalid condtional code");
159   }
160 }
161 
162 std::pair<unsigned, unsigned>
163 LanaiInstrInfo::decomposeMachineOperandsTargetFlags(unsigned TF) const {
164   return std::make_pair(TF, 0u);
165 }
166 
167 ArrayRef<std::pair<unsigned, const char *>>
168 LanaiInstrInfo::getSerializableDirectMachineOperandTargetFlags() const {
169   using namespace LanaiII;
170   static const std::pair<unsigned, const char *> TargetFlags[] = {
171       {MO_ABS_HI, "lanai-hi"},
172       {MO_ABS_LO, "lanai-lo"},
173       {MO_NO_FLAG, "lanai-nf"}};
174   return ArrayRef(TargetFlags);
175 }
176 
177 bool LanaiInstrInfo::analyzeCompare(const MachineInstr &MI, Register &SrcReg,
178                                     Register &SrcReg2, int64_t &CmpMask,
179                                     int64_t &CmpValue) const {
180   switch (MI.getOpcode()) {
181   default:
182     break;
183   case Lanai::SFSUB_F_RI_LO:
184   case Lanai::SFSUB_F_RI_HI:
185     SrcReg = MI.getOperand(0).getReg();
186     SrcReg2 = Register();
187     CmpMask = ~0;
188     CmpValue = MI.getOperand(1).getImm();
189     return true;
190   case Lanai::SFSUB_F_RR:
191     SrcReg = MI.getOperand(0).getReg();
192     SrcReg2 = MI.getOperand(1).getReg();
193     CmpMask = ~0;
194     CmpValue = 0;
195     return true;
196   }
197 
198   return false;
199 }
200 
201 // isRedundantFlagInstr - check whether the first instruction, whose only
202 // purpose is to update flags, can be made redundant.
203 // * SFSUB_F_RR can be made redundant by SUB_RI if the operands are the same.
204 // * SFSUB_F_RI can be made redundant by SUB_I if the operands are the same.
205 inline static bool isRedundantFlagInstr(MachineInstr *CmpI, unsigned SrcReg,
206                                         unsigned SrcReg2, int64_t ImmValue,
207                                         MachineInstr *OI) {
208   if (CmpI->getOpcode() == Lanai::SFSUB_F_RR &&
209       OI->getOpcode() == Lanai::SUB_R &&
210       ((OI->getOperand(1).getReg() == SrcReg &&
211         OI->getOperand(2).getReg() == SrcReg2) ||
212        (OI->getOperand(1).getReg() == SrcReg2 &&
213         OI->getOperand(2).getReg() == SrcReg)))
214     return true;
215 
216   if (((CmpI->getOpcode() == Lanai::SFSUB_F_RI_LO &&
217         OI->getOpcode() == Lanai::SUB_I_LO) ||
218        (CmpI->getOpcode() == Lanai::SFSUB_F_RI_HI &&
219         OI->getOpcode() == Lanai::SUB_I_HI)) &&
220       OI->getOperand(1).getReg() == SrcReg &&
221       OI->getOperand(2).getImm() == ImmValue)
222     return true;
223   return false;
224 }
225 
226 inline static unsigned flagSettingOpcodeVariant(unsigned OldOpcode) {
227   switch (OldOpcode) {
228   case Lanai::ADD_I_HI:
229     return Lanai::ADD_F_I_HI;
230   case Lanai::ADD_I_LO:
231     return Lanai::ADD_F_I_LO;
232   case Lanai::ADD_R:
233     return Lanai::ADD_F_R;
234   case Lanai::ADDC_I_HI:
235     return Lanai::ADDC_F_I_HI;
236   case Lanai::ADDC_I_LO:
237     return Lanai::ADDC_F_I_LO;
238   case Lanai::ADDC_R:
239     return Lanai::ADDC_F_R;
240   case Lanai::AND_I_HI:
241     return Lanai::AND_F_I_HI;
242   case Lanai::AND_I_LO:
243     return Lanai::AND_F_I_LO;
244   case Lanai::AND_R:
245     return Lanai::AND_F_R;
246   case Lanai::OR_I_HI:
247     return Lanai::OR_F_I_HI;
248   case Lanai::OR_I_LO:
249     return Lanai::OR_F_I_LO;
250   case Lanai::OR_R:
251     return Lanai::OR_F_R;
252   case Lanai::SL_I:
253     return Lanai::SL_F_I;
254   case Lanai::SRL_R:
255     return Lanai::SRL_F_R;
256   case Lanai::SA_I:
257     return Lanai::SA_F_I;
258   case Lanai::SRA_R:
259     return Lanai::SRA_F_R;
260   case Lanai::SUB_I_HI:
261     return Lanai::SUB_F_I_HI;
262   case Lanai::SUB_I_LO:
263     return Lanai::SUB_F_I_LO;
264   case Lanai::SUB_R:
265     return Lanai::SUB_F_R;
266   case Lanai::SUBB_I_HI:
267     return Lanai::SUBB_F_I_HI;
268   case Lanai::SUBB_I_LO:
269     return Lanai::SUBB_F_I_LO;
270   case Lanai::SUBB_R:
271     return Lanai::SUBB_F_R;
272   case Lanai::XOR_I_HI:
273     return Lanai::XOR_F_I_HI;
274   case Lanai::XOR_I_LO:
275     return Lanai::XOR_F_I_LO;
276   case Lanai::XOR_R:
277     return Lanai::XOR_F_R;
278   default:
279     return Lanai::NOP;
280   }
281 }
282 
283 bool LanaiInstrInfo::optimizeCompareInstr(
284     MachineInstr &CmpInstr, Register SrcReg, Register SrcReg2,
285     int64_t /*CmpMask*/, int64_t CmpValue,
286     const MachineRegisterInfo *MRI) const {
287   // Get the unique definition of SrcReg.
288   MachineInstr *MI = MRI->getUniqueVRegDef(SrcReg);
289   if (!MI)
290     return false;
291 
292   // Get ready to iterate backward from CmpInstr.
293   MachineBasicBlock::iterator I = CmpInstr, E = MI,
294                               B = CmpInstr.getParent()->begin();
295 
296   // Early exit if CmpInstr is at the beginning of the BB.
297   if (I == B)
298     return false;
299 
300   // There are two possible candidates which can be changed to set SR:
301   // One is MI, the other is a SUB instruction.
302   // * For SFSUB_F_RR(r1,r2), we are looking for SUB(r1,r2) or SUB(r2,r1).
303   // * For SFSUB_F_RI(r1, CmpValue), we are looking for SUB(r1, CmpValue).
304   MachineInstr *Sub = nullptr;
305   if (SrcReg2 != 0)
306     // MI is not a candidate to transform into a flag setting instruction.
307     MI = nullptr;
308   else if (MI->getParent() != CmpInstr.getParent() || CmpValue != 0) {
309     // Conservatively refuse to convert an instruction which isn't in the same
310     // BB as the comparison. Don't return if SFSUB_F_RI and CmpValue != 0 as Sub
311     // may still be a candidate.
312     if (CmpInstr.getOpcode() == Lanai::SFSUB_F_RI_LO)
313       MI = nullptr;
314     else
315       return false;
316   }
317 
318   // Check that SR isn't set between the comparison instruction and the
319   // instruction we want to change while searching for Sub.
320   const TargetRegisterInfo *TRI = &getRegisterInfo();
321   for (--I; I != E; --I) {
322     const MachineInstr &Instr = *I;
323 
324     if (Instr.modifiesRegister(Lanai::SR, TRI) ||
325         Instr.readsRegister(Lanai::SR, TRI))
326       // This instruction modifies or uses SR after the one we want to change.
327       // We can't do this transformation.
328       return false;
329 
330     // Check whether CmpInstr can be made redundant by the current instruction.
331     if (isRedundantFlagInstr(&CmpInstr, SrcReg, SrcReg2, CmpValue, &*I)) {
332       Sub = &*I;
333       break;
334     }
335 
336     // Don't search outside the containing basic block.
337     if (I == B)
338       return false;
339   }
340 
341   // Return false if no candidates exist.
342   if (!MI && !Sub)
343     return false;
344 
345   // The single candidate is called MI.
346   if (!MI)
347     MI = Sub;
348 
349   if (flagSettingOpcodeVariant(MI->getOpcode()) != Lanai::NOP) {
350     bool isSafe = false;
351 
352     SmallVector<std::pair<MachineOperand *, LPCC::CondCode>, 4>
353         OperandsToUpdate;
354     I = CmpInstr;
355     E = CmpInstr.getParent()->end();
356     while (!isSafe && ++I != E) {
357       const MachineInstr &Instr = *I;
358       for (unsigned IO = 0, EO = Instr.getNumOperands(); !isSafe && IO != EO;
359            ++IO) {
360         const MachineOperand &MO = Instr.getOperand(IO);
361         if (MO.isRegMask() && MO.clobbersPhysReg(Lanai::SR)) {
362           isSafe = true;
363           break;
364         }
365         if (!MO.isReg() || MO.getReg() != Lanai::SR)
366           continue;
367         if (MO.isDef()) {
368           isSafe = true;
369           break;
370         }
371         // Condition code is after the operand before SR.
372         LPCC::CondCode CC;
373         CC = (LPCC::CondCode)Instr.getOperand(IO - 1).getImm();
374 
375         if (Sub) {
376           LPCC::CondCode NewCC = getOppositeCondition(CC);
377           if (NewCC == LPCC::ICC_T)
378             return false;
379           // If we have SUB(r1, r2) and CMP(r2, r1), the condition code based on
380           // CMP needs to be updated to be based on SUB.  Push the condition
381           // code operands to OperandsToUpdate.  If it is safe to remove
382           // CmpInstr, the condition code of these operands will be modified.
383           if (SrcReg2 != 0 && Sub->getOperand(1).getReg() == SrcReg2 &&
384               Sub->getOperand(2).getReg() == SrcReg) {
385             OperandsToUpdate.push_back(
386                 std::make_pair(&((*I).getOperand(IO - 1)), NewCC));
387           }
388         } else {
389           // No Sub, so this is x = <op> y, z; cmp x, 0.
390           switch (CC) {
391           case LPCC::ICC_EQ: // Z
392           case LPCC::ICC_NE: // Z
393           case LPCC::ICC_MI: // N
394           case LPCC::ICC_PL: // N
395           case LPCC::ICC_F:  // none
396           case LPCC::ICC_T:  // none
397             // SR can be used multiple times, we should continue.
398             break;
399           case LPCC::ICC_CS: // C
400           case LPCC::ICC_CC: // C
401           case LPCC::ICC_VS: // V
402           case LPCC::ICC_VC: // V
403           case LPCC::ICC_HI: // C Z
404           case LPCC::ICC_LS: // C Z
405           case LPCC::ICC_GE: // N V
406           case LPCC::ICC_LT: // N V
407           case LPCC::ICC_GT: // Z N V
408           case LPCC::ICC_LE: // Z N V
409             // The instruction uses the V bit or C bit which is not safe.
410             return false;
411           case LPCC::UNKNOWN:
412             return false;
413           }
414         }
415       }
416     }
417 
418     // If SR is not killed nor re-defined, we should check whether it is
419     // live-out. If it is live-out, do not optimize.
420     if (!isSafe) {
421       MachineBasicBlock *MBB = CmpInstr.getParent();
422       for (const MachineBasicBlock *Succ : MBB->successors())
423         if (Succ->isLiveIn(Lanai::SR))
424           return false;
425     }
426 
427     // Toggle the optional operand to SR.
428     MI->setDesc(get(flagSettingOpcodeVariant(MI->getOpcode())));
429     MI->addRegisterDefined(Lanai::SR);
430     CmpInstr.eraseFromParent();
431     return true;
432   }
433 
434   return false;
435 }
436 
437 bool LanaiInstrInfo::analyzeSelect(const MachineInstr &MI,
438                                    SmallVectorImpl<MachineOperand> &Cond,
439                                    unsigned &TrueOp, unsigned &FalseOp,
440                                    bool &Optimizable) const {
441   assert(MI.getOpcode() == Lanai::SELECT && "unknown select instruction");
442   // Select operands:
443   // 0: Def.
444   // 1: True use.
445   // 2: False use.
446   // 3: Condition code.
447   TrueOp = 1;
448   FalseOp = 2;
449   Cond.push_back(MI.getOperand(3));
450   Optimizable = true;
451   return false;
452 }
453 
454 // Identify instructions that can be folded into a SELECT instruction, and
455 // return the defining instruction.
456 static MachineInstr *canFoldIntoSelect(Register Reg,
457                                        const MachineRegisterInfo &MRI) {
458   if (!Reg.isVirtual())
459     return nullptr;
460   if (!MRI.hasOneNonDBGUse(Reg))
461     return nullptr;
462   MachineInstr *MI = MRI.getVRegDef(Reg);
463   if (!MI)
464     return nullptr;
465   // MI is folded into the SELECT by predicating it.
466   if (!MI->isPredicable())
467     return nullptr;
468   // Check if MI has any non-dead defs or physreg uses. This also detects
469   // predicated instructions which will be reading SR.
470   for (const MachineOperand &MO : llvm::drop_begin(MI->operands(), 1)) {
471     // Reject frame index operands.
472     if (MO.isFI() || MO.isCPI() || MO.isJTI())
473       return nullptr;
474     if (!MO.isReg())
475       continue;
476     // MI can't have any tied operands, that would conflict with predication.
477     if (MO.isTied())
478       return nullptr;
479     if (MO.getReg().isPhysical())
480       return nullptr;
481     if (MO.isDef() && !MO.isDead())
482       return nullptr;
483   }
484   bool DontMoveAcrossStores = true;
485   if (!MI->isSafeToMove(/*AliasAnalysis=*/nullptr, DontMoveAcrossStores))
486     return nullptr;
487   return MI;
488 }
489 
490 MachineInstr *
491 LanaiInstrInfo::optimizeSelect(MachineInstr &MI,
492                                SmallPtrSetImpl<MachineInstr *> &SeenMIs,
493                                bool /*PreferFalse*/) const {
494   assert(MI.getOpcode() == Lanai::SELECT && "unknown select instruction");
495   MachineRegisterInfo &MRI = MI.getParent()->getParent()->getRegInfo();
496   MachineInstr *DefMI = canFoldIntoSelect(MI.getOperand(1).getReg(), MRI);
497   bool Invert = !DefMI;
498   if (!DefMI)
499     DefMI = canFoldIntoSelect(MI.getOperand(2).getReg(), MRI);
500   if (!DefMI)
501     return nullptr;
502 
503   // Find new register class to use.
504   MachineOperand FalseReg = MI.getOperand(Invert ? 1 : 2);
505   Register DestReg = MI.getOperand(0).getReg();
506   const TargetRegisterClass *PreviousClass = MRI.getRegClass(FalseReg.getReg());
507   if (!MRI.constrainRegClass(DestReg, PreviousClass))
508     return nullptr;
509 
510   // Create a new predicated version of DefMI.
511   MachineInstrBuilder NewMI =
512       BuildMI(*MI.getParent(), MI, MI.getDebugLoc(), DefMI->getDesc(), DestReg);
513 
514   // Copy all the DefMI operands, excluding its (null) predicate.
515   const MCInstrDesc &DefDesc = DefMI->getDesc();
516   for (unsigned i = 1, e = DefDesc.getNumOperands();
517        i != e && !DefDesc.operands()[i].isPredicate(); ++i)
518     NewMI.add(DefMI->getOperand(i));
519 
520   unsigned CondCode = MI.getOperand(3).getImm();
521   if (Invert)
522     NewMI.addImm(getOppositeCondition(LPCC::CondCode(CondCode)));
523   else
524     NewMI.addImm(CondCode);
525   NewMI.copyImplicitOps(MI);
526 
527   // The output register value when the predicate is false is an implicit
528   // register operand tied to the first def.  The tie makes the register
529   // allocator ensure the FalseReg is allocated the same register as operand 0.
530   FalseReg.setImplicit();
531   NewMI.add(FalseReg);
532   NewMI->tieOperands(0, NewMI->getNumOperands() - 1);
533 
534   // Update SeenMIs set: register newly created MI and erase removed DefMI.
535   SeenMIs.insert(NewMI);
536   SeenMIs.erase(DefMI);
537 
538   // If MI is inside a loop, and DefMI is outside the loop, then kill flags on
539   // DefMI would be invalid when transferred inside the loop.  Checking for a
540   // loop is expensive, but at least remove kill flags if they are in different
541   // BBs.
542   if (DefMI->getParent() != MI.getParent())
543     NewMI->clearKillInfo();
544 
545   // The caller will erase MI, but not DefMI.
546   DefMI->eraseFromParent();
547   return NewMI;
548 }
549 
550 // The analyzeBranch function is used to examine conditional instructions and
551 // remove unnecessary instructions. This method is used by BranchFolder and
552 // IfConverter machine function passes to improve the CFG.
553 // - TrueBlock is set to the destination if condition evaluates true (it is the
554 //   nullptr if the destination is the fall-through branch);
555 // - FalseBlock is set to the destination if condition evaluates to false (it
556 //   is the nullptr if the branch is unconditional);
557 // - condition is populated with machine operands needed to generate the branch
558 //   to insert in insertBranch;
559 // Returns: false if branch could successfully be analyzed.
560 bool LanaiInstrInfo::analyzeBranch(MachineBasicBlock &MBB,
561                                    MachineBasicBlock *&TrueBlock,
562                                    MachineBasicBlock *&FalseBlock,
563                                    SmallVectorImpl<MachineOperand> &Condition,
564                                    bool AllowModify) const {
565   // Iterator to current instruction being considered.
566   MachineBasicBlock::iterator Instruction = MBB.end();
567 
568   // Start from the bottom of the block and work up, examining the
569   // terminator instructions.
570   while (Instruction != MBB.begin()) {
571     --Instruction;
572 
573     // Skip over debug instructions.
574     if (Instruction->isDebugInstr())
575       continue;
576 
577     // Working from the bottom, when we see a non-terminator
578     // instruction, we're done.
579     if (!isUnpredicatedTerminator(*Instruction))
580       break;
581 
582     // A terminator that isn't a branch can't easily be handled
583     // by this analysis.
584     if (!Instruction->isBranch())
585       return true;
586 
587     // Handle unconditional branches.
588     if (Instruction->getOpcode() == Lanai::BT) {
589       if (!AllowModify) {
590         TrueBlock = Instruction->getOperand(0).getMBB();
591         continue;
592       }
593 
594       // If the block has any instructions after a branch, delete them.
595       MBB.erase(std::next(Instruction), MBB.end());
596 
597       Condition.clear();
598       FalseBlock = nullptr;
599 
600       // Delete the jump if it's equivalent to a fall-through.
601       if (MBB.isLayoutSuccessor(Instruction->getOperand(0).getMBB())) {
602         TrueBlock = nullptr;
603         Instruction->eraseFromParent();
604         Instruction = MBB.end();
605         continue;
606       }
607 
608       // TrueBlock is used to indicate the unconditional destination.
609       TrueBlock = Instruction->getOperand(0).getMBB();
610       continue;
611     }
612 
613     // Handle conditional branches
614     unsigned Opcode = Instruction->getOpcode();
615     if (Opcode != Lanai::BRCC)
616       return true; // Unknown opcode.
617 
618     // Multiple conditional branches are not handled here so only proceed if
619     // there are no conditions enqueued.
620     if (Condition.empty()) {
621       LPCC::CondCode BranchCond =
622           static_cast<LPCC::CondCode>(Instruction->getOperand(1).getImm());
623 
624       // TrueBlock is the target of the previously seen unconditional branch.
625       FalseBlock = TrueBlock;
626       TrueBlock = Instruction->getOperand(0).getMBB();
627       Condition.push_back(MachineOperand::CreateImm(BranchCond));
628       continue;
629     }
630 
631     // Multiple conditional branches are not handled.
632     return true;
633   }
634 
635   // Return false indicating branch successfully analyzed.
636   return false;
637 }
638 
639 // reverseBranchCondition - Reverses the branch condition of the specified
640 // condition list, returning false on success and true if it cannot be
641 // reversed.
642 bool LanaiInstrInfo::reverseBranchCondition(
643     SmallVectorImpl<llvm::MachineOperand> &Condition) const {
644   assert((Condition.size() == 1) &&
645          "Lanai branch conditions should have one component.");
646 
647   LPCC::CondCode BranchCond =
648       static_cast<LPCC::CondCode>(Condition[0].getImm());
649   Condition[0].setImm(getOppositeCondition(BranchCond));
650   return false;
651 }
652 
653 // Insert the branch with condition specified in condition and given targets
654 // (TrueBlock and FalseBlock). This function returns the number of machine
655 // instructions inserted.
656 unsigned LanaiInstrInfo::insertBranch(MachineBasicBlock &MBB,
657                                       MachineBasicBlock *TrueBlock,
658                                       MachineBasicBlock *FalseBlock,
659                                       ArrayRef<MachineOperand> Condition,
660                                       const DebugLoc &DL,
661                                       int *BytesAdded) const {
662   // Shouldn't be a fall through.
663   assert(TrueBlock && "insertBranch must not be told to insert a fallthrough");
664   assert(!BytesAdded && "code size not handled");
665 
666   // If condition is empty then an unconditional branch is being inserted.
667   if (Condition.empty()) {
668     assert(!FalseBlock && "Unconditional branch with multiple successors!");
669     BuildMI(&MBB, DL, get(Lanai::BT)).addMBB(TrueBlock);
670     return 1;
671   }
672 
673   // Else a conditional branch is inserted.
674   assert((Condition.size() == 1) &&
675          "Lanai branch conditions should have one component.");
676   unsigned ConditionalCode = Condition[0].getImm();
677   BuildMI(&MBB, DL, get(Lanai::BRCC)).addMBB(TrueBlock).addImm(ConditionalCode);
678 
679   // If no false block, then false behavior is fall through and no branch needs
680   // to be inserted.
681   if (!FalseBlock)
682     return 1;
683 
684   BuildMI(&MBB, DL, get(Lanai::BT)).addMBB(FalseBlock);
685   return 2;
686 }
687 
688 unsigned LanaiInstrInfo::removeBranch(MachineBasicBlock &MBB,
689                                       int *BytesRemoved) const {
690   assert(!BytesRemoved && "code size not handled");
691 
692   MachineBasicBlock::iterator Instruction = MBB.end();
693   unsigned Count = 0;
694 
695   while (Instruction != MBB.begin()) {
696     --Instruction;
697     if (Instruction->isDebugInstr())
698       continue;
699     if (Instruction->getOpcode() != Lanai::BT &&
700         Instruction->getOpcode() != Lanai::BRCC) {
701       break;
702     }
703 
704     // Remove the branch.
705     Instruction->eraseFromParent();
706     Instruction = MBB.end();
707     ++Count;
708   }
709 
710   return Count;
711 }
712 
713 unsigned LanaiInstrInfo::isLoadFromStackSlot(const MachineInstr &MI,
714                                              int &FrameIndex) const {
715   if (MI.getOpcode() == Lanai::LDW_RI)
716     if (MI.getOperand(1).isFI() && MI.getOperand(2).isImm() &&
717         MI.getOperand(2).getImm() == 0) {
718       FrameIndex = MI.getOperand(1).getIndex();
719       return MI.getOperand(0).getReg();
720     }
721   return 0;
722 }
723 
724 unsigned LanaiInstrInfo::isLoadFromStackSlotPostFE(const MachineInstr &MI,
725                                                    int &FrameIndex) const {
726   if (MI.getOpcode() == Lanai::LDW_RI) {
727     unsigned Reg;
728     if ((Reg = isLoadFromStackSlot(MI, FrameIndex)))
729       return Reg;
730     // Check for post-frame index elimination operations
731     SmallVector<const MachineMemOperand *, 1> Accesses;
732     if (hasLoadFromStackSlot(MI, Accesses)){
733       FrameIndex =
734           cast<FixedStackPseudoSourceValue>(Accesses.front()->getPseudoValue())
735               ->getFrameIndex();
736       return 1;
737     }
738   }
739   return 0;
740 }
741 
742 unsigned LanaiInstrInfo::isStoreToStackSlot(const MachineInstr &MI,
743                                             int &FrameIndex) const {
744   if (MI.getOpcode() == Lanai::SW_RI)
745     if (MI.getOperand(0).isFI() && MI.getOperand(1).isImm() &&
746         MI.getOperand(1).getImm() == 0) {
747       FrameIndex = MI.getOperand(0).getIndex();
748       return MI.getOperand(2).getReg();
749     }
750   return 0;
751 }
752 
753 bool LanaiInstrInfo::getMemOperandWithOffsetWidth(
754     const MachineInstr &LdSt, const MachineOperand *&BaseOp, int64_t &Offset,
755     unsigned &Width, const TargetRegisterInfo * /*TRI*/) const {
756   // Handle only loads/stores with base register followed by immediate offset
757   // and with add as ALU op.
758   if (LdSt.getNumOperands() != 4)
759     return false;
760   if (!LdSt.getOperand(1).isReg() || !LdSt.getOperand(2).isImm() ||
761       !(LdSt.getOperand(3).isImm() && LdSt.getOperand(3).getImm() == LPAC::ADD))
762     return false;
763 
764   switch (LdSt.getOpcode()) {
765   default:
766     return false;
767   case Lanai::LDW_RI:
768   case Lanai::LDW_RR:
769   case Lanai::SW_RR:
770   case Lanai::SW_RI:
771     Width = 4;
772     break;
773   case Lanai::LDHs_RI:
774   case Lanai::LDHz_RI:
775   case Lanai::STH_RI:
776     Width = 2;
777     break;
778   case Lanai::LDBs_RI:
779   case Lanai::LDBz_RI:
780   case Lanai::STB_RI:
781     Width = 1;
782     break;
783   }
784 
785   BaseOp = &LdSt.getOperand(1);
786   Offset = LdSt.getOperand(2).getImm();
787 
788   if (!BaseOp->isReg())
789     return false;
790 
791   return true;
792 }
793 
794 bool LanaiInstrInfo::getMemOperandsWithOffsetWidth(
795     const MachineInstr &LdSt, SmallVectorImpl<const MachineOperand *> &BaseOps,
796     int64_t &Offset, bool &OffsetIsScalable, unsigned &Width,
797     const TargetRegisterInfo *TRI) const {
798   switch (LdSt.getOpcode()) {
799   default:
800     return false;
801   case Lanai::LDW_RI:
802   case Lanai::LDW_RR:
803   case Lanai::SW_RR:
804   case Lanai::SW_RI:
805   case Lanai::LDHs_RI:
806   case Lanai::LDHz_RI:
807   case Lanai::STH_RI:
808   case Lanai::LDBs_RI:
809   case Lanai::LDBz_RI:
810     const MachineOperand *BaseOp;
811     OffsetIsScalable = false;
812     if (!getMemOperandWithOffsetWidth(LdSt, BaseOp, Offset, Width, TRI))
813       return false;
814     BaseOps.push_back(BaseOp);
815     return true;
816   }
817 }
818