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