MipsInstrInfo.cpp revision 749c6f6b5ed301c84aac562e414486549d7b98eb
1//===- MipsInstrInfo.cpp - Mips 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 Mips implementation of the TargetInstrInfo class.
11//
12//===----------------------------------------------------------------------===//
13
14#include "Mips.h"
15#include "MipsInstrInfo.h"
16#include "llvm/ADT/STLExtras.h"
17#include "llvm/CodeGen/MachineInstrBuilder.h"
18#include "MipsGenInstrInfo.inc"
19
20using namespace llvm;
21
22// TODO: Add the subtarget support on this constructor
23MipsInstrInfo::MipsInstrInfo(MipsTargetMachine &tm)
24  : TargetInstrInfoImpl(MipsInsts, array_lengthof(MipsInsts)),
25    TM(tm), RI(*this) {}
26
27static bool isZeroImm(const MachineOperand &op) {
28  return op.isImmediate() && op.getImm() == 0;
29}
30
31/// Return true if the instruction is a register to register move and
32/// leave the source and dest operands in the passed parameters.
33bool MipsInstrInfo::
34isMoveInstr(const MachineInstr &MI, unsigned &SrcReg, unsigned &DstReg) const
35{
36  //  addu  $dst, $src, $zero || addu  $dst, $zero, $src
37  //  or    $dst, $src, $zero || or    $dst, $zero, $src
38  if ((MI.getOpcode() == Mips::ADDu) || (MI.getOpcode() == Mips::OR))
39  {
40    if (MI.getOperand(1).getReg() == Mips::ZERO) {
41      DstReg = MI.getOperand(0).getReg();
42      SrcReg = MI.getOperand(2).getReg();
43      return true;
44    } else if (MI.getOperand(2).getReg() == Mips::ZERO) {
45      DstReg = MI.getOperand(0).getReg();
46      SrcReg = MI.getOperand(1).getReg();
47      return true;
48    }
49  }
50
51  //  addiu $dst, $src, 0
52  if (MI.getOpcode() == Mips::ADDiu)
53  {
54    if ((MI.getOperand(1).isRegister()) && (isZeroImm(MI.getOperand(2)))) {
55      DstReg = MI.getOperand(0).getReg();
56      SrcReg = MI.getOperand(1).getReg();
57      return true;
58    }
59  }
60  return false;
61}
62
63/// isLoadFromStackSlot - If the specified machine instruction is a direct
64/// load from a stack slot, return the virtual or physical register number of
65/// the destination along with the FrameIndex of the loaded stack slot.  If
66/// not, return 0.  This predicate must return 0 if the instruction has
67/// any side effects other than loading from the stack slot.
68unsigned MipsInstrInfo::
69isLoadFromStackSlot(MachineInstr *MI, int &FrameIndex) const
70{
71  if (MI->getOpcode() == Mips::LW)
72  {
73    if ((MI->getOperand(2).isFrameIndex()) && // is a stack slot
74        (MI->getOperand(1).isImmediate()) &&  // the imm is zero
75        (isZeroImm(MI->getOperand(1))))
76    {
77      FrameIndex = MI->getOperand(2).getIndex();
78      return MI->getOperand(0).getReg();
79    }
80  }
81
82  return 0;
83}
84
85/// isStoreToStackSlot - If the specified machine instruction is a direct
86/// store to a stack slot, return the virtual or physical register number of
87/// the source reg along with the FrameIndex of the loaded stack slot.  If
88/// not, return 0.  This predicate must return 0 if the instruction has
89/// any side effects other than storing to the stack slot.
90unsigned MipsInstrInfo::
91isStoreToStackSlot(MachineInstr *MI, int &FrameIndex) const
92{
93  if (MI->getOpcode() == Mips::SW) {
94    if ((MI->getOperand(0).isFrameIndex()) && // is a stack slot
95        (MI->getOperand(1).isImmediate()) &&  // the imm is zero
96        (isZeroImm(MI->getOperand(1))))
97    {
98      FrameIndex = MI->getOperand(0).getIndex();
99      return MI->getOperand(2).getReg();
100    }
101  }
102  return 0;
103}
104
105/// insertNoop - If data hazard condition is found insert the target nop
106/// instruction.
107void MipsInstrInfo::
108insertNoop(MachineBasicBlock &MBB, MachineBasicBlock::iterator MI) const
109{
110  BuildMI(MBB, MI, get(Mips::NOP));
111}
112
113//===----------------------------------------------------------------------===//
114// Branch Analysis
115//===----------------------------------------------------------------------===//
116
117/// GetCondFromBranchOpc - Return the Mips CC that matches
118/// the correspondent Branch instruction opcode.
119static Mips::CondCode GetCondFromBranchOpc(unsigned BrOpc)
120{
121  switch (BrOpc) {
122  default: return Mips::COND_INVALID;
123  case Mips::BEQ  : return Mips::COND_E;
124  case Mips::BNE  : return Mips::COND_NE;
125  case Mips::BGTZ : return Mips::COND_GZ;
126  case Mips::BGEZ : return Mips::COND_GEZ;
127  case Mips::BLTZ : return Mips::COND_LZ;
128  case Mips::BLEZ : return Mips::COND_LEZ;
129  }
130}
131
132/// GetCondBranchFromCond - Return the Branch instruction
133/// opcode that matches the cc.
134unsigned Mips::GetCondBranchFromCond(Mips::CondCode CC)
135{
136  switch (CC) {
137  default: assert(0 && "Illegal condition code!");
138  case Mips::COND_E   : return Mips::BEQ;
139  case Mips::COND_NE  : return Mips::BNE;
140  case Mips::COND_GZ  : return Mips::BGTZ;
141  case Mips::COND_GEZ : return Mips::BGEZ;
142  case Mips::COND_LZ  : return Mips::BLTZ;
143  case Mips::COND_LEZ : return Mips::BLEZ;
144  }
145}
146
147/// GetOppositeBranchCondition - Return the inverse of the specified
148/// condition, e.g. turning COND_E to COND_NE.
149Mips::CondCode Mips::GetOppositeBranchCondition(Mips::CondCode CC)
150{
151  switch (CC) {
152  default: assert(0 && "Illegal condition code!");
153  case Mips::COND_E   : return Mips::COND_NE;
154  case Mips::COND_NE  : return Mips::COND_E;
155  case Mips::COND_GZ  : return Mips::COND_LEZ;
156  case Mips::COND_GEZ : return Mips::COND_LZ;
157  case Mips::COND_LZ  : return Mips::COND_GEZ;
158  case Mips::COND_LEZ : return Mips::COND_GZ;
159  }
160}
161
162bool MipsInstrInfo::AnalyzeBranch(MachineBasicBlock &MBB,
163                                  MachineBasicBlock *&TBB,
164                                  MachineBasicBlock *&FBB,
165                                  std::vector<MachineOperand> &Cond) const
166{
167  // If the block has no terminators, it just falls into the block after it.
168  MachineBasicBlock::iterator I = MBB.end();
169  if (I == MBB.begin() || !isUnpredicatedTerminator(--I))
170    return false;
171
172  // Get the last instruction in the block.
173  MachineInstr *LastInst = I;
174
175  // If there is only one terminator instruction, process it.
176  unsigned LastOpc = LastInst->getOpcode();
177  if (I == MBB.begin() || !isUnpredicatedTerminator(--I)) {
178    if (!LastInst->getDesc().isBranch())
179      return true;
180
181    // Unconditional branch
182    if (LastOpc == Mips::J) {
183      TBB = LastInst->getOperand(0).getMBB();
184      return false;
185    }
186
187    Mips::CondCode BranchCode = GetCondFromBranchOpc(LastInst->getOpcode());
188    if (BranchCode == Mips::COND_INVALID)
189      return true;  // Can't handle indirect branch.
190
191    // Conditional branch
192    // Block ends with fall-through condbranch.
193    if (LastOpc != Mips::COND_INVALID) {
194      int LastNumOp = LastInst->getNumOperands();
195
196      TBB = LastInst->getOperand(LastNumOp-1).getMBB();
197      Cond.push_back(MachineOperand::CreateImm(BranchCode));
198
199      for (int i=0; i<LastNumOp-1; i++) {
200        Cond.push_back(LastInst->getOperand(i));
201      }
202
203      return false;
204    }
205  }
206
207  // Get the instruction before it if it is a terminator.
208  MachineInstr *SecondLastInst = I;
209
210  // If there are three terminators, we don't know what sort of block this is.
211  if (SecondLastInst && I != MBB.begin() && isUnpredicatedTerminator(--I))
212    return true;
213
214  // If the block ends with Mips::J and a Mips::BNE/Mips::BEQ, handle it.
215  unsigned SecondLastOpc    = SecondLastInst->getOpcode();
216  Mips::CondCode BranchCode = GetCondFromBranchOpc(SecondLastOpc);
217
218  if (SecondLastOpc != Mips::COND_INVALID && LastOpc == Mips::J) {
219    int SecondNumOp = SecondLastInst->getNumOperands();
220
221    TBB = SecondLastInst->getOperand(SecondNumOp-1).getMBB();
222    Cond.push_back(MachineOperand::CreateImm(BranchCode));
223
224    for (int i=0; i<SecondNumOp-1; i++) {
225      Cond.push_back(SecondLastInst->getOperand(i));
226    }
227
228    FBB = LastInst->getOperand(0).getMBB();
229    return false;
230  }
231
232  // If the block ends with two unconditional branches, handle it. The last
233  // one is not executed, so remove it.
234  if ((SecondLastOpc == Mips::J) && (LastOpc == Mips::J)) {
235    TBB = SecondLastInst->getOperand(0).getMBB();
236    I = LastInst;
237    I->eraseFromParent();
238    return false;
239  }
240
241  // Otherwise, can't handle this.
242  return true;
243}
244
245unsigned MipsInstrInfo::
246InsertBranch(MachineBasicBlock &MBB, MachineBasicBlock *TBB,
247             MachineBasicBlock *FBB, const std::vector<MachineOperand> &Cond)
248             const
249{
250  // Shouldn't be a fall through.
251  assert(TBB && "InsertBranch must not be told to insert a fallthrough");
252  assert((Cond.size() == 3 || Cond.size() == 2 || Cond.size() == 0) &&
253         "Mips branch conditions can have two|three components!");
254
255  if (FBB == 0) { // One way branch.
256    if (Cond.empty()) {
257      // Unconditional branch?
258      BuildMI(&MBB, get(Mips::J)).addMBB(TBB);
259    } else {
260      // Conditional branch.
261      unsigned Opc = GetCondBranchFromCond((Mips::CondCode)Cond[0].getImm());
262      const TargetInstrDesc &TID = get(Opc);
263
264      if (TID.getNumOperands() == 3)
265        BuildMI(&MBB, TID).addReg(Cond[1].getReg())
266                          .addReg(Cond[2].getReg())
267                          .addMBB(TBB);
268      else
269        BuildMI(&MBB, TID).addReg(Cond[1].getReg())
270                          .addMBB(TBB);
271
272    }
273    return 1;
274  }
275
276  // Two-way Conditional branch.
277  unsigned Opc = GetCondBranchFromCond((Mips::CondCode)Cond[0].getImm());
278  const TargetInstrDesc &TID = get(Opc);
279
280  if (TID.getNumOperands() == 3)
281    BuildMI(&MBB, TID).addReg(Cond[1].getReg()).addReg(Cond[2].getReg())
282                      .addMBB(TBB);
283  else
284    BuildMI(&MBB, TID).addReg(Cond[1].getReg()).addMBB(TBB);
285
286  BuildMI(&MBB, get(Mips::J)).addMBB(FBB);
287  return 2;
288}
289
290void MipsInstrInfo::
291copyRegToReg(MachineBasicBlock &MBB, MachineBasicBlock::iterator I,
292             unsigned DestReg, unsigned SrcReg,
293             const TargetRegisterClass *DestRC,
294             const TargetRegisterClass *SrcRC) const {
295  if (DestRC != SrcRC) {
296    cerr << "Not yet supported!";
297    abort();
298  }
299
300  if (DestRC == Mips::CPURegsRegisterClass)
301    BuildMI(MBB, I, get(Mips::ADDu), DestReg).addReg(Mips::ZERO)
302      .addReg(SrcReg);
303  else
304    assert (0 && "Can't copy this register");
305}
306
307void MipsInstrInfo::
308storeRegToStackSlot(MachineBasicBlock &MBB, MachineBasicBlock::iterator I,
309          unsigned SrcReg, bool isKill, int FI,
310          const TargetRegisterClass *RC) const
311{
312  if (RC == Mips::CPURegsRegisterClass)
313    BuildMI(MBB, I, get(Mips::SW)).addReg(SrcReg, false, false, isKill)
314          .addImm(0).addFrameIndex(FI);
315  else
316    assert(0 && "Can't store this register to stack slot");
317}
318
319void MipsInstrInfo::storeRegToAddr(MachineFunction &MF, unsigned SrcReg,
320                                      bool isKill,
321                                      SmallVectorImpl<MachineOperand> &Addr,
322                                      const TargetRegisterClass *RC,
323                                 SmallVectorImpl<MachineInstr*> &NewMIs) const {
324  if (RC != Mips::CPURegsRegisterClass)
325    assert(0 && "Can't store this register");
326  MachineInstrBuilder MIB = BuildMI(get(Mips::SW))
327    .addReg(SrcReg, false, false, isKill);
328  for (unsigned i = 0, e = Addr.size(); i != e; ++i) {
329    MachineOperand &MO = Addr[i];
330    if (MO.isRegister())
331      MIB.addReg(MO.getReg());
332    else if (MO.isImmediate())
333      MIB.addImm(MO.getImm());
334    else
335      MIB.addFrameIndex(MO.getIndex());
336  }
337  NewMIs.push_back(MIB);
338  return;
339}
340
341void MipsInstrInfo::
342loadRegFromStackSlot(MachineBasicBlock &MBB, MachineBasicBlock::iterator I,
343                     unsigned DestReg, int FI,
344                     const TargetRegisterClass *RC) const
345{
346  if (RC == Mips::CPURegsRegisterClass)
347    BuildMI(MBB, I, get(Mips::LW), DestReg).addImm(0).addFrameIndex(FI);
348  else
349    assert(0 && "Can't load this register from stack slot");
350}
351
352void MipsInstrInfo::loadRegFromAddr(MachineFunction &MF, unsigned DestReg,
353                                       SmallVectorImpl<MachineOperand> &Addr,
354                                       const TargetRegisterClass *RC,
355                                 SmallVectorImpl<MachineInstr*> &NewMIs) const {
356  if (RC != Mips::CPURegsRegisterClass)
357    assert(0 && "Can't load this register");
358  MachineInstrBuilder MIB = BuildMI(get(Mips::LW), DestReg);
359  for (unsigned i = 0, e = Addr.size(); i != e; ++i) {
360    MachineOperand &MO = Addr[i];
361    if (MO.isRegister())
362      MIB.addReg(MO.getReg());
363    else if (MO.isImmediate())
364      MIB.addImm(MO.getImm());
365    else
366      MIB.addFrameIndex(MO.getIndex());
367  }
368  NewMIs.push_back(MIB);
369  return;
370}
371
372MachineInstr *MipsInstrInfo::
373foldMemoryOperand(MachineInstr* MI,
374                  SmallVectorImpl<unsigned> &Ops, int FI) const
375{
376  if (Ops.size() != 1) return NULL;
377
378  MachineInstr *NewMI = NULL;
379
380  switch (MI->getOpcode())
381  {
382    case Mips::ADDu:
383      if ((MI->getOperand(0).isRegister()) &&
384        (MI->getOperand(1).isRegister()) &&
385        (MI->getOperand(1).getReg() == Mips::ZERO) &&
386        (MI->getOperand(2).isRegister()))
387      {
388        if (Ops[0] == 0)    // COPY -> STORE
389          NewMI = BuildMI(get(Mips::SW)).addFrameIndex(FI)
390                  .addImm(0).addReg(MI->getOperand(2).getReg());
391        else                   // COPY -> LOAD
392          NewMI = BuildMI(get(Mips::LW), MI->getOperand(0)
393                  .getReg()).addImm(0).addFrameIndex(FI);
394      }
395      break;
396  }
397
398  if (NewMI)
399    NewMI->copyKillDeadInfo(MI);
400  return NewMI;
401}
402
403unsigned MipsInstrInfo::
404RemoveBranch(MachineBasicBlock &MBB) const
405{
406  MachineBasicBlock::iterator I = MBB.end();
407  if (I == MBB.begin()) return 0;
408  --I;
409  if (I->getOpcode() != Mips::J &&
410      GetCondFromBranchOpc(I->getOpcode()) == Mips::COND_INVALID)
411    return 0;
412
413  // Remove the branch.
414  I->eraseFromParent();
415
416  I = MBB.end();
417
418  if (I == MBB.begin()) return 1;
419  --I;
420  if (GetCondFromBranchOpc(I->getOpcode()) == Mips::COND_INVALID)
421    return 1;
422
423  // Remove the branch.
424  I->eraseFromParent();
425  return 2;
426}
427
428/// BlockHasNoFallThrough - Analyse if MachineBasicBlock does not
429/// fall-through into its successor block.
430bool MipsInstrInfo::
431BlockHasNoFallThrough(MachineBasicBlock &MBB) const
432{
433  if (MBB.empty()) return false;
434
435  switch (MBB.back().getOpcode()) {
436  case Mips::RET:     // Return.
437  case Mips::JR:      // Indirect branch.
438  case Mips::J:       // Uncond branch.
439    return true;
440  default: return false;
441  }
442}
443
444/// ReverseBranchCondition - Return the inverse opcode of the
445/// specified Branch instruction.
446bool MipsInstrInfo::
447ReverseBranchCondition(std::vector<MachineOperand> &Cond) const
448{
449  assert( (Cond.size() == 3 || Cond.size() == 2) &&
450          "Invalid Mips branch condition!");
451  Cond[0].setImm(GetOppositeBranchCondition((Mips::CondCode)Cond[0].getImm()));
452  return false;
453}
454
455
456