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 //==-----------------------------------------------------------------------===//
14 #include "AMDGPUInstrInfo.h"
15 #include "R600InstrInfo.h"
16 #include "AMDGPUSubtarget.h"
17 #include "llvm/ADT/DepthFirstIterator.h"
18 #include "llvm/ADT/SCCIterator.h"
19 #include "llvm/ADT/SmallVector.h"
20 #include "llvm/ADT/Statistic.h"
21 #include "llvm/CodeGen/MachineDominators.h"
22 #include "llvm/CodeGen/MachineFunction.h"
23 #include "llvm/CodeGen/MachineFunctionAnalysis.h"
24 #include "llvm/CodeGen/MachineFunctionPass.h"
25 #include "llvm/CodeGen/MachineInstrBuilder.h"
26 #include "llvm/CodeGen/MachineJumpTableInfo.h"
27 #include "llvm/CodeGen/MachineLoopInfo.h"
28 #include "llvm/CodeGen/MachinePostDominators.h"
29 #include "llvm/CodeGen/MachineRegisterInfo.h"
30 #include "llvm/IR/Dominators.h"
31 #include "llvm/Support/Debug.h"
32 #include "llvm/Support/raw_ostream.h"
33 #include "llvm/Target/TargetInstrInfo.h"
34 #include "llvm/Target/TargetMachine.h"
38 #define DEBUG_TYPE "structcfg"
40 #define DEFAULT_VEC_SLOTS 8
44 //===----------------------------------------------------------------------===//
46 // Statistics for CFGStructurizer.
48 //===----------------------------------------------------------------------===//
50 STATISTIC(numSerialPatternMatch, "CFGStructurizer number of serial pattern "
52 STATISTIC(numIfPatternMatch, "CFGStructurizer number of if pattern "
54 STATISTIC(numLoopcontPatternMatch, "CFGStructurizer number of loop-continue "
56 STATISTIC(numClonedBlock, "CFGStructurizer cloned blocks");
57 STATISTIC(numClonedInstr, "CFGStructurizer cloned instructions");
60 void initializeAMDGPUCFGStructurizerPass(PassRegistry&);
63 //===----------------------------------------------------------------------===//
65 // Miscellaneous utility for CFGStructurizer.
67 //===----------------------------------------------------------------------===//
69 #define SHOWNEWINSTR(i) \
70 DEBUG(dbgs() << "New instr: " << *i << "\n");
72 #define SHOWNEWBLK(b, msg) \
74 dbgs() << msg << "BB" << b->getNumber() << "size " << b->size(); \
78 #define SHOWBLK_DETAIL(b, msg) \
81 dbgs() << msg << "BB" << b->getNumber() << "size " << b->size(); \
87 #define INVALIDSCCNUM -1
90 void ReverseVector(SmallVectorImpl<NodeT *> &Src) {
91 size_t sz = Src.size();
92 for (size_t i = 0; i < sz/2; ++i) {
94 Src[i] = Src[sz - i - 1];
99 } // end anonymous namespace
101 //===----------------------------------------------------------------------===//
103 // supporting data structure for CFGStructurizer
105 //===----------------------------------------------------------------------===//
110 class BlockInformation {
114 BlockInformation() : IsRetired(false), SccNum(INVALIDSCCNUM) {}
117 } // end anonymous namespace
119 //===----------------------------------------------------------------------===//
123 //===----------------------------------------------------------------------===//
126 class AMDGPUCFGStructurizer : public MachineFunctionPass {
128 typedef SmallVector<MachineBasicBlock *, 32> MBBVector;
129 typedef std::map<MachineBasicBlock *, BlockInformation *> MBBInfoMap;
130 typedef std::map<MachineLoop *, MachineBasicBlock *> LoopLandInfoMap;
134 SinglePath_InPath = 1,
135 SinglePath_NotInPath = 2
140 AMDGPUCFGStructurizer() :
141 MachineFunctionPass(ID), TII(nullptr), TRI(nullptr) {
142 initializeAMDGPUCFGStructurizerPass(*PassRegistry::getPassRegistry());
145 const char *getPassName() const override {
146 return "AMDGPU Control Flow Graph structurizer Pass";
149 void getAnalysisUsage(AnalysisUsage &AU) const override {
150 AU.addPreserved<MachineFunctionAnalysis>();
151 AU.addRequired<MachineFunctionAnalysis>();
152 AU.addRequired<MachineDominatorTree>();
153 AU.addRequired<MachinePostDominatorTree>();
154 AU.addRequired<MachineLoopInfo>();
157 /// Perform the CFG structurization
160 /// Perform the CFG preparation
161 /// This step will remove every unconditionnal/dead jump instructions and make
162 /// sure all loops have an exit block
165 bool runOnMachineFunction(MachineFunction &MF) override {
166 TII = static_cast<const R600InstrInfo *>(MF.getSubtarget().getInstrInfo());
167 TRI = &TII->getRegisterInfo();
172 MLI = &getAnalysis<MachineLoopInfo>();
173 DEBUG(dbgs() << "LoopInfo:\n"; PrintLoopinfo(*MLI););
174 MDT = &getAnalysis<MachineDominatorTree>();
175 DEBUG(MDT->print(dbgs(), (const llvm::Module*)nullptr););
176 PDT = &getAnalysis<MachinePostDominatorTree>();
177 DEBUG(PDT->print(dbgs()););
185 MachineDominatorTree *MDT;
186 MachinePostDominatorTree *PDT;
187 MachineLoopInfo *MLI;
188 const R600InstrInfo *TII;
189 const AMDGPURegisterInfo *TRI;
192 /// Print the ordered Blocks.
193 void printOrderedBlocks() const {
195 for (MBBVector::const_iterator iterBlk = OrderedBlks.begin(),
196 iterBlkEnd = OrderedBlks.end(); iterBlk != iterBlkEnd; ++iterBlk, ++i) {
197 dbgs() << "BB" << (*iterBlk)->getNumber();
198 dbgs() << "(" << getSCCNum(*iterBlk) << "," << (*iterBlk)->size() << ")";
199 if (i != 0 && i % 10 == 0) {
206 static void PrintLoopinfo(const MachineLoopInfo &LoopInfo) {
207 for (MachineLoop::iterator iter = LoopInfo.begin(),
208 iterEnd = LoopInfo.end(); iter != iterEnd; ++iter) {
209 (*iter)->print(dbgs(), 0);
214 int getSCCNum(MachineBasicBlock *MBB) const;
215 MachineBasicBlock *getLoopLandInfo(MachineLoop *LoopRep) const;
216 bool hasBackEdge(MachineBasicBlock *MBB) const;
217 static unsigned getLoopDepth(MachineLoop *LoopRep);
218 bool isRetiredBlock(MachineBasicBlock *MBB) const;
219 bool isActiveLoophead(MachineBasicBlock *MBB) const;
220 PathToKind singlePathTo(MachineBasicBlock *SrcMBB, MachineBasicBlock *DstMBB,
221 bool AllowSideEntry = true) const;
222 int countActiveBlock(MBBVector::const_iterator It,
223 MBBVector::const_iterator E) const;
224 bool needMigrateBlock(MachineBasicBlock *MBB) const;
227 void reversePredicateSetter(MachineBasicBlock::iterator I);
228 /// Compute the reversed DFS post order of Blocks
229 void orderBlocks(MachineFunction *MF);
231 // Function originally from CFGStructTraits
232 void insertInstrEnd(MachineBasicBlock *MBB, int NewOpcode,
233 DebugLoc DL = DebugLoc());
234 MachineInstr *insertInstrBefore(MachineBasicBlock *MBB, int NewOpcode,
235 DebugLoc DL = DebugLoc());
236 MachineInstr *insertInstrBefore(MachineBasicBlock::iterator I, int NewOpcode);
237 void insertCondBranchBefore(MachineBasicBlock::iterator I, int NewOpcode,
239 void insertCondBranchBefore(MachineBasicBlock *MBB,
240 MachineBasicBlock::iterator I, int NewOpcode, int RegNum,
242 void insertCondBranchEnd(MachineBasicBlock *MBB, int NewOpcode, int RegNum);
243 static int getBranchNzeroOpcode(int OldOpcode);
244 static int getBranchZeroOpcode(int OldOpcode);
245 static int getContinueNzeroOpcode(int OldOpcode);
246 static int getContinueZeroOpcode(int OldOpcode);
247 static MachineBasicBlock *getTrueBranch(MachineInstr *MI);
248 static void setTrueBranch(MachineInstr *MI, MachineBasicBlock *MBB);
249 static MachineBasicBlock *getFalseBranch(MachineBasicBlock *MBB,
251 static bool isCondBranch(MachineInstr *MI);
252 static bool isUncondBranch(MachineInstr *MI);
253 static DebugLoc getLastDebugLocInBB(MachineBasicBlock *MBB);
254 static MachineInstr *getNormalBlockBranchInstr(MachineBasicBlock *MBB);
255 /// The correct naming for this is getPossibleLoopendBlockBranchInstr.
257 /// BB with backward-edge could have move instructions after the branch
258 /// instruction. Such move instruction "belong to" the loop backward-edge.
259 MachineInstr *getLoopendBlockBranchInstr(MachineBasicBlock *MBB);
260 static MachineInstr *getReturnInstr(MachineBasicBlock *MBB);
261 static MachineInstr *getContinueInstr(MachineBasicBlock *MBB);
262 static bool isReturnBlock(MachineBasicBlock *MBB);
263 static void cloneSuccessorList(MachineBasicBlock *DstMBB,
264 MachineBasicBlock *SrcMBB) ;
265 static MachineBasicBlock *clone(MachineBasicBlock *MBB);
266 /// MachineBasicBlock::ReplaceUsesOfBlockWith doesn't serve the purpose
267 /// because the AMDGPU instruction is not recognized as terminator fix this
268 /// and retire this routine
269 void replaceInstrUseOfBlockWith(MachineBasicBlock *SrcMBB,
270 MachineBasicBlock *OldMBB, MachineBasicBlock *NewBlk);
271 static void wrapup(MachineBasicBlock *MBB);
274 int patternMatch(MachineBasicBlock *MBB);
275 int patternMatchGroup(MachineBasicBlock *MBB);
276 int serialPatternMatch(MachineBasicBlock *MBB);
277 int ifPatternMatch(MachineBasicBlock *MBB);
278 int loopendPatternMatch();
279 int mergeLoop(MachineLoop *LoopRep);
280 int loopcontPatternMatch(MachineLoop *LoopRep, MachineBasicBlock *LoopHeader);
282 void handleLoopcontBlock(MachineBasicBlock *ContingMBB,
283 MachineLoop *ContingLoop, MachineBasicBlock *ContMBB,
284 MachineLoop *ContLoop);
285 /// return true iff src1Blk->succ_size() == 0 && src1Blk and src2Blk are in
286 /// the same loop with LoopLandInfo without explicitly keeping track of
287 /// loopContBlks and loopBreakBlks, this is a method to get the information.
288 bool isSameloopDetachedContbreak(MachineBasicBlock *Src1MBB,
289 MachineBasicBlock *Src2MBB);
290 int handleJumpintoIf(MachineBasicBlock *HeadMBB,
291 MachineBasicBlock *TrueMBB, MachineBasicBlock *FalseMBB);
292 int handleJumpintoIfImp(MachineBasicBlock *HeadMBB,
293 MachineBasicBlock *TrueMBB, MachineBasicBlock *FalseMBB);
294 int improveSimpleJumpintoIf(MachineBasicBlock *HeadMBB,
295 MachineBasicBlock *TrueMBB, MachineBasicBlock *FalseMBB,
296 MachineBasicBlock **LandMBBPtr);
297 void showImproveSimpleJumpintoIf(MachineBasicBlock *HeadMBB,
298 MachineBasicBlock *TrueMBB, MachineBasicBlock *FalseMBB,
299 MachineBasicBlock *LandMBB, bool Detail = false);
300 int cloneOnSideEntryTo(MachineBasicBlock *PreMBB,
301 MachineBasicBlock *SrcMBB, MachineBasicBlock *DstMBB);
302 void mergeSerialBlock(MachineBasicBlock *DstMBB,
303 MachineBasicBlock *SrcMBB);
305 void mergeIfthenelseBlock(MachineInstr *BranchMI,
306 MachineBasicBlock *MBB, MachineBasicBlock *TrueMBB,
307 MachineBasicBlock *FalseMBB, MachineBasicBlock *LandMBB);
308 void mergeLooplandBlock(MachineBasicBlock *DstMBB,
309 MachineBasicBlock *LandMBB);
310 void mergeLoopbreakBlock(MachineBasicBlock *ExitingMBB,
311 MachineBasicBlock *LandMBB);
312 void settleLoopcontBlock(MachineBasicBlock *ContingMBB,
313 MachineBasicBlock *ContMBB);
314 /// normalizeInfiniteLoopExit change
316 /// uncond_br LoopHeader
320 /// cond_br 1 LoopHeader dummyExit
321 /// and return the newly added dummy exit block
322 MachineBasicBlock *normalizeInfiniteLoopExit(MachineLoop *LoopRep);
323 void removeUnconditionalBranch(MachineBasicBlock *MBB);
324 /// Remove duplicate branches instructions in a block.
329 /// is transformed to
332 void removeRedundantConditionalBranch(MachineBasicBlock *MBB);
333 void addDummyExitBlock(SmallVectorImpl<MachineBasicBlock *> &RetMBB);
334 void removeSuccessor(MachineBasicBlock *MBB);
335 MachineBasicBlock *cloneBlockForPredecessor(MachineBasicBlock *MBB,
336 MachineBasicBlock *PredMBB);
337 void migrateInstruction(MachineBasicBlock *SrcMBB,
338 MachineBasicBlock *DstMBB, MachineBasicBlock::iterator I);
339 void recordSccnum(MachineBasicBlock *MBB, int SCCNum);
340 void retireBlock(MachineBasicBlock *MBB);
341 void setLoopLandBlock(MachineLoop *LoopRep, MachineBasicBlock *MBB = nullptr);
343 MachineBasicBlock *findNearestCommonPostDom(std::set<MachineBasicBlock *>&);
344 /// This is work around solution for findNearestCommonDominator not available
345 /// to post dom a proper fix should go to Dominators.h.
346 MachineBasicBlock *findNearestCommonPostDom(MachineBasicBlock *MBB1,
347 MachineBasicBlock *MBB2);
350 MBBInfoMap BlockInfoMap;
351 LoopLandInfoMap LLInfoMap;
352 std::map<MachineLoop *, bool> Visited;
353 MachineFunction *FuncRep;
354 SmallVector<MachineBasicBlock *, DEFAULT_VEC_SLOTS> OrderedBlks;
357 int AMDGPUCFGStructurizer::getSCCNum(MachineBasicBlock *MBB) const {
358 MBBInfoMap::const_iterator It = BlockInfoMap.find(MBB);
359 if (It == BlockInfoMap.end())
360 return INVALIDSCCNUM;
361 return (*It).second->SccNum;
364 MachineBasicBlock *AMDGPUCFGStructurizer::getLoopLandInfo(MachineLoop *LoopRep)
366 LoopLandInfoMap::const_iterator It = LLInfoMap.find(LoopRep);
367 if (It == LLInfoMap.end())
372 bool AMDGPUCFGStructurizer::hasBackEdge(MachineBasicBlock *MBB) const {
373 MachineLoop *LoopRep = MLI->getLoopFor(MBB);
376 MachineBasicBlock *LoopHeader = LoopRep->getHeader();
377 return MBB->isSuccessor(LoopHeader);
380 unsigned AMDGPUCFGStructurizer::getLoopDepth(MachineLoop *LoopRep) {
381 return LoopRep ? LoopRep->getLoopDepth() : 0;
384 bool AMDGPUCFGStructurizer::isRetiredBlock(MachineBasicBlock *MBB) const {
385 MBBInfoMap::const_iterator It = BlockInfoMap.find(MBB);
386 if (It == BlockInfoMap.end())
388 return (*It).second->IsRetired;
391 bool AMDGPUCFGStructurizer::isActiveLoophead(MachineBasicBlock *MBB) const {
392 MachineLoop *LoopRep = MLI->getLoopFor(MBB);
393 while (LoopRep && LoopRep->getHeader() == MBB) {
394 MachineBasicBlock *LoopLand = getLoopLandInfo(LoopRep);
397 if (!isRetiredBlock(LoopLand))
399 LoopRep = LoopRep->getParentLoop();
403 AMDGPUCFGStructurizer::PathToKind AMDGPUCFGStructurizer::singlePathTo(
404 MachineBasicBlock *SrcMBB, MachineBasicBlock *DstMBB,
405 bool AllowSideEntry) const {
407 if (SrcMBB == DstMBB)
408 return SinglePath_InPath;
409 while (SrcMBB && SrcMBB->succ_size() == 1) {
410 SrcMBB = *SrcMBB->succ_begin();
411 if (SrcMBB == DstMBB)
412 return SinglePath_InPath;
413 if (!AllowSideEntry && SrcMBB->pred_size() > 1)
414 return Not_SinglePath;
416 if (SrcMBB && SrcMBB->succ_size()==0)
417 return SinglePath_NotInPath;
418 return Not_SinglePath;
421 int AMDGPUCFGStructurizer::countActiveBlock(MBBVector::const_iterator It,
422 MBBVector::const_iterator E) const {
425 if (!isRetiredBlock(*It))
432 bool AMDGPUCFGStructurizer::needMigrateBlock(MachineBasicBlock *MBB) const {
433 unsigned BlockSizeThreshold = 30;
434 unsigned CloneInstrThreshold = 100;
435 bool MultiplePreds = MBB && (MBB->pred_size() > 1);
439 unsigned BlkSize = MBB->size();
440 return ((BlkSize > BlockSizeThreshold) &&
441 (BlkSize * (MBB->pred_size() - 1) > CloneInstrThreshold));
444 void AMDGPUCFGStructurizer::reversePredicateSetter(
445 MachineBasicBlock::iterator I) {
447 if (I->getOpcode() == AMDGPU::PRED_X) {
448 switch (static_cast<MachineInstr *>(I)->getOperand(2).getImm()) {
449 case OPCODE_IS_ZERO_INT:
450 static_cast<MachineInstr *>(I)->getOperand(2)
451 .setImm(OPCODE_IS_NOT_ZERO_INT);
453 case OPCODE_IS_NOT_ZERO_INT:
454 static_cast<MachineInstr *>(I)->getOperand(2)
455 .setImm(OPCODE_IS_ZERO_INT);
458 static_cast<MachineInstr *>(I)->getOperand(2)
459 .setImm(OPCODE_IS_NOT_ZERO);
461 case OPCODE_IS_NOT_ZERO:
462 static_cast<MachineInstr *>(I)->getOperand(2)
463 .setImm(OPCODE_IS_ZERO);
466 llvm_unreachable("PRED_X Opcode invalid!");
472 void AMDGPUCFGStructurizer::insertInstrEnd(MachineBasicBlock *MBB,
473 int NewOpcode, DebugLoc DL) {
474 MachineInstr *MI = MBB->getParent()
475 ->CreateMachineInstr(TII->get(NewOpcode), DL);
477 //assume the instruction doesn't take any reg operand ...
481 MachineInstr *AMDGPUCFGStructurizer::insertInstrBefore(MachineBasicBlock *MBB,
482 int NewOpcode, DebugLoc DL) {
484 MBB->getParent()->CreateMachineInstr(TII->get(NewOpcode), DL);
485 if (MBB->begin() != MBB->end())
486 MBB->insert(MBB->begin(), MI);
493 MachineInstr *AMDGPUCFGStructurizer::insertInstrBefore(
494 MachineBasicBlock::iterator I, int NewOpcode) {
495 MachineInstr *OldMI = &(*I);
496 MachineBasicBlock *MBB = OldMI->getParent();
497 MachineInstr *NewMBB =
498 MBB->getParent()->CreateMachineInstr(TII->get(NewOpcode), DebugLoc());
499 MBB->insert(I, NewMBB);
500 //assume the instruction doesn't take any reg operand ...
501 SHOWNEWINSTR(NewMBB);
505 void AMDGPUCFGStructurizer::insertCondBranchBefore(
506 MachineBasicBlock::iterator I, int NewOpcode, DebugLoc DL) {
507 MachineInstr *OldMI = &(*I);
508 MachineBasicBlock *MBB = OldMI->getParent();
509 MachineFunction *MF = MBB->getParent();
510 MachineInstr *NewMI = MF->CreateMachineInstr(TII->get(NewOpcode), DL);
511 MBB->insert(I, NewMI);
512 MachineInstrBuilder MIB(*MF, NewMI);
513 MIB.addReg(OldMI->getOperand(1).getReg(), false);
515 //erase later oldInstr->eraseFromParent();
518 void AMDGPUCFGStructurizer::insertCondBranchBefore(MachineBasicBlock *blk,
519 MachineBasicBlock::iterator I, int NewOpcode, int RegNum,
521 MachineFunction *MF = blk->getParent();
522 MachineInstr *NewInstr = MF->CreateMachineInstr(TII->get(NewOpcode), DL);
524 blk->insert(I, NewInstr);
525 MachineInstrBuilder(*MF, NewInstr).addReg(RegNum, false);
526 SHOWNEWINSTR(NewInstr);
529 void AMDGPUCFGStructurizer::insertCondBranchEnd(MachineBasicBlock *MBB,
530 int NewOpcode, int RegNum) {
531 MachineFunction *MF = MBB->getParent();
532 MachineInstr *NewInstr =
533 MF->CreateMachineInstr(TII->get(NewOpcode), DebugLoc());
534 MBB->push_back(NewInstr);
535 MachineInstrBuilder(*MF, NewInstr).addReg(RegNum, false);
536 SHOWNEWINSTR(NewInstr);
539 int AMDGPUCFGStructurizer::getBranchNzeroOpcode(int OldOpcode) {
541 case AMDGPU::JUMP_COND:
542 case AMDGPU::JUMP: return AMDGPU::IF_PREDICATE_SET;
543 case AMDGPU::BRANCH_COND_i32:
544 case AMDGPU::BRANCH_COND_f32: return AMDGPU::IF_LOGICALNZ_f32;
545 default: llvm_unreachable("internal error");
550 int AMDGPUCFGStructurizer::getBranchZeroOpcode(int OldOpcode) {
552 case AMDGPU::JUMP_COND:
553 case AMDGPU::JUMP: return AMDGPU::IF_PREDICATE_SET;
554 case AMDGPU::BRANCH_COND_i32:
555 case AMDGPU::BRANCH_COND_f32: return AMDGPU::IF_LOGICALZ_f32;
556 default: llvm_unreachable("internal error");
561 int AMDGPUCFGStructurizer::getContinueNzeroOpcode(int OldOpcode) {
563 case AMDGPU::JUMP_COND:
564 case AMDGPU::JUMP: return AMDGPU::CONTINUE_LOGICALNZ_i32;
565 default: llvm_unreachable("internal error");
570 int AMDGPUCFGStructurizer::getContinueZeroOpcode(int OldOpcode) {
572 case AMDGPU::JUMP_COND:
573 case AMDGPU::JUMP: return AMDGPU::CONTINUE_LOGICALZ_i32;
574 default: llvm_unreachable("internal error");
579 MachineBasicBlock *AMDGPUCFGStructurizer::getTrueBranch(MachineInstr *MI) {
580 return MI->getOperand(0).getMBB();
583 void AMDGPUCFGStructurizer::setTrueBranch(MachineInstr *MI,
584 MachineBasicBlock *MBB) {
585 MI->getOperand(0).setMBB(MBB);
589 AMDGPUCFGStructurizer::getFalseBranch(MachineBasicBlock *MBB,
591 assert(MBB->succ_size() == 2);
592 MachineBasicBlock *TrueBranch = getTrueBranch(MI);
593 MachineBasicBlock::succ_iterator It = MBB->succ_begin();
594 MachineBasicBlock::succ_iterator Next = It;
596 return (*It == TrueBranch) ? *Next : *It;
599 bool AMDGPUCFGStructurizer::isCondBranch(MachineInstr *MI) {
600 switch (MI->getOpcode()) {
601 case AMDGPU::JUMP_COND:
602 case AMDGPU::BRANCH_COND_i32:
603 case AMDGPU::BRANCH_COND_f32: return true;
610 bool AMDGPUCFGStructurizer::isUncondBranch(MachineInstr *MI) {
611 switch (MI->getOpcode()) {
621 DebugLoc AMDGPUCFGStructurizer::getLastDebugLocInBB(MachineBasicBlock *MBB) {
622 //get DebugLoc from the first MachineBasicBlock instruction with debug info
624 for (MachineBasicBlock::iterator It = MBB->begin(); It != MBB->end();
626 MachineInstr *instr = &(*It);
627 if (instr->getDebugLoc().isUnknown() == false)
628 DL = instr->getDebugLoc();
633 MachineInstr *AMDGPUCFGStructurizer::getNormalBlockBranchInstr(
634 MachineBasicBlock *MBB) {
635 MachineBasicBlock::reverse_iterator It = MBB->rbegin();
636 MachineInstr *MI = &*It;
637 if (MI && (isCondBranch(MI) || isUncondBranch(MI)))
642 MachineInstr *AMDGPUCFGStructurizer::getLoopendBlockBranchInstr(
643 MachineBasicBlock *MBB) {
644 for (MachineBasicBlock::reverse_iterator It = MBB->rbegin(), E = MBB->rend();
647 MachineInstr *MI = &*It;
649 if (isCondBranch(MI) || isUncondBranch(MI))
651 else if (!TII->isMov(MI->getOpcode()))
658 MachineInstr *AMDGPUCFGStructurizer::getReturnInstr(MachineBasicBlock *MBB) {
659 MachineBasicBlock::reverse_iterator It = MBB->rbegin();
660 if (It != MBB->rend()) {
661 MachineInstr *instr = &(*It);
662 if (instr->getOpcode() == AMDGPU::RETURN)
668 MachineInstr *AMDGPUCFGStructurizer::getContinueInstr(MachineBasicBlock *MBB) {
669 MachineBasicBlock::reverse_iterator It = MBB->rbegin();
670 if (It != MBB->rend()) {
671 MachineInstr *MI = &(*It);
672 if (MI->getOpcode() == AMDGPU::CONTINUE)
678 bool AMDGPUCFGStructurizer::isReturnBlock(MachineBasicBlock *MBB) {
679 MachineInstr *MI = getReturnInstr(MBB);
680 bool IsReturn = (MBB->succ_size() == 0);
685 dbgs() << "BB" << MBB->getNumber()
686 <<" is return block without RETURN instr\n";);
690 void AMDGPUCFGStructurizer::cloneSuccessorList(MachineBasicBlock *DstMBB,
691 MachineBasicBlock *SrcMBB) {
692 for (MachineBasicBlock::succ_iterator It = SrcMBB->succ_begin(),
693 iterEnd = SrcMBB->succ_end(); It != iterEnd; ++It)
694 DstMBB->addSuccessor(*It); // *iter's predecessor is also taken care of
697 MachineBasicBlock *AMDGPUCFGStructurizer::clone(MachineBasicBlock *MBB) {
698 MachineFunction *Func = MBB->getParent();
699 MachineBasicBlock *NewMBB = Func->CreateMachineBasicBlock();
700 Func->push_back(NewMBB); //insert to function
701 for (MachineBasicBlock::iterator It = MBB->begin(), E = MBB->end();
703 MachineInstr *MI = Func->CloneMachineInstr(It);
704 NewMBB->push_back(MI);
709 void AMDGPUCFGStructurizer::replaceInstrUseOfBlockWith(
710 MachineBasicBlock *SrcMBB, MachineBasicBlock *OldMBB,
711 MachineBasicBlock *NewBlk) {
712 MachineInstr *BranchMI = getLoopendBlockBranchInstr(SrcMBB);
713 if (BranchMI && isCondBranch(BranchMI) &&
714 getTrueBranch(BranchMI) == OldMBB)
715 setTrueBranch(BranchMI, NewBlk);
718 void AMDGPUCFGStructurizer::wrapup(MachineBasicBlock *MBB) {
719 assert((!MBB->getParent()->getJumpTableInfo()
720 || MBB->getParent()->getJumpTableInfo()->isEmpty())
721 && "found a jump table");
723 //collect continue right before endloop
724 SmallVector<MachineInstr *, DEFAULT_VEC_SLOTS> ContInstr;
725 MachineBasicBlock::iterator Pre = MBB->begin();
726 MachineBasicBlock::iterator E = MBB->end();
727 MachineBasicBlock::iterator It = Pre;
729 if (Pre->getOpcode() == AMDGPU::CONTINUE
730 && It->getOpcode() == AMDGPU::ENDLOOP)
731 ContInstr.push_back(Pre);
736 //delete continue right before endloop
737 for (unsigned i = 0; i < ContInstr.size(); ++i)
738 ContInstr[i]->eraseFromParent();
740 // TODO to fix up jump table so later phase won't be confused. if
741 // (jumpTableInfo->isEmpty() == false) { need to clean the jump table, but
742 // there isn't such an interface yet. alternatively, replace all the other
743 // blocks in the jump table with the entryBlk //}
748 bool AMDGPUCFGStructurizer::prepare() {
749 bool Changed = false;
751 //FIXME: if not reducible flow graph, make it so ???
753 DEBUG(dbgs() << "AMDGPUCFGStructurizer::prepare\n";);
755 orderBlocks(FuncRep);
757 SmallVector<MachineBasicBlock *, DEFAULT_VEC_SLOTS> RetBlks;
759 // Add an ExitBlk to loop that don't have one
760 for (MachineLoopInfo::iterator It = MLI->begin(),
761 E = MLI->end(); It != E; ++It) {
762 MachineLoop *LoopRep = (*It);
763 MBBVector ExitingMBBs;
764 LoopRep->getExitingBlocks(ExitingMBBs);
766 if (ExitingMBBs.size() == 0) {
767 MachineBasicBlock* DummyExitBlk = normalizeInfiniteLoopExit(LoopRep);
769 RetBlks.push_back(DummyExitBlk);
773 // Remove unconditional branch instr.
774 // Add dummy exit block iff there are multiple returns.
775 for (SmallVectorImpl<MachineBasicBlock *>::const_iterator
776 It = OrderedBlks.begin(), E = OrderedBlks.end(); It != E; ++It) {
777 MachineBasicBlock *MBB = *It;
778 removeUnconditionalBranch(MBB);
779 removeRedundantConditionalBranch(MBB);
780 if (isReturnBlock(MBB)) {
781 RetBlks.push_back(MBB);
783 assert(MBB->succ_size() <= 2);
786 if (RetBlks.size() >= 2) {
787 addDummyExitBlock(RetBlks);
794 bool AMDGPUCFGStructurizer::run() {
796 //Assume reducible CFG...
797 DEBUG(dbgs() << "AMDGPUCFGStructurizer::run\n");
800 //Use the worse block ordering to test the algorithm.
801 ReverseVector(orderedBlks);
804 DEBUG(dbgs() << "Ordered blocks:\n"; printOrderedBlocks(););
807 MachineBasicBlock *MBB;
808 bool MakeProgress = false;
809 int NumRemainedBlk = countActiveBlock(OrderedBlks.begin(),
815 dbgs() << "numIter = " << NumIter
816 << ", numRemaintedBlk = " << NumRemainedBlk << "\n";
819 SmallVectorImpl<MachineBasicBlock *>::const_iterator It =
821 SmallVectorImpl<MachineBasicBlock *>::const_iterator E =
824 SmallVectorImpl<MachineBasicBlock *>::const_iterator SccBeginIter =
826 MachineBasicBlock *SccBeginMBB = nullptr;
827 int SccNumBlk = 0; // The number of active blocks, init to a
828 // maximum possible number.
829 int SccNumIter; // Number of iteration in this SCC.
838 SccNumBlk = NumRemainedBlk; // Init to maximum possible number.
840 dbgs() << "start processing SCC" << getSCCNum(SccBeginMBB);
845 if (!isRetiredBlock(MBB))
850 bool ContNextScc = true;
852 || getSCCNum(SccBeginMBB) != getSCCNum(*It)) {
853 // Just finish one scc.
855 int sccRemainedNumBlk = countActiveBlock(SccBeginIter, It);
856 if (sccRemainedNumBlk != 1 && sccRemainedNumBlk >= SccNumBlk) {
858 dbgs() << "Can't reduce SCC " << getSCCNum(MBB)
859 << ", sccNumIter = " << SccNumIter;
860 dbgs() << "doesn't make any progress\n";
863 } else if (sccRemainedNumBlk != 1 && sccRemainedNumBlk < SccNumBlk) {
864 SccNumBlk = sccRemainedNumBlk;
868 dbgs() << "repeat processing SCC" << getSCCNum(MBB)
869 << "sccNumIter = " << SccNumIter << '\n';
872 // Finish the current scc.
876 // Continue on next component in the current scc.
881 SccBeginMBB = nullptr;
882 } //while, "one iteration" over the function.
884 MachineBasicBlock *EntryMBB =
885 GraphTraits<MachineFunction *>::nodes_begin(FuncRep);
886 if (EntryMBB->succ_size() == 0) {
889 dbgs() << "Reduce to one block\n";
892 int NewnumRemainedBlk
893 = countActiveBlock(OrderedBlks.begin(), OrderedBlks.end());
894 // consider cloned blocks ??
895 if (NewnumRemainedBlk == 1 || NewnumRemainedBlk < NumRemainedBlk) {
897 NumRemainedBlk = NewnumRemainedBlk;
899 MakeProgress = false;
901 dbgs() << "No progress\n";
905 } while (!Finish && MakeProgress);
907 // Misc wrap up to maintain the consistency of the Function representation.
908 wrapup(GraphTraits<MachineFunction *>::nodes_begin(FuncRep));
910 // Detach retired Block, release memory.
911 for (MBBInfoMap::iterator It = BlockInfoMap.begin(), E = BlockInfoMap.end();
913 if ((*It).second && (*It).second->IsRetired) {
914 assert(((*It).first)->getNumber() != -1);
916 dbgs() << "Erase BB" << ((*It).first)->getNumber() << "\n";
918 (*It).first->eraseFromParent(); //Remove from the parent Function.
922 BlockInfoMap.clear();
926 DEBUG(FuncRep->viewCFG());
927 llvm_unreachable("IRREDUCIBLE_CFG");
935 void AMDGPUCFGStructurizer::orderBlocks(MachineFunction *MF) {
937 MachineBasicBlock *MBB;
938 for (scc_iterator<MachineFunction *> It = scc_begin(MF); !It.isAtEnd();
940 const std::vector<MachineBasicBlock *> &SccNext = *It;
941 for (std::vector<MachineBasicBlock *>::const_iterator
942 blockIter = SccNext.begin(), blockEnd = SccNext.end();
943 blockIter != blockEnd; ++blockIter) {
945 OrderedBlks.push_back(MBB);
946 recordSccnum(MBB, SccNum);
950 //walk through all the block in func to check for unreachable
951 typedef GraphTraits<MachineFunction *> GTM;
952 MachineFunction::iterator It = GTM::nodes_begin(MF), E = GTM::nodes_end(MF);
953 for (; It != E; ++It) {
954 MachineBasicBlock *MBB = &(*It);
955 SccNum = getSCCNum(MBB);
956 if (SccNum == INVALIDSCCNUM)
957 dbgs() << "unreachable block BB" << MBB->getNumber() << "\n";
961 int AMDGPUCFGStructurizer::patternMatch(MachineBasicBlock *MBB) {
966 dbgs() << "Begin patternMatch BB" << MBB->getNumber() << "\n";
969 while ((CurMatch = patternMatchGroup(MBB)) > 0)
970 NumMatch += CurMatch;
973 dbgs() << "End patternMatch BB" << MBB->getNumber()
974 << ", numMatch = " << NumMatch << "\n";
980 int AMDGPUCFGStructurizer::patternMatchGroup(MachineBasicBlock *MBB) {
982 NumMatch += loopendPatternMatch();
983 NumMatch += serialPatternMatch(MBB);
984 NumMatch += ifPatternMatch(MBB);
989 int AMDGPUCFGStructurizer::serialPatternMatch(MachineBasicBlock *MBB) {
990 if (MBB->succ_size() != 1)
993 MachineBasicBlock *childBlk = *MBB->succ_begin();
994 if (childBlk->pred_size() != 1 || isActiveLoophead(childBlk))
997 mergeSerialBlock(MBB, childBlk);
998 ++numSerialPatternMatch;
1002 int AMDGPUCFGStructurizer::ifPatternMatch(MachineBasicBlock *MBB) {
1004 if (MBB->succ_size() != 2)
1006 if (hasBackEdge(MBB))
1008 MachineInstr *BranchMI = getNormalBlockBranchInstr(MBB);
1012 assert(isCondBranch(BranchMI));
1015 MachineBasicBlock *TrueMBB = getTrueBranch(BranchMI);
1016 NumMatch += serialPatternMatch(TrueMBB);
1017 NumMatch += ifPatternMatch(TrueMBB);
1018 MachineBasicBlock *FalseMBB = getFalseBranch(MBB, BranchMI);
1019 NumMatch += serialPatternMatch(FalseMBB);
1020 NumMatch += ifPatternMatch(FalseMBB);
1021 MachineBasicBlock *LandBlk;
1024 assert (!TrueMBB->succ_empty() || !FalseMBB->succ_empty());
1026 if (TrueMBB->succ_size() == 1 && FalseMBB->succ_size() == 1
1027 && *TrueMBB->succ_begin() == *FalseMBB->succ_begin()) {
1029 LandBlk = *TrueMBB->succ_begin();
1030 } else if (TrueMBB->succ_size() == 1 && *TrueMBB->succ_begin() == FalseMBB) {
1031 // Triangle pattern, false is empty
1034 } else if (FalseMBB->succ_size() == 1
1035 && *FalseMBB->succ_begin() == TrueMBB) {
1036 // Triangle pattern, true is empty
1037 // We reverse the predicate to make a triangle, empty false pattern;
1038 std::swap(TrueMBB, FalseMBB);
1039 reversePredicateSetter(MBB->end());
1042 } else if (FalseMBB->succ_size() == 1
1043 && isSameloopDetachedContbreak(TrueMBB, FalseMBB)) {
1044 LandBlk = *FalseMBB->succ_begin();
1045 } else if (TrueMBB->succ_size() == 1
1046 && isSameloopDetachedContbreak(FalseMBB, TrueMBB)) {
1047 LandBlk = *TrueMBB->succ_begin();
1049 return NumMatch + handleJumpintoIf(MBB, TrueMBB, FalseMBB);
1052 // improveSimpleJumpinfoIf can handle the case where landBlk == NULL but the
1053 // new BB created for landBlk==NULL may introduce new challenge to the
1054 // reduction process.
1056 ((TrueMBB && TrueMBB->pred_size() > 1)
1057 || (FalseMBB && FalseMBB->pred_size() > 1))) {
1058 Cloned += improveSimpleJumpintoIf(MBB, TrueMBB, FalseMBB, &LandBlk);
1061 if (TrueMBB && TrueMBB->pred_size() > 1) {
1062 TrueMBB = cloneBlockForPredecessor(TrueMBB, MBB);
1066 if (FalseMBB && FalseMBB->pred_size() > 1) {
1067 FalseMBB = cloneBlockForPredecessor(FalseMBB, MBB);
1071 mergeIfthenelseBlock(BranchMI, MBB, TrueMBB, FalseMBB, LandBlk);
1073 ++numIfPatternMatch;
1075 numClonedBlock += Cloned;
1077 return 1 + Cloned + NumMatch;
1080 int AMDGPUCFGStructurizer::loopendPatternMatch() {
1081 std::deque<MachineLoop *> NestedLoops;
1082 for (auto &It: *MLI)
1083 for (MachineLoop *ML : depth_first(It))
1084 NestedLoops.push_front(ML);
1086 if (NestedLoops.size() == 0)
1089 // Process nested loop outside->inside (we did push_front),
1090 // so "continue" to a outside loop won't be mistaken as "break"
1091 // of the current loop.
1093 for (MachineLoop *ExaminedLoop : NestedLoops) {
1094 if (ExaminedLoop->getNumBlocks() == 0 || Visited[ExaminedLoop])
1096 DEBUG(dbgs() << "Processing:\n"; ExaminedLoop->dump(););
1097 int NumBreak = mergeLoop(ExaminedLoop);
1105 int AMDGPUCFGStructurizer::mergeLoop(MachineLoop *LoopRep) {
1106 MachineBasicBlock *LoopHeader = LoopRep->getHeader();
1107 MBBVector ExitingMBBs;
1108 LoopRep->getExitingBlocks(ExitingMBBs);
1109 assert(!ExitingMBBs.empty() && "Infinite Loop not supported");
1110 DEBUG(dbgs() << "Loop has " << ExitingMBBs.size() << " exiting blocks\n";);
1111 // We assume a single ExitBlk
1113 LoopRep->getExitBlocks(ExitBlks);
1114 SmallPtrSet<MachineBasicBlock *, 2> ExitBlkSet;
1115 for (unsigned i = 0, e = ExitBlks.size(); i < e; ++i)
1116 ExitBlkSet.insert(ExitBlks[i]);
1117 assert(ExitBlkSet.size() == 1);
1118 MachineBasicBlock *ExitBlk = *ExitBlks.begin();
1119 assert(ExitBlk && "Loop has several exit block");
1120 MBBVector LatchBlks;
1121 typedef GraphTraits<Inverse<MachineBasicBlock*> > InvMBBTraits;
1122 InvMBBTraits::ChildIteratorType PI = InvMBBTraits::child_begin(LoopHeader),
1123 PE = InvMBBTraits::child_end(LoopHeader);
1124 for (; PI != PE; PI++) {
1125 if (LoopRep->contains(*PI))
1126 LatchBlks.push_back(*PI);
1129 for (unsigned i = 0, e = ExitingMBBs.size(); i < e; ++i)
1130 mergeLoopbreakBlock(ExitingMBBs[i], ExitBlk);
1131 for (unsigned i = 0, e = LatchBlks.size(); i < e; ++i)
1132 settleLoopcontBlock(LatchBlks[i], LoopHeader);
1136 Match += serialPatternMatch(LoopHeader);
1137 Match += ifPatternMatch(LoopHeader);
1138 } while (Match > 0);
1139 mergeLooplandBlock(LoopHeader, ExitBlk);
1140 MachineLoop *ParentLoop = LoopRep->getParentLoop();
1142 MLI->changeLoopFor(LoopHeader, ParentLoop);
1144 MLI->removeBlock(LoopHeader);
1145 Visited[LoopRep] = true;
1149 int AMDGPUCFGStructurizer::loopcontPatternMatch(MachineLoop *LoopRep,
1150 MachineBasicBlock *LoopHeader) {
1152 SmallVector<MachineBasicBlock *, DEFAULT_VEC_SLOTS> ContMBB;
1153 typedef GraphTraits<Inverse<MachineBasicBlock *> > GTIM;
1154 GTIM::ChildIteratorType It = GTIM::child_begin(LoopHeader),
1155 E = GTIM::child_end(LoopHeader);
1156 for (; It != E; ++It) {
1157 MachineBasicBlock *MBB = *It;
1158 if (LoopRep->contains(MBB)) {
1159 handleLoopcontBlock(MBB, MLI->getLoopFor(MBB),
1160 LoopHeader, LoopRep);
1161 ContMBB.push_back(MBB);
1166 for (SmallVectorImpl<MachineBasicBlock *>::iterator It = ContMBB.begin(),
1167 E = ContMBB.end(); It != E; ++It) {
1168 (*It)->removeSuccessor(LoopHeader);
1171 numLoopcontPatternMatch += NumCont;
1177 bool AMDGPUCFGStructurizer::isSameloopDetachedContbreak(
1178 MachineBasicBlock *Src1MBB, MachineBasicBlock *Src2MBB) {
1179 if (Src1MBB->succ_size() == 0) {
1180 MachineLoop *LoopRep = MLI->getLoopFor(Src1MBB);
1181 if (LoopRep&& LoopRep == MLI->getLoopFor(Src2MBB)) {
1182 MachineBasicBlock *&TheEntry = LLInfoMap[LoopRep];
1185 dbgs() << "isLoopContBreakBlock yes src1 = BB"
1186 << Src1MBB->getNumber()
1187 << " src2 = BB" << Src2MBB->getNumber() << "\n";
1196 int AMDGPUCFGStructurizer::handleJumpintoIf(MachineBasicBlock *HeadMBB,
1197 MachineBasicBlock *TrueMBB, MachineBasicBlock *FalseMBB) {
1198 int Num = handleJumpintoIfImp(HeadMBB, TrueMBB, FalseMBB);
1201 dbgs() << "handleJumpintoIf swap trueBlk and FalseBlk" << "\n";
1203 Num = handleJumpintoIfImp(HeadMBB, FalseMBB, TrueMBB);
1208 int AMDGPUCFGStructurizer::handleJumpintoIfImp(MachineBasicBlock *HeadMBB,
1209 MachineBasicBlock *TrueMBB, MachineBasicBlock *FalseMBB) {
1211 MachineBasicBlock *DownBlk;
1213 //trueBlk could be the common post dominator
1217 dbgs() << "handleJumpintoIfImp head = BB" << HeadMBB->getNumber()
1218 << " true = BB" << TrueMBB->getNumber()
1219 << ", numSucc=" << TrueMBB->succ_size()
1220 << " false = BB" << FalseMBB->getNumber() << "\n";
1225 dbgs() << "check down = BB" << DownBlk->getNumber();
1228 if (singlePathTo(FalseMBB, DownBlk) == SinglePath_InPath) {
1230 dbgs() << " working\n";
1233 Num += cloneOnSideEntryTo(HeadMBB, TrueMBB, DownBlk);
1234 Num += cloneOnSideEntryTo(HeadMBB, FalseMBB, DownBlk);
1236 numClonedBlock += Num;
1237 Num += serialPatternMatch(*HeadMBB->succ_begin());
1238 Num += serialPatternMatch(*std::next(HeadMBB->succ_begin()));
1239 Num += ifPatternMatch(HeadMBB);
1245 dbgs() << " not working\n";
1247 DownBlk = (DownBlk->succ_size() == 1) ? (*DownBlk->succ_begin()) : nullptr;
1248 } // walk down the postDomTree
1253 void AMDGPUCFGStructurizer::showImproveSimpleJumpintoIf(
1254 MachineBasicBlock *HeadMBB, MachineBasicBlock *TrueMBB,
1255 MachineBasicBlock *FalseMBB, MachineBasicBlock *LandMBB, bool Detail) {
1256 dbgs() << "head = BB" << HeadMBB->getNumber()
1257 << " size = " << HeadMBB->size();
1260 HeadMBB->print(dbgs());
1265 dbgs() << ", true = BB" << TrueMBB->getNumber() << " size = "
1266 << TrueMBB->size() << " numPred = " << TrueMBB->pred_size();
1269 TrueMBB->print(dbgs());
1274 dbgs() << ", false = BB" << FalseMBB->getNumber() << " size = "
1275 << FalseMBB->size() << " numPred = " << FalseMBB->pred_size();
1278 FalseMBB->print(dbgs());
1283 dbgs() << ", land = BB" << LandMBB->getNumber() << " size = "
1284 << LandMBB->size() << " numPred = " << LandMBB->pred_size();
1287 LandMBB->print(dbgs());
1295 int AMDGPUCFGStructurizer::improveSimpleJumpintoIf(MachineBasicBlock *HeadMBB,
1296 MachineBasicBlock *TrueMBB, MachineBasicBlock *FalseMBB,
1297 MachineBasicBlock **LandMBBPtr) {
1298 bool MigrateTrue = false;
1299 bool MigrateFalse = false;
1301 MachineBasicBlock *LandBlk = *LandMBBPtr;
1303 assert((!TrueMBB || TrueMBB->succ_size() <= 1)
1304 && (!FalseMBB || FalseMBB->succ_size() <= 1));
1306 if (TrueMBB == FalseMBB)
1309 MigrateTrue = needMigrateBlock(TrueMBB);
1310 MigrateFalse = needMigrateBlock(FalseMBB);
1312 if (!MigrateTrue && !MigrateFalse)
1315 // If we need to migrate either trueBlk and falseBlk, migrate the rest that
1316 // have more than one predecessors. without doing this, its predecessor
1317 // rather than headBlk will have undefined value in initReg.
1318 if (!MigrateTrue && TrueMBB && TrueMBB->pred_size() > 1)
1320 if (!MigrateFalse && FalseMBB && FalseMBB->pred_size() > 1)
1321 MigrateFalse = true;
1324 dbgs() << "before improveSimpleJumpintoIf: ";
1325 showImproveSimpleJumpintoIf(HeadMBB, TrueMBB, FalseMBB, LandBlk, 0);
1328 // org: headBlk => if () {trueBlk} else {falseBlk} => landBlk
1330 // new: headBlk => if () {initReg = 1; org trueBlk branch} else
1331 // {initReg = 0; org falseBlk branch }
1332 // => landBlk => if (initReg) {org trueBlk} else {org falseBlk}
1334 // if landBlk->pred_size() > 2, put the about if-else inside
1335 // if (initReg !=2) {...}
1337 // add initReg = initVal to headBlk
1339 const TargetRegisterClass * I32RC = TRI->getCFGStructurizerRegClass(MVT::i32);
1340 if (!MigrateTrue || !MigrateFalse) {
1341 // XXX: We have an opportunity here to optimize the "branch into if" case
1342 // here. Branch into if looks like this:
1345 // diamond_head branch_from
1347 // diamond_false diamond_true
1351 // The diamond_head block begins the "if" and the diamond_true block
1352 // is the block being "branched into".
1354 // If MigrateTrue is true, then TrueBB is the block being "branched into"
1355 // and if MigrateFalse is true, then FalseBB is the block being
1358 // Here is the pseudo code for how I think the optimization should work:
1359 // 1. Insert MOV GPR0, 0 before the branch instruction in diamond_head.
1360 // 2. Insert MOV GPR0, 1 before the branch instruction in branch_from.
1361 // 3. Move the branch instruction from diamond_head into its own basic
1362 // block (new_block).
1363 // 4. Add an unconditional branch from diamond_head to new_block
1364 // 5. Replace the branch instruction in branch_from with an unconditional
1365 // branch to new_block. If branch_from has multiple predecessors, then
1366 // we need to replace the True/False block in the branch
1367 // instruction instead of replacing it.
1368 // 6. Change the condition of the branch instruction in new_block from
1369 // COND to (COND || GPR0)
1371 // In order insert these MOV instruction, we will need to use the
1372 // RegisterScavenger. Usually liveness stops being tracked during
1373 // the late machine optimization passes, however if we implement
1374 // bool TargetRegisterInfo::requiresRegisterScavenging(
1375 // const MachineFunction &MF)
1376 // and have it return true, liveness will be tracked correctly
1377 // by generic optimization passes. We will also need to make sure that
1378 // all of our target-specific passes that run after regalloc and before
1379 // the CFGStructurizer track liveness and we will need to modify this pass
1380 // to correctly track liveness.
1382 // After the above changes, the new CFG should look like this:
1385 // diamond_head branch_from
1389 // diamond_false diamond_true
1393 // Without this optimization, we are forced to duplicate the diamond_true
1394 // block and we will end up with a CFG like this:
1398 // diamond_head branch_from
1400 // diamond_false diamond_true diamond_true (duplicate)
1402 // done --------------------|
1404 // Duplicating diamond_true can be very costly especially if it has a
1405 // lot of instructions.
1411 bool LandBlkHasOtherPred = (LandBlk->pred_size() > 2);
1413 //insert AMDGPU::ENDIF to avoid special case "input landBlk == NULL"
1414 MachineBasicBlock::iterator I = insertInstrBefore(LandBlk, AMDGPU::ENDIF);
1416 if (LandBlkHasOtherPred) {
1417 llvm_unreachable("Extra register needed to handle CFG");
1418 unsigned CmpResReg =
1419 HeadMBB->getParent()->getRegInfo().createVirtualRegister(I32RC);
1420 llvm_unreachable("Extra compare instruction needed to handle CFG");
1421 insertCondBranchBefore(LandBlk, I, AMDGPU::IF_PREDICATE_SET,
1422 CmpResReg, DebugLoc());
1425 // XXX: We are running this after RA, so creating virtual registers will
1426 // cause an assertion failure in the PostRA scheduling pass.
1428 HeadMBB->getParent()->getRegInfo().createVirtualRegister(I32RC);
1429 insertCondBranchBefore(LandBlk, I, AMDGPU::IF_PREDICATE_SET, InitReg,
1433 migrateInstruction(TrueMBB, LandBlk, I);
1434 // need to uncondionally insert the assignment to ensure a path from its
1435 // predecessor rather than headBlk has valid value in initReg if
1437 llvm_unreachable("Extra register needed to handle CFG");
1439 insertInstrBefore(I, AMDGPU::ELSE);
1442 migrateInstruction(FalseMBB, LandBlk, I);
1443 // need to uncondionally insert the assignment to ensure a path from its
1444 // predecessor rather than headBlk has valid value in initReg if
1446 llvm_unreachable("Extra register needed to handle CFG");
1449 if (LandBlkHasOtherPred) {
1451 insertInstrBefore(I, AMDGPU::ENDIF);
1453 // put initReg = 2 to other predecessors of landBlk
1454 for (MachineBasicBlock::pred_iterator PI = LandBlk->pred_begin(),
1455 PE = LandBlk->pred_end(); PI != PE; ++PI) {
1456 MachineBasicBlock *MBB = *PI;
1457 if (MBB != TrueMBB && MBB != FalseMBB)
1458 llvm_unreachable("Extra register needed to handle CFG");
1462 dbgs() << "result from improveSimpleJumpintoIf: ";
1463 showImproveSimpleJumpintoIf(HeadMBB, TrueMBB, FalseMBB, LandBlk, 0);
1467 *LandMBBPtr = LandBlk;
1472 void AMDGPUCFGStructurizer::handleLoopcontBlock(MachineBasicBlock *ContingMBB,
1473 MachineLoop *ContingLoop, MachineBasicBlock *ContMBB,
1474 MachineLoop *ContLoop) {
1475 DEBUG(dbgs() << "loopcontPattern cont = BB" << ContingMBB->getNumber()
1476 << " header = BB" << ContMBB->getNumber() << "\n";
1477 dbgs() << "Trying to continue loop-depth = "
1478 << getLoopDepth(ContLoop)
1479 << " from loop-depth = " << getLoopDepth(ContingLoop) << "\n";);
1480 settleLoopcontBlock(ContingMBB, ContMBB);
1483 void AMDGPUCFGStructurizer::mergeSerialBlock(MachineBasicBlock *DstMBB,
1484 MachineBasicBlock *SrcMBB) {
1486 dbgs() << "serialPattern BB" << DstMBB->getNumber()
1487 << " <= BB" << SrcMBB->getNumber() << "\n";
1489 DstMBB->splice(DstMBB->end(), SrcMBB, SrcMBB->begin(), SrcMBB->end());
1491 DstMBB->removeSuccessor(SrcMBB);
1492 cloneSuccessorList(DstMBB, SrcMBB);
1494 removeSuccessor(SrcMBB);
1495 MLI->removeBlock(SrcMBB);
1496 retireBlock(SrcMBB);
1499 void AMDGPUCFGStructurizer::mergeIfthenelseBlock(MachineInstr *BranchMI,
1500 MachineBasicBlock *MBB, MachineBasicBlock *TrueMBB,
1501 MachineBasicBlock *FalseMBB, MachineBasicBlock *LandMBB) {
1504 dbgs() << "ifPattern BB" << MBB->getNumber();
1507 dbgs() << "BB" << TrueMBB->getNumber();
1509 dbgs() << " } else ";
1512 dbgs() << "BB" << FalseMBB->getNumber();
1515 dbgs() << "landBlock: ";
1519 dbgs() << "BB" << LandMBB->getNumber();
1524 int OldOpcode = BranchMI->getOpcode();
1525 DebugLoc BranchDL = BranchMI->getDebugLoc();
1535 MachineBasicBlock::iterator I = BranchMI;
1536 insertCondBranchBefore(I, getBranchNzeroOpcode(OldOpcode),
1540 MBB->splice(I, TrueMBB, TrueMBB->begin(), TrueMBB->end());
1541 MBB->removeSuccessor(TrueMBB);
1542 if (LandMBB && TrueMBB->succ_size()!=0)
1543 TrueMBB->removeSuccessor(LandMBB);
1544 retireBlock(TrueMBB);
1545 MLI->removeBlock(TrueMBB);
1549 insertInstrBefore(I, AMDGPU::ELSE);
1550 MBB->splice(I, FalseMBB, FalseMBB->begin(),
1552 MBB->removeSuccessor(FalseMBB);
1553 if (LandMBB && FalseMBB->succ_size() != 0)
1554 FalseMBB->removeSuccessor(LandMBB);
1555 retireBlock(FalseMBB);
1556 MLI->removeBlock(FalseMBB);
1558 insertInstrBefore(I, AMDGPU::ENDIF);
1560 BranchMI->eraseFromParent();
1562 if (LandMBB && TrueMBB && FalseMBB)
1563 MBB->addSuccessor(LandMBB);
1567 void AMDGPUCFGStructurizer::mergeLooplandBlock(MachineBasicBlock *DstBlk,
1568 MachineBasicBlock *LandMBB) {
1569 DEBUG(dbgs() << "loopPattern header = BB" << DstBlk->getNumber()
1570 << " land = BB" << LandMBB->getNumber() << "\n";);
1572 insertInstrBefore(DstBlk, AMDGPU::WHILELOOP, DebugLoc());
1573 insertInstrEnd(DstBlk, AMDGPU::ENDLOOP, DebugLoc());
1574 DstBlk->addSuccessor(LandMBB);
1575 DstBlk->removeSuccessor(DstBlk);
1579 void AMDGPUCFGStructurizer::mergeLoopbreakBlock(MachineBasicBlock *ExitingMBB,
1580 MachineBasicBlock *LandMBB) {
1581 DEBUG(dbgs() << "loopbreakPattern exiting = BB" << ExitingMBB->getNumber()
1582 << " land = BB" << LandMBB->getNumber() << "\n";);
1583 MachineInstr *BranchMI = getLoopendBlockBranchInstr(ExitingMBB);
1584 assert(BranchMI && isCondBranch(BranchMI));
1585 DebugLoc DL = BranchMI->getDebugLoc();
1586 MachineBasicBlock *TrueBranch = getTrueBranch(BranchMI);
1587 MachineBasicBlock::iterator I = BranchMI;
1588 if (TrueBranch != LandMBB)
1589 reversePredicateSetter(I);
1590 insertCondBranchBefore(ExitingMBB, I, AMDGPU::IF_PREDICATE_SET, AMDGPU::PREDICATE_BIT, DL);
1591 insertInstrBefore(I, AMDGPU::BREAK);
1592 insertInstrBefore(I, AMDGPU::ENDIF);
1593 //now branchInst can be erase safely
1594 BranchMI->eraseFromParent();
1595 //now take care of successors, retire blocks
1596 ExitingMBB->removeSuccessor(LandMBB);
1599 void AMDGPUCFGStructurizer::settleLoopcontBlock(MachineBasicBlock *ContingMBB,
1600 MachineBasicBlock *ContMBB) {
1601 DEBUG(dbgs() << "settleLoopcontBlock conting = BB"
1602 << ContingMBB->getNumber()
1603 << ", cont = BB" << ContMBB->getNumber() << "\n";);
1605 MachineInstr *MI = getLoopendBlockBranchInstr(ContingMBB);
1607 assert(isCondBranch(MI));
1608 MachineBasicBlock::iterator I = MI;
1609 MachineBasicBlock *TrueBranch = getTrueBranch(MI);
1610 int OldOpcode = MI->getOpcode();
1611 DebugLoc DL = MI->getDebugLoc();
1613 bool UseContinueLogical = ((&*ContingMBB->rbegin()) == MI);
1615 if (UseContinueLogical == false) {
1617 TrueBranch == ContMBB ? getBranchNzeroOpcode(OldOpcode) :
1618 getBranchZeroOpcode(OldOpcode);
1619 insertCondBranchBefore(I, BranchOpcode, DL);
1620 // insertEnd to ensure phi-moves, if exist, go before the continue-instr.
1621 insertInstrEnd(ContingMBB, AMDGPU::CONTINUE, DL);
1622 insertInstrEnd(ContingMBB, AMDGPU::ENDIF, DL);
1625 TrueBranch == ContMBB ? getContinueNzeroOpcode(OldOpcode) :
1626 getContinueZeroOpcode(OldOpcode);
1627 insertCondBranchBefore(I, BranchOpcode, DL);
1630 MI->eraseFromParent();
1632 // if we've arrived here then we've already erased the branch instruction
1633 // travel back up the basic block to see the last reference of our debug
1634 // location we've just inserted that reference here so it should be
1635 // representative insertEnd to ensure phi-moves, if exist, go before the
1637 insertInstrEnd(ContingMBB, AMDGPU::CONTINUE,
1638 getLastDebugLocInBB(ContingMBB));
1642 int AMDGPUCFGStructurizer::cloneOnSideEntryTo(MachineBasicBlock *PreMBB,
1643 MachineBasicBlock *SrcMBB, MachineBasicBlock *DstMBB) {
1645 assert(PreMBB->isSuccessor(SrcMBB));
1646 while (SrcMBB && SrcMBB != DstMBB) {
1647 assert(SrcMBB->succ_size() == 1);
1648 if (SrcMBB->pred_size() > 1) {
1649 SrcMBB = cloneBlockForPredecessor(SrcMBB, PreMBB);
1654 SrcMBB = *SrcMBB->succ_begin();
1661 AMDGPUCFGStructurizer::cloneBlockForPredecessor(MachineBasicBlock *MBB,
1662 MachineBasicBlock *PredMBB) {
1663 assert(PredMBB->isSuccessor(MBB) &&
1664 "succBlk is not a prececessor of curBlk");
1666 MachineBasicBlock *CloneMBB = clone(MBB); //clone instructions
1667 replaceInstrUseOfBlockWith(PredMBB, MBB, CloneMBB);
1668 //srcBlk, oldBlk, newBlk
1670 PredMBB->removeSuccessor(MBB);
1671 PredMBB->addSuccessor(CloneMBB);
1673 // add all successor to cloneBlk
1674 cloneSuccessorList(CloneMBB, MBB);
1676 numClonedInstr += MBB->size();
1679 dbgs() << "Cloned block: " << "BB"
1680 << MBB->getNumber() << "size " << MBB->size() << "\n";
1683 SHOWNEWBLK(CloneMBB, "result of Cloned block: ");
1688 void AMDGPUCFGStructurizer::migrateInstruction(MachineBasicBlock *SrcMBB,
1689 MachineBasicBlock *DstMBB, MachineBasicBlock::iterator I) {
1690 MachineBasicBlock::iterator SpliceEnd;
1691 //look for the input branchinstr, not the AMDGPU branchinstr
1692 MachineInstr *BranchMI = getNormalBlockBranchInstr(SrcMBB);
1695 dbgs() << "migrateInstruction don't see branch instr\n" ;
1697 SpliceEnd = SrcMBB->end();
1700 dbgs() << "migrateInstruction see branch instr\n" ;
1703 SpliceEnd = BranchMI;
1706 dbgs() << "migrateInstruction before splice dstSize = " << DstMBB->size()
1707 << "srcSize = " << SrcMBB->size() << "\n";
1710 //splice insert before insertPos
1711 DstMBB->splice(I, SrcMBB, SrcMBB->begin(), SpliceEnd);
1714 dbgs() << "migrateInstruction after splice dstSize = " << DstMBB->size()
1715 << "srcSize = " << SrcMBB->size() << "\n";
1720 AMDGPUCFGStructurizer::normalizeInfiniteLoopExit(MachineLoop* LoopRep) {
1721 MachineBasicBlock *LoopHeader = LoopRep->getHeader();
1722 MachineBasicBlock *LoopLatch = LoopRep->getLoopLatch();
1723 const TargetRegisterClass * I32RC = TRI->getCFGStructurizerRegClass(MVT::i32);
1725 if (!LoopHeader || !LoopLatch)
1727 MachineInstr *BranchMI = getLoopendBlockBranchInstr(LoopLatch);
1728 // Is LoopRep an infinite loop ?
1729 if (!BranchMI || !isUncondBranch(BranchMI))
1732 MachineBasicBlock *DummyExitBlk = FuncRep->CreateMachineBasicBlock();
1733 FuncRep->push_back(DummyExitBlk); //insert to function
1734 SHOWNEWBLK(DummyExitBlk, "DummyExitBlock to normalize infiniteLoop: ");
1735 DEBUG(dbgs() << "Old branch instr: " << *BranchMI << "\n";);
1736 MachineBasicBlock::iterator I = BranchMI;
1737 unsigned ImmReg = FuncRep->getRegInfo().createVirtualRegister(I32RC);
1738 llvm_unreachable("Extra register needed to handle CFG");
1739 MachineInstr *NewMI = insertInstrBefore(I, AMDGPU::BRANCH_COND_i32);
1740 MachineInstrBuilder MIB(*FuncRep, NewMI);
1741 MIB.addMBB(LoopHeader);
1742 MIB.addReg(ImmReg, false);
1743 SHOWNEWINSTR(NewMI);
1744 BranchMI->eraseFromParent();
1745 LoopLatch->addSuccessor(DummyExitBlk);
1747 return DummyExitBlk;
1750 void AMDGPUCFGStructurizer::removeUnconditionalBranch(MachineBasicBlock *MBB) {
1751 MachineInstr *BranchMI;
1753 // I saw two unconditional branch in one basic block in example
1754 // test_fc_do_while_or.c need to fix the upstream on this to remove the loop.
1755 while ((BranchMI = getLoopendBlockBranchInstr(MBB))
1756 && isUncondBranch(BranchMI)) {
1757 DEBUG(dbgs() << "Removing uncond branch instr"; BranchMI->dump(););
1758 BranchMI->eraseFromParent();
1762 void AMDGPUCFGStructurizer::removeRedundantConditionalBranch(
1763 MachineBasicBlock *MBB) {
1764 if (MBB->succ_size() != 2)
1766 MachineBasicBlock *MBB1 = *MBB->succ_begin();
1767 MachineBasicBlock *MBB2 = *std::next(MBB->succ_begin());
1771 MachineInstr *BranchMI = getNormalBlockBranchInstr(MBB);
1772 assert(BranchMI && isCondBranch(BranchMI));
1773 DEBUG(dbgs() << "Removing unneeded cond branch instr"; BranchMI->dump(););
1774 BranchMI->eraseFromParent();
1775 SHOWNEWBLK(MBB1, "Removing redundant successor");
1776 MBB->removeSuccessor(MBB1);
1779 void AMDGPUCFGStructurizer::addDummyExitBlock(
1780 SmallVectorImpl<MachineBasicBlock*> &RetMBB) {
1781 MachineBasicBlock *DummyExitBlk = FuncRep->CreateMachineBasicBlock();
1782 FuncRep->push_back(DummyExitBlk); //insert to function
1783 insertInstrEnd(DummyExitBlk, AMDGPU::RETURN);
1785 for (SmallVectorImpl<MachineBasicBlock *>::iterator It = RetMBB.begin(),
1786 E = RetMBB.end(); It != E; ++It) {
1787 MachineBasicBlock *MBB = *It;
1788 MachineInstr *MI = getReturnInstr(MBB);
1790 MI->eraseFromParent();
1791 MBB->addSuccessor(DummyExitBlk);
1793 dbgs() << "Add dummyExitBlock to BB" << MBB->getNumber()
1797 SHOWNEWBLK(DummyExitBlk, "DummyExitBlock: ");
1800 void AMDGPUCFGStructurizer::removeSuccessor(MachineBasicBlock *MBB) {
1801 while (MBB->succ_size())
1802 MBB->removeSuccessor(*MBB->succ_begin());
1805 void AMDGPUCFGStructurizer::recordSccnum(MachineBasicBlock *MBB,
1807 BlockInformation *&srcBlkInfo = BlockInfoMap[MBB];
1809 srcBlkInfo = new BlockInformation();
1810 srcBlkInfo->SccNum = SccNum;
1813 void AMDGPUCFGStructurizer::retireBlock(MachineBasicBlock *MBB) {
1815 dbgs() << "Retiring BB" << MBB->getNumber() << "\n";
1818 BlockInformation *&SrcBlkInfo = BlockInfoMap[MBB];
1821 SrcBlkInfo = new BlockInformation();
1823 SrcBlkInfo->IsRetired = true;
1824 assert(MBB->succ_size() == 0 && MBB->pred_size() == 0
1825 && "can't retire block yet");
1828 void AMDGPUCFGStructurizer::setLoopLandBlock(MachineLoop *loopRep,
1829 MachineBasicBlock *MBB) {
1830 MachineBasicBlock *&TheEntry = LLInfoMap[loopRep];
1832 MBB = FuncRep->CreateMachineBasicBlock();
1833 FuncRep->push_back(MBB); //insert to function
1834 SHOWNEWBLK(MBB, "DummyLandingBlock for loop without break: ");
1838 dbgs() << "setLoopLandBlock loop-header = BB"
1839 << loopRep->getHeader()->getNumber()
1840 << " landing-block = BB" << MBB->getNumber() << "\n";
1845 AMDGPUCFGStructurizer::findNearestCommonPostDom(MachineBasicBlock *MBB1,
1846 MachineBasicBlock *MBB2) {
1848 if (PDT->dominates(MBB1, MBB2))
1850 if (PDT->dominates(MBB2, MBB1))
1853 MachineDomTreeNode *Node1 = PDT->getNode(MBB1);
1854 MachineDomTreeNode *Node2 = PDT->getNode(MBB2);
1856 // Handle newly cloned node.
1857 if (!Node1 && MBB1->succ_size() == 1)
1858 return findNearestCommonPostDom(*MBB1->succ_begin(), MBB2);
1859 if (!Node2 && MBB2->succ_size() == 1)
1860 return findNearestCommonPostDom(MBB1, *MBB2->succ_begin());
1862 if (!Node1 || !Node2)
1865 Node1 = Node1->getIDom();
1867 if (PDT->dominates(Node1, Node2))
1868 return Node1->getBlock();
1869 Node1 = Node1->getIDom();
1876 AMDGPUCFGStructurizer::findNearestCommonPostDom(
1877 std::set<MachineBasicBlock *> &MBBs) {
1878 MachineBasicBlock *CommonDom;
1879 std::set<MachineBasicBlock *>::const_iterator It = MBBs.begin();
1880 std::set<MachineBasicBlock *>::const_iterator E = MBBs.end();
1881 for (CommonDom = *It; It != E && CommonDom; ++It) {
1882 MachineBasicBlock *MBB = *It;
1883 if (MBB != CommonDom)
1884 CommonDom = findNearestCommonPostDom(MBB, CommonDom);
1888 dbgs() << "Common post dominator for exit blocks is ";
1890 dbgs() << "BB" << CommonDom->getNumber() << "\n";
1898 char AMDGPUCFGStructurizer::ID = 0;
1900 } // end anonymous namespace
1903 INITIALIZE_PASS_BEGIN(AMDGPUCFGStructurizer, "amdgpustructurizer",
1904 "AMDGPU CFG Structurizer", false, false)
1905 INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
1906 INITIALIZE_PASS_DEPENDENCY(MachinePostDominatorTree)
1907 INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo)
1908 INITIALIZE_PASS_END(AMDGPUCFGStructurizer, "amdgpustructurizer",
1909 "AMDGPU CFG Structurizer", false, false)
1911 FunctionPass *llvm::createAMDGPUCFGStructurizerPass() {
1912 return new AMDGPUCFGStructurizer();