1 //===-- AMDILCFGStructurizer.cpp - CFG Structurizer -----------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
9 //==-----------------------------------------------------------------------===//
12 #include "AMDGPUInstrInfo.h"
13 #include "R600InstrInfo.h"
14 #include "AMDGPUSubtarget.h"
15 #include "llvm/ADT/DepthFirstIterator.h"
16 #include "llvm/ADT/SCCIterator.h"
17 #include "llvm/ADT/SmallVector.h"
18 #include "llvm/ADT/Statistic.h"
19 #include "llvm/CodeGen/MachineDominators.h"
20 #include "llvm/CodeGen/MachineFunction.h"
21 #include "llvm/CodeGen/MachineFunctionAnalysis.h"
22 #include "llvm/CodeGen/MachineFunctionPass.h"
23 #include "llvm/CodeGen/MachineInstrBuilder.h"
24 #include "llvm/CodeGen/MachineJumpTableInfo.h"
25 #include "llvm/CodeGen/MachineLoopInfo.h"
26 #include "llvm/CodeGen/MachinePostDominators.h"
27 #include "llvm/CodeGen/MachineRegisterInfo.h"
28 #include "llvm/IR/Dominators.h"
29 #include "llvm/Support/Debug.h"
30 #include "llvm/Support/raw_ostream.h"
31 #include "llvm/Target/TargetInstrInfo.h"
32 #include "llvm/Target/TargetMachine.h"
36 #define DEBUG_TYPE "structcfg"
38 #define DEFAULT_VEC_SLOTS 8
42 //===----------------------------------------------------------------------===//
44 // Statistics for CFGStructurizer.
46 //===----------------------------------------------------------------------===//
48 STATISTIC(numSerialPatternMatch, "CFGStructurizer number of serial pattern "
50 STATISTIC(numIfPatternMatch, "CFGStructurizer number of if pattern "
52 STATISTIC(numLoopcontPatternMatch, "CFGStructurizer number of loop-continue "
54 STATISTIC(numClonedBlock, "CFGStructurizer cloned blocks");
55 STATISTIC(numClonedInstr, "CFGStructurizer cloned instructions");
58 void initializeAMDGPUCFGStructurizerPass(PassRegistry&);
61 //===----------------------------------------------------------------------===//
63 // Miscellaneous utility for CFGStructurizer.
65 //===----------------------------------------------------------------------===//
67 #define SHOWNEWINSTR(i) \
68 DEBUG(dbgs() << "New instr: " << *i << "\n");
70 #define SHOWNEWBLK(b, msg) \
72 dbgs() << msg << "BB" << b->getNumber() << "size " << b->size(); \
76 #define SHOWBLK_DETAIL(b, msg) \
79 dbgs() << msg << "BB" << b->getNumber() << "size " << b->size(); \
85 #define INVALIDSCCNUM -1
88 void ReverseVector(SmallVectorImpl<NodeT *> &Src) {
89 size_t sz = Src.size();
90 for (size_t i = 0; i < sz/2; ++i) {
92 Src[i] = Src[sz - i - 1];
97 } // end anonymous namespace
99 //===----------------------------------------------------------------------===//
101 // supporting data structure for CFGStructurizer
103 //===----------------------------------------------------------------------===//
108 class BlockInformation {
112 BlockInformation() : IsRetired(false), SccNum(INVALIDSCCNUM) {}
115 } // end anonymous namespace
117 //===----------------------------------------------------------------------===//
121 //===----------------------------------------------------------------------===//
124 class AMDGPUCFGStructurizer : public MachineFunctionPass {
126 typedef SmallVector<MachineBasicBlock *, 32> MBBVector;
127 typedef std::map<MachineBasicBlock *, BlockInformation *> MBBInfoMap;
128 typedef std::map<MachineLoop *, MachineBasicBlock *> LoopLandInfoMap;
132 SinglePath_InPath = 1,
133 SinglePath_NotInPath = 2
138 AMDGPUCFGStructurizer() :
139 MachineFunctionPass(ID), TII(nullptr), TRI(nullptr) {
140 initializeAMDGPUCFGStructurizerPass(*PassRegistry::getPassRegistry());
143 const char *getPassName() const override {
144 return "AMDGPU Control Flow Graph structurizer Pass";
147 void getAnalysisUsage(AnalysisUsage &AU) const override {
148 AU.addPreserved<MachineFunctionAnalysis>();
149 AU.addRequired<MachineFunctionAnalysis>();
150 AU.addRequired<MachineDominatorTree>();
151 AU.addRequired<MachinePostDominatorTree>();
152 AU.addRequired<MachineLoopInfo>();
155 /// Perform the CFG structurization
158 /// Perform the CFG preparation
159 /// This step will remove every unconditionnal/dead jump instructions and make
160 /// sure all loops have an exit block
163 bool runOnMachineFunction(MachineFunction &MF) override {
164 TII = static_cast<const R600InstrInfo *>(MF.getSubtarget().getInstrInfo());
165 TRI = &TII->getRegisterInfo();
169 MLI = &getAnalysis<MachineLoopInfo>();
170 DEBUG(dbgs() << "LoopInfo:\n"; PrintLoopinfo(*MLI););
171 MDT = &getAnalysis<MachineDominatorTree>();
172 DEBUG(MDT->print(dbgs(), (const llvm::Module*)nullptr););
173 PDT = &getAnalysis<MachinePostDominatorTree>();
174 DEBUG(PDT->print(dbgs()););
182 MachineDominatorTree *MDT;
183 MachinePostDominatorTree *PDT;
184 MachineLoopInfo *MLI;
185 const R600InstrInfo *TII;
186 const AMDGPURegisterInfo *TRI;
189 /// Print the ordered Blocks.
190 void printOrderedBlocks() const {
192 for (MBBVector::const_iterator iterBlk = OrderedBlks.begin(),
193 iterBlkEnd = OrderedBlks.end(); iterBlk != iterBlkEnd; ++iterBlk, ++i) {
194 dbgs() << "BB" << (*iterBlk)->getNumber();
195 dbgs() << "(" << getSCCNum(*iterBlk) << "," << (*iterBlk)->size() << ")";
196 if (i != 0 && i % 10 == 0) {
203 static void PrintLoopinfo(const MachineLoopInfo &LoopInfo) {
204 for (MachineLoop::iterator iter = LoopInfo.begin(),
205 iterEnd = LoopInfo.end(); iter != iterEnd; ++iter) {
206 (*iter)->print(dbgs(), 0);
211 int getSCCNum(MachineBasicBlock *MBB) const;
212 MachineBasicBlock *getLoopLandInfo(MachineLoop *LoopRep) const;
213 bool hasBackEdge(MachineBasicBlock *MBB) const;
214 static unsigned getLoopDepth(MachineLoop *LoopRep);
215 bool isRetiredBlock(MachineBasicBlock *MBB) const;
216 bool isActiveLoophead(MachineBasicBlock *MBB) const;
217 PathToKind singlePathTo(MachineBasicBlock *SrcMBB, MachineBasicBlock *DstMBB,
218 bool AllowSideEntry = true) const;
219 int countActiveBlock(MBBVector::const_iterator It,
220 MBBVector::const_iterator E) const;
221 bool needMigrateBlock(MachineBasicBlock *MBB) const;
224 void reversePredicateSetter(MachineBasicBlock::iterator I);
225 /// Compute the reversed DFS post order of Blocks
226 void orderBlocks(MachineFunction *MF);
228 // Function originally from CFGStructTraits
229 void insertInstrEnd(MachineBasicBlock *MBB, int NewOpcode,
230 DebugLoc DL = DebugLoc());
231 MachineInstr *insertInstrBefore(MachineBasicBlock *MBB, int NewOpcode,
232 DebugLoc DL = DebugLoc());
233 MachineInstr *insertInstrBefore(MachineBasicBlock::iterator I, int NewOpcode);
234 void insertCondBranchBefore(MachineBasicBlock::iterator I, int NewOpcode,
236 void insertCondBranchBefore(MachineBasicBlock *MBB,
237 MachineBasicBlock::iterator I, int NewOpcode, int RegNum,
239 void insertCondBranchEnd(MachineBasicBlock *MBB, int NewOpcode, int RegNum);
240 static int getBranchNzeroOpcode(int OldOpcode);
241 static int getBranchZeroOpcode(int OldOpcode);
242 static int getContinueNzeroOpcode(int OldOpcode);
243 static int getContinueZeroOpcode(int OldOpcode);
244 static MachineBasicBlock *getTrueBranch(MachineInstr *MI);
245 static void setTrueBranch(MachineInstr *MI, MachineBasicBlock *MBB);
246 static MachineBasicBlock *getFalseBranch(MachineBasicBlock *MBB,
248 static bool isCondBranch(MachineInstr *MI);
249 static bool isUncondBranch(MachineInstr *MI);
250 static DebugLoc getLastDebugLocInBB(MachineBasicBlock *MBB);
251 static MachineInstr *getNormalBlockBranchInstr(MachineBasicBlock *MBB);
252 /// The correct naming for this is getPossibleLoopendBlockBranchInstr.
254 /// BB with backward-edge could have move instructions after the branch
255 /// instruction. Such move instruction "belong to" the loop backward-edge.
256 MachineInstr *getLoopendBlockBranchInstr(MachineBasicBlock *MBB);
257 static MachineInstr *getReturnInstr(MachineBasicBlock *MBB);
258 static MachineInstr *getContinueInstr(MachineBasicBlock *MBB);
259 static bool isReturnBlock(MachineBasicBlock *MBB);
260 static void cloneSuccessorList(MachineBasicBlock *DstMBB,
261 MachineBasicBlock *SrcMBB) ;
262 static MachineBasicBlock *clone(MachineBasicBlock *MBB);
263 /// MachineBasicBlock::ReplaceUsesOfBlockWith doesn't serve the purpose
264 /// because the AMDGPU instruction is not recognized as terminator fix this
265 /// and retire this routine
266 void replaceInstrUseOfBlockWith(MachineBasicBlock *SrcMBB,
267 MachineBasicBlock *OldMBB, MachineBasicBlock *NewBlk);
268 static void wrapup(MachineBasicBlock *MBB);
271 int patternMatch(MachineBasicBlock *MBB);
272 int patternMatchGroup(MachineBasicBlock *MBB);
273 int serialPatternMatch(MachineBasicBlock *MBB);
274 int ifPatternMatch(MachineBasicBlock *MBB);
275 int loopendPatternMatch();
276 int mergeLoop(MachineLoop *LoopRep);
277 int loopcontPatternMatch(MachineLoop *LoopRep, MachineBasicBlock *LoopHeader);
279 void handleLoopcontBlock(MachineBasicBlock *ContingMBB,
280 MachineLoop *ContingLoop, MachineBasicBlock *ContMBB,
281 MachineLoop *ContLoop);
282 /// return true iff src1Blk->succ_size() == 0 && src1Blk and src2Blk are in
283 /// the same loop with LoopLandInfo without explicitly keeping track of
284 /// loopContBlks and loopBreakBlks, this is a method to get the information.
285 bool isSameloopDetachedContbreak(MachineBasicBlock *Src1MBB,
286 MachineBasicBlock *Src2MBB);
287 int handleJumpintoIf(MachineBasicBlock *HeadMBB,
288 MachineBasicBlock *TrueMBB, MachineBasicBlock *FalseMBB);
289 int handleJumpintoIfImp(MachineBasicBlock *HeadMBB,
290 MachineBasicBlock *TrueMBB, MachineBasicBlock *FalseMBB);
291 int improveSimpleJumpintoIf(MachineBasicBlock *HeadMBB,
292 MachineBasicBlock *TrueMBB, MachineBasicBlock *FalseMBB,
293 MachineBasicBlock **LandMBBPtr);
294 void showImproveSimpleJumpintoIf(MachineBasicBlock *HeadMBB,
295 MachineBasicBlock *TrueMBB, MachineBasicBlock *FalseMBB,
296 MachineBasicBlock *LandMBB, bool Detail = false);
297 int cloneOnSideEntryTo(MachineBasicBlock *PreMBB,
298 MachineBasicBlock *SrcMBB, MachineBasicBlock *DstMBB);
299 void mergeSerialBlock(MachineBasicBlock *DstMBB,
300 MachineBasicBlock *SrcMBB);
302 void mergeIfthenelseBlock(MachineInstr *BranchMI,
303 MachineBasicBlock *MBB, MachineBasicBlock *TrueMBB,
304 MachineBasicBlock *FalseMBB, MachineBasicBlock *LandMBB);
305 void mergeLooplandBlock(MachineBasicBlock *DstMBB,
306 MachineBasicBlock *LandMBB);
307 void mergeLoopbreakBlock(MachineBasicBlock *ExitingMBB,
308 MachineBasicBlock *LandMBB);
309 void settleLoopcontBlock(MachineBasicBlock *ContingMBB,
310 MachineBasicBlock *ContMBB);
311 /// normalizeInfiniteLoopExit change
313 /// uncond_br LoopHeader
317 /// cond_br 1 LoopHeader dummyExit
318 /// and return the newly added dummy exit block
319 MachineBasicBlock *normalizeInfiniteLoopExit(MachineLoop *LoopRep);
320 void removeUnconditionalBranch(MachineBasicBlock *MBB);
321 /// Remove duplicate branches instructions in a block.
326 /// is transformed to
329 void removeRedundantConditionalBranch(MachineBasicBlock *MBB);
330 void addDummyExitBlock(SmallVectorImpl<MachineBasicBlock *> &RetMBB);
331 void removeSuccessor(MachineBasicBlock *MBB);
332 MachineBasicBlock *cloneBlockForPredecessor(MachineBasicBlock *MBB,
333 MachineBasicBlock *PredMBB);
334 void migrateInstruction(MachineBasicBlock *SrcMBB,
335 MachineBasicBlock *DstMBB, MachineBasicBlock::iterator I);
336 void recordSccnum(MachineBasicBlock *MBB, int SCCNum);
337 void retireBlock(MachineBasicBlock *MBB);
338 void setLoopLandBlock(MachineLoop *LoopRep, MachineBasicBlock *MBB = nullptr);
340 MachineBasicBlock *findNearestCommonPostDom(std::set<MachineBasicBlock *>&);
341 /// This is work around solution for findNearestCommonDominator not available
342 /// to post dom a proper fix should go to Dominators.h.
343 MachineBasicBlock *findNearestCommonPostDom(MachineBasicBlock *MBB1,
344 MachineBasicBlock *MBB2);
347 MBBInfoMap BlockInfoMap;
348 LoopLandInfoMap LLInfoMap;
349 std::map<MachineLoop *, bool> Visited;
350 MachineFunction *FuncRep;
351 SmallVector<MachineBasicBlock *, DEFAULT_VEC_SLOTS> OrderedBlks;
354 int AMDGPUCFGStructurizer::getSCCNum(MachineBasicBlock *MBB) const {
355 MBBInfoMap::const_iterator It = BlockInfoMap.find(MBB);
356 if (It == BlockInfoMap.end())
357 return INVALIDSCCNUM;
358 return (*It).second->SccNum;
361 MachineBasicBlock *AMDGPUCFGStructurizer::getLoopLandInfo(MachineLoop *LoopRep)
363 LoopLandInfoMap::const_iterator It = LLInfoMap.find(LoopRep);
364 if (It == LLInfoMap.end())
369 bool AMDGPUCFGStructurizer::hasBackEdge(MachineBasicBlock *MBB) const {
370 MachineLoop *LoopRep = MLI->getLoopFor(MBB);
373 MachineBasicBlock *LoopHeader = LoopRep->getHeader();
374 return MBB->isSuccessor(LoopHeader);
377 unsigned AMDGPUCFGStructurizer::getLoopDepth(MachineLoop *LoopRep) {
378 return LoopRep ? LoopRep->getLoopDepth() : 0;
381 bool AMDGPUCFGStructurizer::isRetiredBlock(MachineBasicBlock *MBB) const {
382 MBBInfoMap::const_iterator It = BlockInfoMap.find(MBB);
383 if (It == BlockInfoMap.end())
385 return (*It).second->IsRetired;
388 bool AMDGPUCFGStructurizer::isActiveLoophead(MachineBasicBlock *MBB) const {
389 MachineLoop *LoopRep = MLI->getLoopFor(MBB);
390 while (LoopRep && LoopRep->getHeader() == MBB) {
391 MachineBasicBlock *LoopLand = getLoopLandInfo(LoopRep);
394 if (!isRetiredBlock(LoopLand))
396 LoopRep = LoopRep->getParentLoop();
400 AMDGPUCFGStructurizer::PathToKind AMDGPUCFGStructurizer::singlePathTo(
401 MachineBasicBlock *SrcMBB, MachineBasicBlock *DstMBB,
402 bool AllowSideEntry) const {
404 if (SrcMBB == DstMBB)
405 return SinglePath_InPath;
406 while (SrcMBB && SrcMBB->succ_size() == 1) {
407 SrcMBB = *SrcMBB->succ_begin();
408 if (SrcMBB == DstMBB)
409 return SinglePath_InPath;
410 if (!AllowSideEntry && SrcMBB->pred_size() > 1)
411 return Not_SinglePath;
413 if (SrcMBB && SrcMBB->succ_size()==0)
414 return SinglePath_NotInPath;
415 return Not_SinglePath;
418 int AMDGPUCFGStructurizer::countActiveBlock(MBBVector::const_iterator It,
419 MBBVector::const_iterator E) const {
422 if (!isRetiredBlock(*It))
429 bool AMDGPUCFGStructurizer::needMigrateBlock(MachineBasicBlock *MBB) const {
430 unsigned BlockSizeThreshold = 30;
431 unsigned CloneInstrThreshold = 100;
432 bool MultiplePreds = MBB && (MBB->pred_size() > 1);
436 unsigned BlkSize = MBB->size();
437 return ((BlkSize > BlockSizeThreshold) &&
438 (BlkSize * (MBB->pred_size() - 1) > CloneInstrThreshold));
441 void AMDGPUCFGStructurizer::reversePredicateSetter(
442 MachineBasicBlock::iterator I) {
444 if (I->getOpcode() == AMDGPU::PRED_X) {
445 switch (static_cast<MachineInstr *>(I)->getOperand(2).getImm()) {
446 case OPCODE_IS_ZERO_INT:
447 static_cast<MachineInstr *>(I)->getOperand(2)
448 .setImm(OPCODE_IS_NOT_ZERO_INT);
450 case OPCODE_IS_NOT_ZERO_INT:
451 static_cast<MachineInstr *>(I)->getOperand(2)
452 .setImm(OPCODE_IS_ZERO_INT);
455 static_cast<MachineInstr *>(I)->getOperand(2)
456 .setImm(OPCODE_IS_NOT_ZERO);
458 case OPCODE_IS_NOT_ZERO:
459 static_cast<MachineInstr *>(I)->getOperand(2)
460 .setImm(OPCODE_IS_ZERO);
463 llvm_unreachable("PRED_X Opcode invalid!");
469 void AMDGPUCFGStructurizer::insertInstrEnd(MachineBasicBlock *MBB,
470 int NewOpcode, DebugLoc DL) {
471 MachineInstr *MI = MBB->getParent()
472 ->CreateMachineInstr(TII->get(NewOpcode), DL);
474 //assume the instruction doesn't take any reg operand ...
478 MachineInstr *AMDGPUCFGStructurizer::insertInstrBefore(MachineBasicBlock *MBB,
479 int NewOpcode, DebugLoc DL) {
481 MBB->getParent()->CreateMachineInstr(TII->get(NewOpcode), DL);
482 if (MBB->begin() != MBB->end())
483 MBB->insert(MBB->begin(), MI);
490 MachineInstr *AMDGPUCFGStructurizer::insertInstrBefore(
491 MachineBasicBlock::iterator I, int NewOpcode) {
492 MachineInstr *OldMI = &(*I);
493 MachineBasicBlock *MBB = OldMI->getParent();
494 MachineInstr *NewMBB =
495 MBB->getParent()->CreateMachineInstr(TII->get(NewOpcode), DebugLoc());
496 MBB->insert(I, NewMBB);
497 //assume the instruction doesn't take any reg operand ...
498 SHOWNEWINSTR(NewMBB);
502 void AMDGPUCFGStructurizer::insertCondBranchBefore(
503 MachineBasicBlock::iterator I, int NewOpcode, DebugLoc DL) {
504 MachineInstr *OldMI = &(*I);
505 MachineBasicBlock *MBB = OldMI->getParent();
506 MachineFunction *MF = MBB->getParent();
507 MachineInstr *NewMI = MF->CreateMachineInstr(TII->get(NewOpcode), DL);
508 MBB->insert(I, NewMI);
509 MachineInstrBuilder MIB(*MF, NewMI);
510 MIB.addReg(OldMI->getOperand(1).getReg(), false);
512 //erase later oldInstr->eraseFromParent();
515 void AMDGPUCFGStructurizer::insertCondBranchBefore(MachineBasicBlock *blk,
516 MachineBasicBlock::iterator I, int NewOpcode, int RegNum,
518 MachineFunction *MF = blk->getParent();
519 MachineInstr *NewInstr = MF->CreateMachineInstr(TII->get(NewOpcode), DL);
521 blk->insert(I, NewInstr);
522 MachineInstrBuilder(*MF, NewInstr).addReg(RegNum, false);
523 SHOWNEWINSTR(NewInstr);
526 void AMDGPUCFGStructurizer::insertCondBranchEnd(MachineBasicBlock *MBB,
527 int NewOpcode, int RegNum) {
528 MachineFunction *MF = MBB->getParent();
529 MachineInstr *NewInstr =
530 MF->CreateMachineInstr(TII->get(NewOpcode), DebugLoc());
531 MBB->push_back(NewInstr);
532 MachineInstrBuilder(*MF, NewInstr).addReg(RegNum, false);
533 SHOWNEWINSTR(NewInstr);
536 int AMDGPUCFGStructurizer::getBranchNzeroOpcode(int OldOpcode) {
538 case AMDGPU::JUMP_COND:
539 case AMDGPU::JUMP: return AMDGPU::IF_PREDICATE_SET;
540 case AMDGPU::BRANCH_COND_i32:
541 case AMDGPU::BRANCH_COND_f32: return AMDGPU::IF_LOGICALNZ_f32;
542 default: llvm_unreachable("internal error");
547 int AMDGPUCFGStructurizer::getBranchZeroOpcode(int OldOpcode) {
549 case AMDGPU::JUMP_COND:
550 case AMDGPU::JUMP: return AMDGPU::IF_PREDICATE_SET;
551 case AMDGPU::BRANCH_COND_i32:
552 case AMDGPU::BRANCH_COND_f32: return AMDGPU::IF_LOGICALZ_f32;
553 default: llvm_unreachable("internal error");
558 int AMDGPUCFGStructurizer::getContinueNzeroOpcode(int OldOpcode) {
560 case AMDGPU::JUMP_COND:
561 case AMDGPU::JUMP: return AMDGPU::CONTINUE_LOGICALNZ_i32;
562 default: llvm_unreachable("internal error");
567 int AMDGPUCFGStructurizer::getContinueZeroOpcode(int OldOpcode) {
569 case AMDGPU::JUMP_COND:
570 case AMDGPU::JUMP: return AMDGPU::CONTINUE_LOGICALZ_i32;
571 default: llvm_unreachable("internal error");
576 MachineBasicBlock *AMDGPUCFGStructurizer::getTrueBranch(MachineInstr *MI) {
577 return MI->getOperand(0).getMBB();
580 void AMDGPUCFGStructurizer::setTrueBranch(MachineInstr *MI,
581 MachineBasicBlock *MBB) {
582 MI->getOperand(0).setMBB(MBB);
586 AMDGPUCFGStructurizer::getFalseBranch(MachineBasicBlock *MBB,
588 assert(MBB->succ_size() == 2);
589 MachineBasicBlock *TrueBranch = getTrueBranch(MI);
590 MachineBasicBlock::succ_iterator It = MBB->succ_begin();
591 MachineBasicBlock::succ_iterator Next = It;
593 return (*It == TrueBranch) ? *Next : *It;
596 bool AMDGPUCFGStructurizer::isCondBranch(MachineInstr *MI) {
597 switch (MI->getOpcode()) {
598 case AMDGPU::JUMP_COND:
599 case AMDGPU::BRANCH_COND_i32:
600 case AMDGPU::BRANCH_COND_f32: return true;
607 bool AMDGPUCFGStructurizer::isUncondBranch(MachineInstr *MI) {
608 switch (MI->getOpcode()) {
618 DebugLoc AMDGPUCFGStructurizer::getLastDebugLocInBB(MachineBasicBlock *MBB) {
619 //get DebugLoc from the first MachineBasicBlock instruction with debug info
621 for (MachineBasicBlock::iterator It = MBB->begin(); It != MBB->end();
623 MachineInstr *instr = &(*It);
624 if (instr->getDebugLoc().isUnknown() == false)
625 DL = instr->getDebugLoc();
630 MachineInstr *AMDGPUCFGStructurizer::getNormalBlockBranchInstr(
631 MachineBasicBlock *MBB) {
632 MachineBasicBlock::reverse_iterator It = MBB->rbegin();
633 MachineInstr *MI = &*It;
634 if (MI && (isCondBranch(MI) || isUncondBranch(MI)))
639 MachineInstr *AMDGPUCFGStructurizer::getLoopendBlockBranchInstr(
640 MachineBasicBlock *MBB) {
641 for (MachineBasicBlock::reverse_iterator It = MBB->rbegin(), E = MBB->rend();
644 MachineInstr *MI = &*It;
646 if (isCondBranch(MI) || isUncondBranch(MI))
648 else if (!TII->isMov(MI->getOpcode()))
655 MachineInstr *AMDGPUCFGStructurizer::getReturnInstr(MachineBasicBlock *MBB) {
656 MachineBasicBlock::reverse_iterator It = MBB->rbegin();
657 if (It != MBB->rend()) {
658 MachineInstr *instr = &(*It);
659 if (instr->getOpcode() == AMDGPU::RETURN)
665 MachineInstr *AMDGPUCFGStructurizer::getContinueInstr(MachineBasicBlock *MBB) {
666 MachineBasicBlock::reverse_iterator It = MBB->rbegin();
667 if (It != MBB->rend()) {
668 MachineInstr *MI = &(*It);
669 if (MI->getOpcode() == AMDGPU::CONTINUE)
675 bool AMDGPUCFGStructurizer::isReturnBlock(MachineBasicBlock *MBB) {
676 MachineInstr *MI = getReturnInstr(MBB);
677 bool IsReturn = (MBB->succ_size() == 0);
682 dbgs() << "BB" << MBB->getNumber()
683 <<" is return block without RETURN instr\n";);
687 void AMDGPUCFGStructurizer::cloneSuccessorList(MachineBasicBlock *DstMBB,
688 MachineBasicBlock *SrcMBB) {
689 for (MachineBasicBlock::succ_iterator It = SrcMBB->succ_begin(),
690 iterEnd = SrcMBB->succ_end(); It != iterEnd; ++It)
691 DstMBB->addSuccessor(*It); // *iter's predecessor is also taken care of
694 MachineBasicBlock *AMDGPUCFGStructurizer::clone(MachineBasicBlock *MBB) {
695 MachineFunction *Func = MBB->getParent();
696 MachineBasicBlock *NewMBB = Func->CreateMachineBasicBlock();
697 Func->push_back(NewMBB); //insert to function
698 for (MachineBasicBlock::iterator It = MBB->begin(), E = MBB->end();
700 MachineInstr *MI = Func->CloneMachineInstr(It);
701 NewMBB->push_back(MI);
706 void AMDGPUCFGStructurizer::replaceInstrUseOfBlockWith(
707 MachineBasicBlock *SrcMBB, MachineBasicBlock *OldMBB,
708 MachineBasicBlock *NewBlk) {
709 MachineInstr *BranchMI = getLoopendBlockBranchInstr(SrcMBB);
710 if (BranchMI && isCondBranch(BranchMI) &&
711 getTrueBranch(BranchMI) == OldMBB)
712 setTrueBranch(BranchMI, NewBlk);
715 void AMDGPUCFGStructurizer::wrapup(MachineBasicBlock *MBB) {
716 assert((!MBB->getParent()->getJumpTableInfo()
717 || MBB->getParent()->getJumpTableInfo()->isEmpty())
718 && "found a jump table");
720 //collect continue right before endloop
721 SmallVector<MachineInstr *, DEFAULT_VEC_SLOTS> ContInstr;
722 MachineBasicBlock::iterator Pre = MBB->begin();
723 MachineBasicBlock::iterator E = MBB->end();
724 MachineBasicBlock::iterator It = Pre;
726 if (Pre->getOpcode() == AMDGPU::CONTINUE
727 && It->getOpcode() == AMDGPU::ENDLOOP)
728 ContInstr.push_back(Pre);
733 //delete continue right before endloop
734 for (unsigned i = 0; i < ContInstr.size(); ++i)
735 ContInstr[i]->eraseFromParent();
737 // TODO to fix up jump table so later phase won't be confused. if
738 // (jumpTableInfo->isEmpty() == false) { need to clean the jump table, but
739 // there isn't such an interface yet. alternatively, replace all the other
740 // blocks in the jump table with the entryBlk //}
745 bool AMDGPUCFGStructurizer::prepare() {
746 bool Changed = false;
748 //FIXME: if not reducible flow graph, make it so ???
750 DEBUG(dbgs() << "AMDGPUCFGStructurizer::prepare\n";);
752 orderBlocks(FuncRep);
754 SmallVector<MachineBasicBlock *, DEFAULT_VEC_SLOTS> RetBlks;
756 // Add an ExitBlk to loop that don't have one
757 for (MachineLoopInfo::iterator It = MLI->begin(),
758 E = MLI->end(); It != E; ++It) {
759 MachineLoop *LoopRep = (*It);
760 MBBVector ExitingMBBs;
761 LoopRep->getExitingBlocks(ExitingMBBs);
763 if (ExitingMBBs.size() == 0) {
764 MachineBasicBlock* DummyExitBlk = normalizeInfiniteLoopExit(LoopRep);
766 RetBlks.push_back(DummyExitBlk);
770 // Remove unconditional branch instr.
771 // Add dummy exit block iff there are multiple returns.
772 for (SmallVectorImpl<MachineBasicBlock *>::const_iterator
773 It = OrderedBlks.begin(), E = OrderedBlks.end(); It != E; ++It) {
774 MachineBasicBlock *MBB = *It;
775 removeUnconditionalBranch(MBB);
776 removeRedundantConditionalBranch(MBB);
777 if (isReturnBlock(MBB)) {
778 RetBlks.push_back(MBB);
780 assert(MBB->succ_size() <= 2);
783 if (RetBlks.size() >= 2) {
784 addDummyExitBlock(RetBlks);
791 bool AMDGPUCFGStructurizer::run() {
793 //Assume reducible CFG...
794 DEBUG(dbgs() << "AMDGPUCFGStructurizer::run\n");
797 //Use the worse block ordering to test the algorithm.
798 ReverseVector(orderedBlks);
801 DEBUG(dbgs() << "Ordered blocks:\n"; printOrderedBlocks(););
804 MachineBasicBlock *MBB;
805 bool MakeProgress = false;
806 int NumRemainedBlk = countActiveBlock(OrderedBlks.begin(),
812 dbgs() << "numIter = " << NumIter
813 << ", numRemaintedBlk = " << NumRemainedBlk << "\n";
816 SmallVectorImpl<MachineBasicBlock *>::const_iterator It =
818 SmallVectorImpl<MachineBasicBlock *>::const_iterator E =
821 SmallVectorImpl<MachineBasicBlock *>::const_iterator SccBeginIter =
823 MachineBasicBlock *SccBeginMBB = nullptr;
824 int SccNumBlk = 0; // The number of active blocks, init to a
825 // maximum possible number.
826 int SccNumIter; // Number of iteration in this SCC.
835 SccNumBlk = NumRemainedBlk; // Init to maximum possible number.
837 dbgs() << "start processing SCC" << getSCCNum(SccBeginMBB);
842 if (!isRetiredBlock(MBB))
847 bool ContNextScc = true;
849 || getSCCNum(SccBeginMBB) != getSCCNum(*It)) {
850 // Just finish one scc.
852 int sccRemainedNumBlk = countActiveBlock(SccBeginIter, It);
853 if (sccRemainedNumBlk != 1 && sccRemainedNumBlk >= SccNumBlk) {
855 dbgs() << "Can't reduce SCC " << getSCCNum(MBB)
856 << ", sccNumIter = " << SccNumIter;
857 dbgs() << "doesn't make any progress\n";
860 } else if (sccRemainedNumBlk != 1 && sccRemainedNumBlk < SccNumBlk) {
861 SccNumBlk = sccRemainedNumBlk;
865 dbgs() << "repeat processing SCC" << getSCCNum(MBB)
866 << "sccNumIter = " << SccNumIter << '\n';
869 // Finish the current scc.
873 // Continue on next component in the current scc.
878 SccBeginMBB = nullptr;
879 } //while, "one iteration" over the function.
881 MachineBasicBlock *EntryMBB =
882 GraphTraits<MachineFunction *>::nodes_begin(FuncRep);
883 if (EntryMBB->succ_size() == 0) {
886 dbgs() << "Reduce to one block\n";
889 int NewnumRemainedBlk
890 = countActiveBlock(OrderedBlks.begin(), OrderedBlks.end());
891 // consider cloned blocks ??
892 if (NewnumRemainedBlk == 1 || NewnumRemainedBlk < NumRemainedBlk) {
894 NumRemainedBlk = NewnumRemainedBlk;
896 MakeProgress = false;
898 dbgs() << "No progress\n";
902 } while (!Finish && MakeProgress);
904 // Misc wrap up to maintain the consistency of the Function representation.
905 wrapup(GraphTraits<MachineFunction *>::nodes_begin(FuncRep));
907 // Detach retired Block, release memory.
908 for (MBBInfoMap::iterator It = BlockInfoMap.begin(), E = BlockInfoMap.end();
910 if ((*It).second && (*It).second->IsRetired) {
911 assert(((*It).first)->getNumber() != -1);
913 dbgs() << "Erase BB" << ((*It).first)->getNumber() << "\n";
915 (*It).first->eraseFromParent(); //Remove from the parent Function.
919 BlockInfoMap.clear();
923 DEBUG(FuncRep->viewCFG());
924 llvm_unreachable("IRREDUCIBLE_CFG");
932 void AMDGPUCFGStructurizer::orderBlocks(MachineFunction *MF) {
934 MachineBasicBlock *MBB;
935 for (scc_iterator<MachineFunction *> It = scc_begin(MF); !It.isAtEnd();
937 const std::vector<MachineBasicBlock *> &SccNext = *It;
938 for (std::vector<MachineBasicBlock *>::const_iterator
939 blockIter = SccNext.begin(), blockEnd = SccNext.end();
940 blockIter != blockEnd; ++blockIter) {
942 OrderedBlks.push_back(MBB);
943 recordSccnum(MBB, SccNum);
947 //walk through all the block in func to check for unreachable
948 typedef GraphTraits<MachineFunction *> GTM;
949 MachineFunction::iterator It = GTM::nodes_begin(MF), E = GTM::nodes_end(MF);
950 for (; It != E; ++It) {
951 MachineBasicBlock *MBB = &(*It);
952 SccNum = getSCCNum(MBB);
953 if (SccNum == INVALIDSCCNUM)
954 dbgs() << "unreachable block BB" << MBB->getNumber() << "\n";
958 int AMDGPUCFGStructurizer::patternMatch(MachineBasicBlock *MBB) {
963 dbgs() << "Begin patternMatch BB" << MBB->getNumber() << "\n";
966 while ((CurMatch = patternMatchGroup(MBB)) > 0)
967 NumMatch += CurMatch;
970 dbgs() << "End patternMatch BB" << MBB->getNumber()
971 << ", numMatch = " << NumMatch << "\n";
977 int AMDGPUCFGStructurizer::patternMatchGroup(MachineBasicBlock *MBB) {
979 NumMatch += loopendPatternMatch();
980 NumMatch += serialPatternMatch(MBB);
981 NumMatch += ifPatternMatch(MBB);
986 int AMDGPUCFGStructurizer::serialPatternMatch(MachineBasicBlock *MBB) {
987 if (MBB->succ_size() != 1)
990 MachineBasicBlock *childBlk = *MBB->succ_begin();
991 if (childBlk->pred_size() != 1 || isActiveLoophead(childBlk))
994 mergeSerialBlock(MBB, childBlk);
995 ++numSerialPatternMatch;
999 int AMDGPUCFGStructurizer::ifPatternMatch(MachineBasicBlock *MBB) {
1001 if (MBB->succ_size() != 2)
1003 if (hasBackEdge(MBB))
1005 MachineInstr *BranchMI = getNormalBlockBranchInstr(MBB);
1009 assert(isCondBranch(BranchMI));
1012 MachineBasicBlock *TrueMBB = getTrueBranch(BranchMI);
1013 NumMatch += serialPatternMatch(TrueMBB);
1014 NumMatch += ifPatternMatch(TrueMBB);
1015 MachineBasicBlock *FalseMBB = getFalseBranch(MBB, BranchMI);
1016 NumMatch += serialPatternMatch(FalseMBB);
1017 NumMatch += ifPatternMatch(FalseMBB);
1018 MachineBasicBlock *LandBlk;
1021 assert (!TrueMBB->succ_empty() || !FalseMBB->succ_empty());
1023 if (TrueMBB->succ_size() == 1 && FalseMBB->succ_size() == 1
1024 && *TrueMBB->succ_begin() == *FalseMBB->succ_begin()) {
1026 LandBlk = *TrueMBB->succ_begin();
1027 } else if (TrueMBB->succ_size() == 1 && *TrueMBB->succ_begin() == FalseMBB) {
1028 // Triangle pattern, false is empty
1031 } else if (FalseMBB->succ_size() == 1
1032 && *FalseMBB->succ_begin() == TrueMBB) {
1033 // Triangle pattern, true is empty
1034 // We reverse the predicate to make a triangle, empty false pattern;
1035 std::swap(TrueMBB, FalseMBB);
1036 reversePredicateSetter(MBB->end());
1039 } else if (FalseMBB->succ_size() == 1
1040 && isSameloopDetachedContbreak(TrueMBB, FalseMBB)) {
1041 LandBlk = *FalseMBB->succ_begin();
1042 } else if (TrueMBB->succ_size() == 1
1043 && isSameloopDetachedContbreak(FalseMBB, TrueMBB)) {
1044 LandBlk = *TrueMBB->succ_begin();
1046 return NumMatch + handleJumpintoIf(MBB, TrueMBB, FalseMBB);
1049 // improveSimpleJumpinfoIf can handle the case where landBlk == NULL but the
1050 // new BB created for landBlk==NULL may introduce new challenge to the
1051 // reduction process.
1053 ((TrueMBB && TrueMBB->pred_size() > 1)
1054 || (FalseMBB && FalseMBB->pred_size() > 1))) {
1055 Cloned += improveSimpleJumpintoIf(MBB, TrueMBB, FalseMBB, &LandBlk);
1058 if (TrueMBB && TrueMBB->pred_size() > 1) {
1059 TrueMBB = cloneBlockForPredecessor(TrueMBB, MBB);
1063 if (FalseMBB && FalseMBB->pred_size() > 1) {
1064 FalseMBB = cloneBlockForPredecessor(FalseMBB, MBB);
1068 mergeIfthenelseBlock(BranchMI, MBB, TrueMBB, FalseMBB, LandBlk);
1070 ++numIfPatternMatch;
1072 numClonedBlock += Cloned;
1074 return 1 + Cloned + NumMatch;
1077 int AMDGPUCFGStructurizer::loopendPatternMatch() {
1078 std::vector<MachineLoop *> NestedLoops;
1079 for (MachineLoopInfo::iterator It = MLI->begin(), E = MLI->end(); It != E;
1081 for (MachineLoop *ML : depth_first(*It))
1082 NestedLoops.push_back(ML);
1084 if (NestedLoops.size() == 0)
1087 // Process nested loop outside->inside, so "continue" to a outside loop won't
1088 // be mistaken as "break" of the current loop.
1090 for (std::vector<MachineLoop *>::reverse_iterator It = NestedLoops.rbegin(),
1091 E = NestedLoops.rend(); It != E; ++It) {
1092 MachineLoop *ExaminedLoop = *It;
1093 if (ExaminedLoop->getNumBlocks() == 0 || Visited[ExaminedLoop])
1095 DEBUG(dbgs() << "Processing:\n"; ExaminedLoop->dump(););
1096 int NumBreak = mergeLoop(ExaminedLoop);
1104 int AMDGPUCFGStructurizer::mergeLoop(MachineLoop *LoopRep) {
1105 MachineBasicBlock *LoopHeader = LoopRep->getHeader();
1106 MBBVector ExitingMBBs;
1107 LoopRep->getExitingBlocks(ExitingMBBs);
1108 assert(!ExitingMBBs.empty() && "Infinite Loop not supported");
1109 DEBUG(dbgs() << "Loop has " << ExitingMBBs.size() << " exiting blocks\n";);
1110 // We assume a single ExitBlk
1112 LoopRep->getExitBlocks(ExitBlks);
1113 SmallPtrSet<MachineBasicBlock *, 2> ExitBlkSet;
1114 for (unsigned i = 0, e = ExitBlks.size(); i < e; ++i)
1115 ExitBlkSet.insert(ExitBlks[i]);
1116 assert(ExitBlkSet.size() == 1);
1117 MachineBasicBlock *ExitBlk = *ExitBlks.begin();
1118 assert(ExitBlk && "Loop has several exit block");
1119 MBBVector LatchBlks;
1120 typedef GraphTraits<Inverse<MachineBasicBlock*> > InvMBBTraits;
1121 InvMBBTraits::ChildIteratorType PI = InvMBBTraits::child_begin(LoopHeader),
1122 PE = InvMBBTraits::child_end(LoopHeader);
1123 for (; PI != PE; PI++) {
1124 if (LoopRep->contains(*PI))
1125 LatchBlks.push_back(*PI);
1128 for (unsigned i = 0, e = ExitingMBBs.size(); i < e; ++i)
1129 mergeLoopbreakBlock(ExitingMBBs[i], ExitBlk);
1130 for (unsigned i = 0, e = LatchBlks.size(); i < e; ++i)
1131 settleLoopcontBlock(LatchBlks[i], LoopHeader);
1135 Match += serialPatternMatch(LoopHeader);
1136 Match += ifPatternMatch(LoopHeader);
1137 } while (Match > 0);
1138 mergeLooplandBlock(LoopHeader, ExitBlk);
1139 MachineLoop *ParentLoop = LoopRep->getParentLoop();
1141 MLI->changeLoopFor(LoopHeader, ParentLoop);
1143 MLI->removeBlock(LoopHeader);
1144 Visited[LoopRep] = true;
1148 int AMDGPUCFGStructurizer::loopcontPatternMatch(MachineLoop *LoopRep,
1149 MachineBasicBlock *LoopHeader) {
1151 SmallVector<MachineBasicBlock *, DEFAULT_VEC_SLOTS> ContMBB;
1152 typedef GraphTraits<Inverse<MachineBasicBlock *> > GTIM;
1153 GTIM::ChildIteratorType It = GTIM::child_begin(LoopHeader),
1154 E = GTIM::child_end(LoopHeader);
1155 for (; It != E; ++It) {
1156 MachineBasicBlock *MBB = *It;
1157 if (LoopRep->contains(MBB)) {
1158 handleLoopcontBlock(MBB, MLI->getLoopFor(MBB),
1159 LoopHeader, LoopRep);
1160 ContMBB.push_back(MBB);
1165 for (SmallVectorImpl<MachineBasicBlock *>::iterator It = ContMBB.begin(),
1166 E = ContMBB.end(); It != E; ++It) {
1167 (*It)->removeSuccessor(LoopHeader);
1170 numLoopcontPatternMatch += NumCont;
1176 bool AMDGPUCFGStructurizer::isSameloopDetachedContbreak(
1177 MachineBasicBlock *Src1MBB, MachineBasicBlock *Src2MBB) {
1178 if (Src1MBB->succ_size() == 0) {
1179 MachineLoop *LoopRep = MLI->getLoopFor(Src1MBB);
1180 if (LoopRep&& LoopRep == MLI->getLoopFor(Src2MBB)) {
1181 MachineBasicBlock *&TheEntry = LLInfoMap[LoopRep];
1184 dbgs() << "isLoopContBreakBlock yes src1 = BB"
1185 << Src1MBB->getNumber()
1186 << " src2 = BB" << Src2MBB->getNumber() << "\n";
1195 int AMDGPUCFGStructurizer::handleJumpintoIf(MachineBasicBlock *HeadMBB,
1196 MachineBasicBlock *TrueMBB, MachineBasicBlock *FalseMBB) {
1197 int Num = handleJumpintoIfImp(HeadMBB, TrueMBB, FalseMBB);
1200 dbgs() << "handleJumpintoIf swap trueBlk and FalseBlk" << "\n";
1202 Num = handleJumpintoIfImp(HeadMBB, FalseMBB, TrueMBB);
1207 int AMDGPUCFGStructurizer::handleJumpintoIfImp(MachineBasicBlock *HeadMBB,
1208 MachineBasicBlock *TrueMBB, MachineBasicBlock *FalseMBB) {
1210 MachineBasicBlock *DownBlk;
1212 //trueBlk could be the common post dominator
1216 dbgs() << "handleJumpintoIfImp head = BB" << HeadMBB->getNumber()
1217 << " true = BB" << TrueMBB->getNumber()
1218 << ", numSucc=" << TrueMBB->succ_size()
1219 << " false = BB" << FalseMBB->getNumber() << "\n";
1224 dbgs() << "check down = BB" << DownBlk->getNumber();
1227 if (singlePathTo(FalseMBB, DownBlk) == SinglePath_InPath) {
1229 dbgs() << " working\n";
1232 Num += cloneOnSideEntryTo(HeadMBB, TrueMBB, DownBlk);
1233 Num += cloneOnSideEntryTo(HeadMBB, FalseMBB, DownBlk);
1235 numClonedBlock += Num;
1236 Num += serialPatternMatch(*HeadMBB->succ_begin());
1237 Num += serialPatternMatch(*std::next(HeadMBB->succ_begin()));
1238 Num += ifPatternMatch(HeadMBB);
1244 dbgs() << " not working\n";
1246 DownBlk = (DownBlk->succ_size() == 1) ? (*DownBlk->succ_begin()) : nullptr;
1247 } // walk down the postDomTree
1252 void AMDGPUCFGStructurizer::showImproveSimpleJumpintoIf(
1253 MachineBasicBlock *HeadMBB, MachineBasicBlock *TrueMBB,
1254 MachineBasicBlock *FalseMBB, MachineBasicBlock *LandMBB, bool Detail) {
1255 dbgs() << "head = BB" << HeadMBB->getNumber()
1256 << " size = " << HeadMBB->size();
1259 HeadMBB->print(dbgs());
1264 dbgs() << ", true = BB" << TrueMBB->getNumber() << " size = "
1265 << TrueMBB->size() << " numPred = " << TrueMBB->pred_size();
1268 TrueMBB->print(dbgs());
1273 dbgs() << ", false = BB" << FalseMBB->getNumber() << " size = "
1274 << FalseMBB->size() << " numPred = " << FalseMBB->pred_size();
1277 FalseMBB->print(dbgs());
1282 dbgs() << ", land = BB" << LandMBB->getNumber() << " size = "
1283 << LandMBB->size() << " numPred = " << LandMBB->pred_size();
1286 LandMBB->print(dbgs());
1294 int AMDGPUCFGStructurizer::improveSimpleJumpintoIf(MachineBasicBlock *HeadMBB,
1295 MachineBasicBlock *TrueMBB, MachineBasicBlock *FalseMBB,
1296 MachineBasicBlock **LandMBBPtr) {
1297 bool MigrateTrue = false;
1298 bool MigrateFalse = false;
1300 MachineBasicBlock *LandBlk = *LandMBBPtr;
1302 assert((!TrueMBB || TrueMBB->succ_size() <= 1)
1303 && (!FalseMBB || FalseMBB->succ_size() <= 1));
1305 if (TrueMBB == FalseMBB)
1308 MigrateTrue = needMigrateBlock(TrueMBB);
1309 MigrateFalse = needMigrateBlock(FalseMBB);
1311 if (!MigrateTrue && !MigrateFalse)
1314 // If we need to migrate either trueBlk and falseBlk, migrate the rest that
1315 // have more than one predecessors. without doing this, its predecessor
1316 // rather than headBlk will have undefined value in initReg.
1317 if (!MigrateTrue && TrueMBB && TrueMBB->pred_size() > 1)
1319 if (!MigrateFalse && FalseMBB && FalseMBB->pred_size() > 1)
1320 MigrateFalse = true;
1323 dbgs() << "before improveSimpleJumpintoIf: ";
1324 showImproveSimpleJumpintoIf(HeadMBB, TrueMBB, FalseMBB, LandBlk, 0);
1327 // org: headBlk => if () {trueBlk} else {falseBlk} => landBlk
1329 // new: headBlk => if () {initReg = 1; org trueBlk branch} else
1330 // {initReg = 0; org falseBlk branch }
1331 // => landBlk => if (initReg) {org trueBlk} else {org falseBlk}
1333 // if landBlk->pred_size() > 2, put the about if-else inside
1334 // if (initReg !=2) {...}
1336 // add initReg = initVal to headBlk
1338 const TargetRegisterClass * I32RC = TRI->getCFGStructurizerRegClass(MVT::i32);
1339 if (!MigrateTrue || !MigrateFalse) {
1340 // XXX: We have an opportunity here to optimize the "branch into if" case
1341 // here. Branch into if looks like this:
1344 // diamond_head branch_from
1346 // diamond_false diamond_true
1350 // The diamond_head block begins the "if" and the diamond_true block
1351 // is the block being "branched into".
1353 // If MigrateTrue is true, then TrueBB is the block being "branched into"
1354 // and if MigrateFalse is true, then FalseBB is the block being
1357 // Here is the pseudo code for how I think the optimization should work:
1358 // 1. Insert MOV GPR0, 0 before the branch instruction in diamond_head.
1359 // 2. Insert MOV GPR0, 1 before the branch instruction in branch_from.
1360 // 3. Move the branch instruction from diamond_head into its own basic
1361 // block (new_block).
1362 // 4. Add an unconditional branch from diamond_head to new_block
1363 // 5. Replace the branch instruction in branch_from with an unconditional
1364 // branch to new_block. If branch_from has multiple predecessors, then
1365 // we need to replace the True/False block in the branch
1366 // instruction instead of replacing it.
1367 // 6. Change the condition of the branch instruction in new_block from
1368 // COND to (COND || GPR0)
1370 // In order insert these MOV instruction, we will need to use the
1371 // RegisterScavenger. Usually liveness stops being tracked during
1372 // the late machine optimization passes, however if we implement
1373 // bool TargetRegisterInfo::requiresRegisterScavenging(
1374 // const MachineFunction &MF)
1375 // and have it return true, liveness will be tracked correctly
1376 // by generic optimization passes. We will also need to make sure that
1377 // all of our target-specific passes that run after regalloc and before
1378 // the CFGStructurizer track liveness and we will need to modify this pass
1379 // to correctly track liveness.
1381 // After the above changes, the new CFG should look like this:
1384 // diamond_head branch_from
1388 // diamond_false diamond_true
1392 // Without this optimization, we are forced to duplicate the diamond_true
1393 // block and we will end up with a CFG like this:
1397 // diamond_head branch_from
1399 // diamond_false diamond_true diamond_true (duplicate)
1401 // done --------------------|
1403 // Duplicating diamond_true can be very costly especially if it has a
1404 // lot of instructions.
1410 bool LandBlkHasOtherPred = (LandBlk->pred_size() > 2);
1412 //insert AMDGPU::ENDIF to avoid special case "input landBlk == NULL"
1413 MachineBasicBlock::iterator I = insertInstrBefore(LandBlk, AMDGPU::ENDIF);
1415 if (LandBlkHasOtherPred) {
1416 llvm_unreachable("Extra register needed to handle CFG");
1417 unsigned CmpResReg =
1418 HeadMBB->getParent()->getRegInfo().createVirtualRegister(I32RC);
1419 llvm_unreachable("Extra compare instruction needed to handle CFG");
1420 insertCondBranchBefore(LandBlk, I, AMDGPU::IF_PREDICATE_SET,
1421 CmpResReg, DebugLoc());
1424 // XXX: We are running this after RA, so creating virtual registers will
1425 // cause an assertion failure in the PostRA scheduling pass.
1427 HeadMBB->getParent()->getRegInfo().createVirtualRegister(I32RC);
1428 insertCondBranchBefore(LandBlk, I, AMDGPU::IF_PREDICATE_SET, InitReg,
1432 migrateInstruction(TrueMBB, LandBlk, I);
1433 // need to uncondionally insert the assignment to ensure a path from its
1434 // predecessor rather than headBlk has valid value in initReg if
1436 llvm_unreachable("Extra register needed to handle CFG");
1438 insertInstrBefore(I, AMDGPU::ELSE);
1441 migrateInstruction(FalseMBB, LandBlk, I);
1442 // need to uncondionally insert the assignment to ensure a path from its
1443 // predecessor rather than headBlk has valid value in initReg if
1445 llvm_unreachable("Extra register needed to handle CFG");
1448 if (LandBlkHasOtherPred) {
1450 insertInstrBefore(I, AMDGPU::ENDIF);
1452 // put initReg = 2 to other predecessors of landBlk
1453 for (MachineBasicBlock::pred_iterator PI = LandBlk->pred_begin(),
1454 PE = LandBlk->pred_end(); PI != PE; ++PI) {
1455 MachineBasicBlock *MBB = *PI;
1456 if (MBB != TrueMBB && MBB != FalseMBB)
1457 llvm_unreachable("Extra register needed to handle CFG");
1461 dbgs() << "result from improveSimpleJumpintoIf: ";
1462 showImproveSimpleJumpintoIf(HeadMBB, TrueMBB, FalseMBB, LandBlk, 0);
1466 *LandMBBPtr = LandBlk;
1471 void AMDGPUCFGStructurizer::handleLoopcontBlock(MachineBasicBlock *ContingMBB,
1472 MachineLoop *ContingLoop, MachineBasicBlock *ContMBB,
1473 MachineLoop *ContLoop) {
1474 DEBUG(dbgs() << "loopcontPattern cont = BB" << ContingMBB->getNumber()
1475 << " header = BB" << ContMBB->getNumber() << "\n";
1476 dbgs() << "Trying to continue loop-depth = "
1477 << getLoopDepth(ContLoop)
1478 << " from loop-depth = " << getLoopDepth(ContingLoop) << "\n";);
1479 settleLoopcontBlock(ContingMBB, ContMBB);
1482 void AMDGPUCFGStructurizer::mergeSerialBlock(MachineBasicBlock *DstMBB,
1483 MachineBasicBlock *SrcMBB) {
1485 dbgs() << "serialPattern BB" << DstMBB->getNumber()
1486 << " <= BB" << SrcMBB->getNumber() << "\n";
1488 DstMBB->splice(DstMBB->end(), SrcMBB, SrcMBB->begin(), SrcMBB->end());
1490 DstMBB->removeSuccessor(SrcMBB);
1491 cloneSuccessorList(DstMBB, SrcMBB);
1493 removeSuccessor(SrcMBB);
1494 MLI->removeBlock(SrcMBB);
1495 retireBlock(SrcMBB);
1498 void AMDGPUCFGStructurizer::mergeIfthenelseBlock(MachineInstr *BranchMI,
1499 MachineBasicBlock *MBB, MachineBasicBlock *TrueMBB,
1500 MachineBasicBlock *FalseMBB, MachineBasicBlock *LandMBB) {
1503 dbgs() << "ifPattern BB" << MBB->getNumber();
1506 dbgs() << "BB" << TrueMBB->getNumber();
1508 dbgs() << " } else ";
1511 dbgs() << "BB" << FalseMBB->getNumber();
1514 dbgs() << "landBlock: ";
1518 dbgs() << "BB" << LandMBB->getNumber();
1523 int OldOpcode = BranchMI->getOpcode();
1524 DebugLoc BranchDL = BranchMI->getDebugLoc();
1534 MachineBasicBlock::iterator I = BranchMI;
1535 insertCondBranchBefore(I, getBranchNzeroOpcode(OldOpcode),
1539 MBB->splice(I, TrueMBB, TrueMBB->begin(), TrueMBB->end());
1540 MBB->removeSuccessor(TrueMBB);
1541 if (LandMBB && TrueMBB->succ_size()!=0)
1542 TrueMBB->removeSuccessor(LandMBB);
1543 retireBlock(TrueMBB);
1544 MLI->removeBlock(TrueMBB);
1548 insertInstrBefore(I, AMDGPU::ELSE);
1549 MBB->splice(I, FalseMBB, FalseMBB->begin(),
1551 MBB->removeSuccessor(FalseMBB);
1552 if (LandMBB && FalseMBB->succ_size() != 0)
1553 FalseMBB->removeSuccessor(LandMBB);
1554 retireBlock(FalseMBB);
1555 MLI->removeBlock(FalseMBB);
1557 insertInstrBefore(I, AMDGPU::ENDIF);
1559 BranchMI->eraseFromParent();
1561 if (LandMBB && TrueMBB && FalseMBB)
1562 MBB->addSuccessor(LandMBB);
1566 void AMDGPUCFGStructurizer::mergeLooplandBlock(MachineBasicBlock *DstBlk,
1567 MachineBasicBlock *LandMBB) {
1568 DEBUG(dbgs() << "loopPattern header = BB" << DstBlk->getNumber()
1569 << " land = BB" << LandMBB->getNumber() << "\n";);
1571 insertInstrBefore(DstBlk, AMDGPU::WHILELOOP, DebugLoc());
1572 insertInstrEnd(DstBlk, AMDGPU::ENDLOOP, DebugLoc());
1573 DstBlk->addSuccessor(LandMBB);
1574 DstBlk->removeSuccessor(DstBlk);
1578 void AMDGPUCFGStructurizer::mergeLoopbreakBlock(MachineBasicBlock *ExitingMBB,
1579 MachineBasicBlock *LandMBB) {
1580 DEBUG(dbgs() << "loopbreakPattern exiting = BB" << ExitingMBB->getNumber()
1581 << " land = BB" << LandMBB->getNumber() << "\n";);
1582 MachineInstr *BranchMI = getLoopendBlockBranchInstr(ExitingMBB);
1583 assert(BranchMI && isCondBranch(BranchMI));
1584 DebugLoc DL = BranchMI->getDebugLoc();
1585 MachineBasicBlock *TrueBranch = getTrueBranch(BranchMI);
1586 MachineBasicBlock::iterator I = BranchMI;
1587 if (TrueBranch != LandMBB)
1588 reversePredicateSetter(I);
1589 insertCondBranchBefore(ExitingMBB, I, AMDGPU::IF_PREDICATE_SET, AMDGPU::PREDICATE_BIT, DL);
1590 insertInstrBefore(I, AMDGPU::BREAK);
1591 insertInstrBefore(I, AMDGPU::ENDIF);
1592 //now branchInst can be erase safely
1593 BranchMI->eraseFromParent();
1594 //now take care of successors, retire blocks
1595 ExitingMBB->removeSuccessor(LandMBB);
1598 void AMDGPUCFGStructurizer::settleLoopcontBlock(MachineBasicBlock *ContingMBB,
1599 MachineBasicBlock *ContMBB) {
1600 DEBUG(dbgs() << "settleLoopcontBlock conting = BB"
1601 << ContingMBB->getNumber()
1602 << ", cont = BB" << ContMBB->getNumber() << "\n";);
1604 MachineInstr *MI = getLoopendBlockBranchInstr(ContingMBB);
1606 assert(isCondBranch(MI));
1607 MachineBasicBlock::iterator I = MI;
1608 MachineBasicBlock *TrueBranch = getTrueBranch(MI);
1609 int OldOpcode = MI->getOpcode();
1610 DebugLoc DL = MI->getDebugLoc();
1612 bool UseContinueLogical = ((&*ContingMBB->rbegin()) == MI);
1614 if (UseContinueLogical == false) {
1616 TrueBranch == ContMBB ? getBranchNzeroOpcode(OldOpcode) :
1617 getBranchZeroOpcode(OldOpcode);
1618 insertCondBranchBefore(I, BranchOpcode, DL);
1619 // insertEnd to ensure phi-moves, if exist, go before the continue-instr.
1620 insertInstrEnd(ContingMBB, AMDGPU::CONTINUE, DL);
1621 insertInstrEnd(ContingMBB, AMDGPU::ENDIF, DL);
1624 TrueBranch == ContMBB ? getContinueNzeroOpcode(OldOpcode) :
1625 getContinueZeroOpcode(OldOpcode);
1626 insertCondBranchBefore(I, BranchOpcode, DL);
1629 MI->eraseFromParent();
1631 // if we've arrived here then we've already erased the branch instruction
1632 // travel back up the basic block to see the last reference of our debug
1633 // location we've just inserted that reference here so it should be
1634 // representative insertEnd to ensure phi-moves, if exist, go before the
1636 insertInstrEnd(ContingMBB, AMDGPU::CONTINUE,
1637 getLastDebugLocInBB(ContingMBB));
1641 int AMDGPUCFGStructurizer::cloneOnSideEntryTo(MachineBasicBlock *PreMBB,
1642 MachineBasicBlock *SrcMBB, MachineBasicBlock *DstMBB) {
1644 assert(PreMBB->isSuccessor(SrcMBB));
1645 while (SrcMBB && SrcMBB != DstMBB) {
1646 assert(SrcMBB->succ_size() == 1);
1647 if (SrcMBB->pred_size() > 1) {
1648 SrcMBB = cloneBlockForPredecessor(SrcMBB, PreMBB);
1653 SrcMBB = *SrcMBB->succ_begin();
1660 AMDGPUCFGStructurizer::cloneBlockForPredecessor(MachineBasicBlock *MBB,
1661 MachineBasicBlock *PredMBB) {
1662 assert(PredMBB->isSuccessor(MBB) &&
1663 "succBlk is not a prececessor of curBlk");
1665 MachineBasicBlock *CloneMBB = clone(MBB); //clone instructions
1666 replaceInstrUseOfBlockWith(PredMBB, MBB, CloneMBB);
1667 //srcBlk, oldBlk, newBlk
1669 PredMBB->removeSuccessor(MBB);
1670 PredMBB->addSuccessor(CloneMBB);
1672 // add all successor to cloneBlk
1673 cloneSuccessorList(CloneMBB, MBB);
1675 numClonedInstr += MBB->size();
1678 dbgs() << "Cloned block: " << "BB"
1679 << MBB->getNumber() << "size " << MBB->size() << "\n";
1682 SHOWNEWBLK(CloneMBB, "result of Cloned block: ");
1687 void AMDGPUCFGStructurizer::migrateInstruction(MachineBasicBlock *SrcMBB,
1688 MachineBasicBlock *DstMBB, MachineBasicBlock::iterator I) {
1689 MachineBasicBlock::iterator SpliceEnd;
1690 //look for the input branchinstr, not the AMDGPU branchinstr
1691 MachineInstr *BranchMI = getNormalBlockBranchInstr(SrcMBB);
1694 dbgs() << "migrateInstruction don't see branch instr\n" ;
1696 SpliceEnd = SrcMBB->end();
1699 dbgs() << "migrateInstruction see branch instr\n" ;
1702 SpliceEnd = BranchMI;
1705 dbgs() << "migrateInstruction before splice dstSize = " << DstMBB->size()
1706 << "srcSize = " << SrcMBB->size() << "\n";
1709 //splice insert before insertPos
1710 DstMBB->splice(I, SrcMBB, SrcMBB->begin(), SpliceEnd);
1713 dbgs() << "migrateInstruction after splice dstSize = " << DstMBB->size()
1714 << "srcSize = " << SrcMBB->size() << "\n";
1719 AMDGPUCFGStructurizer::normalizeInfiniteLoopExit(MachineLoop* LoopRep) {
1720 MachineBasicBlock *LoopHeader = LoopRep->getHeader();
1721 MachineBasicBlock *LoopLatch = LoopRep->getLoopLatch();
1722 const TargetRegisterClass * I32RC = TRI->getCFGStructurizerRegClass(MVT::i32);
1724 if (!LoopHeader || !LoopLatch)
1726 MachineInstr *BranchMI = getLoopendBlockBranchInstr(LoopLatch);
1727 // Is LoopRep an infinite loop ?
1728 if (!BranchMI || !isUncondBranch(BranchMI))
1731 MachineBasicBlock *DummyExitBlk = FuncRep->CreateMachineBasicBlock();
1732 FuncRep->push_back(DummyExitBlk); //insert to function
1733 SHOWNEWBLK(DummyExitBlk, "DummyExitBlock to normalize infiniteLoop: ");
1734 DEBUG(dbgs() << "Old branch instr: " << *BranchMI << "\n";);
1735 MachineBasicBlock::iterator I = BranchMI;
1736 unsigned ImmReg = FuncRep->getRegInfo().createVirtualRegister(I32RC);
1737 llvm_unreachable("Extra register needed to handle CFG");
1738 MachineInstr *NewMI = insertInstrBefore(I, AMDGPU::BRANCH_COND_i32);
1739 MachineInstrBuilder MIB(*FuncRep, NewMI);
1740 MIB.addMBB(LoopHeader);
1741 MIB.addReg(ImmReg, false);
1742 SHOWNEWINSTR(NewMI);
1743 BranchMI->eraseFromParent();
1744 LoopLatch->addSuccessor(DummyExitBlk);
1746 return DummyExitBlk;
1749 void AMDGPUCFGStructurizer::removeUnconditionalBranch(MachineBasicBlock *MBB) {
1750 MachineInstr *BranchMI;
1752 // I saw two unconditional branch in one basic block in example
1753 // test_fc_do_while_or.c need to fix the upstream on this to remove the loop.
1754 while ((BranchMI = getLoopendBlockBranchInstr(MBB))
1755 && isUncondBranch(BranchMI)) {
1756 DEBUG(dbgs() << "Removing uncond branch instr"; BranchMI->dump(););
1757 BranchMI->eraseFromParent();
1761 void AMDGPUCFGStructurizer::removeRedundantConditionalBranch(
1762 MachineBasicBlock *MBB) {
1763 if (MBB->succ_size() != 2)
1765 MachineBasicBlock *MBB1 = *MBB->succ_begin();
1766 MachineBasicBlock *MBB2 = *std::next(MBB->succ_begin());
1770 MachineInstr *BranchMI = getNormalBlockBranchInstr(MBB);
1771 assert(BranchMI && isCondBranch(BranchMI));
1772 DEBUG(dbgs() << "Removing unneeded cond branch instr"; BranchMI->dump(););
1773 BranchMI->eraseFromParent();
1774 SHOWNEWBLK(MBB1, "Removing redundant successor");
1775 MBB->removeSuccessor(MBB1);
1778 void AMDGPUCFGStructurizer::addDummyExitBlock(
1779 SmallVectorImpl<MachineBasicBlock*> &RetMBB) {
1780 MachineBasicBlock *DummyExitBlk = FuncRep->CreateMachineBasicBlock();
1781 FuncRep->push_back(DummyExitBlk); //insert to function
1782 insertInstrEnd(DummyExitBlk, AMDGPU::RETURN);
1784 for (SmallVectorImpl<MachineBasicBlock *>::iterator It = RetMBB.begin(),
1785 E = RetMBB.end(); It != E; ++It) {
1786 MachineBasicBlock *MBB = *It;
1787 MachineInstr *MI = getReturnInstr(MBB);
1789 MI->eraseFromParent();
1790 MBB->addSuccessor(DummyExitBlk);
1792 dbgs() << "Add dummyExitBlock to BB" << MBB->getNumber()
1796 SHOWNEWBLK(DummyExitBlk, "DummyExitBlock: ");
1799 void AMDGPUCFGStructurizer::removeSuccessor(MachineBasicBlock *MBB) {
1800 while (MBB->succ_size())
1801 MBB->removeSuccessor(*MBB->succ_begin());
1804 void AMDGPUCFGStructurizer::recordSccnum(MachineBasicBlock *MBB,
1806 BlockInformation *&srcBlkInfo = BlockInfoMap[MBB];
1808 srcBlkInfo = new BlockInformation();
1809 srcBlkInfo->SccNum = SccNum;
1812 void AMDGPUCFGStructurizer::retireBlock(MachineBasicBlock *MBB) {
1814 dbgs() << "Retiring BB" << MBB->getNumber() << "\n";
1817 BlockInformation *&SrcBlkInfo = BlockInfoMap[MBB];
1820 SrcBlkInfo = new BlockInformation();
1822 SrcBlkInfo->IsRetired = true;
1823 assert(MBB->succ_size() == 0 && MBB->pred_size() == 0
1824 && "can't retire block yet");
1827 void AMDGPUCFGStructurizer::setLoopLandBlock(MachineLoop *loopRep,
1828 MachineBasicBlock *MBB) {
1829 MachineBasicBlock *&TheEntry = LLInfoMap[loopRep];
1831 MBB = FuncRep->CreateMachineBasicBlock();
1832 FuncRep->push_back(MBB); //insert to function
1833 SHOWNEWBLK(MBB, "DummyLandingBlock for loop without break: ");
1837 dbgs() << "setLoopLandBlock loop-header = BB"
1838 << loopRep->getHeader()->getNumber()
1839 << " landing-block = BB" << MBB->getNumber() << "\n";
1844 AMDGPUCFGStructurizer::findNearestCommonPostDom(MachineBasicBlock *MBB1,
1845 MachineBasicBlock *MBB2) {
1847 if (PDT->dominates(MBB1, MBB2))
1849 if (PDT->dominates(MBB2, MBB1))
1852 MachineDomTreeNode *Node1 = PDT->getNode(MBB1);
1853 MachineDomTreeNode *Node2 = PDT->getNode(MBB2);
1855 // Handle newly cloned node.
1856 if (!Node1 && MBB1->succ_size() == 1)
1857 return findNearestCommonPostDom(*MBB1->succ_begin(), MBB2);
1858 if (!Node2 && MBB2->succ_size() == 1)
1859 return findNearestCommonPostDom(MBB1, *MBB2->succ_begin());
1861 if (!Node1 || !Node2)
1864 Node1 = Node1->getIDom();
1866 if (PDT->dominates(Node1, Node2))
1867 return Node1->getBlock();
1868 Node1 = Node1->getIDom();
1875 AMDGPUCFGStructurizer::findNearestCommonPostDom(
1876 std::set<MachineBasicBlock *> &MBBs) {
1877 MachineBasicBlock *CommonDom;
1878 std::set<MachineBasicBlock *>::const_iterator It = MBBs.begin();
1879 std::set<MachineBasicBlock *>::const_iterator E = MBBs.end();
1880 for (CommonDom = *It; It != E && CommonDom; ++It) {
1881 MachineBasicBlock *MBB = *It;
1882 if (MBB != CommonDom)
1883 CommonDom = findNearestCommonPostDom(MBB, CommonDom);
1887 dbgs() << "Common post dominator for exit blocks is ";
1889 dbgs() << "BB" << CommonDom->getNumber() << "\n";
1897 char AMDGPUCFGStructurizer::ID = 0;
1899 } // end anonymous namespace
1902 INITIALIZE_PASS_BEGIN(AMDGPUCFGStructurizer, "amdgpustructurizer",
1903 "AMDGPU CFG Structurizer", false, false)
1904 INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
1905 INITIALIZE_PASS_DEPENDENCY(MachinePostDominatorTree)
1906 INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo)
1907 INITIALIZE_PASS_END(AMDGPUCFGStructurizer, "amdgpustructurizer",
1908 "AMDGPU CFG Structurizer", false, false)
1910 FunctionPass *llvm::createAMDGPUCFGStructurizerPass() {
1911 return new AMDGPUCFGStructurizer();