1 //===-- AMDILCFGStructurizer.cpp - CFG Structurizer -----------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
9 //==-----------------------------------------------------------------------===//
12 #define DEBUG_TYPE "structcfg"
15 #include "AMDGPUInstrInfo.h"
16 #include "llvm/ADT/SCCIterator.h"
17 #include "llvm/ADT/SmallVector.h"
18 #include "llvm/ADT/Statistic.h"
19 #include "llvm/Analysis/DominatorInternals.h"
20 #include "llvm/Analysis/Dominators.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/Target/TargetInstrInfo.h"
31 #include "llvm/Target/TargetMachine.h"
35 #define DEFAULT_VEC_SLOTS 8
39 //===----------------------------------------------------------------------===//
41 // Statistics for CFGStructurizer.
43 //===----------------------------------------------------------------------===//
45 STATISTIC(numSerialPatternMatch, "CFGStructurizer number of serial pattern "
47 STATISTIC(numIfPatternMatch, "CFGStructurizer number of if pattern "
49 STATISTIC(numLoopbreakPatternMatch, "CFGStructurizer number of loop-break "
51 STATISTIC(numLoopcontPatternMatch, "CFGStructurizer number of loop-continue "
53 STATISTIC(numLoopPatternMatch, "CFGStructurizer number of loop pattern "
55 STATISTIC(numClonedBlock, "CFGStructurizer cloned blocks");
56 STATISTIC(numClonedInstr, "CFGStructurizer cloned instructions");
58 //===----------------------------------------------------------------------===//
60 // Miscellaneous utility for CFGStructurizer.
62 //===----------------------------------------------------------------------===//
64 #define SHOWNEWINSTR(i) \
65 if (DEBUGME) errs() << "New instr: " << *i << "\n"
67 #define SHOWNEWBLK(b, msg) \
69 errs() << msg << "BB" << b->getNumber() << "size " << b->size(); \
73 #define SHOWBLK_DETAIL(b, msg) \
76 errs() << msg << "BB" << b->getNumber() << "size " << b->size(); \
82 #define INVALIDSCCNUM -1
83 #define INVALIDREGNUM 0
85 template<class LoopinfoT>
86 void PrintLoopinfo(const LoopinfoT &LoopInfo, llvm::raw_ostream &OS) {
87 for (typename LoopinfoT::iterator iter = LoopInfo.begin(),
88 iterEnd = LoopInfo.end();
89 iter != iterEnd; ++iter) {
90 (*iter)->print(OS, 0);
95 void ReverseVector(SmallVector<NodeT *, DEFAULT_VEC_SLOTS> &Src) {
96 size_t sz = Src.size();
97 for (size_t i = 0; i < sz/2; ++i) {
99 Src[i] = Src[sz - i - 1];
104 } // end anonymous namespace
106 //===----------------------------------------------------------------------===//
108 // supporting data structure for CFGStructurizer
110 //===----------------------------------------------------------------------===//
113 template<class PassT>
114 struct CFGStructTraits {
117 template <class InstrT>
118 class BlockInformation {
122 //SmallVector<InstrT*, DEFAULT_VEC_SLOTS> succInstr;
123 //Instructions defining the corresponding successor.
124 BlockInformation() : isRetired(false), sccNum(INVALIDSCCNUM) {}
127 template <class BlockT, class InstrT, class RegiT>
128 class LandInformation {
131 std::set<RegiT> breakInitRegs; //Registers that need to "reg = 0", before
132 //WHILELOOP(thisloop) init before entering
134 std::set<RegiT> contInitRegs; //Registers that need to "reg = 0", after
135 //WHILELOOP(thisloop) init after entering
137 std::set<RegiT> endbranchInitRegs; //Init before entering this loop, at loop
138 //land block, branch cond on this reg.
139 std::set<RegiT> breakOnRegs; //registers that need to "if (reg) break
140 //endif" after ENDLOOP(thisloop) break
141 //outerLoopOf(thisLoop).
142 std::set<RegiT> contOnRegs; //registers that need to "if (reg) continue
143 //endif" after ENDLOOP(thisloop) continue on
144 //outerLoopOf(thisLoop).
145 LandInformation() : landBlk(NULL) {}
148 } // end anonymous namespace
150 //===----------------------------------------------------------------------===//
154 //===----------------------------------------------------------------------===//
157 // bixia TODO: port it to BasicBlock, not just MachineBasicBlock.
158 template<class PassT>
159 class CFGStructurizer {
163 SinglePath_InPath = 1,
164 SinglePath_NotInPath = 2
168 typedef typename PassT::InstructionType InstrT;
169 typedef typename PassT::FunctionType FuncT;
170 typedef typename PassT::DominatortreeType DomTreeT;
171 typedef typename PassT::PostDominatortreeType PostDomTreeT;
172 typedef typename PassT::DomTreeNodeType DomTreeNodeT;
173 typedef typename PassT::LoopinfoType LoopInfoT;
175 typedef GraphTraits<FuncT *> FuncGTraits;
176 //typedef FuncGTraits::nodes_iterator BlockIterator;
177 typedef typename FuncT::iterator BlockIterator;
179 typedef typename FuncGTraits::NodeType BlockT;
180 typedef GraphTraits<BlockT *> BlockGTraits;
181 typedef GraphTraits<Inverse<BlockT *> > InvBlockGTraits;
182 //typedef BlockGTraits::succ_iterator InstructionIterator;
183 typedef typename BlockT::iterator InstrIterator;
185 typedef CFGStructTraits<PassT> CFGTraits;
186 typedef BlockInformation<InstrT> BlockInfo;
187 typedef std::map<BlockT *, BlockInfo *> BlockInfoMap;
190 typedef typename PassT::LoopType LoopT;
191 typedef LandInformation<BlockT, InstrT, RegiT> LoopLandInfo;
192 typedef std::map<LoopT *, LoopLandInfo *> LoopLandInfoMap;
193 //landing info for loop break
194 typedef SmallVector<BlockT *, 32> BlockTSmallerVector;
200 /// Perform the CFG structurization
201 bool run(FuncT &Func, PassT &Pass, const AMDGPURegisterInfo *tri);
203 /// Perform the CFG preparation
204 bool prepare(FuncT &Func, PassT &Pass, const AMDGPURegisterInfo *tri);
207 void reversePredicateSetter(typename BlockT::iterator);
209 void printOrderedBlocks(llvm::raw_ostream &OS);
210 int patternMatch(BlockT *CurBlock);
211 int patternMatchGroup(BlockT *CurBlock);
213 int serialPatternMatch(BlockT *CurBlock);
214 int ifPatternMatch(BlockT *CurBlock);
215 int switchPatternMatch(BlockT *CurBlock);
216 int loopendPatternMatch(BlockT *CurBlock);
217 int loopPatternMatch(BlockT *CurBlock);
219 int loopbreakPatternMatch(LoopT *LoopRep, BlockT *LoopHeader);
220 int loopcontPatternMatch(LoopT *LoopRep, BlockT *LoopHeader);
221 //int loopWithoutBreak(BlockT *);
223 void handleLoopbreak (BlockT *ExitingBlock, LoopT *ExitingLoop,
224 BlockT *ExitBlock, LoopT *exitLoop, BlockT *landBlock);
225 void handleLoopcontBlock(BlockT *ContingBlock, LoopT *contingLoop,
226 BlockT *ContBlock, LoopT *contLoop);
227 bool isSameloopDetachedContbreak(BlockT *Src1Block, BlockT *Src2Block);
228 int handleJumpintoIf(BlockT *HeadBlock, BlockT *TrueBlock,
230 int handleJumpintoIfImp(BlockT *HeadBlock, BlockT *TrueBlock,
232 int improveSimpleJumpintoIf(BlockT *HeadBlock, BlockT *TrueBlock,
233 BlockT *FalseBlock, BlockT **LandBlockPtr);
234 void showImproveSimpleJumpintoIf(BlockT *HeadBlock, BlockT *TrueBlock,
235 BlockT *FalseBlock, BlockT *LandBlock,
236 bool Detail = false);
237 PathToKind singlePathTo(BlockT *SrcBlock, BlockT *DstBlock,
238 bool AllowSideEntry = true);
239 BlockT *singlePathEnd(BlockT *srcBlock, BlockT *DstBlock,
240 bool AllowSideEntry = true);
241 int cloneOnSideEntryTo(BlockT *PreBlock, BlockT *SrcBlock, BlockT *DstBlock);
242 void mergeSerialBlock(BlockT *DstBlock, BlockT *srcBlock);
244 void mergeIfthenelseBlock(InstrT *BranchInstr, BlockT *CurBlock,
245 BlockT *TrueBlock, BlockT *FalseBlock,
247 void mergeLooplandBlock(BlockT *DstBlock, LoopLandInfo *LoopLand);
248 void mergeLoopbreakBlock(BlockT *ExitingBlock, BlockT *ExitBlock,
249 BlockT *ExitLandBlock, RegiT SetReg);
250 void settleLoopcontBlock(BlockT *ContingBlock, BlockT *ContBlock,
252 BlockT *relocateLoopcontBlock(LoopT *ParentLoopRep, LoopT *LoopRep,
253 std::set<BlockT*> &ExitBlockSet,
254 BlockT *ExitLandBlk);
255 BlockT *addLoopEndbranchBlock(LoopT *LoopRep,
256 BlockTSmallerVector &ExitingBlocks,
257 BlockTSmallerVector &ExitBlocks);
258 BlockT *normalizeInfiniteLoopExit(LoopT *LoopRep);
259 void removeUnconditionalBranch(BlockT *SrcBlock);
260 void removeRedundantConditionalBranch(BlockT *SrcBlock);
261 void addDummyExitBlock(SmallVector<BlockT *, DEFAULT_VEC_SLOTS> &RetBlocks);
263 void removeSuccessor(BlockT *SrcBlock);
264 BlockT *cloneBlockForPredecessor(BlockT *CurBlock, BlockT *PredBlock);
265 BlockT *exitingBlock2ExitBlock (LoopT *LoopRep, BlockT *exitingBlock);
267 void migrateInstruction(BlockT *SrcBlock, BlockT *DstBlock,
268 InstrIterator InsertPos);
270 void recordSccnum(BlockT *SrcBlock, int SCCNum);
271 int getSCCNum(BlockT *srcBlk);
273 void retireBlock(BlockT *DstBlock, BlockT *SrcBlock);
274 bool isRetiredBlock(BlockT *SrcBlock);
275 bool isActiveLoophead(BlockT *CurBlock);
276 bool needMigrateBlock(BlockT *Block);
278 BlockT *recordLoopLandBlock(LoopT *LoopRep, BlockT *LandBlock,
279 BlockTSmallerVector &exitBlocks,
280 std::set<BlockT*> &ExitBlockSet);
281 void setLoopLandBlock(LoopT *LoopRep, BlockT *Block = NULL);
282 BlockT *getLoopLandBlock(LoopT *LoopRep);
283 LoopLandInfo *getLoopLandInfo(LoopT *LoopRep);
285 void addLoopBreakOnReg(LoopT *LoopRep, RegiT RegNum);
286 void addLoopContOnReg(LoopT *LoopRep, RegiT RegNum);
287 void addLoopBreakInitReg(LoopT *LoopRep, RegiT RegNum);
288 void addLoopContInitReg(LoopT *LoopRep, RegiT RegNum);
289 void addLoopEndbranchInitReg(LoopT *LoopRep, RegiT RegNum);
291 bool hasBackEdge(BlockT *curBlock);
292 unsigned getLoopDepth (LoopT *LoopRep);
293 int countActiveBlock(
294 typename SmallVector<BlockT *, DEFAULT_VEC_SLOTS>::const_iterator IterStart,
295 typename SmallVector<BlockT *, DEFAULT_VEC_SLOTS>::const_iterator IterEnd);
296 BlockT *findNearestCommonPostDom(std::set<BlockT *>&);
297 BlockT *findNearestCommonPostDom(BlockT *Block1, BlockT *Block2);
301 PostDomTreeT *postDomTree;
306 BlockInfoMap blockInfoMap;
307 LoopLandInfoMap loopLandInfoMap;
308 SmallVector<BlockT *, DEFAULT_VEC_SLOTS> orderedBlks;
309 const AMDGPURegisterInfo *TRI;
311 }; //template class CFGStructurizer
313 template<class PassT> CFGStructurizer<PassT>::CFGStructurizer()
314 : domTree(NULL), postDomTree(NULL), loopInfo(NULL) {
317 template<class PassT> CFGStructurizer<PassT>::~CFGStructurizer() {
318 for (typename BlockInfoMap::iterator I = blockInfoMap.begin(),
319 E = blockInfoMap.end(); I != E; ++I) {
324 template<class PassT>
325 bool CFGStructurizer<PassT>::prepare(FuncT &func, PassT &pass,
326 const AMDGPURegisterInfo * tri) {
331 bool changed = false;
333 //FIXME: if not reducible flow graph, make it so ???
336 errs() << "AMDGPUCFGStructurizer::prepare\n";
339 loopInfo = CFGTraits::getLoopInfo(pass);
341 errs() << "LoopInfo:\n";
342 PrintLoopinfo(*loopInfo, errs());
347 errs() << "Ordered blocks:\n";
348 printOrderedBlocks(errs());
351 SmallVector<BlockT *, DEFAULT_VEC_SLOTS> retBlks;
353 for (typename LoopInfoT::iterator iter = loopInfo->begin(),
354 iterEnd = loopInfo->end();
355 iter != iterEnd; ++iter) {
356 LoopT* loopRep = (*iter);
357 BlockTSmallerVector exitingBlks;
358 loopRep->getExitingBlocks(exitingBlks);
360 if (exitingBlks.size() == 0) {
361 BlockT* dummyExitBlk = normalizeInfiniteLoopExit(loopRep);
362 if (dummyExitBlk != NULL)
363 retBlks.push_back(dummyExitBlk);
367 // Remove unconditional branch instr.
368 // Add dummy exit block iff there are multiple returns.
370 for (typename SmallVector<BlockT *, DEFAULT_VEC_SLOTS>::const_iterator
371 iterBlk = orderedBlks.begin(), iterEndBlk = orderedBlks.end();
372 iterBlk != iterEndBlk;
374 BlockT *curBlk = *iterBlk;
375 removeUnconditionalBranch(curBlk);
376 removeRedundantConditionalBranch(curBlk);
377 if (CFGTraits::isReturnBlock(curBlk)) {
378 retBlks.push_back(curBlk);
380 assert(curBlk->succ_size() <= 2);
383 if (retBlks.size() >= 2) {
384 addDummyExitBlock(retBlks);
389 } //CFGStructurizer::prepare
391 template<class PassT>
392 bool CFGStructurizer<PassT>::run(FuncT &func, PassT &pass,
393 const AMDGPURegisterInfo * tri) {
398 //Assume reducible CFG...
400 errs() << "AMDGPUCFGStructurizer::run\n";
404 domTree = CFGTraits::getDominatorTree(pass);
406 domTree->print(errs(), (const llvm::Module*)0);
409 postDomTree = CFGTraits::getPostDominatorTree(pass);
411 postDomTree->print(errs());
414 loopInfo = CFGTraits::getLoopInfo(pass);
416 errs() << "LoopInfo:\n";
417 PrintLoopinfo(*loopInfo, errs());
422 //Use the worse block ordering to test the algorithm.
423 ReverseVector(orderedBlks);
427 errs() << "Ordered blocks:\n";
428 printOrderedBlocks(errs());
433 bool makeProgress = false;
434 int numRemainedBlk = countActiveBlock(orderedBlks.begin(),
440 errs() << "numIter = " << numIter
441 << ", numRemaintedBlk = " << numRemainedBlk << "\n";
444 typename SmallVector<BlockT *, DEFAULT_VEC_SLOTS>::const_iterator
445 iterBlk = orderedBlks.begin();
446 typename SmallVector<BlockT *, DEFAULT_VEC_SLOTS>::const_iterator
447 iterBlkEnd = orderedBlks.end();
449 typename SmallVector<BlockT *, DEFAULT_VEC_SLOTS>::const_iterator
450 sccBeginIter = iterBlk;
451 BlockT *sccBeginBlk = NULL;
452 int sccNumBlk = 0; // The number of active blocks, init to a
453 // maximum possible number.
454 int sccNumIter; // Number of iteration in this SCC.
456 while (iterBlk != iterBlkEnd) {
459 if (sccBeginBlk == NULL) {
460 sccBeginIter = iterBlk;
461 sccBeginBlk = curBlk;
463 sccNumBlk = numRemainedBlk; // Init to maximum possible number.
465 errs() << "start processing SCC" << getSCCNum(sccBeginBlk);
470 if (!isRetiredBlock(curBlk)) {
471 patternMatch(curBlk);
476 bool contNextScc = true;
477 if (iterBlk == iterBlkEnd
478 || getSCCNum(sccBeginBlk) != getSCCNum(*iterBlk)) {
479 // Just finish one scc.
481 int sccRemainedNumBlk = countActiveBlock(sccBeginIter, iterBlk);
482 if (sccRemainedNumBlk != 1 && sccRemainedNumBlk >= sccNumBlk) {
484 errs() << "Can't reduce SCC " << getSCCNum(curBlk)
485 << ", sccNumIter = " << sccNumIter;
486 errs() << "doesn't make any progress\n";
489 } else if (sccRemainedNumBlk != 1 && sccRemainedNumBlk < sccNumBlk) {
490 sccNumBlk = sccRemainedNumBlk;
491 iterBlk = sccBeginIter;
494 errs() << "repeat processing SCC" << getSCCNum(curBlk)
495 << "sccNumIter = " << sccNumIter << "\n";
499 // Finish the current scc.
503 // Continue on next component in the current scc.
510 } //while, "one iteration" over the function.
512 BlockT *entryBlk = FuncGTraits::nodes_begin(&func);
513 if (entryBlk->succ_size() == 0) {
516 errs() << "Reduce to one block\n";
519 int newnumRemainedBlk
520 = countActiveBlock(orderedBlks.begin(), orderedBlks.end());
521 // consider cloned blocks ??
522 if (newnumRemainedBlk == 1 || newnumRemainedBlk < numRemainedBlk) {
524 numRemainedBlk = newnumRemainedBlk;
526 makeProgress = false;
528 errs() << "No progress\n";
532 } while (!finish && makeProgress);
534 // Misc wrap up to maintain the consistency of the Function representation.
535 CFGTraits::wrapup(FuncGTraits::nodes_begin(&func));
537 // Detach retired Block, release memory.
538 for (typename BlockInfoMap::iterator iterMap = blockInfoMap.begin(),
539 iterEndMap = blockInfoMap.end(); iterMap != iterEndMap; ++iterMap) {
540 if ((*iterMap).second && (*iterMap).second->isRetired) {
541 assert(((*iterMap).first)->getNumber() != -1);
543 errs() << "Erase BB" << ((*iterMap).first)->getNumber() << "\n";
545 (*iterMap).first->eraseFromParent(); //Remove from the parent Function.
547 delete (*iterMap).second;
549 blockInfoMap.clear();
551 // clear loopLandInfoMap
552 for (typename LoopLandInfoMap::iterator iterMap = loopLandInfoMap.begin(),
553 iterEndMap = loopLandInfoMap.end(); iterMap != iterEndMap; ++iterMap) {
554 delete (*iterMap).second;
556 loopLandInfoMap.clear();
563 assert(!"IRREDUCIBL_CF");
567 } //CFGStructurizer::run
569 /// Print the ordered Blocks.
571 template<class PassT>
572 void CFGStructurizer<PassT>::printOrderedBlocks(llvm::raw_ostream &os) {
574 for (typename SmallVector<BlockT *, DEFAULT_VEC_SLOTS>::const_iterator
575 iterBlk = orderedBlks.begin(), iterBlkEnd = orderedBlks.end();
576 iterBlk != iterBlkEnd;
578 os << "BB" << (*iterBlk)->getNumber();
579 os << "(" << getSCCNum(*iterBlk) << "," << (*iterBlk)->size() << ")";
580 if (i != 0 && i % 10 == 0) {
586 } //printOrderedBlocks
588 /// Compute the reversed DFS post order of Blocks
590 template<class PassT> void CFGStructurizer<PassT>::orderBlocks() {
593 for (scc_iterator<FuncT *> sccIter = scc_begin(funcRep),
594 sccEnd = scc_end(funcRep); sccIter != sccEnd; ++sccIter, ++sccNum) {
595 std::vector<BlockT *> &sccNext = *sccIter;
596 for (typename std::vector<BlockT *>::const_iterator
597 blockIter = sccNext.begin(), blockEnd = sccNext.end();
598 blockIter != blockEnd; ++blockIter) {
600 orderedBlks.push_back(bb);
601 recordSccnum(bb, sccNum);
605 //walk through all the block in func to check for unreachable
606 for (BlockIterator blockIter1 = FuncGTraits::nodes_begin(funcRep),
607 blockEnd1 = FuncGTraits::nodes_end(funcRep);
608 blockIter1 != blockEnd1; ++blockIter1) {
609 BlockT *bb = &(*blockIter1);
610 sccNum = getSCCNum(bb);
611 if (sccNum == INVALIDSCCNUM) {
612 errs() << "unreachable block BB" << bb->getNumber() << "\n";
617 template<class PassT> int CFGStructurizer<PassT>::patternMatch(BlockT *curBlk) {
622 errs() << "Begin patternMatch BB" << curBlk->getNumber() << "\n";
625 while ((curMatch = patternMatchGroup(curBlk)) > 0) {
626 numMatch += curMatch;
630 errs() << "End patternMatch BB" << curBlk->getNumber()
631 << ", numMatch = " << numMatch << "\n";
637 template<class PassT>
638 int CFGStructurizer<PassT>::patternMatchGroup(BlockT *curBlk) {
640 numMatch += serialPatternMatch(curBlk);
641 numMatch += ifPatternMatch(curBlk);
642 numMatch += loopendPatternMatch(curBlk);
643 numMatch += loopPatternMatch(curBlk);
647 template<class PassT>
648 int CFGStructurizer<PassT>::serialPatternMatch(BlockT *curBlk) {
649 if (curBlk->succ_size() != 1) {
653 BlockT *childBlk = *curBlk->succ_begin();
654 if (childBlk->pred_size() != 1 || isActiveLoophead(childBlk)) {
658 mergeSerialBlock(curBlk, childBlk);
659 ++numSerialPatternMatch;
661 } //serialPatternMatch
663 template<class PassT>
664 int CFGStructurizer<PassT>::ifPatternMatch(BlockT *curBlk) {
666 if (curBlk->succ_size() != 2) {
670 if (hasBackEdge(curBlk)) {
674 InstrT *branchInstr = CFGTraits::getNormalBlockBranchInstr(curBlk);
675 if (branchInstr == NULL) {
679 assert(CFGTraits::isCondBranch(branchInstr));
681 BlockT *trueBlk = CFGTraits::getTrueBranch(branchInstr);
682 BlockT *falseBlk = CFGTraits::getFalseBranch(curBlk, branchInstr);
687 if (trueBlk->succ_size() == 1 && falseBlk->succ_size() == 1
688 && *trueBlk->succ_begin() == *falseBlk->succ_begin()) {
689 landBlk = *trueBlk->succ_begin();
690 } else if (trueBlk->succ_size() == 0 && falseBlk->succ_size() == 0) {
692 } else if (trueBlk->succ_size() == 1 && *trueBlk->succ_begin() == falseBlk) {
695 } else if (falseBlk->succ_size() == 1
696 && *falseBlk->succ_begin() == trueBlk) {
699 } else if (falseBlk->succ_size() == 1
700 && isSameloopDetachedContbreak(trueBlk, falseBlk)) {
701 landBlk = *falseBlk->succ_begin();
702 } else if (trueBlk->succ_size() == 1
703 && isSameloopDetachedContbreak(falseBlk, trueBlk)) {
704 landBlk = *trueBlk->succ_begin();
706 return handleJumpintoIf(curBlk, trueBlk, falseBlk);
709 // improveSimpleJumpinfoIf can handle the case where landBlk == NULL but the
710 // new BB created for landBlk==NULL may introduce new challenge to the
711 // reduction process.
712 if (landBlk != NULL &&
713 ((trueBlk && trueBlk->pred_size() > 1)
714 || (falseBlk && falseBlk->pred_size() > 1))) {
715 cloned += improveSimpleJumpintoIf(curBlk, trueBlk, falseBlk, &landBlk);
718 if (trueBlk && trueBlk->pred_size() > 1) {
719 trueBlk = cloneBlockForPredecessor(trueBlk, curBlk);
723 if (falseBlk && falseBlk->pred_size() > 1) {
724 falseBlk = cloneBlockForPredecessor(falseBlk, curBlk);
728 mergeIfthenelseBlock(branchInstr, curBlk, trueBlk, falseBlk, landBlk);
732 numClonedBlock += cloned;
737 template<class PassT>
738 int CFGStructurizer<PassT>::switchPatternMatch(BlockT *curBlk) {
740 } //switchPatternMatch
742 template<class PassT>
743 int CFGStructurizer<PassT>::loopendPatternMatch(BlockT *curBlk) {
744 LoopT *loopRep = loopInfo->getLoopFor(curBlk);
745 typename std::vector<LoopT *> nestedLoops;
747 nestedLoops.push_back(loopRep);
748 loopRep = loopRep->getParentLoop();
751 if (nestedLoops.size() == 0) {
755 // Process nested loop outside->inside, so "continue" to a outside loop won't
756 // be mistaken as "break" of the current loop.
758 for (typename std::vector<LoopT *>::reverse_iterator
759 iter = nestedLoops.rbegin(), iterEnd = nestedLoops.rend();
760 iter != iterEnd; ++iter) {
763 if (getLoopLandBlock(loopRep) != NULL) {
767 BlockT *loopHeader = loopRep->getHeader();
769 int numBreak = loopbreakPatternMatch(loopRep, loopHeader);
771 if (numBreak == -1) {
775 int numCont = loopcontPatternMatch(loopRep, loopHeader);
776 num += numBreak + numCont;
780 } //loopendPatternMatch
782 template<class PassT>
783 int CFGStructurizer<PassT>::loopPatternMatch(BlockT *curBlk) {
784 if (curBlk->succ_size() != 0) {
789 LoopT *loopRep = loopInfo->getLoopFor(curBlk);
790 while (loopRep && loopRep->getHeader() == curBlk) {
791 LoopLandInfo *loopLand = getLoopLandInfo(loopRep);
793 BlockT *landBlk = loopLand->landBlk;
795 if (!isRetiredBlock(landBlk)) {
796 mergeLooplandBlock(curBlk, loopLand);
800 loopRep = loopRep->getParentLoop();
803 numLoopPatternMatch += numLoop;
808 template<class PassT>
809 int CFGStructurizer<PassT>::loopbreakPatternMatch(LoopT *loopRep,
810 BlockT *loopHeader) {
811 BlockTSmallerVector exitingBlks;
812 loopRep->getExitingBlocks(exitingBlks);
815 errs() << "Loop has " << exitingBlks.size() << " exiting blocks\n";
818 if (exitingBlks.size() == 0) {
819 setLoopLandBlock(loopRep);
823 // Compute the corresponding exitBlks and exit block set.
824 BlockTSmallerVector exitBlks;
825 std::set<BlockT *> exitBlkSet;
826 for (typename BlockTSmallerVector::const_iterator iter = exitingBlks.begin(),
827 iterEnd = exitingBlks.end(); iter != iterEnd; ++iter) {
828 BlockT *exitingBlk = *iter;
829 BlockT *exitBlk = exitingBlock2ExitBlock(loopRep, exitingBlk);
830 exitBlks.push_back(exitBlk);
831 exitBlkSet.insert(exitBlk); //non-duplicate insert
834 assert(exitBlkSet.size() > 0);
835 assert(exitBlks.size() == exitingBlks.size());
838 errs() << "Loop has " << exitBlkSet.size() << " exit blocks\n";
842 BlockT *exitLandBlk = NULL;
846 if (exitBlkSet.size() == 1) {
847 exitLandBlk = *exitBlkSet.begin();
849 exitLandBlk = findNearestCommonPostDom(exitBlkSet);
851 if (exitLandBlk == NULL) {
855 bool allInPath = true;
856 bool allNotInPath = true;
857 for (typename std::set<BlockT*>::const_iterator
858 iter = exitBlkSet.begin(),
859 iterEnd = exitBlkSet.end();
860 iter != iterEnd; ++iter) {
861 BlockT *exitBlk = *iter;
863 PathToKind pathKind = singlePathTo(exitBlk, exitLandBlk, true);
865 errs() << "BB" << exitBlk->getNumber()
866 << " to BB" << exitLandBlk->getNumber() << " PathToKind="
870 allInPath = allInPath && (pathKind == SinglePath_InPath);
871 allNotInPath = allNotInPath && (pathKind == SinglePath_NotInPath);
873 if (!allInPath && !allNotInPath) {
875 errs() << "singlePath check fail\n";
879 } // check all exit blocks
883 // TODO: Simplify, maybe separate function?
884 LoopT *parentLoopRep = loopRep->getParentLoop();
885 BlockT *parentLoopHeader = NULL;
887 parentLoopHeader = parentLoopRep->getHeader();
889 if (exitLandBlk == parentLoopHeader &&
890 (exitLandBlk = relocateLoopcontBlock(parentLoopRep,
893 exitLandBlk)) != NULL) {
895 errs() << "relocateLoopcontBlock success\n";
897 } else if ((exitLandBlk = addLoopEndbranchBlock(loopRep,
899 exitBlks)) != NULL) {
901 errs() << "insertEndbranchBlock success\n";
905 errs() << "loop exit fail\n";
911 // Handle side entry to exit path.
914 for (typename BlockTSmallerVector::iterator iterExiting =
916 iterExitingEnd = exitingBlks.end();
917 iterExiting != iterExitingEnd; ++iterExiting) {
918 BlockT *exitingBlk = *iterExiting;
919 BlockT *exitBlk = exitingBlock2ExitBlock(loopRep, exitingBlk);
920 BlockT *newExitBlk = exitBlk;
922 if (exitBlk != exitLandBlk && exitBlk->pred_size() > 1) {
923 newExitBlk = cloneBlockForPredecessor(exitBlk, exitingBlk);
927 numCloned += cloneOnSideEntryTo(exitingBlk, newExitBlk, exitLandBlk);
929 exitBlks.push_back(newExitBlk);
930 exitBlkSet.insert(newExitBlk);
933 for (typename BlockTSmallerVector::iterator iterExit = exitBlks.begin(),
934 iterExitEnd = exitBlks.end();
935 iterExit != iterExitEnd; ++iterExit) {
936 BlockT *exitBlk = *iterExit;
937 numSerial += serialPatternMatch(exitBlk);
940 for (typename BlockTSmallerVector::iterator iterExit = exitBlks.begin(),
941 iterExitEnd = exitBlks.end();
942 iterExit != iterExitEnd; ++iterExit) {
943 BlockT *exitBlk = *iterExit;
944 if (exitBlk->pred_size() > 1) {
945 if (exitBlk != exitLandBlk) {
949 if (exitBlk != exitLandBlk &&
950 (exitBlk->succ_size() != 1 ||
951 *exitBlk->succ_begin() != exitLandBlk)) {
958 exitLandBlk = recordLoopLandBlock(loopRep, exitLandBlk, exitBlks, exitBlkSet);
960 // Fold break into the breaking block. Leverage across level breaks.
961 assert(exitingBlks.size() == exitBlks.size());
962 for (typename BlockTSmallerVector::const_iterator iterExit = exitBlks.begin(),
963 iterExiting = exitingBlks.begin(), iterExitEnd = exitBlks.end();
964 iterExit != iterExitEnd; ++iterExit, ++iterExiting) {
965 BlockT *exitBlk = *iterExit;
966 BlockT *exitingBlk = *iterExiting;
967 assert(exitBlk->pred_size() == 1 || exitBlk == exitLandBlk);
968 LoopT *exitingLoop = loopInfo->getLoopFor(exitingBlk);
969 handleLoopbreak(exitingBlk, exitingLoop, exitBlk, loopRep, exitLandBlk);
972 int numBreak = static_cast<int>(exitingBlks.size());
973 numLoopbreakPatternMatch += numBreak;
974 numClonedBlock += numCloned;
975 return numBreak + numSerial + numCloned;
976 } //loopbreakPatternMatch
978 template<class PassT>
979 int CFGStructurizer<PassT>::loopcontPatternMatch(LoopT *loopRep,
980 BlockT *loopHeader) {
982 SmallVector<BlockT *, DEFAULT_VEC_SLOTS> contBlk;
983 for (typename InvBlockGTraits::ChildIteratorType iter =
984 InvBlockGTraits::child_begin(loopHeader),
985 iterEnd = InvBlockGTraits::child_end(loopHeader);
986 iter != iterEnd; ++iter) {
987 BlockT *curBlk = *iter;
988 if (loopRep->contains(curBlk)) {
989 handleLoopcontBlock(curBlk, loopInfo->getLoopFor(curBlk),
990 loopHeader, loopRep);
991 contBlk.push_back(curBlk);
996 for (typename SmallVector<BlockT *, DEFAULT_VEC_SLOTS>::iterator
997 iter = contBlk.begin(), iterEnd = contBlk.end();
998 iter != iterEnd; ++iter) {
999 (*iter)->removeSuccessor(loopHeader);
1002 numLoopcontPatternMatch += numCont;
1005 } //loopcontPatternMatch
1008 template<class PassT>
1009 bool CFGStructurizer<PassT>::isSameloopDetachedContbreak(BlockT *src1Blk,
1011 // return true iff src1Blk->succ_size() == 0 && src1Blk and src2Blk are in the
1012 // same loop with LoopLandInfo without explicitly keeping track of
1013 // loopContBlks and loopBreakBlks, this is a method to get the information.
1015 if (src1Blk->succ_size() == 0) {
1016 LoopT *loopRep = loopInfo->getLoopFor(src1Blk);
1017 if (loopRep != NULL && loopRep == loopInfo->getLoopFor(src2Blk)) {
1018 LoopLandInfo *&theEntry = loopLandInfoMap[loopRep];
1019 if (theEntry != NULL) {
1021 errs() << "isLoopContBreakBlock yes src1 = BB"
1022 << src1Blk->getNumber()
1023 << " src2 = BB" << src2Blk->getNumber() << "\n";
1030 } //isSameloopDetachedContbreak
1032 template<class PassT>
1033 int CFGStructurizer<PassT>::handleJumpintoIf(BlockT *headBlk,
1036 int num = handleJumpintoIfImp(headBlk, trueBlk, falseBlk);
1039 errs() << "handleJumpintoIf swap trueBlk and FalseBlk" << "\n";
1041 num = handleJumpintoIfImp(headBlk, falseBlk, trueBlk);
1046 template<class PassT>
1047 int CFGStructurizer<PassT>::handleJumpintoIfImp(BlockT *headBlk,
1053 //trueBlk could be the common post dominator
1057 errs() << "handleJumpintoIfImp head = BB" << headBlk->getNumber()
1058 << " true = BB" << trueBlk->getNumber()
1059 << ", numSucc=" << trueBlk->succ_size()
1060 << " false = BB" << falseBlk->getNumber() << "\n";
1065 errs() << "check down = BB" << downBlk->getNumber();
1068 if (singlePathTo(falseBlk, downBlk) == SinglePath_InPath) {
1070 errs() << " working\n";
1073 num += cloneOnSideEntryTo(headBlk, trueBlk, downBlk);
1074 num += cloneOnSideEntryTo(headBlk, falseBlk, downBlk);
1076 numClonedBlock += num;
1077 num += serialPatternMatch(*headBlk->succ_begin());
1078 num += serialPatternMatch(*(++headBlk->succ_begin()));
1079 num += ifPatternMatch(headBlk);
1085 errs() << " not working\n";
1087 downBlk = (downBlk->succ_size() == 1) ? (*downBlk->succ_begin()) : NULL;
1088 } // walk down the postDomTree
1091 } //handleJumpintoIf
1093 template<class PassT>
1094 void CFGStructurizer<PassT>::showImproveSimpleJumpintoIf(BlockT *headBlk,
1099 errs() << "head = BB" << headBlk->getNumber()
1100 << " size = " << headBlk->size();
1103 headBlk->print(errs());
1108 errs() << ", true = BB" << trueBlk->getNumber() << " size = "
1109 << trueBlk->size() << " numPred = " << trueBlk->pred_size();
1112 trueBlk->print(errs());
1117 errs() << ", false = BB" << falseBlk->getNumber() << " size = "
1118 << falseBlk->size() << " numPred = " << falseBlk->pred_size();
1121 falseBlk->print(errs());
1126 errs() << ", land = BB" << landBlk->getNumber() << " size = "
1127 << landBlk->size() << " numPred = " << landBlk->pred_size();
1130 landBlk->print(errs());
1136 } //showImproveSimpleJumpintoIf
1138 template<class PassT>
1139 int CFGStructurizer<PassT>::improveSimpleJumpintoIf(BlockT *headBlk,
1142 BlockT **plandBlk) {
1143 bool migrateTrue = false;
1144 bool migrateFalse = false;
1146 BlockT *landBlk = *plandBlk;
1148 assert((trueBlk == NULL || trueBlk->succ_size() <= 1)
1149 && (falseBlk == NULL || falseBlk->succ_size() <= 1));
1151 if (trueBlk == falseBlk) {
1155 migrateTrue = needMigrateBlock(trueBlk);
1156 migrateFalse = needMigrateBlock(falseBlk);
1158 if (!migrateTrue && !migrateFalse) {
1162 // If we need to migrate either trueBlk and falseBlk, migrate the rest that
1163 // have more than one predecessors. without doing this, its predecessor
1164 // rather than headBlk will have undefined value in initReg.
1165 if (!migrateTrue && trueBlk && trueBlk->pred_size() > 1) {
1168 if (!migrateFalse && falseBlk && falseBlk->pred_size() > 1) {
1169 migrateFalse = true;
1173 errs() << "before improveSimpleJumpintoIf: ";
1174 showImproveSimpleJumpintoIf(headBlk, trueBlk, falseBlk, landBlk, 0);
1177 // org: headBlk => if () {trueBlk} else {falseBlk} => landBlk
1179 // new: headBlk => if () {initReg = 1; org trueBlk branch} else
1180 // {initReg = 0; org falseBlk branch }
1181 // => landBlk => if (initReg) {org trueBlk} else {org falseBlk}
1183 // if landBlk->pred_size() > 2, put the about if-else inside
1184 // if (initReg !=2) {...}
1186 // add initReg = initVal to headBlk
1188 const TargetRegisterClass * I32RC = TRI->getCFGStructurizerRegClass(MVT::i32);
1190 funcRep->getRegInfo().createVirtualRegister(I32RC);
1191 if (!migrateTrue || !migrateFalse) {
1192 int initVal = migrateTrue ? 0 : 1;
1193 CFGTraits::insertAssignInstrBefore(headBlk, passRep, initReg, initVal);
1198 if (landBlk == NULL) {
1199 landBlk = funcRep->CreateMachineBasicBlock();
1200 funcRep->push_back(landBlk); //insert to function
1203 trueBlk->addSuccessor(landBlk);
1205 headBlk->addSuccessor(landBlk);
1209 falseBlk->addSuccessor(landBlk);
1211 headBlk->addSuccessor(landBlk);
1217 bool landBlkHasOtherPred = (landBlk->pred_size() > 2);
1219 //insert AMDGPU::ENDIF to avoid special case "input landBlk == NULL"
1220 typename BlockT::iterator insertPos =
1221 CFGTraits::getInstrPos
1222 (landBlk, CFGTraits::insertInstrBefore(landBlk, AMDGPU::ENDIF, passRep));
1224 if (landBlkHasOtherPred) {
1226 funcRep->getRegInfo().createVirtualRegister(I32RC);
1227 CFGTraits::insertAssignInstrBefore(insertPos, passRep, immReg, 2);
1228 unsigned cmpResReg =
1229 funcRep->getRegInfo().createVirtualRegister(I32RC);
1231 CFGTraits::insertCompareInstrBefore(landBlk, insertPos, passRep, cmpResReg,
1233 CFGTraits::insertCondBranchBefore(landBlk, insertPos,
1234 AMDGPU::IF_PREDICATE_SET, passRep,
1235 cmpResReg, DebugLoc());
1238 CFGTraits::insertCondBranchBefore(landBlk, insertPos, AMDGPU::IF_PREDICATE_SET,
1239 passRep, initReg, DebugLoc());
1242 migrateInstruction(trueBlk, landBlk, insertPos);
1243 // need to uncondionally insert the assignment to ensure a path from its
1244 // predecessor rather than headBlk has valid value in initReg if
1246 CFGTraits::insertAssignInstrBefore(trueBlk, passRep, initReg, 1);
1248 CFGTraits::insertInstrBefore(insertPos, AMDGPU::ELSE, passRep);
1251 migrateInstruction(falseBlk, landBlk, insertPos);
1252 // need to uncondionally insert the assignment to ensure a path from its
1253 // predecessor rather than headBlk has valid value in initReg if
1255 CFGTraits::insertAssignInstrBefore(falseBlk, passRep, initReg, 0);
1258 if (landBlkHasOtherPred) {
1260 CFGTraits::insertInstrBefore(insertPos, AMDGPU::ENDIF, passRep);
1262 // put initReg = 2 to other predecessors of landBlk
1263 for (typename BlockT::pred_iterator predIter = landBlk->pred_begin(),
1264 predIterEnd = landBlk->pred_end(); predIter != predIterEnd;
1266 BlockT *curBlk = *predIter;
1267 if (curBlk != trueBlk && curBlk != falseBlk) {
1268 CFGTraits::insertAssignInstrBefore(curBlk, passRep, initReg, 2);
1273 errs() << "result from improveSimpleJumpintoIf: ";
1274 showImproveSimpleJumpintoIf(headBlk, trueBlk, falseBlk, landBlk, 0);
1278 *plandBlk = landBlk;
1281 } //improveSimpleJumpintoIf
1283 template<class PassT>
1284 void CFGStructurizer<PassT>::handleLoopbreak(BlockT *exitingBlk,
1290 errs() << "Trying to break loop-depth = " << getLoopDepth(exitLoop)
1291 << " from loop-depth = " << getLoopDepth(exitingLoop) << "\n";
1293 const TargetRegisterClass * I32RC = TRI->getCFGStructurizerRegClass(MVT::i32);
1295 RegiT initReg = INVALIDREGNUM;
1296 if (exitingLoop != exitLoop) {
1297 initReg = static_cast<int>
1298 (funcRep->getRegInfo().createVirtualRegister(I32RC));
1299 assert(initReg != INVALIDREGNUM);
1300 addLoopBreakInitReg(exitLoop, initReg);
1301 while (exitingLoop != exitLoop && exitingLoop) {
1302 addLoopBreakOnReg(exitingLoop, initReg);
1303 exitingLoop = exitingLoop->getParentLoop();
1305 assert(exitingLoop == exitLoop);
1308 mergeLoopbreakBlock(exitingBlk, exitBlk, landBlk, initReg);
1312 template<class PassT>
1313 void CFGStructurizer<PassT>::handleLoopcontBlock(BlockT *contingBlk,
1318 errs() << "loopcontPattern cont = BB" << contingBlk->getNumber()
1319 << " header = BB" << contBlk->getNumber() << "\n";
1321 errs() << "Trying to continue loop-depth = "
1322 << getLoopDepth(contLoop)
1323 << " from loop-depth = " << getLoopDepth(contingLoop) << "\n";
1326 RegiT initReg = INVALIDREGNUM;
1327 const TargetRegisterClass * I32RC = TRI->getCFGStructurizerRegClass(MVT::i32);
1328 if (contingLoop != contLoop) {
1329 initReg = static_cast<int>
1330 (funcRep->getRegInfo().createVirtualRegister(I32RC));
1331 assert(initReg != INVALIDREGNUM);
1332 addLoopContInitReg(contLoop, initReg);
1333 while (contingLoop && contingLoop->getParentLoop() != contLoop) {
1334 addLoopBreakOnReg(contingLoop, initReg); //not addLoopContOnReg
1335 contingLoop = contingLoop->getParentLoop();
1337 assert(contingLoop && contingLoop->getParentLoop() == contLoop);
1338 addLoopContOnReg(contingLoop, initReg);
1341 settleLoopcontBlock(contingBlk, contBlk, initReg);
1342 } //handleLoopcontBlock
1344 template<class PassT>
1345 void CFGStructurizer<PassT>::mergeSerialBlock(BlockT *dstBlk, BlockT *srcBlk) {
1347 errs() << "serialPattern BB" << dstBlk->getNumber()
1348 << " <= BB" << srcBlk->getNumber() << "\n";
1350 dstBlk->splice(dstBlk->end(), srcBlk, srcBlk->begin(), srcBlk->end());
1352 dstBlk->removeSuccessor(srcBlk);
1353 CFGTraits::cloneSuccessorList(dstBlk, srcBlk);
1355 removeSuccessor(srcBlk);
1356 retireBlock(dstBlk, srcBlk);
1357 } //mergeSerialBlock
1359 template<class PassT>
1360 void CFGStructurizer<PassT>::mergeIfthenelseBlock(InstrT *branchInstr,
1366 errs() << "ifPattern BB" << curBlk->getNumber();
1369 errs() << "BB" << trueBlk->getNumber();
1371 errs() << " } else ";
1374 errs() << "BB" << falseBlk->getNumber();
1377 errs() << "landBlock: ";
1378 if (landBlk == NULL) {
1381 errs() << "BB" << landBlk->getNumber();
1386 int oldOpcode = branchInstr->getOpcode();
1387 DebugLoc branchDL = branchInstr->getDebugLoc();
1397 typename BlockT::iterator branchInstrPos =
1398 CFGTraits::getInstrPos(curBlk, branchInstr);
1399 CFGTraits::insertCondBranchBefore(branchInstrPos,
1400 CFGTraits::getBranchNzeroOpcode(oldOpcode),
1405 curBlk->splice(branchInstrPos, trueBlk, trueBlk->begin(), trueBlk->end());
1406 curBlk->removeSuccessor(trueBlk);
1407 if (landBlk && trueBlk->succ_size()!=0) {
1408 trueBlk->removeSuccessor(landBlk);
1410 retireBlock(curBlk, trueBlk);
1412 CFGTraits::insertInstrBefore(branchInstrPos, AMDGPU::ELSE, passRep);
1415 curBlk->splice(branchInstrPos, falseBlk, falseBlk->begin(),
1417 curBlk->removeSuccessor(falseBlk);
1418 if (landBlk && falseBlk->succ_size() != 0) {
1419 falseBlk->removeSuccessor(landBlk);
1421 retireBlock(curBlk, falseBlk);
1423 CFGTraits::insertInstrBefore(branchInstrPos, AMDGPU::ENDIF, passRep);
1425 branchInstr->eraseFromParent();
1427 if (landBlk && trueBlk && falseBlk) {
1428 curBlk->addSuccessor(landBlk);
1431 } //mergeIfthenelseBlock
1433 template<class PassT>
1434 void CFGStructurizer<PassT>::mergeLooplandBlock(BlockT *dstBlk,
1435 LoopLandInfo *loopLand) {
1436 BlockT *landBlk = loopLand->landBlk;
1439 errs() << "loopPattern header = BB" << dstBlk->getNumber()
1440 << " land = BB" << landBlk->getNumber() << "\n";
1443 // Loop contInitRegs are init at the beginning of the loop.
1444 for (typename std::set<RegiT>::const_iterator iter =
1445 loopLand->contInitRegs.begin(),
1446 iterEnd = loopLand->contInitRegs.end(); iter != iterEnd; ++iter) {
1447 CFGTraits::insertAssignInstrBefore(dstBlk, passRep, *iter, 0);
1450 /* we last inserterd the DebugLoc in the
1451 * BREAK_LOGICALZ_i32 or AMDGPU::BREAK_LOGICALNZ statement in the current dstBlk.
1452 * search for the DebugLoc in the that statement.
1453 * if not found, we have to insert the empty/default DebugLoc */
1454 InstrT *loopBreakInstr = CFGTraits::getLoopBreakInstr(dstBlk);
1455 DebugLoc DLBreak = (loopBreakInstr) ? loopBreakInstr->getDebugLoc() : DebugLoc();
1457 CFGTraits::insertInstrBefore(dstBlk, AMDGPU::WHILELOOP, passRep, DLBreak);
1458 // Loop breakInitRegs are init before entering the loop.
1459 for (typename std::set<RegiT>::const_iterator iter =
1460 loopLand->breakInitRegs.begin(),
1461 iterEnd = loopLand->breakInitRegs.end(); iter != iterEnd; ++iter) {
1462 CFGTraits::insertAssignInstrBefore(dstBlk, passRep, *iter, 0);
1464 // Loop endbranchInitRegs are init before entering the loop.
1465 for (typename std::set<RegiT>::const_iterator iter =
1466 loopLand->endbranchInitRegs.begin(),
1467 iterEnd = loopLand->endbranchInitRegs.end(); iter != iterEnd; ++iter) {
1468 CFGTraits::insertAssignInstrBefore(dstBlk, passRep, *iter, 0);
1471 /* we last inserterd the DebugLoc in the continue statement in the current dstBlk
1472 * search for the DebugLoc in the continue statement.
1473 * if not found, we have to insert the empty/default DebugLoc */
1474 InstrT *continueInstr = CFGTraits::getContinueInstr(dstBlk);
1475 DebugLoc DLContinue = (continueInstr) ? continueInstr->getDebugLoc() : DebugLoc();
1477 CFGTraits::insertInstrEnd(dstBlk, AMDGPU::ENDLOOP, passRep, DLContinue);
1478 // Loop breakOnRegs are check after the ENDLOOP: break the loop outside this
1480 for (typename std::set<RegiT>::const_iterator iter =
1481 loopLand->breakOnRegs.begin(),
1482 iterEnd = loopLand->breakOnRegs.end(); iter != iterEnd; ++iter) {
1483 CFGTraits::insertCondBranchEnd(dstBlk, AMDGPU::PREDICATED_BREAK, passRep,
1487 // Loop contOnRegs are check after the ENDLOOP: cont the loop outside this
1489 for (std::set<RegiT>::const_iterator iter = loopLand->contOnRegs.begin(),
1490 iterEnd = loopLand->contOnRegs.end(); iter != iterEnd; ++iter) {
1491 CFGTraits::insertCondBranchEnd(dstBlk, AMDGPU::CONTINUE_LOGICALNZ_i32,
1495 dstBlk->splice(dstBlk->end(), landBlk, landBlk->begin(), landBlk->end());
1497 for (typename BlockT::succ_iterator iter = landBlk->succ_begin(),
1498 iterEnd = landBlk->succ_end(); iter != iterEnd; ++iter) {
1499 dstBlk->addSuccessor(*iter); // *iter's predecessor is also taken care of.
1502 removeSuccessor(landBlk);
1503 retireBlock(dstBlk, landBlk);
1504 } //mergeLooplandBlock
1506 template<class PassT>
1507 void CFGStructurizer<PassT>::reversePredicateSetter(typename BlockT::iterator I) {
1509 if (I->getOpcode() == AMDGPU::PRED_X) {
1510 switch (static_cast<MachineInstr *>(I)->getOperand(2).getImm()) {
1511 case OPCODE_IS_ZERO_INT:
1512 static_cast<MachineInstr *>(I)->getOperand(2).setImm(OPCODE_IS_NOT_ZERO_INT);
1514 case OPCODE_IS_NOT_ZERO_INT:
1515 static_cast<MachineInstr *>(I)->getOperand(2).setImm(OPCODE_IS_ZERO_INT);
1517 case OPCODE_IS_ZERO:
1518 static_cast<MachineInstr *>(I)->getOperand(2).setImm(OPCODE_IS_NOT_ZERO);
1520 case OPCODE_IS_NOT_ZERO:
1521 static_cast<MachineInstr *>(I)->getOperand(2).setImm(OPCODE_IS_ZERO);
1524 assert(0 && "PRED_X Opcode invalid!");
1530 template<class PassT>
1531 void CFGStructurizer<PassT>::mergeLoopbreakBlock(BlockT *exitingBlk,
1533 BlockT *exitLandBlk,
1536 errs() << "loopbreakPattern exiting = BB" << exitingBlk->getNumber()
1537 << " exit = BB" << exitBlk->getNumber()
1538 << " land = BB" << exitLandBlk->getNumber() << "\n";
1541 InstrT *branchInstr = CFGTraits::getLoopendBlockBranchInstr(exitingBlk);
1542 assert(branchInstr && CFGTraits::isCondBranch(branchInstr));
1544 DebugLoc DL = branchInstr->getDebugLoc();
1546 BlockT *trueBranch = CFGTraits::getTrueBranch(branchInstr);
1548 // transform exitingBlk to
1550 // exitBlk (if exitBlk != exitLandBlk)
1554 // successor = {orgSuccessor(exitingBlk) - exitBlk}
1556 typename BlockT::iterator branchInstrPos =
1557 CFGTraits::getInstrPos(exitingBlk, branchInstr);
1559 if (exitBlk == exitLandBlk && setReg == INVALIDREGNUM) {
1562 if (trueBranch != exitBlk) {
1563 reversePredicateSetter(branchInstrPos);
1565 CFGTraits::insertCondBranchBefore(branchInstrPos, AMDGPU::PREDICATED_BREAK, passRep, DL);
1567 if (trueBranch != exitBlk) {
1568 reversePredicateSetter(branchInstr);
1570 CFGTraits::insertCondBranchBefore(branchInstrPos, AMDGPU::PREDICATED_BREAK, passRep, DL);
1571 if (exitBlk != exitLandBlk) {
1572 //splice is insert-before ...
1573 exitingBlk->splice(branchInstrPos, exitBlk, exitBlk->begin(),
1576 if (setReg != INVALIDREGNUM) {
1577 CFGTraits::insertAssignInstrBefore(branchInstrPos, passRep, setReg, 1);
1579 CFGTraits::insertInstrBefore(branchInstrPos, AMDGPU::BREAK, passRep);
1582 //now branchInst can be erase safely
1583 branchInstr->eraseFromParent();
1585 //now take care of successors, retire blocks
1586 exitingBlk->removeSuccessor(exitBlk);
1587 if (exitBlk != exitLandBlk) {
1588 //splice is insert-before ...
1589 exitBlk->removeSuccessor(exitLandBlk);
1590 retireBlock(exitingBlk, exitBlk);
1593 } //mergeLoopbreakBlock
1595 template<class PassT>
1596 void CFGStructurizer<PassT>::settleLoopcontBlock(BlockT *contingBlk,
1600 errs() << "settleLoopcontBlock conting = BB"
1601 << contingBlk->getNumber()
1602 << ", cont = BB" << contBlk->getNumber() << "\n";
1605 InstrT *branchInstr = CFGTraits::getLoopendBlockBranchInstr(contingBlk);
1607 assert(CFGTraits::isCondBranch(branchInstr));
1608 typename BlockT::iterator branchInstrPos =
1609 CFGTraits::getInstrPos(contingBlk, branchInstr);
1610 BlockT *trueBranch = CFGTraits::getTrueBranch(branchInstr);
1611 int oldOpcode = branchInstr->getOpcode();
1612 DebugLoc DL = branchInstr->getDebugLoc();
1614 // transform contingBlk to
1616 // move instr after branchInstr
1622 // successor = {orgSuccessor(contingBlk) - loopHeader}
1624 bool useContinueLogical =
1625 (setReg == INVALIDREGNUM && (&*contingBlk->rbegin()) == branchInstr);
1627 if (useContinueLogical == false) {
1629 trueBranch == contBlk ? CFGTraits::getBranchNzeroOpcode(oldOpcode)
1630 : CFGTraits::getBranchZeroOpcode(oldOpcode);
1632 CFGTraits::insertCondBranchBefore(branchInstrPos, branchOpcode, passRep, DL);
1634 if (setReg != INVALIDREGNUM) {
1635 CFGTraits::insertAssignInstrBefore(branchInstrPos, passRep, setReg, 1);
1636 // insertEnd to ensure phi-moves, if exist, go before the continue-instr.
1637 CFGTraits::insertInstrEnd(contingBlk, AMDGPU::BREAK, passRep, DL);
1639 // insertEnd to ensure phi-moves, if exist, go before the continue-instr.
1640 CFGTraits::insertInstrEnd(contingBlk, AMDGPU::CONTINUE, passRep, DL);
1643 CFGTraits::insertInstrEnd(contingBlk, AMDGPU::ENDIF, passRep, DL);
1646 trueBranch == contBlk ? CFGTraits::getContinueNzeroOpcode(oldOpcode)
1647 : CFGTraits::getContinueZeroOpcode(oldOpcode);
1649 CFGTraits::insertCondBranchBefore(branchInstrPos, branchOpcode, passRep, DL);
1652 branchInstr->eraseFromParent();
1654 // if we've arrived here then we've already erased the branch instruction
1655 // travel back up the basic block to see the last reference of our debug location
1656 // we've just inserted that reference here so it should be representative
1657 if (setReg != INVALIDREGNUM) {
1658 CFGTraits::insertAssignInstrBefore(contingBlk, passRep, setReg, 1);
1659 // insertEnd to ensure phi-moves, if exist, go before the continue-instr.
1660 CFGTraits::insertInstrEnd(contingBlk, AMDGPU::BREAK, passRep, CFGTraits::getLastDebugLocInBB(contingBlk));
1662 // insertEnd to ensure phi-moves, if exist, go before the continue-instr.
1663 CFGTraits::insertInstrEnd(contingBlk, AMDGPU::CONTINUE, passRep, CFGTraits::getLastDebugLocInBB(contingBlk));
1667 } //settleLoopcontBlock
1669 // BBs in exitBlkSet are determined as in break-path for loopRep,
1670 // before we can put code for BBs as inside loop-body for loopRep
1671 // check whether those BBs are determined as cont-BB for parentLoopRep
1673 // If so, generate a new BB newBlk
1674 // (1) set newBlk common successor of BBs in exitBlkSet
1675 // (2) change the continue-instr in BBs in exitBlkSet to break-instr
1676 // (3) generate continue-instr in newBlk
1678 template<class PassT>
1679 typename CFGStructurizer<PassT>::BlockT *
1680 CFGStructurizer<PassT>::relocateLoopcontBlock(LoopT *parentLoopRep,
1682 std::set<BlockT *> &exitBlkSet,
1683 BlockT *exitLandBlk) {
1684 std::set<BlockT *> endBlkSet;
1688 for (typename std::set<BlockT *>::const_iterator iter = exitBlkSet.begin(),
1689 iterEnd = exitBlkSet.end();
1690 iter != iterEnd; ++iter) {
1691 BlockT *exitBlk = *iter;
1692 BlockT *endBlk = singlePathEnd(exitBlk, exitLandBlk);
1694 if (endBlk == NULL || CFGTraits::getContinueInstr(endBlk) == NULL)
1697 endBlkSet.insert(endBlk);
1700 BlockT *newBlk = funcRep->CreateMachineBasicBlock();
1701 funcRep->push_back(newBlk); //insert to function
1702 CFGTraits::insertInstrEnd(newBlk, AMDGPU::CONTINUE, passRep);
1703 SHOWNEWBLK(newBlk, "New continue block: ");
1705 for (typename std::set<BlockT*>::const_iterator iter = endBlkSet.begin(),
1706 iterEnd = endBlkSet.end();
1707 iter != iterEnd; ++iter) {
1708 BlockT *endBlk = *iter;
1709 InstrT *contInstr = CFGTraits::getContinueInstr(endBlk);
1711 contInstr->eraseFromParent();
1713 endBlk->addSuccessor(newBlk);
1715 errs() << "Add new continue Block to BB"
1716 << endBlk->getNumber() << " successors\n";
1721 } //relocateLoopcontBlock
1724 // LoopEndbranchBlock is a BB created by the CFGStructurizer to use as
1725 // LoopLandBlock. This BB branch on the loop endBranchInit register to the
1726 // pathes corresponding to the loop exiting branches.
1728 template<class PassT>
1729 typename CFGStructurizer<PassT>::BlockT *
1730 CFGStructurizer<PassT>::addLoopEndbranchBlock(LoopT *loopRep,
1731 BlockTSmallerVector &exitingBlks,
1732 BlockTSmallerVector &exitBlks) {
1733 const AMDGPUInstrInfo *tii =
1734 static_cast<const AMDGPUInstrInfo *>(passRep->getTargetInstrInfo());
1735 const TargetRegisterClass * I32RC = TRI->getCFGStructurizerRegClass(MVT::i32);
1737 RegiT endBranchReg = static_cast<int>
1738 (funcRep->getRegInfo().createVirtualRegister(I32RC));
1739 assert(endBranchReg >= 0);
1741 // reg = 0 before entering the loop
1742 addLoopEndbranchInitReg(loopRep, endBranchReg);
1744 uint32_t numBlks = static_cast<uint32_t>(exitingBlks.size());
1745 assert(numBlks >=2 && numBlks == exitBlks.size());
1747 BlockT *preExitingBlk = exitingBlks[0];
1748 BlockT *preExitBlk = exitBlks[0];
1749 BlockT *preBranchBlk = funcRep->CreateMachineBasicBlock();
1750 funcRep->push_back(preBranchBlk); //insert to function
1751 SHOWNEWBLK(preBranchBlk, "New loopEndbranch block: ");
1753 BlockT *newLandBlk = preBranchBlk;
1755 CFGTraits::replaceInstrUseOfBlockWith(preExitingBlk, preExitBlk,
1757 preExitingBlk->removeSuccessor(preExitBlk);
1758 preExitingBlk->addSuccessor(newLandBlk);
1760 //it is redundant to add reg = 0 to exitingBlks[0]
1762 // For 1..n th exiting path (the last iteration handles two pathes) create the
1763 // branch to the previous path and the current path.
1764 for (uint32_t i = 1; i < numBlks; ++i) {
1765 BlockT *curExitingBlk = exitingBlks[i];
1766 BlockT *curExitBlk = exitBlks[i];
1767 BlockT *curBranchBlk;
1769 if (i == numBlks - 1) {
1770 curBranchBlk = curExitBlk;
1772 curBranchBlk = funcRep->CreateMachineBasicBlock();
1773 funcRep->push_back(curBranchBlk); //insert to function
1774 SHOWNEWBLK(curBranchBlk, "New loopEndbranch block: ");
1777 // Add reg = i to exitingBlks[i].
1778 CFGTraits::insertAssignInstrBefore(curExitingBlk, passRep,
1781 // Remove the edge (exitingBlks[i] exitBlks[i]) add new edge
1782 // (exitingBlks[i], newLandBlk).
1783 CFGTraits::replaceInstrUseOfBlockWith(curExitingBlk, curExitBlk,
1785 curExitingBlk->removeSuccessor(curExitBlk);
1786 curExitingBlk->addSuccessor(newLandBlk);
1788 // add to preBranchBlk the branch instruction:
1789 // if (endBranchReg == preVal)
1794 // preValReg = i - 1
1797 RegiT preValReg = static_cast<int>
1798 (funcRep->getRegInfo().createVirtualRegister(I32RC));
1800 preBranchBlk->insert(preBranchBlk->begin(),
1801 tii->getMovImmInstr(preBranchBlk->getParent(), preValReg,
1804 // condResReg = (endBranchReg == preValReg)
1805 RegiT condResReg = static_cast<int>
1806 (funcRep->getRegInfo().createVirtualRegister(I32RC));
1807 BuildMI(preBranchBlk, DL, tii->get(tii->getIEQOpcode()), condResReg)
1808 .addReg(endBranchReg).addReg(preValReg);
1810 BuildMI(preBranchBlk, DL, tii->get(AMDGPU::BRANCH_COND_i32))
1811 .addMBB(preExitBlk).addReg(condResReg);
1813 preBranchBlk->addSuccessor(preExitBlk);
1814 preBranchBlk->addSuccessor(curBranchBlk);
1816 // Update preExitingBlk, preExitBlk, preBranchBlk.
1817 preExitingBlk = curExitingBlk;
1818 preExitBlk = curExitBlk;
1819 preBranchBlk = curBranchBlk;
1821 } //end for 1 .. n blocks
1824 } //addLoopEndbranchBlock
1826 template<class PassT>
1827 typename CFGStructurizer<PassT>::PathToKind
1828 CFGStructurizer<PassT>::singlePathTo(BlockT *srcBlk, BlockT *dstBlk,
1829 bool allowSideEntry) {
1832 if (srcBlk == dstBlk) {
1833 return SinglePath_InPath;
1836 while (srcBlk && srcBlk->succ_size() == 1) {
1837 srcBlk = *srcBlk->succ_begin();
1838 if (srcBlk == dstBlk) {
1839 return SinglePath_InPath;
1842 if (!allowSideEntry && srcBlk->pred_size() > 1) {
1843 return Not_SinglePath;
1847 if (srcBlk && srcBlk->succ_size()==0) {
1848 return SinglePath_NotInPath;
1851 return Not_SinglePath;
1854 // If there is a single path from srcBlk to dstBlk, return the last block before
1855 // dstBlk If there is a single path from srcBlk->end without dstBlk, return the
1856 // last block in the path Otherwise, return NULL
1857 template<class PassT>
1858 typename CFGStructurizer<PassT>::BlockT *
1859 CFGStructurizer<PassT>::singlePathEnd(BlockT *srcBlk, BlockT *dstBlk,
1860 bool allowSideEntry) {
1863 if (srcBlk == dstBlk) {
1867 if (srcBlk->succ_size() == 0) {
1871 while (srcBlk && srcBlk->succ_size() == 1) {
1872 BlockT *preBlk = srcBlk;
1874 srcBlk = *srcBlk->succ_begin();
1875 if (srcBlk == NULL) {
1879 if (!allowSideEntry && srcBlk->pred_size() > 1) {
1884 if (srcBlk && srcBlk->succ_size()==0) {
1892 template<class PassT>
1893 int CFGStructurizer<PassT>::cloneOnSideEntryTo(BlockT *preBlk, BlockT *srcBlk,
1896 assert(preBlk->isSuccessor(srcBlk));
1897 while (srcBlk && srcBlk != dstBlk) {
1898 assert(srcBlk->succ_size() == 1);
1899 if (srcBlk->pred_size() > 1) {
1900 srcBlk = cloneBlockForPredecessor(srcBlk, preBlk);
1905 srcBlk = *srcBlk->succ_begin();
1909 } //cloneOnSideEntryTo
1911 template<class PassT>
1912 typename CFGStructurizer<PassT>::BlockT *
1913 CFGStructurizer<PassT>::cloneBlockForPredecessor(BlockT *curBlk,
1915 assert(predBlk->isSuccessor(curBlk) &&
1916 "succBlk is not a prececessor of curBlk");
1918 BlockT *cloneBlk = CFGTraits::clone(curBlk); //clone instructions
1919 CFGTraits::replaceInstrUseOfBlockWith(predBlk, curBlk, cloneBlk);
1920 //srcBlk, oldBlk, newBlk
1922 predBlk->removeSuccessor(curBlk);
1923 predBlk->addSuccessor(cloneBlk);
1925 // add all successor to cloneBlk
1926 CFGTraits::cloneSuccessorList(cloneBlk, curBlk);
1928 numClonedInstr += curBlk->size();
1931 errs() << "Cloned block: " << "BB"
1932 << curBlk->getNumber() << "size " << curBlk->size() << "\n";
1935 SHOWNEWBLK(cloneBlk, "result of Cloned block: ");
1938 } //cloneBlockForPredecessor
1940 template<class PassT>
1941 typename CFGStructurizer<PassT>::BlockT *
1942 CFGStructurizer<PassT>::exitingBlock2ExitBlock(LoopT *loopRep,
1943 BlockT *exitingBlk) {
1944 BlockT *exitBlk = NULL;
1946 for (typename BlockT::succ_iterator iterSucc = exitingBlk->succ_begin(),
1947 iterSuccEnd = exitingBlk->succ_end();
1948 iterSucc != iterSuccEnd; ++iterSucc) {
1949 BlockT *curBlk = *iterSucc;
1950 if (!loopRep->contains(curBlk)) {
1951 assert(exitBlk == NULL);
1956 assert(exitBlk != NULL);
1959 } //exitingBlock2ExitBlock
1961 template<class PassT>
1962 void CFGStructurizer<PassT>::migrateInstruction(BlockT *srcBlk,
1964 InstrIterator insertPos) {
1965 InstrIterator spliceEnd;
1966 //look for the input branchinstr, not the AMDGPU branchinstr
1967 InstrT *branchInstr = CFGTraits::getNormalBlockBranchInstr(srcBlk);
1968 if (branchInstr == NULL) {
1970 errs() << "migrateInstruction don't see branch instr\n" ;
1972 spliceEnd = srcBlk->end();
1975 errs() << "migrateInstruction see branch instr\n" ;
1976 branchInstr->dump();
1978 spliceEnd = CFGTraits::getInstrPos(srcBlk, branchInstr);
1981 errs() << "migrateInstruction before splice dstSize = " << dstBlk->size()
1982 << "srcSize = " << srcBlk->size() << "\n";
1985 //splice insert before insertPos
1986 dstBlk->splice(insertPos, srcBlk, srcBlk->begin(), spliceEnd);
1989 errs() << "migrateInstruction after splice dstSize = " << dstBlk->size()
1990 << "srcSize = " << srcBlk->size() << "\n";
1992 } //migrateInstruction
1994 // normalizeInfiniteLoopExit change
1996 // uncond_br LoopHeader
2000 // cond_br 1 LoopHeader dummyExit
2001 // and return the newly added dummy exit block
2003 template<class PassT>
2004 typename CFGStructurizer<PassT>::BlockT *
2005 CFGStructurizer<PassT>::normalizeInfiniteLoopExit(LoopT* LoopRep) {
2008 loopHeader = LoopRep->getHeader();
2009 loopLatch = LoopRep->getLoopLatch();
2010 BlockT *dummyExitBlk = NULL;
2011 const TargetRegisterClass * I32RC = TRI->getCFGStructurizerRegClass(MVT::i32);
2012 if (loopHeader!=NULL && loopLatch!=NULL) {
2013 InstrT *branchInstr = CFGTraits::getLoopendBlockBranchInstr(loopLatch);
2014 if (branchInstr!=NULL && CFGTraits::isUncondBranch(branchInstr)) {
2015 dummyExitBlk = funcRep->CreateMachineBasicBlock();
2016 funcRep->push_back(dummyExitBlk); //insert to function
2017 SHOWNEWBLK(dummyExitBlk, "DummyExitBlock to normalize infiniteLoop: ");
2019 if (DEBUGME) errs() << "Old branch instr: " << *branchInstr << "\n";
2021 typename BlockT::iterator insertPos =
2022 CFGTraits::getInstrPos(loopLatch, branchInstr);
2024 funcRep->getRegInfo().createVirtualRegister(I32RC);
2025 CFGTraits::insertAssignInstrBefore(insertPos, passRep, immReg, 1);
2027 CFGTraits::insertInstrBefore(insertPos, AMDGPU::BRANCH_COND_i32, passRep);
2028 MachineInstrBuilder MIB(*funcRep, newInstr);
2029 MIB.addMBB(loopHeader);
2030 MIB.addReg(immReg, false);
2032 SHOWNEWINSTR(newInstr);
2034 branchInstr->eraseFromParent();
2035 loopLatch->addSuccessor(dummyExitBlk);
2039 return dummyExitBlk;
2040 } //normalizeInfiniteLoopExit
2042 template<class PassT>
2043 void CFGStructurizer<PassT>::removeUnconditionalBranch(BlockT *srcBlk) {
2044 InstrT *branchInstr;
2046 // I saw two unconditional branch in one basic block in example
2047 // test_fc_do_while_or.c need to fix the upstream on this to remove the loop.
2048 while ((branchInstr = CFGTraits::getLoopendBlockBranchInstr(srcBlk))
2049 && CFGTraits::isUncondBranch(branchInstr)) {
2051 errs() << "Removing unconditional branch instruction" ;
2052 branchInstr->dump();
2054 branchInstr->eraseFromParent();
2056 } //removeUnconditionalBranch
2058 template<class PassT>
2059 void CFGStructurizer<PassT>::removeRedundantConditionalBranch(BlockT *srcBlk) {
2060 if (srcBlk->succ_size() == 2) {
2061 BlockT *blk1 = *srcBlk->succ_begin();
2062 BlockT *blk2 = *(++srcBlk->succ_begin());
2065 InstrT *branchInstr = CFGTraits::getNormalBlockBranchInstr(srcBlk);
2066 assert(branchInstr && CFGTraits::isCondBranch(branchInstr));
2068 errs() << "Removing unneeded conditional branch instruction" ;
2069 branchInstr->dump();
2071 branchInstr->eraseFromParent();
2072 SHOWNEWBLK(blk1, "Removing redundant successor");
2073 srcBlk->removeSuccessor(blk1);
2076 } //removeRedundantConditionalBranch
2078 template<class PassT>
2079 void CFGStructurizer<PassT>::addDummyExitBlock(SmallVector<BlockT*,
2080 DEFAULT_VEC_SLOTS> &retBlks) {
2081 BlockT *dummyExitBlk = funcRep->CreateMachineBasicBlock();
2082 funcRep->push_back(dummyExitBlk); //insert to function
2083 CFGTraits::insertInstrEnd(dummyExitBlk, AMDGPU::RETURN, passRep);
2085 for (typename SmallVector<BlockT *, DEFAULT_VEC_SLOTS>::iterator iter =
2087 iterEnd = retBlks.end(); iter != iterEnd; ++iter) {
2088 BlockT *curBlk = *iter;
2089 InstrT *curInstr = CFGTraits::getReturnInstr(curBlk);
2091 curInstr->eraseFromParent();
2093 curBlk->addSuccessor(dummyExitBlk);
2095 errs() << "Add dummyExitBlock to BB" << curBlk->getNumber()
2100 SHOWNEWBLK(dummyExitBlk, "DummyExitBlock: ");
2101 } //addDummyExitBlock
2103 template<class PassT>
2104 void CFGStructurizer<PassT>::removeSuccessor(BlockT *srcBlk) {
2105 while (srcBlk->succ_size()) {
2106 srcBlk->removeSuccessor(*srcBlk->succ_begin());
2110 template<class PassT>
2111 void CFGStructurizer<PassT>::recordSccnum(BlockT *srcBlk, int sccNum) {
2112 BlockInfo *&srcBlkInfo = blockInfoMap[srcBlk];
2114 if (srcBlkInfo == NULL) {
2115 srcBlkInfo = new BlockInfo();
2118 srcBlkInfo->sccNum = sccNum;
2121 template<class PassT>
2122 int CFGStructurizer<PassT>::getSCCNum(BlockT *srcBlk) {
2123 BlockInfo *srcBlkInfo = blockInfoMap[srcBlk];
2124 return srcBlkInfo ? srcBlkInfo->sccNum : INVALIDSCCNUM;
2127 template<class PassT>
2128 void CFGStructurizer<PassT>::retireBlock(BlockT *dstBlk, BlockT *srcBlk) {
2130 errs() << "Retiring BB" << srcBlk->getNumber() << "\n";
2133 BlockInfo *&srcBlkInfo = blockInfoMap[srcBlk];
2135 if (srcBlkInfo == NULL) {
2136 srcBlkInfo = new BlockInfo();
2139 srcBlkInfo->isRetired = true;
2140 assert(srcBlk->succ_size() == 0 && srcBlk->pred_size() == 0
2141 && "can't retire block yet");
2144 template<class PassT>
2145 bool CFGStructurizer<PassT>::isRetiredBlock(BlockT *srcBlk) {
2146 BlockInfo *srcBlkInfo = blockInfoMap[srcBlk];
2147 return (srcBlkInfo && srcBlkInfo->isRetired);
2150 template<class PassT>
2151 bool CFGStructurizer<PassT>::isActiveLoophead(BlockT *curBlk) {
2152 LoopT *loopRep = loopInfo->getLoopFor(curBlk);
2153 while (loopRep && loopRep->getHeader() == curBlk) {
2154 LoopLandInfo *loopLand = getLoopLandInfo(loopRep);
2156 if(loopLand == NULL)
2159 BlockT *landBlk = loopLand->landBlk;
2161 if (!isRetiredBlock(landBlk)) {
2165 loopRep = loopRep->getParentLoop();
2169 } //isActiveLoophead
2171 template<class PassT>
2172 bool CFGStructurizer<PassT>::needMigrateBlock(BlockT *blk) {
2173 const unsigned blockSizeThreshold = 30;
2174 const unsigned cloneInstrThreshold = 100;
2176 bool multiplePreds = blk && (blk->pred_size() > 1);
2181 unsigned blkSize = blk->size();
2182 return ((blkSize > blockSizeThreshold)
2183 && (blkSize * (blk->pred_size() - 1) > cloneInstrThreshold));
2184 } //needMigrateBlock
2186 template<class PassT>
2187 typename CFGStructurizer<PassT>::BlockT *
2188 CFGStructurizer<PassT>::recordLoopLandBlock(LoopT *loopRep, BlockT *landBlk,
2189 BlockTSmallerVector &exitBlks,
2190 std::set<BlockT *> &exitBlkSet) {
2191 SmallVector<BlockT *, DEFAULT_VEC_SLOTS> inpathBlks; //in exit path blocks
2193 for (typename BlockT::pred_iterator predIter = landBlk->pred_begin(),
2194 predIterEnd = landBlk->pred_end();
2195 predIter != predIterEnd; ++predIter) {
2196 BlockT *curBlk = *predIter;
2197 if (loopRep->contains(curBlk) || exitBlkSet.count(curBlk)) {
2198 inpathBlks.push_back(curBlk);
2202 //if landBlk has predecessors that are not in the given loop,
2203 //create a new block
2204 BlockT *newLandBlk = landBlk;
2205 if (inpathBlks.size() != landBlk->pred_size()) {
2206 newLandBlk = funcRep->CreateMachineBasicBlock();
2207 funcRep->push_back(newLandBlk); //insert to function
2208 newLandBlk->addSuccessor(landBlk);
2209 for (typename SmallVector<BlockT*, DEFAULT_VEC_SLOTS>::iterator iter =
2211 iterEnd = inpathBlks.end(); iter != iterEnd; ++iter) {
2212 BlockT *curBlk = *iter;
2213 CFGTraits::replaceInstrUseOfBlockWith(curBlk, landBlk, newLandBlk);
2214 //srcBlk, oldBlk, newBlk
2215 curBlk->removeSuccessor(landBlk);
2216 curBlk->addSuccessor(newLandBlk);
2218 for (size_t i = 0, tot = exitBlks.size(); i < tot; ++i) {
2219 if (exitBlks[i] == landBlk) {
2220 exitBlks[i] = newLandBlk;
2223 SHOWNEWBLK(newLandBlk, "NewLandingBlock: ");
2226 setLoopLandBlock(loopRep, newLandBlk);
2229 } // recordLoopbreakLand
2231 template<class PassT>
2232 void CFGStructurizer<PassT>::setLoopLandBlock(LoopT *loopRep, BlockT *blk) {
2233 LoopLandInfo *&theEntry = loopLandInfoMap[loopRep];
2235 if (theEntry == NULL) {
2236 theEntry = new LoopLandInfo();
2238 assert(theEntry->landBlk == NULL);
2241 blk = funcRep->CreateMachineBasicBlock();
2242 funcRep->push_back(blk); //insert to function
2243 SHOWNEWBLK(blk, "DummyLandingBlock for loop without break: ");
2246 theEntry->landBlk = blk;
2249 errs() << "setLoopLandBlock loop-header = BB"
2250 << loopRep->getHeader()->getNumber()
2251 << " landing-block = BB" << blk->getNumber() << "\n";
2253 } // setLoopLandBlock
2255 template<class PassT>
2256 void CFGStructurizer<PassT>::addLoopBreakOnReg(LoopT *loopRep, RegiT regNum) {
2257 LoopLandInfo *&theEntry = loopLandInfoMap[loopRep];
2259 if (theEntry == NULL) {
2260 theEntry = new LoopLandInfo();
2263 theEntry->breakOnRegs.insert(regNum);
2266 errs() << "addLoopBreakOnReg loop-header = BB"
2267 << loopRep->getHeader()->getNumber()
2268 << " regNum = " << regNum << "\n";
2270 } // addLoopBreakOnReg
2272 template<class PassT>
2273 void CFGStructurizer<PassT>::addLoopContOnReg(LoopT *loopRep, RegiT regNum) {
2274 LoopLandInfo *&theEntry = loopLandInfoMap[loopRep];
2276 if (theEntry == NULL) {
2277 theEntry = new LoopLandInfo();
2279 theEntry->contOnRegs.insert(regNum);
2282 errs() << "addLoopContOnReg loop-header = BB"
2283 << loopRep->getHeader()->getNumber()
2284 << " regNum = " << regNum << "\n";
2286 } // addLoopContOnReg
2288 template<class PassT>
2289 void CFGStructurizer<PassT>::addLoopBreakInitReg(LoopT *loopRep, RegiT regNum) {
2290 LoopLandInfo *&theEntry = loopLandInfoMap[loopRep];
2292 if (theEntry == NULL) {
2293 theEntry = new LoopLandInfo();
2295 theEntry->breakInitRegs.insert(regNum);
2298 errs() << "addLoopBreakInitReg loop-header = BB"
2299 << loopRep->getHeader()->getNumber()
2300 << " regNum = " << regNum << "\n";
2302 } // addLoopBreakInitReg
2304 template<class PassT>
2305 void CFGStructurizer<PassT>::addLoopContInitReg(LoopT *loopRep, RegiT regNum) {
2306 LoopLandInfo *&theEntry = loopLandInfoMap[loopRep];
2308 if (theEntry == NULL) {
2309 theEntry = new LoopLandInfo();
2311 theEntry->contInitRegs.insert(regNum);
2314 errs() << "addLoopContInitReg loop-header = BB"
2315 << loopRep->getHeader()->getNumber()
2316 << " regNum = " << regNum << "\n";
2318 } // addLoopContInitReg
2320 template<class PassT>
2321 void CFGStructurizer<PassT>::addLoopEndbranchInitReg(LoopT *loopRep,
2323 LoopLandInfo *&theEntry = loopLandInfoMap[loopRep];
2325 if (theEntry == NULL) {
2326 theEntry = new LoopLandInfo();
2328 theEntry->endbranchInitRegs.insert(regNum);
2331 errs() << "addLoopEndbranchInitReg loop-header = BB"
2332 << loopRep->getHeader()->getNumber()
2333 << " regNum = " << regNum << "\n";
2335 } // addLoopEndbranchInitReg
2337 template<class PassT>
2338 typename CFGStructurizer<PassT>::LoopLandInfo *
2339 CFGStructurizer<PassT>::getLoopLandInfo(LoopT *loopRep) {
2340 LoopLandInfo *&theEntry = loopLandInfoMap[loopRep];
2343 } // getLoopLandInfo
2345 template<class PassT>
2346 typename CFGStructurizer<PassT>::BlockT *
2347 CFGStructurizer<PassT>::getLoopLandBlock(LoopT *loopRep) {
2348 LoopLandInfo *&theEntry = loopLandInfoMap[loopRep];
2350 return theEntry ? theEntry->landBlk : NULL;
2351 } // getLoopLandBlock
2354 template<class PassT>
2355 bool CFGStructurizer<PassT>::hasBackEdge(BlockT *curBlk) {
2356 LoopT *loopRep = loopInfo->getLoopFor(curBlk);
2357 if (loopRep == NULL)
2360 BlockT *loopHeader = loopRep->getHeader();
2362 return curBlk->isSuccessor(loopHeader);
2366 template<class PassT>
2367 unsigned CFGStructurizer<PassT>::getLoopDepth(LoopT *loopRep) {
2368 return loopRep ? loopRep->getLoopDepth() : 0;
2371 template<class PassT>
2372 int CFGStructurizer<PassT>::countActiveBlock
2373 (typename SmallVector<BlockT*, DEFAULT_VEC_SLOTS>::const_iterator iterStart,
2374 typename SmallVector<BlockT*, DEFAULT_VEC_SLOTS>::const_iterator iterEnd) {
2376 while (iterStart != iterEnd) {
2377 if (!isRetiredBlock(*iterStart)) {
2384 } //countActiveBlock
2386 // This is work around solution for findNearestCommonDominator not avaiable to
2387 // post dom a proper fix should go to Dominators.h.
2389 template<class PassT>
2390 typename CFGStructurizer<PassT>::BlockT*
2391 CFGStructurizer<PassT>::findNearestCommonPostDom(BlockT *blk1, BlockT *blk2) {
2393 if (postDomTree->dominates(blk1, blk2)) {
2396 if (postDomTree->dominates(blk2, blk1)) {
2400 DomTreeNodeT *node1 = postDomTree->getNode(blk1);
2401 DomTreeNodeT *node2 = postDomTree->getNode(blk2);
2403 // Handle newly cloned node.
2404 if (node1 == NULL && blk1->succ_size() == 1) {
2405 return findNearestCommonPostDom(*blk1->succ_begin(), blk2);
2407 if (node2 == NULL && blk2->succ_size() == 1) {
2408 return findNearestCommonPostDom(blk1, *blk2->succ_begin());
2411 if (node1 == NULL || node2 == NULL) {
2415 node1 = node1->getIDom();
2417 if (postDomTree->dominates(node1, node2)) {
2418 return node1->getBlock();
2420 node1 = node1->getIDom();
2426 template<class PassT>
2427 typename CFGStructurizer<PassT>::BlockT *
2428 CFGStructurizer<PassT>::findNearestCommonPostDom
2429 (typename std::set<BlockT *> &blks) {
2431 typename std::set<BlockT *>::const_iterator iter = blks.begin();
2432 typename std::set<BlockT *>::const_iterator iterEnd = blks.end();
2433 for (commonDom = *iter; iter != iterEnd && commonDom != NULL; ++iter) {
2434 BlockT *curBlk = *iter;
2435 if (curBlk != commonDom) {
2436 commonDom = findNearestCommonPostDom(curBlk, commonDom);
2441 errs() << "Common post dominator for exit blocks is ";
2443 errs() << "BB" << commonDom->getNumber() << "\n";
2450 } //findNearestCommonPostDom
2452 } // end anonymous namespace
2457 //===----------------------------------------------------------------------===//
2459 // CFGStructurizer for AMDGPU
2461 //===----------------------------------------------------------------------===//
2465 class AMDGPUCFGStructurizer : public MachineFunctionPass {
2467 typedef MachineInstr InstructionType;
2468 typedef MachineFunction FunctionType;
2469 typedef MachineBasicBlock BlockType;
2470 typedef MachineLoopInfo LoopinfoType;
2471 typedef MachineDominatorTree DominatortreeType;
2472 typedef MachinePostDominatorTree PostDominatortreeType;
2473 typedef MachineDomTreeNode DomTreeNodeType;
2474 typedef MachineLoop LoopType;
2480 AMDGPUCFGStructurizer(char &pid, TargetMachine &tm);
2481 const TargetInstrInfo *getTargetInstrInfo() const;
2482 const AMDGPURegisterInfo *getTargetRegisterInfo() const;
2485 } // end anonymous namespace
2486 AMDGPUCFGStructurizer::AMDGPUCFGStructurizer(char &pid, TargetMachine &tm)
2487 : MachineFunctionPass(pid), TM(tm) {
2490 const TargetInstrInfo *AMDGPUCFGStructurizer::getTargetInstrInfo() const {
2491 return TM.getInstrInfo();
2494 const AMDGPURegisterInfo *AMDGPUCFGStructurizer::getTargetRegisterInfo() const {
2495 return static_cast<const AMDGPURegisterInfo *>(TM.getRegisterInfo());
2498 //===----------------------------------------------------------------------===//
2502 //===----------------------------------------------------------------------===//
2506 class AMDGPUCFGPrepare : public AMDGPUCFGStructurizer {
2511 AMDGPUCFGPrepare(TargetMachine &tm);
2513 virtual const char *getPassName() const;
2514 virtual void getAnalysisUsage(AnalysisUsage &AU) const;
2516 bool runOnMachineFunction(MachineFunction &F);
2519 char AMDGPUCFGPrepare::ID = 0;
2520 } // end anonymous namespace
2522 AMDGPUCFGPrepare::AMDGPUCFGPrepare(TargetMachine &tm)
2523 : AMDGPUCFGStructurizer(ID, tm ) {
2525 const char *AMDGPUCFGPrepare::getPassName() const {
2526 return "AMD IL Control Flow Graph Preparation Pass";
2529 void AMDGPUCFGPrepare::getAnalysisUsage(AnalysisUsage &AU) const {
2530 AU.addPreserved<MachineFunctionAnalysis>();
2531 AU.addRequired<MachineFunctionAnalysis>();
2532 AU.addRequired<MachineDominatorTree>();
2533 AU.addRequired<MachinePostDominatorTree>();
2534 AU.addRequired<MachineLoopInfo>();
2537 //===----------------------------------------------------------------------===//
2541 //===----------------------------------------------------------------------===//
2545 class AMDGPUCFGPerform : public AMDGPUCFGStructurizer {
2550 AMDGPUCFGPerform(TargetMachine &tm);
2551 virtual const char *getPassName() const;
2552 virtual void getAnalysisUsage(AnalysisUsage &AU) const;
2553 bool runOnMachineFunction(MachineFunction &F);
2556 char AMDGPUCFGPerform::ID = 0;
2557 } // end anonymous namespace
2559 AMDGPUCFGPerform::AMDGPUCFGPerform(TargetMachine &tm)
2560 : AMDGPUCFGStructurizer(ID, tm) {
2563 const char *AMDGPUCFGPerform::getPassName() const {
2564 return "AMD IL Control Flow Graph structurizer Pass";
2567 void AMDGPUCFGPerform::getAnalysisUsage(AnalysisUsage &AU) const {
2568 AU.addPreserved<MachineFunctionAnalysis>();
2569 AU.addRequired<MachineFunctionAnalysis>();
2570 AU.addRequired<MachineDominatorTree>();
2571 AU.addRequired<MachinePostDominatorTree>();
2572 AU.addRequired<MachineLoopInfo>();
2575 //===----------------------------------------------------------------------===//
2577 // CFGStructTraits<AMDGPUCFGStructurizer>
2579 //===----------------------------------------------------------------------===//
2582 // this class is tailor to the AMDGPU backend
2584 struct CFGStructTraits<AMDGPUCFGStructurizer> {
2587 static int getBranchNzeroOpcode(int oldOpcode) {
2589 case AMDGPU::JUMP_COND:
2590 case AMDGPU::JUMP: return AMDGPU::IF_PREDICATE_SET;
2591 case AMDGPU::BRANCH_COND_i32:
2592 case AMDGPU::BRANCH_COND_f32: return AMDGPU::IF_LOGICALNZ_f32;
2594 assert(0 && "internal error");
2599 static int getBranchZeroOpcode(int oldOpcode) {
2601 case AMDGPU::JUMP_COND:
2602 case AMDGPU::JUMP: return AMDGPU::IF_PREDICATE_SET;
2603 case AMDGPU::BRANCH_COND_i32:
2604 case AMDGPU::BRANCH_COND_f32: return AMDGPU::IF_LOGICALZ_f32;
2606 assert(0 && "internal error");
2611 static int getContinueNzeroOpcode(int oldOpcode) {
2613 case AMDGPU::JUMP_COND:
2614 case AMDGPU::JUMP: return AMDGPU::CONTINUE_LOGICALNZ_i32;
2616 assert(0 && "internal error");
2621 static int getContinueZeroOpcode(int oldOpcode) {
2623 case AMDGPU::JUMP_COND:
2624 case AMDGPU::JUMP: return AMDGPU::CONTINUE_LOGICALZ_i32;
2626 assert(0 && "internal error");
2631 static MachineBasicBlock *getTrueBranch(MachineInstr *instr) {
2632 return instr->getOperand(0).getMBB();
2635 static void setTrueBranch(MachineInstr *instr, MachineBasicBlock *blk) {
2636 instr->getOperand(0).setMBB(blk);
2639 static MachineBasicBlock *
2640 getFalseBranch(MachineBasicBlock *blk, MachineInstr *instr) {
2641 assert(blk->succ_size() == 2);
2642 MachineBasicBlock *trueBranch = getTrueBranch(instr);
2643 MachineBasicBlock::succ_iterator iter = blk->succ_begin();
2644 MachineBasicBlock::succ_iterator iterNext = iter;
2647 return (*iter == trueBranch) ? *iterNext : *iter;
2650 static bool isCondBranch(MachineInstr *instr) {
2651 switch (instr->getOpcode()) {
2652 case AMDGPU::JUMP_COND:
2653 case AMDGPU::BRANCH_COND_i32:
2654 case AMDGPU::BRANCH_COND_f32:
2662 static bool isUncondBranch(MachineInstr *instr) {
2663 switch (instr->getOpcode()) {
2665 case AMDGPU::BRANCH:
2673 static DebugLoc getLastDebugLocInBB(MachineBasicBlock *blk) {
2674 //get DebugLoc from the first MachineBasicBlock instruction with debug info
2676 for (MachineBasicBlock::iterator iter = blk->begin(); iter != blk->end(); ++iter) {
2677 MachineInstr *instr = &(*iter);
2678 if (instr->getDebugLoc().isUnknown() == false) {
2679 DL = instr->getDebugLoc();
2685 static MachineInstr *getNormalBlockBranchInstr(MachineBasicBlock *blk) {
2686 MachineBasicBlock::reverse_iterator iter = blk->rbegin();
2687 MachineInstr *instr = &*iter;
2688 if (instr && (isCondBranch(instr) || isUncondBranch(instr))) {
2694 // The correct naming for this is getPossibleLoopendBlockBranchInstr.
2696 // BB with backward-edge could have move instructions after the branch
2697 // instruction. Such move instruction "belong to" the loop backward-edge.
2699 static MachineInstr *getLoopendBlockBranchInstr(MachineBasicBlock *blk) {
2700 const AMDGPUInstrInfo * TII = static_cast<const AMDGPUInstrInfo *>(
2701 blk->getParent()->getTarget().getInstrInfo());
2703 for (MachineBasicBlock::reverse_iterator iter = blk->rbegin(),
2704 iterEnd = blk->rend(); iter != iterEnd; ++iter) {
2706 MachineInstr *instr = &*iter;
2708 if (isCondBranch(instr) || isUncondBranch(instr)) {
2710 } else if (!TII->isMov(instr->getOpcode())) {
2718 static MachineInstr *getReturnInstr(MachineBasicBlock *blk) {
2719 MachineBasicBlock::reverse_iterator iter = blk->rbegin();
2720 if (iter != blk->rend()) {
2721 MachineInstr *instr = &(*iter);
2722 if (instr->getOpcode() == AMDGPU::RETURN) {
2729 static MachineInstr *getContinueInstr(MachineBasicBlock *blk) {
2730 MachineBasicBlock::reverse_iterator iter = blk->rbegin();
2731 if (iter != blk->rend()) {
2732 MachineInstr *instr = &(*iter);
2733 if (instr->getOpcode() == AMDGPU::CONTINUE) {
2740 static MachineInstr *getLoopBreakInstr(MachineBasicBlock *blk) {
2741 for (MachineBasicBlock::iterator iter = blk->begin(); (iter != blk->end()); ++iter) {
2742 MachineInstr *instr = &(*iter);
2743 if (instr->getOpcode() == AMDGPU::PREDICATED_BREAK) {
2750 static bool isReturnBlock(MachineBasicBlock *blk) {
2751 MachineInstr *instr = getReturnInstr(blk);
2752 bool isReturn = (blk->succ_size() == 0);
2755 } else if (isReturn) {
2757 errs() << "BB" << blk->getNumber()
2758 <<" is return block without RETURN instr\n";
2765 static MachineBasicBlock::iterator
2766 getInstrPos(MachineBasicBlock *blk, MachineInstr *instr) {
2767 assert(instr->getParent() == blk && "instruction doesn't belong to block");
2768 MachineBasicBlock::iterator iter = blk->begin();
2769 MachineBasicBlock::iterator iterEnd = blk->end();
2770 while (&(*iter) != instr && iter != iterEnd) {
2774 assert(iter != iterEnd);
2778 static MachineInstr *insertInstrBefore(MachineBasicBlock *blk, int newOpcode,
2779 AMDGPUCFGStructurizer *passRep) {
2780 return insertInstrBefore(blk,newOpcode,passRep,DebugLoc());
2781 } //insertInstrBefore
2783 static MachineInstr *insertInstrBefore(MachineBasicBlock *blk, int newOpcode,
2784 AMDGPUCFGStructurizer *passRep, DebugLoc DL) {
2785 const TargetInstrInfo *tii = passRep->getTargetInstrInfo();
2786 MachineInstr *newInstr =
2787 blk->getParent()->CreateMachineInstr(tii->get(newOpcode), DL);
2789 MachineBasicBlock::iterator res;
2790 if (blk->begin() != blk->end()) {
2791 blk->insert(blk->begin(), newInstr);
2793 blk->push_back(newInstr);
2796 SHOWNEWINSTR(newInstr);
2799 } //insertInstrBefore
2801 static void insertInstrEnd(MachineBasicBlock *blk, int newOpcode,
2802 AMDGPUCFGStructurizer *passRep) {
2803 insertInstrEnd(blk,newOpcode,passRep,DebugLoc());
2806 static void insertInstrEnd(MachineBasicBlock *blk, int newOpcode,
2807 AMDGPUCFGStructurizer *passRep, DebugLoc DL) {
2808 const TargetInstrInfo *tii = passRep->getTargetInstrInfo();
2809 MachineInstr *newInstr = blk->getParent()
2810 ->CreateMachineInstr(tii->get(newOpcode), DL);
2812 blk->push_back(newInstr);
2813 //assume the instruction doesn't take any reg operand ...
2815 SHOWNEWINSTR(newInstr);
2818 static MachineInstr *insertInstrBefore(MachineBasicBlock::iterator instrPos,
2820 AMDGPUCFGStructurizer *passRep) {
2821 MachineInstr *oldInstr = &(*instrPos);
2822 const TargetInstrInfo *tii = passRep->getTargetInstrInfo();
2823 MachineBasicBlock *blk = oldInstr->getParent();
2824 MachineInstr *newInstr =
2825 blk->getParent()->CreateMachineInstr(tii->get(newOpcode),
2828 blk->insert(instrPos, newInstr);
2829 //assume the instruction doesn't take any reg operand ...
2831 SHOWNEWINSTR(newInstr);
2833 } //insertInstrBefore
2835 static void insertCondBranchBefore(MachineBasicBlock::iterator instrPos,
2837 AMDGPUCFGStructurizer *passRep,
2839 MachineInstr *oldInstr = &(*instrPos);
2840 const TargetInstrInfo *tii = passRep->getTargetInstrInfo();
2841 MachineBasicBlock *blk = oldInstr->getParent();
2842 MachineFunction *MF = blk->getParent();
2843 MachineInstr *newInstr = MF->CreateMachineInstr(tii->get(newOpcode), DL);
2845 blk->insert(instrPos, newInstr);
2846 MachineInstrBuilder MIB(*MF, newInstr);
2847 MIB.addReg(oldInstr->getOperand(1).getReg(), false);
2849 SHOWNEWINSTR(newInstr);
2850 //erase later oldInstr->eraseFromParent();
2851 } //insertCondBranchBefore
2853 static void insertCondBranchBefore(MachineBasicBlock *blk,
2854 MachineBasicBlock::iterator insertPos,
2856 AMDGPUCFGStructurizer *passRep,
2859 const TargetInstrInfo *tii = passRep->getTargetInstrInfo();
2860 MachineFunction *MF = blk->getParent();
2862 MachineInstr *newInstr = MF->CreateMachineInstr(tii->get(newOpcode), DL);
2865 blk->insert(insertPos, newInstr);
2866 MachineInstrBuilder(*MF, newInstr).addReg(regNum, false);
2868 SHOWNEWINSTR(newInstr);
2869 } //insertCondBranchBefore
2871 static void insertCondBranchEnd(MachineBasicBlock *blk,
2873 AMDGPUCFGStructurizer *passRep,
2875 const TargetInstrInfo *tii = passRep->getTargetInstrInfo();
2876 MachineFunction *MF = blk->getParent();
2877 MachineInstr *newInstr =
2878 MF->CreateMachineInstr(tii->get(newOpcode), DebugLoc());
2880 blk->push_back(newInstr);
2881 MachineInstrBuilder(*MF, newInstr).addReg(regNum, false);
2883 SHOWNEWINSTR(newInstr);
2884 } //insertCondBranchEnd
2887 static void insertAssignInstrBefore(MachineBasicBlock::iterator instrPos,
2888 AMDGPUCFGStructurizer *passRep,
2889 RegiT regNum, int regVal) {
2890 MachineInstr *oldInstr = &(*instrPos);
2891 const AMDGPUInstrInfo *tii =
2892 static_cast<const AMDGPUInstrInfo *>(passRep->getTargetInstrInfo());
2893 MachineBasicBlock *blk = oldInstr->getParent();
2894 MachineInstr *newInstr = tii->getMovImmInstr(blk->getParent(), regNum,
2896 blk->insert(instrPos, newInstr);
2898 SHOWNEWINSTR(newInstr);
2899 } //insertAssignInstrBefore
2901 static void insertAssignInstrBefore(MachineBasicBlock *blk,
2902 AMDGPUCFGStructurizer *passRep,
2903 RegiT regNum, int regVal) {
2904 const AMDGPUInstrInfo *tii =
2905 static_cast<const AMDGPUInstrInfo *>(passRep->getTargetInstrInfo());
2907 MachineInstr *newInstr = tii->getMovImmInstr(blk->getParent(), regNum,
2909 if (blk->begin() != blk->end()) {
2910 blk->insert(blk->begin(), newInstr);
2912 blk->push_back(newInstr);
2915 SHOWNEWINSTR(newInstr);
2917 } //insertInstrBefore
2919 static void insertCompareInstrBefore(MachineBasicBlock *blk,
2920 MachineBasicBlock::iterator instrPos,
2921 AMDGPUCFGStructurizer *passRep,
2922 RegiT dstReg, RegiT src1Reg,
2924 const AMDGPUInstrInfo *tii =
2925 static_cast<const AMDGPUInstrInfo *>(passRep->getTargetInstrInfo());
2926 MachineFunction *MF = blk->getParent();
2927 MachineInstr *newInstr =
2928 MF->CreateMachineInstr(tii->get(tii->getIEQOpcode()), DebugLoc());
2930 MachineInstrBuilder MIB(*MF, newInstr);
2931 MIB.addReg(dstReg, RegState::Define); //set target
2932 MIB.addReg(src1Reg); //set src value
2933 MIB.addReg(src2Reg); //set src value
2935 blk->insert(instrPos, newInstr);
2936 SHOWNEWINSTR(newInstr);
2938 } //insertCompareInstrBefore
2940 static void cloneSuccessorList(MachineBasicBlock *dstBlk,
2941 MachineBasicBlock *srcBlk) {
2942 for (MachineBasicBlock::succ_iterator iter = srcBlk->succ_begin(),
2943 iterEnd = srcBlk->succ_end(); iter != iterEnd; ++iter) {
2944 dstBlk->addSuccessor(*iter); // *iter's predecessor is also taken care of
2946 } //cloneSuccessorList
2948 static MachineBasicBlock *clone(MachineBasicBlock *srcBlk) {
2949 MachineFunction *func = srcBlk->getParent();
2950 MachineBasicBlock *newBlk = func->CreateMachineBasicBlock();
2951 func->push_back(newBlk); //insert to function
2952 for (MachineBasicBlock::iterator iter = srcBlk->begin(),
2953 iterEnd = srcBlk->end();
2954 iter != iterEnd; ++iter) {
2955 MachineInstr *instr = func->CloneMachineInstr(iter);
2956 newBlk->push_back(instr);
2961 //MachineBasicBlock::ReplaceUsesOfBlockWith doesn't serve the purpose because
2962 //the AMDGPU instruction is not recognized as terminator fix this and retire
2964 static void replaceInstrUseOfBlockWith(MachineBasicBlock *srcBlk,
2965 MachineBasicBlock *oldBlk,
2966 MachineBasicBlock *newBlk) {
2967 MachineInstr *branchInstr = getLoopendBlockBranchInstr(srcBlk);
2968 if (branchInstr && isCondBranch(branchInstr) &&
2969 getTrueBranch(branchInstr) == oldBlk) {
2970 setTrueBranch(branchInstr, newBlk);
2974 static void wrapup(MachineBasicBlock *entryBlk) {
2975 assert((!entryBlk->getParent()->getJumpTableInfo()
2976 || entryBlk->getParent()->getJumpTableInfo()->isEmpty())
2977 && "found a jump table");
2979 //collect continue right before endloop
2980 SmallVector<MachineInstr *, DEFAULT_VEC_SLOTS> contInstr;
2981 MachineBasicBlock::iterator pre = entryBlk->begin();
2982 MachineBasicBlock::iterator iterEnd = entryBlk->end();
2983 MachineBasicBlock::iterator iter = pre;
2984 while (iter != iterEnd) {
2985 if (pre->getOpcode() == AMDGPU::CONTINUE
2986 && iter->getOpcode() == AMDGPU::ENDLOOP) {
2987 contInstr.push_back(pre);
2993 //delete continue right before endloop
2994 for (unsigned i = 0; i < contInstr.size(); ++i) {
2995 contInstr[i]->eraseFromParent();
2998 // TODO to fix up jump table so later phase won't be confused. if
2999 // (jumpTableInfo->isEmpty() == false) { need to clean the jump table, but
3000 // there isn't such an interface yet. alternatively, replace all the other
3001 // blocks in the jump table with the entryBlk //}
3005 static MachineDominatorTree *getDominatorTree(AMDGPUCFGStructurizer &pass) {
3006 return &pass.getAnalysis<MachineDominatorTree>();
3009 static MachinePostDominatorTree*
3010 getPostDominatorTree(AMDGPUCFGStructurizer &pass) {
3011 return &pass.getAnalysis<MachinePostDominatorTree>();
3014 static MachineLoopInfo *getLoopInfo(AMDGPUCFGStructurizer &pass) {
3015 return &pass.getAnalysis<MachineLoopInfo>();
3017 }; // template class CFGStructTraits
3018 } // end anonymous namespace
3020 // createAMDGPUCFGPreparationPass- Returns a pass
3021 FunctionPass *llvm::createAMDGPUCFGPreparationPass(TargetMachine &tm) {
3022 return new AMDGPUCFGPrepare(tm);
3025 bool AMDGPUCFGPrepare::runOnMachineFunction(MachineFunction &func) {
3026 return CFGStructurizer<AMDGPUCFGStructurizer>().prepare(func, *this,
3027 getTargetRegisterInfo());
3030 // createAMDGPUCFGStructurizerPass- Returns a pass
3031 FunctionPass *llvm::createAMDGPUCFGStructurizerPass(TargetMachine &tm) {
3032 return new AMDGPUCFGPerform(tm);
3035 bool AMDGPUCFGPerform::runOnMachineFunction(MachineFunction &func) {
3036 return CFGStructurizer<AMDGPUCFGStructurizer>().run(func, *this,
3037 getTargetRegisterInfo());