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 //==-----------------------------------------------------------------------===//
11 #define DEBUG_TYPE "structcfg"
14 #include "AMDGPUInstrInfo.h"
15 #include "R600InstrInfo.h"
16 #include "llvm/Support/Debug.h"
17 #include "llvm/Support/raw_ostream.h"
18 #include "llvm/ADT/SCCIterator.h"
19 #include "llvm/ADT/SmallVector.h"
20 #include "llvm/ADT/Statistic.h"
21 #include "llvm/ADT/DepthFirstIterator.h"
22 #include "llvm/Analysis/DominatorInternals.h"
23 #include "llvm/Analysis/Dominators.h"
24 #include "llvm/CodeGen/MachineDominators.h"
25 #include "llvm/CodeGen/MachineFunction.h"
26 #include "llvm/CodeGen/MachineFunctionAnalysis.h"
27 #include "llvm/CodeGen/MachineFunctionPass.h"
28 #include "llvm/CodeGen/MachineInstrBuilder.h"
29 #include "llvm/CodeGen/MachineJumpTableInfo.h"
30 #include "llvm/CodeGen/MachineLoopInfo.h"
31 #include "llvm/CodeGen/MachinePostDominators.h"
32 #include "llvm/CodeGen/MachineRegisterInfo.h"
33 #include "llvm/Target/TargetInstrInfo.h"
34 #include "llvm/Target/TargetMachine.h"
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");
57 //===----------------------------------------------------------------------===//
59 // Miscellaneous utility for CFGStructurizer.
61 //===----------------------------------------------------------------------===//
63 #define SHOWNEWINSTR(i) \
64 DEBUG(dbgs() << "New instr: " << *i << "\n");
66 #define SHOWNEWBLK(b, msg) \
68 dbgs() << msg << "BB" << b->getNumber() << "size " << b->size(); \
72 #define SHOWBLK_DETAIL(b, msg) \
75 dbgs() << msg << "BB" << b->getNumber() << "size " << b->size(); \
81 #define INVALIDSCCNUM -1
84 void ReverseVector(SmallVectorImpl<NodeT *> &Src) {
85 size_t sz = Src.size();
86 for (size_t i = 0; i < sz/2; ++i) {
88 Src[i] = Src[sz - i - 1];
93 } // end anonymous namespace
95 //===----------------------------------------------------------------------===//
97 // supporting data structure for CFGStructurizer
99 //===----------------------------------------------------------------------===//
104 class BlockInformation {
108 BlockInformation() : IsRetired(false), SccNum(INVALIDSCCNUM) {}
111 } // end anonymous namespace
113 //===----------------------------------------------------------------------===//
117 //===----------------------------------------------------------------------===//
120 class AMDGPUCFGStructurizer : public MachineFunctionPass {
122 typedef SmallVector<MachineBasicBlock *, 32> MBBVector;
123 typedef std::map<MachineBasicBlock *, BlockInformation *> MBBInfoMap;
124 typedef std::map<MachineLoop *, MachineBasicBlock *> LoopLandInfoMap;
128 SinglePath_InPath = 1,
129 SinglePath_NotInPath = 2
134 AMDGPUCFGStructurizer(TargetMachine &tm) :
135 MachineFunctionPass(ID), TM(tm),
136 TII(static_cast<const R600InstrInfo *>(tm.getInstrInfo())),
137 TRI(&TII->getRegisterInfo()) { }
139 const char *getPassName() const {
140 return "AMD IL Control Flow Graph structurizer Pass";
143 void getAnalysisUsage(AnalysisUsage &AU) const {
144 AU.addPreserved<MachineFunctionAnalysis>();
145 AU.addRequired<MachineFunctionAnalysis>();
146 AU.addRequired<MachineDominatorTree>();
147 AU.addRequired<MachinePostDominatorTree>();
148 AU.addRequired<MachineLoopInfo>();
151 /// Perform the CFG structurization
154 /// Perform the CFG preparation
155 /// This step will remove every unconditionnal/dead jump instructions and make
156 /// sure all loops have an exit block
159 bool runOnMachineFunction(MachineFunction &MF) {
163 MLI = &getAnalysis<MachineLoopInfo>();
164 DEBUG(dbgs() << "LoopInfo:\n"; PrintLoopinfo(*MLI););
165 MDT = &getAnalysis<MachineDominatorTree>();
166 DEBUG(MDT->print(dbgs(), (const llvm::Module*)0););
167 PDT = &getAnalysis<MachinePostDominatorTree>();
168 DEBUG(PDT->print(dbgs()););
177 MachineDominatorTree *MDT;
178 MachinePostDominatorTree *PDT;
179 MachineLoopInfo *MLI;
180 const R600InstrInfo *TII;
181 const AMDGPURegisterInfo *TRI;
184 /// Print the ordered Blocks.
185 void printOrderedBlocks() const {
187 for (MBBVector::const_iterator iterBlk = OrderedBlks.begin(),
188 iterBlkEnd = OrderedBlks.end(); iterBlk != iterBlkEnd; ++iterBlk, ++i) {
189 dbgs() << "BB" << (*iterBlk)->getNumber();
190 dbgs() << "(" << getSCCNum(*iterBlk) << "," << (*iterBlk)->size() << ")";
191 if (i != 0 && i % 10 == 0) {
198 static void PrintLoopinfo(const MachineLoopInfo &LoopInfo) {
199 for (MachineLoop::iterator iter = LoopInfo.begin(),
200 iterEnd = LoopInfo.end(); iter != iterEnd; ++iter) {
201 (*iter)->print(dbgs(), 0);
206 int getSCCNum(MachineBasicBlock *MBB) const;
207 MachineBasicBlock *getLoopLandInfo(MachineLoop *LoopRep) const;
208 bool hasBackEdge(MachineBasicBlock *MBB) const;
209 static unsigned getLoopDepth(MachineLoop *LoopRep);
210 bool isRetiredBlock(MachineBasicBlock *MBB) const;
211 bool isActiveLoophead(MachineBasicBlock *MBB) const;
212 PathToKind singlePathTo(MachineBasicBlock *SrcMBB, MachineBasicBlock *DstMBB,
213 bool AllowSideEntry = true) const;
214 int countActiveBlock(MBBVector::const_iterator It,
215 MBBVector::const_iterator E) const;
216 bool needMigrateBlock(MachineBasicBlock *MBB) const;
219 void reversePredicateSetter(MachineBasicBlock::iterator I);
220 /// Compute the reversed DFS post order of Blocks
221 void orderBlocks(MachineFunction *MF);
223 // Function originaly from CFGStructTraits
224 void insertInstrEnd(MachineBasicBlock *MBB, int NewOpcode,
225 DebugLoc DL = DebugLoc());
226 MachineInstr *insertInstrBefore(MachineBasicBlock *MBB, int NewOpcode,
227 DebugLoc DL = DebugLoc());
228 MachineInstr *insertInstrBefore(MachineBasicBlock::iterator I, int NewOpcode);
229 void insertCondBranchBefore(MachineBasicBlock::iterator I, int NewOpcode,
231 void insertCondBranchBefore(MachineBasicBlock *MBB,
232 MachineBasicBlock::iterator I, int NewOpcode, int RegNum,
234 void insertCondBranchEnd(MachineBasicBlock *MBB, int NewOpcode, int RegNum);
235 static int getBranchNzeroOpcode(int OldOpcode);
236 static int getBranchZeroOpcode(int OldOpcode);
237 static int getContinueNzeroOpcode(int OldOpcode);
238 static int getContinueZeroOpcode(int OldOpcode);
239 static MachineBasicBlock *getTrueBranch(MachineInstr *MI);
240 static void setTrueBranch(MachineInstr *MI, MachineBasicBlock *MBB);
241 static MachineBasicBlock *getFalseBranch(MachineBasicBlock *MBB,
243 static bool isCondBranch(MachineInstr *MI);
244 static bool isUncondBranch(MachineInstr *MI);
245 static DebugLoc getLastDebugLocInBB(MachineBasicBlock *MBB);
246 static MachineInstr *getNormalBlockBranchInstr(MachineBasicBlock *MBB);
247 /// The correct naming for this is getPossibleLoopendBlockBranchInstr.
249 /// BB with backward-edge could have move instructions after the branch
250 /// instruction. Such move instruction "belong to" the loop backward-edge.
251 MachineInstr *getLoopendBlockBranchInstr(MachineBasicBlock *MBB);
252 static MachineInstr *getReturnInstr(MachineBasicBlock *MBB);
253 static MachineInstr *getContinueInstr(MachineBasicBlock *MBB);
254 static MachineInstr *getLoopBreakInstr(MachineBasicBlock *MBB);
255 static bool isReturnBlock(MachineBasicBlock *MBB);
256 static void cloneSuccessorList(MachineBasicBlock *DstMBB,
257 MachineBasicBlock *SrcMBB) ;
258 static MachineBasicBlock *clone(MachineBasicBlock *MBB);
259 /// MachineBasicBlock::ReplaceUsesOfBlockWith doesn't serve the purpose
260 /// because the AMDGPU instruction is not recognized as terminator fix this
261 /// and retire this routine
262 void replaceInstrUseOfBlockWith(MachineBasicBlock *SrcMBB,
263 MachineBasicBlock *OldMBB, MachineBasicBlock *NewBlk);
264 static void wrapup(MachineBasicBlock *MBB);
267 int patternMatch(MachineBasicBlock *MBB);
268 int patternMatchGroup(MachineBasicBlock *MBB);
269 int serialPatternMatch(MachineBasicBlock *MBB);
270 int ifPatternMatch(MachineBasicBlock *MBB);
271 int loopendPatternMatch();
272 int mergeLoop(MachineLoop *LoopRep);
273 int loopcontPatternMatch(MachineLoop *LoopRep, MachineBasicBlock *LoopHeader);
275 void handleLoopcontBlock(MachineBasicBlock *ContingMBB,
276 MachineLoop *ContingLoop, MachineBasicBlock *ContMBB,
277 MachineLoop *ContLoop);
278 /// return true iff src1Blk->succ_size() == 0 && src1Blk and src2Blk are in
279 /// the same loop with LoopLandInfo without explicitly keeping track of
280 /// loopContBlks and loopBreakBlks, this is a method to get the information.
281 bool isSameloopDetachedContbreak(MachineBasicBlock *Src1MBB,
282 MachineBasicBlock *Src2MBB);
283 int handleJumpintoIf(MachineBasicBlock *HeadMBB,
284 MachineBasicBlock *TrueMBB, MachineBasicBlock *FalseMBB);
285 int handleJumpintoIfImp(MachineBasicBlock *HeadMBB,
286 MachineBasicBlock *TrueMBB, MachineBasicBlock *FalseMBB);
287 int improveSimpleJumpintoIf(MachineBasicBlock *HeadMBB,
288 MachineBasicBlock *TrueMBB, MachineBasicBlock *FalseMBB,
289 MachineBasicBlock **LandMBBPtr);
290 void showImproveSimpleJumpintoIf(MachineBasicBlock *HeadMBB,
291 MachineBasicBlock *TrueMBB, MachineBasicBlock *FalseMBB,
292 MachineBasicBlock *LandMBB, bool Detail = false);
293 int cloneOnSideEntryTo(MachineBasicBlock *PreMBB,
294 MachineBasicBlock *SrcMBB, MachineBasicBlock *DstMBB);
295 void mergeSerialBlock(MachineBasicBlock *DstMBB,
296 MachineBasicBlock *SrcMBB);
298 void mergeIfthenelseBlock(MachineInstr *BranchMI,
299 MachineBasicBlock *MBB, MachineBasicBlock *TrueMBB,
300 MachineBasicBlock *FalseMBB, MachineBasicBlock *LandMBB);
301 void mergeLooplandBlock(MachineBasicBlock *DstMBB,
302 MachineBasicBlock *LandMBB);
303 void mergeLoopbreakBlock(MachineBasicBlock *ExitingMBB,
304 MachineBasicBlock *LandMBB);
305 void settleLoopcontBlock(MachineBasicBlock *ContingMBB,
306 MachineBasicBlock *ContMBB);
307 /// normalizeInfiniteLoopExit change
309 /// uncond_br LoopHeader
313 /// cond_br 1 LoopHeader dummyExit
314 /// and return the newly added dummy exit block
315 MachineBasicBlock *normalizeInfiniteLoopExit(MachineLoop *LoopRep);
316 void removeUnconditionalBranch(MachineBasicBlock *MBB);
317 /// Remove duplicate branches instructions in a block.
322 /// is transformed to
325 void removeRedundantConditionalBranch(MachineBasicBlock *MBB);
326 void addDummyExitBlock(SmallVectorImpl<MachineBasicBlock *> &RetMBB);
327 void removeSuccessor(MachineBasicBlock *MBB);
328 MachineBasicBlock *cloneBlockForPredecessor(MachineBasicBlock *MBB,
329 MachineBasicBlock *PredMBB);
330 void migrateInstruction(MachineBasicBlock *SrcMBB,
331 MachineBasicBlock *DstMBB, MachineBasicBlock::iterator I);
332 void recordSccnum(MachineBasicBlock *MBB, int SCCNum);
333 void retireBlock(MachineBasicBlock *MBB);
334 void setLoopLandBlock(MachineLoop *LoopRep, MachineBasicBlock *MBB = NULL);
336 MachineBasicBlock *findNearestCommonPostDom(std::set<MachineBasicBlock *>&);
337 /// This is work around solution for findNearestCommonDominator not avaiable
338 /// to post dom a proper fix should go to Dominators.h.
339 MachineBasicBlock *findNearestCommonPostDom(MachineBasicBlock *MBB1,
340 MachineBasicBlock *MBB2);
343 MBBInfoMap BlockInfoMap;
344 LoopLandInfoMap LLInfoMap;
345 std::map<MachineLoop *, bool> Visited;
346 MachineFunction *FuncRep;
347 SmallVector<MachineBasicBlock *, DEFAULT_VEC_SLOTS> OrderedBlks;
350 int AMDGPUCFGStructurizer::getSCCNum(MachineBasicBlock *MBB) const {
351 MBBInfoMap::const_iterator It = BlockInfoMap.find(MBB);
352 if (It == BlockInfoMap.end())
353 return INVALIDSCCNUM;
354 return (*It).second->SccNum;
357 MachineBasicBlock *AMDGPUCFGStructurizer::getLoopLandInfo(MachineLoop *LoopRep)
359 LoopLandInfoMap::const_iterator It = LLInfoMap.find(LoopRep);
360 if (It == LLInfoMap.end())
365 bool AMDGPUCFGStructurizer::hasBackEdge(MachineBasicBlock *MBB) const {
366 MachineLoop *LoopRep = MLI->getLoopFor(MBB);
369 MachineBasicBlock *LoopHeader = LoopRep->getHeader();
370 return MBB->isSuccessor(LoopHeader);
373 unsigned AMDGPUCFGStructurizer::getLoopDepth(MachineLoop *LoopRep) {
374 return LoopRep ? LoopRep->getLoopDepth() : 0;
377 bool AMDGPUCFGStructurizer::isRetiredBlock(MachineBasicBlock *MBB) const {
378 MBBInfoMap::const_iterator It = BlockInfoMap.find(MBB);
379 if (It == BlockInfoMap.end())
381 return (*It).second->IsRetired;
384 bool AMDGPUCFGStructurizer::isActiveLoophead(MachineBasicBlock *MBB) const {
385 MachineLoop *LoopRep = MLI->getLoopFor(MBB);
386 while (LoopRep && LoopRep->getHeader() == MBB) {
387 MachineBasicBlock *LoopLand = getLoopLandInfo(LoopRep);
390 if (!isRetiredBlock(LoopLand))
392 LoopRep = LoopRep->getParentLoop();
396 AMDGPUCFGStructurizer::PathToKind AMDGPUCFGStructurizer::singlePathTo(
397 MachineBasicBlock *SrcMBB, MachineBasicBlock *DstMBB,
398 bool AllowSideEntry) const {
400 if (SrcMBB == DstMBB)
401 return SinglePath_InPath;
402 while (SrcMBB && SrcMBB->succ_size() == 1) {
403 SrcMBB = *SrcMBB->succ_begin();
404 if (SrcMBB == DstMBB)
405 return SinglePath_InPath;
406 if (!AllowSideEntry && SrcMBB->pred_size() > 1)
407 return Not_SinglePath;
409 if (SrcMBB && SrcMBB->succ_size()==0)
410 return SinglePath_NotInPath;
411 return Not_SinglePath;
414 int AMDGPUCFGStructurizer::countActiveBlock(MBBVector::const_iterator It,
415 MBBVector::const_iterator E) const {
418 if (!isRetiredBlock(*It))
425 bool AMDGPUCFGStructurizer::needMigrateBlock(MachineBasicBlock *MBB) const {
426 unsigned BlockSizeThreshold = 30;
427 unsigned CloneInstrThreshold = 100;
428 bool MultiplePreds = MBB && (MBB->pred_size() > 1);
432 unsigned BlkSize = MBB->size();
433 return ((BlkSize > BlockSizeThreshold) &&
434 (BlkSize * (MBB->pred_size() - 1) > CloneInstrThreshold));
437 void AMDGPUCFGStructurizer::reversePredicateSetter(
438 MachineBasicBlock::iterator I) {
440 if (I->getOpcode() == AMDGPU::PRED_X) {
441 switch (static_cast<MachineInstr *>(I)->getOperand(2).getImm()) {
442 case OPCODE_IS_ZERO_INT:
443 static_cast<MachineInstr *>(I)->getOperand(2)
444 .setImm(OPCODE_IS_NOT_ZERO_INT);
446 case OPCODE_IS_NOT_ZERO_INT:
447 static_cast<MachineInstr *>(I)->getOperand(2)
448 .setImm(OPCODE_IS_ZERO_INT);
451 static_cast<MachineInstr *>(I)->getOperand(2)
452 .setImm(OPCODE_IS_NOT_ZERO);
454 case OPCODE_IS_NOT_ZERO:
455 static_cast<MachineInstr *>(I)->getOperand(2)
456 .setImm(OPCODE_IS_ZERO);
459 llvm_unreachable("PRED_X Opcode invalid!");
465 void AMDGPUCFGStructurizer::insertInstrEnd(MachineBasicBlock *MBB,
466 int NewOpcode, DebugLoc DL) {
467 MachineInstr *MI = MBB->getParent()
468 ->CreateMachineInstr(TII->get(NewOpcode), DL);
470 //assume the instruction doesn't take any reg operand ...
474 MachineInstr *AMDGPUCFGStructurizer::insertInstrBefore(MachineBasicBlock *MBB,
475 int NewOpcode, DebugLoc DL) {
477 MBB->getParent()->CreateMachineInstr(TII->get(NewOpcode), DL);
478 if (MBB->begin() != MBB->end())
479 MBB->insert(MBB->begin(), MI);
486 MachineInstr *AMDGPUCFGStructurizer::insertInstrBefore(
487 MachineBasicBlock::iterator I, int NewOpcode) {
488 MachineInstr *OldMI = &(*I);
489 MachineBasicBlock *MBB = OldMI->getParent();
490 MachineInstr *NewMBB =
491 MBB->getParent()->CreateMachineInstr(TII->get(NewOpcode), DebugLoc());
492 MBB->insert(I, NewMBB);
493 //assume the instruction doesn't take any reg operand ...
494 SHOWNEWINSTR(NewMBB);
498 void AMDGPUCFGStructurizer::insertCondBranchBefore(
499 MachineBasicBlock::iterator I, int NewOpcode, DebugLoc DL) {
500 MachineInstr *OldMI = &(*I);
501 MachineBasicBlock *MBB = OldMI->getParent();
502 MachineFunction *MF = MBB->getParent();
503 MachineInstr *NewMI = MF->CreateMachineInstr(TII->get(NewOpcode), DL);
504 MBB->insert(I, NewMI);
505 MachineInstrBuilder MIB(*MF, NewMI);
506 MIB.addReg(OldMI->getOperand(1).getReg(), false);
508 //erase later oldInstr->eraseFromParent();
511 void AMDGPUCFGStructurizer::insertCondBranchBefore(MachineBasicBlock *blk,
512 MachineBasicBlock::iterator I, int NewOpcode, int RegNum,
514 MachineFunction *MF = blk->getParent();
515 MachineInstr *NewInstr = MF->CreateMachineInstr(TII->get(NewOpcode), DL);
517 blk->insert(I, NewInstr);
518 MachineInstrBuilder(*MF, NewInstr).addReg(RegNum, false);
519 SHOWNEWINSTR(NewInstr);
522 void AMDGPUCFGStructurizer::insertCondBranchEnd(MachineBasicBlock *MBB,
523 int NewOpcode, int RegNum) {
524 MachineFunction *MF = MBB->getParent();
525 MachineInstr *NewInstr =
526 MF->CreateMachineInstr(TII->get(NewOpcode), DebugLoc());
527 MBB->push_back(NewInstr);
528 MachineInstrBuilder(*MF, NewInstr).addReg(RegNum, false);
529 SHOWNEWINSTR(NewInstr);
532 int AMDGPUCFGStructurizer::getBranchNzeroOpcode(int OldOpcode) {
534 case AMDGPU::JUMP_COND:
535 case AMDGPU::JUMP: return AMDGPU::IF_PREDICATE_SET;
536 case AMDGPU::BRANCH_COND_i32:
537 case AMDGPU::BRANCH_COND_f32: return AMDGPU::IF_LOGICALNZ_f32;
538 default: llvm_unreachable("internal error");
543 int AMDGPUCFGStructurizer::getBranchZeroOpcode(int OldOpcode) {
545 case AMDGPU::JUMP_COND:
546 case AMDGPU::JUMP: return AMDGPU::IF_PREDICATE_SET;
547 case AMDGPU::BRANCH_COND_i32:
548 case AMDGPU::BRANCH_COND_f32: return AMDGPU::IF_LOGICALZ_f32;
549 default: llvm_unreachable("internal error");
554 int AMDGPUCFGStructurizer::getContinueNzeroOpcode(int OldOpcode) {
556 case AMDGPU::JUMP_COND:
557 case AMDGPU::JUMP: return AMDGPU::CONTINUE_LOGICALNZ_i32;
558 default: llvm_unreachable("internal error");
563 int AMDGPUCFGStructurizer::getContinueZeroOpcode(int OldOpcode) {
565 case AMDGPU::JUMP_COND:
566 case AMDGPU::JUMP: return AMDGPU::CONTINUE_LOGICALZ_i32;
567 default: llvm_unreachable("internal error");
572 MachineBasicBlock *AMDGPUCFGStructurizer::getTrueBranch(MachineInstr *MI) {
573 return MI->getOperand(0).getMBB();
576 void AMDGPUCFGStructurizer::setTrueBranch(MachineInstr *MI,
577 MachineBasicBlock *MBB) {
578 MI->getOperand(0).setMBB(MBB);
582 AMDGPUCFGStructurizer::getFalseBranch(MachineBasicBlock *MBB,
584 assert(MBB->succ_size() == 2);
585 MachineBasicBlock *TrueBranch = getTrueBranch(MI);
586 MachineBasicBlock::succ_iterator It = MBB->succ_begin();
587 MachineBasicBlock::succ_iterator Next = It;
589 return (*It == TrueBranch) ? *Next : *It;
592 bool AMDGPUCFGStructurizer::isCondBranch(MachineInstr *MI) {
593 switch (MI->getOpcode()) {
594 case AMDGPU::JUMP_COND:
595 case AMDGPU::BRANCH_COND_i32:
596 case AMDGPU::BRANCH_COND_f32: return true;
603 bool AMDGPUCFGStructurizer::isUncondBranch(MachineInstr *MI) {
604 switch (MI->getOpcode()) {
614 DebugLoc AMDGPUCFGStructurizer::getLastDebugLocInBB(MachineBasicBlock *MBB) {
615 //get DebugLoc from the first MachineBasicBlock instruction with debug info
617 for (MachineBasicBlock::iterator It = MBB->begin(); It != MBB->end();
619 MachineInstr *instr = &(*It);
620 if (instr->getDebugLoc().isUnknown() == false)
621 DL = instr->getDebugLoc();
626 MachineInstr *AMDGPUCFGStructurizer::getNormalBlockBranchInstr(
627 MachineBasicBlock *MBB) {
628 MachineBasicBlock::reverse_iterator It = MBB->rbegin();
629 MachineInstr *MI = &*It;
630 if (MI && (isCondBranch(MI) || isUncondBranch(MI)))
635 MachineInstr *AMDGPUCFGStructurizer::getLoopendBlockBranchInstr(
636 MachineBasicBlock *MBB) {
637 for (MachineBasicBlock::reverse_iterator It = MBB->rbegin(), E = MBB->rend();
640 MachineInstr *MI = &*It;
642 if (isCondBranch(MI) || isUncondBranch(MI))
644 else if (!TII->isMov(MI->getOpcode()))
651 MachineInstr *AMDGPUCFGStructurizer::getReturnInstr(MachineBasicBlock *MBB) {
652 MachineBasicBlock::reverse_iterator It = MBB->rbegin();
653 if (It != MBB->rend()) {
654 MachineInstr *instr = &(*It);
655 if (instr->getOpcode() == AMDGPU::RETURN)
661 MachineInstr *AMDGPUCFGStructurizer::getContinueInstr(MachineBasicBlock *MBB) {
662 MachineBasicBlock::reverse_iterator It = MBB->rbegin();
663 if (It != MBB->rend()) {
664 MachineInstr *MI = &(*It);
665 if (MI->getOpcode() == AMDGPU::CONTINUE)
671 MachineInstr *AMDGPUCFGStructurizer::getLoopBreakInstr(MachineBasicBlock *MBB) {
672 for (MachineBasicBlock::iterator It = MBB->begin(); (It != MBB->end());
674 MachineInstr *MI = &(*It);
675 if (MI->getOpcode() == AMDGPU::PREDICATED_BREAK)
681 bool AMDGPUCFGStructurizer::isReturnBlock(MachineBasicBlock *MBB) {
682 MachineInstr *MI = getReturnInstr(MBB);
683 bool IsReturn = (MBB->succ_size() == 0);
688 dbgs() << "BB" << MBB->getNumber()
689 <<" is return block without RETURN instr\n";);
693 void AMDGPUCFGStructurizer::cloneSuccessorList(MachineBasicBlock *DstMBB,
694 MachineBasicBlock *SrcMBB) {
695 for (MachineBasicBlock::succ_iterator It = SrcMBB->succ_begin(),
696 iterEnd = SrcMBB->succ_end(); It != iterEnd; ++It)
697 DstMBB->addSuccessor(*It); // *iter's predecessor is also taken care of
700 MachineBasicBlock *AMDGPUCFGStructurizer::clone(MachineBasicBlock *MBB) {
701 MachineFunction *Func = MBB->getParent();
702 MachineBasicBlock *NewMBB = Func->CreateMachineBasicBlock();
703 Func->push_back(NewMBB); //insert to function
704 for (MachineBasicBlock::iterator It = MBB->begin(), E = MBB->end();
706 MachineInstr *MI = Func->CloneMachineInstr(It);
707 NewMBB->push_back(MI);
712 void AMDGPUCFGStructurizer::replaceInstrUseOfBlockWith(
713 MachineBasicBlock *SrcMBB, MachineBasicBlock *OldMBB,
714 MachineBasicBlock *NewBlk) {
715 MachineInstr *BranchMI = getLoopendBlockBranchInstr(SrcMBB);
716 if (BranchMI && isCondBranch(BranchMI) &&
717 getTrueBranch(BranchMI) == OldMBB)
718 setTrueBranch(BranchMI, NewBlk);
721 void AMDGPUCFGStructurizer::wrapup(MachineBasicBlock *MBB) {
722 assert((!MBB->getParent()->getJumpTableInfo()
723 || MBB->getParent()->getJumpTableInfo()->isEmpty())
724 && "found a jump table");
726 //collect continue right before endloop
727 SmallVector<MachineInstr *, DEFAULT_VEC_SLOTS> ContInstr;
728 MachineBasicBlock::iterator Pre = MBB->begin();
729 MachineBasicBlock::iterator E = MBB->end();
730 MachineBasicBlock::iterator It = Pre;
732 if (Pre->getOpcode() == AMDGPU::CONTINUE
733 && It->getOpcode() == AMDGPU::ENDLOOP)
734 ContInstr.push_back(Pre);
739 //delete continue right before endloop
740 for (unsigned i = 0; i < ContInstr.size(); ++i)
741 ContInstr[i]->eraseFromParent();
743 // TODO to fix up jump table so later phase won't be confused. if
744 // (jumpTableInfo->isEmpty() == false) { need to clean the jump table, but
745 // there isn't such an interface yet. alternatively, replace all the other
746 // blocks in the jump table with the entryBlk //}
751 bool AMDGPUCFGStructurizer::prepare() {
752 bool Changed = false;
754 //FIXME: if not reducible flow graph, make it so ???
756 DEBUG(dbgs() << "AMDGPUCFGStructurizer::prepare\n";);
758 orderBlocks(FuncRep);
760 SmallVector<MachineBasicBlock *, DEFAULT_VEC_SLOTS> RetBlks;
762 // Add an ExitBlk to loop that don't have one
763 for (MachineLoopInfo::iterator It = MLI->begin(),
764 E = MLI->end(); It != E; ++It) {
765 MachineLoop *LoopRep = (*It);
766 MBBVector ExitingMBBs;
767 LoopRep->getExitingBlocks(ExitingMBBs);
769 if (ExitingMBBs.size() == 0) {
770 MachineBasicBlock* DummyExitBlk = normalizeInfiniteLoopExit(LoopRep);
772 RetBlks.push_back(DummyExitBlk);
776 // Remove unconditional branch instr.
777 // Add dummy exit block iff there are multiple returns.
778 for (SmallVectorImpl<MachineBasicBlock *>::const_iterator
779 It = OrderedBlks.begin(), E = OrderedBlks.end(); It != E; ++It) {
780 MachineBasicBlock *MBB = *It;
781 removeUnconditionalBranch(MBB);
782 removeRedundantConditionalBranch(MBB);
783 if (isReturnBlock(MBB)) {
784 RetBlks.push_back(MBB);
786 assert(MBB->succ_size() <= 2);
789 if (RetBlks.size() >= 2) {
790 addDummyExitBlock(RetBlks);
797 bool AMDGPUCFGStructurizer::run() {
799 //Assume reducible CFG...
800 DEBUG(dbgs() << "AMDGPUCFGStructurizer::run\n";FuncRep->viewCFG(););
803 //Use the worse block ordering to test the algorithm.
804 ReverseVector(orderedBlks);
807 DEBUG(dbgs() << "Ordered blocks:\n"; printOrderedBlocks(););
810 MachineBasicBlock *MBB;
811 bool MakeProgress = false;
812 int NumRemainedBlk = countActiveBlock(OrderedBlks.begin(),
818 dbgs() << "numIter = " << NumIter
819 << ", numRemaintedBlk = " << NumRemainedBlk << "\n";
822 SmallVectorImpl<MachineBasicBlock *>::const_iterator It =
824 SmallVectorImpl<MachineBasicBlock *>::const_iterator E =
827 SmallVectorImpl<MachineBasicBlock *>::const_iterator SccBeginIter =
829 MachineBasicBlock *SccBeginMBB = NULL;
830 int SccNumBlk = 0; // The number of active blocks, init to a
831 // maximum possible number.
832 int SccNumIter; // Number of iteration in this SCC.
841 SccNumBlk = NumRemainedBlk; // Init to maximum possible number.
843 dbgs() << "start processing SCC" << getSCCNum(SccBeginMBB);
848 if (!isRetiredBlock(MBB))
853 bool ContNextScc = true;
855 || getSCCNum(SccBeginMBB) != getSCCNum(*It)) {
856 // Just finish one scc.
858 int sccRemainedNumBlk = countActiveBlock(SccBeginIter, It);
859 if (sccRemainedNumBlk != 1 && sccRemainedNumBlk >= SccNumBlk) {
861 dbgs() << "Can't reduce SCC " << getSCCNum(MBB)
862 << ", sccNumIter = " << SccNumIter;
863 dbgs() << "doesn't make any progress\n";
866 } else if (sccRemainedNumBlk != 1 && sccRemainedNumBlk < SccNumBlk) {
867 SccNumBlk = sccRemainedNumBlk;
871 dbgs() << "repeat processing SCC" << getSCCNum(MBB)
872 << "sccNumIter = " << SccNumIter << "\n";
876 // Finish the current scc.
880 // Continue on next component in the current scc.
886 } //while, "one iteration" over the function.
888 MachineBasicBlock *EntryMBB =
889 GraphTraits<MachineFunction *>::nodes_begin(FuncRep);
890 if (EntryMBB->succ_size() == 0) {
893 dbgs() << "Reduce to one block\n";
896 int NewnumRemainedBlk
897 = countActiveBlock(OrderedBlks.begin(), OrderedBlks.end());
898 // consider cloned blocks ??
899 if (NewnumRemainedBlk == 1 || NewnumRemainedBlk < NumRemainedBlk) {
901 NumRemainedBlk = NewnumRemainedBlk;
903 MakeProgress = false;
905 dbgs() << "No progress\n";
909 } while (!Finish && MakeProgress);
911 // Misc wrap up to maintain the consistency of the Function representation.
912 wrapup(GraphTraits<MachineFunction *>::nodes_begin(FuncRep));
914 // Detach retired Block, release memory.
915 for (MBBInfoMap::iterator It = BlockInfoMap.begin(), E = BlockInfoMap.end();
917 if ((*It).second && (*It).second->IsRetired) {
918 assert(((*It).first)->getNumber() != -1);
920 dbgs() << "Erase BB" << ((*It).first)->getNumber() << "\n";
922 (*It).first->eraseFromParent(); //Remove from the parent Function.
926 BlockInfoMap.clear();
934 llvm_unreachable("IRREDUCIBL_CF");
941 void AMDGPUCFGStructurizer::orderBlocks(MachineFunction *MF) {
943 MachineBasicBlock *MBB;
944 for (scc_iterator<MachineFunction *> It = scc_begin(MF), E = scc_end(MF);
945 It != E; ++It, ++SccNum) {
946 std::vector<MachineBasicBlock *> &SccNext = *It;
947 for (std::vector<MachineBasicBlock *>::const_iterator
948 blockIter = SccNext.begin(), blockEnd = SccNext.end();
949 blockIter != blockEnd; ++blockIter) {
951 OrderedBlks.push_back(MBB);
952 recordSccnum(MBB, SccNum);
956 //walk through all the block in func to check for unreachable
957 typedef GraphTraits<MachineFunction *> GTM;
958 MachineFunction::iterator It = GTM::nodes_begin(MF), E = GTM::nodes_end(MF);
959 for (; It != E; ++It) {
960 MachineBasicBlock *MBB = &(*It);
961 SccNum = getSCCNum(MBB);
962 if (SccNum == INVALIDSCCNUM)
963 dbgs() << "unreachable block BB" << MBB->getNumber() << "\n";
967 int AMDGPUCFGStructurizer::patternMatch(MachineBasicBlock *MBB) {
972 dbgs() << "Begin patternMatch BB" << MBB->getNumber() << "\n";
975 while ((CurMatch = patternMatchGroup(MBB)) > 0)
976 NumMatch += CurMatch;
979 dbgs() << "End patternMatch BB" << MBB->getNumber()
980 << ", numMatch = " << NumMatch << "\n";
986 int AMDGPUCFGStructurizer::patternMatchGroup(MachineBasicBlock *MBB) {
988 NumMatch += loopendPatternMatch();
989 NumMatch += serialPatternMatch(MBB);
990 NumMatch += ifPatternMatch(MBB);
995 int AMDGPUCFGStructurizer::serialPatternMatch(MachineBasicBlock *MBB) {
996 if (MBB->succ_size() != 1)
999 MachineBasicBlock *childBlk = *MBB->succ_begin();
1000 if (childBlk->pred_size() != 1 || isActiveLoophead(childBlk))
1003 mergeSerialBlock(MBB, childBlk);
1004 ++numSerialPatternMatch;
1008 int AMDGPUCFGStructurizer::ifPatternMatch(MachineBasicBlock *MBB) {
1010 if (MBB->succ_size() != 2)
1012 if (hasBackEdge(MBB))
1014 MachineInstr *BranchMI = getNormalBlockBranchInstr(MBB);
1018 assert(isCondBranch(BranchMI));
1020 MachineBasicBlock *TrueMBB = getTrueBranch(BranchMI);
1021 serialPatternMatch(TrueMBB);
1022 ifPatternMatch(TrueMBB);
1023 MachineBasicBlock *FalseMBB = getFalseBranch(MBB, BranchMI);
1024 serialPatternMatch(FalseMBB);
1025 ifPatternMatch(FalseMBB);
1026 MachineBasicBlock *LandBlk;
1029 assert (!TrueMBB->succ_empty() || !FalseMBB->succ_empty());
1031 if (TrueMBB->succ_size() == 1 && FalseMBB->succ_size() == 1
1032 && *TrueMBB->succ_begin() == *FalseMBB->succ_begin()) {
1034 LandBlk = *TrueMBB->succ_begin();
1035 } else if (TrueMBB->succ_size() == 1 && *TrueMBB->succ_begin() == FalseMBB) {
1036 // Triangle pattern, false is empty
1039 } else if (FalseMBB->succ_size() == 1
1040 && *FalseMBB->succ_begin() == TrueMBB) {
1041 // Triangle pattern, true is empty
1042 // We reverse the predicate to make a triangle, empty false pattern;
1043 std::swap(TrueMBB, FalseMBB);
1044 reversePredicateSetter(MBB->end());
1047 } else if (FalseMBB->succ_size() == 1
1048 && isSameloopDetachedContbreak(TrueMBB, FalseMBB)) {
1049 LandBlk = *FalseMBB->succ_begin();
1050 } else if (TrueMBB->succ_size() == 1
1051 && isSameloopDetachedContbreak(FalseMBB, TrueMBB)) {
1052 LandBlk = *TrueMBB->succ_begin();
1054 return handleJumpintoIf(MBB, TrueMBB, FalseMBB);
1057 // improveSimpleJumpinfoIf can handle the case where landBlk == NULL but the
1058 // new BB created for landBlk==NULL may introduce new challenge to the
1059 // reduction process.
1061 ((TrueMBB && TrueMBB->pred_size() > 1)
1062 || (FalseMBB && FalseMBB->pred_size() > 1))) {
1063 Cloned += improveSimpleJumpintoIf(MBB, TrueMBB, FalseMBB, &LandBlk);
1066 if (TrueMBB && TrueMBB->pred_size() > 1) {
1067 TrueMBB = cloneBlockForPredecessor(TrueMBB, MBB);
1071 if (FalseMBB && FalseMBB->pred_size() > 1) {
1072 FalseMBB = cloneBlockForPredecessor(FalseMBB, MBB);
1076 mergeIfthenelseBlock(BranchMI, MBB, TrueMBB, FalseMBB, LandBlk);
1078 ++numIfPatternMatch;
1080 numClonedBlock += Cloned;
1085 int AMDGPUCFGStructurizer::loopendPatternMatch() {
1086 std::vector<MachineLoop *> NestedLoops;
1087 for (MachineLoopInfo::iterator It = MLI->begin(), E = MLI->end();
1089 df_iterator<MachineLoop *> LpIt = df_begin(*It),
1091 for (; LpIt != LpE; ++LpIt)
1092 NestedLoops.push_back(*LpIt);
1094 if (NestedLoops.size() == 0)
1097 // Process nested loop outside->inside, so "continue" to a outside loop won't
1098 // be mistaken as "break" of the current loop.
1100 for (std::vector<MachineLoop *>::reverse_iterator It = NestedLoops.rbegin(),
1101 E = NestedLoops.rend(); It != E; ++It) {
1102 MachineLoop *ExaminedLoop = *It;
1103 if (ExaminedLoop->getNumBlocks() == 0 || Visited[ExaminedLoop])
1105 DEBUG(dbgs() << "Processing:\n"; ExaminedLoop->dump(););
1106 int NumBreak = mergeLoop(ExaminedLoop);
1114 int AMDGPUCFGStructurizer::mergeLoop(MachineLoop *LoopRep) {
1115 MachineBasicBlock *LoopHeader = LoopRep->getHeader();
1116 MBBVector ExitingMBBs;
1117 LoopRep->getExitingBlocks(ExitingMBBs);
1118 assert(!ExitingMBBs.empty() && "Infinite Loop not supported");
1119 DEBUG(dbgs() << "Loop has " << ExitingMBBs.size() << " exiting blocks\n";);
1120 // We assume a single ExitBlk
1122 LoopRep->getExitBlocks(ExitBlks);
1123 SmallPtrSet<MachineBasicBlock *, 2> ExitBlkSet;
1124 for (unsigned i = 0, e = ExitBlks.size(); i < e; ++i)
1125 ExitBlkSet.insert(ExitBlks[i]);
1126 assert(ExitBlkSet.size() == 1);
1127 MachineBasicBlock *ExitBlk = *ExitBlks.begin();
1128 assert(ExitBlk && "Loop has several exit block");
1129 MBBVector LatchBlks;
1130 typedef GraphTraits<Inverse<MachineBasicBlock*> > InvMBBTraits;
1131 InvMBBTraits::ChildIteratorType PI = InvMBBTraits::child_begin(LoopHeader),
1132 PE = InvMBBTraits::child_end(LoopHeader);
1133 for (; PI != PE; PI++) {
1134 if (LoopRep->contains(*PI))
1135 LatchBlks.push_back(*PI);
1138 for (unsigned i = 0, e = ExitingMBBs.size(); i < e; ++i)
1139 mergeLoopbreakBlock(ExitingMBBs[i], ExitBlk);
1140 for (unsigned i = 0, e = LatchBlks.size(); i < e; ++i)
1141 settleLoopcontBlock(LatchBlks[i], LoopHeader);
1145 Match += serialPatternMatch(LoopHeader);
1146 Match += ifPatternMatch(LoopHeader);
1147 } while (Match > 0);
1148 mergeLooplandBlock(LoopHeader, ExitBlk);
1149 MachineLoop *ParentLoop = LoopRep->getParentLoop();
1151 MLI->changeLoopFor(LoopHeader, ParentLoop);
1153 MLI->removeBlock(LoopHeader);
1154 Visited[LoopRep] = true;
1158 int AMDGPUCFGStructurizer::loopcontPatternMatch(MachineLoop *LoopRep,
1159 MachineBasicBlock *LoopHeader) {
1161 SmallVector<MachineBasicBlock *, DEFAULT_VEC_SLOTS> ContMBB;
1162 typedef GraphTraits<Inverse<MachineBasicBlock *> > GTIM;
1163 GTIM::ChildIteratorType It = GTIM::child_begin(LoopHeader),
1164 E = GTIM::child_end(LoopHeader);
1165 for (; It != E; ++It) {
1166 MachineBasicBlock *MBB = *It;
1167 if (LoopRep->contains(MBB)) {
1168 handleLoopcontBlock(MBB, MLI->getLoopFor(MBB),
1169 LoopHeader, LoopRep);
1170 ContMBB.push_back(MBB);
1175 for (SmallVectorImpl<MachineBasicBlock *>::iterator It = ContMBB.begin(),
1176 E = ContMBB.end(); It != E; ++It) {
1177 (*It)->removeSuccessor(LoopHeader);
1180 numLoopcontPatternMatch += NumCont;
1186 bool AMDGPUCFGStructurizer::isSameloopDetachedContbreak(
1187 MachineBasicBlock *Src1MBB, MachineBasicBlock *Src2MBB) {
1188 if (Src1MBB->succ_size() == 0) {
1189 MachineLoop *LoopRep = MLI->getLoopFor(Src1MBB);
1190 if (LoopRep&& LoopRep == MLI->getLoopFor(Src2MBB)) {
1191 MachineBasicBlock *&TheEntry = LLInfoMap[LoopRep];
1194 dbgs() << "isLoopContBreakBlock yes src1 = BB"
1195 << Src1MBB->getNumber()
1196 << " src2 = BB" << Src2MBB->getNumber() << "\n";
1205 int AMDGPUCFGStructurizer::handleJumpintoIf(MachineBasicBlock *HeadMBB,
1206 MachineBasicBlock *TrueMBB, MachineBasicBlock *FalseMBB) {
1207 int Num = handleJumpintoIfImp(HeadMBB, TrueMBB, FalseMBB);
1210 dbgs() << "handleJumpintoIf swap trueBlk and FalseBlk" << "\n";
1212 Num = handleJumpintoIfImp(HeadMBB, FalseMBB, TrueMBB);
1217 int AMDGPUCFGStructurizer::handleJumpintoIfImp(MachineBasicBlock *HeadMBB,
1218 MachineBasicBlock *TrueMBB, MachineBasicBlock *FalseMBB) {
1220 MachineBasicBlock *DownBlk;
1222 //trueBlk could be the common post dominator
1226 dbgs() << "handleJumpintoIfImp head = BB" << HeadMBB->getNumber()
1227 << " true = BB" << TrueMBB->getNumber()
1228 << ", numSucc=" << TrueMBB->succ_size()
1229 << " false = BB" << FalseMBB->getNumber() << "\n";
1234 dbgs() << "check down = BB" << DownBlk->getNumber();
1237 if (singlePathTo(FalseMBB, DownBlk) == SinglePath_InPath) {
1239 dbgs() << " working\n";
1242 Num += cloneOnSideEntryTo(HeadMBB, TrueMBB, DownBlk);
1243 Num += cloneOnSideEntryTo(HeadMBB, FalseMBB, DownBlk);
1245 numClonedBlock += Num;
1246 Num += serialPatternMatch(*HeadMBB->succ_begin());
1247 Num += serialPatternMatch(*(++HeadMBB->succ_begin()));
1248 Num += ifPatternMatch(HeadMBB);
1254 dbgs() << " not working\n";
1256 DownBlk = (DownBlk->succ_size() == 1) ? (*DownBlk->succ_begin()) : NULL;
1257 } // walk down the postDomTree
1262 void AMDGPUCFGStructurizer::showImproveSimpleJumpintoIf(
1263 MachineBasicBlock *HeadMBB, MachineBasicBlock *TrueMBB,
1264 MachineBasicBlock *FalseMBB, MachineBasicBlock *LandMBB, bool Detail) {
1265 dbgs() << "head = BB" << HeadMBB->getNumber()
1266 << " size = " << HeadMBB->size();
1269 HeadMBB->print(dbgs());
1274 dbgs() << ", true = BB" << TrueMBB->getNumber() << " size = "
1275 << TrueMBB->size() << " numPred = " << TrueMBB->pred_size();
1278 TrueMBB->print(dbgs());
1283 dbgs() << ", false = BB" << FalseMBB->getNumber() << " size = "
1284 << FalseMBB->size() << " numPred = " << FalseMBB->pred_size();
1287 FalseMBB->print(dbgs());
1292 dbgs() << ", land = BB" << LandMBB->getNumber() << " size = "
1293 << LandMBB->size() << " numPred = " << LandMBB->pred_size();
1296 LandMBB->print(dbgs());
1304 int AMDGPUCFGStructurizer::improveSimpleJumpintoIf(MachineBasicBlock *HeadMBB,
1305 MachineBasicBlock *TrueMBB, MachineBasicBlock *FalseMBB,
1306 MachineBasicBlock **LandMBBPtr) {
1307 bool MigrateTrue = false;
1308 bool MigrateFalse = false;
1310 MachineBasicBlock *LandBlk = *LandMBBPtr;
1312 assert((!TrueMBB || TrueMBB->succ_size() <= 1)
1313 && (!FalseMBB || FalseMBB->succ_size() <= 1));
1315 if (TrueMBB == FalseMBB)
1318 MigrateTrue = needMigrateBlock(TrueMBB);
1319 MigrateFalse = needMigrateBlock(FalseMBB);
1321 if (!MigrateTrue && !MigrateFalse)
1324 // If we need to migrate either trueBlk and falseBlk, migrate the rest that
1325 // have more than one predecessors. without doing this, its predecessor
1326 // rather than headBlk will have undefined value in initReg.
1327 if (!MigrateTrue && TrueMBB && TrueMBB->pred_size() > 1)
1329 if (!MigrateFalse && FalseMBB && FalseMBB->pred_size() > 1)
1330 MigrateFalse = true;
1333 dbgs() << "before improveSimpleJumpintoIf: ";
1334 showImproveSimpleJumpintoIf(HeadMBB, TrueMBB, FalseMBB, LandBlk, 0);
1337 // org: headBlk => if () {trueBlk} else {falseBlk} => landBlk
1339 // new: headBlk => if () {initReg = 1; org trueBlk branch} else
1340 // {initReg = 0; org falseBlk branch }
1341 // => landBlk => if (initReg) {org trueBlk} else {org falseBlk}
1343 // if landBlk->pred_size() > 2, put the about if-else inside
1344 // if (initReg !=2) {...}
1346 // add initReg = initVal to headBlk
1348 const TargetRegisterClass * I32RC = TRI->getCFGStructurizerRegClass(MVT::i32);
1350 HeadMBB->getParent()->getRegInfo().createVirtualRegister(I32RC);
1351 if (!MigrateTrue || !MigrateFalse)
1352 llvm_unreachable("Extra register needed to handle CFG");
1357 LandBlk = HeadMBB->getParent()->CreateMachineBasicBlock();
1358 HeadMBB->getParent()->push_back(LandBlk); //insert to function
1361 TrueMBB->addSuccessor(LandBlk);
1363 HeadMBB->addSuccessor(LandBlk);
1367 FalseMBB->addSuccessor(LandBlk);
1369 HeadMBB->addSuccessor(LandBlk);
1375 bool LandBlkHasOtherPred = (LandBlk->pred_size() > 2);
1377 //insert AMDGPU::ENDIF to avoid special case "input landBlk == NULL"
1378 MachineBasicBlock::iterator I = insertInstrBefore(LandBlk, AMDGPU::ENDIF);
1380 if (LandBlkHasOtherPred) {
1381 llvm_unreachable("Extra register needed to handle CFG");
1382 unsigned CmpResReg =
1383 HeadMBB->getParent()->getRegInfo().createVirtualRegister(I32RC);
1384 llvm_unreachable("Extra compare instruction needed to handle CFG");
1385 insertCondBranchBefore(LandBlk, I, AMDGPU::IF_PREDICATE_SET,
1386 CmpResReg, DebugLoc());
1389 insertCondBranchBefore(LandBlk, I, AMDGPU::IF_PREDICATE_SET, InitReg,
1393 migrateInstruction(TrueMBB, LandBlk, I);
1394 // need to uncondionally insert the assignment to ensure a path from its
1395 // predecessor rather than headBlk has valid value in initReg if
1397 llvm_unreachable("Extra register needed to handle CFG");
1399 insertInstrBefore(I, AMDGPU::ELSE);
1402 migrateInstruction(FalseMBB, LandBlk, I);
1403 // need to uncondionally insert the assignment to ensure a path from its
1404 // predecessor rather than headBlk has valid value in initReg if
1406 llvm_unreachable("Extra register needed to handle CFG");
1409 if (LandBlkHasOtherPred) {
1411 insertInstrBefore(I, AMDGPU::ENDIF);
1413 // put initReg = 2 to other predecessors of landBlk
1414 for (MachineBasicBlock::pred_iterator PI = LandBlk->pred_begin(),
1415 PE = LandBlk->pred_end(); PI != PE; ++PI) {
1416 MachineBasicBlock *MBB = *PI;
1417 if (MBB != TrueMBB && MBB != FalseMBB)
1418 llvm_unreachable("Extra register needed to handle CFG");
1422 dbgs() << "result from improveSimpleJumpintoIf: ";
1423 showImproveSimpleJumpintoIf(HeadMBB, TrueMBB, FalseMBB, LandBlk, 0);
1427 *LandMBBPtr = LandBlk;
1432 void AMDGPUCFGStructurizer::handleLoopcontBlock(MachineBasicBlock *ContingMBB,
1433 MachineLoop *ContingLoop, MachineBasicBlock *ContMBB,
1434 MachineLoop *ContLoop) {
1435 DEBUG(dbgs() << "loopcontPattern cont = BB" << ContingMBB->getNumber()
1436 << " header = BB" << ContMBB->getNumber() << "\n";
1437 dbgs() << "Trying to continue loop-depth = "
1438 << getLoopDepth(ContLoop)
1439 << " from loop-depth = " << getLoopDepth(ContingLoop) << "\n";);
1440 settleLoopcontBlock(ContingMBB, ContMBB);
1443 void AMDGPUCFGStructurizer::mergeSerialBlock(MachineBasicBlock *DstMBB,
1444 MachineBasicBlock *SrcMBB) {
1446 dbgs() << "serialPattern BB" << DstMBB->getNumber()
1447 << " <= BB" << SrcMBB->getNumber() << "\n";
1449 DstMBB->splice(DstMBB->end(), SrcMBB, SrcMBB->begin(), SrcMBB->end());
1451 DstMBB->removeSuccessor(SrcMBB);
1452 cloneSuccessorList(DstMBB, SrcMBB);
1454 removeSuccessor(SrcMBB);
1455 MLI->removeBlock(SrcMBB);
1456 retireBlock(SrcMBB);
1459 void AMDGPUCFGStructurizer::mergeIfthenelseBlock(MachineInstr *BranchMI,
1460 MachineBasicBlock *MBB, MachineBasicBlock *TrueMBB,
1461 MachineBasicBlock *FalseMBB, MachineBasicBlock *LandMBB) {
1464 dbgs() << "ifPattern BB" << MBB->getNumber();
1467 dbgs() << "BB" << TrueMBB->getNumber();
1469 dbgs() << " } else ";
1472 dbgs() << "BB" << FalseMBB->getNumber();
1475 dbgs() << "landBlock: ";
1479 dbgs() << "BB" << LandMBB->getNumber();
1484 int OldOpcode = BranchMI->getOpcode();
1485 DebugLoc BranchDL = BranchMI->getDebugLoc();
1495 MachineBasicBlock::iterator I = BranchMI;
1496 insertCondBranchBefore(I, getBranchNzeroOpcode(OldOpcode),
1500 MBB->splice(I, TrueMBB, TrueMBB->begin(), TrueMBB->end());
1501 MBB->removeSuccessor(TrueMBB);
1502 if (LandMBB && TrueMBB->succ_size()!=0)
1503 TrueMBB->removeSuccessor(LandMBB);
1504 retireBlock(TrueMBB);
1505 MLI->removeBlock(TrueMBB);
1509 insertInstrBefore(I, AMDGPU::ELSE);
1510 MBB->splice(I, FalseMBB, FalseMBB->begin(),
1512 MBB->removeSuccessor(FalseMBB);
1513 if (LandMBB && FalseMBB->succ_size() != 0)
1514 FalseMBB->removeSuccessor(LandMBB);
1515 retireBlock(FalseMBB);
1516 MLI->removeBlock(FalseMBB);
1518 insertInstrBefore(I, AMDGPU::ENDIF);
1520 BranchMI->eraseFromParent();
1522 if (LandMBB && TrueMBB && FalseMBB)
1523 MBB->addSuccessor(LandMBB);
1527 void AMDGPUCFGStructurizer::mergeLooplandBlock(MachineBasicBlock *DstBlk,
1528 MachineBasicBlock *LandMBB) {
1529 DEBUG(dbgs() << "loopPattern header = BB" << DstBlk->getNumber()
1530 << " land = BB" << LandMBB->getNumber() << "\n";);
1532 /* we last inserterd the DebugLoc in the
1533 * BREAK_LOGICALZ_i32 or AMDGPU::BREAK_LOGICALNZ statement in the current
1535 * search for the DebugLoc in the that statement.
1536 * if not found, we have to insert the empty/default DebugLoc */
1537 MachineInstr *LoopBreakInstr = getLoopBreakInstr(DstBlk);
1538 DebugLoc DLBreak = (LoopBreakInstr) ? LoopBreakInstr->getDebugLoc() :
1541 insertInstrBefore(DstBlk, AMDGPU::WHILELOOP, DLBreak);
1543 /* we last inserterd the DebugLoc in the continue statement in the current
1545 * search for the DebugLoc in the continue statement.
1546 * if not found, we have to insert the empty/default DebugLoc */
1547 MachineInstr *ContinueInstr = getContinueInstr(DstBlk);
1548 DebugLoc DLContinue = (ContinueInstr) ? ContinueInstr->getDebugLoc() :
1551 insertInstrEnd(DstBlk, AMDGPU::ENDLOOP, DLContinue);
1552 DstBlk->addSuccessor(LandMBB);
1553 DstBlk->removeSuccessor(DstBlk);
1557 void AMDGPUCFGStructurizer::mergeLoopbreakBlock(MachineBasicBlock *ExitingMBB,
1558 MachineBasicBlock *LandMBB) {
1559 DEBUG(dbgs() << "loopbreakPattern exiting = BB" << ExitingMBB->getNumber()
1560 << " land = BB" << LandMBB->getNumber() << "\n";);
1561 MachineInstr *BranchMI = getLoopendBlockBranchInstr(ExitingMBB);
1562 assert(BranchMI && isCondBranch(BranchMI));
1563 DebugLoc DL = BranchMI->getDebugLoc();
1564 MachineBasicBlock *TrueBranch = getTrueBranch(BranchMI);
1565 MachineBasicBlock::iterator I = BranchMI;
1566 if (TrueBranch != LandMBB)
1567 reversePredicateSetter(I);
1568 insertCondBranchBefore(I, AMDGPU::PREDICATED_BREAK, DL);
1569 //now branchInst can be erase safely
1570 BranchMI->eraseFromParent();
1571 //now take care of successors, retire blocks
1572 ExitingMBB->removeSuccessor(LandMBB);
1575 void AMDGPUCFGStructurizer::settleLoopcontBlock(MachineBasicBlock *ContingMBB,
1576 MachineBasicBlock *ContMBB) {
1577 DEBUG(dbgs() << "settleLoopcontBlock conting = BB"
1578 << ContingMBB->getNumber()
1579 << ", cont = BB" << ContMBB->getNumber() << "\n";);
1581 MachineInstr *MI = getLoopendBlockBranchInstr(ContingMBB);
1583 assert(isCondBranch(MI));
1584 MachineBasicBlock::iterator I = MI;
1585 MachineBasicBlock *TrueBranch = getTrueBranch(MI);
1586 int OldOpcode = MI->getOpcode();
1587 DebugLoc DL = MI->getDebugLoc();
1589 bool UseContinueLogical = ((&*ContingMBB->rbegin()) == MI);
1591 if (UseContinueLogical == false) {
1593 TrueBranch == ContMBB ? getBranchNzeroOpcode(OldOpcode) :
1594 getBranchZeroOpcode(OldOpcode);
1595 insertCondBranchBefore(I, BranchOpcode, DL);
1596 // insertEnd to ensure phi-moves, if exist, go before the continue-instr.
1597 insertInstrEnd(ContingMBB, AMDGPU::CONTINUE, DL);
1598 insertInstrEnd(ContingMBB, AMDGPU::ENDIF, DL);
1601 TrueBranch == ContMBB ? getContinueNzeroOpcode(OldOpcode) :
1602 getContinueZeroOpcode(OldOpcode);
1603 insertCondBranchBefore(I, BranchOpcode, DL);
1606 MI->eraseFromParent();
1608 // if we've arrived here then we've already erased the branch instruction
1609 // travel back up the basic block to see the last reference of our debug
1610 // location we've just inserted that reference here so it should be
1611 // representative insertEnd to ensure phi-moves, if exist, go before the
1613 insertInstrEnd(ContingMBB, AMDGPU::CONTINUE,
1614 getLastDebugLocInBB(ContingMBB));
1618 int AMDGPUCFGStructurizer::cloneOnSideEntryTo(MachineBasicBlock *PreMBB,
1619 MachineBasicBlock *SrcMBB, MachineBasicBlock *DstMBB) {
1621 assert(PreMBB->isSuccessor(SrcMBB));
1622 while (SrcMBB && SrcMBB != DstMBB) {
1623 assert(SrcMBB->succ_size() == 1);
1624 if (SrcMBB->pred_size() > 1) {
1625 SrcMBB = cloneBlockForPredecessor(SrcMBB, PreMBB);
1630 SrcMBB = *SrcMBB->succ_begin();
1637 AMDGPUCFGStructurizer::cloneBlockForPredecessor(MachineBasicBlock *MBB,
1638 MachineBasicBlock *PredMBB) {
1639 assert(PredMBB->isSuccessor(MBB) &&
1640 "succBlk is not a prececessor of curBlk");
1642 MachineBasicBlock *CloneMBB = clone(MBB); //clone instructions
1643 replaceInstrUseOfBlockWith(PredMBB, MBB, CloneMBB);
1644 //srcBlk, oldBlk, newBlk
1646 PredMBB->removeSuccessor(MBB);
1647 PredMBB->addSuccessor(CloneMBB);
1649 // add all successor to cloneBlk
1650 cloneSuccessorList(CloneMBB, MBB);
1652 numClonedInstr += MBB->size();
1655 dbgs() << "Cloned block: " << "BB"
1656 << MBB->getNumber() << "size " << MBB->size() << "\n";
1659 SHOWNEWBLK(CloneMBB, "result of Cloned block: ");
1664 void AMDGPUCFGStructurizer::migrateInstruction(MachineBasicBlock *SrcMBB,
1665 MachineBasicBlock *DstMBB, MachineBasicBlock::iterator I) {
1666 MachineBasicBlock::iterator SpliceEnd;
1667 //look for the input branchinstr, not the AMDGPU branchinstr
1668 MachineInstr *BranchMI = getNormalBlockBranchInstr(SrcMBB);
1671 dbgs() << "migrateInstruction don't see branch instr\n" ;
1673 SpliceEnd = SrcMBB->end();
1676 dbgs() << "migrateInstruction see branch instr\n" ;
1679 SpliceEnd = BranchMI;
1682 dbgs() << "migrateInstruction before splice dstSize = " << DstMBB->size()
1683 << "srcSize = " << SrcMBB->size() << "\n";
1686 //splice insert before insertPos
1687 DstMBB->splice(I, SrcMBB, SrcMBB->begin(), SpliceEnd);
1690 dbgs() << "migrateInstruction after splice dstSize = " << DstMBB->size()
1691 << "srcSize = " << SrcMBB->size() << "\n";
1696 AMDGPUCFGStructurizer::normalizeInfiniteLoopExit(MachineLoop* LoopRep) {
1697 MachineBasicBlock *LoopHeader = LoopRep->getHeader();
1698 MachineBasicBlock *LoopLatch = LoopRep->getLoopLatch();
1699 const TargetRegisterClass * I32RC = TRI->getCFGStructurizerRegClass(MVT::i32);
1701 if (!LoopHeader || !LoopLatch)
1703 MachineInstr *BranchMI = getLoopendBlockBranchInstr(LoopLatch);
1704 // Is LoopRep an infinite loop ?
1705 if (!BranchMI || !isUncondBranch(BranchMI))
1708 MachineBasicBlock *DummyExitBlk = FuncRep->CreateMachineBasicBlock();
1709 FuncRep->push_back(DummyExitBlk); //insert to function
1710 SHOWNEWBLK(DummyExitBlk, "DummyExitBlock to normalize infiniteLoop: ");
1711 DEBUG(dbgs() << "Old branch instr: " << *BranchMI << "\n";);
1712 MachineBasicBlock::iterator I = BranchMI;
1713 unsigned ImmReg = FuncRep->getRegInfo().createVirtualRegister(I32RC);
1714 llvm_unreachable("Extra register needed to handle CFG");
1715 MachineInstr *NewMI = insertInstrBefore(I, AMDGPU::BRANCH_COND_i32);
1716 MachineInstrBuilder MIB(*FuncRep, NewMI);
1717 MIB.addMBB(LoopHeader);
1718 MIB.addReg(ImmReg, false);
1719 SHOWNEWINSTR(NewMI);
1720 BranchMI->eraseFromParent();
1721 LoopLatch->addSuccessor(DummyExitBlk);
1723 return DummyExitBlk;
1726 void AMDGPUCFGStructurizer::removeUnconditionalBranch(MachineBasicBlock *MBB) {
1727 MachineInstr *BranchMI;
1729 // I saw two unconditional branch in one basic block in example
1730 // test_fc_do_while_or.c need to fix the upstream on this to remove the loop.
1731 while ((BranchMI = getLoopendBlockBranchInstr(MBB))
1732 && isUncondBranch(BranchMI)) {
1733 DEBUG(dbgs() << "Removing uncond branch instr"; BranchMI->dump(););
1734 BranchMI->eraseFromParent();
1738 void AMDGPUCFGStructurizer::removeRedundantConditionalBranch(
1739 MachineBasicBlock *MBB) {
1740 if (MBB->succ_size() != 2)
1742 MachineBasicBlock *MBB1 = *MBB->succ_begin();
1743 MachineBasicBlock *MBB2 = *(++MBB->succ_begin());
1747 MachineInstr *BranchMI = getNormalBlockBranchInstr(MBB);
1748 assert(BranchMI && isCondBranch(BranchMI));
1749 DEBUG(dbgs() << "Removing unneeded cond branch instr"; BranchMI->dump(););
1750 BranchMI->eraseFromParent();
1751 SHOWNEWBLK(MBB1, "Removing redundant successor");
1752 MBB->removeSuccessor(MBB1);
1755 void AMDGPUCFGStructurizer::addDummyExitBlock(
1756 SmallVectorImpl<MachineBasicBlock*> &RetMBB) {
1757 MachineBasicBlock *DummyExitBlk = FuncRep->CreateMachineBasicBlock();
1758 FuncRep->push_back(DummyExitBlk); //insert to function
1759 insertInstrEnd(DummyExitBlk, AMDGPU::RETURN);
1761 for (SmallVectorImpl<MachineBasicBlock *>::iterator It = RetMBB.begin(),
1762 E = RetMBB.end(); It != E; ++It) {
1763 MachineBasicBlock *MBB = *It;
1764 MachineInstr *MI = getReturnInstr(MBB);
1766 MI->eraseFromParent();
1767 MBB->addSuccessor(DummyExitBlk);
1769 dbgs() << "Add dummyExitBlock to BB" << MBB->getNumber()
1773 SHOWNEWBLK(DummyExitBlk, "DummyExitBlock: ");
1776 void AMDGPUCFGStructurizer::removeSuccessor(MachineBasicBlock *MBB) {
1777 while (MBB->succ_size())
1778 MBB->removeSuccessor(*MBB->succ_begin());
1781 void AMDGPUCFGStructurizer::recordSccnum(MachineBasicBlock *MBB,
1783 BlockInformation *&srcBlkInfo = BlockInfoMap[MBB];
1785 srcBlkInfo = new BlockInformation();
1786 srcBlkInfo->SccNum = SccNum;
1789 void AMDGPUCFGStructurizer::retireBlock(MachineBasicBlock *MBB) {
1791 dbgs() << "Retiring BB" << MBB->getNumber() << "\n";
1794 BlockInformation *&SrcBlkInfo = BlockInfoMap[MBB];
1797 SrcBlkInfo = new BlockInformation();
1799 SrcBlkInfo->IsRetired = true;
1800 assert(MBB->succ_size() == 0 && MBB->pred_size() == 0
1801 && "can't retire block yet");
1804 void AMDGPUCFGStructurizer::setLoopLandBlock(MachineLoop *loopRep,
1805 MachineBasicBlock *MBB) {
1806 MachineBasicBlock *&TheEntry = LLInfoMap[loopRep];
1808 MBB = FuncRep->CreateMachineBasicBlock();
1809 FuncRep->push_back(MBB); //insert to function
1810 SHOWNEWBLK(MBB, "DummyLandingBlock for loop without break: ");
1814 dbgs() << "setLoopLandBlock loop-header = BB"
1815 << loopRep->getHeader()->getNumber()
1816 << " landing-block = BB" << MBB->getNumber() << "\n";
1821 AMDGPUCFGStructurizer::findNearestCommonPostDom(MachineBasicBlock *MBB1,
1822 MachineBasicBlock *MBB2) {
1824 if (PDT->dominates(MBB1, MBB2))
1826 if (PDT->dominates(MBB2, MBB1))
1829 MachineDomTreeNode *Node1 = PDT->getNode(MBB1);
1830 MachineDomTreeNode *Node2 = PDT->getNode(MBB2);
1832 // Handle newly cloned node.
1833 if (!Node1 && MBB1->succ_size() == 1)
1834 return findNearestCommonPostDom(*MBB1->succ_begin(), MBB2);
1835 if (!Node2 && MBB2->succ_size() == 1)
1836 return findNearestCommonPostDom(MBB1, *MBB2->succ_begin());
1838 if (!Node1 || !Node2)
1841 Node1 = Node1->getIDom();
1843 if (PDT->dominates(Node1, Node2))
1844 return Node1->getBlock();
1845 Node1 = Node1->getIDom();
1852 AMDGPUCFGStructurizer::findNearestCommonPostDom(
1853 std::set<MachineBasicBlock *> &MBBs) {
1854 MachineBasicBlock *CommonDom;
1855 std::set<MachineBasicBlock *>::const_iterator It = MBBs.begin();
1856 std::set<MachineBasicBlock *>::const_iterator E = MBBs.end();
1857 for (CommonDom = *It; It != E && CommonDom; ++It) {
1858 MachineBasicBlock *MBB = *It;
1859 if (MBB != CommonDom)
1860 CommonDom = findNearestCommonPostDom(MBB, CommonDom);
1864 dbgs() << "Common post dominator for exit blocks is ";
1866 dbgs() << "BB" << CommonDom->getNumber() << "\n";
1874 char AMDGPUCFGStructurizer::ID = 0;
1876 } // end anonymous namespace
1879 FunctionPass *llvm::createAMDGPUCFGStructurizerPass(TargetMachine &tm) {
1880 return new AMDGPUCFGStructurizer(tm);