MipsInstrInfo.cpp revision f6372aa1cc568df19da7c5023e83c75aa9404a07 
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 (!isBranch(LastInst->getOpcode()))
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 TargetInstrDescriptor &TID = get(Opc);
263
264      if (TID.numOperands == 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 TargetInstrDescriptor &TID = get(Opc);
279
280  if (TID.numOperands == 3)
281    BuildMI(&MBB, TID).addReg(Cond[1].getReg())
282                      .addReg(Cond[2].getReg())
283                      .addMBB(TBB);
284  else
285    BuildMI(&MBB, TID).addReg(Cond[1].getReg())
286                      .addMBB(TBB);
287
288  BuildMI(&MBB, get(Mips::J)).addMBB(FBB);
289  return 2;
290}
291
292void MipsInstrInfo::
293copyRegToReg(MachineBasicBlock &MBB, MachineBasicBlock::iterator I,
294             unsigned DestReg, unsigned SrcReg,
295             const TargetRegisterClass *DestRC,
296             const TargetRegisterClass *SrcRC) const {
297  if (DestRC != SrcRC) {
298    cerr << "Not yet supported!";
299    abort();
300  }
301
302  if (DestRC == Mips::CPURegsRegisterClass)
303    BuildMI(MBB, I, get(Mips::ADDu), DestReg).addReg(Mips::ZERO)
304      .addReg(SrcReg);
305  else
306    assert (0 && "Can't copy this register");
307}
308
309void MipsInstrInfo::
310storeRegToStackSlot(MachineBasicBlock &MBB, MachineBasicBlock::iterator I,
311          unsigned SrcReg, bool isKill, int FI,
312          const TargetRegisterClass *RC) const
313{
314  if (RC == Mips::CPURegsRegisterClass)
315    BuildMI(MBB, I, get(Mips::SW)).addReg(SrcReg, false, false, isKill)
316          .addImm(0).addFrameIndex(FI);
317  else
318    assert(0 && "Can't store this register to stack slot");
319}
320
321void MipsInstrInfo::storeRegToAddr(MachineFunction &MF, unsigned SrcReg,
322                                      bool isKill,
323                                      SmallVectorImpl<MachineOperand> &Addr,
324                                      const TargetRegisterClass *RC,
325                                 SmallVectorImpl<MachineInstr*> &NewMIs) const {
326  if (RC != Mips::CPURegsRegisterClass)
327    assert(0 && "Can't store this register");
328  MachineInstrBuilder MIB = BuildMI(get(Mips::SW))
329    .addReg(SrcReg, false, false, isKill);
330  for (unsigned i = 0, e = Addr.size(); i != e; ++i) {
331    MachineOperand &MO = Addr[i];
332    if (MO.isRegister())
333      MIB.addReg(MO.getReg());
334    else if (MO.isImmediate())
335      MIB.addImm(MO.getImm());
336    else
337      MIB.addFrameIndex(MO.getIndex());
338  }
339  NewMIs.push_back(MIB);
340  return;
341}
342
343void MipsInstrInfo::
344loadRegFromStackSlot(MachineBasicBlock &MBB, MachineBasicBlock::iterator I,
345                     unsigned DestReg, int FI,
346                     const TargetRegisterClass *RC) const
347{
348  if (RC == Mips::CPURegsRegisterClass)
349    BuildMI(MBB, I, get(Mips::LW), DestReg).addImm(0).addFrameIndex(FI);
350  else
351    assert(0 && "Can't load this register from stack slot");
352}
353
354void MipsInstrInfo::loadRegFromAddr(MachineFunction &MF, unsigned DestReg,
355                                       SmallVectorImpl<MachineOperand> &Addr,
356                                       const TargetRegisterClass *RC,
357                                 SmallVectorImpl<MachineInstr*> &NewMIs) const {
358  if (RC != Mips::CPURegsRegisterClass)
359    assert(0 && "Can't load this register");
360  MachineInstrBuilder MIB = BuildMI(get(Mips::LW), DestReg);
361  for (unsigned i = 0, e = Addr.size(); i != e; ++i) {
362    MachineOperand &MO = Addr[i];
363    if (MO.isRegister())
364      MIB.addReg(MO.getReg());
365    else if (MO.isImmediate())
366      MIB.addImm(MO.getImm());
367    else
368      MIB.addFrameIndex(MO.getIndex());
369  }
370  NewMIs.push_back(MIB);
371  return;
372}
373
374unsigned MipsInstrInfo::
375RemoveBranch(MachineBasicBlock &MBB) const
376{
377  MachineBasicBlock::iterator I = MBB.end();
378  if (I == MBB.begin()) return 0;
379  --I;
380  if (I->getOpcode() != Mips::J &&
381      GetCondFromBranchOpc(I->getOpcode()) == Mips::COND_INVALID)
382    return 0;
383
384  // Remove the branch.
385  I->eraseFromParent();
386
387  I = MBB.end();
388
389  if (I == MBB.begin()) return 1;
390  --I;
391  if (GetCondFromBranchOpc(I->getOpcode()) == Mips::COND_INVALID)
392    return 1;
393
394  // Remove the branch.
395  I->eraseFromParent();
396  return 2;
397}
398
399/// BlockHasNoFallThrough - Analyse if MachineBasicBlock does not
400/// fall-through into its successor block.
401bool MipsInstrInfo::
402BlockHasNoFallThrough(MachineBasicBlock &MBB) const
403{
404  if (MBB.empty()) return false;
405
406  switch (MBB.back().getOpcode()) {
407  case Mips::RET:     // Return.
408  case Mips::JR:      // Indirect branch.
409  case Mips::J:       // Uncond branch.
410    return true;
411  default: return false;
412  }
413}
414
415/// ReverseBranchCondition - Return the inverse opcode of the
416/// specified Branch instruction.
417bool MipsInstrInfo::
418ReverseBranchCondition(std::vector<MachineOperand> &Cond) const
419{
420  assert( (Cond.size() == 3 || Cond.size() == 2) &&
421          "Invalid Mips branch condition!");
422  Cond[0].setImm(GetOppositeBranchCondition((Mips::CondCode)Cond[0].getImm()));
423  return false;
424}
425
426
427