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