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/Support/ErrorHandling.h"
23 #include "llvm/Support/TargetRegistry.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                                  unsigned DestinationRegister,
38                                  unsigned 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     unsigned SourceRegister, bool IsKill, int FrameIndex,
52     const TargetRegisterClass *RegisterClass,
53     const TargetRegisterInfo * /*RegisterInfo*/) 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     unsigned DestinationRegister, int FrameIndex,
72     const TargetRegisterClass *RegisterClass,
73     const TargetRegisterInfo * /*RegisterInfo*/) 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,
90     AliasAnalysis * /*AA*/) const {
91   assert(MIa.mayLoadOrStore() && "MIa must be a load or store.");
92   assert(MIb.mayLoadOrStore() && "MIb must be a load or store.");
93 
94   if (MIa.hasUnmodeledSideEffects() || MIb.hasUnmodeledSideEffects() ||
95       MIa.hasOrderedMemoryRef() || MIb.hasOrderedMemoryRef())
96     return false;
97 
98   // Retrieve the base register, offset from the base register and width. Width
99   // is the size of memory that is being loaded/stored (e.g. 1, 2, 4).  If
100   // base registers are identical, and the offset of a lower memory access +
101   // the width doesn't overlap the offset of a higher memory access,
102   // then the memory accesses are different.
103   const TargetRegisterInfo *TRI = &getRegisterInfo();
104   const MachineOperand *BaseOpA = nullptr, *BaseOpB = nullptr;
105   int64_t OffsetA = 0, OffsetB = 0;
106   unsigned int WidthA = 0, WidthB = 0;
107   if (getMemOperandWithOffsetWidth(MIa, BaseOpA, OffsetA, WidthA, TRI) &&
108       getMemOperandWithOffsetWidth(MIb, BaseOpB, OffsetB, WidthB, TRI)) {
109     if (BaseOpA->isIdenticalTo(*BaseOpB)) {
110       int LowOffset = std::min(OffsetA, OffsetB);
111       int HighOffset = std::max(OffsetA, OffsetB);
112       int LowWidth = (LowOffset == OffsetA) ? WidthA : WidthB;
113       if (LowOffset + LowWidth <= HighOffset)
114         return true;
115     }
116   }
117   return false;
118 }
119 
120 bool LanaiInstrInfo::expandPostRAPseudo(MachineInstr & /*MI*/) const {
121   return false;
122 }
123 
124 static LPCC::CondCode getOppositeCondition(LPCC::CondCode CC) {
125   switch (CC) {
126   case LPCC::ICC_T: //  true
127     return LPCC::ICC_F;
128   case LPCC::ICC_F: //  false
129     return LPCC::ICC_T;
130   case LPCC::ICC_HI: //  high
131     return LPCC::ICC_LS;
132   case LPCC::ICC_LS: //  low or same
133     return LPCC::ICC_HI;
134   case LPCC::ICC_CC: //  carry cleared
135     return LPCC::ICC_CS;
136   case LPCC::ICC_CS: //  carry set
137     return LPCC::ICC_CC;
138   case LPCC::ICC_NE: //  not equal
139     return LPCC::ICC_EQ;
140   case LPCC::ICC_EQ: //  equal
141     return LPCC::ICC_NE;
142   case LPCC::ICC_VC: //  oVerflow cleared
143     return LPCC::ICC_VS;
144   case LPCC::ICC_VS: //  oVerflow set
145     return LPCC::ICC_VC;
146   case LPCC::ICC_PL: //  plus (note: 0 is "minus" too here)
147     return LPCC::ICC_MI;
148   case LPCC::ICC_MI: //  minus
149     return LPCC::ICC_PL;
150   case LPCC::ICC_GE: //  greater than or equal
151     return LPCC::ICC_LT;
152   case LPCC::ICC_LT: //  less than
153     return LPCC::ICC_GE;
154   case LPCC::ICC_GT: //  greater than
155     return LPCC::ICC_LE;
156   case LPCC::ICC_LE: //  less than or equal
157     return LPCC::ICC_GT;
158   default:
159     llvm_unreachable("Invalid condtional code");
160   }
161 }
162 
163 std::pair<unsigned, unsigned>
164 LanaiInstrInfo::decomposeMachineOperandsTargetFlags(unsigned TF) const {
165   return std::make_pair(TF, 0u);
166 }
167 
168 ArrayRef<std::pair<unsigned, const char *>>
169 LanaiInstrInfo::getSerializableDirectMachineOperandTargetFlags() const {
170   using namespace LanaiII;
171   static const std::pair<unsigned, const char *> TargetFlags[] = {
172       {MO_ABS_HI, "lanai-hi"},
173       {MO_ABS_LO, "lanai-lo"},
174       {MO_NO_FLAG, "lanai-nf"}};
175   return makeArrayRef(TargetFlags);
176 }
177 
178 bool LanaiInstrInfo::analyzeCompare(const MachineInstr &MI, unsigned &SrcReg,
179                                     unsigned &SrcReg2, int &CmpMask,
180                                     int &CmpValue) const {
181   switch (MI.getOpcode()) {
182   default:
183     break;
184   case Lanai::SFSUB_F_RI_LO:
185   case Lanai::SFSUB_F_RI_HI:
186     SrcReg = MI.getOperand(0).getReg();
187     SrcReg2 = 0;
188     CmpMask = ~0;
189     CmpValue = MI.getOperand(1).getImm();
190     return true;
191   case Lanai::SFSUB_F_RR:
192     SrcReg = MI.getOperand(0).getReg();
193     SrcReg2 = MI.getOperand(1).getReg();
194     CmpMask = ~0;
195     CmpValue = 0;
196     return true;
197   }
198 
199   return false;
200 }
201 
202 // isRedundantFlagInstr - check whether the first instruction, whose only
203 // purpose is to update flags, can be made redundant.
204 // * SFSUB_F_RR can be made redundant by SUB_RI if the operands are the same.
205 // * SFSUB_F_RI can be made redundant by SUB_I if the operands are the same.
206 inline static bool isRedundantFlagInstr(MachineInstr *CmpI, unsigned SrcReg,
207                                         unsigned SrcReg2, int ImmValue,
208                                         MachineInstr *OI) {
209   if (CmpI->getOpcode() == Lanai::SFSUB_F_RR &&
210       OI->getOpcode() == Lanai::SUB_R &&
211       ((OI->getOperand(1).getReg() == SrcReg &&
212         OI->getOperand(2).getReg() == SrcReg2) ||
213        (OI->getOperand(1).getReg() == SrcReg2 &&
214         OI->getOperand(2).getReg() == SrcReg)))
215     return true;
216 
217   if (((CmpI->getOpcode() == Lanai::SFSUB_F_RI_LO &&
218         OI->getOpcode() == Lanai::SUB_I_LO) ||
219        (CmpI->getOpcode() == Lanai::SFSUB_F_RI_HI &&
220         OI->getOpcode() == Lanai::SUB_I_HI)) &&
221       OI->getOperand(1).getReg() == SrcReg &&
222       OI->getOperand(2).getImm() == ImmValue)
223     return true;
224   return false;
225 }
226 
227 inline static unsigned flagSettingOpcodeVariant(unsigned OldOpcode) {
228   switch (OldOpcode) {
229   case Lanai::ADD_I_HI:
230     return Lanai::ADD_F_I_HI;
231   case Lanai::ADD_I_LO:
232     return Lanai::ADD_F_I_LO;
233   case Lanai::ADD_R:
234     return Lanai::ADD_F_R;
235   case Lanai::ADDC_I_HI:
236     return Lanai::ADDC_F_I_HI;
237   case Lanai::ADDC_I_LO:
238     return Lanai::ADDC_F_I_LO;
239   case Lanai::ADDC_R:
240     return Lanai::ADDC_F_R;
241   case Lanai::AND_I_HI:
242     return Lanai::AND_F_I_HI;
243   case Lanai::AND_I_LO:
244     return Lanai::AND_F_I_LO;
245   case Lanai::AND_R:
246     return Lanai::AND_F_R;
247   case Lanai::OR_I_HI:
248     return Lanai::OR_F_I_HI;
249   case Lanai::OR_I_LO:
250     return Lanai::OR_F_I_LO;
251   case Lanai::OR_R:
252     return Lanai::OR_F_R;
253   case Lanai::SL_I:
254     return Lanai::SL_F_I;
255   case Lanai::SRL_R:
256     return Lanai::SRL_F_R;
257   case Lanai::SA_I:
258     return Lanai::SA_F_I;
259   case Lanai::SRA_R:
260     return Lanai::SRA_F_R;
261   case Lanai::SUB_I_HI:
262     return Lanai::SUB_F_I_HI;
263   case Lanai::SUB_I_LO:
264     return Lanai::SUB_F_I_LO;
265   case Lanai::SUB_R:
266     return Lanai::SUB_F_R;
267   case Lanai::SUBB_I_HI:
268     return Lanai::SUBB_F_I_HI;
269   case Lanai::SUBB_I_LO:
270     return Lanai::SUBB_F_I_LO;
271   case Lanai::SUBB_R:
272     return Lanai::SUBB_F_R;
273   case Lanai::XOR_I_HI:
274     return Lanai::XOR_F_I_HI;
275   case Lanai::XOR_I_LO:
276     return Lanai::XOR_F_I_LO;
277   case Lanai::XOR_R:
278     return Lanai::XOR_F_R;
279   default:
280     return Lanai::NOP;
281   }
282 }
283 
284 bool LanaiInstrInfo::optimizeCompareInstr(
285     MachineInstr &CmpInstr, unsigned SrcReg, unsigned SrcReg2, int /*CmpMask*/,
286     int CmpValue, 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 (MachineBasicBlock::succ_iterator SI = MBB->succ_begin(),
423                                             SE = MBB->succ_end();
424            SI != SE; ++SI)
425         if ((*SI)->isLiveIn(Lanai::SR))
426           return false;
427     }
428 
429     // Toggle the optional operand to SR.
430     MI->setDesc(get(flagSettingOpcodeVariant(MI->getOpcode())));
431     MI->addRegisterDefined(Lanai::SR);
432     CmpInstr.eraseFromParent();
433     return true;
434   }
435 
436   return false;
437 }
438 
439 bool LanaiInstrInfo::analyzeSelect(const MachineInstr &MI,
440                                    SmallVectorImpl<MachineOperand> &Cond,
441                                    unsigned &TrueOp, unsigned &FalseOp,
442                                    bool &Optimizable) const {
443   assert(MI.getOpcode() == Lanai::SELECT && "unknown select instruction");
444   // Select operands:
445   // 0: Def.
446   // 1: True use.
447   // 2: False use.
448   // 3: Condition code.
449   TrueOp = 1;
450   FalseOp = 2;
451   Cond.push_back(MI.getOperand(3));
452   Optimizable = true;
453   return false;
454 }
455 
456 // Identify instructions that can be folded into a SELECT instruction, and
457 // return the defining instruction.
458 static MachineInstr *canFoldIntoSelect(unsigned Reg,
459                                        const MachineRegisterInfo &MRI) {
460   if (!TargetRegisterInfo::isVirtualRegister(Reg))
461     return nullptr;
462   if (!MRI.hasOneNonDBGUse(Reg))
463     return nullptr;
464   MachineInstr *MI = MRI.getVRegDef(Reg);
465   if (!MI)
466     return nullptr;
467   // MI is folded into the SELECT by predicating it.
468   if (!MI->isPredicable())
469     return nullptr;
470   // Check if MI has any non-dead defs or physreg uses. This also detects
471   // predicated instructions which will be reading SR.
472   for (unsigned i = 1, e = MI->getNumOperands(); i != e; ++i) {
473     const MachineOperand &MO = MI->getOperand(i);
474     // Reject frame index operands.
475     if (MO.isFI() || MO.isCPI() || MO.isJTI())
476       return nullptr;
477     if (!MO.isReg())
478       continue;
479     // MI can't have any tied operands, that would conflict with predication.
480     if (MO.isTied())
481       return nullptr;
482     if (TargetRegisterInfo::isPhysicalRegister(MO.getReg()))
483       return nullptr;
484     if (MO.isDef() && !MO.isDead())
485       return nullptr;
486   }
487   bool DontMoveAcrossStores = true;
488   if (!MI->isSafeToMove(/*AliasAnalysis=*/nullptr, DontMoveAcrossStores))
489     return nullptr;
490   return MI;
491 }
492 
493 MachineInstr *
494 LanaiInstrInfo::optimizeSelect(MachineInstr &MI,
495                                SmallPtrSetImpl<MachineInstr *> &SeenMIs,
496                                bool /*PreferFalse*/) const {
497   assert(MI.getOpcode() == Lanai::SELECT && "unknown select instruction");
498   MachineRegisterInfo &MRI = MI.getParent()->getParent()->getRegInfo();
499   MachineInstr *DefMI = canFoldIntoSelect(MI.getOperand(1).getReg(), MRI);
500   bool Invert = !DefMI;
501   if (!DefMI)
502     DefMI = canFoldIntoSelect(MI.getOperand(2).getReg(), MRI);
503   if (!DefMI)
504     return nullptr;
505 
506   // Find new register class to use.
507   MachineOperand FalseReg = MI.getOperand(Invert ? 1 : 2);
508   unsigned DestReg = MI.getOperand(0).getReg();
509   const TargetRegisterClass *PreviousClass = MRI.getRegClass(FalseReg.getReg());
510   if (!MRI.constrainRegClass(DestReg, PreviousClass))
511     return nullptr;
512 
513   // Create a new predicated version of DefMI.
514   MachineInstrBuilder NewMI =
515       BuildMI(*MI.getParent(), MI, MI.getDebugLoc(), DefMI->getDesc(), DestReg);
516 
517   // Copy all the DefMI operands, excluding its (null) predicate.
518   const MCInstrDesc &DefDesc = DefMI->getDesc();
519   for (unsigned i = 1, e = DefDesc.getNumOperands();
520        i != e && !DefDesc.OpInfo[i].isPredicate(); ++i)
521     NewMI.add(DefMI->getOperand(i));
522 
523   unsigned CondCode = MI.getOperand(3).getImm();
524   if (Invert)
525     NewMI.addImm(getOppositeCondition(LPCC::CondCode(CondCode)));
526   else
527     NewMI.addImm(CondCode);
528   NewMI.copyImplicitOps(MI);
529 
530   // The output register value when the predicate is false is an implicit
531   // register operand tied to the first def.  The tie makes the register
532   // allocator ensure the FalseReg is allocated the same register as operand 0.
533   FalseReg.setImplicit();
534   NewMI.add(FalseReg);
535   NewMI->tieOperands(0, NewMI->getNumOperands() - 1);
536 
537   // Update SeenMIs set: register newly created MI and erase removed DefMI.
538   SeenMIs.insert(NewMI);
539   SeenMIs.erase(DefMI);
540 
541   // If MI is inside a loop, and DefMI is outside the loop, then kill flags on
542   // DefMI would be invalid when transferred inside the loop.  Checking for a
543   // loop is expensive, but at least remove kill flags if they are in different
544   // BBs.
545   if (DefMI->getParent() != MI.getParent())
546     NewMI->clearKillInfo();
547 
548   // The caller will erase MI, but not DefMI.
549   DefMI->eraseFromParent();
550   return NewMI;
551 }
552 
553 // The analyzeBranch function is used to examine conditional instructions and
554 // remove unnecessary instructions. This method is used by BranchFolder and
555 // IfConverter machine function passes to improve the CFG.
556 // - TrueBlock is set to the destination if condition evaluates true (it is the
557 //   nullptr if the destination is the fall-through branch);
558 // - FalseBlock is set to the destination if condition evaluates to false (it
559 //   is the nullptr if the branch is unconditional);
560 // - condition is populated with machine operands needed to generate the branch
561 //   to insert in insertBranch;
562 // Returns: false if branch could successfully be analyzed.
563 bool LanaiInstrInfo::analyzeBranch(MachineBasicBlock &MBB,
564                                    MachineBasicBlock *&TrueBlock,
565                                    MachineBasicBlock *&FalseBlock,
566                                    SmallVectorImpl<MachineOperand> &Condition,
567                                    bool AllowModify) const {
568   // Iterator to current instruction being considered.
569   MachineBasicBlock::iterator Instruction = MBB.end();
570 
571   // Start from the bottom of the block and work up, examining the
572   // terminator instructions.
573   while (Instruction != MBB.begin()) {
574     --Instruction;
575 
576     // Skip over debug instructions.
577     if (Instruction->isDebugInstr())
578       continue;
579 
580     // Working from the bottom, when we see a non-terminator
581     // instruction, we're done.
582     if (!isUnpredicatedTerminator(*Instruction))
583       break;
584 
585     // A terminator that isn't a branch can't easily be handled
586     // by this analysis.
587     if (!Instruction->isBranch())
588       return true;
589 
590     // Handle unconditional branches.
591     if (Instruction->getOpcode() == Lanai::BT) {
592       if (!AllowModify) {
593         TrueBlock = Instruction->getOperand(0).getMBB();
594         continue;
595       }
596 
597       // If the block has any instructions after a branch, delete them.
598       while (std::next(Instruction) != MBB.end()) {
599         std::next(Instruction)->eraseFromParent();
600       }
601 
602       Condition.clear();
603       FalseBlock = nullptr;
604 
605       // Delete the jump if it's equivalent to a fall-through.
606       if (MBB.isLayoutSuccessor(Instruction->getOperand(0).getMBB())) {
607         TrueBlock = nullptr;
608         Instruction->eraseFromParent();
609         Instruction = MBB.end();
610         continue;
611       }
612 
613       // TrueBlock is used to indicate the unconditional destination.
614       TrueBlock = Instruction->getOperand(0).getMBB();
615       continue;
616     }
617 
618     // Handle conditional branches
619     unsigned Opcode = Instruction->getOpcode();
620     if (Opcode != Lanai::BRCC)
621       return true; // Unknown opcode.
622 
623     // Multiple conditional branches are not handled here so only proceed if
624     // there are no conditions enqueued.
625     if (Condition.empty()) {
626       LPCC::CondCode BranchCond =
627           static_cast<LPCC::CondCode>(Instruction->getOperand(1).getImm());
628 
629       // TrueBlock is the target of the previously seen unconditional branch.
630       FalseBlock = TrueBlock;
631       TrueBlock = Instruction->getOperand(0).getMBB();
632       Condition.push_back(MachineOperand::CreateImm(BranchCond));
633       continue;
634     }
635 
636     // Multiple conditional branches are not handled.
637     return true;
638   }
639 
640   // Return false indicating branch successfully analyzed.
641   return false;
642 }
643 
644 // reverseBranchCondition - Reverses the branch condition of the specified
645 // condition list, returning false on success and true if it cannot be
646 // reversed.
647 bool LanaiInstrInfo::reverseBranchCondition(
648     SmallVectorImpl<llvm::MachineOperand> &Condition) const {
649   assert((Condition.size() == 1) &&
650          "Lanai branch conditions should have one component.");
651 
652   LPCC::CondCode BranchCond =
653       static_cast<LPCC::CondCode>(Condition[0].getImm());
654   Condition[0].setImm(getOppositeCondition(BranchCond));
655   return false;
656 }
657 
658 // Insert the branch with condition specified in condition and given targets
659 // (TrueBlock and FalseBlock). This function returns the number of machine
660 // instructions inserted.
661 unsigned LanaiInstrInfo::insertBranch(MachineBasicBlock &MBB,
662                                       MachineBasicBlock *TrueBlock,
663                                       MachineBasicBlock *FalseBlock,
664                                       ArrayRef<MachineOperand> Condition,
665                                       const DebugLoc &DL,
666                                       int *BytesAdded) const {
667   // Shouldn't be a fall through.
668   assert(TrueBlock && "insertBranch must not be told to insert a fallthrough");
669   assert(!BytesAdded && "code size not handled");
670 
671   // If condition is empty then an unconditional branch is being inserted.
672   if (Condition.empty()) {
673     assert(!FalseBlock && "Unconditional branch with multiple successors!");
674     BuildMI(&MBB, DL, get(Lanai::BT)).addMBB(TrueBlock);
675     return 1;
676   }
677 
678   // Else a conditional branch is inserted.
679   assert((Condition.size() == 1) &&
680          "Lanai branch conditions should have one component.");
681   unsigned ConditionalCode = Condition[0].getImm();
682   BuildMI(&MBB, DL, get(Lanai::BRCC)).addMBB(TrueBlock).addImm(ConditionalCode);
683 
684   // If no false block, then false behavior is fall through and no branch needs
685   // to be inserted.
686   if (!FalseBlock)
687     return 1;
688 
689   BuildMI(&MBB, DL, get(Lanai::BT)).addMBB(FalseBlock);
690   return 2;
691 }
692 
693 unsigned LanaiInstrInfo::removeBranch(MachineBasicBlock &MBB,
694                                       int *BytesRemoved) const {
695   assert(!BytesRemoved && "code size not handled");
696 
697   MachineBasicBlock::iterator Instruction = MBB.end();
698   unsigned Count = 0;
699 
700   while (Instruction != MBB.begin()) {
701     --Instruction;
702     if (Instruction->isDebugInstr())
703       continue;
704     if (Instruction->getOpcode() != Lanai::BT &&
705         Instruction->getOpcode() != Lanai::BRCC) {
706       break;
707     }
708 
709     // Remove the branch.
710     Instruction->eraseFromParent();
711     Instruction = MBB.end();
712     ++Count;
713   }
714 
715   return Count;
716 }
717 
718 unsigned LanaiInstrInfo::isLoadFromStackSlot(const MachineInstr &MI,
719                                              int &FrameIndex) const {
720   if (MI.getOpcode() == Lanai::LDW_RI)
721     if (MI.getOperand(1).isFI() && MI.getOperand(2).isImm() &&
722         MI.getOperand(2).getImm() == 0) {
723       FrameIndex = MI.getOperand(1).getIndex();
724       return MI.getOperand(0).getReg();
725     }
726   return 0;
727 }
728 
729 unsigned LanaiInstrInfo::isLoadFromStackSlotPostFE(const MachineInstr &MI,
730                                                    int &FrameIndex) const {
731   if (MI.getOpcode() == Lanai::LDW_RI) {
732     unsigned Reg;
733     if ((Reg = isLoadFromStackSlot(MI, FrameIndex)))
734       return Reg;
735     // Check for post-frame index elimination operations
736     SmallVector<const MachineMemOperand *, 1> Accesses;
737     if (hasLoadFromStackSlot(MI, Accesses)){
738       FrameIndex =
739           cast<FixedStackPseudoSourceValue>(Accesses.front()->getPseudoValue())
740               ->getFrameIndex();
741       return 1;
742     }
743   }
744   return 0;
745 }
746 
747 unsigned LanaiInstrInfo::isStoreToStackSlot(const MachineInstr &MI,
748                                             int &FrameIndex) const {
749   if (MI.getOpcode() == Lanai::SW_RI)
750     if (MI.getOperand(0).isFI() && MI.getOperand(1).isImm() &&
751         MI.getOperand(1).getImm() == 0) {
752       FrameIndex = MI.getOperand(0).getIndex();
753       return MI.getOperand(2).getReg();
754     }
755   return 0;
756 }
757 
758 bool LanaiInstrInfo::getMemOperandWithOffsetWidth(
759     const MachineInstr &LdSt, const MachineOperand *&BaseOp, int64_t &Offset,
760     unsigned &Width, const TargetRegisterInfo * /*TRI*/) const {
761   // Handle only loads/stores with base register followed by immediate offset
762   // and with add as ALU op.
763   if (LdSt.getNumOperands() != 4)
764     return false;
765   if (!LdSt.getOperand(1).isReg() || !LdSt.getOperand(2).isImm() ||
766       !(LdSt.getOperand(3).isImm() && LdSt.getOperand(3).getImm() == LPAC::ADD))
767     return false;
768 
769   switch (LdSt.getOpcode()) {
770   default:
771     return false;
772   case Lanai::LDW_RI:
773   case Lanai::LDW_RR:
774   case Lanai::SW_RR:
775   case Lanai::SW_RI:
776     Width = 4;
777     break;
778   case Lanai::LDHs_RI:
779   case Lanai::LDHz_RI:
780   case Lanai::STH_RI:
781     Width = 2;
782     break;
783   case Lanai::LDBs_RI:
784   case Lanai::LDBz_RI:
785   case Lanai::STB_RI:
786     Width = 1;
787     break;
788   }
789 
790   BaseOp = &LdSt.getOperand(1);
791   Offset = LdSt.getOperand(2).getImm();
792   assert(BaseOp->isReg() && "getMemOperandWithOffset only supports base "
793                             "operands of type register.");
794   return true;
795 }
796 
797 bool LanaiInstrInfo::getMemOperandWithOffset(const MachineInstr &LdSt,
798                                         const MachineOperand *&BaseOp,
799                                         int64_t &Offset,
800                                         const TargetRegisterInfo *TRI) const {
801   switch (LdSt.getOpcode()) {
802   default:
803     return false;
804   case Lanai::LDW_RI:
805   case Lanai::LDW_RR:
806   case Lanai::SW_RR:
807   case Lanai::SW_RI:
808   case Lanai::LDHs_RI:
809   case Lanai::LDHz_RI:
810   case Lanai::STH_RI:
811   case Lanai::LDBs_RI:
812   case Lanai::LDBz_RI:
813     unsigned Width;
814     return getMemOperandWithOffsetWidth(LdSt, BaseOp, Offset, Width, TRI);
815   }
816 }
817