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