LLVM  6.0.0svn
PPCExpandISEL.cpp
Go to the documentation of this file.
1 //===------------- PPCExpandISEL.cpp - Expand ISEL instruction ------------===//
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 // A pass that expands the ISEL instruction into an if-then-else sequence.
11 // This pass must be run post-RA since all operands must be physical registers.
12 //
13 //===----------------------------------------------------------------------===//
14 
15 #include "PPC.h"
16 #include "PPCInstrInfo.h"
17 #include "PPCSubtarget.h"
18 #include "llvm/ADT/DenseMap.h"
19 #include "llvm/ADT/Statistic.h"
25 #include "llvm/Support/Debug.h"
27 
28 using namespace llvm;
29 
30 #define DEBUG_TYPE "ppc-expand-isel"
31 
32 STATISTIC(NumExpanded, "Number of ISEL instructions expanded");
33 STATISTIC(NumRemoved, "Number of ISEL instructions removed");
34 STATISTIC(NumFolded, "Number of ISEL instructions folded");
35 
36 // If -ppc-gen-isel=false is set, we will disable generating the ISEL
37 // instruction on all PPC targets. Otherwise, if the user set option
38 // -misel or the platform supports ISEL by default, still generate the
39 // ISEL instruction, else expand it.
40 static cl::opt<bool>
41  GenerateISEL("ppc-gen-isel",
42  cl::desc("Enable generating the ISEL instruction."),
43  cl::init(true), cl::Hidden);
44 
45 namespace {
46 class PPCExpandISEL : public MachineFunctionPass {
47  DebugLoc dl;
48  MachineFunction *MF;
49  const TargetInstrInfo *TII;
50  bool IsTrueBlockRequired;
51  bool IsFalseBlockRequired;
52  MachineBasicBlock *TrueBlock;
53  MachineBasicBlock *FalseBlock;
54  MachineBasicBlock *NewSuccessor;
55  MachineBasicBlock::iterator TrueBlockI;
56  MachineBasicBlock::iterator FalseBlockI;
57 
58  typedef SmallVector<MachineInstr *, 4> BlockISELList;
59  typedef SmallDenseMap<int, BlockISELList> ISELInstructionList;
60 
61  // A map of MBB numbers to their lists of contained ISEL instructions.
62  ISELInstructionList ISELInstructions;
63 
64  /// Initialize the object.
65  void initialize(MachineFunction &MFParam);
66 
67  void handleSpecialCases(BlockISELList &BIL, MachineBasicBlock *MBB);
68  void reorganizeBlockLayout(BlockISELList &BIL, MachineBasicBlock *MBB);
69  void populateBlocks(BlockISELList &BIL);
70  void expandMergeableISELs(BlockISELList &BIL);
71  void expandAndMergeISELs();
72 
73  bool canMerge(MachineInstr *PrevPushedMI, MachineInstr *MI);
74 
75  /// Is this instruction an ISEL or ISEL8?
76  static bool isISEL(const MachineInstr &MI) {
77  return (MI.getOpcode() == PPC::ISEL || MI.getOpcode() == PPC::ISEL8);
78  }
79 
80  /// Is this instruction an ISEL8?
81  static bool isISEL8(const MachineInstr &MI) {
82  return (MI.getOpcode() == PPC::ISEL8);
83  }
84 
85  /// Are the two operands using the same register?
86  bool useSameRegister(const MachineOperand &Op1, const MachineOperand &Op2) {
87  return (Op1.getReg() == Op2.getReg());
88  }
89 
90  ///
91  /// Collect all ISEL instructions from the current function.
92  ///
93  /// Walk the current function and collect all the ISEL instructions that are
94  /// found. The instructions are placed in the ISELInstructions vector.
95  ///
96  /// \return true if any ISEL instructions were found, false otherwise
97  ///
98  bool collectISELInstructions();
99 
100 public:
101  static char ID;
102  PPCExpandISEL() : MachineFunctionPass(ID) {
104  }
105 
106  ///
107  /// Determine whether to generate the ISEL instruction or expand it.
108  ///
109  /// Expand ISEL instruction into if-then-else sequence when one of
110  /// the following two conditions hold:
111  /// (1) -ppc-gen-isel=false
112  /// (2) hasISEL() return false
113  /// Otherwise, still generate ISEL instruction.
114  /// The -ppc-gen-isel option is set to true by default. Which means the ISEL
115  /// instruction is still generated by default on targets that support them.
116  ///
117  /// \return true if ISEL should be expanded into if-then-else code sequence;
118  /// false if ISEL instruction should be generated, i.e. not expaned.
119  ///
120  static bool isExpandISELEnabled(const MachineFunction &MF);
121 
122 #ifndef NDEBUG
123  void DumpISELInstructions() const;
124 #endif
125 
126  bool runOnMachineFunction(MachineFunction &MF) override {
127  if (!isExpandISELEnabled(MF))
128  return false;
129 
130  DEBUG(dbgs() << "Function: "; MF.dump(); dbgs() << "\n");
131  initialize(MF);
132 
133  if (!collectISELInstructions()) {
134  DEBUG(dbgs() << "No ISEL instructions in this function\n");
135  return false;
136  }
137 
138 #ifndef NDEBUG
139  DumpISELInstructions();
140 #endif
141 
142  expandAndMergeISELs();
143 
144  return true;
145  }
146 };
147 } // end anonymous namespace
148 
150  MF = &MFParam;
151  TII = MF->getSubtarget().getInstrInfo();
152  ISELInstructions.clear();
153 }
154 
155 bool PPCExpandISEL::isExpandISELEnabled(const MachineFunction &MF) {
156  return !GenerateISEL || !MF.getSubtarget<PPCSubtarget>().hasISEL();
157 }
158 
159 bool PPCExpandISEL::collectISELInstructions() {
160  for (MachineBasicBlock &MBB : *MF) {
161  BlockISELList thisBlockISELs;
162  for (MachineInstr &MI : MBB)
163  if (isISEL(MI))
164  thisBlockISELs.push_back(&MI);
165  if (!thisBlockISELs.empty())
166  ISELInstructions.insert(std::make_pair(MBB.getNumber(), thisBlockISELs));
167  }
168  return !ISELInstructions.empty();
169 }
170 
171 #ifndef NDEBUG
172 void PPCExpandISEL::DumpISELInstructions() const {
173  for (const auto &I : ISELInstructions) {
174  DEBUG(dbgs() << "BB#" << I.first << ":\n");
175  for (const auto &VI : I.second)
176  DEBUG(dbgs() << " "; VI->print(dbgs()));
177  }
178 }
179 #endif
180 
181 /// Contiguous ISELs that have the same condition can be merged.
182 bool PPCExpandISEL::canMerge(MachineInstr *PrevPushedMI, MachineInstr *MI) {
183  // Same Condition Register?
184  if (!useSameRegister(PrevPushedMI->getOperand(3), MI->getOperand(3)))
185  return false;
186 
187  MachineBasicBlock::iterator PrevPushedMBBI = *PrevPushedMI;
189  return (std::prev(MBBI) == PrevPushedMBBI); // Contiguous ISELs?
190 }
191 
192 void PPCExpandISEL::expandAndMergeISELs() {
193  for (auto &BlockList : ISELInstructions) {
194  DEBUG(dbgs() << "Expanding ISEL instructions in BB#" << BlockList.first
195  << "\n");
196 
197  BlockISELList &CurrentISELList = BlockList.second;
198  auto I = CurrentISELList.begin();
199  auto E = CurrentISELList.end();
200 
201  while (I != E) {
202  BlockISELList SubISELList;
203 
204  SubISELList.push_back(*I++);
205 
206  // Collect the ISELs that can be merged together.
207  while (I != E && canMerge(SubISELList.back(), *I))
208  SubISELList.push_back(*I++);
209 
210  expandMergeableISELs(SubISELList);
211  }
212  }
213 }
214 
215 void PPCExpandISEL::handleSpecialCases(BlockISELList &BIL,
216  MachineBasicBlock *MBB) {
217  IsTrueBlockRequired = false;
218  IsFalseBlockRequired = false;
219 
220  auto MI = BIL.begin();
221  while (MI != BIL.end()) {
222  assert(isISEL(**MI) && "Expecting an ISEL instruction");
223  DEBUG(dbgs() << "ISEL: " << **MI << "\n");
224 
225  MachineOperand &Dest = (*MI)->getOperand(0);
226  MachineOperand &TrueValue = (*MI)->getOperand(1);
227  MachineOperand &FalseValue = (*MI)->getOperand(2);
228 
229  // If at least one of the ISEL instructions satisfy the following
230  // condition, we need the True Block:
231  // The Dest Register and True Value Register are not the same
232  // Similarly, if at least one of the ISEL instructions satisfy the
233  // following condition, we need the False Block:
234  // The Dest Register and False Value Register are not the same.
235 
236  bool IsADDIInstRequired = !useSameRegister(Dest, TrueValue);
237  bool IsORIInstRequired = !useSameRegister(Dest, FalseValue);
238 
239  // Special case 1, all registers used by ISEL are the same one.
240  if (!IsADDIInstRequired && !IsORIInstRequired) {
241  DEBUG(dbgs() << "Remove redudant ISEL instruction.");
242  NumRemoved++;
243  (*MI)->eraseFromParent();
244  // Setting MI to the erase result keeps the iterator valid and increased.
245  MI = BIL.erase(MI);
246  continue;
247  }
248 
249  // Special case 2, the two input registers used by ISEL are the same.
250  // Note 1: We favor merging ISEL expansions over folding a single one. If
251  // the passed list has multiple merge-able ISEL's, we won't fold any.
252  // Note 2: There is no need to test for PPC::R0/PPC::X0 because PPC::ZERO/
253  // PPC::ZERO8 will be used for the first operand if the value is meant to
254  // be zero. In this case, the useSameRegister method will return false,
255  // thereby preventing this ISEL from being folded.
256 
257  if (useSameRegister(TrueValue, FalseValue) && (BIL.size() == 1)) {
258  DEBUG(dbgs() << "Fold the ISEL instruction to an unconditonal copy.");
259  NumFolded++;
260  BuildMI(*MBB, (*MI), dl, TII->get(isISEL8(**MI) ? PPC::ADDI8 : PPC::ADDI))
261  .add(Dest)
262  .add(TrueValue)
263  .add(MachineOperand::CreateImm(0));
264  (*MI)->eraseFromParent();
265  // Setting MI to the erase result keeps the iterator valid and increased.
266  MI = BIL.erase(MI);
267  continue;
268  }
269 
270  IsTrueBlockRequired |= IsADDIInstRequired;
271  IsFalseBlockRequired |= IsORIInstRequired;
272  MI++;
273  }
274 }
275 
276 void PPCExpandISEL::reorganizeBlockLayout(BlockISELList &BIL,
277  MachineBasicBlock *MBB) {
278  if (BIL.empty())
279  return;
280 
281  assert((IsTrueBlockRequired || IsFalseBlockRequired) &&
282  "Should have been handled by special cases earlier!");
283 
284  MachineBasicBlock *Successor = nullptr;
285  const BasicBlock *LLVM_BB = MBB->getBasicBlock();
286  MachineBasicBlock::iterator MBBI = (*BIL.back());
287  NewSuccessor = (MBBI != MBB->getLastNonDebugInstr() || !MBB->canFallThrough())
288  // Another BB is needed to move the instructions that
289  // follow this ISEL. If the ISEL is the last instruction
290  // in a block that can't fall through, we also need a block
291  // to branch to.
292  ? MF->CreateMachineBasicBlock(LLVM_BB)
293  : nullptr;
294 
296  ++It; // Point to the successor block of MBB.
297 
298  // If NewSuccessor is NULL then the last ISEL in this group is the last
299  // non-debug instruction in this block. Find the fall-through successor
300  // of this block to use when updating the CFG below.
301  if (!NewSuccessor) {
302  for (auto &Succ : MBB->successors()) {
303  if (MBB->isLayoutSuccessor(Succ)) {
304  Successor = Succ;
305  break;
306  }
307  }
308  } else
309  Successor = NewSuccessor;
310 
311  // The FalseBlock and TrueBlock are inserted after the MBB block but before
312  // its successor.
313  // Note this need to be done *after* the above setting the Successor code.
314  if (IsFalseBlockRequired) {
315  FalseBlock = MF->CreateMachineBasicBlock(LLVM_BB);
316  MF->insert(It, FalseBlock);
317  }
318 
319  if (IsTrueBlockRequired) {
320  TrueBlock = MF->CreateMachineBasicBlock(LLVM_BB);
321  MF->insert(It, TrueBlock);
322  }
323 
324  if (NewSuccessor) {
325  MF->insert(It, NewSuccessor);
326 
327  // Transfer the rest of this block into the new successor block.
328  NewSuccessor->splice(NewSuccessor->end(), MBB,
329  std::next(MachineBasicBlock::iterator(BIL.back())),
330  MBB->end());
331  NewSuccessor->transferSuccessorsAndUpdatePHIs(MBB);
332 
333  // Copy the original liveIns of MBB to NewSuccessor.
334  for (auto &LI : MBB->liveins())
335  NewSuccessor->addLiveIn(LI);
336 
337  // After splitting the NewSuccessor block, Regs defined but not killed
338  // in MBB should be treated as liveins of NewSuccessor.
339  // Note: Cannot use stepBackward instead since we are using the Reg
340  // liveness state at the end of MBB (liveOut of MBB) as the liveIn for
341  // NewSuccessor. Otherwise, will cause cyclic dependence.
342  LivePhysRegs LPR(*MF->getSubtarget<PPCSubtarget>().getRegisterInfo());
344  for (MachineInstr &MI : *MBB)
345  LPR.stepForward(MI, Clobbers);
346  for (auto &LI : LPR)
347  NewSuccessor->addLiveIn(LI);
348  } else {
349  // Remove successor from MBB.
350  MBB->removeSuccessor(Successor);
351  }
352 
353  // Note that this needs to be done *after* transfering the successors from MBB
354  // to the NewSuccessor block, otherwise these blocks will also be transferred
355  // as successors!
356  MBB->addSuccessor(IsTrueBlockRequired ? TrueBlock : Successor);
357  MBB->addSuccessor(IsFalseBlockRequired ? FalseBlock : Successor);
358 
359  if (IsTrueBlockRequired) {
360  TrueBlockI = TrueBlock->begin();
361  TrueBlock->addSuccessor(Successor);
362  }
363 
364  if (IsFalseBlockRequired) {
365  FalseBlockI = FalseBlock->begin();
366  FalseBlock->addSuccessor(Successor);
367  }
368 
369  // Conditional branch to the TrueBlock or Successor
370  BuildMI(*MBB, BIL.back(), dl, TII->get(PPC::BC))
371  .add(BIL.back()->getOperand(3))
372  .addMBB(IsTrueBlockRequired ? TrueBlock : Successor);
373 
374  // Jump over the true block to the new successor if the condition is false.
375  BuildMI(*(IsFalseBlockRequired ? FalseBlock : MBB),
376  (IsFalseBlockRequired ? FalseBlockI : BIL.back()), dl,
377  TII->get(PPC::B))
378  .addMBB(Successor);
379 
380  if (IsFalseBlockRequired)
381  FalseBlockI = FalseBlock->begin(); // get the position of PPC::B
382 }
383 
384 void PPCExpandISEL::populateBlocks(BlockISELList &BIL) {
385  for (auto &MI : BIL) {
386  assert(isISEL(*MI) && "Expecting an ISEL instruction");
387 
388  MachineOperand &Dest = MI->getOperand(0); // location to store to
389  MachineOperand &TrueValue = MI->getOperand(1); // Value to store if
390  // condition is true
391  MachineOperand &FalseValue = MI->getOperand(2); // Value to store if
392  // condition is false
393  MachineOperand &ConditionRegister = MI->getOperand(3); // Condition
394 
395  DEBUG(dbgs() << "Dest: " << Dest << "\n");
396  DEBUG(dbgs() << "TrueValue: " << TrueValue << "\n");
397  DEBUG(dbgs() << "FalseValue: " << FalseValue << "\n");
398  DEBUG(dbgs() << "ConditionRegister: " << ConditionRegister << "\n");
399 
400 
401  // If the Dest Register and True Value Register are not the same one, we
402  // need the True Block.
403  bool IsADDIInstRequired = !useSameRegister(Dest, TrueValue);
404  bool IsORIInstRequired = !useSameRegister(Dest, FalseValue);
405 
406  if (IsADDIInstRequired) {
407  // Copy the result into the destination if the condition is true.
408  BuildMI(*TrueBlock, TrueBlockI, dl,
409  TII->get(isISEL8(*MI) ? PPC::ADDI8 : PPC::ADDI))
410  .add(Dest)
411  .add(TrueValue)
412  .add(MachineOperand::CreateImm(0));
413 
414  // Add the LiveIn registers required by true block.
415  TrueBlock->addLiveIn(TrueValue.getReg());
416  }
417 
418  if (IsORIInstRequired) {
419  // Add the LiveIn registers required by false block.
420  FalseBlock->addLiveIn(FalseValue.getReg());
421  }
422 
423  if (NewSuccessor) {
424  // Add the LiveIn registers required by NewSuccessor block.
425  NewSuccessor->addLiveIn(Dest.getReg());
426  NewSuccessor->addLiveIn(TrueValue.getReg());
427  NewSuccessor->addLiveIn(FalseValue.getReg());
428  NewSuccessor->addLiveIn(ConditionRegister.getReg());
429  }
430 
431  // Copy the value into the destination if the condition is false.
432  if (IsORIInstRequired)
433  BuildMI(*FalseBlock, FalseBlockI, dl,
434  TII->get(isISEL8(*MI) ? PPC::ORI8 : PPC::ORI))
435  .add(Dest)
436  .add(FalseValue)
437  .add(MachineOperand::CreateImm(0));
438 
439  MI->eraseFromParent(); // Remove the ISEL instruction.
440 
441  NumExpanded++;
442  }
443 }
444 
445 void PPCExpandISEL::expandMergeableISELs(BlockISELList &BIL) {
446  // At this stage all the ISELs of BIL are in the same MBB.
447  MachineBasicBlock *MBB = BIL.back()->getParent();
448 
449  handleSpecialCases(BIL, MBB);
450  reorganizeBlockLayout(BIL, MBB);
451  populateBlocks(BIL);
452 }
453 
454 INITIALIZE_PASS(PPCExpandISEL, DEBUG_TYPE, "PowerPC Expand ISEL Generation",
455  false, false)
456 char PPCExpandISEL::ID = 0;
457 
458 FunctionPass *llvm::createPPCExpandISELPass() { return new PPCExpandISEL(); }
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
unsigned getReg() const
getReg - Returns the register number.
void transferSuccessorsAndUpdatePHIs(MachineBasicBlock *FromMBB)
Transfers all the successors, as in transferSuccessors, and update PHI operands in the successor bloc...
STATISTIC(NumFunctions, "Total number of functions")
A debug info location.
Definition: DebugLoc.h:34
void dump() const
dump - Print the current MachineFunction to cerr, useful for debugger use.
iterator_range< succ_iterator > successors()
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
const HexagonInstrInfo * TII
void eraseFromParent()
Unlink &#39;this&#39; from the containing basic block and delete it.
unsigned getOpcode() const
Returns the opcode of this MachineInstr.
Definition: MachineInstr.h:290
bool canFallThrough()
Return true if the block can implicitly transfer control to the block after it by falling off the end...
iterator getLastNonDebugInstr()
Returns an iterator to the last non-debug instruction in the basic block, or end().
virtual const TargetInstrInfo * getInstrInfo() const
instr_iterator insert(instr_iterator I, MachineInstr *M)
Insert MI into the instruction list before I, possibly inside a bundle.
TargetInstrInfo - Interface to description of machine instruction set.
MachineInstrBuilder BuildMI(MachineFunction &MF, const DebugLoc &DL, const MCInstrDesc &MCID)
Builder interface. Specify how to create the initial instruction itself.
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:406
void addLiveIn(MCPhysReg PhysReg, LaneBitmask LaneMask=LaneBitmask::getAll())
Adds the specified register as a live in.
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
LLVM Basic Block Representation.
Definition: BasicBlock.h:59
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:285
self_iterator getIterator()
Definition: ilist_node.h:82
This file implements the LivePhysRegs utility for tracking liveness of physical registers.
#define INITIALIZE_PASS(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:34
const PPCRegisterInfo * getRegisterInfo() const override
Definition: PPCSubtarget.h:186
Iterator for intrusive lists based on ilist_node.
void initializePPCExpandISELPass(PassRegistry &)
void addSuccessor(MachineBasicBlock *Succ, BranchProbability Prob=BranchProbability::getUnknown())
Add Succ as a successor of this MachineBasicBlock.
MachineOperand class - Representation of each machine instruction operand.
bool isLayoutSuccessor(const MachineBasicBlock *MBB) const
Return true if the specified MBB will be emitted immediately after this block, such that if this bloc...
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
static void initialize(TargetLibraryInfoImpl &TLI, const Triple &T, ArrayRef< StringRef > StandardNames)
initialize - Initialize the set of available library functions based on the specified target triple...
#define DEBUG_TYPE
const MachineBasicBlock * getParent() const
Definition: MachineInstr.h:139
Representation of each machine instruction.
Definition: MachineInstr.h:59
void splice(iterator Where, MachineBasicBlock *Other, iterator From)
Take an instruction from MBB &#39;Other&#39; at the position From, and insert it into this MBB right before &#39;...
A set of physical registers with utility functions to track liveness when walking backward/forward th...
Definition: LivePhysRegs.h:49
const MCInstrDesc & get(unsigned Opcode) const
Return the machine instruction descriptor that corresponds to the specified instruction opcode...
Definition: MCInstrInfo.h:45
static MachineOperand CreateImm(int64_t Val)
#define I(x, y, z)
Definition: MD5.cpp:58
const BasicBlock * getBasicBlock() const
Return the LLVM basic block that this instance corresponded to originally.
iterator_range< livein_iterator > liveins() const
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
static cl::opt< bool > GenerateISEL("ppc-gen-isel", cl::desc("Enable generating the ISEL instruction."), cl::init(true), cl::Hidden)
#define DEBUG(X)
Definition: Debug.h:118
IRTranslator LLVM IR MI
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:295
FunctionPass * createPPCExpandISELPass()