LLVM  10.0.0svn
AMDILCFGStructurizer.cpp
Go to the documentation of this file.
1 //===- AMDILCFGStructurizer.cpp - CFG Structurizer ------------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //==-----------------------------------------------------------------------===//
8 
9 #include "AMDGPU.h"
10 #include "AMDGPUSubtarget.h"
11 #include "R600InstrInfo.h"
12 #include "R600RegisterInfo.h"
15 #include "llvm/ADT/SCCIterator.h"
16 #include "llvm/ADT/SmallPtrSet.h"
17 #include "llvm/ADT/SmallVector.h"
18 #include "llvm/ADT/Statistic.h"
19 #include "llvm/ADT/StringRef.h"
31 #include "llvm/IR/DebugLoc.h"
32 #include "llvm/IR/LLVMContext.h"
33 #include "llvm/Pass.h"
34 #include "llvm/Support/Debug.h"
38 #include <cassert>
39 #include <cstddef>
40 #include <deque>
41 #include <iterator>
42 #include <map>
43 #include <utility>
44 #include <vector>
45 
46 using namespace llvm;
47 
48 #define DEBUG_TYPE "structcfg"
49 
50 #define DEFAULT_VEC_SLOTS 8
51 
52 // TODO: move-begin.
53 
54 //===----------------------------------------------------------------------===//
55 //
56 // Statistics for CFGStructurizer.
57 //
58 //===----------------------------------------------------------------------===//
59 
60 STATISTIC(numSerialPatternMatch, "CFGStructurizer number of serial pattern "
61  "matched");
62 STATISTIC(numIfPatternMatch, "CFGStructurizer number of if pattern "
63  "matched");
64 STATISTIC(numClonedBlock, "CFGStructurizer cloned blocks");
65 STATISTIC(numClonedInstr, "CFGStructurizer cloned instructions");
66 
67 namespace llvm {
68 
70 
71 } // end namespace llvm
72 
73 namespace {
74 
75 //===----------------------------------------------------------------------===//
76 //
77 // Miscellaneous utility for CFGStructurizer.
78 //
79 //===----------------------------------------------------------------------===//
80 
81 #define SHOWNEWINSTR(i) LLVM_DEBUG(dbgs() << "New instr: " << *i << "\n");
82 
83 #define SHOWNEWBLK(b, msg) \
84  LLVM_DEBUG(dbgs() << msg << "BB" << b->getNumber() << "size " << b->size(); \
85  dbgs() << "\n";);
86 
87 #define SHOWBLK_DETAIL(b, msg) \
88  LLVM_DEBUG(if (b) { \
89  dbgs() << msg << "BB" << b->getNumber() << "size " << b->size(); \
90  b->print(dbgs()); \
91  dbgs() << "\n"; \
92  });
93 
94 #define INVALIDSCCNUM -1
95 
96 //===----------------------------------------------------------------------===//
97 //
98 // supporting data structure for CFGStructurizer
99 //
100 //===----------------------------------------------------------------------===//
101 
102 class BlockInformation {
103 public:
104  bool IsRetired = false;
105  int SccNum = INVALIDSCCNUM;
106 
107  BlockInformation() = default;
108 };
109 
110 //===----------------------------------------------------------------------===//
111 //
112 // CFGStructurizer
113 //
114 //===----------------------------------------------------------------------===//
115 
116 class AMDGPUCFGStructurizer : public MachineFunctionPass {
117 public:
119  using MBBInfoMap = std::map<MachineBasicBlock *, BlockInformation *>;
120  using LoopLandInfoMap = std::map<MachineLoop *, MachineBasicBlock *>;
121 
122  enum PathToKind {
123  Not_SinglePath = 0,
124  SinglePath_InPath = 1,
125  SinglePath_NotInPath = 2
126  };
127 
128  static char ID;
129 
130  AMDGPUCFGStructurizer() : MachineFunctionPass(ID) {
132  }
133 
134  StringRef getPassName() const override {
135  return "AMDGPU Control Flow Graph structurizer Pass";
136  }
137 
138  void getAnalysisUsage(AnalysisUsage &AU) const override {
143  }
144 
145  /// Perform the CFG structurization
146  bool run();
147 
148  /// Perform the CFG preparation
149  /// This step will remove every unconditionnal/dead jump instructions and make
150  /// sure all loops have an exit block
151  bool prepare();
152 
153  bool runOnMachineFunction(MachineFunction &MF) override {
154  TII = MF.getSubtarget<R600Subtarget>().getInstrInfo();
155  TRI = &TII->getRegisterInfo();
156  LLVM_DEBUG(MF.dump(););
157  OrderedBlks.clear();
158  Visited.clear();
159  FuncRep = &MF;
160  MLI = &getAnalysis<MachineLoopInfo>();
161  LLVM_DEBUG(dbgs() << "LoopInfo:\n"; PrintLoopinfo(*MLI););
162  MDT = &getAnalysis<MachineDominatorTree>();
163  LLVM_DEBUG(MDT->print(dbgs(), (const Module *)nullptr););
164  PDT = &getAnalysis<MachinePostDominatorTree>();
165  LLVM_DEBUG(PDT->print(dbgs()););
166  prepare();
167  run();
168  LLVM_DEBUG(MF.dump(););
169  return true;
170  }
171 
172 protected:
175  MachineLoopInfo *MLI;
176  const R600InstrInfo *TII = nullptr;
177  const R600RegisterInfo *TRI = nullptr;
178 
179  // PRINT FUNCTIONS
180  /// Print the ordered Blocks.
181  void printOrderedBlocks() const {
182  size_t i = 0;
183  for (MBBVector::const_iterator iterBlk = OrderedBlks.begin(),
184  iterBlkEnd = OrderedBlks.end(); iterBlk != iterBlkEnd; ++iterBlk, ++i) {
185  dbgs() << "BB" << (*iterBlk)->getNumber();
186  dbgs() << "(" << getSCCNum(*iterBlk) << "," << (*iterBlk)->size() << ")";
187  if (i != 0 && i % 10 == 0) {
188  dbgs() << "\n";
189  } else {
190  dbgs() << " ";
191  }
192  }
193  }
194 
195  static void PrintLoopinfo(const MachineLoopInfo &LoopInfo) {
196  for (MachineLoop::iterator iter = LoopInfo.begin(),
197  iterEnd = LoopInfo.end(); iter != iterEnd; ++iter) {
198  (*iter)->print(dbgs(), 0);
199  }
200  }
201 
202  // UTILITY FUNCTIONS
203  int getSCCNum(MachineBasicBlock *MBB) const;
204  MachineBasicBlock *getLoopLandInfo(MachineLoop *LoopRep) const;
205  bool hasBackEdge(MachineBasicBlock *MBB) const;
206  bool isRetiredBlock(MachineBasicBlock *MBB) const;
207  bool isActiveLoophead(MachineBasicBlock *MBB) const;
208  PathToKind singlePathTo(MachineBasicBlock *SrcMBB, MachineBasicBlock *DstMBB,
209  bool AllowSideEntry = true) const;
210  int countActiveBlock(MBBVector::const_iterator It,
212  bool needMigrateBlock(MachineBasicBlock *MBB) const;
213 
214  // Utility Functions
215  void reversePredicateSetter(MachineBasicBlock::iterator I,
216  MachineBasicBlock &MBB);
217  /// Compute the reversed DFS post order of Blocks
218  void orderBlocks(MachineFunction *MF);
219 
220  // Function originally from CFGStructTraits
221  void insertInstrEnd(MachineBasicBlock *MBB, int NewOpcode,
222  const DebugLoc &DL = DebugLoc());
223  MachineInstr *insertInstrBefore(MachineBasicBlock *MBB, int NewOpcode,
224  const DebugLoc &DL = DebugLoc());
225  MachineInstr *insertInstrBefore(MachineBasicBlock::iterator I, int NewOpcode);
226  void insertCondBranchBefore(MachineBasicBlock::iterator I, int NewOpcode,
227  const DebugLoc &DL);
228  void insertCondBranchBefore(MachineBasicBlock *MBB,
229  MachineBasicBlock::iterator I, int NewOpcode,
230  int RegNum, const DebugLoc &DL);
231 
232  static int getBranchNzeroOpcode(int OldOpcode);
233  static int getBranchZeroOpcode(int OldOpcode);
234  static int getContinueNzeroOpcode(int OldOpcode);
235  static int getContinueZeroOpcode(int OldOpcode);
236  static MachineBasicBlock *getTrueBranch(MachineInstr *MI);
237  static void setTrueBranch(MachineInstr *MI, MachineBasicBlock *MBB);
238  static MachineBasicBlock *getFalseBranch(MachineBasicBlock *MBB,
239  MachineInstr *MI);
240  static bool isCondBranch(MachineInstr *MI);
241  static bool isUncondBranch(MachineInstr *MI);
242  static DebugLoc getLastDebugLocInBB(MachineBasicBlock *MBB);
243  static MachineInstr *getNormalBlockBranchInstr(MachineBasicBlock *MBB);
244 
245  /// The correct naming for this is getPossibleLoopendBlockBranchInstr.
246  ///
247  /// BB with backward-edge could have move instructions after the branch
248  /// instruction. Such move instruction "belong to" the loop backward-edge.
249  MachineInstr *getLoopendBlockBranchInstr(MachineBasicBlock *MBB);
250 
251  static MachineInstr *getReturnInstr(MachineBasicBlock *MBB);
252  static bool isReturnBlock(MachineBasicBlock *MBB);
253  static void cloneSuccessorList(MachineBasicBlock *DstMBB,
254  MachineBasicBlock *SrcMBB);
255  static MachineBasicBlock *clone(MachineBasicBlock *MBB);
256 
257  /// MachineBasicBlock::ReplaceUsesOfBlockWith doesn't serve the purpose
258  /// because the AMDGPU instruction is not recognized as terminator fix this
259  /// and retire this routine
260  void replaceInstrUseOfBlockWith(MachineBasicBlock *SrcMBB,
261  MachineBasicBlock *OldMBB, MachineBasicBlock *NewBlk);
262 
263  static void wrapup(MachineBasicBlock *MBB);
264 
265  int patternMatch(MachineBasicBlock *MBB);
266  int patternMatchGroup(MachineBasicBlock *MBB);
267  int serialPatternMatch(MachineBasicBlock *MBB);
268  int ifPatternMatch(MachineBasicBlock *MBB);
269  int loopendPatternMatch();
270  int mergeLoop(MachineLoop *LoopRep);
271 
272  /// return true iff src1Blk->succ_size() == 0 && src1Blk and src2Blk are in
273  /// the same loop with LoopLandInfo without explicitly keeping track of
274  /// loopContBlks and loopBreakBlks, this is a method to get the information.
275  bool isSameloopDetachedContbreak(MachineBasicBlock *Src1MBB,
276  MachineBasicBlock *Src2MBB);
277  int handleJumpintoIf(MachineBasicBlock *HeadMBB,
278  MachineBasicBlock *TrueMBB, MachineBasicBlock *FalseMBB);
279  int handleJumpintoIfImp(MachineBasicBlock *HeadMBB,
280  MachineBasicBlock *TrueMBB, MachineBasicBlock *FalseMBB);
281  int improveSimpleJumpintoIf(MachineBasicBlock *HeadMBB,
282  MachineBasicBlock *TrueMBB, MachineBasicBlock *FalseMBB,
283  MachineBasicBlock **LandMBBPtr);
284  void showImproveSimpleJumpintoIf(MachineBasicBlock *HeadMBB,
285  MachineBasicBlock *TrueMBB, MachineBasicBlock *FalseMBB,
286  MachineBasicBlock *LandMBB, bool Detail = false);
287  int cloneOnSideEntryTo(MachineBasicBlock *PreMBB,
288  MachineBasicBlock *SrcMBB, MachineBasicBlock *DstMBB);
289  void mergeSerialBlock(MachineBasicBlock *DstMBB,
290  MachineBasicBlock *SrcMBB);
291 
292  void mergeIfthenelseBlock(MachineInstr *BranchMI,
293  MachineBasicBlock *MBB, MachineBasicBlock *TrueMBB,
294  MachineBasicBlock *FalseMBB, MachineBasicBlock *LandMBB);
295  void mergeLooplandBlock(MachineBasicBlock *DstMBB,
296  MachineBasicBlock *LandMBB);
297  void mergeLoopbreakBlock(MachineBasicBlock *ExitingMBB,
298  MachineBasicBlock *LandMBB);
299  void settleLoopcontBlock(MachineBasicBlock *ContingMBB,
300  MachineBasicBlock *ContMBB);
301 
302  /// normalizeInfiniteLoopExit change
303  /// B1:
304  /// uncond_br LoopHeader
305  ///
306  /// to
307  /// B1:
308  /// cond_br 1 LoopHeader dummyExit
309  /// and return the newly added dummy exit block
310  MachineBasicBlock *normalizeInfiniteLoopExit(MachineLoop *LoopRep);
311  void removeUnconditionalBranch(MachineBasicBlock *MBB);
312 
313  /// Remove duplicate branches instructions in a block.
314  /// For instance
315  /// B0:
316  /// cond_br X B1 B2
317  /// cond_br X B1 B2
318  /// is transformed to
319  /// B0:
320  /// cond_br X B1 B2
321  void removeRedundantConditionalBranch(MachineBasicBlock *MBB);
322 
323  void addDummyExitBlock(SmallVectorImpl<MachineBasicBlock *> &RetMBB);
324  void removeSuccessor(MachineBasicBlock *MBB);
325  MachineBasicBlock *cloneBlockForPredecessor(MachineBasicBlock *MBB,
326  MachineBasicBlock *PredMBB);
327  void migrateInstruction(MachineBasicBlock *SrcMBB,
329  void recordSccnum(MachineBasicBlock *MBB, int SCCNum);
330  void retireBlock(MachineBasicBlock *MBB);
331 
332 private:
333  MBBInfoMap BlockInfoMap;
334  LoopLandInfoMap LLInfoMap;
335  std::map<MachineLoop *, bool> Visited;
336  MachineFunction *FuncRep;
338 };
339 
340 } // end anonymous namespace
341 
343 
345  MBBInfoMap::const_iterator It = BlockInfoMap.find(MBB);
346  if (It == BlockInfoMap.end())
347  return INVALIDSCCNUM;
348  return (*It).second->SccNum;
349 }
350 
351 MachineBasicBlock *AMDGPUCFGStructurizer::getLoopLandInfo(MachineLoop *LoopRep)
352  const {
353  LoopLandInfoMap::const_iterator It = LLInfoMap.find(LoopRep);
354  if (It == LLInfoMap.end())
355  return nullptr;
356  return (*It).second;
357 }
358 
359 bool AMDGPUCFGStructurizer::hasBackEdge(MachineBasicBlock *MBB) const {
360  MachineLoop *LoopRep = MLI->getLoopFor(MBB);
361  if (!LoopRep)
362  return false;
363  MachineBasicBlock *LoopHeader = LoopRep->getHeader();
364  return MBB->isSuccessor(LoopHeader);
365 }
366 
367 bool AMDGPUCFGStructurizer::isRetiredBlock(MachineBasicBlock *MBB) const {
368  MBBInfoMap::const_iterator It = BlockInfoMap.find(MBB);
369  if (It == BlockInfoMap.end())
370  return false;
371  return (*It).second->IsRetired;
372 }
373 
374 bool AMDGPUCFGStructurizer::isActiveLoophead(MachineBasicBlock *MBB) const {
375  MachineLoop *LoopRep = MLI->getLoopFor(MBB);
376  while (LoopRep && LoopRep->getHeader() == MBB) {
377  MachineBasicBlock *LoopLand = getLoopLandInfo(LoopRep);
378  if(!LoopLand)
379  return true;
380  if (!isRetiredBlock(LoopLand))
381  return true;
382  LoopRep = LoopRep->getParentLoop();
383  }
384  return false;
385 }
386 
387 AMDGPUCFGStructurizer::PathToKind AMDGPUCFGStructurizer::singlePathTo(
388  MachineBasicBlock *SrcMBB, MachineBasicBlock *DstMBB,
389  bool AllowSideEntry) const {
390  assert(DstMBB);
391  if (SrcMBB == DstMBB)
392  return SinglePath_InPath;
393  while (SrcMBB && SrcMBB->succ_size() == 1) {
394  SrcMBB = *SrcMBB->succ_begin();
395  if (SrcMBB == DstMBB)
396  return SinglePath_InPath;
397  if (!AllowSideEntry && SrcMBB->pred_size() > 1)
398  return Not_SinglePath;
399  }
400  if (SrcMBB && SrcMBB->succ_size()==0)
401  return SinglePath_NotInPath;
402  return Not_SinglePath;
403 }
404 
405 int AMDGPUCFGStructurizer::countActiveBlock(MBBVector::const_iterator It,
407  int Count = 0;
408  while (It != E) {
409  if (!isRetiredBlock(*It))
410  ++Count;
411  ++It;
412  }
413  return Count;
414 }
415 
416 bool AMDGPUCFGStructurizer::needMigrateBlock(MachineBasicBlock *MBB) const {
417  unsigned BlockSizeThreshold = 30;
418  unsigned CloneInstrThreshold = 100;
419  bool MultiplePreds = MBB && (MBB->pred_size() > 1);
420 
421  if(!MultiplePreds)
422  return false;
423  unsigned BlkSize = MBB->size();
424  return ((BlkSize > BlockSizeThreshold) &&
425  (BlkSize * (MBB->pred_size() - 1) > CloneInstrThreshold));
426 }
427 
428 void AMDGPUCFGStructurizer::reversePredicateSetter(
430  assert(I.isValid() && "Expected valid iterator");
431  for (;; --I) {
432  if (I == MBB.end())
433  continue;
434  if (I->getOpcode() == R600::PRED_X) {
435  switch (I->getOperand(2).getImm()) {
436  case R600::PRED_SETE_INT:
437  I->getOperand(2).setImm(R600::PRED_SETNE_INT);
438  return;
439  case R600::PRED_SETNE_INT:
440  I->getOperand(2).setImm(R600::PRED_SETE_INT);
441  return;
442  case R600::PRED_SETE:
443  I->getOperand(2).setImm(R600::PRED_SETNE);
444  return;
445  case R600::PRED_SETNE:
446  I->getOperand(2).setImm(R600::PRED_SETE);
447  return;
448  default:
449  llvm_unreachable("PRED_X Opcode invalid!");
450  }
451  }
452  }
453 }
454 
455 void AMDGPUCFGStructurizer::insertInstrEnd(MachineBasicBlock *MBB,
456  int NewOpcode, const DebugLoc &DL) {
457  MachineInstr *MI =
458  MBB->getParent()->CreateMachineInstr(TII->get(NewOpcode), DL);
459  MBB->push_back(MI);
460  //assume the instruction doesn't take any reg operand ...
461  SHOWNEWINSTR(MI);
462 }
463 
464 MachineInstr *AMDGPUCFGStructurizer::insertInstrBefore(MachineBasicBlock *MBB,
465  int NewOpcode,
466  const DebugLoc &DL) {
467  MachineInstr *MI =
468  MBB->getParent()->CreateMachineInstr(TII->get(NewOpcode), DL);
469  if (MBB->begin() != MBB->end())
470  MBB->insert(MBB->begin(), MI);
471  else
472  MBB->push_back(MI);
473  SHOWNEWINSTR(MI);
474  return MI;
475 }
476 
477 MachineInstr *AMDGPUCFGStructurizer::insertInstrBefore(
478  MachineBasicBlock::iterator I, int NewOpcode) {
479  MachineInstr *OldMI = &(*I);
480  MachineBasicBlock *MBB = OldMI->getParent();
481  MachineInstr *NewMBB =
482  MBB->getParent()->CreateMachineInstr(TII->get(NewOpcode), DebugLoc());
483  MBB->insert(I, NewMBB);
484  //assume the instruction doesn't take any reg operand ...
485  SHOWNEWINSTR(NewMBB);
486  return NewMBB;
487 }
488 
489 void AMDGPUCFGStructurizer::insertCondBranchBefore(
490  MachineBasicBlock::iterator I, int NewOpcode, const DebugLoc &DL) {
491  MachineInstr *OldMI = &(*I);
492  MachineBasicBlock *MBB = OldMI->getParent();
493  MachineFunction *MF = MBB->getParent();
494  MachineInstr *NewMI = MF->CreateMachineInstr(TII->get(NewOpcode), DL);
495  MBB->insert(I, NewMI);
496  MachineInstrBuilder MIB(*MF, NewMI);
497  MIB.addReg(OldMI->getOperand(1).getReg(), false);
498  SHOWNEWINSTR(NewMI);
499  //erase later oldInstr->eraseFromParent();
500 }
501 
502 void AMDGPUCFGStructurizer::insertCondBranchBefore(
504  int RegNum, const DebugLoc &DL) {
505  MachineFunction *MF = blk->getParent();
506  MachineInstr *NewInstr = MF->CreateMachineInstr(TII->get(NewOpcode), DL);
507  //insert before
508  blk->insert(I, NewInstr);
509  MachineInstrBuilder(*MF, NewInstr).addReg(RegNum, false);
510  SHOWNEWINSTR(NewInstr);
511 }
512 
513 int AMDGPUCFGStructurizer::getBranchNzeroOpcode(int OldOpcode) {
514  switch(OldOpcode) {
515  case R600::JUMP_COND:
516  case R600::JUMP: return R600::IF_PREDICATE_SET;
517  case R600::BRANCH_COND_i32:
518  case R600::BRANCH_COND_f32: return R600::IF_LOGICALNZ_f32;
519  default: llvm_unreachable("internal error");
520  }
521  return -1;
522 }
523 
524 int AMDGPUCFGStructurizer::getBranchZeroOpcode(int OldOpcode) {
525  switch(OldOpcode) {
526  case R600::JUMP_COND:
527  case R600::JUMP: return R600::IF_PREDICATE_SET;
528  case R600::BRANCH_COND_i32:
529  case R600::BRANCH_COND_f32: return R600::IF_LOGICALZ_f32;
530  default: llvm_unreachable("internal error");
531  }
532  return -1;
533 }
534 
535 int AMDGPUCFGStructurizer::getContinueNzeroOpcode(int OldOpcode) {
536  switch(OldOpcode) {
537  case R600::JUMP_COND:
538  case R600::JUMP: return R600::CONTINUE_LOGICALNZ_i32;
539  default: llvm_unreachable("internal error");
540  }
541  return -1;
542 }
543 
544 int AMDGPUCFGStructurizer::getContinueZeroOpcode(int OldOpcode) {
545  switch(OldOpcode) {
546  case R600::JUMP_COND:
547  case R600::JUMP: return R600::CONTINUE_LOGICALZ_i32;
548  default: llvm_unreachable("internal error");
549  }
550  return -1;
551 }
552 
553 MachineBasicBlock *AMDGPUCFGStructurizer::getTrueBranch(MachineInstr *MI) {
554  return MI->getOperand(0).getMBB();
555 }
556 
557 void AMDGPUCFGStructurizer::setTrueBranch(MachineInstr *MI,
558  MachineBasicBlock *MBB) {
559  MI->getOperand(0).setMBB(MBB);
560 }
561 
563 AMDGPUCFGStructurizer::getFalseBranch(MachineBasicBlock *MBB,
564  MachineInstr *MI) {
565  assert(MBB->succ_size() == 2);
566  MachineBasicBlock *TrueBranch = getTrueBranch(MI);
569  ++Next;
570  return (*It == TrueBranch) ? *Next : *It;
571 }
572 
573 bool AMDGPUCFGStructurizer::isCondBranch(MachineInstr *MI) {
574  switch (MI->getOpcode()) {
575  case R600::JUMP_COND:
576  case R600::BRANCH_COND_i32:
577  case R600::BRANCH_COND_f32: return true;
578  default:
579  return false;
580  }
581  return false;
582 }
583 
584 bool AMDGPUCFGStructurizer::isUncondBranch(MachineInstr *MI) {
585  switch (MI->getOpcode()) {
586  case R600::JUMP:
587  case R600::BRANCH:
588  return true;
589  default:
590  return false;
591  }
592  return false;
593 }
594 
595 DebugLoc AMDGPUCFGStructurizer::getLastDebugLocInBB(MachineBasicBlock *MBB) {
596  //get DebugLoc from the first MachineBasicBlock instruction with debug info
597  DebugLoc DL;
598  for (MachineBasicBlock::iterator It = MBB->begin(); It != MBB->end();
599  ++It) {
600  MachineInstr *instr = &(*It);
601  if (instr->getDebugLoc())
602  DL = instr->getDebugLoc();
603  }
604  return DL;
605 }
606 
607 MachineInstr *AMDGPUCFGStructurizer::getNormalBlockBranchInstr(
608  MachineBasicBlock *MBB) {
610  MachineInstr *MI = &*It;
611  if (MI && (isCondBranch(MI) || isUncondBranch(MI)))
612  return MI;
613  return nullptr;
614 }
615 
616 MachineInstr *AMDGPUCFGStructurizer::getLoopendBlockBranchInstr(
617  MachineBasicBlock *MBB) {
618  for (MachineBasicBlock::reverse_iterator It = MBB->rbegin(), E = MBB->rend();
619  It != E; ++It) {
620  // FIXME: Simplify
621  MachineInstr *MI = &*It;
622  if (MI) {
623  if (isCondBranch(MI) || isUncondBranch(MI))
624  return MI;
625  else if (!TII->isMov(MI->getOpcode()))
626  break;
627  }
628  }
629  return nullptr;
630 }
631 
632 MachineInstr *AMDGPUCFGStructurizer::getReturnInstr(MachineBasicBlock *MBB) {
634  if (It != MBB->rend()) {
635  MachineInstr *instr = &(*It);
636  if (instr->getOpcode() == R600::RETURN)
637  return instr;
638  }
639  return nullptr;
640 }
641 
642 bool AMDGPUCFGStructurizer::isReturnBlock(MachineBasicBlock *MBB) {
643  MachineInstr *MI = getReturnInstr(MBB);
644  bool IsReturn = (MBB->succ_size() == 0);
645  if (MI)
646  assert(IsReturn);
647  else if (IsReturn)
648  LLVM_DEBUG(dbgs() << "BB" << MBB->getNumber()
649  << " is return block without RETURN instr\n";);
650  return IsReturn;
651 }
652 
653 void AMDGPUCFGStructurizer::cloneSuccessorList(MachineBasicBlock *DstMBB,
654  MachineBasicBlock *SrcMBB) {
655  for (MachineBasicBlock::succ_iterator It = SrcMBB->succ_begin(),
656  iterEnd = SrcMBB->succ_end(); It != iterEnd; ++It)
657  DstMBB->addSuccessor(*It); // *iter's predecessor is also taken care of
658 }
659 
660 MachineBasicBlock *AMDGPUCFGStructurizer::clone(MachineBasicBlock *MBB) {
661  MachineFunction *Func = MBB->getParent();
662  MachineBasicBlock *NewMBB = Func->CreateMachineBasicBlock();
663  Func->push_back(NewMBB); //insert to function
664  for (const MachineInstr &It : *MBB)
665  NewMBB->push_back(Func->CloneMachineInstr(&It));
666  return NewMBB;
667 }
668 
669 void AMDGPUCFGStructurizer::replaceInstrUseOfBlockWith(
670  MachineBasicBlock *SrcMBB, MachineBasicBlock *OldMBB,
671  MachineBasicBlock *NewBlk) {
672  MachineInstr *BranchMI = getLoopendBlockBranchInstr(SrcMBB);
673  if (BranchMI && isCondBranch(BranchMI) &&
674  getTrueBranch(BranchMI) == OldMBB)
675  setTrueBranch(BranchMI, NewBlk);
676 }
677 
678 void AMDGPUCFGStructurizer::wrapup(MachineBasicBlock *MBB) {
679  assert((!MBB->getParent()->getJumpTableInfo()
680  || MBB->getParent()->getJumpTableInfo()->isEmpty())
681  && "found a jump table");
682 
683  //collect continue right before endloop
685  MachineBasicBlock::iterator Pre = MBB->begin();
688  while (It != E) {
689  if (Pre->getOpcode() == R600::CONTINUE
690  && It->getOpcode() == R600::ENDLOOP)
691  ContInstr.push_back(&*Pre);
692  Pre = It;
693  ++It;
694  }
695 
696  //delete continue right before endloop
697  for (unsigned i = 0; i < ContInstr.size(); ++i)
698  ContInstr[i]->eraseFromParent();
699 
700  // TODO to fix up jump table so later phase won't be confused. if
701  // (jumpTableInfo->isEmpty() == false) { need to clean the jump table, but
702  // there isn't such an interface yet. alternatively, replace all the other
703  // blocks in the jump table with the entryBlk //}
704 }
705 
706 bool AMDGPUCFGStructurizer::prepare() {
707  bool Changed = false;
708 
709  //FIXME: if not reducible flow graph, make it so ???
710 
711  LLVM_DEBUG(dbgs() << "AMDGPUCFGStructurizer::prepare\n";);
712 
713  orderBlocks(FuncRep);
714 
716 
717  // Add an ExitBlk to loop that don't have one
718  for (MachineLoopInfo::iterator It = MLI->begin(),
719  E = MLI->end(); It != E; ++It) {
720  MachineLoop *LoopRep = (*It);
721  MBBVector ExitingMBBs;
722  LoopRep->getExitingBlocks(ExitingMBBs);
723 
724  if (ExitingMBBs.size() == 0) {
725  MachineBasicBlock* DummyExitBlk = normalizeInfiniteLoopExit(LoopRep);
726  if (DummyExitBlk)
727  RetBlks.push_back(DummyExitBlk);
728  }
729  }
730 
731  // Remove unconditional branch instr.
732  // Add dummy exit block iff there are multiple returns.
734  It = OrderedBlks.begin(), E = OrderedBlks.end(); It != E; ++It) {
735  MachineBasicBlock *MBB = *It;
736  removeUnconditionalBranch(MBB);
737  removeRedundantConditionalBranch(MBB);
738  if (isReturnBlock(MBB)) {
739  RetBlks.push_back(MBB);
740  }
741  assert(MBB->succ_size() <= 2);
742  }
743 
744  if (RetBlks.size() >= 2) {
745  addDummyExitBlock(RetBlks);
746  Changed = true;
747  }
748 
749  return Changed;
750 }
751 
752 bool AMDGPUCFGStructurizer::run() {
753  //Assume reducible CFG...
754  LLVM_DEBUG(dbgs() << "AMDGPUCFGStructurizer::run\n");
755 
756 #ifdef STRESSTEST
757  //Use the worse block ordering to test the algorithm.
758  ReverseVector(orderedBlks);
759 #endif
760 
761  LLVM_DEBUG(dbgs() << "Ordered blocks:\n"; printOrderedBlocks(););
762  int NumIter = 0;
763  bool Finish = false;
764  MachineBasicBlock *MBB;
765  bool MakeProgress = false;
766  int NumRemainedBlk = countActiveBlock(OrderedBlks.begin(),
767  OrderedBlks.end());
768 
769  do {
770  ++NumIter;
771  LLVM_DEBUG(dbgs() << "numIter = " << NumIter
772  << ", numRemaintedBlk = " << NumRemainedBlk << "\n";);
773 
775  OrderedBlks.begin();
777  OrderedBlks.end();
778 
780  It;
781  MachineBasicBlock *SccBeginMBB = nullptr;
782  int SccNumBlk = 0; // The number of active blocks, init to a
783  // maximum possible number.
784  int SccNumIter; // Number of iteration in this SCC.
785 
786  while (It != E) {
787  MBB = *It;
788 
789  if (!SccBeginMBB) {
790  SccBeginIter = It;
791  SccBeginMBB = MBB;
792  SccNumIter = 0;
793  SccNumBlk = NumRemainedBlk; // Init to maximum possible number.
794  LLVM_DEBUG(dbgs() << "start processing SCC" << getSCCNum(SccBeginMBB);
795  dbgs() << "\n";);
796  }
797 
798  if (!isRetiredBlock(MBB))
799  patternMatch(MBB);
800 
801  ++It;
802 
803  bool ContNextScc = true;
804  if (It == E
805  || getSCCNum(SccBeginMBB) != getSCCNum(*It)) {
806  // Just finish one scc.
807  ++SccNumIter;
808  int sccRemainedNumBlk = countActiveBlock(SccBeginIter, It);
809  if (sccRemainedNumBlk != 1 && sccRemainedNumBlk >= SccNumBlk) {
810  LLVM_DEBUG(dbgs() << "Can't reduce SCC " << getSCCNum(MBB)
811  << ", sccNumIter = " << SccNumIter;
812  dbgs() << "doesn't make any progress\n";);
813  ContNextScc = true;
814  } else if (sccRemainedNumBlk != 1 && sccRemainedNumBlk < SccNumBlk) {
815  SccNumBlk = sccRemainedNumBlk;
816  It = SccBeginIter;
817  ContNextScc = false;
818  LLVM_DEBUG(dbgs() << "repeat processing SCC" << getSCCNum(MBB)
819  << "sccNumIter = " << SccNumIter << '\n';);
820  } else {
821  // Finish the current scc.
822  ContNextScc = true;
823  }
824  } else {
825  // Continue on next component in the current scc.
826  ContNextScc = false;
827  }
828 
829  if (ContNextScc)
830  SccBeginMBB = nullptr;
831  } //while, "one iteration" over the function.
832 
833  MachineBasicBlock *EntryMBB =
835  if (EntryMBB->succ_size() == 0) {
836  Finish = true;
837  LLVM_DEBUG(dbgs() << "Reduce to one block\n";);
838  } else {
839  int NewnumRemainedBlk
840  = countActiveBlock(OrderedBlks.begin(), OrderedBlks.end());
841  // consider cloned blocks ??
842  if (NewnumRemainedBlk == 1 || NewnumRemainedBlk < NumRemainedBlk) {
843  MakeProgress = true;
844  NumRemainedBlk = NewnumRemainedBlk;
845  } else {
846  MakeProgress = false;
847  LLVM_DEBUG(dbgs() << "No progress\n";);
848  }
849  }
850  } while (!Finish && MakeProgress);
851 
852  // Misc wrap up to maintain the consistency of the Function representation.
854 
855  // Detach retired Block, release memory.
856  for (MBBInfoMap::iterator It = BlockInfoMap.begin(), E = BlockInfoMap.end();
857  It != E; ++It) {
858  if ((*It).second && (*It).second->IsRetired) {
859  assert(((*It).first)->getNumber() != -1);
860  LLVM_DEBUG(dbgs() << "Erase BB" << ((*It).first)->getNumber() << "\n";);
861  (*It).first->eraseFromParent(); //Remove from the parent Function.
862  }
863  delete (*It).second;
864  }
865  BlockInfoMap.clear();
866  LLInfoMap.clear();
867 
868  if (!Finish) {
869  LLVM_DEBUG(FuncRep->viewCFG());
870  report_fatal_error("IRREDUCIBLE_CFG");
871  }
872 
873  return true;
874 }
875 
876 void AMDGPUCFGStructurizer::orderBlocks(MachineFunction *MF) {
877  int SccNum = 0;
878  MachineBasicBlock *MBB;
879  for (scc_iterator<MachineFunction *> It = scc_begin(MF); !It.isAtEnd();
880  ++It, ++SccNum) {
881  const std::vector<MachineBasicBlock *> &SccNext = *It;
882  for (std::vector<MachineBasicBlock *>::const_iterator
883  blockIter = SccNext.begin(), blockEnd = SccNext.end();
884  blockIter != blockEnd; ++blockIter) {
885  MBB = *blockIter;
886  OrderedBlks.push_back(MBB);
887  recordSccnum(MBB, SccNum);
888  }
889  }
890 
891  // walk through all the block in func to check for unreachable
892  for (auto *MBB : nodes(MF)) {
893  SccNum = getSCCNum(MBB);
894  if (SccNum == INVALIDSCCNUM)
895  dbgs() << "unreachable block BB" << MBB->getNumber() << "\n";
896  }
897 }
898 
899 int AMDGPUCFGStructurizer::patternMatch(MachineBasicBlock *MBB) {
900  int NumMatch = 0;
901  int CurMatch;
902 
903  LLVM_DEBUG(dbgs() << "Begin patternMatch BB" << MBB->getNumber() << "\n";);
904 
905  while ((CurMatch = patternMatchGroup(MBB)) > 0)
906  NumMatch += CurMatch;
907 
908  LLVM_DEBUG(dbgs() << "End patternMatch BB" << MBB->getNumber()
909  << ", numMatch = " << NumMatch << "\n";);
910 
911  return NumMatch;
912 }
913 
914 int AMDGPUCFGStructurizer::patternMatchGroup(MachineBasicBlock *MBB) {
915  int NumMatch = 0;
916  NumMatch += loopendPatternMatch();
917  NumMatch += serialPatternMatch(MBB);
918  NumMatch += ifPatternMatch(MBB);
919  return NumMatch;
920 }
921 
922 int AMDGPUCFGStructurizer::serialPatternMatch(MachineBasicBlock *MBB) {
923  if (MBB->succ_size() != 1)
924  return 0;
925 
926  MachineBasicBlock *childBlk = *MBB->succ_begin();
927  if (childBlk->pred_size() != 1 || isActiveLoophead(childBlk))
928  return 0;
929 
930  mergeSerialBlock(MBB, childBlk);
931  ++numSerialPatternMatch;
932  return 1;
933 }
934 
935 int AMDGPUCFGStructurizer::ifPatternMatch(MachineBasicBlock *MBB) {
936  //two edges
937  if (MBB->succ_size() != 2)
938  return 0;
939  if (hasBackEdge(MBB))
940  return 0;
941  MachineInstr *BranchMI = getNormalBlockBranchInstr(MBB);
942  if (!BranchMI)
943  return 0;
944 
945  assert(isCondBranch(BranchMI));
946  int NumMatch = 0;
947 
948  MachineBasicBlock *TrueMBB = getTrueBranch(BranchMI);
949  NumMatch += serialPatternMatch(TrueMBB);
950  NumMatch += ifPatternMatch(TrueMBB);
951  MachineBasicBlock *FalseMBB = getFalseBranch(MBB, BranchMI);
952  NumMatch += serialPatternMatch(FalseMBB);
953  NumMatch += ifPatternMatch(FalseMBB);
954  MachineBasicBlock *LandBlk;
955  int Cloned = 0;
956 
957  assert (!TrueMBB->succ_empty() || !FalseMBB->succ_empty());
958  // TODO: Simplify
959  if (TrueMBB->succ_size() == 1 && FalseMBB->succ_size() == 1
960  && *TrueMBB->succ_begin() == *FalseMBB->succ_begin()) {
961  // Diamond pattern
962  LandBlk = *TrueMBB->succ_begin();
963  } else if (TrueMBB->succ_size() == 1 && *TrueMBB->succ_begin() == FalseMBB) {
964  // Triangle pattern, false is empty
965  LandBlk = FalseMBB;
966  FalseMBB = nullptr;
967  } else if (FalseMBB->succ_size() == 1
968  && *FalseMBB->succ_begin() == TrueMBB) {
969  // Triangle pattern, true is empty
970  // We reverse the predicate to make a triangle, empty false pattern;
971  std::swap(TrueMBB, FalseMBB);
972  reversePredicateSetter(MBB->end(), *MBB);
973  LandBlk = FalseMBB;
974  FalseMBB = nullptr;
975  } else if (FalseMBB->succ_size() == 1
976  && isSameloopDetachedContbreak(TrueMBB, FalseMBB)) {
977  LandBlk = *FalseMBB->succ_begin();
978  } else if (TrueMBB->succ_size() == 1
979  && isSameloopDetachedContbreak(FalseMBB, TrueMBB)) {
980  LandBlk = *TrueMBB->succ_begin();
981  } else {
982  return NumMatch + handleJumpintoIf(MBB, TrueMBB, FalseMBB);
983  }
984 
985  // improveSimpleJumpinfoIf can handle the case where landBlk == NULL but the
986  // new BB created for landBlk==NULL may introduce new challenge to the
987  // reduction process.
988  if (LandBlk &&
989  ((TrueMBB && TrueMBB->pred_size() > 1)
990  || (FalseMBB && FalseMBB->pred_size() > 1))) {
991  Cloned += improveSimpleJumpintoIf(MBB, TrueMBB, FalseMBB, &LandBlk);
992  }
993 
994  if (TrueMBB && TrueMBB->pred_size() > 1) {
995  TrueMBB = cloneBlockForPredecessor(TrueMBB, MBB);
996  ++Cloned;
997  }
998 
999  if (FalseMBB && FalseMBB->pred_size() > 1) {
1000  FalseMBB = cloneBlockForPredecessor(FalseMBB, MBB);
1001  ++Cloned;
1002  }
1003 
1004  mergeIfthenelseBlock(BranchMI, MBB, TrueMBB, FalseMBB, LandBlk);
1005 
1006  ++numIfPatternMatch;
1007 
1008  numClonedBlock += Cloned;
1009 
1010  return 1 + Cloned + NumMatch;
1011 }
1012 
1013 int AMDGPUCFGStructurizer::loopendPatternMatch() {
1014  std::deque<MachineLoop *> NestedLoops;
1015  for (auto &It: *MLI)
1016  for (MachineLoop *ML : depth_first(It))
1017  NestedLoops.push_front(ML);
1018 
1019  if (NestedLoops.empty())
1020  return 0;
1021 
1022  // Process nested loop outside->inside (we did push_front),
1023  // so "continue" to a outside loop won't be mistaken as "break"
1024  // of the current loop.
1025  int Num = 0;
1026  for (MachineLoop *ExaminedLoop : NestedLoops) {
1027  if (ExaminedLoop->getNumBlocks() == 0 || Visited[ExaminedLoop])
1028  continue;
1029  LLVM_DEBUG(dbgs() << "Processing:\n"; ExaminedLoop->dump(););
1030  int NumBreak = mergeLoop(ExaminedLoop);
1031  if (NumBreak == -1)
1032  break;
1033  Num += NumBreak;
1034  }
1035  return Num;
1036 }
1037 
1038 int AMDGPUCFGStructurizer::mergeLoop(MachineLoop *LoopRep) {
1039  MachineBasicBlock *LoopHeader = LoopRep->getHeader();
1040  MBBVector ExitingMBBs;
1041  LoopRep->getExitingBlocks(ExitingMBBs);
1042  assert(!ExitingMBBs.empty() && "Infinite Loop not supported");
1043  LLVM_DEBUG(dbgs() << "Loop has " << ExitingMBBs.size()
1044  << " exiting blocks\n";);
1045  // We assume a single ExitBlk
1046  MBBVector ExitBlks;
1047  LoopRep->getExitBlocks(ExitBlks);
1049  for (unsigned i = 0, e = ExitBlks.size(); i < e; ++i)
1050  ExitBlkSet.insert(ExitBlks[i]);
1051  assert(ExitBlkSet.size() == 1);
1052  MachineBasicBlock *ExitBlk = *ExitBlks.begin();
1053  assert(ExitBlk && "Loop has several exit block");
1054  MBBVector LatchBlks;
1055  for (auto *LB : inverse_children<MachineBasicBlock*>(LoopHeader))
1056  if (LoopRep->contains(LB))
1057  LatchBlks.push_back(LB);
1058 
1059  for (unsigned i = 0, e = ExitingMBBs.size(); i < e; ++i)
1060  mergeLoopbreakBlock(ExitingMBBs[i], ExitBlk);
1061  for (unsigned i = 0, e = LatchBlks.size(); i < e; ++i)
1062  settleLoopcontBlock(LatchBlks[i], LoopHeader);
1063  int Match = 0;
1064  do {
1065  Match = 0;
1066  Match += serialPatternMatch(LoopHeader);
1067  Match += ifPatternMatch(LoopHeader);
1068  } while (Match > 0);
1069  mergeLooplandBlock(LoopHeader, ExitBlk);
1070  MachineLoop *ParentLoop = LoopRep->getParentLoop();
1071  if (ParentLoop)
1072  MLI->changeLoopFor(LoopHeader, ParentLoop);
1073  else
1074  MLI->removeBlock(LoopHeader);
1075  Visited[LoopRep] = true;
1076  return 1;
1077 }
1078 
1079 bool AMDGPUCFGStructurizer::isSameloopDetachedContbreak(
1080  MachineBasicBlock *Src1MBB, MachineBasicBlock *Src2MBB) {
1081  if (Src1MBB->succ_size() == 0) {
1082  MachineLoop *LoopRep = MLI->getLoopFor(Src1MBB);
1083  if (LoopRep&& LoopRep == MLI->getLoopFor(Src2MBB)) {
1084  MachineBasicBlock *&TheEntry = LLInfoMap[LoopRep];
1085  if (TheEntry) {
1086  LLVM_DEBUG(dbgs() << "isLoopContBreakBlock yes src1 = BB"
1087  << Src1MBB->getNumber() << " src2 = BB"
1088  << Src2MBB->getNumber() << "\n";);
1089  return true;
1090  }
1091  }
1092  }
1093  return false;
1094 }
1095 
1096 int AMDGPUCFGStructurizer::handleJumpintoIf(MachineBasicBlock *HeadMBB,
1097  MachineBasicBlock *TrueMBB, MachineBasicBlock *FalseMBB) {
1098  int Num = handleJumpintoIfImp(HeadMBB, TrueMBB, FalseMBB);
1099  if (Num == 0) {
1100  LLVM_DEBUG(dbgs() << "handleJumpintoIf swap trueBlk and FalseBlk"
1101  << "\n";);
1102  Num = handleJumpintoIfImp(HeadMBB, FalseMBB, TrueMBB);
1103  }
1104  return Num;
1105 }
1106 
1107 int AMDGPUCFGStructurizer::handleJumpintoIfImp(MachineBasicBlock *HeadMBB,
1108  MachineBasicBlock *TrueMBB, MachineBasicBlock *FalseMBB) {
1109  int Num = 0;
1110  MachineBasicBlock *DownBlk;
1111 
1112  //trueBlk could be the common post dominator
1113  DownBlk = TrueMBB;
1114 
1115  LLVM_DEBUG(dbgs() << "handleJumpintoIfImp head = BB" << HeadMBB->getNumber()
1116  << " true = BB" << TrueMBB->getNumber()
1117  << ", numSucc=" << TrueMBB->succ_size() << " false = BB"
1118  << FalseMBB->getNumber() << "\n";);
1119 
1120  while (DownBlk) {
1121  LLVM_DEBUG(dbgs() << "check down = BB" << DownBlk->getNumber(););
1122 
1123  if (singlePathTo(FalseMBB, DownBlk) == SinglePath_InPath) {
1124  LLVM_DEBUG(dbgs() << " working\n";);
1125 
1126  Num += cloneOnSideEntryTo(HeadMBB, TrueMBB, DownBlk);
1127  Num += cloneOnSideEntryTo(HeadMBB, FalseMBB, DownBlk);
1128 
1129  numClonedBlock += Num;
1130  Num += serialPatternMatch(*HeadMBB->succ_begin());
1131  Num += serialPatternMatch(*std::next(HeadMBB->succ_begin()));
1132  Num += ifPatternMatch(HeadMBB);
1133  assert(Num > 0);
1134 
1135  break;
1136  }
1137  LLVM_DEBUG(dbgs() << " not working\n";);
1138  DownBlk = (DownBlk->succ_size() == 1) ? (*DownBlk->succ_begin()) : nullptr;
1139  } // walk down the postDomTree
1140 
1141  return Num;
1142 }
1143 
1144 #ifndef NDEBUG
1145 void AMDGPUCFGStructurizer::showImproveSimpleJumpintoIf(
1146  MachineBasicBlock *HeadMBB, MachineBasicBlock *TrueMBB,
1147  MachineBasicBlock *FalseMBB, MachineBasicBlock *LandMBB, bool Detail) {
1148  dbgs() << "head = BB" << HeadMBB->getNumber()
1149  << " size = " << HeadMBB->size();
1150  if (Detail) {
1151  dbgs() << "\n";
1152  HeadMBB->print(dbgs());
1153  dbgs() << "\n";
1154  }
1155 
1156  if (TrueMBB) {
1157  dbgs() << ", true = BB" << TrueMBB->getNumber() << " size = "
1158  << TrueMBB->size() << " numPred = " << TrueMBB->pred_size();
1159  if (Detail) {
1160  dbgs() << "\n";
1161  TrueMBB->print(dbgs());
1162  dbgs() << "\n";
1163  }
1164  }
1165  if (FalseMBB) {
1166  dbgs() << ", false = BB" << FalseMBB->getNumber() << " size = "
1167  << FalseMBB->size() << " numPred = " << FalseMBB->pred_size();
1168  if (Detail) {
1169  dbgs() << "\n";
1170  FalseMBB->print(dbgs());
1171  dbgs() << "\n";
1172  }
1173  }
1174  if (LandMBB) {
1175  dbgs() << ", land = BB" << LandMBB->getNumber() << " size = "
1176  << LandMBB->size() << " numPred = " << LandMBB->pred_size();
1177  if (Detail) {
1178  dbgs() << "\n";
1179  LandMBB->print(dbgs());
1180  dbgs() << "\n";
1181  }
1182  }
1183 
1184  dbgs() << "\n";
1185 }
1186 #endif
1187 
1188 int AMDGPUCFGStructurizer::improveSimpleJumpintoIf(MachineBasicBlock *HeadMBB,
1189  MachineBasicBlock *TrueMBB, MachineBasicBlock *FalseMBB,
1190  MachineBasicBlock **LandMBBPtr) {
1191  bool MigrateTrue = false;
1192  bool MigrateFalse = false;
1193 
1194  MachineBasicBlock *LandBlk = *LandMBBPtr;
1195 
1196  assert((!TrueMBB || TrueMBB->succ_size() <= 1)
1197  && (!FalseMBB || FalseMBB->succ_size() <= 1));
1198 
1199  if (TrueMBB == FalseMBB)
1200  return 0;
1201 
1202  MigrateTrue = needMigrateBlock(TrueMBB);
1203  MigrateFalse = needMigrateBlock(FalseMBB);
1204 
1205  if (!MigrateTrue && !MigrateFalse)
1206  return 0;
1207 
1208  // If we need to migrate either trueBlk and falseBlk, migrate the rest that
1209  // have more than one predecessors. without doing this, its predecessor
1210  // rather than headBlk will have undefined value in initReg.
1211  if (!MigrateTrue && TrueMBB && TrueMBB->pred_size() > 1)
1212  MigrateTrue = true;
1213  if (!MigrateFalse && FalseMBB && FalseMBB->pred_size() > 1)
1214  MigrateFalse = true;
1215 
1216  LLVM_DEBUG(
1217  dbgs() << "before improveSimpleJumpintoIf: ";
1218  showImproveSimpleJumpintoIf(HeadMBB, TrueMBB, FalseMBB, LandBlk, 0););
1219 
1220  // org: headBlk => if () {trueBlk} else {falseBlk} => landBlk
1221  //
1222  // new: headBlk => if () {initReg = 1; org trueBlk branch} else
1223  // {initReg = 0; org falseBlk branch }
1224  // => landBlk => if (initReg) {org trueBlk} else {org falseBlk}
1225  // => org landBlk
1226  // if landBlk->pred_size() > 2, put the about if-else inside
1227  // if (initReg !=2) {...}
1228  //
1229  // add initReg = initVal to headBlk
1230 
1231  const TargetRegisterClass * I32RC = TRI->getCFGStructurizerRegClass(MVT::i32);
1232  if (!MigrateTrue || !MigrateFalse) {
1233  // XXX: We have an opportunity here to optimize the "branch into if" case
1234  // here. Branch into if looks like this:
1235  // entry
1236  // / |
1237  // diamond_head branch_from
1238  // / \ |
1239  // diamond_false diamond_true
1240  // \ /
1241  // done
1242  //
1243  // The diamond_head block begins the "if" and the diamond_true block
1244  // is the block being "branched into".
1245  //
1246  // If MigrateTrue is true, then TrueBB is the block being "branched into"
1247  // and if MigrateFalse is true, then FalseBB is the block being
1248  // "branched into"
1249  //
1250  // Here is the pseudo code for how I think the optimization should work:
1251  // 1. Insert MOV GPR0, 0 before the branch instruction in diamond_head.
1252  // 2. Insert MOV GPR0, 1 before the branch instruction in branch_from.
1253  // 3. Move the branch instruction from diamond_head into its own basic
1254  // block (new_block).
1255  // 4. Add an unconditional branch from diamond_head to new_block
1256  // 5. Replace the branch instruction in branch_from with an unconditional
1257  // branch to new_block. If branch_from has multiple predecessors, then
1258  // we need to replace the True/False block in the branch
1259  // instruction instead of replacing it.
1260  // 6. Change the condition of the branch instruction in new_block from
1261  // COND to (COND || GPR0)
1262  //
1263  // In order insert these MOV instruction, we will need to use the
1264  // RegisterScavenger. Usually liveness stops being tracked during
1265  // the late machine optimization passes, however if we implement
1266  // bool TargetRegisterInfo::requiresRegisterScavenging(
1267  // const MachineFunction &MF)
1268  // and have it return true, liveness will be tracked correctly
1269  // by generic optimization passes. We will also need to make sure that
1270  // all of our target-specific passes that run after regalloc and before
1271  // the CFGStructurizer track liveness and we will need to modify this pass
1272  // to correctly track liveness.
1273  //
1274  // After the above changes, the new CFG should look like this:
1275  // entry
1276  // / |
1277  // diamond_head branch_from
1278  // \ /
1279  // new_block
1280  // / |
1281  // diamond_false diamond_true
1282  // \ /
1283  // done
1284  //
1285  // Without this optimization, we are forced to duplicate the diamond_true
1286  // block and we will end up with a CFG like this:
1287  //
1288  // entry
1289  // / |
1290  // diamond_head branch_from
1291  // / \ |
1292  // diamond_false diamond_true diamond_true (duplicate)
1293  // \ / |
1294  // done --------------------|
1295  //
1296  // Duplicating diamond_true can be very costly especially if it has a
1297  // lot of instructions.
1298  return 0;
1299  }
1300 
1301  int NumNewBlk = 0;
1302 
1303  bool LandBlkHasOtherPred = (LandBlk->pred_size() > 2);
1304 
1305  //insert R600::ENDIF to avoid special case "input landBlk == NULL"
1306  MachineBasicBlock::iterator I = insertInstrBefore(LandBlk, R600::ENDIF);
1307 
1308  if (LandBlkHasOtherPred) {
1309  report_fatal_error("Extra register needed to handle CFG");
1310  Register CmpResReg =
1311  HeadMBB->getParent()->getRegInfo().createVirtualRegister(I32RC);
1312  report_fatal_error("Extra compare instruction needed to handle CFG");
1313  insertCondBranchBefore(LandBlk, I, R600::IF_PREDICATE_SET,
1314  CmpResReg, DebugLoc());
1315  }
1316 
1317  // XXX: We are running this after RA, so creating virtual registers will
1318  // cause an assertion failure in the PostRA scheduling pass.
1319  Register InitReg =
1320  HeadMBB->getParent()->getRegInfo().createVirtualRegister(I32RC);
1321  insertCondBranchBefore(LandBlk, I, R600::IF_PREDICATE_SET, InitReg,
1322  DebugLoc());
1323 
1324  if (MigrateTrue) {
1325  migrateInstruction(TrueMBB, LandBlk, I);
1326  // need to uncondionally insert the assignment to ensure a path from its
1327  // predecessor rather than headBlk has valid value in initReg if
1328  // (initVal != 1).
1329  report_fatal_error("Extra register needed to handle CFG");
1330  }
1331  insertInstrBefore(I, R600::ELSE);
1332 
1333  if (MigrateFalse) {
1334  migrateInstruction(FalseMBB, LandBlk, I);
1335  // need to uncondionally insert the assignment to ensure a path from its
1336  // predecessor rather than headBlk has valid value in initReg if
1337  // (initVal != 0)
1338  report_fatal_error("Extra register needed to handle CFG");
1339  }
1340 
1341  if (LandBlkHasOtherPred) {
1342  // add endif
1343  insertInstrBefore(I, R600::ENDIF);
1344 
1345  // put initReg = 2 to other predecessors of landBlk
1346  for (MachineBasicBlock::pred_iterator PI = LandBlk->pred_begin(),
1347  PE = LandBlk->pred_end(); PI != PE; ++PI) {
1348  MachineBasicBlock *MBB = *PI;
1349  if (MBB != TrueMBB && MBB != FalseMBB)
1350  report_fatal_error("Extra register needed to handle CFG");
1351  }
1352  }
1353  LLVM_DEBUG(
1354  dbgs() << "result from improveSimpleJumpintoIf: ";
1355  showImproveSimpleJumpintoIf(HeadMBB, TrueMBB, FalseMBB, LandBlk, 0););
1356 
1357  // update landBlk
1358  *LandMBBPtr = LandBlk;
1359 
1360  return NumNewBlk;
1361 }
1362 
1363 void AMDGPUCFGStructurizer::mergeSerialBlock(MachineBasicBlock *DstMBB,
1364  MachineBasicBlock *SrcMBB) {
1365  LLVM_DEBUG(dbgs() << "serialPattern BB" << DstMBB->getNumber() << " <= BB"
1366  << SrcMBB->getNumber() << "\n";);
1367  DstMBB->splice(DstMBB->end(), SrcMBB, SrcMBB->begin(), SrcMBB->end());
1368 
1369  DstMBB->removeSuccessor(SrcMBB, true);
1370  cloneSuccessorList(DstMBB, SrcMBB);
1371 
1372  removeSuccessor(SrcMBB);
1373  MLI->removeBlock(SrcMBB);
1374  retireBlock(SrcMBB);
1375 }
1376 
1377 void AMDGPUCFGStructurizer::mergeIfthenelseBlock(MachineInstr *BranchMI,
1378  MachineBasicBlock *MBB, MachineBasicBlock *TrueMBB,
1379  MachineBasicBlock *FalseMBB, MachineBasicBlock *LandMBB) {
1380  assert (TrueMBB);
1381  LLVM_DEBUG(dbgs() << "ifPattern BB" << MBB->getNumber(); dbgs() << "{ ";
1382  if (TrueMBB) { dbgs() << "BB" << TrueMBB->getNumber(); } dbgs()
1383  << " } else ";
1384  dbgs() << "{ "; if (FalseMBB) {
1385  dbgs() << "BB" << FalseMBB->getNumber();
1386  } dbgs() << " }\n ";
1387  dbgs() << "landBlock: "; if (!LandMBB) { dbgs() << "NULL"; } else {
1388  dbgs() << "BB" << LandMBB->getNumber();
1389  } dbgs() << "\n";);
1390 
1391  int OldOpcode = BranchMI->getOpcode();
1392  DebugLoc BranchDL = BranchMI->getDebugLoc();
1393 
1394 // transform to
1395 // if cond
1396 // trueBlk
1397 // else
1398 // falseBlk
1399 // endif
1400 // landBlk
1401 
1402  MachineBasicBlock::iterator I = BranchMI;
1403  insertCondBranchBefore(I, getBranchNzeroOpcode(OldOpcode),
1404  BranchDL);
1405 
1406  if (TrueMBB) {
1407  MBB->splice(I, TrueMBB, TrueMBB->begin(), TrueMBB->end());
1408  MBB->removeSuccessor(TrueMBB, true);
1409  if (LandMBB && TrueMBB->succ_size()!=0)
1410  TrueMBB->removeSuccessor(LandMBB, true);
1411  retireBlock(TrueMBB);
1412  MLI->removeBlock(TrueMBB);
1413  }
1414 
1415  if (FalseMBB) {
1416  insertInstrBefore(I, R600::ELSE);
1417  MBB->splice(I, FalseMBB, FalseMBB->begin(),
1418  FalseMBB->end());
1419  MBB->removeSuccessor(FalseMBB, true);
1420  if (LandMBB && FalseMBB->succ_size() != 0)
1421  FalseMBB->removeSuccessor(LandMBB, true);
1422  retireBlock(FalseMBB);
1423  MLI->removeBlock(FalseMBB);
1424  }
1425  insertInstrBefore(I, R600::ENDIF);
1426 
1427  BranchMI->eraseFromParent();
1428 
1429  if (LandMBB && TrueMBB && FalseMBB)
1430  MBB->addSuccessor(LandMBB);
1431 }
1432 
1433 void AMDGPUCFGStructurizer::mergeLooplandBlock(MachineBasicBlock *DstBlk,
1434  MachineBasicBlock *LandMBB) {
1435  LLVM_DEBUG(dbgs() << "loopPattern header = BB" << DstBlk->getNumber()
1436  << " land = BB" << LandMBB->getNumber() << "\n";);
1437 
1438  insertInstrBefore(DstBlk, R600::WHILELOOP, DebugLoc());
1439  insertInstrEnd(DstBlk, R600::ENDLOOP, DebugLoc());
1440  DstBlk->replaceSuccessor(DstBlk, LandMBB);
1441 }
1442 
1443 void AMDGPUCFGStructurizer::mergeLoopbreakBlock(MachineBasicBlock *ExitingMBB,
1444  MachineBasicBlock *LandMBB) {
1445  LLVM_DEBUG(dbgs() << "loopbreakPattern exiting = BB"
1446  << ExitingMBB->getNumber() << " land = BB"
1447  << LandMBB->getNumber() << "\n";);
1448  MachineInstr *BranchMI = getLoopendBlockBranchInstr(ExitingMBB);
1449  assert(BranchMI && isCondBranch(BranchMI));
1450  DebugLoc DL = BranchMI->getDebugLoc();
1451  MachineBasicBlock *TrueBranch = getTrueBranch(BranchMI);
1452  MachineBasicBlock::iterator I = BranchMI;
1453  if (TrueBranch != LandMBB)
1454  reversePredicateSetter(I, *I->getParent());
1455  insertCondBranchBefore(ExitingMBB, I, R600::IF_PREDICATE_SET, R600::PREDICATE_BIT, DL);
1456  insertInstrBefore(I, R600::BREAK);
1457  insertInstrBefore(I, R600::ENDIF);
1458  //now branchInst can be erase safely
1459  BranchMI->eraseFromParent();
1460  //now take care of successors, retire blocks
1461  ExitingMBB->removeSuccessor(LandMBB, true);
1462 }
1463 
1464 void AMDGPUCFGStructurizer::settleLoopcontBlock(MachineBasicBlock *ContingMBB,
1465  MachineBasicBlock *ContMBB) {
1466  LLVM_DEBUG(dbgs() << "settleLoopcontBlock conting = BB"
1467  << ContingMBB->getNumber() << ", cont = BB"
1468  << ContMBB->getNumber() << "\n";);
1469 
1470  MachineInstr *MI = getLoopendBlockBranchInstr(ContingMBB);
1471  if (MI) {
1472  assert(isCondBranch(MI));
1474  MachineBasicBlock *TrueBranch = getTrueBranch(MI);
1475  int OldOpcode = MI->getOpcode();
1476  DebugLoc DL = MI->getDebugLoc();
1477 
1478  bool UseContinueLogical = ((&*ContingMBB->rbegin()) == MI);
1479 
1480  if (!UseContinueLogical) {
1481  int BranchOpcode =
1482  TrueBranch == ContMBB ? getBranchNzeroOpcode(OldOpcode) :
1483  getBranchZeroOpcode(OldOpcode);
1484  insertCondBranchBefore(I, BranchOpcode, DL);
1485  // insertEnd to ensure phi-moves, if exist, go before the continue-instr.
1486  insertInstrEnd(ContingMBB, R600::CONTINUE, DL);
1487  insertInstrEnd(ContingMBB, R600::ENDIF, DL);
1488  } else {
1489  int BranchOpcode =
1490  TrueBranch == ContMBB ? getContinueNzeroOpcode(OldOpcode) :
1491  getContinueZeroOpcode(OldOpcode);
1492  insertCondBranchBefore(I, BranchOpcode, DL);
1493  }
1494 
1495  MI->eraseFromParent();
1496  } else {
1497  // if we've arrived here then we've already erased the branch instruction
1498  // travel back up the basic block to see the last reference of our debug
1499  // location we've just inserted that reference here so it should be
1500  // representative insertEnd to ensure phi-moves, if exist, go before the
1501  // continue-instr.
1502  insertInstrEnd(ContingMBB, R600::CONTINUE,
1503  getLastDebugLocInBB(ContingMBB));
1504  }
1505 }
1506 
1507 int AMDGPUCFGStructurizer::cloneOnSideEntryTo(MachineBasicBlock *PreMBB,
1508  MachineBasicBlock *SrcMBB, MachineBasicBlock *DstMBB) {
1509  int Cloned = 0;
1510  assert(PreMBB->isSuccessor(SrcMBB));
1511  while (SrcMBB && SrcMBB != DstMBB) {
1512  assert(SrcMBB->succ_size() == 1);
1513  if (SrcMBB->pred_size() > 1) {
1514  SrcMBB = cloneBlockForPredecessor(SrcMBB, PreMBB);
1515  ++Cloned;
1516  }
1517 
1518  PreMBB = SrcMBB;
1519  SrcMBB = *SrcMBB->succ_begin();
1520  }
1521 
1522  return Cloned;
1523 }
1524 
1526 AMDGPUCFGStructurizer::cloneBlockForPredecessor(MachineBasicBlock *MBB,
1527  MachineBasicBlock *PredMBB) {
1528  assert(PredMBB->isSuccessor(MBB) &&
1529  "succBlk is not a prececessor of curBlk");
1530 
1531  MachineBasicBlock *CloneMBB = clone(MBB); //clone instructions
1532  replaceInstrUseOfBlockWith(PredMBB, MBB, CloneMBB);
1533  //srcBlk, oldBlk, newBlk
1534 
1535  PredMBB->replaceSuccessor(MBB, CloneMBB);
1536 
1537  // add all successor to cloneBlk
1538  cloneSuccessorList(CloneMBB, MBB);
1539 
1540  numClonedInstr += MBB->size();
1541 
1542  LLVM_DEBUG(dbgs() << "Cloned block: "
1543  << "BB" << MBB->getNumber() << "size " << MBB->size()
1544  << "\n";);
1545 
1546  SHOWNEWBLK(CloneMBB, "result of Cloned block: ");
1547 
1548  return CloneMBB;
1549 }
1550 
1551 void AMDGPUCFGStructurizer::migrateInstruction(MachineBasicBlock *SrcMBB,
1553  MachineBasicBlock::iterator SpliceEnd;
1554  //look for the input branchinstr, not the AMDGPU branchinstr
1555  MachineInstr *BranchMI = getNormalBlockBranchInstr(SrcMBB);
1556  if (!BranchMI) {
1557  LLVM_DEBUG(dbgs() << "migrateInstruction don't see branch instr\n";);
1558  SpliceEnd = SrcMBB->end();
1559  } else {
1560  LLVM_DEBUG(dbgs() << "migrateInstruction see branch instr: " << *BranchMI);
1561  SpliceEnd = BranchMI;
1562  }
1563  LLVM_DEBUG(dbgs() << "migrateInstruction before splice dstSize = "
1564  << DstMBB->size() << "srcSize = " << SrcMBB->size()
1565  << "\n";);
1566 
1567  //splice insert before insertPos
1568  DstMBB->splice(I, SrcMBB, SrcMBB->begin(), SpliceEnd);
1569 
1570  LLVM_DEBUG(dbgs() << "migrateInstruction after splice dstSize = "
1571  << DstMBB->size() << "srcSize = " << SrcMBB->size()
1572  << '\n';);
1573 }
1574 
1576 AMDGPUCFGStructurizer::normalizeInfiniteLoopExit(MachineLoop* LoopRep) {
1577  MachineBasicBlock *LoopHeader = LoopRep->getHeader();
1578  MachineBasicBlock *LoopLatch = LoopRep->getLoopLatch();
1579 
1580  if (!LoopHeader || !LoopLatch)
1581  return nullptr;
1582  MachineInstr *BranchMI = getLoopendBlockBranchInstr(LoopLatch);
1583  // Is LoopRep an infinite loop ?
1584  if (!BranchMI || !isUncondBranch(BranchMI))
1585  return nullptr;
1586 
1587  MachineBasicBlock *DummyExitBlk = FuncRep->CreateMachineBasicBlock();
1588  FuncRep->push_back(DummyExitBlk); //insert to function
1589  SHOWNEWBLK(DummyExitBlk, "DummyExitBlock to normalize infiniteLoop: ");
1590  LLVM_DEBUG(dbgs() << "Old branch instr: " << *BranchMI << "\n";);
1591  LLVMContext &Ctx = LoopHeader->getParent()->getFunction().getContext();
1592  Ctx.emitError("Extra register needed to handle CFG");
1593  return nullptr;
1594 }
1595 
1596 void AMDGPUCFGStructurizer::removeUnconditionalBranch(MachineBasicBlock *MBB) {
1597  MachineInstr *BranchMI;
1598 
1599  // I saw two unconditional branch in one basic block in example
1600  // test_fc_do_while_or.c need to fix the upstream on this to remove the loop.
1601  while ((BranchMI = getLoopendBlockBranchInstr(MBB))
1602  && isUncondBranch(BranchMI)) {
1603  LLVM_DEBUG(dbgs() << "Removing uncond branch instr: " << *BranchMI);
1604  BranchMI->eraseFromParent();
1605  }
1606 }
1607 
1608 void AMDGPUCFGStructurizer::removeRedundantConditionalBranch(
1609  MachineBasicBlock *MBB) {
1610  if (MBB->succ_size() != 2)
1611  return;
1612  MachineBasicBlock *MBB1 = *MBB->succ_begin();
1613  MachineBasicBlock *MBB2 = *std::next(MBB->succ_begin());
1614  if (MBB1 != MBB2)
1615  return;
1616 
1617  MachineInstr *BranchMI = getNormalBlockBranchInstr(MBB);
1618  assert(BranchMI && isCondBranch(BranchMI));
1619  LLVM_DEBUG(dbgs() << "Removing unneeded cond branch instr: " << *BranchMI);
1620  BranchMI->eraseFromParent();
1621  SHOWNEWBLK(MBB1, "Removing redundant successor");
1622  MBB->removeSuccessor(MBB1, true);
1623 }
1624 
1625 void AMDGPUCFGStructurizer::addDummyExitBlock(
1627  MachineBasicBlock *DummyExitBlk = FuncRep->CreateMachineBasicBlock();
1628  FuncRep->push_back(DummyExitBlk); //insert to function
1629  insertInstrEnd(DummyExitBlk, R600::RETURN);
1630 
1632  E = RetMBB.end(); It != E; ++It) {
1633  MachineBasicBlock *MBB = *It;
1634  MachineInstr *MI = getReturnInstr(MBB);
1635  if (MI)
1636  MI->eraseFromParent();
1637  MBB->addSuccessor(DummyExitBlk);
1638  LLVM_DEBUG(dbgs() << "Add dummyExitBlock to BB" << MBB->getNumber()
1639  << " successors\n";);
1640  }
1641  SHOWNEWBLK(DummyExitBlk, "DummyExitBlock: ");
1642 }
1643 
1644 void AMDGPUCFGStructurizer::removeSuccessor(MachineBasicBlock *MBB) {
1645  while (MBB->succ_size())
1646  MBB->removeSuccessor(*MBB->succ_begin());
1647 }
1648 
1649 void AMDGPUCFGStructurizer::recordSccnum(MachineBasicBlock *MBB,
1650  int SccNum) {
1651  BlockInformation *&srcBlkInfo = BlockInfoMap[MBB];
1652  if (!srcBlkInfo)
1653  srcBlkInfo = new BlockInformation();
1654  srcBlkInfo->SccNum = SccNum;
1655 }
1656 
1657 void AMDGPUCFGStructurizer::retireBlock(MachineBasicBlock *MBB) {
1658  LLVM_DEBUG(dbgs() << "Retiring BB" << MBB->getNumber() << "\n";);
1659 
1660  BlockInformation *&SrcBlkInfo = BlockInfoMap[MBB];
1661 
1662  if (!SrcBlkInfo)
1663  SrcBlkInfo = new BlockInformation();
1664 
1665  SrcBlkInfo->IsRetired = true;
1666  assert(MBB->succ_size() == 0 && MBB->pred_size() == 0
1667  && "can't retire block yet");
1668 }
1669 
1670 INITIALIZE_PASS_BEGIN(AMDGPUCFGStructurizer, "amdgpustructurizer",
1671  "AMDGPU CFG Structurizer", false, false)
1675 INITIALIZE_PASS_END(AMDGPUCFGStructurizer, "amdgpustructurizer",
1677 
1679  return new AMDGPUCFGStructurizer();
1680 }
void print(raw_ostream &OS, const SlotIndexes *=nullptr, bool IsStandalone=true) const
INITIALIZE_PASS_BEGIN(AMDGPUCFGStructurizer, "amdgpustructurizer", "AMDGPU CFG Structurizer", false, false) INITIALIZE_PASS_END(AMDGPUCFGStructurizer
This builds on the llvm/ADT/GraphTraits.h file to find the strongly connected components (SCCs) of a ...
BlockT * getLoopLatch() const
If there is a single latch block for this loop, return it.
Definition: LoopInfoImpl.h:209
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
AMDGPU specific subclass of TargetSubtarget.
typename SuperClass::const_iterator const_iterator
Definition: SmallVector.h:320
MachineBasicBlock * getMBB() const
LLVM_ATTRIBUTE_NORETURN void report_fatal_error(Error Err, bool gen_crash_diag=true)
Report a serious error, calling any installed error handler.
Definition: Error.cpp:139
This class represents lattice values for constants.
Definition: AllocatorList.h:23
Interface definition for R600InstrInfo.
A Module instance is used to store all the information related to an LLVM module. ...
Definition: Module.h:66
Register createVirtualRegister(const TargetRegisterClass *RegClass, StringRef Name="")
createVirtualRegister - Create and return a new virtual register in the function with the specified r...
const DebugLoc & getDebugLoc() const
Returns the debug location id of this MachineInstr.
Definition: MachineInstr.h:384
AMDGPU CFG Structurizer
STATISTIC(NumFunctions, "Total number of functions")
unsigned const TargetRegisterInfo * TRI
A debug info location.
Definition: DebugLoc.h:33
FunctionPass * createAMDGPUCFGStructurizerPass()
Interface definition for R600RegisterInfo.
void dump() const
dump - Print the current MachineFunction to cerr, useful for debugger use.
MachineInstr * CreateMachineInstr(const MCInstrDesc &MCID, const DebugLoc &DL, bool NoImp=false)
CreateMachineInstr - Allocate a new MachineInstr.
AnalysisUsage & addRequired()
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:50
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
const HexagonInstrInfo * TII
#define SHOWNEWINSTR(i)
void initializeAMDGPUCFGStructurizerPass(PassRegistry &)
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:41
void eraseFromParent()
Unlink &#39;this&#39; from the containing basic block and delete it.
static int getSCCNum(const BasicBlock *BB, const BranchProbabilityInfo::SccInfo &SccI)
unsigned getOpcode() const
Returns the opcode of this MachineInstr.
Definition: MachineInstr.h:410
BlockT * getHeader() const
Definition: LoopInfo.h:105
scc_iterator< T > scc_begin(const T &G)
Construct the begin iterator for a deduced graph type T.
Definition: SCCIterator.h:225
void getExitBlocks(SmallVectorImpl< BlockT *> &ExitBlocks) const
Return all of the successor blocks of this loop.
Definition: LoopInfoImpl.h:62
void emitError(unsigned LocCookie, const Twine &ErrorStr)
emitError - Emit an error message to the currently installed error handler with optional location inf...
std::vector< MachineLoop *>::const_iterator iterator
Definition: LoopInfo.h:144
int getNumber() const
MachineBasicBlocks are uniquely numbered at the function level, unless they&#39;re not in a MachineFuncti...
instr_iterator insert(instr_iterator I, MachineInstr *M)
Insert MI into the instruction list before I, possibly inside a bundle.
reverse_iterator rend()
MachineBasicBlock * CreateMachineBasicBlock(const BasicBlock *bb=nullptr)
CreateMachineBasicBlock - Allocate a new MachineBasicBlock.
reverse_iterator rbegin()
iterator begin() const
#define INVALIDSCCNUM
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:64
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:370
#define SHOWNEWBLK(b, msg)
void setMBB(MachineBasicBlock *MBB)
Represent the analysis usage information of a pass.
constexpr double e
Definition: MathExtras.h:57
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:284
std::vector< MachineBasicBlock * >::iterator pred_iterator
LLVMContext & getContext() const
getContext - Return a reference to the LLVMContext associated with this function. ...
Definition: Function.cpp:205
void getExitingBlocks(SmallVectorImpl< BlockT *> &ExitingBlocks) const
Return all blocks inside the loop that have successors outside of the loop.
Definition: LoopInfoImpl.h:34
size_t size() const
Definition: SmallVector.h:52
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
size_type size() const
Definition: SmallPtrSet.h:92
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
Definition: LoopInfo.h:115
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements...
Definition: SmallPtrSet.h:417
void addSuccessor(MachineBasicBlock *Succ, BranchProbability Prob=BranchProbability::getUnknown())
Add Succ as a successor of this MachineBasicBlock.
MachineInstr * CloneMachineInstr(const MachineInstr *Orig)
Create a new MachineInstr which is a copy of Orig, identical in all ways except the instruction has n...
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:837
unsigned pred_size() const
const Function & getFunction() const
Return the LLVM function that this machine code represents.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:940
typename SuperClass::iterator iterator
Definition: SmallVector.h:319
void replaceSuccessor(MachineBasicBlock *Old, MachineBasicBlock *New)
Replace successor OLD with NEW and update probability info.
iterator end() const
unsigned succ_size() const
const MachineBasicBlock * getParent() const
Definition: MachineInstr.h:255
LoopT * getParentLoop() const
Definition: LoopInfo.h:106
Provides AMDGPU specific target descriptions.
Representation of each machine instruction.
Definition: MachineInstr.h:63
const MachineFunction * getParent() const
Return the MachineFunction containing this basic block.
Flatten the CFG
iterator_range< typename GraphTraits< GraphType >::nodes_iterator > nodes(const GraphType &G)
Definition: GraphTraits.h:108
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;...
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:55
void push_back(MachineInstr *MI)
#define I(x, y, z)
Definition: MD5.cpp:58
LoopInfoBase< MachineBasicBlock, MachineLoop >::iterator iterator
The iterator interface to the top-level loops in the current function.
bool isSuccessor(const MachineBasicBlock *MBB) const
Return true if the specified MBB is a successor of this block.
void removeSuccessor(MachineBasicBlock *Succ, bool NormalizeSuccProbs=false)
Remove successor from the successors list of this MachineBasicBlock.
iterator_range< df_iterator< T > > depth_first(const T &G)
bool isEmpty() const
isEmpty - Return true if there are no jump tables.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
MachinePostDominatorTree - an analysis pass wrapper for DominatorTree used to compute the post-domina...
void push_back(MachineBasicBlock *MBB)
IRTranslator LLVM IR MI
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:48
static uint32_t blk(uint32_t *Buf, int I)
Definition: SHA1.cpp:35
PassRegistry - This class manages the registration and intitialization of the pass subsystem as appli...
Definition: PassRegistry.h:38
Register getReg() const
getReg - Returns the register number.
#define LLVM_DEBUG(X)
Definition: Debug.h:122
const MachineJumpTableInfo * getJumpTableInfo() const
getJumpTableInfo - Return the jump table info object for the current function.
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:415
const MachineInstrBuilder & addReg(Register RegNo, unsigned flags=0, unsigned SubReg=0) const
Add a new virtual register operand.
DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to compute a normal dominat...
std::vector< MachineBasicBlock * >::iterator succ_iterator
Wrapper class representing virtual and physical registers.
Definition: Register.h:19
Enumerate the SCCs of a directed graph in reverse topological order of the SCC DAG.
Definition: SCCIterator.h:42