blob: 85ac72542a47247de20e4ce6c5600910983b69b1 [file] [log] [blame]
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001//===-- AMDILCFGStructurizer.cpp - CFG Structurizer -----------------------===//
2//
3// The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8/// \file
9//==-----------------------------------------------------------------------===//
10
Tom Stellardf98f2ce2012-12-11 21:25:42 +000011#define DEBUG_TYPE "structcfg"
12
Tom Stellard3ff0abf2013-06-07 20:37:48 +000013#include "AMDGPU.h"
Tom Stellardf98f2ce2012-12-11 21:25:42 +000014#include "AMDGPUInstrInfo.h"
Vincent Lejeune12140452013-07-19 21:45:06 +000015#include "R600InstrInfo.h"
Vincent Lejeune9e8ba2b2013-07-19 21:44:56 +000016#include "llvm/Support/Debug.h"
17#include "llvm/Support/raw_ostream.h"
Tom Stellardf98f2ce2012-12-11 21:25:42 +000018#include "llvm/ADT/SCCIterator.h"
19#include "llvm/ADT/SmallVector.h"
20#include "llvm/ADT/Statistic.h"
Vincent Lejeune12140452013-07-19 21:45:06 +000021#include "llvm/ADT/DepthFirstIterator.h"
Tom Stellardf98f2ce2012-12-11 21:25:42 +000022#include "llvm/Analysis/DominatorInternals.h"
23#include "llvm/Analysis/Dominators.h"
Tom Stellardf98f2ce2012-12-11 21:25:42 +000024#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"
Chandler Carruth58a2cbe2013-01-02 10:22:59 +000031#include "llvm/CodeGen/MachinePostDominators.h"
Tom Stellardf98f2ce2012-12-11 21:25:42 +000032#include "llvm/CodeGen/MachineRegisterInfo.h"
33#include "llvm/Target/TargetInstrInfo.h"
Tom Stellard3ff0abf2013-06-07 20:37:48 +000034#include "llvm/Target/TargetMachine.h"
Tom Stellardf98f2ce2012-12-11 21:25:42 +000035
36using namespace llvm;
37
Tom Stellard3ff0abf2013-06-07 20:37:48 +000038#define DEFAULT_VEC_SLOTS 8
39
Tom Stellardf98f2ce2012-12-11 21:25:42 +000040// TODO: move-begin.
41
42//===----------------------------------------------------------------------===//
43//
44// Statistics for CFGStructurizer.
45//
46//===----------------------------------------------------------------------===//
47
48STATISTIC(numSerialPatternMatch, "CFGStructurizer number of serial pattern "
49 "matched");
50STATISTIC(numIfPatternMatch, "CFGStructurizer number of if pattern "
51 "matched");
Tom Stellardf98f2ce2012-12-11 21:25:42 +000052STATISTIC(numLoopcontPatternMatch, "CFGStructurizer number of loop-continue "
53 "pattern matched");
Tom Stellardf98f2ce2012-12-11 21:25:42 +000054STATISTIC(numClonedBlock, "CFGStructurizer cloned blocks");
55STATISTIC(numClonedInstr, "CFGStructurizer cloned instructions");
56
57//===----------------------------------------------------------------------===//
58//
59// Miscellaneous utility for CFGStructurizer.
60//
61//===----------------------------------------------------------------------===//
Benjamin Kramer879b0712013-05-23 15:43:05 +000062namespace {
Tom Stellardf98f2ce2012-12-11 21:25:42 +000063#define SHOWNEWINSTR(i) \
Vincent Lejeune9e8ba2b2013-07-19 21:44:56 +000064 DEBUG(dbgs() << "New instr: " << *i << "\n");
Tom Stellardf98f2ce2012-12-11 21:25:42 +000065
66#define SHOWNEWBLK(b, msg) \
Vincent Lejeune9e8ba2b2013-07-19 21:44:56 +000067DEBUG( \
68 dbgs() << msg << "BB" << b->getNumber() << "size " << b->size(); \
69 dbgs() << "\n"; \
70);
Tom Stellardf98f2ce2012-12-11 21:25:42 +000071
72#define SHOWBLK_DETAIL(b, msg) \
Vincent Lejeune9e8ba2b2013-07-19 21:44:56 +000073DEBUG( \
Tom Stellardf98f2ce2012-12-11 21:25:42 +000074 if (b) { \
Vincent Lejeune9e8ba2b2013-07-19 21:44:56 +000075 dbgs() << msg << "BB" << b->getNumber() << "size " << b->size(); \
76 b->print(dbgs()); \
77 dbgs() << "\n"; \
Tom Stellardf98f2ce2012-12-11 21:25:42 +000078 } \
Vincent Lejeune9e8ba2b2013-07-19 21:44:56 +000079);
Tom Stellardf98f2ce2012-12-11 21:25:42 +000080
81#define INVALIDSCCNUM -1
Tom Stellardf98f2ce2012-12-11 21:25:42 +000082
83template<class NodeT>
Craig Toppera0ec3f92013-07-14 04:42:23 +000084void ReverseVector(SmallVectorImpl<NodeT *> &Src) {
Tom Stellardf98f2ce2012-12-11 21:25:42 +000085 size_t sz = Src.size();
86 for (size_t i = 0; i < sz/2; ++i) {
87 NodeT *t = Src[i];
88 Src[i] = Src[sz - i - 1];
89 Src[sz - i - 1] = t;
90 }
91}
92
Benjamin Kramer879b0712013-05-23 15:43:05 +000093} // end anonymous namespace
Tom Stellardf98f2ce2012-12-11 21:25:42 +000094
95//===----------------------------------------------------------------------===//
96//
97// supporting data structure for CFGStructurizer
98//
99//===----------------------------------------------------------------------===//
100
Tom Stellardf98f2ce2012-12-11 21:25:42 +0000101
Vincent Lejeune12140452013-07-19 21:45:06 +0000102namespace {
103
Tom Stellardf98f2ce2012-12-11 21:25:42 +0000104class BlockInformation {
105public:
Vincent Lejeune12140452013-07-19 21:45:06 +0000106 bool IsRetired;
107 int SccNum;
108 BlockInformation() : IsRetired(false), SccNum(INVALIDSCCNUM) {}
Tom Stellardf98f2ce2012-12-11 21:25:42 +0000109};
110
Benjamin Kramer879b0712013-05-23 15:43:05 +0000111} // end anonymous namespace
Tom Stellardf98f2ce2012-12-11 21:25:42 +0000112
113//===----------------------------------------------------------------------===//
114//
115// CFGStructurizer
116//
117//===----------------------------------------------------------------------===//
118
Benjamin Kramer879b0712013-05-23 15:43:05 +0000119namespace {
Vincent Lejeune12140452013-07-19 21:45:06 +0000120class AMDGPUCFGStructurizer : public MachineFunctionPass {
Tom Stellardf98f2ce2012-12-11 21:25:42 +0000121public:
Vincent Lejeune12140452013-07-19 21:45:06 +0000122 typedef SmallVector<MachineBasicBlock *, 32> MBBVector;
123 typedef std::map<MachineBasicBlock *, BlockInformation *> MBBInfoMap;
124 typedef std::map<MachineLoop *, MachineBasicBlock *> LoopLandInfoMap;
125
126 enum PathToKind {
Tom Stellardf98f2ce2012-12-11 21:25:42 +0000127 Not_SinglePath = 0,
128 SinglePath_InPath = 1,
129 SinglePath_NotInPath = 2
Vincent Lejeune12140452013-07-19 21:45:06 +0000130 };
Tom Stellardf98f2ce2012-12-11 21:25:42 +0000131
Vincent Lejeune12140452013-07-19 21:45:06 +0000132 static char ID;
Tom Stellardf98f2ce2012-12-11 21:25:42 +0000133
Vincent Lejeune12140452013-07-19 21:45:06 +0000134 AMDGPUCFGStructurizer(TargetMachine &tm) :
135 MachineFunctionPass(ID), TM(tm),
136 TII(static_cast<const R600InstrInfo *>(tm.getInstrInfo())),
137 TRI(&TII->getRegisterInfo()) { }
Tom Stellardf98f2ce2012-12-11 21:25:42 +0000138
Vincent Lejeune12140452013-07-19 21:45:06 +0000139 const char *getPassName() const {
140 return "AMD IL Control Flow Graph structurizer Pass";
141 }
Tom Stellardf98f2ce2012-12-11 21:25:42 +0000142
Vincent Lejeune12140452013-07-19 21:45:06 +0000143 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>();
149 }
Tom Stellardf98f2ce2012-12-11 21:25:42 +0000150
151 /// Perform the CFG structurization
Vincent Lejeune12140452013-07-19 21:45:06 +0000152 bool run();
Tom Stellardf98f2ce2012-12-11 21:25:42 +0000153
154 /// Perform the CFG preparation
Vincent Lejeune12140452013-07-19 21:45:06 +0000155 /// This step will remove every unconditionnal/dead jump instructions and make
156 /// sure all loops have an exit block
157 bool prepare();
Tom Stellardf98f2ce2012-12-11 21:25:42 +0000158
Vincent Lejeune12140452013-07-19 21:45:06 +0000159 bool runOnMachineFunction(MachineFunction &MF) {
160 DEBUG(MF.dump(););
161 OrderedBlks.clear();
162 FuncRep = &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()););
169 prepare();
170 run();
171 DEBUG(MF.dump(););
172 return true;
173 }
Tom Stellardf98f2ce2012-12-11 21:25:42 +0000174
Vincent Lejeune12140452013-07-19 21:45:06 +0000175protected:
176 TargetMachine &TM;
177 MachineDominatorTree *MDT;
178 MachinePostDominatorTree *PDT;
179 MachineLoopInfo *MLI;
180 const R600InstrInfo *TII;
Tom Stellardf98f2ce2012-12-11 21:25:42 +0000181 const AMDGPURegisterInfo *TRI;
182
Vincent Lejeune12140452013-07-19 21:45:06 +0000183 // PRINT FUNCTIONS
184 /// Print the ordered Blocks.
185 void printOrderedBlocks() const {
186 size_t i = 0;
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) {
192 dbgs() << "\n";
193 } else {
194 dbgs() << " ";
195 }
196 }
197 }
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);
202 }
203 }
Tom Stellardf98f2ce2012-12-11 21:25:42 +0000204
Vincent Lejeune12140452013-07-19 21:45:06 +0000205 // UTILITY FUNCTIONS
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;
217
218 // Utility Functions
219 void reversePredicateSetter(MachineBasicBlock::iterator I);
220 /// Compute the reversed DFS post order of Blocks
221 void orderBlocks(MachineFunction *MF);
222
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,
230 DebugLoc DL);
231 void insertCondBranchBefore(MachineBasicBlock *MBB,
232 MachineBasicBlock::iterator I, int NewOpcode, int RegNum,
233 DebugLoc DL);
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,
242 MachineInstr *MI);
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.
248 ///
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);
265
266
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);
274
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);
297
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
308 /// B1:
309 /// uncond_br LoopHeader
310 ///
311 /// to
312 /// B1:
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.
318 /// For instance
319 /// B0:
320 /// cond_br X B1 B2
321 /// cond_br X B1 B2
322 /// is transformed to
323 /// B0:
324 /// cond_br X B1 B2
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);
335
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);
341
342private:
343 MBBInfoMap BlockInfoMap;
344 LoopLandInfoMap LLInfoMap;
345 std::map<MachineLoop *, bool> Visited;
346 MachineFunction *FuncRep;
347 SmallVector<MachineBasicBlock *, DEFAULT_VEC_SLOTS> OrderedBlks;
348};
349
350int 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;
Tom Stellardf98f2ce2012-12-11 21:25:42 +0000355}
356
Vincent Lejeune12140452013-07-19 21:45:06 +0000357MachineBasicBlock *AMDGPUCFGStructurizer::getLoopLandInfo(MachineLoop *LoopRep)
358 const {
359 LoopLandInfoMap::const_iterator It = LLInfoMap.find(LoopRep);
360 if (It == LLInfoMap.end())
361 return NULL;
362 return (*It).second;
363}
364
365bool AMDGPUCFGStructurizer::hasBackEdge(MachineBasicBlock *MBB) const {
366 MachineLoop *LoopRep = MLI->getLoopFor(MBB);
367 if (!LoopRep)
368 return false;
369 MachineBasicBlock *LoopHeader = LoopRep->getHeader();
370 return MBB->isSuccessor(LoopHeader);
371}
372
373unsigned AMDGPUCFGStructurizer::getLoopDepth(MachineLoop *LoopRep) {
374 return LoopRep ? LoopRep->getLoopDepth() : 0;
375}
376
377bool AMDGPUCFGStructurizer::isRetiredBlock(MachineBasicBlock *MBB) const {
378 MBBInfoMap::const_iterator It = BlockInfoMap.find(MBB);
379 if (It == BlockInfoMap.end())
380 return false;
381 return (*It).second->IsRetired;
382}
383
384bool AMDGPUCFGStructurizer::isActiveLoophead(MachineBasicBlock *MBB) const {
385 MachineLoop *LoopRep = MLI->getLoopFor(MBB);
386 while (LoopRep && LoopRep->getHeader() == MBB) {
387 MachineBasicBlock *LoopLand = getLoopLandInfo(LoopRep);
388 if(!LoopLand)
389 return true;
390 if (!isRetiredBlock(LoopLand))
391 return true;
392 LoopRep = LoopRep->getParentLoop();
393 }
394 return false;
395}
396AMDGPUCFGStructurizer::PathToKind AMDGPUCFGStructurizer::singlePathTo(
397 MachineBasicBlock *SrcMBB, MachineBasicBlock *DstMBB,
398 bool AllowSideEntry) const {
399 assert(DstMBB);
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;
408 }
409 if (SrcMBB && SrcMBB->succ_size()==0)
410 return SinglePath_NotInPath;
411 return Not_SinglePath;
412}
413
414int AMDGPUCFGStructurizer::countActiveBlock(MBBVector::const_iterator It,
415 MBBVector::const_iterator E) const {
416 int Count = 0;
417 while (It != E) {
418 if (!isRetiredBlock(*It))
419 ++Count;
420 ++It;
421 }
422 return Count;
423}
424
425bool AMDGPUCFGStructurizer::needMigrateBlock(MachineBasicBlock *MBB) const {
426 unsigned BlockSizeThreshold = 30;
427 unsigned CloneInstrThreshold = 100;
428 bool MultiplePreds = MBB && (MBB->pred_size() > 1);
429
430 if(!MultiplePreds)
431 return false;
432 unsigned BlkSize = MBB->size();
433 return ((BlkSize > BlockSizeThreshold) &&
434 (BlkSize * (MBB->pred_size() - 1) > CloneInstrThreshold));
435}
436
437void AMDGPUCFGStructurizer::reversePredicateSetter(
438 MachineBasicBlock::iterator I) {
439 while (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);
445 return;
446 case OPCODE_IS_NOT_ZERO_INT:
447 static_cast<MachineInstr *>(I)->getOperand(2)
448 .setImm(OPCODE_IS_ZERO_INT);
449 return;
450 case OPCODE_IS_ZERO:
451 static_cast<MachineInstr *>(I)->getOperand(2)
452 .setImm(OPCODE_IS_NOT_ZERO);
453 return;
454 case OPCODE_IS_NOT_ZERO:
455 static_cast<MachineInstr *>(I)->getOperand(2)
456 .setImm(OPCODE_IS_ZERO);
457 return;
458 default:
459 llvm_unreachable("PRED_X Opcode invalid!");
460 }
461 }
Tom Stellardf98f2ce2012-12-11 21:25:42 +0000462 }
463}
464
Vincent Lejeune12140452013-07-19 21:45:06 +0000465void AMDGPUCFGStructurizer::insertInstrEnd(MachineBasicBlock *MBB,
466 int NewOpcode, DebugLoc DL) {
467 MachineInstr *MI = MBB->getParent()
468 ->CreateMachineInstr(TII->get(NewOpcode), DL);
469 MBB->push_back(MI);
470 //assume the instruction doesn't take any reg operand ...
471 SHOWNEWINSTR(MI);
472}
Tom Stellardf98f2ce2012-12-11 21:25:42 +0000473
Vincent Lejeune12140452013-07-19 21:45:06 +0000474MachineInstr *AMDGPUCFGStructurizer::insertInstrBefore(MachineBasicBlock *MBB,
475 int NewOpcode, DebugLoc DL) {
476 MachineInstr *MI =
477 MBB->getParent()->CreateMachineInstr(TII->get(NewOpcode), DL);
478 if (MBB->begin() != MBB->end())
479 MBB->insert(MBB->begin(), MI);
480 else
481 MBB->push_back(MI);
482 SHOWNEWINSTR(MI);
483 return MI;
484}
485
486MachineInstr *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);
495 return NewMBB;
496}
497
498void 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);
507 SHOWNEWINSTR(NewMI);
508 //erase later oldInstr->eraseFromParent();
509}
510
511void AMDGPUCFGStructurizer::insertCondBranchBefore(MachineBasicBlock *blk,
512 MachineBasicBlock::iterator I, int NewOpcode, int RegNum,
513 DebugLoc DL) {
514 MachineFunction *MF = blk->getParent();
515 MachineInstr *NewInstr = MF->CreateMachineInstr(TII->get(NewOpcode), DL);
516 //insert before
517 blk->insert(I, NewInstr);
518 MachineInstrBuilder(*MF, NewInstr).addReg(RegNum, false);
519 SHOWNEWINSTR(NewInstr);
520}
521
522void 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);
530}
531
532int AMDGPUCFGStructurizer::getBranchNzeroOpcode(int OldOpcode) {
533 switch(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");
539 }
540 return -1;
541}
542
543int AMDGPUCFGStructurizer::getBranchZeroOpcode(int OldOpcode) {
544 switch(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");
550 }
551 return -1;
552}
553
554int AMDGPUCFGStructurizer::getContinueNzeroOpcode(int OldOpcode) {
555 switch(OldOpcode) {
556 case AMDGPU::JUMP_COND:
557 case AMDGPU::JUMP: return AMDGPU::CONTINUE_LOGICALNZ_i32;
558 default: llvm_unreachable("internal error");
559 };
560 return -1;
561}
562
563int AMDGPUCFGStructurizer::getContinueZeroOpcode(int OldOpcode) {
564 switch(OldOpcode) {
565 case AMDGPU::JUMP_COND:
566 case AMDGPU::JUMP: return AMDGPU::CONTINUE_LOGICALZ_i32;
567 default: llvm_unreachable("internal error");
568 }
569 return -1;
570}
571
572MachineBasicBlock *AMDGPUCFGStructurizer::getTrueBranch(MachineInstr *MI) {
573 return MI->getOperand(0).getMBB();
574}
575
576void AMDGPUCFGStructurizer::setTrueBranch(MachineInstr *MI,
577 MachineBasicBlock *MBB) {
578 MI->getOperand(0).setMBB(MBB);
579}
580
581MachineBasicBlock *
582AMDGPUCFGStructurizer::getFalseBranch(MachineBasicBlock *MBB,
583 MachineInstr *MI) {
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;
588 ++Next;
589 return (*It == TrueBranch) ? *Next : *It;
590}
591
592bool 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;
597 default:
598 return false;
599 }
600 return false;
601}
602
603bool AMDGPUCFGStructurizer::isUncondBranch(MachineInstr *MI) {
604 switch (MI->getOpcode()) {
605 case AMDGPU::JUMP:
606 case AMDGPU::BRANCH:
607 return true;
608 default:
609 return false;
610 }
611 return false;
612}
613
614DebugLoc AMDGPUCFGStructurizer::getLastDebugLocInBB(MachineBasicBlock *MBB) {
615 //get DebugLoc from the first MachineBasicBlock instruction with debug info
616 DebugLoc DL;
617 for (MachineBasicBlock::iterator It = MBB->begin(); It != MBB->end();
618 ++It) {
619 MachineInstr *instr = &(*It);
620 if (instr->getDebugLoc().isUnknown() == false)
621 DL = instr->getDebugLoc();
622 }
623 return DL;
624}
625
626MachineInstr *AMDGPUCFGStructurizer::getNormalBlockBranchInstr(
627 MachineBasicBlock *MBB) {
628 MachineBasicBlock::reverse_iterator It = MBB->rbegin();
629 MachineInstr *MI = &*It;
630 if (MI && (isCondBranch(MI) || isUncondBranch(MI)))
631 return MI;
632 return NULL;
633}
634
635MachineInstr *AMDGPUCFGStructurizer::getLoopendBlockBranchInstr(
636 MachineBasicBlock *MBB) {
637 for (MachineBasicBlock::reverse_iterator It = MBB->rbegin(), E = MBB->rend();
638 It != E; ++It) {
639 // FIXME: Simplify
640 MachineInstr *MI = &*It;
641 if (MI) {
642 if (isCondBranch(MI) || isUncondBranch(MI))
643 return MI;
644 else if (!TII->isMov(MI->getOpcode()))
645 break;
646 }
647 }
648 return NULL;
649}
650
651MachineInstr *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)
656 return instr;
657 }
658 return NULL;
659}
660
661MachineInstr *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)
666 return MI;
667 }
668 return NULL;
669}
670
671MachineInstr *AMDGPUCFGStructurizer::getLoopBreakInstr(MachineBasicBlock *MBB) {
672 for (MachineBasicBlock::iterator It = MBB->begin(); (It != MBB->end());
673 ++It) {
674 MachineInstr *MI = &(*It);
675 if (MI->getOpcode() == AMDGPU::PREDICATED_BREAK)
676 return MI;
677 }
678 return NULL;
679}
680
681bool AMDGPUCFGStructurizer::isReturnBlock(MachineBasicBlock *MBB) {
682 MachineInstr *MI = getReturnInstr(MBB);
683 bool IsReturn = (MBB->succ_size() == 0);
684 if (MI)
685 assert(IsReturn);
686 else if (IsReturn)
687 DEBUG(
688 dbgs() << "BB" << MBB->getNumber()
689 <<" is return block without RETURN instr\n";);
690 return IsReturn;
691}
692
693void 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
698}
699
700MachineBasicBlock *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();
705 It != E; ++It) {
706 MachineInstr *MI = Func->CloneMachineInstr(It);
707 NewMBB->push_back(MI);
708 }
709 return NewMBB;
710}
711
712void 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);
719}
720
721void AMDGPUCFGStructurizer::wrapup(MachineBasicBlock *MBB) {
722 assert((!MBB->getParent()->getJumpTableInfo()
723 || MBB->getParent()->getJumpTableInfo()->isEmpty())
724 && "found a jump table");
725
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;
731 while (It != E) {
732 if (Pre->getOpcode() == AMDGPU::CONTINUE
733 && It->getOpcode() == AMDGPU::ENDLOOP)
734 ContInstr.push_back(Pre);
735 Pre = It;
736 ++It;
737 }
738
739 //delete continue right before endloop
740 for (unsigned i = 0; i < ContInstr.size(); ++i)
741 ContInstr[i]->eraseFromParent();
742
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 //}
747
748}
749
750
751bool AMDGPUCFGStructurizer::prepare() {
752 bool Changed = false;
Tom Stellardf98f2ce2012-12-11 21:25:42 +0000753
754 //FIXME: if not reducible flow graph, make it so ???
755
Vincent Lejeune12140452013-07-19 21:45:06 +0000756 DEBUG(dbgs() << "AMDGPUCFGStructurizer::prepare\n";);
Tom Stellardf98f2ce2012-12-11 21:25:42 +0000757
Vincent Lejeune12140452013-07-19 21:45:06 +0000758 orderBlocks(FuncRep);
Tom Stellardf98f2ce2012-12-11 21:25:42 +0000759
Vincent Lejeune12140452013-07-19 21:45:06 +0000760 SmallVector<MachineBasicBlock *, DEFAULT_VEC_SLOTS> RetBlks;
Tom Stellardf98f2ce2012-12-11 21:25:42 +0000761
Vincent Lejeune12140452013-07-19 21:45:06 +0000762 // 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);
Tom Stellardf98f2ce2012-12-11 21:25:42 +0000768
Vincent Lejeune12140452013-07-19 21:45:06 +0000769 if (ExitingMBBs.size() == 0) {
770 MachineBasicBlock* DummyExitBlk = normalizeInfiniteLoopExit(LoopRep);
771 if (DummyExitBlk)
772 RetBlks.push_back(DummyExitBlk);
Tom Stellardf98f2ce2012-12-11 21:25:42 +0000773 }
774 }
775
776 // Remove unconditional branch instr.
777 // Add dummy exit block iff there are multiple returns.
Vincent Lejeune12140452013-07-19 21:45:06 +0000778 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);
Tom Stellardf98f2ce2012-12-11 21:25:42 +0000785 }
Vincent Lejeune12140452013-07-19 21:45:06 +0000786 assert(MBB->succ_size() <= 2);
Tom Stellardf98f2ce2012-12-11 21:25:42 +0000787 }
788
Vincent Lejeune12140452013-07-19 21:45:06 +0000789 if (RetBlks.size() >= 2) {
790 addDummyExitBlock(RetBlks);
791 Changed = true;
792 }
Tom Stellardf98f2ce2012-12-11 21:25:42 +0000793
Vincent Lejeune12140452013-07-19 21:45:06 +0000794 return Changed;
795}
796
797bool AMDGPUCFGStructurizer::run() {
Tom Stellardf98f2ce2012-12-11 21:25:42 +0000798
799 //Assume reducible CFG...
Vincent Lejeune12140452013-07-19 21:45:06 +0000800 DEBUG(dbgs() << "AMDGPUCFGStructurizer::run\n";FuncRep->viewCFG(););
Tom Stellardf98f2ce2012-12-11 21:25:42 +0000801
Tom Stellardf98f2ce2012-12-11 21:25:42 +0000802#ifdef STRESSTEST
803 //Use the worse block ordering to test the algorithm.
804 ReverseVector(orderedBlks);
805#endif
806
Vincent Lejeune12140452013-07-19 21:45:06 +0000807 DEBUG(dbgs() << "Ordered blocks:\n"; printOrderedBlocks(););
808 int NumIter = 0;
809 bool Finish = false;
810 MachineBasicBlock *MBB;
811 bool MakeProgress = false;
812 int NumRemainedBlk = countActiveBlock(OrderedBlks.begin(),
813 OrderedBlks.end());
Tom Stellardf98f2ce2012-12-11 21:25:42 +0000814
815 do {
Vincent Lejeune12140452013-07-19 21:45:06 +0000816 ++NumIter;
Vincent Lejeune9e8ba2b2013-07-19 21:44:56 +0000817 DEBUG(
Vincent Lejeune12140452013-07-19 21:45:06 +0000818 dbgs() << "numIter = " << NumIter
819 << ", numRemaintedBlk = " << NumRemainedBlk << "\n";
Vincent Lejeune9e8ba2b2013-07-19 21:44:56 +0000820 );
Tom Stellardf98f2ce2012-12-11 21:25:42 +0000821
Vincent Lejeune12140452013-07-19 21:45:06 +0000822 SmallVectorImpl<MachineBasicBlock *>::const_iterator It =
823 OrderedBlks.begin();
824 SmallVectorImpl<MachineBasicBlock *>::const_iterator E =
825 OrderedBlks.end();
Tom Stellardf98f2ce2012-12-11 21:25:42 +0000826
Vincent Lejeune12140452013-07-19 21:45:06 +0000827 SmallVectorImpl<MachineBasicBlock *>::const_iterator SccBeginIter =
828 It;
829 MachineBasicBlock *SccBeginMBB = NULL;
830 int SccNumBlk = 0; // The number of active blocks, init to a
Tom Stellardf98f2ce2012-12-11 21:25:42 +0000831 // maximum possible number.
Vincent Lejeune12140452013-07-19 21:45:06 +0000832 int SccNumIter; // Number of iteration in this SCC.
Tom Stellardf98f2ce2012-12-11 21:25:42 +0000833
Vincent Lejeune12140452013-07-19 21:45:06 +0000834 while (It != E) {
835 MBB = *It;
Tom Stellardf98f2ce2012-12-11 21:25:42 +0000836
Vincent Lejeune12140452013-07-19 21:45:06 +0000837 if (!SccBeginMBB) {
838 SccBeginIter = It;
839 SccBeginMBB = MBB;
840 SccNumIter = 0;
841 SccNumBlk = NumRemainedBlk; // Init to maximum possible number.
Vincent Lejeune9e8ba2b2013-07-19 21:44:56 +0000842 DEBUG(
Vincent Lejeune12140452013-07-19 21:45:06 +0000843 dbgs() << "start processing SCC" << getSCCNum(SccBeginMBB);
Vincent Lejeune9e8ba2b2013-07-19 21:44:56 +0000844 dbgs() << "\n";
845 );
Tom Stellardf98f2ce2012-12-11 21:25:42 +0000846 }
847
Vincent Lejeune12140452013-07-19 21:45:06 +0000848 if (!isRetiredBlock(MBB))
849 patternMatch(MBB);
Tom Stellardf98f2ce2012-12-11 21:25:42 +0000850
Vincent Lejeune12140452013-07-19 21:45:06 +0000851 ++It;
Tom Stellardf98f2ce2012-12-11 21:25:42 +0000852
Vincent Lejeune12140452013-07-19 21:45:06 +0000853 bool ContNextScc = true;
854 if (It == E
855 || getSCCNum(SccBeginMBB) != getSCCNum(*It)) {
Tom Stellardf98f2ce2012-12-11 21:25:42 +0000856 // Just finish one scc.
Vincent Lejeune12140452013-07-19 21:45:06 +0000857 ++SccNumIter;
858 int sccRemainedNumBlk = countActiveBlock(SccBeginIter, It);
859 if (sccRemainedNumBlk != 1 && sccRemainedNumBlk >= SccNumBlk) {
Vincent Lejeune9e8ba2b2013-07-19 21:44:56 +0000860 DEBUG(
Vincent Lejeune12140452013-07-19 21:45:06 +0000861 dbgs() << "Can't reduce SCC " << getSCCNum(MBB)
862 << ", sccNumIter = " << SccNumIter;
Vincent Lejeune9e8ba2b2013-07-19 21:44:56 +0000863 dbgs() << "doesn't make any progress\n";
864 );
Vincent Lejeune12140452013-07-19 21:45:06 +0000865 ContNextScc = true;
866 } else if (sccRemainedNumBlk != 1 && sccRemainedNumBlk < SccNumBlk) {
867 SccNumBlk = sccRemainedNumBlk;
868 It = SccBeginIter;
869 ContNextScc = false;
Vincent Lejeune9e8ba2b2013-07-19 21:44:56 +0000870 DEBUG(
Vincent Lejeune12140452013-07-19 21:45:06 +0000871 dbgs() << "repeat processing SCC" << getSCCNum(MBB)
872 << "sccNumIter = " << SccNumIter << "\n";
873 FuncRep->viewCFG();
Vincent Lejeune9e8ba2b2013-07-19 21:44:56 +0000874 );
Tom Stellardf98f2ce2012-12-11 21:25:42 +0000875 } else {
876 // Finish the current scc.
Vincent Lejeune12140452013-07-19 21:45:06 +0000877 ContNextScc = true;
Tom Stellardf98f2ce2012-12-11 21:25:42 +0000878 }
879 } else {
880 // Continue on next component in the current scc.
Vincent Lejeune12140452013-07-19 21:45:06 +0000881 ContNextScc = false;
Tom Stellardf98f2ce2012-12-11 21:25:42 +0000882 }
883
Vincent Lejeune12140452013-07-19 21:45:06 +0000884 if (ContNextScc)
885 SccBeginMBB = NULL;
Tom Stellardf98f2ce2012-12-11 21:25:42 +0000886 } //while, "one iteration" over the function.
887
Vincent Lejeune12140452013-07-19 21:45:06 +0000888 MachineBasicBlock *EntryMBB =
889 GraphTraits<MachineFunction *>::nodes_begin(FuncRep);
890 if (EntryMBB->succ_size() == 0) {
891 Finish = true;
Vincent Lejeune9e8ba2b2013-07-19 21:44:56 +0000892 DEBUG(
893 dbgs() << "Reduce to one block\n";
894 );
Tom Stellardf98f2ce2012-12-11 21:25:42 +0000895 } else {
Vincent Lejeune12140452013-07-19 21:45:06 +0000896 int NewnumRemainedBlk
897 = countActiveBlock(OrderedBlks.begin(), OrderedBlks.end());
Tom Stellardf98f2ce2012-12-11 21:25:42 +0000898 // consider cloned blocks ??
Vincent Lejeune12140452013-07-19 21:45:06 +0000899 if (NewnumRemainedBlk == 1 || NewnumRemainedBlk < NumRemainedBlk) {
900 MakeProgress = true;
901 NumRemainedBlk = NewnumRemainedBlk;
Tom Stellardf98f2ce2012-12-11 21:25:42 +0000902 } else {
Vincent Lejeune12140452013-07-19 21:45:06 +0000903 MakeProgress = false;
Vincent Lejeune9e8ba2b2013-07-19 21:44:56 +0000904 DEBUG(
905 dbgs() << "No progress\n";
906 );
Tom Stellardf98f2ce2012-12-11 21:25:42 +0000907 }
908 }
Vincent Lejeune12140452013-07-19 21:45:06 +0000909 } while (!Finish && MakeProgress);
Tom Stellardf98f2ce2012-12-11 21:25:42 +0000910
911 // Misc wrap up to maintain the consistency of the Function representation.
Vincent Lejeune12140452013-07-19 21:45:06 +0000912 wrapup(GraphTraits<MachineFunction *>::nodes_begin(FuncRep));
Tom Stellardf98f2ce2012-12-11 21:25:42 +0000913
914 // Detach retired Block, release memory.
Vincent Lejeune12140452013-07-19 21:45:06 +0000915 for (MBBInfoMap::iterator It = BlockInfoMap.begin(), E = BlockInfoMap.end();
916 It != E; ++It) {
917 if ((*It).second && (*It).second->IsRetired) {
918 assert(((*It).first)->getNumber() != -1);
Vincent Lejeune9e8ba2b2013-07-19 21:44:56 +0000919 DEBUG(
Vincent Lejeune12140452013-07-19 21:45:06 +0000920 dbgs() << "Erase BB" << ((*It).first)->getNumber() << "\n";
Vincent Lejeune9e8ba2b2013-07-19 21:44:56 +0000921 );
Vincent Lejeune12140452013-07-19 21:45:06 +0000922 (*It).first->eraseFromParent(); //Remove from the parent Function.
Tom Stellardf98f2ce2012-12-11 21:25:42 +0000923 }
Vincent Lejeune12140452013-07-19 21:45:06 +0000924 delete (*It).second;
Tom Stellardf98f2ce2012-12-11 21:25:42 +0000925 }
Vincent Lejeune12140452013-07-19 21:45:06 +0000926 BlockInfoMap.clear();
927 LLInfoMap.clear();
Tom Stellardf98f2ce2012-12-11 21:25:42 +0000928
Vincent Lejeune9e8ba2b2013-07-19 21:44:56 +0000929 DEBUG(
Vincent Lejeune12140452013-07-19 21:45:06 +0000930 FuncRep->viewCFG();
Vincent Lejeune9e8ba2b2013-07-19 21:44:56 +0000931 );
Tom Stellardf98f2ce2012-12-11 21:25:42 +0000932
Vincent Lejeune12140452013-07-19 21:45:06 +0000933 if (!Finish)
Vincent Lejeune9e8ba2b2013-07-19 21:44:56 +0000934 llvm_unreachable("IRREDUCIBL_CF");
Tom Stellardf98f2ce2012-12-11 21:25:42 +0000935
936 return true;
Vincent Lejeune12140452013-07-19 21:45:06 +0000937}
Tom Stellardf98f2ce2012-12-11 21:25:42 +0000938
Tom Stellardf98f2ce2012-12-11 21:25:42 +0000939
Vincent Lejeune12140452013-07-19 21:45:06 +0000940
941void AMDGPUCFGStructurizer::orderBlocks(MachineFunction *MF) {
942 int SccNum = 0;
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();
Tom Stellardf98f2ce2012-12-11 21:25:42 +0000949 blockIter != blockEnd; ++blockIter) {
Vincent Lejeune12140452013-07-19 21:45:06 +0000950 MBB = *blockIter;
951 OrderedBlks.push_back(MBB);
952 recordSccnum(MBB, SccNum);
Tom Stellardf98f2ce2012-12-11 21:25:42 +0000953 }
954 }
955
956 //walk through all the block in func to check for unreachable
Vincent Lejeune12140452013-07-19 21:45:06 +0000957 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";
Tom Stellardf98f2ce2012-12-11 21:25:42 +0000964 }
Vincent Lejeune12140452013-07-19 21:45:06 +0000965}
Tom Stellardf98f2ce2012-12-11 21:25:42 +0000966
Vincent Lejeune12140452013-07-19 21:45:06 +0000967int AMDGPUCFGStructurizer::patternMatch(MachineBasicBlock *MBB) {
968 int NumMatch = 0;
969 int CurMatch;
Tom Stellardf98f2ce2012-12-11 21:25:42 +0000970
Vincent Lejeune9e8ba2b2013-07-19 21:44:56 +0000971 DEBUG(
Vincent Lejeune12140452013-07-19 21:45:06 +0000972 dbgs() << "Begin patternMatch BB" << MBB->getNumber() << "\n";
Vincent Lejeune9e8ba2b2013-07-19 21:44:56 +0000973 );
Tom Stellardf98f2ce2012-12-11 21:25:42 +0000974
Vincent Lejeune12140452013-07-19 21:45:06 +0000975 while ((CurMatch = patternMatchGroup(MBB)) > 0)
976 NumMatch += CurMatch;
Tom Stellardf98f2ce2012-12-11 21:25:42 +0000977
Vincent Lejeune9e8ba2b2013-07-19 21:44:56 +0000978 DEBUG(
Vincent Lejeune12140452013-07-19 21:45:06 +0000979 dbgs() << "End patternMatch BB" << MBB->getNumber()
980 << ", numMatch = " << NumMatch << "\n";
Vincent Lejeune9e8ba2b2013-07-19 21:44:56 +0000981 );
Tom Stellardf98f2ce2012-12-11 21:25:42 +0000982
Vincent Lejeune12140452013-07-19 21:45:06 +0000983 return NumMatch;
984}
Tom Stellardf98f2ce2012-12-11 21:25:42 +0000985
Vincent Lejeune12140452013-07-19 21:45:06 +0000986int AMDGPUCFGStructurizer::patternMatchGroup(MachineBasicBlock *MBB) {
987 int NumMatch = 0;
988 NumMatch += loopendPatternMatch();
989 NumMatch += serialPatternMatch(MBB);
990 NumMatch += ifPatternMatch(MBB);
991 return NumMatch;
992}
Tom Stellardf98f2ce2012-12-11 21:25:42 +0000993
Vincent Lejeune12140452013-07-19 21:45:06 +0000994
995int AMDGPUCFGStructurizer::serialPatternMatch(MachineBasicBlock *MBB) {
996 if (MBB->succ_size() != 1)
Tom Stellardf98f2ce2012-12-11 21:25:42 +0000997 return 0;
Tom Stellardf98f2ce2012-12-11 21:25:42 +0000998
Vincent Lejeune12140452013-07-19 21:45:06 +0000999 MachineBasicBlock *childBlk = *MBB->succ_begin();
1000 if (childBlk->pred_size() != 1 || isActiveLoophead(childBlk))
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001001 return 0;
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001002
Vincent Lejeune12140452013-07-19 21:45:06 +00001003 mergeSerialBlock(MBB, childBlk);
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001004 ++numSerialPatternMatch;
1005 return 1;
Vincent Lejeune12140452013-07-19 21:45:06 +00001006}
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001007
Vincent Lejeune12140452013-07-19 21:45:06 +00001008int AMDGPUCFGStructurizer::ifPatternMatch(MachineBasicBlock *MBB) {
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001009 //two edges
Vincent Lejeune12140452013-07-19 21:45:06 +00001010 if (MBB->succ_size() != 2)
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001011 return 0;
Vincent Lejeune12140452013-07-19 21:45:06 +00001012 if (hasBackEdge(MBB))
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001013 return 0;
Vincent Lejeune12140452013-07-19 21:45:06 +00001014 MachineInstr *BranchMI = getNormalBlockBranchInstr(MBB);
1015 if (!BranchMI)
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001016 return 0;
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001017
Vincent Lejeune12140452013-07-19 21:45:06 +00001018 assert(isCondBranch(BranchMI));
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001019
Vincent Lejeune12140452013-07-19 21:45:06 +00001020 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;
1027 int Cloned = 0;
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001028
Vincent Lejeune12140452013-07-19 21:45:06 +00001029 assert (!TrueMBB->succ_empty() || !FalseMBB->succ_empty());
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001030 // TODO: Simplify
Vincent Lejeune12140452013-07-19 21:45:06 +00001031 if (TrueMBB->succ_size() == 1 && FalseMBB->succ_size() == 1
1032 && *TrueMBB->succ_begin() == *FalseMBB->succ_begin()) {
1033 // Diamond pattern
1034 LandBlk = *TrueMBB->succ_begin();
1035 } else if (TrueMBB->succ_size() == 1 && *TrueMBB->succ_begin() == FalseMBB) {
1036 // Triangle pattern, false is empty
1037 LandBlk = FalseMBB;
1038 FalseMBB = NULL;
1039 } else if (FalseMBB->succ_size() == 1
1040 && *FalseMBB->succ_begin() == TrueMBB) {
1041 // Triangle pattern, true is empty
1042 LandBlk = TrueMBB;
1043 TrueMBB = NULL;
1044 } else if (FalseMBB->succ_size() == 1
1045 && isSameloopDetachedContbreak(TrueMBB, FalseMBB)) {
1046 LandBlk = *FalseMBB->succ_begin();
1047 } else if (TrueMBB->succ_size() == 1
1048 && isSameloopDetachedContbreak(FalseMBB, TrueMBB)) {
1049 LandBlk = *TrueMBB->succ_begin();
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001050 } else {
Vincent Lejeune12140452013-07-19 21:45:06 +00001051 return handleJumpintoIf(MBB, TrueMBB, FalseMBB);
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001052 }
1053
1054 // improveSimpleJumpinfoIf can handle the case where landBlk == NULL but the
1055 // new BB created for landBlk==NULL may introduce new challenge to the
1056 // reduction process.
Vincent Lejeune12140452013-07-19 21:45:06 +00001057 if (LandBlk &&
1058 ((TrueMBB && TrueMBB->pred_size() > 1)
1059 || (FalseMBB && FalseMBB->pred_size() > 1))) {
1060 Cloned += improveSimpleJumpintoIf(MBB, TrueMBB, FalseMBB, &LandBlk);
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001061 }
1062
Vincent Lejeune12140452013-07-19 21:45:06 +00001063 if (TrueMBB && TrueMBB->pred_size() > 1) {
1064 TrueMBB = cloneBlockForPredecessor(TrueMBB, MBB);
1065 ++Cloned;
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001066 }
1067
Vincent Lejeune12140452013-07-19 21:45:06 +00001068 if (FalseMBB && FalseMBB->pred_size() > 1) {
1069 FalseMBB = cloneBlockForPredecessor(FalseMBB, MBB);
1070 ++Cloned;
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001071 }
1072
Vincent Lejeune12140452013-07-19 21:45:06 +00001073 mergeIfthenelseBlock(BranchMI, MBB, TrueMBB, FalseMBB, LandBlk);
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001074
1075 ++numIfPatternMatch;
1076
Vincent Lejeune12140452013-07-19 21:45:06 +00001077 numClonedBlock += Cloned;
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001078
Vincent Lejeune12140452013-07-19 21:45:06 +00001079 return 1 + Cloned;
1080}
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001081
Vincent Lejeune12140452013-07-19 21:45:06 +00001082int AMDGPUCFGStructurizer::loopendPatternMatch() {
1083 std::vector<MachineLoop *> NestedLoops;
1084 for (MachineLoopInfo::iterator It = MLI->begin(), E = MLI->end();
1085 It != E; ++It) {
1086 df_iterator<MachineLoop *> LpIt = df_begin(*It),
1087 LpE = df_end(*It);
1088 for (; LpIt != LpE; ++LpIt)
1089 NestedLoops.push_back(*LpIt);
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001090 }
Vincent Lejeune12140452013-07-19 21:45:06 +00001091 if (NestedLoops.size() == 0)
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001092 return 0;
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001093
1094 // Process nested loop outside->inside, so "continue" to a outside loop won't
1095 // be mistaken as "break" of the current loop.
Vincent Lejeune12140452013-07-19 21:45:06 +00001096 int Num = 0;
1097 for (std::vector<MachineLoop *>::reverse_iterator It = NestedLoops.rbegin(),
1098 E = NestedLoops.rend(); It != E; ++It) {
1099 MachineLoop *ExaminedLoop = *It;
1100 if (ExaminedLoop->getNumBlocks() == 0 || Visited[ExaminedLoop])
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001101 continue;
Vincent Lejeune12140452013-07-19 21:45:06 +00001102 DEBUG(dbgs() << "Processing:\n"; ExaminedLoop->dump(););
1103 int NumBreak = mergeLoop(ExaminedLoop);
1104 if (NumBreak == -1)
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001105 break;
Vincent Lejeune12140452013-07-19 21:45:06 +00001106 Num += NumBreak;
1107 }
1108 return Num;
1109}
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001110
Vincent Lejeune12140452013-07-19 21:45:06 +00001111int AMDGPUCFGStructurizer::mergeLoop(MachineLoop *LoopRep) {
1112 MachineBasicBlock *LoopHeader = LoopRep->getHeader();
1113 MBBVector ExitingMBBs;
1114 LoopRep->getExitingBlocks(ExitingMBBs);
1115 assert(!ExitingMBBs.empty() && "Infinite Loop not supported");
1116 DEBUG(dbgs() << "Loop has " << ExitingMBBs.size() << " exiting blocks\n";);
1117 // We assume a single ExitBlk
1118 MBBVector ExitBlks;
1119 LoopRep->getExitBlocks(ExitBlks);
1120 SmallPtrSet<MachineBasicBlock *, 2> ExitBlkSet;
1121 for (unsigned i = 0, e = ExitBlks.size(); i < e; ++i)
1122 ExitBlkSet.insert(ExitBlks[i]);
1123 assert(ExitBlkSet.size() == 1);
1124 MachineBasicBlock *ExitBlk = *ExitBlks.begin();
1125 assert(ExitBlk && "Loop has several exit block");
1126 MBBVector LatchBlks;
1127 typedef GraphTraits<Inverse<MachineBasicBlock*> > InvMBBTraits;
1128 InvMBBTraits::ChildIteratorType PI = InvMBBTraits::child_begin(LoopHeader),
1129 PE = InvMBBTraits::child_end(LoopHeader);
1130 for (; PI != PE; PI++) {
1131 if (LoopRep->contains(*PI))
1132 LatchBlks.push_back(*PI);
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001133 }
1134
Vincent Lejeune12140452013-07-19 21:45:06 +00001135 for (unsigned i = 0, e = ExitingMBBs.size(); i < e; ++i)
1136 mergeLoopbreakBlock(ExitingMBBs[i], ExitBlk);
1137 for (unsigned i = 0, e = LatchBlks.size(); i < e; ++i)
1138 settleLoopcontBlock(LatchBlks[i], LoopHeader);
1139 int Match = 0;
1140 do {
1141 Match = 0;
1142 Match += serialPatternMatch(LoopHeader);
1143 Match += ifPatternMatch(LoopHeader);
1144 } while (Match > 0);
1145 mergeLooplandBlock(LoopHeader, ExitBlk);
1146 MachineLoop *ParentLoop = LoopRep->getParentLoop();
1147 if (ParentLoop)
1148 MLI->changeLoopFor(LoopHeader, ParentLoop);
1149 else
1150 MLI->removeBlock(LoopHeader);
1151 Visited[LoopRep] = true;
1152 return 1;
1153}
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001154
Vincent Lejeune12140452013-07-19 21:45:06 +00001155int AMDGPUCFGStructurizer::loopcontPatternMatch(MachineLoop *LoopRep,
1156 MachineBasicBlock *LoopHeader) {
1157 int NumCont = 0;
1158 SmallVector<MachineBasicBlock *, DEFAULT_VEC_SLOTS> ContMBB;
1159 typedef GraphTraits<Inverse<MachineBasicBlock *> > GTIM;
1160 GTIM::ChildIteratorType It = GTIM::child_begin(LoopHeader),
1161 E = GTIM::child_end(LoopHeader);
1162 for (; It != E; ++It) {
1163 MachineBasicBlock *MBB = *It;
1164 if (LoopRep->contains(MBB)) {
1165 handleLoopcontBlock(MBB, MLI->getLoopFor(MBB),
1166 LoopHeader, LoopRep);
1167 ContMBB.push_back(MBB);
1168 ++NumCont;
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001169 }
1170 }
1171
Vincent Lejeune12140452013-07-19 21:45:06 +00001172 for (SmallVectorImpl<MachineBasicBlock *>::iterator It = ContMBB.begin(),
1173 E = ContMBB.end(); It != E; ++It) {
1174 (*It)->removeSuccessor(LoopHeader);
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001175 }
1176
Vincent Lejeune12140452013-07-19 21:45:06 +00001177 numLoopcontPatternMatch += NumCont;
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001178
Vincent Lejeune12140452013-07-19 21:45:06 +00001179 return NumCont;
1180}
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001181
1182
Vincent Lejeune12140452013-07-19 21:45:06 +00001183bool AMDGPUCFGStructurizer::isSameloopDetachedContbreak(
1184 MachineBasicBlock *Src1MBB, MachineBasicBlock *Src2MBB) {
1185 if (Src1MBB->succ_size() == 0) {
1186 MachineLoop *LoopRep = MLI->getLoopFor(Src1MBB);
1187 if (LoopRep&& LoopRep == MLI->getLoopFor(Src2MBB)) {
1188 MachineBasicBlock *&TheEntry = LLInfoMap[LoopRep];
1189 if (TheEntry) {
Vincent Lejeune9e8ba2b2013-07-19 21:44:56 +00001190 DEBUG(
1191 dbgs() << "isLoopContBreakBlock yes src1 = BB"
Vincent Lejeune12140452013-07-19 21:45:06 +00001192 << Src1MBB->getNumber()
1193 << " src2 = BB" << Src2MBB->getNumber() << "\n";
Vincent Lejeune9e8ba2b2013-07-19 21:44:56 +00001194 );
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001195 return true;
1196 }
1197 }
1198 }
1199 return false;
Vincent Lejeune12140452013-07-19 21:45:06 +00001200}
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001201
Vincent Lejeune12140452013-07-19 21:45:06 +00001202int AMDGPUCFGStructurizer::handleJumpintoIf(MachineBasicBlock *HeadMBB,
1203 MachineBasicBlock *TrueMBB, MachineBasicBlock *FalseMBB) {
1204 int Num = handleJumpintoIfImp(HeadMBB, TrueMBB, FalseMBB);
1205 if (Num == 0) {
Vincent Lejeune9e8ba2b2013-07-19 21:44:56 +00001206 DEBUG(
1207 dbgs() << "handleJumpintoIf swap trueBlk and FalseBlk" << "\n";
1208 );
Vincent Lejeune12140452013-07-19 21:45:06 +00001209 Num = handleJumpintoIfImp(HeadMBB, FalseMBB, TrueMBB);
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001210 }
Vincent Lejeune12140452013-07-19 21:45:06 +00001211 return Num;
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001212}
1213
Vincent Lejeune12140452013-07-19 21:45:06 +00001214int AMDGPUCFGStructurizer::handleJumpintoIfImp(MachineBasicBlock *HeadMBB,
1215 MachineBasicBlock *TrueMBB, MachineBasicBlock *FalseMBB) {
1216 int Num = 0;
1217 MachineBasicBlock *DownBlk;
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001218
1219 //trueBlk could be the common post dominator
Vincent Lejeune12140452013-07-19 21:45:06 +00001220 DownBlk = TrueMBB;
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001221
Vincent Lejeune9e8ba2b2013-07-19 21:44:56 +00001222 DEBUG(
Vincent Lejeune12140452013-07-19 21:45:06 +00001223 dbgs() << "handleJumpintoIfImp head = BB" << HeadMBB->getNumber()
1224 << " true = BB" << TrueMBB->getNumber()
1225 << ", numSucc=" << TrueMBB->succ_size()
1226 << " false = BB" << FalseMBB->getNumber() << "\n";
Vincent Lejeune9e8ba2b2013-07-19 21:44:56 +00001227 );
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001228
Vincent Lejeune12140452013-07-19 21:45:06 +00001229 while (DownBlk) {
Vincent Lejeune9e8ba2b2013-07-19 21:44:56 +00001230 DEBUG(
Vincent Lejeune12140452013-07-19 21:45:06 +00001231 dbgs() << "check down = BB" << DownBlk->getNumber();
Vincent Lejeune9e8ba2b2013-07-19 21:44:56 +00001232 );
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001233
Vincent Lejeune12140452013-07-19 21:45:06 +00001234 if (singlePathTo(FalseMBB, DownBlk) == SinglePath_InPath) {
Vincent Lejeune9e8ba2b2013-07-19 21:44:56 +00001235 DEBUG(
1236 dbgs() << " working\n";
1237 );
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001238
Vincent Lejeune12140452013-07-19 21:45:06 +00001239 Num += cloneOnSideEntryTo(HeadMBB, TrueMBB, DownBlk);
1240 Num += cloneOnSideEntryTo(HeadMBB, FalseMBB, DownBlk);
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001241
Vincent Lejeune12140452013-07-19 21:45:06 +00001242 numClonedBlock += Num;
1243 Num += serialPatternMatch(*HeadMBB->succ_begin());
1244 Num += serialPatternMatch(*(++HeadMBB->succ_begin()));
1245 Num += ifPatternMatch(HeadMBB);
1246 assert(Num > 0);
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001247
1248 break;
1249 }
Vincent Lejeune9e8ba2b2013-07-19 21:44:56 +00001250 DEBUG(
1251 dbgs() << " not working\n";
1252 );
Vincent Lejeune12140452013-07-19 21:45:06 +00001253 DownBlk = (DownBlk->succ_size() == 1) ? (*DownBlk->succ_begin()) : NULL;
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001254 } // walk down the postDomTree
1255
Vincent Lejeune12140452013-07-19 21:45:06 +00001256 return Num;
1257}
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001258
Vincent Lejeune12140452013-07-19 21:45:06 +00001259void AMDGPUCFGStructurizer::showImproveSimpleJumpintoIf(
1260 MachineBasicBlock *HeadMBB, MachineBasicBlock *TrueMBB,
1261 MachineBasicBlock *FalseMBB, MachineBasicBlock *LandMBB, bool Detail) {
1262 dbgs() << "head = BB" << HeadMBB->getNumber()
1263 << " size = " << HeadMBB->size();
1264 if (Detail) {
Vincent Lejeune9e8ba2b2013-07-19 21:44:56 +00001265 dbgs() << "\n";
Vincent Lejeune12140452013-07-19 21:45:06 +00001266 HeadMBB->print(dbgs());
Vincent Lejeune9e8ba2b2013-07-19 21:44:56 +00001267 dbgs() << "\n";
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001268 }
1269
Vincent Lejeune12140452013-07-19 21:45:06 +00001270 if (TrueMBB) {
1271 dbgs() << ", true = BB" << TrueMBB->getNumber() << " size = "
1272 << TrueMBB->size() << " numPred = " << TrueMBB->pred_size();
1273 if (Detail) {
Vincent Lejeune9e8ba2b2013-07-19 21:44:56 +00001274 dbgs() << "\n";
Vincent Lejeune12140452013-07-19 21:45:06 +00001275 TrueMBB->print(dbgs());
Vincent Lejeune9e8ba2b2013-07-19 21:44:56 +00001276 dbgs() << "\n";
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001277 }
1278 }
Vincent Lejeune12140452013-07-19 21:45:06 +00001279 if (FalseMBB) {
1280 dbgs() << ", false = BB" << FalseMBB->getNumber() << " size = "
1281 << FalseMBB->size() << " numPred = " << FalseMBB->pred_size();
1282 if (Detail) {
Vincent Lejeune9e8ba2b2013-07-19 21:44:56 +00001283 dbgs() << "\n";
Vincent Lejeune12140452013-07-19 21:45:06 +00001284 FalseMBB->print(dbgs());
Vincent Lejeune9e8ba2b2013-07-19 21:44:56 +00001285 dbgs() << "\n";
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001286 }
1287 }
Vincent Lejeune12140452013-07-19 21:45:06 +00001288 if (LandMBB) {
1289 dbgs() << ", land = BB" << LandMBB->getNumber() << " size = "
1290 << LandMBB->size() << " numPred = " << LandMBB->pred_size();
1291 if (Detail) {
Vincent Lejeune9e8ba2b2013-07-19 21:44:56 +00001292 dbgs() << "\n";
Vincent Lejeune12140452013-07-19 21:45:06 +00001293 LandMBB->print(dbgs());
Vincent Lejeune9e8ba2b2013-07-19 21:44:56 +00001294 dbgs() << "\n";
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001295 }
1296 }
1297
Vincent Lejeune9e8ba2b2013-07-19 21:44:56 +00001298 dbgs() << "\n";
Vincent Lejeune12140452013-07-19 21:45:06 +00001299}
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001300
Vincent Lejeune12140452013-07-19 21:45:06 +00001301int AMDGPUCFGStructurizer::improveSimpleJumpintoIf(MachineBasicBlock *HeadMBB,
1302 MachineBasicBlock *TrueMBB, MachineBasicBlock *FalseMBB,
1303 MachineBasicBlock **LandMBBPtr) {
1304 bool MigrateTrue = false;
1305 bool MigrateFalse = false;
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001306
Vincent Lejeune12140452013-07-19 21:45:06 +00001307 MachineBasicBlock *LandBlk = *LandMBBPtr;
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001308
Vincent Lejeune12140452013-07-19 21:45:06 +00001309 assert((!TrueMBB || TrueMBB->succ_size() <= 1)
1310 && (!FalseMBB || FalseMBB->succ_size() <= 1));
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001311
Vincent Lejeune12140452013-07-19 21:45:06 +00001312 if (TrueMBB == FalseMBB)
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001313 return 0;
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001314
Vincent Lejeune12140452013-07-19 21:45:06 +00001315 MigrateTrue = needMigrateBlock(TrueMBB);
1316 MigrateFalse = needMigrateBlock(FalseMBB);
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001317
Vincent Lejeune12140452013-07-19 21:45:06 +00001318 if (!MigrateTrue && !MigrateFalse)
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001319 return 0;
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001320
1321 // If we need to migrate either trueBlk and falseBlk, migrate the rest that
1322 // have more than one predecessors. without doing this, its predecessor
1323 // rather than headBlk will have undefined value in initReg.
Vincent Lejeune12140452013-07-19 21:45:06 +00001324 if (!MigrateTrue && TrueMBB && TrueMBB->pred_size() > 1)
1325 MigrateTrue = true;
1326 if (!MigrateFalse && FalseMBB && FalseMBB->pred_size() > 1)
1327 MigrateFalse = true;
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001328
Vincent Lejeune9e8ba2b2013-07-19 21:44:56 +00001329 DEBUG(
1330 dbgs() << "before improveSimpleJumpintoIf: ";
Vincent Lejeune12140452013-07-19 21:45:06 +00001331 showImproveSimpleJumpintoIf(HeadMBB, TrueMBB, FalseMBB, LandBlk, 0);
Vincent Lejeune9e8ba2b2013-07-19 21:44:56 +00001332 );
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001333
1334 // org: headBlk => if () {trueBlk} else {falseBlk} => landBlk
1335 //
1336 // new: headBlk => if () {initReg = 1; org trueBlk branch} else
1337 // {initReg = 0; org falseBlk branch }
1338 // => landBlk => if (initReg) {org trueBlk} else {org falseBlk}
1339 // => org landBlk
1340 // if landBlk->pred_size() > 2, put the about if-else inside
1341 // if (initReg !=2) {...}
1342 //
1343 // add initReg = initVal to headBlk
1344
1345 const TargetRegisterClass * I32RC = TRI->getCFGStructurizerRegClass(MVT::i32);
Vincent Lejeune12140452013-07-19 21:45:06 +00001346 unsigned InitReg =
1347 HeadMBB->getParent()->getRegInfo().createVirtualRegister(I32RC);
1348 if (!MigrateTrue || !MigrateFalse)
1349 llvm_unreachable("Extra register needed to handle CFG");
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001350
Vincent Lejeune12140452013-07-19 21:45:06 +00001351 int NumNewBlk = 0;
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001352
Vincent Lejeune12140452013-07-19 21:45:06 +00001353 if (!LandBlk) {
1354 LandBlk = HeadMBB->getParent()->CreateMachineBasicBlock();
1355 HeadMBB->getParent()->push_back(LandBlk); //insert to function
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001356
Vincent Lejeune12140452013-07-19 21:45:06 +00001357 if (TrueMBB) {
1358 TrueMBB->addSuccessor(LandBlk);
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001359 } else {
Vincent Lejeune12140452013-07-19 21:45:06 +00001360 HeadMBB->addSuccessor(LandBlk);
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001361 }
1362
Vincent Lejeune12140452013-07-19 21:45:06 +00001363 if (FalseMBB) {
1364 FalseMBB->addSuccessor(LandBlk);
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001365 } else {
Vincent Lejeune12140452013-07-19 21:45:06 +00001366 HeadMBB->addSuccessor(LandBlk);
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001367 }
1368
Vincent Lejeune12140452013-07-19 21:45:06 +00001369 NumNewBlk ++;
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001370 }
1371
Vincent Lejeune12140452013-07-19 21:45:06 +00001372 bool LandBlkHasOtherPred = (LandBlk->pred_size() > 2);
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001373
1374 //insert AMDGPU::ENDIF to avoid special case "input landBlk == NULL"
Vincent Lejeune12140452013-07-19 21:45:06 +00001375 MachineBasicBlock::iterator I = insertInstrBefore(LandBlk, AMDGPU::ENDIF);
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001376
Vincent Lejeune12140452013-07-19 21:45:06 +00001377 if (LandBlkHasOtherPred) {
1378 llvm_unreachable("Extra register needed to handle CFG");
1379 unsigned CmpResReg =
1380 HeadMBB->getParent()->getRegInfo().createVirtualRegister(I32RC);
1381 llvm_unreachable("Extra compare instruction needed to handle CFG");
1382 insertCondBranchBefore(LandBlk, I, AMDGPU::IF_PREDICATE_SET,
1383 CmpResReg, DebugLoc());
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001384 }
1385
Vincent Lejeune12140452013-07-19 21:45:06 +00001386 insertCondBranchBefore(LandBlk, I, AMDGPU::IF_PREDICATE_SET, InitReg,
1387 DebugLoc());
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001388
Vincent Lejeune12140452013-07-19 21:45:06 +00001389 if (MigrateTrue) {
1390 migrateInstruction(TrueMBB, LandBlk, I);
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001391 // need to uncondionally insert the assignment to ensure a path from its
1392 // predecessor rather than headBlk has valid value in initReg if
1393 // (initVal != 1).
Vincent Lejeune12140452013-07-19 21:45:06 +00001394 llvm_unreachable("Extra register needed to handle CFG");
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001395 }
Vincent Lejeune12140452013-07-19 21:45:06 +00001396 insertInstrBefore(I, AMDGPU::ELSE);
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001397
Vincent Lejeune12140452013-07-19 21:45:06 +00001398 if (MigrateFalse) {
1399 migrateInstruction(FalseMBB, LandBlk, I);
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001400 // need to uncondionally insert the assignment to ensure a path from its
1401 // predecessor rather than headBlk has valid value in initReg if
1402 // (initVal != 0)
Vincent Lejeune12140452013-07-19 21:45:06 +00001403 llvm_unreachable("Extra register needed to handle CFG");
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001404 }
1405
Vincent Lejeune12140452013-07-19 21:45:06 +00001406 if (LandBlkHasOtherPred) {
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001407 // add endif
Vincent Lejeune12140452013-07-19 21:45:06 +00001408 insertInstrBefore(I, AMDGPU::ENDIF);
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001409
1410 // put initReg = 2 to other predecessors of landBlk
Vincent Lejeune12140452013-07-19 21:45:06 +00001411 for (MachineBasicBlock::pred_iterator PI = LandBlk->pred_begin(),
1412 PE = LandBlk->pred_end(); PI != PE; ++PI) {
1413 MachineBasicBlock *MBB = *PI;
1414 if (MBB != TrueMBB && MBB != FalseMBB)
1415 llvm_unreachable("Extra register needed to handle CFG");
1416 }
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001417 }
Vincent Lejeune9e8ba2b2013-07-19 21:44:56 +00001418 DEBUG(
1419 dbgs() << "result from improveSimpleJumpintoIf: ";
Vincent Lejeune12140452013-07-19 21:45:06 +00001420 showImproveSimpleJumpintoIf(HeadMBB, TrueMBB, FalseMBB, LandBlk, 0);
Vincent Lejeune9e8ba2b2013-07-19 21:44:56 +00001421 );
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001422
1423 // update landBlk
Vincent Lejeune12140452013-07-19 21:45:06 +00001424 *LandMBBPtr = LandBlk;
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001425
Vincent Lejeune12140452013-07-19 21:45:06 +00001426 return NumNewBlk;
1427}
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001428
Vincent Lejeune12140452013-07-19 21:45:06 +00001429void AMDGPUCFGStructurizer::handleLoopcontBlock(MachineBasicBlock *ContingMBB,
1430 MachineLoop *ContingLoop, MachineBasicBlock *ContMBB,
1431 MachineLoop *ContLoop) {
1432 DEBUG(dbgs() << "loopcontPattern cont = BB" << ContingMBB->getNumber()
1433 << " header = BB" << ContMBB->getNumber() << "\n";
1434 dbgs() << "Trying to continue loop-depth = "
1435 << getLoopDepth(ContLoop)
1436 << " from loop-depth = " << getLoopDepth(ContingLoop) << "\n";);
1437 settleLoopcontBlock(ContingMBB, ContMBB);
1438}
1439
1440void AMDGPUCFGStructurizer::mergeSerialBlock(MachineBasicBlock *DstMBB,
1441 MachineBasicBlock *SrcMBB) {
Vincent Lejeune9e8ba2b2013-07-19 21:44:56 +00001442 DEBUG(
Vincent Lejeune12140452013-07-19 21:45:06 +00001443 dbgs() << "serialPattern BB" << DstMBB->getNumber()
1444 << " <= BB" << SrcMBB->getNumber() << "\n";
Vincent Lejeune9e8ba2b2013-07-19 21:44:56 +00001445 );
Vincent Lejeune12140452013-07-19 21:45:06 +00001446 DstMBB->splice(DstMBB->end(), SrcMBB, SrcMBB->begin(), SrcMBB->end());
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001447
Vincent Lejeune12140452013-07-19 21:45:06 +00001448 DstMBB->removeSuccessor(SrcMBB);
1449 cloneSuccessorList(DstMBB, SrcMBB);
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001450
Vincent Lejeune12140452013-07-19 21:45:06 +00001451 removeSuccessor(SrcMBB);
1452 MLI->removeBlock(SrcMBB);
1453 retireBlock(SrcMBB);
1454}
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001455
Vincent Lejeune12140452013-07-19 21:45:06 +00001456void AMDGPUCFGStructurizer::mergeIfthenelseBlock(MachineInstr *BranchMI,
1457 MachineBasicBlock *MBB, MachineBasicBlock *TrueMBB,
1458 MachineBasicBlock *FalseMBB, MachineBasicBlock *LandMBB) {
Vincent Lejeune9e8ba2b2013-07-19 21:44:56 +00001459 DEBUG(
Vincent Lejeune12140452013-07-19 21:45:06 +00001460 dbgs() << "ifPattern BB" << MBB->getNumber();
Vincent Lejeune9e8ba2b2013-07-19 21:44:56 +00001461 dbgs() << "{ ";
Vincent Lejeune12140452013-07-19 21:45:06 +00001462 if (TrueMBB) {
1463 dbgs() << "BB" << TrueMBB->getNumber();
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001464 }
Vincent Lejeune9e8ba2b2013-07-19 21:44:56 +00001465 dbgs() << " } else ";
1466 dbgs() << "{ ";
Vincent Lejeune12140452013-07-19 21:45:06 +00001467 if (FalseMBB) {
1468 dbgs() << "BB" << FalseMBB->getNumber();
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001469 }
Vincent Lejeune9e8ba2b2013-07-19 21:44:56 +00001470 dbgs() << " }\n ";
1471 dbgs() << "landBlock: ";
Vincent Lejeune12140452013-07-19 21:45:06 +00001472 if (!LandMBB) {
Vincent Lejeune9e8ba2b2013-07-19 21:44:56 +00001473 dbgs() << "NULL";
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001474 } else {
Vincent Lejeune12140452013-07-19 21:45:06 +00001475 dbgs() << "BB" << LandMBB->getNumber();
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001476 }
Vincent Lejeune9e8ba2b2013-07-19 21:44:56 +00001477 dbgs() << "\n";
1478 );
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001479
Vincent Lejeune12140452013-07-19 21:45:06 +00001480 int OldOpcode = BranchMI->getOpcode();
1481 DebugLoc BranchDL = BranchMI->getDebugLoc();
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001482
1483// transform to
1484// if cond
1485// trueBlk
1486// else
1487// falseBlk
1488// endif
1489// landBlk
1490
Vincent Lejeune12140452013-07-19 21:45:06 +00001491 MachineBasicBlock::iterator I = BranchMI;
1492 insertCondBranchBefore(I, getBranchNzeroOpcode(OldOpcode),
1493 BranchDL);
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001494
Vincent Lejeune12140452013-07-19 21:45:06 +00001495 if (TrueMBB) {
1496 MBB->splice(I, TrueMBB, TrueMBB->begin(), TrueMBB->end());
1497 MBB->removeSuccessor(TrueMBB);
1498 if (LandMBB && TrueMBB->succ_size()!=0)
1499 TrueMBB->removeSuccessor(LandMBB);
1500 retireBlock(TrueMBB);
1501 MLI->removeBlock(TrueMBB);
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001502 }
1503
Vincent Lejeune12140452013-07-19 21:45:06 +00001504 if (FalseMBB) {
1505 insertInstrBefore(I, AMDGPU::ELSE);
1506 MBB->splice(I, FalseMBB, FalseMBB->begin(),
1507 FalseMBB->end());
1508 MBB->removeSuccessor(FalseMBB);
1509 if (LandMBB && FalseMBB->succ_size() != 0)
1510 FalseMBB->removeSuccessor(LandMBB);
1511 retireBlock(FalseMBB);
1512 MLI->removeBlock(FalseMBB);
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001513 }
Vincent Lejeune12140452013-07-19 21:45:06 +00001514 insertInstrBefore(I, AMDGPU::ENDIF);
1515
1516 BranchMI->eraseFromParent();
1517
1518 if (LandMBB && TrueMBB && FalseMBB)
1519 MBB->addSuccessor(LandMBB);
1520
1521}
1522
1523void AMDGPUCFGStructurizer::mergeLooplandBlock(MachineBasicBlock *DstBlk,
1524 MachineBasicBlock *LandMBB) {
1525 DEBUG(dbgs() << "loopPattern header = BB" << DstBlk->getNumber()
1526 << " land = BB" << LandMBB->getNumber() << "\n";);
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001527
1528 /* we last inserterd the DebugLoc in the
Vincent Lejeune12140452013-07-19 21:45:06 +00001529 * BREAK_LOGICALZ_i32 or AMDGPU::BREAK_LOGICALNZ statement in the current
1530 * dstBlk.
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001531 * search for the DebugLoc in the that statement.
1532 * if not found, we have to insert the empty/default DebugLoc */
Vincent Lejeune12140452013-07-19 21:45:06 +00001533 MachineInstr *LoopBreakInstr = getLoopBreakInstr(DstBlk);
1534 DebugLoc DLBreak = (LoopBreakInstr) ? LoopBreakInstr->getDebugLoc() :
1535 DebugLoc();
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001536
Vincent Lejeune12140452013-07-19 21:45:06 +00001537 insertInstrBefore(DstBlk, AMDGPU::WHILELOOP, DLBreak);
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001538
Vincent Lejeune12140452013-07-19 21:45:06 +00001539 /* we last inserterd the DebugLoc in the continue statement in the current
1540 * dstBlk.
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001541 * search for the DebugLoc in the continue statement.
1542 * if not found, we have to insert the empty/default DebugLoc */
Vincent Lejeune12140452013-07-19 21:45:06 +00001543 MachineInstr *ContinueInstr = getContinueInstr(DstBlk);
1544 DebugLoc DLContinue = (ContinueInstr) ? ContinueInstr->getDebugLoc() :
1545 DebugLoc();
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001546
Vincent Lejeune12140452013-07-19 21:45:06 +00001547 insertInstrEnd(DstBlk, AMDGPU::ENDLOOP, DLContinue);
1548 DstBlk->addSuccessor(LandMBB);
1549 DstBlk->removeSuccessor(DstBlk);
1550}
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001551
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001552
Vincent Lejeune12140452013-07-19 21:45:06 +00001553void AMDGPUCFGStructurizer::mergeLoopbreakBlock(MachineBasicBlock *ExitingMBB,
1554 MachineBasicBlock *LandMBB) {
1555 DEBUG(dbgs() << "loopbreakPattern exiting = BB" << ExitingMBB->getNumber()
1556 << " land = BB" << LandMBB->getNumber() << "\n";);
1557 MachineInstr *BranchMI = getLoopendBlockBranchInstr(ExitingMBB);
1558 assert(BranchMI && isCondBranch(BranchMI));
1559 DebugLoc DL = BranchMI->getDebugLoc();
1560 MachineBasicBlock *TrueBranch = getTrueBranch(BranchMI);
1561 MachineBasicBlock::iterator I = BranchMI;
1562 if (TrueBranch != LandMBB)
1563 reversePredicateSetter(I);
1564 insertCondBranchBefore(I, AMDGPU::PREDICATED_BREAK, DL);
1565 //now branchInst can be erase safely
1566 BranchMI->eraseFromParent();
1567 //now take care of successors, retire blocks
1568 ExitingMBB->removeSuccessor(LandMBB);
1569}
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001570
Vincent Lejeune12140452013-07-19 21:45:06 +00001571void AMDGPUCFGStructurizer::settleLoopcontBlock(MachineBasicBlock *ContingMBB,
1572 MachineBasicBlock *ContMBB) {
1573 DEBUG(dbgs() << "settleLoopcontBlock conting = BB"
1574 << ContingMBB->getNumber()
1575 << ", cont = BB" << ContMBB->getNumber() << "\n";);
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001576
Vincent Lejeune12140452013-07-19 21:45:06 +00001577 MachineInstr *MI = getLoopendBlockBranchInstr(ContingMBB);
1578 if (MI) {
1579 assert(isCondBranch(MI));
1580 MachineBasicBlock::iterator I = MI;
1581 MachineBasicBlock *TrueBranch = getTrueBranch(MI);
1582 int OldOpcode = MI->getOpcode();
1583 DebugLoc DL = MI->getDebugLoc();
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001584
Vincent Lejeune12140452013-07-19 21:45:06 +00001585 bool UseContinueLogical = ((&*ContingMBB->rbegin()) == MI);
1586
1587 if (UseContinueLogical == false) {
1588 int BranchOpcode =
1589 TrueBranch == ContMBB ? getBranchNzeroOpcode(OldOpcode) :
1590 getBranchZeroOpcode(OldOpcode);
1591 insertCondBranchBefore(I, BranchOpcode, DL);
1592 // insertEnd to ensure phi-moves, if exist, go before the continue-instr.
1593 insertInstrEnd(ContingMBB, AMDGPU::CONTINUE, DL);
1594 insertInstrEnd(ContingMBB, AMDGPU::ENDIF, DL);
1595 } else {
1596 int BranchOpcode =
1597 TrueBranch == ContMBB ? getContinueNzeroOpcode(OldOpcode) :
1598 getContinueZeroOpcode(OldOpcode);
1599 insertCondBranchBefore(I, BranchOpcode, DL);
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001600 }
Vincent Lejeune12140452013-07-19 21:45:06 +00001601
1602 MI->eraseFromParent();
1603 } else {
1604 // if we've arrived here then we've already erased the branch instruction
1605 // travel back up the basic block to see the last reference of our debug
1606 // location we've just inserted that reference here so it should be
1607 // representative insertEnd to ensure phi-moves, if exist, go before the
1608 // continue-instr.
1609 insertInstrEnd(ContingMBB, AMDGPU::CONTINUE,
1610 getLastDebugLocInBB(ContingMBB));
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001611 }
1612}
1613
Vincent Lejeune12140452013-07-19 21:45:06 +00001614int AMDGPUCFGStructurizer::cloneOnSideEntryTo(MachineBasicBlock *PreMBB,
1615 MachineBasicBlock *SrcMBB, MachineBasicBlock *DstMBB) {
1616 int Cloned = 0;
1617 assert(PreMBB->isSuccessor(SrcMBB));
1618 while (SrcMBB && SrcMBB != DstMBB) {
1619 assert(SrcMBB->succ_size() == 1);
1620 if (SrcMBB->pred_size() > 1) {
1621 SrcMBB = cloneBlockForPredecessor(SrcMBB, PreMBB);
1622 ++Cloned;
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001623 }
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001624
Vincent Lejeune12140452013-07-19 21:45:06 +00001625 PreMBB = SrcMBB;
1626 SrcMBB = *SrcMBB->succ_begin();
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001627 }
1628
Vincent Lejeune12140452013-07-19 21:45:06 +00001629 return Cloned;
1630}
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001631
Vincent Lejeune12140452013-07-19 21:45:06 +00001632MachineBasicBlock *
1633AMDGPUCFGStructurizer::cloneBlockForPredecessor(MachineBasicBlock *MBB,
1634 MachineBasicBlock *PredMBB) {
1635 assert(PredMBB->isSuccessor(MBB) &&
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001636 "succBlk is not a prececessor of curBlk");
1637
Vincent Lejeune12140452013-07-19 21:45:06 +00001638 MachineBasicBlock *CloneMBB = clone(MBB); //clone instructions
1639 replaceInstrUseOfBlockWith(PredMBB, MBB, CloneMBB);
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001640 //srcBlk, oldBlk, newBlk
1641
Vincent Lejeune12140452013-07-19 21:45:06 +00001642 PredMBB->removeSuccessor(MBB);
1643 PredMBB->addSuccessor(CloneMBB);
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001644
1645 // add all successor to cloneBlk
Vincent Lejeune12140452013-07-19 21:45:06 +00001646 cloneSuccessorList(CloneMBB, MBB);
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001647
Vincent Lejeune12140452013-07-19 21:45:06 +00001648 numClonedInstr += MBB->size();
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001649
Vincent Lejeune9e8ba2b2013-07-19 21:44:56 +00001650 DEBUG(
1651 dbgs() << "Cloned block: " << "BB"
Vincent Lejeune12140452013-07-19 21:45:06 +00001652 << MBB->getNumber() << "size " << MBB->size() << "\n";
Vincent Lejeune9e8ba2b2013-07-19 21:44:56 +00001653 );
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001654
Vincent Lejeune12140452013-07-19 21:45:06 +00001655 SHOWNEWBLK(CloneMBB, "result of Cloned block: ");
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001656
Vincent Lejeune12140452013-07-19 21:45:06 +00001657 return CloneMBB;
1658}
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001659
Vincent Lejeune12140452013-07-19 21:45:06 +00001660void AMDGPUCFGStructurizer::migrateInstruction(MachineBasicBlock *SrcMBB,
1661 MachineBasicBlock *DstMBB, MachineBasicBlock::iterator I) {
1662 MachineBasicBlock::iterator SpliceEnd;
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001663 //look for the input branchinstr, not the AMDGPU branchinstr
Vincent Lejeune12140452013-07-19 21:45:06 +00001664 MachineInstr *BranchMI = getNormalBlockBranchInstr(SrcMBB);
1665 if (!BranchMI) {
Vincent Lejeune9e8ba2b2013-07-19 21:44:56 +00001666 DEBUG(
1667 dbgs() << "migrateInstruction don't see branch instr\n" ;
1668 );
Vincent Lejeune12140452013-07-19 21:45:06 +00001669 SpliceEnd = SrcMBB->end();
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001670 } else {
Vincent Lejeune9e8ba2b2013-07-19 21:44:56 +00001671 DEBUG(
1672 dbgs() << "migrateInstruction see branch instr\n" ;
Vincent Lejeune12140452013-07-19 21:45:06 +00001673 BranchMI->dump();
Vincent Lejeune9e8ba2b2013-07-19 21:44:56 +00001674 );
Vincent Lejeune12140452013-07-19 21:45:06 +00001675 SpliceEnd = BranchMI;
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001676 }
Vincent Lejeune9e8ba2b2013-07-19 21:44:56 +00001677 DEBUG(
Vincent Lejeune12140452013-07-19 21:45:06 +00001678 dbgs() << "migrateInstruction before splice dstSize = " << DstMBB->size()
1679 << "srcSize = " << SrcMBB->size() << "\n";
Vincent Lejeune9e8ba2b2013-07-19 21:44:56 +00001680 );
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001681
1682 //splice insert before insertPos
Vincent Lejeune12140452013-07-19 21:45:06 +00001683 DstMBB->splice(I, SrcMBB, SrcMBB->begin(), SpliceEnd);
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001684
Vincent Lejeune9e8ba2b2013-07-19 21:44:56 +00001685 DEBUG(
Vincent Lejeune12140452013-07-19 21:45:06 +00001686 dbgs() << "migrateInstruction after splice dstSize = " << DstMBB->size()
1687 << "srcSize = " << SrcMBB->size() << "\n";
Vincent Lejeune9e8ba2b2013-07-19 21:44:56 +00001688 );
Vincent Lejeune12140452013-07-19 21:45:06 +00001689}
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001690
Vincent Lejeune12140452013-07-19 21:45:06 +00001691MachineBasicBlock *
1692AMDGPUCFGStructurizer::normalizeInfiniteLoopExit(MachineLoop* LoopRep) {
1693 MachineBasicBlock *LoopHeader = LoopRep->getHeader();
1694 MachineBasicBlock *LoopLatch = LoopRep->getLoopLatch();
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001695 const TargetRegisterClass * I32RC = TRI->getCFGStructurizerRegClass(MVT::i32);
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001696
Vincent Lejeune12140452013-07-19 21:45:06 +00001697 if (!LoopHeader || !LoopLatch)
1698 return NULL;
1699 MachineInstr *BranchMI = getLoopendBlockBranchInstr(LoopLatch);
1700 // Is LoopRep an infinite loop ?
1701 if (!BranchMI || !isUncondBranch(BranchMI))
1702 return NULL;
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001703
Vincent Lejeune12140452013-07-19 21:45:06 +00001704 MachineBasicBlock *DummyExitBlk = FuncRep->CreateMachineBasicBlock();
1705 FuncRep->push_back(DummyExitBlk); //insert to function
1706 SHOWNEWBLK(DummyExitBlk, "DummyExitBlock to normalize infiniteLoop: ");
1707 DEBUG(dbgs() << "Old branch instr: " << *BranchMI << "\n";);
1708 MachineBasicBlock::iterator I = BranchMI;
1709 unsigned ImmReg = FuncRep->getRegInfo().createVirtualRegister(I32RC);
1710 llvm_unreachable("Extra register needed to handle CFG");
1711 MachineInstr *NewMI = insertInstrBefore(I, AMDGPU::BRANCH_COND_i32);
1712 MachineInstrBuilder MIB(*FuncRep, NewMI);
1713 MIB.addMBB(LoopHeader);
1714 MIB.addReg(ImmReg, false);
1715 SHOWNEWINSTR(NewMI);
1716 BranchMI->eraseFromParent();
1717 LoopLatch->addSuccessor(DummyExitBlk);
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001718
Vincent Lejeune12140452013-07-19 21:45:06 +00001719 return DummyExitBlk;
1720}
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001721
Vincent Lejeune12140452013-07-19 21:45:06 +00001722void AMDGPUCFGStructurizer::removeUnconditionalBranch(MachineBasicBlock *MBB) {
1723 MachineInstr *BranchMI;
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001724
1725 // I saw two unconditional branch in one basic block in example
1726 // test_fc_do_while_or.c need to fix the upstream on this to remove the loop.
Vincent Lejeune12140452013-07-19 21:45:06 +00001727 while ((BranchMI = getLoopendBlockBranchInstr(MBB))
1728 && isUncondBranch(BranchMI)) {
1729 DEBUG(dbgs() << "Removing uncond branch instr"; BranchMI->dump(););
1730 BranchMI->eraseFromParent();
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001731 }
Vincent Lejeune12140452013-07-19 21:45:06 +00001732}
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001733
Vincent Lejeune12140452013-07-19 21:45:06 +00001734void AMDGPUCFGStructurizer::removeRedundantConditionalBranch(
1735 MachineBasicBlock *MBB) {
1736 if (MBB->succ_size() != 2)
1737 return;
1738 MachineBasicBlock *MBB1 = *MBB->succ_begin();
1739 MachineBasicBlock *MBB2 = *(++MBB->succ_begin());
1740 if (MBB1 != MBB2)
1741 return;
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001742
Vincent Lejeune12140452013-07-19 21:45:06 +00001743 MachineInstr *BranchMI = getNormalBlockBranchInstr(MBB);
1744 assert(BranchMI && isCondBranch(BranchMI));
1745 DEBUG(dbgs() << "Removing unneeded cond branch instr"; BranchMI->dump(););
1746 BranchMI->eraseFromParent();
1747 SHOWNEWBLK(MBB1, "Removing redundant successor");
1748 MBB->removeSuccessor(MBB1);
1749}
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001750
Vincent Lejeune12140452013-07-19 21:45:06 +00001751void AMDGPUCFGStructurizer::addDummyExitBlock(
1752 SmallVectorImpl<MachineBasicBlock*> &RetMBB) {
1753 MachineBasicBlock *DummyExitBlk = FuncRep->CreateMachineBasicBlock();
1754 FuncRep->push_back(DummyExitBlk); //insert to function
1755 insertInstrEnd(DummyExitBlk, AMDGPU::RETURN);
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001756
Vincent Lejeune12140452013-07-19 21:45:06 +00001757 for (SmallVectorImpl<MachineBasicBlock *>::iterator It = RetMBB.begin(),
1758 E = RetMBB.end(); It != E; ++It) {
1759 MachineBasicBlock *MBB = *It;
1760 MachineInstr *MI = getReturnInstr(MBB);
1761 if (MI)
1762 MI->eraseFromParent();
1763 MBB->addSuccessor(DummyExitBlk);
Vincent Lejeune9e8ba2b2013-07-19 21:44:56 +00001764 DEBUG(
Vincent Lejeune12140452013-07-19 21:45:06 +00001765 dbgs() << "Add dummyExitBlock to BB" << MBB->getNumber()
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001766 << " successors\n";
Vincent Lejeune9e8ba2b2013-07-19 21:44:56 +00001767 );
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001768 }
Vincent Lejeune12140452013-07-19 21:45:06 +00001769 SHOWNEWBLK(DummyExitBlk, "DummyExitBlock: ");
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001770}
1771
Vincent Lejeune12140452013-07-19 21:45:06 +00001772void AMDGPUCFGStructurizer::removeSuccessor(MachineBasicBlock *MBB) {
1773 while (MBB->succ_size())
1774 MBB->removeSuccessor(*MBB->succ_begin());
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001775}
1776
Vincent Lejeune12140452013-07-19 21:45:06 +00001777void AMDGPUCFGStructurizer::recordSccnum(MachineBasicBlock *MBB,
1778 int SccNum) {
1779 BlockInformation *&srcBlkInfo = BlockInfoMap[MBB];
1780 if (!srcBlkInfo)
1781 srcBlkInfo = new BlockInformation();
1782 srcBlkInfo->SccNum = SccNum;
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001783}
1784
Vincent Lejeune12140452013-07-19 21:45:06 +00001785void AMDGPUCFGStructurizer::retireBlock(MachineBasicBlock *MBB) {
Vincent Lejeune9e8ba2b2013-07-19 21:44:56 +00001786 DEBUG(
Vincent Lejeune12140452013-07-19 21:45:06 +00001787 dbgs() << "Retiring BB" << MBB->getNumber() << "\n";
Vincent Lejeune9e8ba2b2013-07-19 21:44:56 +00001788 );
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001789
Vincent Lejeune12140452013-07-19 21:45:06 +00001790 BlockInformation *&SrcBlkInfo = BlockInfoMap[MBB];
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001791
Vincent Lejeune12140452013-07-19 21:45:06 +00001792 if (!SrcBlkInfo)
1793 SrcBlkInfo = new BlockInformation();
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001794
Vincent Lejeune12140452013-07-19 21:45:06 +00001795 SrcBlkInfo->IsRetired = true;
1796 assert(MBB->succ_size() == 0 && MBB->pred_size() == 0
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001797 && "can't retire block yet");
1798}
1799
Vincent Lejeune12140452013-07-19 21:45:06 +00001800void AMDGPUCFGStructurizer::setLoopLandBlock(MachineLoop *loopRep,
1801 MachineBasicBlock *MBB) {
1802 MachineBasicBlock *&TheEntry = LLInfoMap[loopRep];
1803 if (!MBB) {
1804 MBB = FuncRep->CreateMachineBasicBlock();
1805 FuncRep->push_back(MBB); //insert to function
1806 SHOWNEWBLK(MBB, "DummyLandingBlock for loop without break: ");
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001807 }
Vincent Lejeune12140452013-07-19 21:45:06 +00001808 TheEntry = MBB;
Vincent Lejeune9e8ba2b2013-07-19 21:44:56 +00001809 DEBUG(
1810 dbgs() << "setLoopLandBlock loop-header = BB"
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001811 << loopRep->getHeader()->getNumber()
Vincent Lejeune12140452013-07-19 21:45:06 +00001812 << " landing-block = BB" << MBB->getNumber() << "\n";
Vincent Lejeune9e8ba2b2013-07-19 21:44:56 +00001813 );
Vincent Lejeune12140452013-07-19 21:45:06 +00001814}
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001815
Vincent Lejeune12140452013-07-19 21:45:06 +00001816MachineBasicBlock *
1817AMDGPUCFGStructurizer::findNearestCommonPostDom(MachineBasicBlock *MBB1,
1818 MachineBasicBlock *MBB2) {
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001819
Vincent Lejeune12140452013-07-19 21:45:06 +00001820 if (PDT->dominates(MBB1, MBB2))
1821 return MBB1;
1822 if (PDT->dominates(MBB2, MBB1))
1823 return MBB2;
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001824
Vincent Lejeune12140452013-07-19 21:45:06 +00001825 MachineDomTreeNode *Node1 = PDT->getNode(MBB1);
1826 MachineDomTreeNode *Node2 = PDT->getNode(MBB2);
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001827
1828 // Handle newly cloned node.
Vincent Lejeune12140452013-07-19 21:45:06 +00001829 if (!Node1 && MBB1->succ_size() == 1)
1830 return findNearestCommonPostDom(*MBB1->succ_begin(), MBB2);
1831 if (!Node2 && MBB2->succ_size() == 1)
1832 return findNearestCommonPostDom(MBB1, *MBB2->succ_begin());
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001833
Vincent Lejeune12140452013-07-19 21:45:06 +00001834 if (!Node1 || !Node2)
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001835 return NULL;
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001836
Vincent Lejeune12140452013-07-19 21:45:06 +00001837 Node1 = Node1->getIDom();
1838 while (Node1) {
1839 if (PDT->dominates(Node1, Node2))
1840 return Node1->getBlock();
1841 Node1 = Node1->getIDom();
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001842 }
1843
1844 return NULL;
1845}
1846
Vincent Lejeune12140452013-07-19 21:45:06 +00001847MachineBasicBlock *
1848AMDGPUCFGStructurizer::findNearestCommonPostDom(
1849 std::set<MachineBasicBlock *> &MBBs) {
1850 MachineBasicBlock *CommonDom;
1851 std::set<MachineBasicBlock *>::const_iterator It = MBBs.begin();
1852 std::set<MachineBasicBlock *>::const_iterator E = MBBs.end();
1853 for (CommonDom = *It; It != E && CommonDom; ++It) {
1854 MachineBasicBlock *MBB = *It;
1855 if (MBB != CommonDom)
1856 CommonDom = findNearestCommonPostDom(MBB, CommonDom);
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001857 }
1858
Vincent Lejeune9e8ba2b2013-07-19 21:44:56 +00001859 DEBUG(
1860 dbgs() << "Common post dominator for exit blocks is ";
Vincent Lejeune12140452013-07-19 21:45:06 +00001861 if (CommonDom)
1862 dbgs() << "BB" << CommonDom->getNumber() << "\n";
1863 else
Vincent Lejeune9e8ba2b2013-07-19 21:44:56 +00001864 dbgs() << "NULL\n";
Vincent Lejeune9e8ba2b2013-07-19 21:44:56 +00001865 );
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001866
Vincent Lejeune12140452013-07-19 21:45:06 +00001867 return CommonDom;
1868}
1869
1870char AMDGPUCFGStructurizer::ID = 0;
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001871
Benjamin Kramer879b0712013-05-23 15:43:05 +00001872} // end anonymous namespace
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001873
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001874
Benjamin Kramer879b0712013-05-23 15:43:05 +00001875FunctionPass *llvm::createAMDGPUCFGStructurizerPass(TargetMachine &tm) {
Vincent Lejeune12140452013-07-19 21:45:06 +00001876 return new AMDGPUCFGStructurizer(tm);
Tom Stellardf98f2ce2012-12-11 21:25:42 +00001877}