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
25using namespace llvm;
26
27#define GET_INSTRINFO_CTOR_DTOR
28#include "LanaiGenInstrInfo.inc"
29
30LanaiInstrInfo::LanaiInstrInfo()
31    : LanaiGenInstrInfo(Lanai::ADJCALLSTACKDOWN, Lanai::ADJCALLSTACKUP),
32      RegisterInfo() {}
33
34void 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
49void 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
69void 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
88bool 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
119bool LanaiInstrInfo::expandPostRAPseudo(MachineInstr & /*MI*/) const {
120  return false;
121}
122
123static 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
162std::pair<unsigned, unsigned>
163LanaiInstrInfo::decomposeMachineOperandsTargetFlags(unsigned TF) const {
164  return std::make_pair(TF, 0u);
165}
166
167ArrayRef<std::pair<unsigned, const char *>>
168LanaiInstrInfo::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 makeArrayRef(TargetFlags);
175}
176
177bool LanaiInstrInfo::analyzeCompare(const MachineInstr &MI, unsigned &SrcReg,
178                                    unsigned &SrcReg2, int &CmpMask,
179                                    int &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 = 0;
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.
205inline static bool isRedundantFlagInstr(MachineInstr *CmpI, unsigned SrcReg,
206                                        unsigned SrcReg2, int 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
226inline 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
283bool LanaiInstrInfo::optimizeCompareInstr(
284    MachineInstr &CmpInstr, unsigned SrcReg, unsigned SrcReg2, int /*CmpMask*/,
285    int CmpValue, const MachineRegisterInfo *MRI) const {
286  // Get the unique definition of SrcReg.
287  MachineInstr *MI = MRI->getUniqueVRegDef(SrcReg);
288  if (!MI)
289    return false;
290
291  // Get ready to iterate backward from CmpInstr.
292  MachineBasicBlock::iterator I = CmpInstr, E = MI,
293                              B = CmpInstr.getParent()->begin();
294
295  // Early exit if CmpInstr is at the beginning of the BB.
296  if (I == B)
297    return false;
298
299  // There are two possible candidates which can be changed to set SR:
300  // One is MI, the other is a SUB instruction.
301  // * For SFSUB_F_RR(r1,r2), we are looking for SUB(r1,r2) or SUB(r2,r1).
302  // * For SFSUB_F_RI(r1, CmpValue), we are looking for SUB(r1, CmpValue).
303  MachineInstr *Sub = nullptr;
304  if (SrcReg2 != 0)
305    // MI is not a candidate to transform into a flag setting instruction.
306    MI = nullptr;
307  else if (MI->getParent() != CmpInstr.getParent() || CmpValue != 0) {
308    // Conservatively refuse to convert an instruction which isn't in the same
309    // BB as the comparison. Don't return if SFSUB_F_RI and CmpValue != 0 as Sub
310    // may still be a candidate.
311    if (CmpInstr.getOpcode() == Lanai::SFSUB_F_RI_LO)
312      MI = nullptr;
313    else
314      return false;
315  }
316
317  // Check that SR isn't set between the comparison instruction and the
318  // instruction we want to change while searching for Sub.
319  const TargetRegisterInfo *TRI = &getRegisterInfo();
320  for (--I; I != E; --I) {
321    const MachineInstr &Instr = *I;
322
323    if (Instr.modifiesRegister(Lanai::SR, TRI) ||
324        Instr.readsRegister(Lanai::SR, TRI))
325      // This instruction modifies or uses SR after the one we want to change.
326      // We can't do this transformation.
327      return false;
328
329    // Check whether CmpInstr can be made redundant by the current instruction.
330    if (isRedundantFlagInstr(&CmpInstr, SrcReg, SrcReg2, CmpValue, &*I)) {
331      Sub = &*I;
332      break;
333    }
334
335    // Don't search outside the containing basic block.
336    if (I == B)
337      return false;
338  }
339
340  // Return false if no candidates exist.
341  if (!MI && !Sub)
342    return false;
343
344  // The single candidate is called MI.
345  if (!MI)
346    MI = Sub;
347
348  if (flagSettingOpcodeVariant(MI->getOpcode()) != Lanai::NOP) {
349    bool isSafe = false;
350
351    SmallVector<std::pair<MachineOperand *, LPCC::CondCode>, 4>
352        OperandsToUpdate;
353    I = CmpInstr;
354    E = CmpInstr.getParent()->end();
355    while (!isSafe && ++I != E) {
356      const MachineInstr &Instr = *I;
357      for (unsigned IO = 0, EO = Instr.getNumOperands(); !isSafe && IO != EO;
358           ++IO) {
359        const MachineOperand &MO = Instr.getOperand(IO);
360        if (MO.isRegMask() && MO.clobbersPhysReg(Lanai::SR)) {
361          isSafe = true;
362          break;
363        }
364        if (!MO.isReg() || MO.getReg() != Lanai::SR)
365          continue;
366        if (MO.isDef()) {
367          isSafe = true;
368          break;
369        }
370        // Condition code is after the operand before SR.
371        LPCC::CondCode CC;
372        CC = (LPCC::CondCode)Instr.getOperand(IO - 1).getImm();
373
374        if (Sub) {
375          LPCC::CondCode NewCC = getOppositeCondition(CC);
376          if (NewCC == LPCC::ICC_T)
377            return false;
378          // If we have SUB(r1, r2) and CMP(r2, r1), the condition code based on
379          // CMP needs to be updated to be based on SUB.  Push the condition
380          // code operands to OperandsToUpdate.  If it is safe to remove
381          // CmpInstr, the condition code of these operands will be modified.
382          if (SrcReg2 != 0 && Sub->getOperand(1).getReg() == SrcReg2 &&
383              Sub->getOperand(2).getReg() == SrcReg) {
384            OperandsToUpdate.push_back(
385                std::make_pair(&((*I).getOperand(IO - 1)), NewCC));
386          }
387        } else {
388          // No Sub, so this is x = <op> y, z; cmp x, 0.
389          switch (CC) {
390          case LPCC::ICC_EQ: // Z
391          case LPCC::ICC_NE: // Z
392          case LPCC::ICC_MI: // N
393          case LPCC::ICC_PL: // N
394          case LPCC::ICC_F:  // none
395          case LPCC::ICC_T:  // none
396            // SR can be used multiple times, we should continue.
397            break;
398          case LPCC::ICC_CS: // C
399          case LPCC::ICC_CC: // C
400          case LPCC::ICC_VS: // V
401          case LPCC::ICC_VC: // V
402          case LPCC::ICC_HI: // C Z
403          case LPCC::ICC_LS: // C Z
404          case LPCC::ICC_GE: // N V
405          case LPCC::ICC_LT: // N V
406          case LPCC::ICC_GT: // Z N V
407          case LPCC::ICC_LE: // Z N V
408            // The instruction uses the V bit or C bit which is not safe.
409            return false;
410          case LPCC::UNKNOWN:
411            return false;
412          }
413        }
414      }
415    }
416
417    // If SR is not killed nor re-defined, we should check whether it is
418    // live-out. If it is live-out, do not optimize.
419    if (!isSafe) {
420      MachineBasicBlock *MBB = CmpInstr.getParent();
421      for (MachineBasicBlock::succ_iterator SI = MBB->succ_begin(),
422                                            SE = MBB->succ_end();
423           SI != SE; ++SI)
424        if ((*SI)->isLiveIn(Lanai::SR))
425          return false;
426    }
427
428    // Toggle the optional operand to SR.
429    MI->setDesc(get(flagSettingOpcodeVariant(MI->getOpcode())));
430    MI->addRegisterDefined(Lanai::SR);
431    CmpInstr.eraseFromParent();
432    return true;
433  }
434
435  return false;
436}
437
438bool LanaiInstrInfo::analyzeSelect(const MachineInstr &MI,
439                                   SmallVectorImpl<MachineOperand> &Cond,
440                                   unsigned &TrueOp, unsigned &FalseOp,
441                                   bool &Optimizable) const {
442  assert(MI.getOpcode() == Lanai::SELECT && "unknown select instruction");
443  // Select operands:
444  // 0: Def.
445  // 1: True use.
446  // 2: False use.
447  // 3: Condition code.
448  TrueOp = 1;
449  FalseOp = 2;
450  Cond.push_back(MI.getOperand(3));
451  Optimizable = true;
452  return false;
453}
454
455// Identify instructions that can be folded into a SELECT instruction, and
456// return the defining instruction.
457static MachineInstr *canFoldIntoSelect(unsigned Reg,
458                                       const MachineRegisterInfo &MRI) {
459  if (!Register::isVirtualRegister(Reg))
460    return nullptr;
461  if (!MRI.hasOneNonDBGUse(Reg))
462    return nullptr;
463  MachineInstr *MI = MRI.getVRegDef(Reg);
464  if (!MI)
465    return nullptr;
466  // MI is folded into the SELECT by predicating it.
467  if (!MI->isPredicable())
468    return nullptr;
469  // Check if MI has any non-dead defs or physreg uses. This also detects
470  // predicated instructions which will be reading SR.
471  for (unsigned i = 1, e = MI->getNumOperands(); i != e; ++i) {
472    const MachineOperand &MO = MI->getOperand(i);
473    // Reject frame index operands.
474    if (MO.isFI() || MO.isCPI() || MO.isJTI())
475      return nullptr;
476    if (!MO.isReg())
477      continue;
478    // MI can't have any tied operands, that would conflict with predication.
479    if (MO.isTied())
480      return nullptr;
481    if (Register::isPhysicalRegister(MO.getReg()))
482      return nullptr;
483    if (MO.isDef() && !MO.isDead())
484      return nullptr;
485  }
486  bool DontMoveAcrossStores = true;
487  if (!MI->isSafeToMove(/*AliasAnalysis=*/nullptr, DontMoveAcrossStores))
488    return nullptr;
489  return MI;
490}
491
492MachineInstr *
493LanaiInstrInfo::optimizeSelect(MachineInstr &MI,
494                               SmallPtrSetImpl<MachineInstr *> &SeenMIs,
495                               bool /*PreferFalse*/) const {
496  assert(MI.getOpcode() == Lanai::SELECT && "unknown select instruction");
497  MachineRegisterInfo &MRI = MI.getParent()->getParent()->getRegInfo();
498  MachineInstr *DefMI = canFoldIntoSelect(MI.getOperand(1).getReg(), MRI);
499  bool Invert = !DefMI;
500  if (!DefMI)
501    DefMI = canFoldIntoSelect(MI.getOperand(2).getReg(), MRI);
502  if (!DefMI)
503    return nullptr;
504
505  // Find new register class to use.
506  MachineOperand FalseReg = MI.getOperand(Invert ? 1 : 2);
507  Register DestReg = MI.getOperand(0).getReg();
508  const TargetRegisterClass *PreviousClass = MRI.getRegClass(FalseReg.getReg());
509  if (!MRI.constrainRegClass(DestReg, PreviousClass))
510    return nullptr;
511
512  // Create a new predicated version of DefMI.
513  MachineInstrBuilder NewMI =
514      BuildMI(*MI.getParent(), MI, MI.getDebugLoc(), DefMI->getDesc(), DestReg);
515
516  // Copy all the DefMI operands, excluding its (null) predicate.
517  const MCInstrDesc &DefDesc = DefMI->getDesc();
518  for (unsigned i = 1, e = DefDesc.getNumOperands();
519       i != e && !DefDesc.OpInfo[i].isPredicate(); ++i)
520    NewMI.add(DefMI->getOperand(i));
521
522  unsigned CondCode = MI.getOperand(3).getImm();
523  if (Invert)
524    NewMI.addImm(getOppositeCondition(LPCC::CondCode(CondCode)));
525  else
526    NewMI.addImm(CondCode);
527  NewMI.copyImplicitOps(MI);
528
529  // The output register value when the predicate is false is an implicit
530  // register operand tied to the first def.  The tie makes the register
531  // allocator ensure the FalseReg is allocated the same register as operand 0.
532  FalseReg.setImplicit();
533  NewMI.add(FalseReg);
534  NewMI->tieOperands(0, NewMI->getNumOperands() - 1);
535
536  // Update SeenMIs set: register newly created MI and erase removed DefMI.
537  SeenMIs.insert(NewMI);
538  SeenMIs.erase(DefMI);
539
540  // If MI is inside a loop, and DefMI is outside the loop, then kill flags on
541  // DefMI would be invalid when transferred inside the loop.  Checking for a
542  // loop is expensive, but at least remove kill flags if they are in different
543  // BBs.
544  if (DefMI->getParent() != MI.getParent())
545    NewMI->clearKillInfo();
546
547  // The caller will erase MI, but not DefMI.
548  DefMI->eraseFromParent();
549  return NewMI;
550}
551
552// The analyzeBranch function is used to examine conditional instructions and
553// remove unnecessary instructions. This method is used by BranchFolder and
554// IfConverter machine function passes to improve the CFG.
555// - TrueBlock is set to the destination if condition evaluates true (it is the
556//   nullptr if the destination is the fall-through branch);
557// - FalseBlock is set to the destination if condition evaluates to false (it
558//   is the nullptr if the branch is unconditional);
559// - condition is populated with machine operands needed to generate the branch
560//   to insert in insertBranch;
561// Returns: false if branch could successfully be analyzed.
562bool LanaiInstrInfo::analyzeBranch(MachineBasicBlock &MBB,
563                                   MachineBasicBlock *&TrueBlock,
564                                   MachineBasicBlock *&FalseBlock,
565                                   SmallVectorImpl<MachineOperand> &Condition,
566                                   bool AllowModify) const {
567  // Iterator to current instruction being considered.
568  MachineBasicBlock::iterator Instruction = MBB.end();
569
570  // Start from the bottom of the block and work up, examining the
571  // terminator instructions.
572  while (Instruction != MBB.begin()) {
573    --Instruction;
574
575    // Skip over debug instructions.
576    if (Instruction->isDebugInstr())
577      continue;
578
579    // Working from the bottom, when we see a non-terminator
580    // instruction, we're done.
581    if (!isUnpredicatedTerminator(*Instruction))
582      break;
583
584    // A terminator that isn't a branch can't easily be handled
585    // by this analysis.
586    if (!Instruction->isBranch())
587      return true;
588
589    // Handle unconditional branches.
590    if (Instruction->getOpcode() == Lanai::BT) {
591      if (!AllowModify) {
592        TrueBlock = Instruction->getOperand(0).getMBB();
593        continue;
594      }
595
596      // If the block has any instructions after a branch, delete them.
597      while (std::next(Instruction) != MBB.end()) {
598        std::next(Instruction)->eraseFromParent();
599      }
600
601      Condition.clear();
602      FalseBlock = nullptr;
603
604      // Delete the jump if it's equivalent to a fall-through.
605      if (MBB.isLayoutSuccessor(Instruction->getOperand(0).getMBB())) {
606        TrueBlock = nullptr;
607        Instruction->eraseFromParent();
608        Instruction = MBB.end();
609        continue;
610      }
611
612      // TrueBlock is used to indicate the unconditional destination.
613      TrueBlock = Instruction->getOperand(0).getMBB();
614      continue;
615    }
616
617    // Handle conditional branches
618    unsigned Opcode = Instruction->getOpcode();
619    if (Opcode != Lanai::BRCC)
620      return true; // Unknown opcode.
621
622    // Multiple conditional branches are not handled here so only proceed if
623    // there are no conditions enqueued.
624    if (Condition.empty()) {
625      LPCC::CondCode BranchCond =
626          static_cast<LPCC::CondCode>(Instruction->getOperand(1).getImm());
627
628      // TrueBlock is the target of the previously seen unconditional branch.
629      FalseBlock = TrueBlock;
630      TrueBlock = Instruction->getOperand(0).getMBB();
631      Condition.push_back(MachineOperand::CreateImm(BranchCond));
632      continue;
633    }
634
635    // Multiple conditional branches are not handled.
636    return true;
637  }
638
639  // Return false indicating branch successfully analyzed.
640  return false;
641}
642
643// reverseBranchCondition - Reverses the branch condition of the specified
644// condition list, returning false on success and true if it cannot be
645// reversed.
646bool LanaiInstrInfo::reverseBranchCondition(
647    SmallVectorImpl<llvm::MachineOperand> &Condition) const {
648  assert((Condition.size() == 1) &&
649         "Lanai branch conditions should have one component.");
650
651  LPCC::CondCode BranchCond =
652      static_cast<LPCC::CondCode>(Condition[0].getImm());
653  Condition[0].setImm(getOppositeCondition(BranchCond));
654  return false;
655}
656
657// Insert the branch with condition specified in condition and given targets
658// (TrueBlock and FalseBlock). This function returns the number of machine
659// instructions inserted.
660unsigned LanaiInstrInfo::insertBranch(MachineBasicBlock &MBB,
661                                      MachineBasicBlock *TrueBlock,
662                                      MachineBasicBlock *FalseBlock,
663                                      ArrayRef<MachineOperand> Condition,
664                                      const DebugLoc &DL,
665                                      int *BytesAdded) const {
666  // Shouldn't be a fall through.
667  assert(TrueBlock && "insertBranch must not be told to insert a fallthrough");
668  assert(!BytesAdded && "code size not handled");
669
670  // If condition is empty then an unconditional branch is being inserted.
671  if (Condition.empty()) {
672    assert(!FalseBlock && "Unconditional branch with multiple successors!");
673    BuildMI(&MBB, DL, get(Lanai::BT)).addMBB(TrueBlock);
674    return 1;
675  }
676
677  // Else a conditional branch is inserted.
678  assert((Condition.size() == 1) &&
679         "Lanai branch conditions should have one component.");
680  unsigned ConditionalCode = Condition[0].getImm();
681  BuildMI(&MBB, DL, get(Lanai::BRCC)).addMBB(TrueBlock).addImm(ConditionalCode);
682
683  // If no false block, then false behavior is fall through and no branch needs
684  // to be inserted.
685  if (!FalseBlock)
686    return 1;
687
688  BuildMI(&MBB, DL, get(Lanai::BT)).addMBB(FalseBlock);
689  return 2;
690}
691
692unsigned LanaiInstrInfo::removeBranch(MachineBasicBlock &MBB,
693                                      int *BytesRemoved) const {
694  assert(!BytesRemoved && "code size not handled");
695
696  MachineBasicBlock::iterator Instruction = MBB.end();
697  unsigned Count = 0;
698
699  while (Instruction != MBB.begin()) {
700    --Instruction;
701    if (Instruction->isDebugInstr())
702      continue;
703    if (Instruction->getOpcode() != Lanai::BT &&
704        Instruction->getOpcode() != Lanai::BRCC) {
705      break;
706    }
707
708    // Remove the branch.
709    Instruction->eraseFromParent();
710    Instruction = MBB.end();
711    ++Count;
712  }
713
714  return Count;
715}
716
717unsigned LanaiInstrInfo::isLoadFromStackSlot(const MachineInstr &MI,
718                                             int &FrameIndex) const {
719  if (MI.getOpcode() == Lanai::LDW_RI)
720    if (MI.getOperand(1).isFI() && MI.getOperand(2).isImm() &&
721        MI.getOperand(2).getImm() == 0) {
722      FrameIndex = MI.getOperand(1).getIndex();
723      return MI.getOperand(0).getReg();
724    }
725  return 0;
726}
727
728unsigned LanaiInstrInfo::isLoadFromStackSlotPostFE(const MachineInstr &MI,
729                                                   int &FrameIndex) const {
730  if (MI.getOpcode() == Lanai::LDW_RI) {
731    unsigned Reg;
732    if ((Reg = isLoadFromStackSlot(MI, FrameIndex)))
733      return Reg;
734    // Check for post-frame index elimination operations
735    SmallVector<const MachineMemOperand *, 1> Accesses;
736    if (hasLoadFromStackSlot(MI, Accesses)){
737      FrameIndex =
738          cast<FixedStackPseudoSourceValue>(Accesses.front()->getPseudoValue())
739              ->getFrameIndex();
740      return 1;
741    }
742  }
743  return 0;
744}
745
746unsigned LanaiInstrInfo::isStoreToStackSlot(const MachineInstr &MI,
747                                            int &FrameIndex) const {
748  if (MI.getOpcode() == Lanai::SW_RI)
749    if (MI.getOperand(0).isFI() && MI.getOperand(1).isImm() &&
750        MI.getOperand(1).getImm() == 0) {
751      FrameIndex = MI.getOperand(0).getIndex();
752      return MI.getOperand(2).getReg();
753    }
754  return 0;
755}
756
757bool LanaiInstrInfo::getMemOperandWithOffsetWidth(
758    const MachineInstr &LdSt, const MachineOperand *&BaseOp, int64_t &Offset,
759    unsigned &Width, const TargetRegisterInfo * /*TRI*/) const {
760  // Handle only loads/stores with base register followed by immediate offset
761  // and with add as ALU op.
762  if (LdSt.getNumOperands() != 4)
763    return false;
764  if (!LdSt.getOperand(1).isReg() || !LdSt.getOperand(2).isImm() ||
765      !(LdSt.getOperand(3).isImm() && LdSt.getOperand(3).getImm() == LPAC::ADD))
766    return false;
767
768  switch (LdSt.getOpcode()) {
769  default:
770    return false;
771  case Lanai::LDW_RI:
772  case Lanai::LDW_RR:
773  case Lanai::SW_RR:
774  case Lanai::SW_RI:
775    Width = 4;
776    break;
777  case Lanai::LDHs_RI:
778  case Lanai::LDHz_RI:
779  case Lanai::STH_RI:
780    Width = 2;
781    break;
782  case Lanai::LDBs_RI:
783  case Lanai::LDBz_RI:
784  case Lanai::STB_RI:
785    Width = 1;
786    break;
787  }
788
789  BaseOp = &LdSt.getOperand(1);
790  Offset = LdSt.getOperand(2).getImm();
791
792  if (!BaseOp->isReg())
793    return false;
794
795  return true;
796}
797
798bool LanaiInstrInfo::getMemOperandWithOffset(const MachineInstr &LdSt,
799                                        const MachineOperand *&BaseOp,
800                                        int64_t &Offset,
801                                        const TargetRegisterInfo *TRI) const {
802  switch (LdSt.getOpcode()) {
803  default:
804    return false;
805  case Lanai::LDW_RI:
806  case Lanai::LDW_RR:
807  case Lanai::SW_RR:
808  case Lanai::SW_RI:
809  case Lanai::LDHs_RI:
810  case Lanai::LDHz_RI:
811  case Lanai::STH_RI:
812  case Lanai::LDBs_RI:
813  case Lanai::LDBz_RI:
814    unsigned Width;
815    return getMemOperandWithOffsetWidth(LdSt, BaseOp, Offset, Width, TRI);
816  }
817}
818