PPCInstrInfo.cpp revision b29de8ba0044548f0259b5eca180e07bdba992bc 
1//===-- PPCInstrInfo.cpp - PowerPC Instruction Information ----------------===//
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 PowerPC implementation of the TargetInstrInfo class.
11//
12//===----------------------------------------------------------------------===//
13
14#include "PPCInstrInfo.h"
15#include "MCTargetDesc/PPCPredicates.h"
16#include "PPC.h"
17#include "PPCHazardRecognizers.h"
18#include "PPCInstrBuilder.h"
19#include "PPCMachineFunctionInfo.h"
20#include "PPCTargetMachine.h"
21#include "llvm/ADT/Statistic.h"
22#include "llvm/ADT/STLExtras.h"
23#include "llvm/CodeGen/MachineFrameInfo.h"
24#include "llvm/CodeGen/MachineFunctionPass.h"
25#include "llvm/CodeGen/MachineInstrBuilder.h"
26#include "llvm/CodeGen/MachineMemOperand.h"
27#include "llvm/CodeGen/MachineRegisterInfo.h"
28#include "llvm/CodeGen/PseudoSourceValue.h"
29#include "llvm/MC/MCAsmInfo.h"
30#include "llvm/Support/CommandLine.h"
31#include "llvm/Support/ErrorHandling.h"
32#include "llvm/Support/TargetRegistry.h"
33#include "llvm/Support/raw_ostream.h"
34
35#define GET_INSTRMAP_INFO
36#define GET_INSTRINFO_CTOR_DTOR
37#include "PPCGenInstrInfo.inc"
38
39using namespace llvm;
40
41static cl::
42opt<bool> DisableCTRLoopAnal("disable-ppc-ctrloop-analysis", cl::Hidden,
43            cl::desc("Disable analysis for CTR loops"));
44
45static cl::opt<bool> DisableCmpOpt("disable-ppc-cmp-opt",
46cl::desc("Disable compare instruction optimization"), cl::Hidden);
47
48// Pin the vtable to this file.
49void PPCInstrInfo::anchor() {}
50
51PPCInstrInfo::PPCInstrInfo(PPCTargetMachine &tm)
52  : PPCGenInstrInfo(PPC::ADJCALLSTACKDOWN, PPC::ADJCALLSTACKUP),
53    TM(tm), RI(*TM.getSubtargetImpl()) {}
54
55/// CreateTargetHazardRecognizer - Return the hazard recognizer to use for
56/// this target when scheduling the DAG.
57ScheduleHazardRecognizer *PPCInstrInfo::CreateTargetHazardRecognizer(
58  const TargetMachine *TM,
59  const ScheduleDAG *DAG) const {
60  unsigned Directive = TM->getSubtarget<PPCSubtarget>().getDarwinDirective();
61  if (Directive == PPC::DIR_440 || Directive == PPC::DIR_A2 ||
62      Directive == PPC::DIR_E500mc || Directive == PPC::DIR_E5500) {
63    const InstrItineraryData *II = TM->getInstrItineraryData();
64    return new PPCScoreboardHazardRecognizer(II, DAG);
65  }
66
67  return TargetInstrInfo::CreateTargetHazardRecognizer(TM, DAG);
68}
69
70/// CreateTargetPostRAHazardRecognizer - Return the postRA hazard recognizer
71/// to use for this target when scheduling the DAG.
72ScheduleHazardRecognizer *PPCInstrInfo::CreateTargetPostRAHazardRecognizer(
73  const InstrItineraryData *II,
74  const ScheduleDAG *DAG) const {
75  unsigned Directive = TM.getSubtarget<PPCSubtarget>().getDarwinDirective();
76
77  // Most subtargets use a PPC970 recognizer.
78  if (Directive != PPC::DIR_440 && Directive != PPC::DIR_A2 &&
79      Directive != PPC::DIR_E500mc && Directive != PPC::DIR_E5500) {
80    assert(TM.getInstrInfo() && "No InstrInfo?");
81
82    return new PPCHazardRecognizer970(TM);
83  }
84
85  return new PPCScoreboardHazardRecognizer(II, DAG);
86}
87
88// Detect 32 -> 64-bit extensions where we may reuse the low sub-register.
89bool PPCInstrInfo::isCoalescableExtInstr(const MachineInstr &MI,
90                                         unsigned &SrcReg, unsigned &DstReg,
91                                         unsigned &SubIdx) const {
92  switch (MI.getOpcode()) {
93  default: return false;
94  case PPC::EXTSW:
95  case PPC::EXTSW_32_64:
96    SrcReg = MI.getOperand(1).getReg();
97    DstReg = MI.getOperand(0).getReg();
98    SubIdx = PPC::sub_32;
99    return true;
100  }
101}
102
103unsigned PPCInstrInfo::isLoadFromStackSlot(const MachineInstr *MI,
104                                           int &FrameIndex) const {
105  // Note: This list must be kept consistent with LoadRegFromStackSlot.
106  switch (MI->getOpcode()) {
107  default: break;
108  case PPC::LD:
109  case PPC::LWZ:
110  case PPC::LFS:
111  case PPC::LFD:
112  case PPC::RESTORE_CR:
113  case PPC::LVX:
114  case PPC::RESTORE_VRSAVE:
115    // Check for the operands added by addFrameReference (the immediate is the
116    // offset which defaults to 0).
117    if (MI->getOperand(1).isImm() && !MI->getOperand(1).getImm() &&
118        MI->getOperand(2).isFI()) {
119      FrameIndex = MI->getOperand(2).getIndex();
120      return MI->getOperand(0).getReg();
121    }
122    break;
123  }
124  return 0;
125}
126
127unsigned PPCInstrInfo::isStoreToStackSlot(const MachineInstr *MI,
128                                          int &FrameIndex) const {
129  // Note: This list must be kept consistent with StoreRegToStackSlot.
130  switch (MI->getOpcode()) {
131  default: break;
132  case PPC::STD:
133  case PPC::STW:
134  case PPC::STFS:
135  case PPC::STFD:
136  case PPC::SPILL_CR:
137  case PPC::STVX:
138  case PPC::SPILL_VRSAVE:
139    // Check for the operands added by addFrameReference (the immediate is the
140    // offset which defaults to 0).
141    if (MI->getOperand(1).isImm() && !MI->getOperand(1).getImm() &&
142        MI->getOperand(2).isFI()) {
143      FrameIndex = MI->getOperand(2).getIndex();
144      return MI->getOperand(0).getReg();
145    }
146    break;
147  }
148  return 0;
149}
150
151// commuteInstruction - We can commute rlwimi instructions, but only if the
152// rotate amt is zero.  We also have to munge the immediates a bit.
153MachineInstr *
154PPCInstrInfo::commuteInstruction(MachineInstr *MI, bool NewMI) const {
155  MachineFunction &MF = *MI->getParent()->getParent();
156
157  // Normal instructions can be commuted the obvious way.
158  if (MI->getOpcode() != PPC::RLWIMI &&
159      MI->getOpcode() != PPC::RLWIMIo)
160    return TargetInstrInfo::commuteInstruction(MI, NewMI);
161
162  // Cannot commute if it has a non-zero rotate count.
163  if (MI->getOperand(3).getImm() != 0)
164    return 0;
165
166  // If we have a zero rotate count, we have:
167  //   M = mask(MB,ME)
168  //   Op0 = (Op1 & ~M) | (Op2 & M)
169  // Change this to:
170  //   M = mask((ME+1)&31, (MB-1)&31)
171  //   Op0 = (Op2 & ~M) | (Op1 & M)
172
173  // Swap op1/op2
174  unsigned Reg0 = MI->getOperand(0).getReg();
175  unsigned Reg1 = MI->getOperand(1).getReg();
176  unsigned Reg2 = MI->getOperand(2).getReg();
177  bool Reg1IsKill = MI->getOperand(1).isKill();
178  bool Reg2IsKill = MI->getOperand(2).isKill();
179  bool ChangeReg0 = false;
180  // If machine instrs are no longer in two-address forms, update
181  // destination register as well.
182  if (Reg0 == Reg1) {
183    // Must be two address instruction!
184    assert(MI->getDesc().getOperandConstraint(0, MCOI::TIED_TO) &&
185           "Expecting a two-address instruction!");
186    Reg2IsKill = false;
187    ChangeReg0 = true;
188  }
189
190  // Masks.
191  unsigned MB = MI->getOperand(4).getImm();
192  unsigned ME = MI->getOperand(5).getImm();
193
194  if (NewMI) {
195    // Create a new instruction.
196    unsigned Reg0 = ChangeReg0 ? Reg2 : MI->getOperand(0).getReg();
197    bool Reg0IsDead = MI->getOperand(0).isDead();
198    return BuildMI(MF, MI->getDebugLoc(), MI->getDesc())
199      .addReg(Reg0, RegState::Define | getDeadRegState(Reg0IsDead))
200      .addReg(Reg2, getKillRegState(Reg2IsKill))
201      .addReg(Reg1, getKillRegState(Reg1IsKill))
202      .addImm((ME+1) & 31)
203      .addImm((MB-1) & 31);
204  }
205
206  if (ChangeReg0)
207    MI->getOperand(0).setReg(Reg2);
208  MI->getOperand(2).setReg(Reg1);
209  MI->getOperand(1).setReg(Reg2);
210  MI->getOperand(2).setIsKill(Reg1IsKill);
211  MI->getOperand(1).setIsKill(Reg2IsKill);
212
213  // Swap the mask around.
214  MI->getOperand(4).setImm((ME+1) & 31);
215  MI->getOperand(5).setImm((MB-1) & 31);
216  return MI;
217}
218
219void PPCInstrInfo::insertNoop(MachineBasicBlock &MBB,
220                              MachineBasicBlock::iterator MI) const {
221  DebugLoc DL;
222  BuildMI(MBB, MI, DL, get(PPC::NOP));
223}
224
225
226// Branch analysis.
227// Note: If the condition register is set to CTR or CTR8 then this is a
228// BDNZ (imm == 1) or BDZ (imm == 0) branch.
229bool PPCInstrInfo::AnalyzeBranch(MachineBasicBlock &MBB,MachineBasicBlock *&TBB,
230                                 MachineBasicBlock *&FBB,
231                                 SmallVectorImpl<MachineOperand> &Cond,
232                                 bool AllowModify) const {
233  bool isPPC64 = TM.getSubtargetImpl()->isPPC64();
234
235  // If the block has no terminators, it just falls into the block after it.
236  MachineBasicBlock::iterator I = MBB.end();
237  if (I == MBB.begin())
238    return false;
239  --I;
240  while (I->isDebugValue()) {
241    if (I == MBB.begin())
242      return false;
243    --I;
244  }
245  if (!isUnpredicatedTerminator(I))
246    return false;
247
248  // Get the last instruction in the block.
249  MachineInstr *LastInst = I;
250
251  // If there is only one terminator instruction, process it.
252  if (I == MBB.begin() || !isUnpredicatedTerminator(--I)) {
253    if (LastInst->getOpcode() == PPC::B) {
254      if (!LastInst->getOperand(0).isMBB())
255        return true;
256      TBB = LastInst->getOperand(0).getMBB();
257      return false;
258    } else if (LastInst->getOpcode() == PPC::BCC) {
259      if (!LastInst->getOperand(2).isMBB())
260        return true;
261      // Block ends with fall-through condbranch.
262      TBB = LastInst->getOperand(2).getMBB();
263      Cond.push_back(LastInst->getOperand(0));
264      Cond.push_back(LastInst->getOperand(1));
265      return false;
266    } else if (LastInst->getOpcode() == PPC::BDNZ8 ||
267               LastInst->getOpcode() == PPC::BDNZ) {
268      if (!LastInst->getOperand(0).isMBB())
269        return true;
270      if (DisableCTRLoopAnal)
271        return true;
272      TBB = LastInst->getOperand(0).getMBB();
273      Cond.push_back(MachineOperand::CreateImm(1));
274      Cond.push_back(MachineOperand::CreateReg(isPPC64 ? PPC::CTR8 : PPC::CTR,
275                                               true));
276      return false;
277    } else if (LastInst->getOpcode() == PPC::BDZ8 ||
278               LastInst->getOpcode() == PPC::BDZ) {
279      if (!LastInst->getOperand(0).isMBB())
280        return true;
281      if (DisableCTRLoopAnal)
282        return true;
283      TBB = LastInst->getOperand(0).getMBB();
284      Cond.push_back(MachineOperand::CreateImm(0));
285      Cond.push_back(MachineOperand::CreateReg(isPPC64 ? PPC::CTR8 : PPC::CTR,
286                                               true));
287      return false;
288    }
289
290    // Otherwise, don't know what this is.
291    return true;
292  }
293
294  // Get the instruction before it if it's a terminator.
295  MachineInstr *SecondLastInst = I;
296
297  // If there are three terminators, we don't know what sort of block this is.
298  if (SecondLastInst && I != MBB.begin() &&
299      isUnpredicatedTerminator(--I))
300    return true;
301
302  // If the block ends with PPC::B and PPC:BCC, handle it.
303  if (SecondLastInst->getOpcode() == PPC::BCC &&
304      LastInst->getOpcode() == PPC::B) {
305    if (!SecondLastInst->getOperand(2).isMBB() ||
306        !LastInst->getOperand(0).isMBB())
307      return true;
308    TBB =  SecondLastInst->getOperand(2).getMBB();
309    Cond.push_back(SecondLastInst->getOperand(0));
310    Cond.push_back(SecondLastInst->getOperand(1));
311    FBB = LastInst->getOperand(0).getMBB();
312    return false;
313  } else if ((SecondLastInst->getOpcode() == PPC::BDNZ8 ||
314              SecondLastInst->getOpcode() == PPC::BDNZ) &&
315      LastInst->getOpcode() == PPC::B) {
316    if (!SecondLastInst->getOperand(0).isMBB() ||
317        !LastInst->getOperand(0).isMBB())
318      return true;
319    if (DisableCTRLoopAnal)
320      return true;
321    TBB = SecondLastInst->getOperand(0).getMBB();
322    Cond.push_back(MachineOperand::CreateImm(1));
323    Cond.push_back(MachineOperand::CreateReg(isPPC64 ? PPC::CTR8 : PPC::CTR,
324                                             true));
325    FBB = LastInst->getOperand(0).getMBB();
326    return false;
327  } else if ((SecondLastInst->getOpcode() == PPC::BDZ8 ||
328              SecondLastInst->getOpcode() == PPC::BDZ) &&
329      LastInst->getOpcode() == PPC::B) {
330    if (!SecondLastInst->getOperand(0).isMBB() ||
331        !LastInst->getOperand(0).isMBB())
332      return true;
333    if (DisableCTRLoopAnal)
334      return true;
335    TBB = SecondLastInst->getOperand(0).getMBB();
336    Cond.push_back(MachineOperand::CreateImm(0));
337    Cond.push_back(MachineOperand::CreateReg(isPPC64 ? PPC::CTR8 : PPC::CTR,
338                                             true));
339    FBB = LastInst->getOperand(0).getMBB();
340    return false;
341  }
342
343  // If the block ends with two PPC:Bs, handle it.  The second one is not
344  // executed, so remove it.
345  if (SecondLastInst->getOpcode() == PPC::B &&
346      LastInst->getOpcode() == PPC::B) {
347    if (!SecondLastInst->getOperand(0).isMBB())
348      return true;
349    TBB = SecondLastInst->getOperand(0).getMBB();
350    I = LastInst;
351    if (AllowModify)
352      I->eraseFromParent();
353    return false;
354  }
355
356  // Otherwise, can't handle this.
357  return true;
358}
359
360unsigned PPCInstrInfo::RemoveBranch(MachineBasicBlock &MBB) const {
361  MachineBasicBlock::iterator I = MBB.end();
362  if (I == MBB.begin()) return 0;
363  --I;
364  while (I->isDebugValue()) {
365    if (I == MBB.begin())
366      return 0;
367    --I;
368  }
369  if (I->getOpcode() != PPC::B && I->getOpcode() != PPC::BCC &&
370      I->getOpcode() != PPC::BDNZ8 && I->getOpcode() != PPC::BDNZ &&
371      I->getOpcode() != PPC::BDZ8  && I->getOpcode() != PPC::BDZ)
372    return 0;
373
374  // Remove the branch.
375  I->eraseFromParent();
376
377  I = MBB.end();
378
379  if (I == MBB.begin()) return 1;
380  --I;
381  if (I->getOpcode() != PPC::BCC &&
382      I->getOpcode() != PPC::BDNZ8 && I->getOpcode() != PPC::BDNZ &&
383      I->getOpcode() != PPC::BDZ8  && I->getOpcode() != PPC::BDZ)
384    return 1;
385
386  // Remove the branch.
387  I->eraseFromParent();
388  return 2;
389}
390
391unsigned
392PPCInstrInfo::InsertBranch(MachineBasicBlock &MBB, MachineBasicBlock *TBB,
393                           MachineBasicBlock *FBB,
394                           const SmallVectorImpl<MachineOperand> &Cond,
395                           DebugLoc DL) const {
396  // Shouldn't be a fall through.
397  assert(TBB && "InsertBranch must not be told to insert a fallthrough");
398  assert((Cond.size() == 2 || Cond.size() == 0) &&
399         "PPC branch conditions have two components!");
400
401  bool isPPC64 = TM.getSubtargetImpl()->isPPC64();
402
403  // One-way branch.
404  if (FBB == 0) {
405    if (Cond.empty())   // Unconditional branch
406      BuildMI(&MBB, DL, get(PPC::B)).addMBB(TBB);
407    else if (Cond[1].getReg() == PPC::CTR || Cond[1].getReg() == PPC::CTR8)
408      BuildMI(&MBB, DL, get(Cond[0].getImm() ?
409                              (isPPC64 ? PPC::BDNZ8 : PPC::BDNZ) :
410                              (isPPC64 ? PPC::BDZ8  : PPC::BDZ))).addMBB(TBB);
411    else                // Conditional branch
412      BuildMI(&MBB, DL, get(PPC::BCC))
413        .addImm(Cond[0].getImm()).addReg(Cond[1].getReg()).addMBB(TBB);
414    return 1;
415  }
416
417  // Two-way Conditional Branch.
418  if (Cond[1].getReg() == PPC::CTR || Cond[1].getReg() == PPC::CTR8)
419    BuildMI(&MBB, DL, get(Cond[0].getImm() ?
420                            (isPPC64 ? PPC::BDNZ8 : PPC::BDNZ) :
421                            (isPPC64 ? PPC::BDZ8  : PPC::BDZ))).addMBB(TBB);
422  else
423    BuildMI(&MBB, DL, get(PPC::BCC))
424      .addImm(Cond[0].getImm()).addReg(Cond[1].getReg()).addMBB(TBB);
425  BuildMI(&MBB, DL, get(PPC::B)).addMBB(FBB);
426  return 2;
427}
428
429// Select analysis.
430bool PPCInstrInfo::canInsertSelect(const MachineBasicBlock &MBB,
431                const SmallVectorImpl<MachineOperand> &Cond,
432                unsigned TrueReg, unsigned FalseReg,
433                int &CondCycles, int &TrueCycles, int &FalseCycles) const {
434  if (!TM.getSubtargetImpl()->hasISEL())
435    return false;
436
437  if (Cond.size() != 2)
438    return false;
439
440  // If this is really a bdnz-like condition, then it cannot be turned into a
441  // select.
442  if (Cond[1].getReg() == PPC::CTR || Cond[1].getReg() == PPC::CTR8)
443    return false;
444
445  // Check register classes.
446  const MachineRegisterInfo &MRI = MBB.getParent()->getRegInfo();
447  const TargetRegisterClass *RC =
448    RI.getCommonSubClass(MRI.getRegClass(TrueReg), MRI.getRegClass(FalseReg));
449  if (!RC)
450    return false;
451
452  // isel is for regular integer GPRs only.
453  if (!PPC::GPRCRegClass.hasSubClassEq(RC) &&
454      !PPC::GPRC_NOR0RegClass.hasSubClassEq(RC) &&
455      !PPC::G8RCRegClass.hasSubClassEq(RC) &&
456      !PPC::G8RC_NOX0RegClass.hasSubClassEq(RC))
457    return false;
458
459  // FIXME: These numbers are for the A2, how well they work for other cores is
460  // an open question. On the A2, the isel instruction has a 2-cycle latency
461  // but single-cycle throughput. These numbers are used in combination with
462  // the MispredictPenalty setting from the active SchedMachineModel.
463  CondCycles = 1;
464  TrueCycles = 1;
465  FalseCycles = 1;
466
467  return true;
468}
469
470void PPCInstrInfo::insertSelect(MachineBasicBlock &MBB,
471                                MachineBasicBlock::iterator MI, DebugLoc dl,
472                                unsigned DestReg,
473                                const SmallVectorImpl<MachineOperand> &Cond,
474                                unsigned TrueReg, unsigned FalseReg) const {
475  assert(Cond.size() == 2 &&
476         "PPC branch conditions have two components!");
477
478  assert(TM.getSubtargetImpl()->hasISEL() &&
479         "Cannot insert select on target without ISEL support");
480
481  // Get the register classes.
482  MachineRegisterInfo &MRI = MBB.getParent()->getRegInfo();
483  const TargetRegisterClass *RC =
484    RI.getCommonSubClass(MRI.getRegClass(TrueReg), MRI.getRegClass(FalseReg));
485  assert(RC && "TrueReg and FalseReg must have overlapping register classes");
486
487  bool Is64Bit = PPC::G8RCRegClass.hasSubClassEq(RC) ||
488                 PPC::G8RC_NOX0RegClass.hasSubClassEq(RC);
489  assert((Is64Bit ||
490          PPC::GPRCRegClass.hasSubClassEq(RC) ||
491          PPC::GPRC_NOR0RegClass.hasSubClassEq(RC)) &&
492         "isel is for regular integer GPRs only");
493
494  unsigned OpCode = Is64Bit ? PPC::ISEL8 : PPC::ISEL;
495  unsigned SelectPred = Cond[0].getImm();
496
497  unsigned SubIdx;
498  bool SwapOps;
499  switch (SelectPred) {
500  default: llvm_unreachable("invalid predicate for isel");
501  case PPC::PRED_EQ: SubIdx = PPC::sub_eq; SwapOps = false; break;
502  case PPC::PRED_NE: SubIdx = PPC::sub_eq; SwapOps = true; break;
503  case PPC::PRED_LT: SubIdx = PPC::sub_lt; SwapOps = false; break;
504  case PPC::PRED_GE: SubIdx = PPC::sub_lt; SwapOps = true; break;
505  case PPC::PRED_GT: SubIdx = PPC::sub_gt; SwapOps = false; break;
506  case PPC::PRED_LE: SubIdx = PPC::sub_gt; SwapOps = true; break;
507  case PPC::PRED_UN: SubIdx = PPC::sub_un; SwapOps = false; break;
508  case PPC::PRED_NU: SubIdx = PPC::sub_un; SwapOps = true; break;
509  }
510
511  unsigned FirstReg =  SwapOps ? FalseReg : TrueReg,
512           SecondReg = SwapOps ? TrueReg  : FalseReg;
513
514  // The first input register of isel cannot be r0. If it is a member
515  // of a register class that can be r0, then copy it first (the
516  // register allocator should eliminate the copy).
517  if (MRI.getRegClass(FirstReg)->contains(PPC::R0) ||
518      MRI.getRegClass(FirstReg)->contains(PPC::X0)) {
519    const TargetRegisterClass *FirstRC =
520      MRI.getRegClass(FirstReg)->contains(PPC::X0) ?
521        &PPC::G8RC_NOX0RegClass : &PPC::GPRC_NOR0RegClass;
522    unsigned OldFirstReg = FirstReg;
523    FirstReg = MRI.createVirtualRegister(FirstRC);
524    BuildMI(MBB, MI, dl, get(TargetOpcode::COPY), FirstReg)
525      .addReg(OldFirstReg);
526  }
527
528  BuildMI(MBB, MI, dl, get(OpCode), DestReg)
529    .addReg(FirstReg).addReg(SecondReg)
530    .addReg(Cond[1].getReg(), 0, SubIdx);
531}
532
533void PPCInstrInfo::copyPhysReg(MachineBasicBlock &MBB,
534                               MachineBasicBlock::iterator I, DebugLoc DL,
535                               unsigned DestReg, unsigned SrcReg,
536                               bool KillSrc) const {
537  unsigned Opc;
538  if (PPC::GPRCRegClass.contains(DestReg, SrcReg))
539    Opc = PPC::OR;
540  else if (PPC::G8RCRegClass.contains(DestReg, SrcReg))
541    Opc = PPC::OR8;
542  else if (PPC::F4RCRegClass.contains(DestReg, SrcReg))
543    Opc = PPC::FMR;
544  else if (PPC::CRRCRegClass.contains(DestReg, SrcReg))
545    Opc = PPC::MCRF;
546  else if (PPC::VRRCRegClass.contains(DestReg, SrcReg))
547    Opc = PPC::VOR;
548  else if (PPC::CRBITRCRegClass.contains(DestReg, SrcReg))
549    Opc = PPC::CROR;
550  else
551    llvm_unreachable("Impossible reg-to-reg copy");
552
553  const MCInstrDesc &MCID = get(Opc);
554  if (MCID.getNumOperands() == 3)
555    BuildMI(MBB, I, DL, MCID, DestReg)
556      .addReg(SrcReg).addReg(SrcReg, getKillRegState(KillSrc));
557  else
558    BuildMI(MBB, I, DL, MCID, DestReg).addReg(SrcReg, getKillRegState(KillSrc));
559}
560
561// This function returns true if a CR spill is necessary and false otherwise.
562bool
563PPCInstrInfo::StoreRegToStackSlot(MachineFunction &MF,
564                                  unsigned SrcReg, bool isKill,
565                                  int FrameIdx,
566                                  const TargetRegisterClass *RC,
567                                  SmallVectorImpl<MachineInstr*> &NewMIs,
568                                  bool &NonRI, bool &SpillsVRS) const{
569  // Note: If additional store instructions are added here,
570  // update isStoreToStackSlot.
571
572  DebugLoc DL;
573  if (PPC::GPRCRegClass.hasSubClassEq(RC)) {
574    NewMIs.push_back(addFrameReference(BuildMI(MF, DL, get(PPC::STW))
575                                       .addReg(SrcReg,
576                                               getKillRegState(isKill)),
577                                       FrameIdx));
578  } else if (PPC::G8RCRegClass.hasSubClassEq(RC)) {
579    NewMIs.push_back(addFrameReference(BuildMI(MF, DL, get(PPC::STD))
580                                       .addReg(SrcReg,
581                                               getKillRegState(isKill)),
582                                       FrameIdx));
583  } else if (PPC::F8RCRegClass.hasSubClassEq(RC)) {
584    NewMIs.push_back(addFrameReference(BuildMI(MF, DL, get(PPC::STFD))
585                                       .addReg(SrcReg,
586                                               getKillRegState(isKill)),
587                                       FrameIdx));
588  } else if (PPC::F4RCRegClass.hasSubClassEq(RC)) {
589    NewMIs.push_back(addFrameReference(BuildMI(MF, DL, get(PPC::STFS))
590                                       .addReg(SrcReg,
591                                               getKillRegState(isKill)),
592                                       FrameIdx));
593  } else if (PPC::CRRCRegClass.hasSubClassEq(RC)) {
594    NewMIs.push_back(addFrameReference(BuildMI(MF, DL, get(PPC::SPILL_CR))
595                                       .addReg(SrcReg,
596                                               getKillRegState(isKill)),
597                                       FrameIdx));
598    return true;
599  } else if (PPC::CRBITRCRegClass.hasSubClassEq(RC)) {
600    // FIXME: We use CRi here because there is no mtcrf on a bit. Since the
601    // backend currently only uses CR1EQ as an individual bit, this should
602    // not cause any bug. If we need other uses of CR bits, the following
603    // code may be invalid.
604    unsigned Reg = 0;
605    if (SrcReg == PPC::CR0LT || SrcReg == PPC::CR0GT ||
606        SrcReg == PPC::CR0EQ || SrcReg == PPC::CR0UN)
607      Reg = PPC::CR0;
608    else if (SrcReg == PPC::CR1LT || SrcReg == PPC::CR1GT ||
609             SrcReg == PPC::CR1EQ || SrcReg == PPC::CR1UN)
610      Reg = PPC::CR1;
611    else if (SrcReg == PPC::CR2LT || SrcReg == PPC::CR2GT ||
612             SrcReg == PPC::CR2EQ || SrcReg == PPC::CR2UN)
613      Reg = PPC::CR2;
614    else if (SrcReg == PPC::CR3LT || SrcReg == PPC::CR3GT ||
615             SrcReg == PPC::CR3EQ || SrcReg == PPC::CR3UN)
616      Reg = PPC::CR3;
617    else if (SrcReg == PPC::CR4LT || SrcReg == PPC::CR4GT ||
618             SrcReg == PPC::CR4EQ || SrcReg == PPC::CR4UN)
619      Reg = PPC::CR4;
620    else if (SrcReg == PPC::CR5LT || SrcReg == PPC::CR5GT ||
621             SrcReg == PPC::CR5EQ || SrcReg == PPC::CR5UN)
622      Reg = PPC::CR5;
623    else if (SrcReg == PPC::CR6LT || SrcReg == PPC::CR6GT ||
624             SrcReg == PPC::CR6EQ || SrcReg == PPC::CR6UN)
625      Reg = PPC::CR6;
626    else if (SrcReg == PPC::CR7LT || SrcReg == PPC::CR7GT ||
627             SrcReg == PPC::CR7EQ || SrcReg == PPC::CR7UN)
628      Reg = PPC::CR7;
629
630    return StoreRegToStackSlot(MF, Reg, isKill, FrameIdx,
631                               &PPC::CRRCRegClass, NewMIs, NonRI, SpillsVRS);
632
633  } else if (PPC::VRRCRegClass.hasSubClassEq(RC)) {
634    NewMIs.push_back(addFrameReference(BuildMI(MF, DL, get(PPC::STVX))
635                                       .addReg(SrcReg,
636                                               getKillRegState(isKill)),
637                                       FrameIdx));
638    NonRI = true;
639  } else if (PPC::VRSAVERCRegClass.hasSubClassEq(RC)) {
640    assert(TM.getSubtargetImpl()->isDarwin() &&
641           "VRSAVE only needs spill/restore on Darwin");
642    NewMIs.push_back(addFrameReference(BuildMI(MF, DL, get(PPC::SPILL_VRSAVE))
643                                       .addReg(SrcReg,
644                                               getKillRegState(isKill)),
645                                       FrameIdx));
646    SpillsVRS = true;
647  } else {
648    llvm_unreachable("Unknown regclass!");
649  }
650
651  return false;
652}
653
654void
655PPCInstrInfo::storeRegToStackSlot(MachineBasicBlock &MBB,
656                                  MachineBasicBlock::iterator MI,
657                                  unsigned SrcReg, bool isKill, int FrameIdx,
658                                  const TargetRegisterClass *RC,
659                                  const TargetRegisterInfo *TRI) const {
660  MachineFunction &MF = *MBB.getParent();
661  SmallVector<MachineInstr*, 4> NewMIs;
662
663  PPCFunctionInfo *FuncInfo = MF.getInfo<PPCFunctionInfo>();
664  FuncInfo->setHasSpills();
665
666  bool NonRI = false, SpillsVRS = false;
667  if (StoreRegToStackSlot(MF, SrcReg, isKill, FrameIdx, RC, NewMIs,
668                          NonRI, SpillsVRS))
669    FuncInfo->setSpillsCR();
670
671  if (SpillsVRS)
672    FuncInfo->setSpillsVRSAVE();
673
674  if (NonRI)
675    FuncInfo->setHasNonRISpills();
676
677  for (unsigned i = 0, e = NewMIs.size(); i != e; ++i)
678    MBB.insert(MI, NewMIs[i]);
679
680  const MachineFrameInfo &MFI = *MF.getFrameInfo();
681  MachineMemOperand *MMO =
682    MF.getMachineMemOperand(MachinePointerInfo::getFixedStack(FrameIdx),
683                            MachineMemOperand::MOStore,
684                            MFI.getObjectSize(FrameIdx),
685                            MFI.getObjectAlignment(FrameIdx));
686  NewMIs.back()->addMemOperand(MF, MMO);
687}
688
689bool
690PPCInstrInfo::LoadRegFromStackSlot(MachineFunction &MF, DebugLoc DL,
691                                   unsigned DestReg, int FrameIdx,
692                                   const TargetRegisterClass *RC,
693                                   SmallVectorImpl<MachineInstr*> &NewMIs,
694                                   bool &NonRI, bool &SpillsVRS) const{
695  // Note: If additional load instructions are added here,
696  // update isLoadFromStackSlot.
697
698  if (PPC::GPRCRegClass.hasSubClassEq(RC)) {
699    NewMIs.push_back(addFrameReference(BuildMI(MF, DL, get(PPC::LWZ),
700                                               DestReg), FrameIdx));
701  } else if (PPC::G8RCRegClass.hasSubClassEq(RC)) {
702    NewMIs.push_back(addFrameReference(BuildMI(MF, DL, get(PPC::LD), DestReg),
703                                       FrameIdx));
704  } else if (PPC::F8RCRegClass.hasSubClassEq(RC)) {
705    NewMIs.push_back(addFrameReference(BuildMI(MF, DL, get(PPC::LFD), DestReg),
706                                       FrameIdx));
707  } else if (PPC::F4RCRegClass.hasSubClassEq(RC)) {
708    NewMIs.push_back(addFrameReference(BuildMI(MF, DL, get(PPC::LFS), DestReg),
709                                       FrameIdx));
710  } else if (PPC::CRRCRegClass.hasSubClassEq(RC)) {
711    NewMIs.push_back(addFrameReference(BuildMI(MF, DL,
712                                               get(PPC::RESTORE_CR), DestReg),
713                                       FrameIdx));
714    return true;
715  } else if (PPC::CRBITRCRegClass.hasSubClassEq(RC)) {
716
717    unsigned Reg = 0;
718    if (DestReg == PPC::CR0LT || DestReg == PPC::CR0GT ||
719        DestReg == PPC::CR0EQ || DestReg == PPC::CR0UN)
720      Reg = PPC::CR0;
721    else if (DestReg == PPC::CR1LT || DestReg == PPC::CR1GT ||
722             DestReg == PPC::CR1EQ || DestReg == PPC::CR1UN)
723      Reg = PPC::CR1;
724    else if (DestReg == PPC::CR2LT || DestReg == PPC::CR2GT ||
725             DestReg == PPC::CR2EQ || DestReg == PPC::CR2UN)
726      Reg = PPC::CR2;
727    else if (DestReg == PPC::CR3LT || DestReg == PPC::CR3GT ||
728             DestReg == PPC::CR3EQ || DestReg == PPC::CR3UN)
729      Reg = PPC::CR3;
730    else if (DestReg == PPC::CR4LT || DestReg == PPC::CR4GT ||
731             DestReg == PPC::CR4EQ || DestReg == PPC::CR4UN)
732      Reg = PPC::CR4;
733    else if (DestReg == PPC::CR5LT || DestReg == PPC::CR5GT ||
734             DestReg == PPC::CR5EQ || DestReg == PPC::CR5UN)
735      Reg = PPC::CR5;
736    else if (DestReg == PPC::CR6LT || DestReg == PPC::CR6GT ||
737             DestReg == PPC::CR6EQ || DestReg == PPC::CR6UN)
738      Reg = PPC::CR6;
739    else if (DestReg == PPC::CR7LT || DestReg == PPC::CR7GT ||
740             DestReg == PPC::CR7EQ || DestReg == PPC::CR7UN)
741      Reg = PPC::CR7;
742
743    return LoadRegFromStackSlot(MF, DL, Reg, FrameIdx,
744                                &PPC::CRRCRegClass, NewMIs, NonRI, SpillsVRS);
745
746  } else if (PPC::VRRCRegClass.hasSubClassEq(RC)) {
747    NewMIs.push_back(addFrameReference(BuildMI(MF, DL, get(PPC::LVX), DestReg),
748                                       FrameIdx));
749    NonRI = true;
750  } else if (PPC::VRSAVERCRegClass.hasSubClassEq(RC)) {
751    assert(TM.getSubtargetImpl()->isDarwin() &&
752           "VRSAVE only needs spill/restore on Darwin");
753    NewMIs.push_back(addFrameReference(BuildMI(MF, DL,
754                                               get(PPC::RESTORE_VRSAVE),
755                                               DestReg),
756                                       FrameIdx));
757    SpillsVRS = true;
758  } else {
759    llvm_unreachable("Unknown regclass!");
760  }
761
762  return false;
763}
764
765void
766PPCInstrInfo::loadRegFromStackSlot(MachineBasicBlock &MBB,
767                                   MachineBasicBlock::iterator MI,
768                                   unsigned DestReg, int FrameIdx,
769                                   const TargetRegisterClass *RC,
770                                   const TargetRegisterInfo *TRI) const {
771  MachineFunction &MF = *MBB.getParent();
772  SmallVector<MachineInstr*, 4> NewMIs;
773  DebugLoc DL;
774  if (MI != MBB.end()) DL = MI->getDebugLoc();
775
776  PPCFunctionInfo *FuncInfo = MF.getInfo<PPCFunctionInfo>();
777  FuncInfo->setHasSpills();
778
779  bool NonRI = false, SpillsVRS = false;
780  if (LoadRegFromStackSlot(MF, DL, DestReg, FrameIdx, RC, NewMIs,
781                           NonRI, SpillsVRS))
782    FuncInfo->setSpillsCR();
783
784  if (SpillsVRS)
785    FuncInfo->setSpillsVRSAVE();
786
787  if (NonRI)
788    FuncInfo->setHasNonRISpills();
789
790  for (unsigned i = 0, e = NewMIs.size(); i != e; ++i)
791    MBB.insert(MI, NewMIs[i]);
792
793  const MachineFrameInfo &MFI = *MF.getFrameInfo();
794  MachineMemOperand *MMO =
795    MF.getMachineMemOperand(MachinePointerInfo::getFixedStack(FrameIdx),
796                            MachineMemOperand::MOLoad,
797                            MFI.getObjectSize(FrameIdx),
798                            MFI.getObjectAlignment(FrameIdx));
799  NewMIs.back()->addMemOperand(MF, MMO);
800}
801
802bool PPCInstrInfo::
803ReverseBranchCondition(SmallVectorImpl<MachineOperand> &Cond) const {
804  assert(Cond.size() == 2 && "Invalid PPC branch opcode!");
805  if (Cond[1].getReg() == PPC::CTR8 || Cond[1].getReg() == PPC::CTR)
806    Cond[0].setImm(Cond[0].getImm() == 0 ? 1 : 0);
807  else
808    // Leave the CR# the same, but invert the condition.
809    Cond[0].setImm(PPC::InvertPredicate((PPC::Predicate)Cond[0].getImm()));
810  return false;
811}
812
813bool PPCInstrInfo::FoldImmediate(MachineInstr *UseMI, MachineInstr *DefMI,
814                             unsigned Reg, MachineRegisterInfo *MRI) const {
815  // For some instructions, it is legal to fold ZERO into the RA register field.
816  // A zero immediate should always be loaded with a single li.
817  unsigned DefOpc = DefMI->getOpcode();
818  if (DefOpc != PPC::LI && DefOpc != PPC::LI8)
819    return false;
820  if (!DefMI->getOperand(1).isImm())
821    return false;
822  if (DefMI->getOperand(1).getImm() != 0)
823    return false;
824
825  // Note that we cannot here invert the arguments of an isel in order to fold
826  // a ZERO into what is presented as the second argument. All we have here
827  // is the condition bit, and that might come from a CR-logical bit operation.
828
829  const MCInstrDesc &UseMCID = UseMI->getDesc();
830
831  // Only fold into real machine instructions.
832  if (UseMCID.isPseudo())
833    return false;
834
835  unsigned UseIdx;
836  for (UseIdx = 0; UseIdx < UseMI->getNumOperands(); ++UseIdx)
837    if (UseMI->getOperand(UseIdx).isReg() &&
838        UseMI->getOperand(UseIdx).getReg() == Reg)
839      break;
840
841  assert(UseIdx < UseMI->getNumOperands() && "Cannot find Reg in UseMI");
842  assert(UseIdx < UseMCID.getNumOperands() && "No operand description for Reg");
843
844  const MCOperandInfo *UseInfo = &UseMCID.OpInfo[UseIdx];
845
846  // We can fold the zero if this register requires a GPRC_NOR0/G8RC_NOX0
847  // register (which might also be specified as a pointer class kind).
848  if (UseInfo->isLookupPtrRegClass()) {
849    if (UseInfo->RegClass /* Kind */ != 1)
850      return false;
851  } else {
852    if (UseInfo->RegClass != PPC::GPRC_NOR0RegClassID &&
853        UseInfo->RegClass != PPC::G8RC_NOX0RegClassID)
854      return false;
855  }
856
857  // Make sure this is not tied to an output register (or otherwise
858  // constrained). This is true for ST?UX registers, for example, which
859  // are tied to their output registers.
860  if (UseInfo->Constraints != 0)
861    return false;
862
863  unsigned ZeroReg;
864  if (UseInfo->isLookupPtrRegClass()) {
865    bool isPPC64 = TM.getSubtargetImpl()->isPPC64();
866    ZeroReg = isPPC64 ? PPC::ZERO8 : PPC::ZERO;
867  } else {
868    ZeroReg = UseInfo->RegClass == PPC::G8RC_NOX0RegClassID ?
869              PPC::ZERO8 : PPC::ZERO;
870  }
871
872  bool DeleteDef = MRI->hasOneNonDBGUse(Reg);
873  UseMI->getOperand(UseIdx).setReg(ZeroReg);
874
875  if (DeleteDef)
876    DefMI->eraseFromParent();
877
878  return true;
879}
880
881static bool MBBDefinesCTR(MachineBasicBlock &MBB) {
882  for (MachineBasicBlock::iterator I = MBB.begin(), IE = MBB.end();
883       I != IE; ++I)
884    if (I->definesRegister(PPC::CTR) || I->definesRegister(PPC::CTR8))
885      return true;
886  return false;
887}
888
889// We should make sure that, if we're going to predicate both sides of a
890// condition (a diamond), that both sides don't define the counter register. We
891// can predicate counter-decrement-based branches, but while that predicates
892// the branching, it does not predicate the counter decrement. If we tried to
893// merge the triangle into one predicated block, we'd decrement the counter
894// twice.
895bool PPCInstrInfo::isProfitableToIfCvt(MachineBasicBlock &TMBB,
896                     unsigned NumT, unsigned ExtraT,
897                     MachineBasicBlock &FMBB,
898                     unsigned NumF, unsigned ExtraF,
899                     const BranchProbability &Probability) const {
900  return !(MBBDefinesCTR(TMBB) && MBBDefinesCTR(FMBB));
901}
902
903
904bool PPCInstrInfo::isPredicated(const MachineInstr *MI) const {
905  // The predicated branches are identified by their type, not really by the
906  // explicit presence of a predicate. Furthermore, some of them can be
907  // predicated more than once. Because if conversion won't try to predicate
908  // any instruction which already claims to be predicated (by returning true
909  // here), always return false. In doing so, we let isPredicable() be the
910  // final word on whether not the instruction can be (further) predicated.
911
912  return false;
913}
914
915bool PPCInstrInfo::isUnpredicatedTerminator(const MachineInstr *MI) const {
916  if (!MI->isTerminator())
917    return false;
918
919  // Conditional branch is a special case.
920  if (MI->isBranch() && !MI->isBarrier())
921    return true;
922
923  return !isPredicated(MI);
924}
925
926bool PPCInstrInfo::PredicateInstruction(
927                     MachineInstr *MI,
928                     const SmallVectorImpl<MachineOperand> &Pred) const {
929  unsigned OpC = MI->getOpcode();
930  if (OpC == PPC::BLR) {
931    if (Pred[1].getReg() == PPC::CTR8 || Pred[1].getReg() == PPC::CTR) {
932      bool isPPC64 = TM.getSubtargetImpl()->isPPC64();
933      MI->setDesc(get(Pred[0].getImm() ?
934                      (isPPC64 ? PPC::BDNZLR8 : PPC::BDNZLR) :
935                      (isPPC64 ? PPC::BDZLR8  : PPC::BDZLR)));
936    } else {
937      MI->setDesc(get(PPC::BCLR));
938      MachineInstrBuilder(*MI->getParent()->getParent(), MI)
939        .addImm(Pred[0].getImm())
940        .addReg(Pred[1].getReg());
941    }
942
943    return true;
944  } else if (OpC == PPC::B) {
945    if (Pred[1].getReg() == PPC::CTR8 || Pred[1].getReg() == PPC::CTR) {
946      bool isPPC64 = TM.getSubtargetImpl()->isPPC64();
947      MI->setDesc(get(Pred[0].getImm() ?
948                      (isPPC64 ? PPC::BDNZ8 : PPC::BDNZ) :
949                      (isPPC64 ? PPC::BDZ8  : PPC::BDZ)));
950    } else {
951      MachineBasicBlock *MBB = MI->getOperand(0).getMBB();
952      MI->RemoveOperand(0);
953
954      MI->setDesc(get(PPC::BCC));
955      MachineInstrBuilder(*MI->getParent()->getParent(), MI)
956        .addImm(Pred[0].getImm())
957        .addReg(Pred[1].getReg())
958        .addMBB(MBB);
959    }
960
961    return true;
962  } else if (OpC == PPC::BCTR  || OpC == PPC::BCTR8 ||
963             OpC == PPC::BCTRL || OpC == PPC::BCTRL8) {
964    if (Pred[1].getReg() == PPC::CTR8 || Pred[1].getReg() == PPC::CTR)
965      llvm_unreachable("Cannot predicate bctr[l] on the ctr register");
966
967    bool setLR = OpC == PPC::BCTRL || OpC == PPC::BCTRL8;
968    bool isPPC64 = TM.getSubtargetImpl()->isPPC64();
969    MI->setDesc(get(isPPC64 ? (setLR ? PPC::BCCTRL8 : PPC::BCCTR8) :
970                              (setLR ? PPC::BCCTRL  : PPC::BCCTR)));
971    MachineInstrBuilder(*MI->getParent()->getParent(), MI)
972      .addImm(Pred[0].getImm())
973      .addReg(Pred[1].getReg());
974    return true;
975  }
976
977  return false;
978}
979
980bool PPCInstrInfo::SubsumesPredicate(
981                     const SmallVectorImpl<MachineOperand> &Pred1,
982                     const SmallVectorImpl<MachineOperand> &Pred2) const {
983  assert(Pred1.size() == 2 && "Invalid PPC first predicate");
984  assert(Pred2.size() == 2 && "Invalid PPC second predicate");
985
986  if (Pred1[1].getReg() == PPC::CTR8 || Pred1[1].getReg() == PPC::CTR)
987    return false;
988  if (Pred2[1].getReg() == PPC::CTR8 || Pred2[1].getReg() == PPC::CTR)
989    return false;
990
991  // P1 can only subsume P2 if they test the same condition register.
992  if (Pred1[1].getReg() != Pred2[1].getReg())
993    return false;
994
995  PPC::Predicate P1 = (PPC::Predicate) Pred1[0].getImm();
996  PPC::Predicate P2 = (PPC::Predicate) Pred2[0].getImm();
997
998  if (P1 == P2)
999    return true;
1000
1001  // Does P1 subsume P2, e.g. GE subsumes GT.
1002  if (P1 == PPC::PRED_LE &&
1003      (P2 == PPC::PRED_LT || P2 == PPC::PRED_EQ))
1004    return true;
1005  if (P1 == PPC::PRED_GE &&
1006      (P2 == PPC::PRED_GT || P2 == PPC::PRED_EQ))
1007    return true;
1008
1009  return false;
1010}
1011
1012bool PPCInstrInfo::DefinesPredicate(MachineInstr *MI,
1013                                    std::vector<MachineOperand> &Pred) const {
1014  // Note: At the present time, the contents of Pred from this function is
1015  // unused by IfConversion. This implementation follows ARM by pushing the
1016  // CR-defining operand. Because the 'DZ' and 'DNZ' count as types of
1017  // predicate, instructions defining CTR or CTR8 are also included as
1018  // predicate-defining instructions.
1019
1020  const TargetRegisterClass *RCs[] =
1021    { &PPC::CRRCRegClass, &PPC::CRBITRCRegClass,
1022      &PPC::CTRRCRegClass, &PPC::CTRRC8RegClass };
1023
1024  bool Found = false;
1025  for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
1026    const MachineOperand &MO = MI->getOperand(i);
1027    for (unsigned c = 0; c < array_lengthof(RCs) && !Found; ++c) {
1028      const TargetRegisterClass *RC = RCs[c];
1029      if (MO.isReg()) {
1030        if (MO.isDef() && RC->contains(MO.getReg())) {
1031          Pred.push_back(MO);
1032          Found = true;
1033        }
1034      } else if (MO.isRegMask()) {
1035        for (TargetRegisterClass::iterator I = RC->begin(),
1036             IE = RC->end(); I != IE; ++I)
1037          if (MO.clobbersPhysReg(*I)) {
1038            Pred.push_back(MO);
1039            Found = true;
1040          }
1041      }
1042    }
1043  }
1044
1045  return Found;
1046}
1047
1048bool PPCInstrInfo::isPredicable(MachineInstr *MI) const {
1049  unsigned OpC = MI->getOpcode();
1050  switch (OpC) {
1051  default:
1052    return false;
1053  case PPC::B:
1054  case PPC::BLR:
1055  case PPC::BCTR:
1056  case PPC::BCTR8:
1057  case PPC::BCTRL:
1058  case PPC::BCTRL8:
1059    return true;
1060  }
1061}
1062
1063bool PPCInstrInfo::analyzeCompare(const MachineInstr *MI,
1064                                  unsigned &SrcReg, unsigned &SrcReg2,
1065                                  int &Mask, int &Value) const {
1066  unsigned Opc = MI->getOpcode();
1067
1068  switch (Opc) {
1069  default: return false;
1070  case PPC::CMPWI:
1071  case PPC::CMPLWI:
1072  case PPC::CMPDI:
1073  case PPC::CMPLDI:
1074    SrcReg = MI->getOperand(1).getReg();
1075    SrcReg2 = 0;
1076    Value = MI->getOperand(2).getImm();
1077    Mask = 0xFFFF;
1078    return true;
1079  case PPC::CMPW:
1080  case PPC::CMPLW:
1081  case PPC::CMPD:
1082  case PPC::CMPLD:
1083  case PPC::FCMPUS:
1084  case PPC::FCMPUD:
1085    SrcReg = MI->getOperand(1).getReg();
1086    SrcReg2 = MI->getOperand(2).getReg();
1087    return true;
1088  }
1089}
1090
1091bool PPCInstrInfo::optimizeCompareInstr(MachineInstr *CmpInstr,
1092                                        unsigned SrcReg, unsigned SrcReg2,
1093                                        int Mask, int Value,
1094                                        const MachineRegisterInfo *MRI) const {
1095  if (DisableCmpOpt)
1096    return false;
1097
1098  int OpC = CmpInstr->getOpcode();
1099  unsigned CRReg = CmpInstr->getOperand(0).getReg();
1100
1101  // FP record forms set CR1 based on the execption status bits, not a
1102  // comparison with zero.
1103  if (OpC == PPC::FCMPUS || OpC == PPC::FCMPUD)
1104    return false;
1105
1106  // The record forms set the condition register based on a signed comparison
1107  // with zero (so says the ISA manual). This is not as straightforward as it
1108  // seems, however, because this is always a 64-bit comparison on PPC64, even
1109  // for instructions that are 32-bit in nature (like slw for example).
1110  // So, on PPC32, for unsigned comparisons, we can use the record forms only
1111  // for equality checks (as those don't depend on the sign). On PPC64,
1112  // we are restricted to equality for unsigned 64-bit comparisons and for
1113  // signed 32-bit comparisons the applicability is more restricted.
1114  bool isPPC64 = TM.getSubtargetImpl()->isPPC64();
1115  bool is32BitSignedCompare   = OpC ==  PPC::CMPWI || OpC == PPC::CMPW;
1116  bool is32BitUnsignedCompare = OpC == PPC::CMPLWI || OpC == PPC::CMPLW;
1117  bool is64BitUnsignedCompare = OpC == PPC::CMPLDI || OpC == PPC::CMPLD;
1118
1119  // Get the unique definition of SrcReg.
1120  MachineInstr *MI = MRI->getUniqueVRegDef(SrcReg);
1121  if (!MI) return false;
1122  int MIOpC = MI->getOpcode();
1123
1124  bool equalityOnly = false;
1125  bool noSub = false;
1126  if (isPPC64) {
1127    if (is32BitSignedCompare) {
1128      // We can perform this optimization only if MI is sign-extending.
1129      if (MIOpC == PPC::SRAW  || MIOpC == PPC::SRAWo ||
1130          MIOpC == PPC::SRAWI || MIOpC == PPC::SRAWIo ||
1131          MIOpC == PPC::EXTSB || MIOpC == PPC::EXTSBo ||
1132          MIOpC == PPC::EXTSH || MIOpC == PPC::EXTSHo ||
1133          MIOpC == PPC::EXTSW || MIOpC == PPC::EXTSWo) {
1134        noSub = true;
1135      } else
1136        return false;
1137    } else if (is32BitUnsignedCompare) {
1138      // We can perform this optimization, equality only, if MI is
1139      // zero-extending.
1140      if (MIOpC == PPC::CNTLZW || MIOpC == PPC::CNTLZWo ||
1141          MIOpC == PPC::SLW    || MIOpC == PPC::SLWo ||
1142          MIOpC == PPC::SRW    || MIOpC == PPC::SRWo) {
1143        noSub = true;
1144        equalityOnly = true;
1145      } else
1146        return false;
1147    } else
1148      equalityOnly = is64BitUnsignedCompare;
1149  } else
1150    equalityOnly = is32BitUnsignedCompare;
1151
1152  if (equalityOnly) {
1153    // We need to check the uses of the condition register in order to reject
1154    // non-equality comparisons.
1155    for (MachineRegisterInfo::use_iterator I = MRI->use_begin(CRReg),
1156         IE = MRI->use_end(); I != IE; ++I) {
1157      MachineInstr *UseMI = &*I;
1158      if (UseMI->getOpcode() == PPC::BCC) {
1159        unsigned Pred = UseMI->getOperand(0).getImm();
1160        if (Pred != PPC::PRED_EQ && Pred != PPC::PRED_NE)
1161          return false;
1162      } else if (UseMI->getOpcode() == PPC::ISEL ||
1163                 UseMI->getOpcode() == PPC::ISEL8) {
1164        unsigned SubIdx = UseMI->getOperand(3).getSubReg();
1165        if (SubIdx != PPC::sub_eq)
1166          return false;
1167      } else
1168        return false;
1169    }
1170  }
1171
1172  MachineBasicBlock::iterator I = CmpInstr;
1173
1174  // Scan forward to find the first use of the compare.
1175  for (MachineBasicBlock::iterator EL = CmpInstr->getParent()->end();
1176       I != EL; ++I) {
1177    bool FoundUse = false;
1178    for (MachineRegisterInfo::use_iterator J = MRI->use_begin(CRReg),
1179         JE = MRI->use_end(); J != JE; ++J)
1180      if (&*J == &*I) {
1181        FoundUse = true;
1182        break;
1183      }
1184
1185    if (FoundUse)
1186      break;
1187  }
1188
1189  // There are two possible candidates which can be changed to set CR[01].
1190  // One is MI, the other is a SUB instruction.
1191  // For CMPrr(r1,r2), we are looking for SUB(r1,r2) or SUB(r2,r1).
1192  MachineInstr *Sub = NULL;
1193  if (SrcReg2 != 0)
1194    // MI is not a candidate for CMPrr.
1195    MI = NULL;
1196  // FIXME: Conservatively refuse to convert an instruction which isn't in the
1197  // same BB as the comparison. This is to allow the check below to avoid calls
1198  // (and other explicit clobbers); instead we should really check for these
1199  // more explicitly (in at least a few predecessors).
1200  else if (MI->getParent() != CmpInstr->getParent() || Value != 0) {
1201    // PPC does not have a record-form SUBri.
1202    return false;
1203  }
1204
1205  // Search for Sub.
1206  const TargetRegisterInfo *TRI = &getRegisterInfo();
1207  --I;
1208
1209  // Get ready to iterate backward from CmpInstr.
1210  MachineBasicBlock::iterator E = MI,
1211                              B = CmpInstr->getParent()->begin();
1212
1213  for (; I != E && !noSub; --I) {
1214    const MachineInstr &Instr = *I;
1215    unsigned IOpC = Instr.getOpcode();
1216
1217    if (&*I != CmpInstr && (
1218        Instr.modifiesRegister(PPC::CR0, TRI) ||
1219        Instr.readsRegister(PPC::CR0, TRI)))
1220      // This instruction modifies or uses the record condition register after
1221      // the one we want to change. While we could do this transformation, it
1222      // would likely not be profitable. This transformation removes one
1223      // instruction, and so even forcing RA to generate one move probably
1224      // makes it unprofitable.
1225      return false;
1226
1227    // Check whether CmpInstr can be made redundant by the current instruction.
1228    if ((OpC == PPC::CMPW || OpC == PPC::CMPLW ||
1229         OpC == PPC::CMPD || OpC == PPC::CMPLD) &&
1230        (IOpC == PPC::SUBF || IOpC == PPC::SUBF8) &&
1231        ((Instr.getOperand(1).getReg() == SrcReg &&
1232          Instr.getOperand(2).getReg() == SrcReg2) ||
1233        (Instr.getOperand(1).getReg() == SrcReg2 &&
1234         Instr.getOperand(2).getReg() == SrcReg))) {
1235      Sub = &*I;
1236      break;
1237    }
1238
1239    if (I == B)
1240      // The 'and' is below the comparison instruction.
1241      return false;
1242  }
1243
1244  // Return false if no candidates exist.
1245  if (!MI && !Sub)
1246    return false;
1247
1248  // The single candidate is called MI.
1249  if (!MI) MI = Sub;
1250
1251  int NewOpC = -1;
1252  MIOpC = MI->getOpcode();
1253  if (MIOpC == PPC::ANDIo || MIOpC == PPC::ANDIo8)
1254    NewOpC = MIOpC;
1255  else {
1256    NewOpC = PPC::getRecordFormOpcode(MIOpC);
1257    if (NewOpC == -1 && PPC::getNonRecordFormOpcode(MIOpC) != -1)
1258      NewOpC = MIOpC;
1259  }
1260
1261  // FIXME: On the non-embedded POWER architectures, only some of the record
1262  // forms are fast, and we should use only the fast ones.
1263
1264  // The defining instruction has a record form (or is already a record
1265  // form). It is possible, however, that we'll need to reverse the condition
1266  // code of the users.
1267  if (NewOpC == -1)
1268    return false;
1269
1270  SmallVector<std::pair<MachineOperand*, PPC::Predicate>, 4> PredsToUpdate;
1271  SmallVector<std::pair<MachineOperand*, unsigned>, 4> SubRegsToUpdate;
1272
1273  // If we have SUB(r1, r2) and CMP(r2, r1), the condition code based on CMP
1274  // needs to be updated to be based on SUB.  Push the condition code
1275  // operands to OperandsToUpdate.  If it is safe to remove CmpInstr, the
1276  // condition code of these operands will be modified.
1277  bool ShouldSwap = false;
1278  if (Sub) {
1279    ShouldSwap = SrcReg2 != 0 && Sub->getOperand(1).getReg() == SrcReg2 &&
1280      Sub->getOperand(2).getReg() == SrcReg;
1281
1282    // The operands to subf are the opposite of sub, so only in the fixed-point
1283    // case, invert the order.
1284    ShouldSwap = !ShouldSwap;
1285  }
1286
1287  if (ShouldSwap)
1288    for (MachineRegisterInfo::use_iterator I = MRI->use_begin(CRReg),
1289         IE = MRI->use_end(); I != IE; ++I) {
1290      MachineInstr *UseMI = &*I;
1291      if (UseMI->getOpcode() == PPC::BCC) {
1292        PPC::Predicate Pred = (PPC::Predicate) UseMI->getOperand(0).getImm();
1293        assert((!equalityOnly ||
1294                Pred == PPC::PRED_EQ || Pred == PPC::PRED_NE) &&
1295               "Invalid predicate for equality-only optimization");
1296        PredsToUpdate.push_back(std::make_pair(&((*I).getOperand(0)),
1297                                PPC::getSwappedPredicate(Pred)));
1298      } else if (UseMI->getOpcode() == PPC::ISEL ||
1299                 UseMI->getOpcode() == PPC::ISEL8) {
1300        unsigned NewSubReg = UseMI->getOperand(3).getSubReg();
1301        assert((!equalityOnly || NewSubReg == PPC::sub_eq) &&
1302               "Invalid CR bit for equality-only optimization");
1303
1304        if (NewSubReg == PPC::sub_lt)
1305          NewSubReg = PPC::sub_gt;
1306        else if (NewSubReg == PPC::sub_gt)
1307          NewSubReg = PPC::sub_lt;
1308
1309        SubRegsToUpdate.push_back(std::make_pair(&((*I).getOperand(3)),
1310                                                 NewSubReg));
1311      } else // We need to abort on a user we don't understand.
1312        return false;
1313    }
1314
1315  // Create a new virtual register to hold the value of the CR set by the
1316  // record-form instruction. If the instruction was not previously in
1317  // record form, then set the kill flag on the CR.
1318  CmpInstr->eraseFromParent();
1319
1320  MachineBasicBlock::iterator MII = MI;
1321  BuildMI(*MI->getParent(), llvm::next(MII), MI->getDebugLoc(),
1322          get(TargetOpcode::COPY), CRReg)
1323    .addReg(PPC::CR0, MIOpC != NewOpC ? RegState::Kill : 0);
1324
1325  if (MIOpC != NewOpC) {
1326    // We need to be careful here: we're replacing one instruction with
1327    // another, and we need to make sure that we get all of the right
1328    // implicit uses and defs. On the other hand, the caller may be holding
1329    // an iterator to this instruction, and so we can't delete it (this is
1330    // specifically the case if this is the instruction directly after the
1331    // compare).
1332
1333    const MCInstrDesc &NewDesc = get(NewOpC);
1334    MI->setDesc(NewDesc);
1335
1336    if (NewDesc.ImplicitDefs)
1337      for (const uint16_t *ImpDefs = NewDesc.getImplicitDefs();
1338           *ImpDefs; ++ImpDefs)
1339        if (!MI->definesRegister(*ImpDefs))
1340          MI->addOperand(*MI->getParent()->getParent(),
1341                         MachineOperand::CreateReg(*ImpDefs, true, true));
1342    if (NewDesc.ImplicitUses)
1343      for (const uint16_t *ImpUses = NewDesc.getImplicitUses();
1344           *ImpUses; ++ImpUses)
1345        if (!MI->readsRegister(*ImpUses))
1346          MI->addOperand(*MI->getParent()->getParent(),
1347                         MachineOperand::CreateReg(*ImpUses, false, true));
1348  }
1349
1350  // Modify the condition code of operands in OperandsToUpdate.
1351  // Since we have SUB(r1, r2) and CMP(r2, r1), the condition code needs to
1352  // be changed from r2 > r1 to r1 < r2, from r2 < r1 to r1 > r2, etc.
1353  for (unsigned i = 0, e = PredsToUpdate.size(); i < e; i++)
1354    PredsToUpdate[i].first->setImm(PredsToUpdate[i].second);
1355
1356  for (unsigned i = 0, e = SubRegsToUpdate.size(); i < e; i++)
1357    SubRegsToUpdate[i].first->setSubReg(SubRegsToUpdate[i].second);
1358
1359  return true;
1360}
1361
1362/// GetInstSize - Return the number of bytes of code the specified
1363/// instruction may be.  This returns the maximum number of bytes.
1364///
1365unsigned PPCInstrInfo::GetInstSizeInBytes(const MachineInstr *MI) const {
1366  switch (MI->getOpcode()) {
1367  case PPC::INLINEASM: {       // Inline Asm: Variable size.
1368    const MachineFunction *MF = MI->getParent()->getParent();
1369    const char *AsmStr = MI->getOperand(0).getSymbolName();
1370    return getInlineAsmLength(AsmStr, *MF->getTarget().getMCAsmInfo());
1371  }
1372  case PPC::PROLOG_LABEL:
1373  case PPC::EH_LABEL:
1374  case PPC::GC_LABEL:
1375  case PPC::DBG_VALUE:
1376    return 0;
1377  case PPC::BL8_NOP:
1378  case PPC::BLA8_NOP:
1379    return 8;
1380  default:
1381    return 4; // PowerPC instructions are all 4 bytes
1382  }
1383}
1384
1385#undef DEBUG_TYPE
1386#define DEBUG_TYPE "ppc-early-ret"
1387STATISTIC(NumBCLR, "Number of early conditional returns");
1388STATISTIC(NumBLR,  "Number of early returns");
1389
1390namespace llvm {
1391  void initializePPCEarlyReturnPass(PassRegistry&);
1392}
1393
1394namespace {
1395  // PPCEarlyReturn pass - For simple functions without epilogue code, move
1396  // returns up, and create conditional returns, to avoid unnecessary
1397  // branch-to-blr sequences.
1398  struct PPCEarlyReturn : public MachineFunctionPass {
1399    static char ID;
1400    PPCEarlyReturn() : MachineFunctionPass(ID) {
1401      initializePPCEarlyReturnPass(*PassRegistry::getPassRegistry());
1402    }
1403
1404    const PPCTargetMachine *TM;
1405    const PPCInstrInfo *TII;
1406
1407protected:
1408    bool processBlock(MachineBasicBlock &ReturnMBB) {
1409      bool Changed = false;
1410
1411      MachineBasicBlock::iterator I = ReturnMBB.begin();
1412      I = ReturnMBB.SkipPHIsAndLabels(I);
1413
1414      // The block must be essentially empty except for the blr.
1415      if (I == ReturnMBB.end() || I->getOpcode() != PPC::BLR ||
1416          I != ReturnMBB.getLastNonDebugInstr())
1417        return Changed;
1418
1419      SmallVector<MachineBasicBlock*, 8> PredToRemove;
1420      for (MachineBasicBlock::pred_iterator PI = ReturnMBB.pred_begin(),
1421           PIE = ReturnMBB.pred_end(); PI != PIE; ++PI) {
1422        bool OtherReference = false, BlockChanged = false;
1423        for (MachineBasicBlock::iterator J = (*PI)->getLastNonDebugInstr();;) {
1424          if (J->getOpcode() == PPC::B) {
1425            if (J->getOperand(0).getMBB() == &ReturnMBB) {
1426              // This is an unconditional branch to the return. Replace the
1427	      // branch with a blr.
1428              BuildMI(**PI, J, J->getDebugLoc(), TII->get(PPC::BLR));
1429              MachineBasicBlock::iterator K = J--;
1430              K->eraseFromParent();
1431              BlockChanged = true;
1432              ++NumBLR;
1433              continue;
1434            }
1435          } else if (J->getOpcode() == PPC::BCC) {
1436            if (J->getOperand(2).getMBB() == &ReturnMBB) {
1437              // This is a conditional branch to the return. Replace the branch
1438              // with a bclr.
1439              BuildMI(**PI, J, J->getDebugLoc(), TII->get(PPC::BCLR))
1440                .addImm(J->getOperand(0).getImm())
1441                .addReg(J->getOperand(1).getReg());
1442              MachineBasicBlock::iterator K = J--;
1443              K->eraseFromParent();
1444              BlockChanged = true;
1445              ++NumBCLR;
1446              continue;
1447            }
1448          } else if (J->isBranch()) {
1449            if (J->isIndirectBranch()) {
1450              if (ReturnMBB.hasAddressTaken())
1451                OtherReference = true;
1452            } else
1453              for (unsigned i = 0; i < J->getNumOperands(); ++i)
1454                if (J->getOperand(i).isMBB() &&
1455                    J->getOperand(i).getMBB() == &ReturnMBB)
1456                  OtherReference = true;
1457          } else if (!J->isTerminator() && !J->isDebugValue())
1458            break;
1459
1460          if (J == (*PI)->begin())
1461            break;
1462
1463          --J;
1464        }
1465
1466        if ((*PI)->canFallThrough() && (*PI)->isLayoutSuccessor(&ReturnMBB))
1467          OtherReference = true;
1468
1469	// Predecessors are stored in a vector and can't be removed here.
1470        if (!OtherReference && BlockChanged) {
1471          PredToRemove.push_back(*PI);
1472        }
1473
1474        if (BlockChanged)
1475          Changed = true;
1476      }
1477
1478      for (unsigned i = 0, ie = PredToRemove.size(); i != ie; ++i)
1479        PredToRemove[i]->removeSuccessor(&ReturnMBB);
1480
1481      if (Changed && !ReturnMBB.hasAddressTaken()) {
1482        // We now might be able to merge this blr-only block into its
1483        // by-layout predecessor.
1484        if (ReturnMBB.pred_size() == 1 &&
1485            (*ReturnMBB.pred_begin())->isLayoutSuccessor(&ReturnMBB)) {
1486          // Move the blr into the preceding block.
1487          MachineBasicBlock &PrevMBB = **ReturnMBB.pred_begin();
1488          PrevMBB.splice(PrevMBB.end(), &ReturnMBB, I);
1489          PrevMBB.removeSuccessor(&ReturnMBB);
1490        }
1491
1492        if (ReturnMBB.pred_empty())
1493          ReturnMBB.eraseFromParent();
1494      }
1495
1496      return Changed;
1497    }
1498
1499public:
1500    virtual bool runOnMachineFunction(MachineFunction &MF) {
1501      TM = static_cast<const PPCTargetMachine *>(&MF.getTarget());
1502      TII = TM->getInstrInfo();
1503
1504      bool Changed = false;
1505
1506      // If the function does not have at least two blocks, then there is
1507      // nothing to do.
1508      if (MF.size() < 2)
1509        return Changed;
1510
1511      for (MachineFunction::iterator I = MF.begin(); I != MF.end();) {
1512        MachineBasicBlock &B = *I++;
1513        if (processBlock(B))
1514          Changed = true;
1515      }
1516
1517      return Changed;
1518    }
1519
1520    virtual void getAnalysisUsage(AnalysisUsage &AU) const {
1521      MachineFunctionPass::getAnalysisUsage(AU);
1522    }
1523  };
1524}
1525
1526INITIALIZE_PASS(PPCEarlyReturn, DEBUG_TYPE,
1527                "PowerPC Early-Return Creation", false, false)
1528
1529char PPCEarlyReturn::ID = 0;
1530FunctionPass*
1531llvm::createPPCEarlyReturnPass() { return new PPCEarlyReturn(); }
1532
1533