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