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