File: | lib/Target/AMDGPU/AMDILCFGStructurizer.cpp |
Location: | line 1736, column 12 |
Description: | Value stored to 'ImmReg' during its initialization is never read |
1 | //===-- 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 | |
11 | #include "AMDGPU.h" |
12 | #include "AMDGPUInstrInfo.h" |
13 | #include "AMDGPUSubtarget.h" |
14 | #include "R600InstrInfo.h" |
15 | #include "llvm/ADT/DepthFirstIterator.h" |
16 | #include "llvm/ADT/SCCIterator.h" |
17 | #include "llvm/ADT/SmallVector.h" |
18 | #include "llvm/ADT/Statistic.h" |
19 | #include "llvm/CodeGen/MachineDominators.h" |
20 | #include "llvm/CodeGen/MachineFunction.h" |
21 | #include "llvm/CodeGen/MachineFunctionAnalysis.h" |
22 | #include "llvm/CodeGen/MachineFunctionPass.h" |
23 | #include "llvm/CodeGen/MachineInstrBuilder.h" |
24 | #include "llvm/CodeGen/MachineJumpTableInfo.h" |
25 | #include "llvm/CodeGen/MachineLoopInfo.h" |
26 | #include "llvm/CodeGen/MachinePostDominators.h" |
27 | #include "llvm/CodeGen/MachineRegisterInfo.h" |
28 | #include "llvm/IR/Dominators.h" |
29 | #include "llvm/Support/Debug.h" |
30 | #include "llvm/Support/raw_ostream.h" |
31 | #include "llvm/Target/TargetInstrInfo.h" |
32 | #include "llvm/Target/TargetMachine.h" |
33 | #include <deque> |
34 | |
35 | using namespace llvm; |
36 | |
37 | #define DEBUG_TYPE"structcfg" "structcfg" |
38 | |
39 | #define DEFAULT_VEC_SLOTS8 8 |
40 | |
41 | // TODO: move-begin. |
42 | |
43 | //===----------------------------------------------------------------------===// |
44 | // |
45 | // Statistics for CFGStructurizer. |
46 | // |
47 | //===----------------------------------------------------------------------===// |
48 | |
49 | STATISTIC(numSerialPatternMatch, "CFGStructurizer number of serial pattern "static llvm::Statistic numSerialPatternMatch = { "structcfg", "CFGStructurizer number of serial pattern " "matched", 0, 0 } |
50 | "matched")static llvm::Statistic numSerialPatternMatch = { "structcfg", "CFGStructurizer number of serial pattern " "matched", 0, 0 }; |
51 | STATISTIC(numIfPatternMatch, "CFGStructurizer number of if pattern "static llvm::Statistic numIfPatternMatch = { "structcfg", "CFGStructurizer number of if pattern " "matched", 0, 0 } |
52 | "matched")static llvm::Statistic numIfPatternMatch = { "structcfg", "CFGStructurizer number of if pattern " "matched", 0, 0 }; |
53 | STATISTIC(numLoopcontPatternMatch, "CFGStructurizer number of loop-continue "static llvm::Statistic numLoopcontPatternMatch = { "structcfg" , "CFGStructurizer number of loop-continue " "pattern matched" , 0, 0 } |
54 | "pattern matched")static llvm::Statistic numLoopcontPatternMatch = { "structcfg" , "CFGStructurizer number of loop-continue " "pattern matched" , 0, 0 }; |
55 | STATISTIC(numClonedBlock, "CFGStructurizer cloned blocks")static llvm::Statistic numClonedBlock = { "structcfg", "CFGStructurizer cloned blocks" , 0, 0 }; |
56 | STATISTIC(numClonedInstr, "CFGStructurizer cloned instructions")static llvm::Statistic numClonedInstr = { "structcfg", "CFGStructurizer cloned instructions" , 0, 0 }; |
57 | |
58 | namespace llvm { |
59 | void initializeAMDGPUCFGStructurizerPass(PassRegistry&); |
60 | } |
61 | |
62 | //===----------------------------------------------------------------------===// |
63 | // |
64 | // Miscellaneous utility for CFGStructurizer. |
65 | // |
66 | //===----------------------------------------------------------------------===// |
67 | namespace { |
68 | #define SHOWNEWINSTR(i)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "New instr: " << *i << "\n"; } } while (0); \ |
69 | DEBUG(dbgs() << "New instr: " << *i << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "New instr: " << *i << "\n"; } } while (0); |
70 | |
71 | #define SHOWNEWBLK(b, msg)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << msg << "BB" << b ->getNumber() << "size " << b->size(); dbgs () << "\n";; } } while (0); \do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << msg << "BB" << b ->getNumber() << "size " << b->size(); dbgs () << "\n";; } } while (0) |
72 | DEBUG( \do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << msg << "BB" << b ->getNumber() << "size " << b->size(); dbgs () << "\n";; } } while (0) |
73 | dbgs() << msg << "BB" << b->getNumber() << "size " << b->size(); \do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << msg << "BB" << b ->getNumber() << "size " << b->size(); dbgs () << "\n";; } } while (0) |
74 | dbgs() << "\n"; \do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << msg << "BB" << b ->getNumber() << "size " << b->size(); dbgs () << "\n";; } } while (0) |
75 | )do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << msg << "BB" << b ->getNumber() << "size " << b->size(); dbgs () << "\n";; } } while (0); |
76 | |
77 | #define SHOWBLK_DETAIL(b, msg)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { if (b) { dbgs() << msg << "BB" << b->getNumber() << "size " << b->size(); b-> print(dbgs()); dbgs() << "\n"; }; } } while (0); \do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { if (b) { dbgs() << msg << "BB" << b->getNumber() << "size " << b->size(); b-> print(dbgs()); dbgs() << "\n"; }; } } while (0) |
78 | DEBUG( \do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { if (b) { dbgs() << msg << "BB" << b->getNumber() << "size " << b->size(); b-> print(dbgs()); dbgs() << "\n"; }; } } while (0) |
79 | if (b) { \do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { if (b) { dbgs() << msg << "BB" << b->getNumber() << "size " << b->size(); b-> print(dbgs()); dbgs() << "\n"; }; } } while (0) |
80 | dbgs() << msg << "BB" << b->getNumber() << "size " << b->size(); \do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { if (b) { dbgs() << msg << "BB" << b->getNumber() << "size " << b->size(); b-> print(dbgs()); dbgs() << "\n"; }; } } while (0) |
81 | b->print(dbgs()); \do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { if (b) { dbgs() << msg << "BB" << b->getNumber() << "size " << b->size(); b-> print(dbgs()); dbgs() << "\n"; }; } } while (0) |
82 | dbgs() << "\n"; \do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { if (b) { dbgs() << msg << "BB" << b->getNumber() << "size " << b->size(); b-> print(dbgs()); dbgs() << "\n"; }; } } while (0) |
83 | } \do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { if (b) { dbgs() << msg << "BB" << b->getNumber() << "size " << b->size(); b-> print(dbgs()); dbgs() << "\n"; }; } } while (0) |
84 | )do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { if (b) { dbgs() << msg << "BB" << b->getNumber() << "size " << b->size(); b-> print(dbgs()); dbgs() << "\n"; }; } } while (0); |
85 | |
86 | #define INVALIDSCCNUM-1 -1 |
87 | |
88 | template<class NodeT> |
89 | void ReverseVector(SmallVectorImpl<NodeT *> &Src) { |
90 | size_t sz = Src.size(); |
91 | for (size_t i = 0; i < sz/2; ++i) { |
92 | NodeT *t = Src[i]; |
93 | Src[i] = Src[sz - i - 1]; |
94 | Src[sz - i - 1] = t; |
95 | } |
96 | } |
97 | |
98 | } // end anonymous namespace |
99 | |
100 | //===----------------------------------------------------------------------===// |
101 | // |
102 | // supporting data structure for CFGStructurizer |
103 | // |
104 | //===----------------------------------------------------------------------===// |
105 | |
106 | |
107 | namespace { |
108 | |
109 | class BlockInformation { |
110 | public: |
111 | bool IsRetired; |
112 | int SccNum; |
113 | BlockInformation() : IsRetired(false), SccNum(INVALIDSCCNUM-1) {} |
114 | }; |
115 | |
116 | } // end anonymous namespace |
117 | |
118 | //===----------------------------------------------------------------------===// |
119 | // |
120 | // CFGStructurizer |
121 | // |
122 | //===----------------------------------------------------------------------===// |
123 | |
124 | namespace { |
125 | class AMDGPUCFGStructurizer : public MachineFunctionPass { |
126 | public: |
127 | typedef SmallVector<MachineBasicBlock *, 32> MBBVector; |
128 | typedef std::map<MachineBasicBlock *, BlockInformation *> MBBInfoMap; |
129 | typedef std::map<MachineLoop *, MachineBasicBlock *> LoopLandInfoMap; |
130 | |
131 | enum PathToKind { |
132 | Not_SinglePath = 0, |
133 | SinglePath_InPath = 1, |
134 | SinglePath_NotInPath = 2 |
135 | }; |
136 | |
137 | static char ID; |
138 | |
139 | AMDGPUCFGStructurizer() : |
140 | MachineFunctionPass(ID), TII(nullptr), TRI(nullptr) { |
141 | initializeAMDGPUCFGStructurizerPass(*PassRegistry::getPassRegistry()); |
142 | } |
143 | |
144 | const char *getPassName() const override { |
145 | return "AMDGPU Control Flow Graph structurizer Pass"; |
146 | } |
147 | |
148 | void getAnalysisUsage(AnalysisUsage &AU) const override { |
149 | AU.addPreserved<MachineFunctionAnalysis>(); |
150 | AU.addRequired<MachineFunctionAnalysis>(); |
151 | AU.addRequired<MachineDominatorTree>(); |
152 | AU.addRequired<MachinePostDominatorTree>(); |
153 | AU.addRequired<MachineLoopInfo>(); |
154 | } |
155 | |
156 | /// Perform the CFG structurization |
157 | bool run(); |
158 | |
159 | /// Perform the CFG preparation |
160 | /// This step will remove every unconditionnal/dead jump instructions and make |
161 | /// sure all loops have an exit block |
162 | bool prepare(); |
163 | |
164 | bool runOnMachineFunction(MachineFunction &MF) override { |
165 | TII = static_cast<const R600InstrInfo *>(MF.getSubtarget().getInstrInfo()); |
166 | TRI = &TII->getRegisterInfo(); |
167 | DEBUG(MF.dump();)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { MF.dump();; } } while (0); |
168 | OrderedBlks.clear(); |
169 | Visited.clear(); |
170 | FuncRep = &MF; |
171 | MLI = &getAnalysis<MachineLoopInfo>(); |
172 | DEBUG(dbgs() << "LoopInfo:\n"; PrintLoopinfo(*MLI);)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "LoopInfo:\n"; PrintLoopinfo (*MLI);; } } while (0); |
173 | MDT = &getAnalysis<MachineDominatorTree>(); |
174 | DEBUG(MDT->print(dbgs(), (const llvm::Module*)nullptr);)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { MDT->print(dbgs(), (const llvm::Module*)nullptr );; } } while (0); |
175 | PDT = &getAnalysis<MachinePostDominatorTree>(); |
176 | DEBUG(PDT->print(dbgs());)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { PDT->print(dbgs());; } } while (0); |
177 | prepare(); |
178 | run(); |
179 | DEBUG(MF.dump();)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { MF.dump();; } } while (0); |
180 | return true; |
181 | } |
182 | |
183 | protected: |
184 | MachineDominatorTree *MDT; |
185 | MachinePostDominatorTree *PDT; |
186 | MachineLoopInfo *MLI; |
187 | const R600InstrInfo *TII; |
188 | const AMDGPURegisterInfo *TRI; |
189 | |
190 | // PRINT FUNCTIONS |
191 | /// Print the ordered Blocks. |
192 | void printOrderedBlocks() const { |
193 | size_t i = 0; |
194 | for (MBBVector::const_iterator iterBlk = OrderedBlks.begin(), |
195 | iterBlkEnd = OrderedBlks.end(); iterBlk != iterBlkEnd; ++iterBlk, ++i) { |
196 | dbgs() << "BB" << (*iterBlk)->getNumber(); |
197 | dbgs() << "(" << getSCCNum(*iterBlk) << "," << (*iterBlk)->size() << ")"; |
198 | if (i != 0 && i % 10 == 0) { |
199 | dbgs() << "\n"; |
200 | } else { |
201 | dbgs() << " "; |
202 | } |
203 | } |
204 | } |
205 | static void PrintLoopinfo(const MachineLoopInfo &LoopInfo) { |
206 | for (MachineLoop::iterator iter = LoopInfo.begin(), |
207 | iterEnd = LoopInfo.end(); iter != iterEnd; ++iter) { |
208 | (*iter)->print(dbgs(), 0); |
209 | } |
210 | } |
211 | |
212 | // UTILITY FUNCTIONS |
213 | int getSCCNum(MachineBasicBlock *MBB) const; |
214 | MachineBasicBlock *getLoopLandInfo(MachineLoop *LoopRep) const; |
215 | bool hasBackEdge(MachineBasicBlock *MBB) const; |
216 | static unsigned getLoopDepth(MachineLoop *LoopRep); |
217 | bool isRetiredBlock(MachineBasicBlock *MBB) const; |
218 | bool isActiveLoophead(MachineBasicBlock *MBB) const; |
219 | PathToKind singlePathTo(MachineBasicBlock *SrcMBB, MachineBasicBlock *DstMBB, |
220 | bool AllowSideEntry = true) const; |
221 | int countActiveBlock(MBBVector::const_iterator It, |
222 | MBBVector::const_iterator E) const; |
223 | bool needMigrateBlock(MachineBasicBlock *MBB) const; |
224 | |
225 | // Utility Functions |
226 | void reversePredicateSetter(MachineBasicBlock::iterator I); |
227 | /// Compute the reversed DFS post order of Blocks |
228 | void orderBlocks(MachineFunction *MF); |
229 | |
230 | // Function originally from CFGStructTraits |
231 | void insertInstrEnd(MachineBasicBlock *MBB, int NewOpcode, |
232 | DebugLoc DL = DebugLoc()); |
233 | MachineInstr *insertInstrBefore(MachineBasicBlock *MBB, int NewOpcode, |
234 | DebugLoc DL = DebugLoc()); |
235 | MachineInstr *insertInstrBefore(MachineBasicBlock::iterator I, int NewOpcode); |
236 | void insertCondBranchBefore(MachineBasicBlock::iterator I, int NewOpcode, |
237 | DebugLoc DL); |
238 | void insertCondBranchBefore(MachineBasicBlock *MBB, |
239 | MachineBasicBlock::iterator I, int NewOpcode, int RegNum, |
240 | DebugLoc DL); |
241 | void insertCondBranchEnd(MachineBasicBlock *MBB, int NewOpcode, int RegNum); |
242 | static int getBranchNzeroOpcode(int OldOpcode); |
243 | static int getBranchZeroOpcode(int OldOpcode); |
244 | static int getContinueNzeroOpcode(int OldOpcode); |
245 | static int getContinueZeroOpcode(int OldOpcode); |
246 | static MachineBasicBlock *getTrueBranch(MachineInstr *MI); |
247 | static void setTrueBranch(MachineInstr *MI, MachineBasicBlock *MBB); |
248 | static MachineBasicBlock *getFalseBranch(MachineBasicBlock *MBB, |
249 | MachineInstr *MI); |
250 | static bool isCondBranch(MachineInstr *MI); |
251 | static bool isUncondBranch(MachineInstr *MI); |
252 | static DebugLoc getLastDebugLocInBB(MachineBasicBlock *MBB); |
253 | static MachineInstr *getNormalBlockBranchInstr(MachineBasicBlock *MBB); |
254 | /// The correct naming for this is getPossibleLoopendBlockBranchInstr. |
255 | /// |
256 | /// BB with backward-edge could have move instructions after the branch |
257 | /// instruction. Such move instruction "belong to" the loop backward-edge. |
258 | MachineInstr *getLoopendBlockBranchInstr(MachineBasicBlock *MBB); |
259 | static MachineInstr *getReturnInstr(MachineBasicBlock *MBB); |
260 | static MachineInstr *getContinueInstr(MachineBasicBlock *MBB); |
261 | static bool isReturnBlock(MachineBasicBlock *MBB); |
262 | static void cloneSuccessorList(MachineBasicBlock *DstMBB, |
263 | MachineBasicBlock *SrcMBB) ; |
264 | static MachineBasicBlock *clone(MachineBasicBlock *MBB); |
265 | /// MachineBasicBlock::ReplaceUsesOfBlockWith doesn't serve the purpose |
266 | /// because the AMDGPU instruction is not recognized as terminator fix this |
267 | /// and retire this routine |
268 | void replaceInstrUseOfBlockWith(MachineBasicBlock *SrcMBB, |
269 | MachineBasicBlock *OldMBB, MachineBasicBlock *NewBlk); |
270 | static void wrapup(MachineBasicBlock *MBB); |
271 | |
272 | |
273 | int patternMatch(MachineBasicBlock *MBB); |
274 | int patternMatchGroup(MachineBasicBlock *MBB); |
275 | int serialPatternMatch(MachineBasicBlock *MBB); |
276 | int ifPatternMatch(MachineBasicBlock *MBB); |
277 | int loopendPatternMatch(); |
278 | int mergeLoop(MachineLoop *LoopRep); |
279 | int loopcontPatternMatch(MachineLoop *LoopRep, MachineBasicBlock *LoopHeader); |
280 | |
281 | void handleLoopcontBlock(MachineBasicBlock *ContingMBB, |
282 | MachineLoop *ContingLoop, MachineBasicBlock *ContMBB, |
283 | MachineLoop *ContLoop); |
284 | /// return true iff src1Blk->succ_size() == 0 && src1Blk and src2Blk are in |
285 | /// the same loop with LoopLandInfo without explicitly keeping track of |
286 | /// loopContBlks and loopBreakBlks, this is a method to get the information. |
287 | bool isSameloopDetachedContbreak(MachineBasicBlock *Src1MBB, |
288 | MachineBasicBlock *Src2MBB); |
289 | int handleJumpintoIf(MachineBasicBlock *HeadMBB, |
290 | MachineBasicBlock *TrueMBB, MachineBasicBlock *FalseMBB); |
291 | int handleJumpintoIfImp(MachineBasicBlock *HeadMBB, |
292 | MachineBasicBlock *TrueMBB, MachineBasicBlock *FalseMBB); |
293 | int improveSimpleJumpintoIf(MachineBasicBlock *HeadMBB, |
294 | MachineBasicBlock *TrueMBB, MachineBasicBlock *FalseMBB, |
295 | MachineBasicBlock **LandMBBPtr); |
296 | void showImproveSimpleJumpintoIf(MachineBasicBlock *HeadMBB, |
297 | MachineBasicBlock *TrueMBB, MachineBasicBlock *FalseMBB, |
298 | MachineBasicBlock *LandMBB, bool Detail = false); |
299 | int cloneOnSideEntryTo(MachineBasicBlock *PreMBB, |
300 | MachineBasicBlock *SrcMBB, MachineBasicBlock *DstMBB); |
301 | void mergeSerialBlock(MachineBasicBlock *DstMBB, |
302 | MachineBasicBlock *SrcMBB); |
303 | |
304 | void mergeIfthenelseBlock(MachineInstr *BranchMI, |
305 | MachineBasicBlock *MBB, MachineBasicBlock *TrueMBB, |
306 | MachineBasicBlock *FalseMBB, MachineBasicBlock *LandMBB); |
307 | void mergeLooplandBlock(MachineBasicBlock *DstMBB, |
308 | MachineBasicBlock *LandMBB); |
309 | void mergeLoopbreakBlock(MachineBasicBlock *ExitingMBB, |
310 | MachineBasicBlock *LandMBB); |
311 | void settleLoopcontBlock(MachineBasicBlock *ContingMBB, |
312 | MachineBasicBlock *ContMBB); |
313 | /// normalizeInfiniteLoopExit change |
314 | /// B1: |
315 | /// uncond_br LoopHeader |
316 | /// |
317 | /// to |
318 | /// B1: |
319 | /// cond_br 1 LoopHeader dummyExit |
320 | /// and return the newly added dummy exit block |
321 | MachineBasicBlock *normalizeInfiniteLoopExit(MachineLoop *LoopRep); |
322 | void removeUnconditionalBranch(MachineBasicBlock *MBB); |
323 | /// Remove duplicate branches instructions in a block. |
324 | /// For instance |
325 | /// B0: |
326 | /// cond_br X B1 B2 |
327 | /// cond_br X B1 B2 |
328 | /// is transformed to |
329 | /// B0: |
330 | /// cond_br X B1 B2 |
331 | void removeRedundantConditionalBranch(MachineBasicBlock *MBB); |
332 | void addDummyExitBlock(SmallVectorImpl<MachineBasicBlock *> &RetMBB); |
333 | void removeSuccessor(MachineBasicBlock *MBB); |
334 | MachineBasicBlock *cloneBlockForPredecessor(MachineBasicBlock *MBB, |
335 | MachineBasicBlock *PredMBB); |
336 | void migrateInstruction(MachineBasicBlock *SrcMBB, |
337 | MachineBasicBlock *DstMBB, MachineBasicBlock::iterator I); |
338 | void recordSccnum(MachineBasicBlock *MBB, int SCCNum); |
339 | void retireBlock(MachineBasicBlock *MBB); |
340 | void setLoopLandBlock(MachineLoop *LoopRep, MachineBasicBlock *MBB = nullptr); |
341 | |
342 | MachineBasicBlock *findNearestCommonPostDom(std::set<MachineBasicBlock *>&); |
343 | /// This is work around solution for findNearestCommonDominator not available |
344 | /// to post dom a proper fix should go to Dominators.h. |
345 | MachineBasicBlock *findNearestCommonPostDom(MachineBasicBlock *MBB1, |
346 | MachineBasicBlock *MBB2); |
347 | |
348 | private: |
349 | MBBInfoMap BlockInfoMap; |
350 | LoopLandInfoMap LLInfoMap; |
351 | std::map<MachineLoop *, bool> Visited; |
352 | MachineFunction *FuncRep; |
353 | SmallVector<MachineBasicBlock *, DEFAULT_VEC_SLOTS8> OrderedBlks; |
354 | }; |
355 | |
356 | int AMDGPUCFGStructurizer::getSCCNum(MachineBasicBlock *MBB) const { |
357 | MBBInfoMap::const_iterator It = BlockInfoMap.find(MBB); |
358 | if (It == BlockInfoMap.end()) |
359 | return INVALIDSCCNUM-1; |
360 | return (*It).second->SccNum; |
361 | } |
362 | |
363 | MachineBasicBlock *AMDGPUCFGStructurizer::getLoopLandInfo(MachineLoop *LoopRep) |
364 | const { |
365 | LoopLandInfoMap::const_iterator It = LLInfoMap.find(LoopRep); |
366 | if (It == LLInfoMap.end()) |
367 | return nullptr; |
368 | return (*It).second; |
369 | } |
370 | |
371 | bool AMDGPUCFGStructurizer::hasBackEdge(MachineBasicBlock *MBB) const { |
372 | MachineLoop *LoopRep = MLI->getLoopFor(MBB); |
373 | if (!LoopRep) |
374 | return false; |
375 | MachineBasicBlock *LoopHeader = LoopRep->getHeader(); |
376 | return MBB->isSuccessor(LoopHeader); |
377 | } |
378 | |
379 | unsigned AMDGPUCFGStructurizer::getLoopDepth(MachineLoop *LoopRep) { |
380 | return LoopRep ? LoopRep->getLoopDepth() : 0; |
381 | } |
382 | |
383 | bool AMDGPUCFGStructurizer::isRetiredBlock(MachineBasicBlock *MBB) const { |
384 | MBBInfoMap::const_iterator It = BlockInfoMap.find(MBB); |
385 | if (It == BlockInfoMap.end()) |
386 | return false; |
387 | return (*It).second->IsRetired; |
388 | } |
389 | |
390 | bool AMDGPUCFGStructurizer::isActiveLoophead(MachineBasicBlock *MBB) const { |
391 | MachineLoop *LoopRep = MLI->getLoopFor(MBB); |
392 | while (LoopRep && LoopRep->getHeader() == MBB) { |
393 | MachineBasicBlock *LoopLand = getLoopLandInfo(LoopRep); |
394 | if(!LoopLand) |
395 | return true; |
396 | if (!isRetiredBlock(LoopLand)) |
397 | return true; |
398 | LoopRep = LoopRep->getParentLoop(); |
399 | } |
400 | return false; |
401 | } |
402 | AMDGPUCFGStructurizer::PathToKind AMDGPUCFGStructurizer::singlePathTo( |
403 | MachineBasicBlock *SrcMBB, MachineBasicBlock *DstMBB, |
404 | bool AllowSideEntry) const { |
405 | assert(DstMBB)((DstMBB) ? static_cast<void> (0) : __assert_fail ("DstMBB" , "/tmp/buildd/llvm-toolchain-snapshot-3.7~svn240924/lib/Target/AMDGPU/AMDILCFGStructurizer.cpp" , 405, __PRETTY_FUNCTION__)); |
406 | if (SrcMBB == DstMBB) |
407 | return SinglePath_InPath; |
408 | while (SrcMBB && SrcMBB->succ_size() == 1) { |
409 | SrcMBB = *SrcMBB->succ_begin(); |
410 | if (SrcMBB == DstMBB) |
411 | return SinglePath_InPath; |
412 | if (!AllowSideEntry && SrcMBB->pred_size() > 1) |
413 | return Not_SinglePath; |
414 | } |
415 | if (SrcMBB && SrcMBB->succ_size()==0) |
416 | return SinglePath_NotInPath; |
417 | return Not_SinglePath; |
418 | } |
419 | |
420 | int AMDGPUCFGStructurizer::countActiveBlock(MBBVector::const_iterator It, |
421 | MBBVector::const_iterator E) const { |
422 | int Count = 0; |
423 | while (It != E) { |
424 | if (!isRetiredBlock(*It)) |
425 | ++Count; |
426 | ++It; |
427 | } |
428 | return Count; |
429 | } |
430 | |
431 | bool AMDGPUCFGStructurizer::needMigrateBlock(MachineBasicBlock *MBB) const { |
432 | unsigned BlockSizeThreshold = 30; |
433 | unsigned CloneInstrThreshold = 100; |
434 | bool MultiplePreds = MBB && (MBB->pred_size() > 1); |
435 | |
436 | if(!MultiplePreds) |
437 | return false; |
438 | unsigned BlkSize = MBB->size(); |
439 | return ((BlkSize > BlockSizeThreshold) && |
440 | (BlkSize * (MBB->pred_size() - 1) > CloneInstrThreshold)); |
441 | } |
442 | |
443 | void AMDGPUCFGStructurizer::reversePredicateSetter( |
444 | MachineBasicBlock::iterator I) { |
445 | while (I--) { |
446 | if (I->getOpcode() == AMDGPU::PRED_X) { |
447 | switch (static_cast<MachineInstr *>(I)->getOperand(2).getImm()) { |
448 | case OPCODE_IS_ZERO_INTAMDGPU::PRED_SETE_INT: |
449 | static_cast<MachineInstr *>(I)->getOperand(2) |
450 | .setImm(OPCODE_IS_NOT_ZERO_INTAMDGPU::PRED_SETNE_INT); |
451 | return; |
452 | case OPCODE_IS_NOT_ZERO_INTAMDGPU::PRED_SETNE_INT: |
453 | static_cast<MachineInstr *>(I)->getOperand(2) |
454 | .setImm(OPCODE_IS_ZERO_INTAMDGPU::PRED_SETE_INT); |
455 | return; |
456 | case OPCODE_IS_ZEROAMDGPU::PRED_SETE: |
457 | static_cast<MachineInstr *>(I)->getOperand(2) |
458 | .setImm(OPCODE_IS_NOT_ZEROAMDGPU::PRED_SETNE); |
459 | return; |
460 | case OPCODE_IS_NOT_ZEROAMDGPU::PRED_SETNE: |
461 | static_cast<MachineInstr *>(I)->getOperand(2) |
462 | .setImm(OPCODE_IS_ZEROAMDGPU::PRED_SETE); |
463 | return; |
464 | default: |
465 | llvm_unreachable("PRED_X Opcode invalid!")::llvm::llvm_unreachable_internal("PRED_X Opcode invalid!", "/tmp/buildd/llvm-toolchain-snapshot-3.7~svn240924/lib/Target/AMDGPU/AMDILCFGStructurizer.cpp" , 465); |
466 | } |
467 | } |
468 | } |
469 | } |
470 | |
471 | void AMDGPUCFGStructurizer::insertInstrEnd(MachineBasicBlock *MBB, |
472 | int NewOpcode, DebugLoc DL) { |
473 | MachineInstr *MI = MBB->getParent() |
474 | ->CreateMachineInstr(TII->get(NewOpcode), DL); |
475 | MBB->push_back(MI); |
476 | //assume the instruction doesn't take any reg operand ... |
477 | SHOWNEWINSTR(MI)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "New instr: " << *MI << "\n"; } } while (0);; |
478 | } |
479 | |
480 | MachineInstr *AMDGPUCFGStructurizer::insertInstrBefore(MachineBasicBlock *MBB, |
481 | int NewOpcode, DebugLoc DL) { |
482 | MachineInstr *MI = |
483 | MBB->getParent()->CreateMachineInstr(TII->get(NewOpcode), DL); |
484 | if (MBB->begin() != MBB->end()) |
485 | MBB->insert(MBB->begin(), MI); |
486 | else |
487 | MBB->push_back(MI); |
488 | SHOWNEWINSTR(MI)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "New instr: " << *MI << "\n"; } } while (0);; |
489 | return MI; |
490 | } |
491 | |
492 | MachineInstr *AMDGPUCFGStructurizer::insertInstrBefore( |
493 | MachineBasicBlock::iterator I, int NewOpcode) { |
494 | MachineInstr *OldMI = &(*I); |
495 | MachineBasicBlock *MBB = OldMI->getParent(); |
496 | MachineInstr *NewMBB = |
497 | MBB->getParent()->CreateMachineInstr(TII->get(NewOpcode), DebugLoc()); |
498 | MBB->insert(I, NewMBB); |
499 | //assume the instruction doesn't take any reg operand ... |
500 | SHOWNEWINSTR(NewMBB)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "New instr: " << *NewMBB << "\n"; } } while (0);; |
501 | return NewMBB; |
502 | } |
503 | |
504 | void AMDGPUCFGStructurizer::insertCondBranchBefore( |
505 | MachineBasicBlock::iterator I, int NewOpcode, DebugLoc DL) { |
506 | MachineInstr *OldMI = &(*I); |
507 | MachineBasicBlock *MBB = OldMI->getParent(); |
508 | MachineFunction *MF = MBB->getParent(); |
509 | MachineInstr *NewMI = MF->CreateMachineInstr(TII->get(NewOpcode), DL); |
510 | MBB->insert(I, NewMI); |
511 | MachineInstrBuilder MIB(*MF, NewMI); |
512 | MIB.addReg(OldMI->getOperand(1).getReg(), false); |
513 | SHOWNEWINSTR(NewMI)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "New instr: " << *NewMI << "\n"; } } while (0);; |
514 | //erase later oldInstr->eraseFromParent(); |
515 | } |
516 | |
517 | void AMDGPUCFGStructurizer::insertCondBranchBefore(MachineBasicBlock *blk, |
518 | MachineBasicBlock::iterator I, int NewOpcode, int RegNum, |
519 | DebugLoc DL) { |
520 | MachineFunction *MF = blk->getParent(); |
521 | MachineInstr *NewInstr = MF->CreateMachineInstr(TII->get(NewOpcode), DL); |
522 | //insert before |
523 | blk->insert(I, NewInstr); |
524 | MachineInstrBuilder(*MF, NewInstr).addReg(RegNum, false); |
525 | SHOWNEWINSTR(NewInstr)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "New instr: " << *NewInstr << "\n"; } } while (0);; |
526 | } |
527 | |
528 | void AMDGPUCFGStructurizer::insertCondBranchEnd(MachineBasicBlock *MBB, |
529 | int NewOpcode, int RegNum) { |
530 | MachineFunction *MF = MBB->getParent(); |
531 | MachineInstr *NewInstr = |
532 | MF->CreateMachineInstr(TII->get(NewOpcode), DebugLoc()); |
533 | MBB->push_back(NewInstr); |
534 | MachineInstrBuilder(*MF, NewInstr).addReg(RegNum, false); |
535 | SHOWNEWINSTR(NewInstr)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "New instr: " << *NewInstr << "\n"; } } while (0);; |
536 | } |
537 | |
538 | int AMDGPUCFGStructurizer::getBranchNzeroOpcode(int OldOpcode) { |
539 | switch(OldOpcode) { |
540 | case AMDGPU::JUMP_COND: |
541 | case AMDGPU::JUMP: return AMDGPU::IF_PREDICATE_SET; |
542 | case AMDGPU::BRANCH_COND_i32: |
543 | case AMDGPU::BRANCH_COND_f32: return AMDGPU::IF_LOGICALNZ_f32; |
544 | default: llvm_unreachable("internal error")::llvm::llvm_unreachable_internal("internal error", "/tmp/buildd/llvm-toolchain-snapshot-3.7~svn240924/lib/Target/AMDGPU/AMDILCFGStructurizer.cpp" , 544); |
545 | } |
546 | return -1; |
547 | } |
548 | |
549 | int AMDGPUCFGStructurizer::getBranchZeroOpcode(int OldOpcode) { |
550 | switch(OldOpcode) { |
551 | case AMDGPU::JUMP_COND: |
552 | case AMDGPU::JUMP: return AMDGPU::IF_PREDICATE_SET; |
553 | case AMDGPU::BRANCH_COND_i32: |
554 | case AMDGPU::BRANCH_COND_f32: return AMDGPU::IF_LOGICALZ_f32; |
555 | default: llvm_unreachable("internal error")::llvm::llvm_unreachable_internal("internal error", "/tmp/buildd/llvm-toolchain-snapshot-3.7~svn240924/lib/Target/AMDGPU/AMDILCFGStructurizer.cpp" , 555); |
556 | } |
557 | return -1; |
558 | } |
559 | |
560 | int AMDGPUCFGStructurizer::getContinueNzeroOpcode(int OldOpcode) { |
561 | switch(OldOpcode) { |
562 | case AMDGPU::JUMP_COND: |
563 | case AMDGPU::JUMP: return AMDGPU::CONTINUE_LOGICALNZ_i32; |
564 | default: llvm_unreachable("internal error")::llvm::llvm_unreachable_internal("internal error", "/tmp/buildd/llvm-toolchain-snapshot-3.7~svn240924/lib/Target/AMDGPU/AMDILCFGStructurizer.cpp" , 564); |
565 | }; |
566 | return -1; |
567 | } |
568 | |
569 | int AMDGPUCFGStructurizer::getContinueZeroOpcode(int OldOpcode) { |
570 | switch(OldOpcode) { |
571 | case AMDGPU::JUMP_COND: |
572 | case AMDGPU::JUMP: return AMDGPU::CONTINUE_LOGICALZ_i32; |
573 | default: llvm_unreachable("internal error")::llvm::llvm_unreachable_internal("internal error", "/tmp/buildd/llvm-toolchain-snapshot-3.7~svn240924/lib/Target/AMDGPU/AMDILCFGStructurizer.cpp" , 573); |
574 | } |
575 | return -1; |
576 | } |
577 | |
578 | MachineBasicBlock *AMDGPUCFGStructurizer::getTrueBranch(MachineInstr *MI) { |
579 | return MI->getOperand(0).getMBB(); |
580 | } |
581 | |
582 | void AMDGPUCFGStructurizer::setTrueBranch(MachineInstr *MI, |
583 | MachineBasicBlock *MBB) { |
584 | MI->getOperand(0).setMBB(MBB); |
585 | } |
586 | |
587 | MachineBasicBlock * |
588 | AMDGPUCFGStructurizer::getFalseBranch(MachineBasicBlock *MBB, |
589 | MachineInstr *MI) { |
590 | assert(MBB->succ_size() == 2)((MBB->succ_size() == 2) ? static_cast<void> (0) : __assert_fail ("MBB->succ_size() == 2", "/tmp/buildd/llvm-toolchain-snapshot-3.7~svn240924/lib/Target/AMDGPU/AMDILCFGStructurizer.cpp" , 590, __PRETTY_FUNCTION__)); |
591 | MachineBasicBlock *TrueBranch = getTrueBranch(MI); |
592 | MachineBasicBlock::succ_iterator It = MBB->succ_begin(); |
593 | MachineBasicBlock::succ_iterator Next = It; |
594 | ++Next; |
595 | return (*It == TrueBranch) ? *Next : *It; |
596 | } |
597 | |
598 | bool AMDGPUCFGStructurizer::isCondBranch(MachineInstr *MI) { |
599 | switch (MI->getOpcode()) { |
600 | case AMDGPU::JUMP_COND: |
601 | case AMDGPU::BRANCH_COND_i32: |
602 | case AMDGPU::BRANCH_COND_f32: return true; |
603 | default: |
604 | return false; |
605 | } |
606 | return false; |
607 | } |
608 | |
609 | bool AMDGPUCFGStructurizer::isUncondBranch(MachineInstr *MI) { |
610 | switch (MI->getOpcode()) { |
611 | case AMDGPU::JUMP: |
612 | case AMDGPU::BRANCH: |
613 | return true; |
614 | default: |
615 | return false; |
616 | } |
617 | return false; |
618 | } |
619 | |
620 | DebugLoc AMDGPUCFGStructurizer::getLastDebugLocInBB(MachineBasicBlock *MBB) { |
621 | //get DebugLoc from the first MachineBasicBlock instruction with debug info |
622 | DebugLoc DL; |
623 | for (MachineBasicBlock::iterator It = MBB->begin(); It != MBB->end(); |
624 | ++It) { |
625 | MachineInstr *instr = &(*It); |
626 | if (instr->getDebugLoc()) |
627 | DL = instr->getDebugLoc(); |
628 | } |
629 | return DL; |
630 | } |
631 | |
632 | MachineInstr *AMDGPUCFGStructurizer::getNormalBlockBranchInstr( |
633 | MachineBasicBlock *MBB) { |
634 | MachineBasicBlock::reverse_iterator It = MBB->rbegin(); |
635 | MachineInstr *MI = &*It; |
636 | if (MI && (isCondBranch(MI) || isUncondBranch(MI))) |
637 | return MI; |
638 | return nullptr; |
639 | } |
640 | |
641 | MachineInstr *AMDGPUCFGStructurizer::getLoopendBlockBranchInstr( |
642 | MachineBasicBlock *MBB) { |
643 | for (MachineBasicBlock::reverse_iterator It = MBB->rbegin(), E = MBB->rend(); |
644 | It != E; ++It) { |
645 | // FIXME: Simplify |
646 | MachineInstr *MI = &*It; |
647 | if (MI) { |
648 | if (isCondBranch(MI) || isUncondBranch(MI)) |
649 | return MI; |
650 | else if (!TII->isMov(MI->getOpcode())) |
651 | break; |
652 | } |
653 | } |
654 | return nullptr; |
655 | } |
656 | |
657 | MachineInstr *AMDGPUCFGStructurizer::getReturnInstr(MachineBasicBlock *MBB) { |
658 | MachineBasicBlock::reverse_iterator It = MBB->rbegin(); |
659 | if (It != MBB->rend()) { |
660 | MachineInstr *instr = &(*It); |
661 | if (instr->getOpcode() == AMDGPU::RETURN) |
662 | return instr; |
663 | } |
664 | return nullptr; |
665 | } |
666 | |
667 | MachineInstr *AMDGPUCFGStructurizer::getContinueInstr(MachineBasicBlock *MBB) { |
668 | MachineBasicBlock::reverse_iterator It = MBB->rbegin(); |
669 | if (It != MBB->rend()) { |
670 | MachineInstr *MI = &(*It); |
671 | if (MI->getOpcode() == AMDGPU::CONTINUE) |
672 | return MI; |
673 | } |
674 | return nullptr; |
675 | } |
676 | |
677 | bool AMDGPUCFGStructurizer::isReturnBlock(MachineBasicBlock *MBB) { |
678 | MachineInstr *MI = getReturnInstr(MBB); |
679 | bool IsReturn = (MBB->succ_size() == 0); |
680 | if (MI) |
681 | assert(IsReturn)((IsReturn) ? static_cast<void> (0) : __assert_fail ("IsReturn" , "/tmp/buildd/llvm-toolchain-snapshot-3.7~svn240924/lib/Target/AMDGPU/AMDILCFGStructurizer.cpp" , 681, __PRETTY_FUNCTION__)); |
682 | else if (IsReturn) |
683 | DEBUG(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "BB" << MBB->getNumber () <<" is return block without RETURN instr\n";; } } while (0) |
684 | dbgs() << "BB" << MBB->getNumber()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "BB" << MBB->getNumber () <<" is return block without RETURN instr\n";; } } while (0) |
685 | <<" is return block without RETURN instr\n";)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "BB" << MBB->getNumber () <<" is return block without RETURN instr\n";; } } while (0); |
686 | return IsReturn; |
687 | } |
688 | |
689 | void AMDGPUCFGStructurizer::cloneSuccessorList(MachineBasicBlock *DstMBB, |
690 | MachineBasicBlock *SrcMBB) { |
691 | for (MachineBasicBlock::succ_iterator It = SrcMBB->succ_begin(), |
692 | iterEnd = SrcMBB->succ_end(); It != iterEnd; ++It) |
693 | DstMBB->addSuccessor(*It); // *iter's predecessor is also taken care of |
694 | } |
695 | |
696 | MachineBasicBlock *AMDGPUCFGStructurizer::clone(MachineBasicBlock *MBB) { |
697 | MachineFunction *Func = MBB->getParent(); |
698 | MachineBasicBlock *NewMBB = Func->CreateMachineBasicBlock(); |
699 | Func->push_back(NewMBB); //insert to function |
700 | for (MachineBasicBlock::iterator It = MBB->begin(), E = MBB->end(); |
701 | It != E; ++It) { |
702 | MachineInstr *MI = Func->CloneMachineInstr(It); |
703 | NewMBB->push_back(MI); |
704 | } |
705 | return NewMBB; |
706 | } |
707 | |
708 | void AMDGPUCFGStructurizer::replaceInstrUseOfBlockWith( |
709 | MachineBasicBlock *SrcMBB, MachineBasicBlock *OldMBB, |
710 | MachineBasicBlock *NewBlk) { |
711 | MachineInstr *BranchMI = getLoopendBlockBranchInstr(SrcMBB); |
712 | if (BranchMI && isCondBranch(BranchMI) && |
713 | getTrueBranch(BranchMI) == OldMBB) |
714 | setTrueBranch(BranchMI, NewBlk); |
715 | } |
716 | |
717 | void AMDGPUCFGStructurizer::wrapup(MachineBasicBlock *MBB) { |
718 | assert((!MBB->getParent()->getJumpTableInfo()(((!MBB->getParent()->getJumpTableInfo() || MBB->getParent ()->getJumpTableInfo()->isEmpty()) && "found a jump table" ) ? static_cast<void> (0) : __assert_fail ("(!MBB->getParent()->getJumpTableInfo() || MBB->getParent()->getJumpTableInfo()->isEmpty()) && \"found a jump table\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.7~svn240924/lib/Target/AMDGPU/AMDILCFGStructurizer.cpp" , 720, __PRETTY_FUNCTION__)) |
719 | || MBB->getParent()->getJumpTableInfo()->isEmpty())(((!MBB->getParent()->getJumpTableInfo() || MBB->getParent ()->getJumpTableInfo()->isEmpty()) && "found a jump table" ) ? static_cast<void> (0) : __assert_fail ("(!MBB->getParent()->getJumpTableInfo() || MBB->getParent()->getJumpTableInfo()->isEmpty()) && \"found a jump table\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.7~svn240924/lib/Target/AMDGPU/AMDILCFGStructurizer.cpp" , 720, __PRETTY_FUNCTION__)) |
720 | && "found a jump table")(((!MBB->getParent()->getJumpTableInfo() || MBB->getParent ()->getJumpTableInfo()->isEmpty()) && "found a jump table" ) ? static_cast<void> (0) : __assert_fail ("(!MBB->getParent()->getJumpTableInfo() || MBB->getParent()->getJumpTableInfo()->isEmpty()) && \"found a jump table\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.7~svn240924/lib/Target/AMDGPU/AMDILCFGStructurizer.cpp" , 720, __PRETTY_FUNCTION__)); |
721 | |
722 | //collect continue right before endloop |
723 | SmallVector<MachineInstr *, DEFAULT_VEC_SLOTS8> ContInstr; |
724 | MachineBasicBlock::iterator Pre = MBB->begin(); |
725 | MachineBasicBlock::iterator E = MBB->end(); |
726 | MachineBasicBlock::iterator It = Pre; |
727 | while (It != E) { |
728 | if (Pre->getOpcode() == AMDGPU::CONTINUE |
729 | && It->getOpcode() == AMDGPU::ENDLOOP) |
730 | ContInstr.push_back(Pre); |
731 | Pre = It; |
732 | ++It; |
733 | } |
734 | |
735 | //delete continue right before endloop |
736 | for (unsigned i = 0; i < ContInstr.size(); ++i) |
737 | ContInstr[i]->eraseFromParent(); |
738 | |
739 | // TODO to fix up jump table so later phase won't be confused. if |
740 | // (jumpTableInfo->isEmpty() == false) { need to clean the jump table, but |
741 | // there isn't such an interface yet. alternatively, replace all the other |
742 | // blocks in the jump table with the entryBlk //} |
743 | |
744 | } |
745 | |
746 | |
747 | bool AMDGPUCFGStructurizer::prepare() { |
748 | bool Changed = false; |
749 | |
750 | //FIXME: if not reducible flow graph, make it so ??? |
751 | |
752 | DEBUG(dbgs() << "AMDGPUCFGStructurizer::prepare\n";)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "AMDGPUCFGStructurizer::prepare\n" ;; } } while (0); |
753 | |
754 | orderBlocks(FuncRep); |
755 | |
756 | SmallVector<MachineBasicBlock *, DEFAULT_VEC_SLOTS8> RetBlks; |
757 | |
758 | // Add an ExitBlk to loop that don't have one |
759 | for (MachineLoopInfo::iterator It = MLI->begin(), |
760 | E = MLI->end(); It != E; ++It) { |
761 | MachineLoop *LoopRep = (*It); |
762 | MBBVector ExitingMBBs; |
763 | LoopRep->getExitingBlocks(ExitingMBBs); |
764 | |
765 | if (ExitingMBBs.size() == 0) { |
766 | MachineBasicBlock* DummyExitBlk = normalizeInfiniteLoopExit(LoopRep); |
767 | if (DummyExitBlk) |
768 | RetBlks.push_back(DummyExitBlk); |
769 | } |
770 | } |
771 | |
772 | // Remove unconditional branch instr. |
773 | // Add dummy exit block iff there are multiple returns. |
774 | for (SmallVectorImpl<MachineBasicBlock *>::const_iterator |
775 | It = OrderedBlks.begin(), E = OrderedBlks.end(); It != E; ++It) { |
776 | MachineBasicBlock *MBB = *It; |
777 | removeUnconditionalBranch(MBB); |
778 | removeRedundantConditionalBranch(MBB); |
779 | if (isReturnBlock(MBB)) { |
780 | RetBlks.push_back(MBB); |
781 | } |
782 | assert(MBB->succ_size() <= 2)((MBB->succ_size() <= 2) ? static_cast<void> (0) : __assert_fail ("MBB->succ_size() <= 2", "/tmp/buildd/llvm-toolchain-snapshot-3.7~svn240924/lib/Target/AMDGPU/AMDILCFGStructurizer.cpp" , 782, __PRETTY_FUNCTION__)); |
783 | } |
784 | |
785 | if (RetBlks.size() >= 2) { |
786 | addDummyExitBlock(RetBlks); |
787 | Changed = true; |
788 | } |
789 | |
790 | return Changed; |
791 | } |
792 | |
793 | bool AMDGPUCFGStructurizer::run() { |
794 | |
795 | //Assume reducible CFG... |
796 | DEBUG(dbgs() << "AMDGPUCFGStructurizer::run\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "AMDGPUCFGStructurizer::run\n" ; } } while (0); |
797 | |
798 | #ifdef STRESSTEST |
799 | //Use the worse block ordering to test the algorithm. |
800 | ReverseVector(orderedBlks); |
801 | #endif |
802 | |
803 | DEBUG(dbgs() << "Ordered blocks:\n"; printOrderedBlocks();)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "Ordered blocks:\n"; printOrderedBlocks ();; } } while (0); |
804 | int NumIter = 0; |
805 | bool Finish = false; |
806 | MachineBasicBlock *MBB; |
807 | bool MakeProgress = false; |
808 | int NumRemainedBlk = countActiveBlock(OrderedBlks.begin(), |
809 | OrderedBlks.end()); |
810 | |
811 | do { |
812 | ++NumIter; |
813 | DEBUG(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "numIter = " << NumIter << ", numRemaintedBlk = " << NumRemainedBlk << "\n";; } } while (0) |
814 | dbgs() << "numIter = " << NumIterdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "numIter = " << NumIter << ", numRemaintedBlk = " << NumRemainedBlk << "\n";; } } while (0) |
815 | << ", numRemaintedBlk = " << NumRemainedBlk << "\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "numIter = " << NumIter << ", numRemaintedBlk = " << NumRemainedBlk << "\n";; } } while (0) |
816 | )do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "numIter = " << NumIter << ", numRemaintedBlk = " << NumRemainedBlk << "\n";; } } while (0); |
817 | |
818 | SmallVectorImpl<MachineBasicBlock *>::const_iterator It = |
819 | OrderedBlks.begin(); |
820 | SmallVectorImpl<MachineBasicBlock *>::const_iterator E = |
821 | OrderedBlks.end(); |
822 | |
823 | SmallVectorImpl<MachineBasicBlock *>::const_iterator SccBeginIter = |
824 | It; |
825 | MachineBasicBlock *SccBeginMBB = nullptr; |
826 | int SccNumBlk = 0; // The number of active blocks, init to a |
827 | // maximum possible number. |
828 | int SccNumIter; // Number of iteration in this SCC. |
829 | |
830 | while (It != E) { |
831 | MBB = *It; |
832 | |
833 | if (!SccBeginMBB) { |
834 | SccBeginIter = It; |
835 | SccBeginMBB = MBB; |
836 | SccNumIter = 0; |
837 | SccNumBlk = NumRemainedBlk; // Init to maximum possible number. |
838 | DEBUG(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "start processing SCC" << getSCCNum(SccBeginMBB); dbgs() << "\n";; } } while (0) |
839 | dbgs() << "start processing SCC" << getSCCNum(SccBeginMBB);do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "start processing SCC" << getSCCNum(SccBeginMBB); dbgs() << "\n";; } } while (0) |
840 | dbgs() << "\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "start processing SCC" << getSCCNum(SccBeginMBB); dbgs() << "\n";; } } while (0) |
841 | )do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "start processing SCC" << getSCCNum(SccBeginMBB); dbgs() << "\n";; } } while (0); |
842 | } |
843 | |
844 | if (!isRetiredBlock(MBB)) |
845 | patternMatch(MBB); |
846 | |
847 | ++It; |
848 | |
849 | bool ContNextScc = true; |
850 | if (It == E |
851 | || getSCCNum(SccBeginMBB) != getSCCNum(*It)) { |
852 | // Just finish one scc. |
853 | ++SccNumIter; |
854 | int sccRemainedNumBlk = countActiveBlock(SccBeginIter, It); |
855 | if (sccRemainedNumBlk != 1 && sccRemainedNumBlk >= SccNumBlk) { |
856 | DEBUG(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "Can't reduce SCC " << getSCCNum(MBB) << ", sccNumIter = " << SccNumIter ; dbgs() << "doesn't make any progress\n";; } } while ( 0) |
857 | dbgs() << "Can't reduce SCC " << getSCCNum(MBB)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "Can't reduce SCC " << getSCCNum(MBB) << ", sccNumIter = " << SccNumIter ; dbgs() << "doesn't make any progress\n";; } } while ( 0) |
858 | << ", sccNumIter = " << SccNumIter;do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "Can't reduce SCC " << getSCCNum(MBB) << ", sccNumIter = " << SccNumIter ; dbgs() << "doesn't make any progress\n";; } } while ( 0) |
859 | dbgs() << "doesn't make any progress\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "Can't reduce SCC " << getSCCNum(MBB) << ", sccNumIter = " << SccNumIter ; dbgs() << "doesn't make any progress\n";; } } while ( 0) |
860 | )do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "Can't reduce SCC " << getSCCNum(MBB) << ", sccNumIter = " << SccNumIter ; dbgs() << "doesn't make any progress\n";; } } while ( 0); |
861 | ContNextScc = true; |
862 | } else if (sccRemainedNumBlk != 1 && sccRemainedNumBlk < SccNumBlk) { |
863 | SccNumBlk = sccRemainedNumBlk; |
864 | It = SccBeginIter; |
865 | ContNextScc = false; |
866 | DEBUG(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "repeat processing SCC" << getSCCNum(MBB) << "sccNumIter = " << SccNumIter << '\n';; } } while (0) |
867 | dbgs() << "repeat processing SCC" << getSCCNum(MBB)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "repeat processing SCC" << getSCCNum(MBB) << "sccNumIter = " << SccNumIter << '\n';; } } while (0) |
868 | << "sccNumIter = " << SccNumIter << '\n';do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "repeat processing SCC" << getSCCNum(MBB) << "sccNumIter = " << SccNumIter << '\n';; } } while (0) |
869 | )do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "repeat processing SCC" << getSCCNum(MBB) << "sccNumIter = " << SccNumIter << '\n';; } } while (0); |
870 | } else { |
871 | // Finish the current scc. |
872 | ContNextScc = true; |
873 | } |
874 | } else { |
875 | // Continue on next component in the current scc. |
876 | ContNextScc = false; |
877 | } |
878 | |
879 | if (ContNextScc) |
880 | SccBeginMBB = nullptr; |
881 | } //while, "one iteration" over the function. |
882 | |
883 | MachineBasicBlock *EntryMBB = |
884 | GraphTraits<MachineFunction *>::nodes_begin(FuncRep); |
885 | if (EntryMBB->succ_size() == 0) { |
886 | Finish = true; |
887 | DEBUG(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "Reduce to one block\n";; } } while (0) |
888 | dbgs() << "Reduce to one block\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "Reduce to one block\n";; } } while (0) |
889 | )do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "Reduce to one block\n";; } } while (0); |
890 | } else { |
891 | int NewnumRemainedBlk |
892 | = countActiveBlock(OrderedBlks.begin(), OrderedBlks.end()); |
893 | // consider cloned blocks ?? |
894 | if (NewnumRemainedBlk == 1 || NewnumRemainedBlk < NumRemainedBlk) { |
895 | MakeProgress = true; |
896 | NumRemainedBlk = NewnumRemainedBlk; |
897 | } else { |
898 | MakeProgress = false; |
899 | DEBUG(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "No progress\n";; } } while ( 0) |
900 | dbgs() << "No progress\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "No progress\n";; } } while ( 0) |
901 | )do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "No progress\n";; } } while ( 0); |
902 | } |
903 | } |
904 | } while (!Finish && MakeProgress); |
905 | |
906 | // Misc wrap up to maintain the consistency of the Function representation. |
907 | wrapup(GraphTraits<MachineFunction *>::nodes_begin(FuncRep)); |
908 | |
909 | // Detach retired Block, release memory. |
910 | for (MBBInfoMap::iterator It = BlockInfoMap.begin(), E = BlockInfoMap.end(); |
911 | It != E; ++It) { |
912 | if ((*It).second && (*It).second->IsRetired) { |
913 | assert(((*It).first)->getNumber() != -1)((((*It).first)->getNumber() != -1) ? static_cast<void> (0) : __assert_fail ("((*It).first)->getNumber() != -1", "/tmp/buildd/llvm-toolchain-snapshot-3.7~svn240924/lib/Target/AMDGPU/AMDILCFGStructurizer.cpp" , 913, __PRETTY_FUNCTION__)); |
914 | DEBUG(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "Erase BB" << ((*It).first )->getNumber() << "\n";; } } while (0) |
915 | dbgs() << "Erase BB" << ((*It).first)->getNumber() << "\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "Erase BB" << ((*It).first )->getNumber() << "\n";; } } while (0) |
916 | )do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "Erase BB" << ((*It).first )->getNumber() << "\n";; } } while (0); |
917 | (*It).first->eraseFromParent(); //Remove from the parent Function. |
918 | } |
919 | delete (*It).second; |
920 | } |
921 | BlockInfoMap.clear(); |
922 | LLInfoMap.clear(); |
923 | |
924 | if (!Finish) { |
925 | DEBUG(FuncRep->viewCFG())do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { FuncRep->viewCFG(); } } while (0); |
926 | llvm_unreachable("IRREDUCIBLE_CFG")::llvm::llvm_unreachable_internal("IRREDUCIBLE_CFG", "/tmp/buildd/llvm-toolchain-snapshot-3.7~svn240924/lib/Target/AMDGPU/AMDILCFGStructurizer.cpp" , 926); |
927 | } |
928 | |
929 | return true; |
930 | } |
931 | |
932 | |
933 | |
934 | void AMDGPUCFGStructurizer::orderBlocks(MachineFunction *MF) { |
935 | int SccNum = 0; |
936 | MachineBasicBlock *MBB; |
937 | for (scc_iterator<MachineFunction *> It = scc_begin(MF); !It.isAtEnd(); |
938 | ++It, ++SccNum) { |
939 | const std::vector<MachineBasicBlock *> &SccNext = *It; |
940 | for (std::vector<MachineBasicBlock *>::const_iterator |
941 | blockIter = SccNext.begin(), blockEnd = SccNext.end(); |
942 | blockIter != blockEnd; ++blockIter) { |
943 | MBB = *blockIter; |
944 | OrderedBlks.push_back(MBB); |
945 | recordSccnum(MBB, SccNum); |
946 | } |
947 | } |
948 | |
949 | //walk through all the block in func to check for unreachable |
950 | typedef GraphTraits<MachineFunction *> GTM; |
951 | MachineFunction::iterator It = GTM::nodes_begin(MF), E = GTM::nodes_end(MF); |
952 | for (; It != E; ++It) { |
953 | MachineBasicBlock *MBB = &(*It); |
954 | SccNum = getSCCNum(MBB); |
955 | if (SccNum == INVALIDSCCNUM-1) |
956 | dbgs() << "unreachable block BB" << MBB->getNumber() << "\n"; |
957 | } |
958 | } |
959 | |
960 | int AMDGPUCFGStructurizer::patternMatch(MachineBasicBlock *MBB) { |
961 | int NumMatch = 0; |
962 | int CurMatch; |
963 | |
964 | DEBUG(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "Begin patternMatch BB" << MBB->getNumber() << "\n";; } } while (0) |
965 | dbgs() << "Begin patternMatch BB" << MBB->getNumber() << "\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "Begin patternMatch BB" << MBB->getNumber() << "\n";; } } while (0) |
966 | )do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "Begin patternMatch BB" << MBB->getNumber() << "\n";; } } while (0); |
967 | |
968 | while ((CurMatch = patternMatchGroup(MBB)) > 0) |
969 | NumMatch += CurMatch; |
970 | |
971 | DEBUG(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "End patternMatch BB" << MBB->getNumber() << ", numMatch = " << NumMatch << "\n";; } } while (0) |
972 | dbgs() << "End patternMatch BB" << MBB->getNumber()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "End patternMatch BB" << MBB->getNumber() << ", numMatch = " << NumMatch << "\n";; } } while (0) |
973 | << ", numMatch = " << NumMatch << "\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "End patternMatch BB" << MBB->getNumber() << ", numMatch = " << NumMatch << "\n";; } } while (0) |
974 | )do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "End patternMatch BB" << MBB->getNumber() << ", numMatch = " << NumMatch << "\n";; } } while (0); |
975 | |
976 | return NumMatch; |
977 | } |
978 | |
979 | int AMDGPUCFGStructurizer::patternMatchGroup(MachineBasicBlock *MBB) { |
980 | int NumMatch = 0; |
981 | NumMatch += loopendPatternMatch(); |
982 | NumMatch += serialPatternMatch(MBB); |
983 | NumMatch += ifPatternMatch(MBB); |
984 | return NumMatch; |
985 | } |
986 | |
987 | |
988 | int AMDGPUCFGStructurizer::serialPatternMatch(MachineBasicBlock *MBB) { |
989 | if (MBB->succ_size() != 1) |
990 | return 0; |
991 | |
992 | MachineBasicBlock *childBlk = *MBB->succ_begin(); |
993 | if (childBlk->pred_size() != 1 || isActiveLoophead(childBlk)) |
994 | return 0; |
995 | |
996 | mergeSerialBlock(MBB, childBlk); |
997 | ++numSerialPatternMatch; |
998 | return 1; |
999 | } |
1000 | |
1001 | int AMDGPUCFGStructurizer::ifPatternMatch(MachineBasicBlock *MBB) { |
1002 | //two edges |
1003 | if (MBB->succ_size() != 2) |
1004 | return 0; |
1005 | if (hasBackEdge(MBB)) |
1006 | return 0; |
1007 | MachineInstr *BranchMI = getNormalBlockBranchInstr(MBB); |
1008 | if (!BranchMI) |
1009 | return 0; |
1010 | |
1011 | assert(isCondBranch(BranchMI))((isCondBranch(BranchMI)) ? static_cast<void> (0) : __assert_fail ("isCondBranch(BranchMI)", "/tmp/buildd/llvm-toolchain-snapshot-3.7~svn240924/lib/Target/AMDGPU/AMDILCFGStructurizer.cpp" , 1011, __PRETTY_FUNCTION__)); |
1012 | int NumMatch = 0; |
1013 | |
1014 | MachineBasicBlock *TrueMBB = getTrueBranch(BranchMI); |
1015 | NumMatch += serialPatternMatch(TrueMBB); |
1016 | NumMatch += ifPatternMatch(TrueMBB); |
1017 | MachineBasicBlock *FalseMBB = getFalseBranch(MBB, BranchMI); |
1018 | NumMatch += serialPatternMatch(FalseMBB); |
1019 | NumMatch += ifPatternMatch(FalseMBB); |
1020 | MachineBasicBlock *LandBlk; |
1021 | int Cloned = 0; |
1022 | |
1023 | assert (!TrueMBB->succ_empty() || !FalseMBB->succ_empty())((!TrueMBB->succ_empty() || !FalseMBB->succ_empty()) ? static_cast <void> (0) : __assert_fail ("!TrueMBB->succ_empty() || !FalseMBB->succ_empty()" , "/tmp/buildd/llvm-toolchain-snapshot-3.7~svn240924/lib/Target/AMDGPU/AMDILCFGStructurizer.cpp" , 1023, __PRETTY_FUNCTION__)); |
1024 | // TODO: Simplify |
1025 | if (TrueMBB->succ_size() == 1 && FalseMBB->succ_size() == 1 |
1026 | && *TrueMBB->succ_begin() == *FalseMBB->succ_begin()) { |
1027 | // Diamond pattern |
1028 | LandBlk = *TrueMBB->succ_begin(); |
1029 | } else if (TrueMBB->succ_size() == 1 && *TrueMBB->succ_begin() == FalseMBB) { |
1030 | // Triangle pattern, false is empty |
1031 | LandBlk = FalseMBB; |
1032 | FalseMBB = nullptr; |
1033 | } else if (FalseMBB->succ_size() == 1 |
1034 | && *FalseMBB->succ_begin() == TrueMBB) { |
1035 | // Triangle pattern, true is empty |
1036 | // We reverse the predicate to make a triangle, empty false pattern; |
1037 | std::swap(TrueMBB, FalseMBB); |
1038 | reversePredicateSetter(MBB->end()); |
1039 | LandBlk = FalseMBB; |
1040 | FalseMBB = nullptr; |
1041 | } else if (FalseMBB->succ_size() == 1 |
1042 | && isSameloopDetachedContbreak(TrueMBB, FalseMBB)) { |
1043 | LandBlk = *FalseMBB->succ_begin(); |
1044 | } else if (TrueMBB->succ_size() == 1 |
1045 | && isSameloopDetachedContbreak(FalseMBB, TrueMBB)) { |
1046 | LandBlk = *TrueMBB->succ_begin(); |
1047 | } else { |
1048 | return NumMatch + handleJumpintoIf(MBB, TrueMBB, FalseMBB); |
1049 | } |
1050 | |
1051 | // improveSimpleJumpinfoIf can handle the case where landBlk == NULL but the |
1052 | // new BB created for landBlk==NULL may introduce new challenge to the |
1053 | // reduction process. |
1054 | if (LandBlk && |
1055 | ((TrueMBB && TrueMBB->pred_size() > 1) |
1056 | || (FalseMBB && FalseMBB->pred_size() > 1))) { |
1057 | Cloned += improveSimpleJumpintoIf(MBB, TrueMBB, FalseMBB, &LandBlk); |
1058 | } |
1059 | |
1060 | if (TrueMBB && TrueMBB->pred_size() > 1) { |
1061 | TrueMBB = cloneBlockForPredecessor(TrueMBB, MBB); |
1062 | ++Cloned; |
1063 | } |
1064 | |
1065 | if (FalseMBB && FalseMBB->pred_size() > 1) { |
1066 | FalseMBB = cloneBlockForPredecessor(FalseMBB, MBB); |
1067 | ++Cloned; |
1068 | } |
1069 | |
1070 | mergeIfthenelseBlock(BranchMI, MBB, TrueMBB, FalseMBB, LandBlk); |
1071 | |
1072 | ++numIfPatternMatch; |
1073 | |
1074 | numClonedBlock += Cloned; |
1075 | |
1076 | return 1 + Cloned + NumMatch; |
1077 | } |
1078 | |
1079 | int AMDGPUCFGStructurizer::loopendPatternMatch() { |
1080 | std::deque<MachineLoop *> NestedLoops; |
1081 | for (auto &It: *MLI) |
1082 | for (MachineLoop *ML : depth_first(It)) |
1083 | NestedLoops.push_front(ML); |
1084 | |
1085 | if (NestedLoops.size() == 0) |
1086 | return 0; |
1087 | |
1088 | // Process nested loop outside->inside (we did push_front), |
1089 | // so "continue" to a outside loop won't be mistaken as "break" |
1090 | // of the current loop. |
1091 | int Num = 0; |
1092 | for (MachineLoop *ExaminedLoop : NestedLoops) { |
1093 | if (ExaminedLoop->getNumBlocks() == 0 || Visited[ExaminedLoop]) |
1094 | continue; |
1095 | DEBUG(dbgs() << "Processing:\n"; ExaminedLoop->dump();)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "Processing:\n"; ExaminedLoop ->dump();; } } while (0); |
1096 | int NumBreak = mergeLoop(ExaminedLoop); |
1097 | if (NumBreak == -1) |
1098 | break; |
1099 | Num += NumBreak; |
1100 | } |
1101 | return Num; |
1102 | } |
1103 | |
1104 | int AMDGPUCFGStructurizer::mergeLoop(MachineLoop *LoopRep) { |
1105 | MachineBasicBlock *LoopHeader = LoopRep->getHeader(); |
1106 | MBBVector ExitingMBBs; |
1107 | LoopRep->getExitingBlocks(ExitingMBBs); |
1108 | assert(!ExitingMBBs.empty() && "Infinite Loop not supported")((!ExitingMBBs.empty() && "Infinite Loop not supported" ) ? static_cast<void> (0) : __assert_fail ("!ExitingMBBs.empty() && \"Infinite Loop not supported\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.7~svn240924/lib/Target/AMDGPU/AMDILCFGStructurizer.cpp" , 1108, __PRETTY_FUNCTION__)); |
1109 | DEBUG(dbgs() << "Loop has " << ExitingMBBs.size() << " exiting blocks\n";)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "Loop has " << ExitingMBBs .size() << " exiting blocks\n";; } } while (0); |
1110 | // We assume a single ExitBlk |
1111 | MBBVector ExitBlks; |
1112 | LoopRep->getExitBlocks(ExitBlks); |
1113 | SmallPtrSet<MachineBasicBlock *, 2> ExitBlkSet; |
1114 | for (unsigned i = 0, e = ExitBlks.size(); i < e; ++i) |
1115 | ExitBlkSet.insert(ExitBlks[i]); |
1116 | assert(ExitBlkSet.size() == 1)((ExitBlkSet.size() == 1) ? static_cast<void> (0) : __assert_fail ("ExitBlkSet.size() == 1", "/tmp/buildd/llvm-toolchain-snapshot-3.7~svn240924/lib/Target/AMDGPU/AMDILCFGStructurizer.cpp" , 1116, __PRETTY_FUNCTION__)); |
1117 | MachineBasicBlock *ExitBlk = *ExitBlks.begin(); |
1118 | assert(ExitBlk && "Loop has several exit block")((ExitBlk && "Loop has several exit block") ? static_cast <void> (0) : __assert_fail ("ExitBlk && \"Loop has several exit block\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.7~svn240924/lib/Target/AMDGPU/AMDILCFGStructurizer.cpp" , 1118, __PRETTY_FUNCTION__)); |
1119 | MBBVector LatchBlks; |
1120 | typedef GraphTraits<Inverse<MachineBasicBlock*> > InvMBBTraits; |
1121 | InvMBBTraits::ChildIteratorType PI = InvMBBTraits::child_begin(LoopHeader), |
1122 | PE = InvMBBTraits::child_end(LoopHeader); |
1123 | for (; PI != PE; PI++) { |
1124 | if (LoopRep->contains(*PI)) |
1125 | LatchBlks.push_back(*PI); |
1126 | } |
1127 | |
1128 | for (unsigned i = 0, e = ExitingMBBs.size(); i < e; ++i) |
1129 | mergeLoopbreakBlock(ExitingMBBs[i], ExitBlk); |
1130 | for (unsigned i = 0, e = LatchBlks.size(); i < e; ++i) |
1131 | settleLoopcontBlock(LatchBlks[i], LoopHeader); |
1132 | int Match = 0; |
1133 | do { |
1134 | Match = 0; |
1135 | Match += serialPatternMatch(LoopHeader); |
1136 | Match += ifPatternMatch(LoopHeader); |
1137 | } while (Match > 0); |
1138 | mergeLooplandBlock(LoopHeader, ExitBlk); |
1139 | MachineLoop *ParentLoop = LoopRep->getParentLoop(); |
1140 | if (ParentLoop) |
1141 | MLI->changeLoopFor(LoopHeader, ParentLoop); |
1142 | else |
1143 | MLI->removeBlock(LoopHeader); |
1144 | Visited[LoopRep] = true; |
1145 | return 1; |
1146 | } |
1147 | |
1148 | int AMDGPUCFGStructurizer::loopcontPatternMatch(MachineLoop *LoopRep, |
1149 | MachineBasicBlock *LoopHeader) { |
1150 | int NumCont = 0; |
1151 | SmallVector<MachineBasicBlock *, DEFAULT_VEC_SLOTS8> ContMBB; |
1152 | typedef GraphTraits<Inverse<MachineBasicBlock *> > GTIM; |
1153 | GTIM::ChildIteratorType It = GTIM::child_begin(LoopHeader), |
1154 | E = GTIM::child_end(LoopHeader); |
1155 | for (; It != E; ++It) { |
1156 | MachineBasicBlock *MBB = *It; |
1157 | if (LoopRep->contains(MBB)) { |
1158 | handleLoopcontBlock(MBB, MLI->getLoopFor(MBB), |
1159 | LoopHeader, LoopRep); |
1160 | ContMBB.push_back(MBB); |
1161 | ++NumCont; |
1162 | } |
1163 | } |
1164 | |
1165 | for (SmallVectorImpl<MachineBasicBlock *>::iterator It = ContMBB.begin(), |
1166 | E = ContMBB.end(); It != E; ++It) { |
1167 | (*It)->removeSuccessor(LoopHeader); |
1168 | } |
1169 | |
1170 | numLoopcontPatternMatch += NumCont; |
1171 | |
1172 | return NumCont; |
1173 | } |
1174 | |
1175 | |
1176 | bool AMDGPUCFGStructurizer::isSameloopDetachedContbreak( |
1177 | MachineBasicBlock *Src1MBB, MachineBasicBlock *Src2MBB) { |
1178 | if (Src1MBB->succ_size() == 0) { |
1179 | MachineLoop *LoopRep = MLI->getLoopFor(Src1MBB); |
1180 | if (LoopRep&& LoopRep == MLI->getLoopFor(Src2MBB)) { |
1181 | MachineBasicBlock *&TheEntry = LLInfoMap[LoopRep]; |
1182 | if (TheEntry) { |
1183 | DEBUG(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "isLoopContBreakBlock yes src1 = BB" << Src1MBB->getNumber() << " src2 = BB" << Src2MBB->getNumber() << "\n";; } } while (0) |
1184 | dbgs() << "isLoopContBreakBlock yes src1 = BB"do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "isLoopContBreakBlock yes src1 = BB" << Src1MBB->getNumber() << " src2 = BB" << Src2MBB->getNumber() << "\n";; } } while (0) |
1185 | << Src1MBB->getNumber()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "isLoopContBreakBlock yes src1 = BB" << Src1MBB->getNumber() << " src2 = BB" << Src2MBB->getNumber() << "\n";; } } while (0) |
1186 | << " src2 = BB" << Src2MBB->getNumber() << "\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "isLoopContBreakBlock yes src1 = BB" << Src1MBB->getNumber() << " src2 = BB" << Src2MBB->getNumber() << "\n";; } } while (0) |
1187 | )do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "isLoopContBreakBlock yes src1 = BB" << Src1MBB->getNumber() << " src2 = BB" << Src2MBB->getNumber() << "\n";; } } while (0); |
1188 | return true; |
1189 | } |
1190 | } |
1191 | } |
1192 | return false; |
1193 | } |
1194 | |
1195 | int AMDGPUCFGStructurizer::handleJumpintoIf(MachineBasicBlock *HeadMBB, |
1196 | MachineBasicBlock *TrueMBB, MachineBasicBlock *FalseMBB) { |
1197 | int Num = handleJumpintoIfImp(HeadMBB, TrueMBB, FalseMBB); |
1198 | if (Num == 0) { |
1199 | DEBUG(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "handleJumpintoIf swap trueBlk and FalseBlk" << "\n";; } } while (0) |
1200 | dbgs() << "handleJumpintoIf swap trueBlk and FalseBlk" << "\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "handleJumpintoIf swap trueBlk and FalseBlk" << "\n";; } } while (0) |
1201 | )do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "handleJumpintoIf swap trueBlk and FalseBlk" << "\n";; } } while (0); |
1202 | Num = handleJumpintoIfImp(HeadMBB, FalseMBB, TrueMBB); |
1203 | } |
1204 | return Num; |
1205 | } |
1206 | |
1207 | int AMDGPUCFGStructurizer::handleJumpintoIfImp(MachineBasicBlock *HeadMBB, |
1208 | MachineBasicBlock *TrueMBB, MachineBasicBlock *FalseMBB) { |
1209 | int Num = 0; |
1210 | MachineBasicBlock *DownBlk; |
1211 | |
1212 | //trueBlk could be the common post dominator |
1213 | DownBlk = TrueMBB; |
1214 | |
1215 | DEBUG(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "handleJumpintoIfImp head = BB" << HeadMBB->getNumber() << " true = BB" << TrueMBB->getNumber() << ", numSucc=" << TrueMBB ->succ_size() << " false = BB" << FalseMBB-> getNumber() << "\n";; } } while (0) |
1216 | dbgs() << "handleJumpintoIfImp head = BB" << HeadMBB->getNumber()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "handleJumpintoIfImp head = BB" << HeadMBB->getNumber() << " true = BB" << TrueMBB->getNumber() << ", numSucc=" << TrueMBB ->succ_size() << " false = BB" << FalseMBB-> getNumber() << "\n";; } } while (0) |
1217 | << " true = BB" << TrueMBB->getNumber()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "handleJumpintoIfImp head = BB" << HeadMBB->getNumber() << " true = BB" << TrueMBB->getNumber() << ", numSucc=" << TrueMBB ->succ_size() << " false = BB" << FalseMBB-> getNumber() << "\n";; } } while (0) |
1218 | << ", numSucc=" << TrueMBB->succ_size()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "handleJumpintoIfImp head = BB" << HeadMBB->getNumber() << " true = BB" << TrueMBB->getNumber() << ", numSucc=" << TrueMBB ->succ_size() << " false = BB" << FalseMBB-> getNumber() << "\n";; } } while (0) |
1219 | << " false = BB" << FalseMBB->getNumber() << "\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "handleJumpintoIfImp head = BB" << HeadMBB->getNumber() << " true = BB" << TrueMBB->getNumber() << ", numSucc=" << TrueMBB ->succ_size() << " false = BB" << FalseMBB-> getNumber() << "\n";; } } while (0) |
1220 | )do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "handleJumpintoIfImp head = BB" << HeadMBB->getNumber() << " true = BB" << TrueMBB->getNumber() << ", numSucc=" << TrueMBB ->succ_size() << " false = BB" << FalseMBB-> getNumber() << "\n";; } } while (0); |
1221 | |
1222 | while (DownBlk) { |
1223 | DEBUG(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "check down = BB" << DownBlk ->getNumber();; } } while (0) |
1224 | dbgs() << "check down = BB" << DownBlk->getNumber();do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "check down = BB" << DownBlk ->getNumber();; } } while (0) |
1225 | )do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "check down = BB" << DownBlk ->getNumber();; } } while (0); |
1226 | |
1227 | if (singlePathTo(FalseMBB, DownBlk) == SinglePath_InPath) { |
1228 | DEBUG(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << " working\n";; } } while (0) |
1229 | dbgs() << " working\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << " working\n";; } } while (0) |
1230 | )do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << " working\n";; } } while (0); |
1231 | |
1232 | Num += cloneOnSideEntryTo(HeadMBB, TrueMBB, DownBlk); |
1233 | Num += cloneOnSideEntryTo(HeadMBB, FalseMBB, DownBlk); |
1234 | |
1235 | numClonedBlock += Num; |
1236 | Num += serialPatternMatch(*HeadMBB->succ_begin()); |
1237 | Num += serialPatternMatch(*std::next(HeadMBB->succ_begin())); |
1238 | Num += ifPatternMatch(HeadMBB); |
1239 | assert(Num > 0)((Num > 0) ? static_cast<void> (0) : __assert_fail ( "Num > 0", "/tmp/buildd/llvm-toolchain-snapshot-3.7~svn240924/lib/Target/AMDGPU/AMDILCFGStructurizer.cpp" , 1239, __PRETTY_FUNCTION__)); |
1240 | |
1241 | break; |
1242 | } |
1243 | DEBUG(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << " not working\n";; } } while (0) |
1244 | dbgs() << " not working\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << " not working\n";; } } while (0) |
1245 | )do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << " not working\n";; } } while (0); |
1246 | DownBlk = (DownBlk->succ_size() == 1) ? (*DownBlk->succ_begin()) : nullptr; |
1247 | } // walk down the postDomTree |
1248 | |
1249 | return Num; |
1250 | } |
1251 | |
1252 | void AMDGPUCFGStructurizer::showImproveSimpleJumpintoIf( |
1253 | MachineBasicBlock *HeadMBB, MachineBasicBlock *TrueMBB, |
1254 | MachineBasicBlock *FalseMBB, MachineBasicBlock *LandMBB, bool Detail) { |
1255 | dbgs() << "head = BB" << HeadMBB->getNumber() |
1256 | << " size = " << HeadMBB->size(); |
1257 | if (Detail) { |
1258 | dbgs() << "\n"; |
1259 | HeadMBB->print(dbgs()); |
1260 | dbgs() << "\n"; |
1261 | } |
1262 | |
1263 | if (TrueMBB) { |
1264 | dbgs() << ", true = BB" << TrueMBB->getNumber() << " size = " |
1265 | << TrueMBB->size() << " numPred = " << TrueMBB->pred_size(); |
1266 | if (Detail) { |
1267 | dbgs() << "\n"; |
1268 | TrueMBB->print(dbgs()); |
1269 | dbgs() << "\n"; |
1270 | } |
1271 | } |
1272 | if (FalseMBB) { |
1273 | dbgs() << ", false = BB" << FalseMBB->getNumber() << " size = " |
1274 | << FalseMBB->size() << " numPred = " << FalseMBB->pred_size(); |
1275 | if (Detail) { |
1276 | dbgs() << "\n"; |
1277 | FalseMBB->print(dbgs()); |
1278 | dbgs() << "\n"; |
1279 | } |
1280 | } |
1281 | if (LandMBB) { |
1282 | dbgs() << ", land = BB" << LandMBB->getNumber() << " size = " |
1283 | << LandMBB->size() << " numPred = " << LandMBB->pred_size(); |
1284 | if (Detail) { |
1285 | dbgs() << "\n"; |
1286 | LandMBB->print(dbgs()); |
1287 | dbgs() << "\n"; |
1288 | } |
1289 | } |
1290 | |
1291 | dbgs() << "\n"; |
1292 | } |
1293 | |
1294 | int AMDGPUCFGStructurizer::improveSimpleJumpintoIf(MachineBasicBlock *HeadMBB, |
1295 | MachineBasicBlock *TrueMBB, MachineBasicBlock *FalseMBB, |
1296 | MachineBasicBlock **LandMBBPtr) { |
1297 | bool MigrateTrue = false; |
1298 | bool MigrateFalse = false; |
1299 | |
1300 | MachineBasicBlock *LandBlk = *LandMBBPtr; |
1301 | |
1302 | assert((!TrueMBB || TrueMBB->succ_size() <= 1)(((!TrueMBB || TrueMBB->succ_size() <= 1) && (! FalseMBB || FalseMBB->succ_size() <= 1)) ? static_cast< void> (0) : __assert_fail ("(!TrueMBB || TrueMBB->succ_size() <= 1) && (!FalseMBB || FalseMBB->succ_size() <= 1)" , "/tmp/buildd/llvm-toolchain-snapshot-3.7~svn240924/lib/Target/AMDGPU/AMDILCFGStructurizer.cpp" , 1303, __PRETTY_FUNCTION__)) |
1303 | && (!FalseMBB || FalseMBB->succ_size() <= 1))(((!TrueMBB || TrueMBB->succ_size() <= 1) && (! FalseMBB || FalseMBB->succ_size() <= 1)) ? static_cast< void> (0) : __assert_fail ("(!TrueMBB || TrueMBB->succ_size() <= 1) && (!FalseMBB || FalseMBB->succ_size() <= 1)" , "/tmp/buildd/llvm-toolchain-snapshot-3.7~svn240924/lib/Target/AMDGPU/AMDILCFGStructurizer.cpp" , 1303, __PRETTY_FUNCTION__)); |
1304 | |
1305 | if (TrueMBB == FalseMBB) |
1306 | return 0; |
1307 | |
1308 | MigrateTrue = needMigrateBlock(TrueMBB); |
1309 | MigrateFalse = needMigrateBlock(FalseMBB); |
1310 | |
1311 | if (!MigrateTrue && !MigrateFalse) |
1312 | return 0; |
1313 | |
1314 | // If we need to migrate either trueBlk and falseBlk, migrate the rest that |
1315 | // have more than one predecessors. without doing this, its predecessor |
1316 | // rather than headBlk will have undefined value in initReg. |
1317 | if (!MigrateTrue && TrueMBB && TrueMBB->pred_size() > 1) |
1318 | MigrateTrue = true; |
1319 | if (!MigrateFalse && FalseMBB && FalseMBB->pred_size() > 1) |
1320 | MigrateFalse = true; |
1321 | |
1322 | DEBUG(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "before improveSimpleJumpintoIf: " ; showImproveSimpleJumpintoIf(HeadMBB, TrueMBB, FalseMBB, LandBlk , 0);; } } while (0) |
1323 | dbgs() << "before improveSimpleJumpintoIf: ";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "before improveSimpleJumpintoIf: " ; showImproveSimpleJumpintoIf(HeadMBB, TrueMBB, FalseMBB, LandBlk , 0);; } } while (0) |
1324 | showImproveSimpleJumpintoIf(HeadMBB, TrueMBB, FalseMBB, LandBlk, 0);do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "before improveSimpleJumpintoIf: " ; showImproveSimpleJumpintoIf(HeadMBB, TrueMBB, FalseMBB, LandBlk , 0);; } } while (0) |
1325 | )do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "before improveSimpleJumpintoIf: " ; showImproveSimpleJumpintoIf(HeadMBB, TrueMBB, FalseMBB, LandBlk , 0);; } } while (0); |
1326 | |
1327 | // org: headBlk => if () {trueBlk} else {falseBlk} => landBlk |
1328 | // |
1329 | // new: headBlk => if () {initReg = 1; org trueBlk branch} else |
1330 | // {initReg = 0; org falseBlk branch } |
1331 | // => landBlk => if (initReg) {org trueBlk} else {org falseBlk} |
1332 | // => org landBlk |
1333 | // if landBlk->pred_size() > 2, put the about if-else inside |
1334 | // if (initReg !=2) {...} |
1335 | // |
1336 | // add initReg = initVal to headBlk |
1337 | |
1338 | const TargetRegisterClass * I32RC = TRI->getCFGStructurizerRegClass(MVT::i32); |
1339 | if (!MigrateTrue || !MigrateFalse) { |
1340 | // XXX: We have an opportunity here to optimize the "branch into if" case |
1341 | // here. Branch into if looks like this: |
1342 | // entry |
1343 | // / | |
1344 | // diamond_head branch_from |
1345 | // / \ | |
1346 | // diamond_false diamond_true |
1347 | // \ / |
1348 | // done |
1349 | // |
1350 | // The diamond_head block begins the "if" and the diamond_true block |
1351 | // is the block being "branched into". |
1352 | // |
1353 | // If MigrateTrue is true, then TrueBB is the block being "branched into" |
1354 | // and if MigrateFalse is true, then FalseBB is the block being |
1355 | // "branched into" |
1356 | // |
1357 | // Here is the pseudo code for how I think the optimization should work: |
1358 | // 1. Insert MOV GPR0, 0 before the branch instruction in diamond_head. |
1359 | // 2. Insert MOV GPR0, 1 before the branch instruction in branch_from. |
1360 | // 3. Move the branch instruction from diamond_head into its own basic |
1361 | // block (new_block). |
1362 | // 4. Add an unconditional branch from diamond_head to new_block |
1363 | // 5. Replace the branch instruction in branch_from with an unconditional |
1364 | // branch to new_block. If branch_from has multiple predecessors, then |
1365 | // we need to replace the True/False block in the branch |
1366 | // instruction instead of replacing it. |
1367 | // 6. Change the condition of the branch instruction in new_block from |
1368 | // COND to (COND || GPR0) |
1369 | // |
1370 | // In order insert these MOV instruction, we will need to use the |
1371 | // RegisterScavenger. Usually liveness stops being tracked during |
1372 | // the late machine optimization passes, however if we implement |
1373 | // bool TargetRegisterInfo::requiresRegisterScavenging( |
1374 | // const MachineFunction &MF) |
1375 | // and have it return true, liveness will be tracked correctly |
1376 | // by generic optimization passes. We will also need to make sure that |
1377 | // all of our target-specific passes that run after regalloc and before |
1378 | // the CFGStructurizer track liveness and we will need to modify this pass |
1379 | // to correctly track liveness. |
1380 | // |
1381 | // After the above changes, the new CFG should look like this: |
1382 | // entry |
1383 | // / | |
1384 | // diamond_head branch_from |
1385 | // \ / |
1386 | // new_block |
1387 | // / | |
1388 | // diamond_false diamond_true |
1389 | // \ / |
1390 | // done |
1391 | // |
1392 | // Without this optimization, we are forced to duplicate the diamond_true |
1393 | // block and we will end up with a CFG like this: |
1394 | // |
1395 | // entry |
1396 | // / | |
1397 | // diamond_head branch_from |
1398 | // / \ | |
1399 | // diamond_false diamond_true diamond_true (duplicate) |
1400 | // \ / | |
1401 | // done --------------------| |
1402 | // |
1403 | // Duplicating diamond_true can be very costly especially if it has a |
1404 | // lot of instructions. |
1405 | return 0; |
1406 | } |
1407 | |
1408 | int NumNewBlk = 0; |
1409 | |
1410 | bool LandBlkHasOtherPred = (LandBlk->pred_size() > 2); |
1411 | |
1412 | //insert AMDGPU::ENDIF to avoid special case "input landBlk == NULL" |
1413 | MachineBasicBlock::iterator I = insertInstrBefore(LandBlk, AMDGPU::ENDIF); |
1414 | |
1415 | if (LandBlkHasOtherPred) { |
1416 | llvm_unreachable("Extra register needed to handle CFG")::llvm::llvm_unreachable_internal("Extra register needed to handle CFG" , "/tmp/buildd/llvm-toolchain-snapshot-3.7~svn240924/lib/Target/AMDGPU/AMDILCFGStructurizer.cpp" , 1416); |
1417 | unsigned CmpResReg = |
1418 | HeadMBB->getParent()->getRegInfo().createVirtualRegister(I32RC); |
1419 | llvm_unreachable("Extra compare instruction needed to handle CFG")::llvm::llvm_unreachable_internal("Extra compare instruction needed to handle CFG" , "/tmp/buildd/llvm-toolchain-snapshot-3.7~svn240924/lib/Target/AMDGPU/AMDILCFGStructurizer.cpp" , 1419); |
1420 | insertCondBranchBefore(LandBlk, I, AMDGPU::IF_PREDICATE_SET, |
1421 | CmpResReg, DebugLoc()); |
1422 | } |
1423 | |
1424 | // XXX: We are running this after RA, so creating virtual registers will |
1425 | // cause an assertion failure in the PostRA scheduling pass. |
1426 | unsigned InitReg = |
1427 | HeadMBB->getParent()->getRegInfo().createVirtualRegister(I32RC); |
1428 | insertCondBranchBefore(LandBlk, I, AMDGPU::IF_PREDICATE_SET, InitReg, |
1429 | DebugLoc()); |
1430 | |
1431 | if (MigrateTrue) { |
1432 | migrateInstruction(TrueMBB, LandBlk, I); |
1433 | // need to uncondionally insert the assignment to ensure a path from its |
1434 | // predecessor rather than headBlk has valid value in initReg if |
1435 | // (initVal != 1). |
1436 | llvm_unreachable("Extra register needed to handle CFG")::llvm::llvm_unreachable_internal("Extra register needed to handle CFG" , "/tmp/buildd/llvm-toolchain-snapshot-3.7~svn240924/lib/Target/AMDGPU/AMDILCFGStructurizer.cpp" , 1436); |
1437 | } |
1438 | insertInstrBefore(I, AMDGPU::ELSE); |
1439 | |
1440 | if (MigrateFalse) { |
1441 | migrateInstruction(FalseMBB, LandBlk, I); |
1442 | // need to uncondionally insert the assignment to ensure a path from its |
1443 | // predecessor rather than headBlk has valid value in initReg if |
1444 | // (initVal != 0) |
1445 | llvm_unreachable("Extra register needed to handle CFG")::llvm::llvm_unreachable_internal("Extra register needed to handle CFG" , "/tmp/buildd/llvm-toolchain-snapshot-3.7~svn240924/lib/Target/AMDGPU/AMDILCFGStructurizer.cpp" , 1445); |
1446 | } |
1447 | |
1448 | if (LandBlkHasOtherPred) { |
1449 | // add endif |
1450 | insertInstrBefore(I, AMDGPU::ENDIF); |
1451 | |
1452 | // put initReg = 2 to other predecessors of landBlk |
1453 | for (MachineBasicBlock::pred_iterator PI = LandBlk->pred_begin(), |
1454 | PE = LandBlk->pred_end(); PI != PE; ++PI) { |
1455 | MachineBasicBlock *MBB = *PI; |
1456 | if (MBB != TrueMBB && MBB != FalseMBB) |
1457 | llvm_unreachable("Extra register needed to handle CFG")::llvm::llvm_unreachable_internal("Extra register needed to handle CFG" , "/tmp/buildd/llvm-toolchain-snapshot-3.7~svn240924/lib/Target/AMDGPU/AMDILCFGStructurizer.cpp" , 1457); |
1458 | } |
1459 | } |
1460 | DEBUG(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "result from improveSimpleJumpintoIf: " ; showImproveSimpleJumpintoIf(HeadMBB, TrueMBB, FalseMBB, LandBlk , 0);; } } while (0) |
1461 | dbgs() << "result from improveSimpleJumpintoIf: ";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "result from improveSimpleJumpintoIf: " ; showImproveSimpleJumpintoIf(HeadMBB, TrueMBB, FalseMBB, LandBlk , 0);; } } while (0) |
1462 | showImproveSimpleJumpintoIf(HeadMBB, TrueMBB, FalseMBB, LandBlk, 0);do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "result from improveSimpleJumpintoIf: " ; showImproveSimpleJumpintoIf(HeadMBB, TrueMBB, FalseMBB, LandBlk , 0);; } } while (0) |
1463 | )do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "result from improveSimpleJumpintoIf: " ; showImproveSimpleJumpintoIf(HeadMBB, TrueMBB, FalseMBB, LandBlk , 0);; } } while (0); |
1464 | |
1465 | // update landBlk |
1466 | *LandMBBPtr = LandBlk; |
1467 | |
1468 | return NumNewBlk; |
1469 | } |
1470 | |
1471 | void AMDGPUCFGStructurizer::handleLoopcontBlock(MachineBasicBlock *ContingMBB, |
1472 | MachineLoop *ContingLoop, MachineBasicBlock *ContMBB, |
1473 | MachineLoop *ContLoop) { |
1474 | DEBUG(dbgs() << "loopcontPattern cont = BB" << ContingMBB->getNumber()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "loopcontPattern cont = BB" << ContingMBB->getNumber() << " header = BB" << ContMBB ->getNumber() << "\n"; dbgs() << "Trying to continue loop-depth = " << getLoopDepth(ContLoop) << " from loop-depth = " << getLoopDepth(ContingLoop) << "\n";; } } while (0) |
1475 | << " header = BB" << ContMBB->getNumber() << "\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "loopcontPattern cont = BB" << ContingMBB->getNumber() << " header = BB" << ContMBB ->getNumber() << "\n"; dbgs() << "Trying to continue loop-depth = " << getLoopDepth(ContLoop) << " from loop-depth = " << getLoopDepth(ContingLoop) << "\n";; } } while (0) |
1476 | dbgs() << "Trying to continue loop-depth = "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "loopcontPattern cont = BB" << ContingMBB->getNumber() << " header = BB" << ContMBB ->getNumber() << "\n"; dbgs() << "Trying to continue loop-depth = " << getLoopDepth(ContLoop) << " from loop-depth = " << getLoopDepth(ContingLoop) << "\n";; } } while (0) |
1477 | << getLoopDepth(ContLoop)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "loopcontPattern cont = BB" << ContingMBB->getNumber() << " header = BB" << ContMBB ->getNumber() << "\n"; dbgs() << "Trying to continue loop-depth = " << getLoopDepth(ContLoop) << " from loop-depth = " << getLoopDepth(ContingLoop) << "\n";; } } while (0) |
1478 | << " from loop-depth = " << getLoopDepth(ContingLoop) << "\n";)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "loopcontPattern cont = BB" << ContingMBB->getNumber() << " header = BB" << ContMBB ->getNumber() << "\n"; dbgs() << "Trying to continue loop-depth = " << getLoopDepth(ContLoop) << " from loop-depth = " << getLoopDepth(ContingLoop) << "\n";; } } while (0); |
1479 | settleLoopcontBlock(ContingMBB, ContMBB); |
1480 | } |
1481 | |
1482 | void AMDGPUCFGStructurizer::mergeSerialBlock(MachineBasicBlock *DstMBB, |
1483 | MachineBasicBlock *SrcMBB) { |
1484 | DEBUG(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "serialPattern BB" << DstMBB ->getNumber() << " <= BB" << SrcMBB->getNumber () << "\n";; } } while (0) |
1485 | dbgs() << "serialPattern BB" << DstMBB->getNumber()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "serialPattern BB" << DstMBB ->getNumber() << " <= BB" << SrcMBB->getNumber () << "\n";; } } while (0) |
1486 | << " <= BB" << SrcMBB->getNumber() << "\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "serialPattern BB" << DstMBB ->getNumber() << " <= BB" << SrcMBB->getNumber () << "\n";; } } while (0) |
1487 | )do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "serialPattern BB" << DstMBB ->getNumber() << " <= BB" << SrcMBB->getNumber () << "\n";; } } while (0); |
1488 | DstMBB->splice(DstMBB->end(), SrcMBB, SrcMBB->begin(), SrcMBB->end()); |
1489 | |
1490 | DstMBB->removeSuccessor(SrcMBB); |
1491 | cloneSuccessorList(DstMBB, SrcMBB); |
1492 | |
1493 | removeSuccessor(SrcMBB); |
1494 | MLI->removeBlock(SrcMBB); |
1495 | retireBlock(SrcMBB); |
1496 | } |
1497 | |
1498 | void AMDGPUCFGStructurizer::mergeIfthenelseBlock(MachineInstr *BranchMI, |
1499 | MachineBasicBlock *MBB, MachineBasicBlock *TrueMBB, |
1500 | MachineBasicBlock *FalseMBB, MachineBasicBlock *LandMBB) { |
1501 | assert (TrueMBB)((TrueMBB) ? static_cast<void> (0) : __assert_fail ("TrueMBB" , "/tmp/buildd/llvm-toolchain-snapshot-3.7~svn240924/lib/Target/AMDGPU/AMDILCFGStructurizer.cpp" , 1501, __PRETTY_FUNCTION__)); |
1502 | DEBUG(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "ifPattern BB" << MBB-> getNumber(); dbgs() << "{ "; if (TrueMBB) { dbgs() << "BB" << TrueMBB->getNumber(); } dbgs() << " } else " ; dbgs() << "{ "; if (FalseMBB) { dbgs() << "BB" << FalseMBB->getNumber(); } dbgs() << " }\n " ; dbgs() << "landBlock: "; if (!LandMBB) { dbgs() << "NULL"; } else { dbgs() << "BB" << LandMBB->getNumber (); } dbgs() << "\n";; } } while (0) |
1503 | dbgs() << "ifPattern BB" << MBB->getNumber();do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "ifPattern BB" << MBB-> getNumber(); dbgs() << "{ "; if (TrueMBB) { dbgs() << "BB" << TrueMBB->getNumber(); } dbgs() << " } else " ; dbgs() << "{ "; if (FalseMBB) { dbgs() << "BB" << FalseMBB->getNumber(); } dbgs() << " }\n " ; dbgs() << "landBlock: "; if (!LandMBB) { dbgs() << "NULL"; } else { dbgs() << "BB" << LandMBB->getNumber (); } dbgs() << "\n";; } } while (0) |
1504 | dbgs() << "{ ";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "ifPattern BB" << MBB-> getNumber(); dbgs() << "{ "; if (TrueMBB) { dbgs() << "BB" << TrueMBB->getNumber(); } dbgs() << " } else " ; dbgs() << "{ "; if (FalseMBB) { dbgs() << "BB" << FalseMBB->getNumber(); } dbgs() << " }\n " ; dbgs() << "landBlock: "; if (!LandMBB) { dbgs() << "NULL"; } else { dbgs() << "BB" << LandMBB->getNumber (); } dbgs() << "\n";; } } while (0) |
1505 | if (TrueMBB) {do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "ifPattern BB" << MBB-> getNumber(); dbgs() << "{ "; if (TrueMBB) { dbgs() << "BB" << TrueMBB->getNumber(); } dbgs() << " } else " ; dbgs() << "{ "; if (FalseMBB) { dbgs() << "BB" << FalseMBB->getNumber(); } dbgs() << " }\n " ; dbgs() << "landBlock: "; if (!LandMBB) { dbgs() << "NULL"; } else { dbgs() << "BB" << LandMBB->getNumber (); } dbgs() << "\n";; } } while (0) |
1506 | dbgs() << "BB" << TrueMBB->getNumber();do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "ifPattern BB" << MBB-> getNumber(); dbgs() << "{ "; if (TrueMBB) { dbgs() << "BB" << TrueMBB->getNumber(); } dbgs() << " } else " ; dbgs() << "{ "; if (FalseMBB) { dbgs() << "BB" << FalseMBB->getNumber(); } dbgs() << " }\n " ; dbgs() << "landBlock: "; if (!LandMBB) { dbgs() << "NULL"; } else { dbgs() << "BB" << LandMBB->getNumber (); } dbgs() << "\n";; } } while (0) |
1507 | }do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "ifPattern BB" << MBB-> getNumber(); dbgs() << "{ "; if (TrueMBB) { dbgs() << "BB" << TrueMBB->getNumber(); } dbgs() << " } else " ; dbgs() << "{ "; if (FalseMBB) { dbgs() << "BB" << FalseMBB->getNumber(); } dbgs() << " }\n " ; dbgs() << "landBlock: "; if (!LandMBB) { dbgs() << "NULL"; } else { dbgs() << "BB" << LandMBB->getNumber (); } dbgs() << "\n";; } } while (0) |
1508 | dbgs() << " } else ";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "ifPattern BB" << MBB-> getNumber(); dbgs() << "{ "; if (TrueMBB) { dbgs() << "BB" << TrueMBB->getNumber(); } dbgs() << " } else " ; dbgs() << "{ "; if (FalseMBB) { dbgs() << "BB" << FalseMBB->getNumber(); } dbgs() << " }\n " ; dbgs() << "landBlock: "; if (!LandMBB) { dbgs() << "NULL"; } else { dbgs() << "BB" << LandMBB->getNumber (); } dbgs() << "\n";; } } while (0) |
1509 | dbgs() << "{ ";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "ifPattern BB" << MBB-> getNumber(); dbgs() << "{ "; if (TrueMBB) { dbgs() << "BB" << TrueMBB->getNumber(); } dbgs() << " } else " ; dbgs() << "{ "; if (FalseMBB) { dbgs() << "BB" << FalseMBB->getNumber(); } dbgs() << " }\n " ; dbgs() << "landBlock: "; if (!LandMBB) { dbgs() << "NULL"; } else { dbgs() << "BB" << LandMBB->getNumber (); } dbgs() << "\n";; } } while (0) |
1510 | if (FalseMBB) {do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "ifPattern BB" << MBB-> getNumber(); dbgs() << "{ "; if (TrueMBB) { dbgs() << "BB" << TrueMBB->getNumber(); } dbgs() << " } else " ; dbgs() << "{ "; if (FalseMBB) { dbgs() << "BB" << FalseMBB->getNumber(); } dbgs() << " }\n " ; dbgs() << "landBlock: "; if (!LandMBB) { dbgs() << "NULL"; } else { dbgs() << "BB" << LandMBB->getNumber (); } dbgs() << "\n";; } } while (0) |
1511 | dbgs() << "BB" << FalseMBB->getNumber();do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "ifPattern BB" << MBB-> getNumber(); dbgs() << "{ "; if (TrueMBB) { dbgs() << "BB" << TrueMBB->getNumber(); } dbgs() << " } else " ; dbgs() << "{ "; if (FalseMBB) { dbgs() << "BB" << FalseMBB->getNumber(); } dbgs() << " }\n " ; dbgs() << "landBlock: "; if (!LandMBB) { dbgs() << "NULL"; } else { dbgs() << "BB" << LandMBB->getNumber (); } dbgs() << "\n";; } } while (0) |
1512 | }do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "ifPattern BB" << MBB-> getNumber(); dbgs() << "{ "; if (TrueMBB) { dbgs() << "BB" << TrueMBB->getNumber(); } dbgs() << " } else " ; dbgs() << "{ "; if (FalseMBB) { dbgs() << "BB" << FalseMBB->getNumber(); } dbgs() << " }\n " ; dbgs() << "landBlock: "; if (!LandMBB) { dbgs() << "NULL"; } else { dbgs() << "BB" << LandMBB->getNumber (); } dbgs() << "\n";; } } while (0) |
1513 | dbgs() << " }\n ";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "ifPattern BB" << MBB-> getNumber(); dbgs() << "{ "; if (TrueMBB) { dbgs() << "BB" << TrueMBB->getNumber(); } dbgs() << " } else " ; dbgs() << "{ "; if (FalseMBB) { dbgs() << "BB" << FalseMBB->getNumber(); } dbgs() << " }\n " ; dbgs() << "landBlock: "; if (!LandMBB) { dbgs() << "NULL"; } else { dbgs() << "BB" << LandMBB->getNumber (); } dbgs() << "\n";; } } while (0) |
1514 | dbgs() << "landBlock: ";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "ifPattern BB" << MBB-> getNumber(); dbgs() << "{ "; if (TrueMBB) { dbgs() << "BB" << TrueMBB->getNumber(); } dbgs() << " } else " ; dbgs() << "{ "; if (FalseMBB) { dbgs() << "BB" << FalseMBB->getNumber(); } dbgs() << " }\n " ; dbgs() << "landBlock: "; if (!LandMBB) { dbgs() << "NULL"; } else { dbgs() << "BB" << LandMBB->getNumber (); } dbgs() << "\n";; } } while (0) |
1515 | if (!LandMBB) {do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "ifPattern BB" << MBB-> getNumber(); dbgs() << "{ "; if (TrueMBB) { dbgs() << "BB" << TrueMBB->getNumber(); } dbgs() << " } else " ; dbgs() << "{ "; if (FalseMBB) { dbgs() << "BB" << FalseMBB->getNumber(); } dbgs() << " }\n " ; dbgs() << "landBlock: "; if (!LandMBB) { dbgs() << "NULL"; } else { dbgs() << "BB" << LandMBB->getNumber (); } dbgs() << "\n";; } } while (0) |
1516 | dbgs() << "NULL";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "ifPattern BB" << MBB-> getNumber(); dbgs() << "{ "; if (TrueMBB) { dbgs() << "BB" << TrueMBB->getNumber(); } dbgs() << " } else " ; dbgs() << "{ "; if (FalseMBB) { dbgs() << "BB" << FalseMBB->getNumber(); } dbgs() << " }\n " ; dbgs() << "landBlock: "; if (!LandMBB) { dbgs() << "NULL"; } else { dbgs() << "BB" << LandMBB->getNumber (); } dbgs() << "\n";; } } while (0) |
1517 | } else {do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "ifPattern BB" << MBB-> getNumber(); dbgs() << "{ "; if (TrueMBB) { dbgs() << "BB" << TrueMBB->getNumber(); } dbgs() << " } else " ; dbgs() << "{ "; if (FalseMBB) { dbgs() << "BB" << FalseMBB->getNumber(); } dbgs() << " }\n " ; dbgs() << "landBlock: "; if (!LandMBB) { dbgs() << "NULL"; } else { dbgs() << "BB" << LandMBB->getNumber (); } dbgs() << "\n";; } } while (0) |
1518 | dbgs() << "BB" << LandMBB->getNumber();do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "ifPattern BB" << MBB-> getNumber(); dbgs() << "{ "; if (TrueMBB) { dbgs() << "BB" << TrueMBB->getNumber(); } dbgs() << " } else " ; dbgs() << "{ "; if (FalseMBB) { dbgs() << "BB" << FalseMBB->getNumber(); } dbgs() << " }\n " ; dbgs() << "landBlock: "; if (!LandMBB) { dbgs() << "NULL"; } else { dbgs() << "BB" << LandMBB->getNumber (); } dbgs() << "\n";; } } while (0) |
1519 | }do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "ifPattern BB" << MBB-> getNumber(); dbgs() << "{ "; if (TrueMBB) { dbgs() << "BB" << TrueMBB->getNumber(); } dbgs() << " } else " ; dbgs() << "{ "; if (FalseMBB) { dbgs() << "BB" << FalseMBB->getNumber(); } dbgs() << " }\n " ; dbgs() << "landBlock: "; if (!LandMBB) { dbgs() << "NULL"; } else { dbgs() << "BB" << LandMBB->getNumber (); } dbgs() << "\n";; } } while (0) |
1520 | dbgs() << "\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "ifPattern BB" << MBB-> getNumber(); dbgs() << "{ "; if (TrueMBB) { dbgs() << "BB" << TrueMBB->getNumber(); } dbgs() << " } else " ; dbgs() << "{ "; if (FalseMBB) { dbgs() << "BB" << FalseMBB->getNumber(); } dbgs() << " }\n " ; dbgs() << "landBlock: "; if (!LandMBB) { dbgs() << "NULL"; } else { dbgs() << "BB" << LandMBB->getNumber (); } dbgs() << "\n";; } } while (0) |
1521 | )do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "ifPattern BB" << MBB-> getNumber(); dbgs() << "{ "; if (TrueMBB) { dbgs() << "BB" << TrueMBB->getNumber(); } dbgs() << " } else " ; dbgs() << "{ "; if (FalseMBB) { dbgs() << "BB" << FalseMBB->getNumber(); } dbgs() << " }\n " ; dbgs() << "landBlock: "; if (!LandMBB) { dbgs() << "NULL"; } else { dbgs() << "BB" << LandMBB->getNumber (); } dbgs() << "\n";; } } while (0); |
1522 | |
1523 | int OldOpcode = BranchMI->getOpcode(); |
1524 | DebugLoc BranchDL = BranchMI->getDebugLoc(); |
1525 | |
1526 | // transform to |
1527 | // if cond |
1528 | // trueBlk |
1529 | // else |
1530 | // falseBlk |
1531 | // endif |
1532 | // landBlk |
1533 | |
1534 | MachineBasicBlock::iterator I = BranchMI; |
1535 | insertCondBranchBefore(I, getBranchNzeroOpcode(OldOpcode), |
1536 | BranchDL); |
1537 | |
1538 | if (TrueMBB) { |
1539 | MBB->splice(I, TrueMBB, TrueMBB->begin(), TrueMBB->end()); |
1540 | MBB->removeSuccessor(TrueMBB); |
1541 | if (LandMBB && TrueMBB->succ_size()!=0) |
1542 | TrueMBB->removeSuccessor(LandMBB); |
1543 | retireBlock(TrueMBB); |
1544 | MLI->removeBlock(TrueMBB); |
1545 | } |
1546 | |
1547 | if (FalseMBB) { |
1548 | insertInstrBefore(I, AMDGPU::ELSE); |
1549 | MBB->splice(I, FalseMBB, FalseMBB->begin(), |
1550 | FalseMBB->end()); |
1551 | MBB->removeSuccessor(FalseMBB); |
1552 | if (LandMBB && FalseMBB->succ_size() != 0) |
1553 | FalseMBB->removeSuccessor(LandMBB); |
1554 | retireBlock(FalseMBB); |
1555 | MLI->removeBlock(FalseMBB); |
1556 | } |
1557 | insertInstrBefore(I, AMDGPU::ENDIF); |
1558 | |
1559 | BranchMI->eraseFromParent(); |
1560 | |
1561 | if (LandMBB && TrueMBB && FalseMBB) |
1562 | MBB->addSuccessor(LandMBB); |
1563 | |
1564 | } |
1565 | |
1566 | void AMDGPUCFGStructurizer::mergeLooplandBlock(MachineBasicBlock *DstBlk, |
1567 | MachineBasicBlock *LandMBB) { |
1568 | DEBUG(dbgs() << "loopPattern header = BB" << DstBlk->getNumber()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "loopPattern header = BB" << DstBlk->getNumber() << " land = BB" << LandMBB ->getNumber() << "\n";; } } while (0) |
1569 | << " land = BB" << LandMBB->getNumber() << "\n";)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "loopPattern header = BB" << DstBlk->getNumber() << " land = BB" << LandMBB ->getNumber() << "\n";; } } while (0); |
1570 | |
1571 | insertInstrBefore(DstBlk, AMDGPU::WHILELOOP, DebugLoc()); |
1572 | insertInstrEnd(DstBlk, AMDGPU::ENDLOOP, DebugLoc()); |
1573 | DstBlk->addSuccessor(LandMBB); |
1574 | DstBlk->removeSuccessor(DstBlk); |
1575 | } |
1576 | |
1577 | |
1578 | void AMDGPUCFGStructurizer::mergeLoopbreakBlock(MachineBasicBlock *ExitingMBB, |
1579 | MachineBasicBlock *LandMBB) { |
1580 | DEBUG(dbgs() << "loopbreakPattern exiting = BB" << ExitingMBB->getNumber()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "loopbreakPattern exiting = BB" << ExitingMBB->getNumber() << " land = BB" << LandMBB->getNumber() << "\n";; } } while (0) |
1581 | << " land = BB" << LandMBB->getNumber() << "\n";)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "loopbreakPattern exiting = BB" << ExitingMBB->getNumber() << " land = BB" << LandMBB->getNumber() << "\n";; } } while (0); |
1582 | MachineInstr *BranchMI = getLoopendBlockBranchInstr(ExitingMBB); |
1583 | assert(BranchMI && isCondBranch(BranchMI))((BranchMI && isCondBranch(BranchMI)) ? static_cast< void> (0) : __assert_fail ("BranchMI && isCondBranch(BranchMI)" , "/tmp/buildd/llvm-toolchain-snapshot-3.7~svn240924/lib/Target/AMDGPU/AMDILCFGStructurizer.cpp" , 1583, __PRETTY_FUNCTION__)); |
1584 | DebugLoc DL = BranchMI->getDebugLoc(); |
1585 | MachineBasicBlock *TrueBranch = getTrueBranch(BranchMI); |
1586 | MachineBasicBlock::iterator I = BranchMI; |
1587 | if (TrueBranch != LandMBB) |
1588 | reversePredicateSetter(I); |
1589 | insertCondBranchBefore(ExitingMBB, I, AMDGPU::IF_PREDICATE_SET, AMDGPU::PREDICATE_BIT, DL); |
1590 | insertInstrBefore(I, AMDGPU::BREAK); |
1591 | insertInstrBefore(I, AMDGPU::ENDIF); |
1592 | //now branchInst can be erase safely |
1593 | BranchMI->eraseFromParent(); |
1594 | //now take care of successors, retire blocks |
1595 | ExitingMBB->removeSuccessor(LandMBB); |
1596 | } |
1597 | |
1598 | void AMDGPUCFGStructurizer::settleLoopcontBlock(MachineBasicBlock *ContingMBB, |
1599 | MachineBasicBlock *ContMBB) { |
1600 | DEBUG(dbgs() << "settleLoopcontBlock conting = BB"do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "settleLoopcontBlock conting = BB" << ContingMBB->getNumber() << ", cont = BB" << ContMBB->getNumber() << "\n";; } } while (0) |
1601 | << ContingMBB->getNumber()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "settleLoopcontBlock conting = BB" << ContingMBB->getNumber() << ", cont = BB" << ContMBB->getNumber() << "\n";; } } while (0) |
1602 | << ", cont = BB" << ContMBB->getNumber() << "\n";)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "settleLoopcontBlock conting = BB" << ContingMBB->getNumber() << ", cont = BB" << ContMBB->getNumber() << "\n";; } } while (0); |
1603 | |
1604 | MachineInstr *MI = getLoopendBlockBranchInstr(ContingMBB); |
1605 | if (MI) { |
1606 | assert(isCondBranch(MI))((isCondBranch(MI)) ? static_cast<void> (0) : __assert_fail ("isCondBranch(MI)", "/tmp/buildd/llvm-toolchain-snapshot-3.7~svn240924/lib/Target/AMDGPU/AMDILCFGStructurizer.cpp" , 1606, __PRETTY_FUNCTION__)); |
1607 | MachineBasicBlock::iterator I = MI; |
1608 | MachineBasicBlock *TrueBranch = getTrueBranch(MI); |
1609 | int OldOpcode = MI->getOpcode(); |
1610 | DebugLoc DL = MI->getDebugLoc(); |
1611 | |
1612 | bool UseContinueLogical = ((&*ContingMBB->rbegin()) == MI); |
1613 | |
1614 | if (!UseContinueLogical) { |
1615 | int BranchOpcode = |
1616 | TrueBranch == ContMBB ? getBranchNzeroOpcode(OldOpcode) : |
1617 | getBranchZeroOpcode(OldOpcode); |
1618 | insertCondBranchBefore(I, BranchOpcode, DL); |
1619 | // insertEnd to ensure phi-moves, if exist, go before the continue-instr. |
1620 | insertInstrEnd(ContingMBB, AMDGPU::CONTINUE, DL); |
1621 | insertInstrEnd(ContingMBB, AMDGPU::ENDIF, DL); |
1622 | } else { |
1623 | int BranchOpcode = |
1624 | TrueBranch == ContMBB ? getContinueNzeroOpcode(OldOpcode) : |
1625 | getContinueZeroOpcode(OldOpcode); |
1626 | insertCondBranchBefore(I, BranchOpcode, DL); |
1627 | } |
1628 | |
1629 | MI->eraseFromParent(); |
1630 | } else { |
1631 | // if we've arrived here then we've already erased the branch instruction |
1632 | // travel back up the basic block to see the last reference of our debug |
1633 | // location we've just inserted that reference here so it should be |
1634 | // representative insertEnd to ensure phi-moves, if exist, go before the |
1635 | // continue-instr. |
1636 | insertInstrEnd(ContingMBB, AMDGPU::CONTINUE, |
1637 | getLastDebugLocInBB(ContingMBB)); |
1638 | } |
1639 | } |
1640 | |
1641 | int AMDGPUCFGStructurizer::cloneOnSideEntryTo(MachineBasicBlock *PreMBB, |
1642 | MachineBasicBlock *SrcMBB, MachineBasicBlock *DstMBB) { |
1643 | int Cloned = 0; |
1644 | assert(PreMBB->isSuccessor(SrcMBB))((PreMBB->isSuccessor(SrcMBB)) ? static_cast<void> ( 0) : __assert_fail ("PreMBB->isSuccessor(SrcMBB)", "/tmp/buildd/llvm-toolchain-snapshot-3.7~svn240924/lib/Target/AMDGPU/AMDILCFGStructurizer.cpp" , 1644, __PRETTY_FUNCTION__)); |
1645 | while (SrcMBB && SrcMBB != DstMBB) { |
1646 | assert(SrcMBB->succ_size() == 1)((SrcMBB->succ_size() == 1) ? static_cast<void> (0) : __assert_fail ("SrcMBB->succ_size() == 1", "/tmp/buildd/llvm-toolchain-snapshot-3.7~svn240924/lib/Target/AMDGPU/AMDILCFGStructurizer.cpp" , 1646, __PRETTY_FUNCTION__)); |
1647 | if (SrcMBB->pred_size() > 1) { |
1648 | SrcMBB = cloneBlockForPredecessor(SrcMBB, PreMBB); |
1649 | ++Cloned; |
1650 | } |
1651 | |
1652 | PreMBB = SrcMBB; |
1653 | SrcMBB = *SrcMBB->succ_begin(); |
1654 | } |
1655 | |
1656 | return Cloned; |
1657 | } |
1658 | |
1659 | MachineBasicBlock * |
1660 | AMDGPUCFGStructurizer::cloneBlockForPredecessor(MachineBasicBlock *MBB, |
1661 | MachineBasicBlock *PredMBB) { |
1662 | assert(PredMBB->isSuccessor(MBB) &&((PredMBB->isSuccessor(MBB) && "succBlk is not a prececessor of curBlk" ) ? static_cast<void> (0) : __assert_fail ("PredMBB->isSuccessor(MBB) && \"succBlk is not a prececessor of curBlk\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.7~svn240924/lib/Target/AMDGPU/AMDILCFGStructurizer.cpp" , 1663, __PRETTY_FUNCTION__)) |
1663 | "succBlk is not a prececessor of curBlk")((PredMBB->isSuccessor(MBB) && "succBlk is not a prececessor of curBlk" ) ? static_cast<void> (0) : __assert_fail ("PredMBB->isSuccessor(MBB) && \"succBlk is not a prececessor of curBlk\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.7~svn240924/lib/Target/AMDGPU/AMDILCFGStructurizer.cpp" , 1663, __PRETTY_FUNCTION__)); |
1664 | |
1665 | MachineBasicBlock *CloneMBB = clone(MBB); //clone instructions |
1666 | replaceInstrUseOfBlockWith(PredMBB, MBB, CloneMBB); |
1667 | //srcBlk, oldBlk, newBlk |
1668 | |
1669 | PredMBB->removeSuccessor(MBB); |
1670 | PredMBB->addSuccessor(CloneMBB); |
1671 | |
1672 | // add all successor to cloneBlk |
1673 | cloneSuccessorList(CloneMBB, MBB); |
1674 | |
1675 | numClonedInstr += MBB->size(); |
1676 | |
1677 | DEBUG(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "Cloned block: " << "BB" << MBB->getNumber() << "size " << MBB-> size() << "\n";; } } while (0) |
1678 | dbgs() << "Cloned block: " << "BB"do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "Cloned block: " << "BB" << MBB->getNumber() << "size " << MBB-> size() << "\n";; } } while (0) |
1679 | << MBB->getNumber() << "size " << MBB->size() << "\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "Cloned block: " << "BB" << MBB->getNumber() << "size " << MBB-> size() << "\n";; } } while (0) |
1680 | )do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "Cloned block: " << "BB" << MBB->getNumber() << "size " << MBB-> size() << "\n";; } } while (0); |
1681 | |
1682 | SHOWNEWBLK(CloneMBB, "result of Cloned block: ")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "result of Cloned block: " << "BB" << CloneMBB->getNumber() << "size " << CloneMBB->size(); dbgs() << "\n";; } } while (0);; |
1683 | |
1684 | return CloneMBB; |
1685 | } |
1686 | |
1687 | void AMDGPUCFGStructurizer::migrateInstruction(MachineBasicBlock *SrcMBB, |
1688 | MachineBasicBlock *DstMBB, MachineBasicBlock::iterator I) { |
1689 | MachineBasicBlock::iterator SpliceEnd; |
1690 | //look for the input branchinstr, not the AMDGPU branchinstr |
1691 | MachineInstr *BranchMI = getNormalBlockBranchInstr(SrcMBB); |
1692 | if (!BranchMI) { |
1693 | DEBUG(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "migrateInstruction don't see branch instr\n" ;; } } while (0) |
1694 | dbgs() << "migrateInstruction don't see branch instr\n" ;do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "migrateInstruction don't see branch instr\n" ;; } } while (0) |
1695 | )do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "migrateInstruction don't see branch instr\n" ;; } } while (0); |
1696 | SpliceEnd = SrcMBB->end(); |
1697 | } else { |
1698 | DEBUG(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "migrateInstruction see branch instr\n" ; BranchMI->dump();; } } while (0) |
1699 | dbgs() << "migrateInstruction see branch instr\n" ;do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "migrateInstruction see branch instr\n" ; BranchMI->dump();; } } while (0) |
1700 | BranchMI->dump();do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "migrateInstruction see branch instr\n" ; BranchMI->dump();; } } while (0) |
1701 | )do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "migrateInstruction see branch instr\n" ; BranchMI->dump();; } } while (0); |
1702 | SpliceEnd = BranchMI; |
1703 | } |
1704 | DEBUG(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "migrateInstruction before splice dstSize = " << DstMBB->size() << "srcSize = " << SrcMBB ->size() << "\n";; } } while (0) |
1705 | dbgs() << "migrateInstruction before splice dstSize = " << DstMBB->size()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "migrateInstruction before splice dstSize = " << DstMBB->size() << "srcSize = " << SrcMBB ->size() << "\n";; } } while (0) |
1706 | << "srcSize = " << SrcMBB->size() << "\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "migrateInstruction before splice dstSize = " << DstMBB->size() << "srcSize = " << SrcMBB ->size() << "\n";; } } while (0) |
1707 | )do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "migrateInstruction before splice dstSize = " << DstMBB->size() << "srcSize = " << SrcMBB ->size() << "\n";; } } while (0); |
1708 | |
1709 | //splice insert before insertPos |
1710 | DstMBB->splice(I, SrcMBB, SrcMBB->begin(), SpliceEnd); |
1711 | |
1712 | DEBUG(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "migrateInstruction after splice dstSize = " << DstMBB->size() << "srcSize = " << SrcMBB ->size() << "\n";; } } while (0) |
1713 | dbgs() << "migrateInstruction after splice dstSize = " << DstMBB->size()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "migrateInstruction after splice dstSize = " << DstMBB->size() << "srcSize = " << SrcMBB ->size() << "\n";; } } while (0) |
1714 | << "srcSize = " << SrcMBB->size() << "\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "migrateInstruction after splice dstSize = " << DstMBB->size() << "srcSize = " << SrcMBB ->size() << "\n";; } } while (0) |
1715 | )do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "migrateInstruction after splice dstSize = " << DstMBB->size() << "srcSize = " << SrcMBB ->size() << "\n";; } } while (0); |
1716 | } |
1717 | |
1718 | MachineBasicBlock * |
1719 | AMDGPUCFGStructurizer::normalizeInfiniteLoopExit(MachineLoop* LoopRep) { |
1720 | MachineBasicBlock *LoopHeader = LoopRep->getHeader(); |
1721 | MachineBasicBlock *LoopLatch = LoopRep->getLoopLatch(); |
1722 | const TargetRegisterClass * I32RC = TRI->getCFGStructurizerRegClass(MVT::i32); |
1723 | |
1724 | if (!LoopHeader || !LoopLatch) |
1725 | return nullptr; |
1726 | MachineInstr *BranchMI = getLoopendBlockBranchInstr(LoopLatch); |
1727 | // Is LoopRep an infinite loop ? |
1728 | if (!BranchMI || !isUncondBranch(BranchMI)) |
1729 | return nullptr; |
1730 | |
1731 | MachineBasicBlock *DummyExitBlk = FuncRep->CreateMachineBasicBlock(); |
1732 | FuncRep->push_back(DummyExitBlk); //insert to function |
1733 | SHOWNEWBLK(DummyExitBlk, "DummyExitBlock to normalize infiniteLoop: ")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "DummyExitBlock to normalize infiniteLoop: " << "BB" << DummyExitBlk->getNumber() << "size " << DummyExitBlk->size(); dbgs() << "\n" ;; } } while (0);; |
1734 | DEBUG(dbgs() << "Old branch instr: " << *BranchMI << "\n";)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "Old branch instr: " << *BranchMI << "\n";; } } while (0); |
1735 | MachineBasicBlock::iterator I = BranchMI; |
1736 | unsigned ImmReg = FuncRep->getRegInfo().createVirtualRegister(I32RC); |
Value stored to 'ImmReg' during its initialization is never read | |
1737 | llvm_unreachable("Extra register needed to handle CFG")::llvm::llvm_unreachable_internal("Extra register needed to handle CFG" , "/tmp/buildd/llvm-toolchain-snapshot-3.7~svn240924/lib/Target/AMDGPU/AMDILCFGStructurizer.cpp" , 1737); |
1738 | MachineInstr *NewMI = insertInstrBefore(I, AMDGPU::BRANCH_COND_i32); |
1739 | MachineInstrBuilder MIB(*FuncRep, NewMI); |
1740 | MIB.addMBB(LoopHeader); |
1741 | MIB.addReg(ImmReg, false); |
1742 | SHOWNEWINSTR(NewMI)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "New instr: " << *NewMI << "\n"; } } while (0);; |
1743 | BranchMI->eraseFromParent(); |
1744 | LoopLatch->addSuccessor(DummyExitBlk); |
1745 | |
1746 | return DummyExitBlk; |
1747 | } |
1748 | |
1749 | void AMDGPUCFGStructurizer::removeUnconditionalBranch(MachineBasicBlock *MBB) { |
1750 | MachineInstr *BranchMI; |
1751 | |
1752 | // I saw two unconditional branch in one basic block in example |
1753 | // test_fc_do_while_or.c need to fix the upstream on this to remove the loop. |
1754 | while ((BranchMI = getLoopendBlockBranchInstr(MBB)) |
1755 | && isUncondBranch(BranchMI)) { |
1756 | DEBUG(dbgs() << "Removing uncond branch instr"; BranchMI->dump();)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "Removing uncond branch instr" ; BranchMI->dump();; } } while (0); |
1757 | BranchMI->eraseFromParent(); |
1758 | } |
1759 | } |
1760 | |
1761 | void AMDGPUCFGStructurizer::removeRedundantConditionalBranch( |
1762 | MachineBasicBlock *MBB) { |
1763 | if (MBB->succ_size() != 2) |
1764 | return; |
1765 | MachineBasicBlock *MBB1 = *MBB->succ_begin(); |
1766 | MachineBasicBlock *MBB2 = *std::next(MBB->succ_begin()); |
1767 | if (MBB1 != MBB2) |
1768 | return; |
1769 | |
1770 | MachineInstr *BranchMI = getNormalBlockBranchInstr(MBB); |
1771 | assert(BranchMI && isCondBranch(BranchMI))((BranchMI && isCondBranch(BranchMI)) ? static_cast< void> (0) : __assert_fail ("BranchMI && isCondBranch(BranchMI)" , "/tmp/buildd/llvm-toolchain-snapshot-3.7~svn240924/lib/Target/AMDGPU/AMDILCFGStructurizer.cpp" , 1771, __PRETTY_FUNCTION__)); |
1772 | DEBUG(dbgs() << "Removing unneeded cond branch instr"; BranchMI->dump();)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "Removing unneeded cond branch instr" ; BranchMI->dump();; } } while (0); |
1773 | BranchMI->eraseFromParent(); |
1774 | SHOWNEWBLK(MBB1, "Removing redundant successor")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "Removing redundant successor" << "BB" << MBB1->getNumber() << "size " << MBB1->size(); dbgs() << "\n";; } } while ( 0);; |
1775 | MBB->removeSuccessor(MBB1); |
1776 | } |
1777 | |
1778 | void AMDGPUCFGStructurizer::addDummyExitBlock( |
1779 | SmallVectorImpl<MachineBasicBlock*> &RetMBB) { |
1780 | MachineBasicBlock *DummyExitBlk = FuncRep->CreateMachineBasicBlock(); |
1781 | FuncRep->push_back(DummyExitBlk); //insert to function |
1782 | insertInstrEnd(DummyExitBlk, AMDGPU::RETURN); |
1783 | |
1784 | for (SmallVectorImpl<MachineBasicBlock *>::iterator It = RetMBB.begin(), |
1785 | E = RetMBB.end(); It != E; ++It) { |
1786 | MachineBasicBlock *MBB = *It; |
1787 | MachineInstr *MI = getReturnInstr(MBB); |
1788 | if (MI) |
1789 | MI->eraseFromParent(); |
1790 | MBB->addSuccessor(DummyExitBlk); |
1791 | DEBUG(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "Add dummyExitBlock to BB" << MBB->getNumber() << " successors\n";; } } while (0) |
1792 | dbgs() << "Add dummyExitBlock to BB" << MBB->getNumber()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "Add dummyExitBlock to BB" << MBB->getNumber() << " successors\n";; } } while (0) |
1793 | << " successors\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "Add dummyExitBlock to BB" << MBB->getNumber() << " successors\n";; } } while (0) |
1794 | )do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "Add dummyExitBlock to BB" << MBB->getNumber() << " successors\n";; } } while (0); |
1795 | } |
1796 | SHOWNEWBLK(DummyExitBlk, "DummyExitBlock: ")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "DummyExitBlock: " << "BB" << DummyExitBlk->getNumber() << "size " << DummyExitBlk->size(); dbgs() << "\n";; } } while (0 );; |
1797 | } |
1798 | |
1799 | void AMDGPUCFGStructurizer::removeSuccessor(MachineBasicBlock *MBB) { |
1800 | while (MBB->succ_size()) |
1801 | MBB->removeSuccessor(*MBB->succ_begin()); |
1802 | } |
1803 | |
1804 | void AMDGPUCFGStructurizer::recordSccnum(MachineBasicBlock *MBB, |
1805 | int SccNum) { |
1806 | BlockInformation *&srcBlkInfo = BlockInfoMap[MBB]; |
1807 | if (!srcBlkInfo) |
1808 | srcBlkInfo = new BlockInformation(); |
1809 | srcBlkInfo->SccNum = SccNum; |
1810 | } |
1811 | |
1812 | void AMDGPUCFGStructurizer::retireBlock(MachineBasicBlock *MBB) { |
1813 | DEBUG(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "Retiring BB" << MBB-> getNumber() << "\n";; } } while (0) |
1814 | dbgs() << "Retiring BB" << MBB->getNumber() << "\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "Retiring BB" << MBB-> getNumber() << "\n";; } } while (0) |
1815 | )do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "Retiring BB" << MBB-> getNumber() << "\n";; } } while (0); |
1816 | |
1817 | BlockInformation *&SrcBlkInfo = BlockInfoMap[MBB]; |
1818 | |
1819 | if (!SrcBlkInfo) |
1820 | SrcBlkInfo = new BlockInformation(); |
1821 | |
1822 | SrcBlkInfo->IsRetired = true; |
1823 | assert(MBB->succ_size() == 0 && MBB->pred_size() == 0((MBB->succ_size() == 0 && MBB->pred_size() == 0 && "can't retire block yet") ? static_cast<void> (0) : __assert_fail ("MBB->succ_size() == 0 && MBB->pred_size() == 0 && \"can't retire block yet\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.7~svn240924/lib/Target/AMDGPU/AMDILCFGStructurizer.cpp" , 1824, __PRETTY_FUNCTION__)) |
1824 | && "can't retire block yet")((MBB->succ_size() == 0 && MBB->pred_size() == 0 && "can't retire block yet") ? static_cast<void> (0) : __assert_fail ("MBB->succ_size() == 0 && MBB->pred_size() == 0 && \"can't retire block yet\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.7~svn240924/lib/Target/AMDGPU/AMDILCFGStructurizer.cpp" , 1824, __PRETTY_FUNCTION__)); |
1825 | } |
1826 | |
1827 | void AMDGPUCFGStructurizer::setLoopLandBlock(MachineLoop *loopRep, |
1828 | MachineBasicBlock *MBB) { |
1829 | MachineBasicBlock *&TheEntry = LLInfoMap[loopRep]; |
1830 | if (!MBB) { |
1831 | MBB = FuncRep->CreateMachineBasicBlock(); |
1832 | FuncRep->push_back(MBB); //insert to function |
1833 | SHOWNEWBLK(MBB, "DummyLandingBlock for loop without break: ")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "DummyLandingBlock for loop without break: " << "BB" << MBB->getNumber() << "size " << MBB->size(); dbgs() << "\n";; } } while (0);; |
1834 | } |
1835 | TheEntry = MBB; |
1836 | DEBUG(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "setLoopLandBlock loop-header = BB" << loopRep->getHeader()->getNumber() << " landing-block = BB" << MBB->getNumber() << "\n";; } } while (0) |
1837 | dbgs() << "setLoopLandBlock loop-header = BB"do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "setLoopLandBlock loop-header = BB" << loopRep->getHeader()->getNumber() << " landing-block = BB" << MBB->getNumber() << "\n";; } } while (0) |
1838 | << loopRep->getHeader()->getNumber()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "setLoopLandBlock loop-header = BB" << loopRep->getHeader()->getNumber() << " landing-block = BB" << MBB->getNumber() << "\n";; } } while (0) |
1839 | << " landing-block = BB" << MBB->getNumber() << "\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "setLoopLandBlock loop-header = BB" << loopRep->getHeader()->getNumber() << " landing-block = BB" << MBB->getNumber() << "\n";; } } while (0) |
1840 | )do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "setLoopLandBlock loop-header = BB" << loopRep->getHeader()->getNumber() << " landing-block = BB" << MBB->getNumber() << "\n";; } } while (0); |
1841 | } |
1842 | |
1843 | MachineBasicBlock * |
1844 | AMDGPUCFGStructurizer::findNearestCommonPostDom(MachineBasicBlock *MBB1, |
1845 | MachineBasicBlock *MBB2) { |
1846 | |
1847 | if (PDT->dominates(MBB1, MBB2)) |
1848 | return MBB1; |
1849 | if (PDT->dominates(MBB2, MBB1)) |
1850 | return MBB2; |
1851 | |
1852 | MachineDomTreeNode *Node1 = PDT->getNode(MBB1); |
1853 | MachineDomTreeNode *Node2 = PDT->getNode(MBB2); |
1854 | |
1855 | // Handle newly cloned node. |
1856 | if (!Node1 && MBB1->succ_size() == 1) |
1857 | return findNearestCommonPostDom(*MBB1->succ_begin(), MBB2); |
1858 | if (!Node2 && MBB2->succ_size() == 1) |
1859 | return findNearestCommonPostDom(MBB1, *MBB2->succ_begin()); |
1860 | |
1861 | if (!Node1 || !Node2) |
1862 | return nullptr; |
1863 | |
1864 | Node1 = Node1->getIDom(); |
1865 | while (Node1) { |
1866 | if (PDT->dominates(Node1, Node2)) |
1867 | return Node1->getBlock(); |
1868 | Node1 = Node1->getIDom(); |
1869 | } |
1870 | |
1871 | return nullptr; |
1872 | } |
1873 | |
1874 | MachineBasicBlock * |
1875 | AMDGPUCFGStructurizer::findNearestCommonPostDom( |
1876 | std::set<MachineBasicBlock *> &MBBs) { |
1877 | MachineBasicBlock *CommonDom; |
1878 | std::set<MachineBasicBlock *>::const_iterator It = MBBs.begin(); |
1879 | std::set<MachineBasicBlock *>::const_iterator E = MBBs.end(); |
1880 | for (CommonDom = *It; It != E && CommonDom; ++It) { |
1881 | MachineBasicBlock *MBB = *It; |
1882 | if (MBB != CommonDom) |
1883 | CommonDom = findNearestCommonPostDom(MBB, CommonDom); |
1884 | } |
1885 | |
1886 | DEBUG(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "Common post dominator for exit blocks is " ; if (CommonDom) dbgs() << "BB" << CommonDom-> getNumber() << "\n"; else dbgs() << "NULL\n";; } } while (0) |
1887 | dbgs() << "Common post dominator for exit blocks is ";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "Common post dominator for exit blocks is " ; if (CommonDom) dbgs() << "BB" << CommonDom-> getNumber() << "\n"; else dbgs() << "NULL\n";; } } while (0) |
1888 | if (CommonDom)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "Common post dominator for exit blocks is " ; if (CommonDom) dbgs() << "BB" << CommonDom-> getNumber() << "\n"; else dbgs() << "NULL\n";; } } while (0) |
1889 | dbgs() << "BB" << CommonDom->getNumber() << "\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "Common post dominator for exit blocks is " ; if (CommonDom) dbgs() << "BB" << CommonDom-> getNumber() << "\n"; else dbgs() << "NULL\n";; } } while (0) |
1890 | elsedo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "Common post dominator for exit blocks is " ; if (CommonDom) dbgs() << "BB" << CommonDom-> getNumber() << "\n"; else dbgs() << "NULL\n";; } } while (0) |
1891 | dbgs() << "NULL\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "Common post dominator for exit blocks is " ; if (CommonDom) dbgs() << "BB" << CommonDom-> getNumber() << "\n"; else dbgs() << "NULL\n";; } } while (0) |
1892 | )do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("structcfg")) { dbgs() << "Common post dominator for exit blocks is " ; if (CommonDom) dbgs() << "BB" << CommonDom-> getNumber() << "\n"; else dbgs() << "NULL\n";; } } while (0); |
1893 | |
1894 | return CommonDom; |
1895 | } |
1896 | |
1897 | char AMDGPUCFGStructurizer::ID = 0; |
1898 | |
1899 | } // end anonymous namespace |
1900 | |
1901 | |
1902 | INITIALIZE_PASS_BEGIN(AMDGPUCFGStructurizer, "amdgpustructurizer",static void* initializeAMDGPUCFGStructurizerPassOnce(PassRegistry &Registry) { |
1903 | "AMDGPU CFG Structurizer", false, false)static void* initializeAMDGPUCFGStructurizerPassOnce(PassRegistry &Registry) { |
1904 | INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)initializeMachineDominatorTreePass(Registry); |
1905 | INITIALIZE_PASS_DEPENDENCY(MachinePostDominatorTree)initializeMachinePostDominatorTreePass(Registry); |
1906 | INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo)initializeMachineLoopInfoPass(Registry); |
1907 | INITIALIZE_PASS_END(AMDGPUCFGStructurizer, "amdgpustructurizer",PassInfo *PI = new PassInfo("AMDGPU CFG Structurizer", "amdgpustructurizer" , & AMDGPUCFGStructurizer ::ID, PassInfo::NormalCtor_t(callDefaultCtor < AMDGPUCFGStructurizer >), false, false); Registry.registerPass (*PI, true); return PI; } void llvm::initializeAMDGPUCFGStructurizerPass (PassRegistry &Registry) { static volatile sys::cas_flag initialized = 0; sys::cas_flag old_val = sys::CompareAndSwap(&initialized , 1, 0); if (old_val == 0) { initializeAMDGPUCFGStructurizerPassOnce (Registry); sys::MemoryFence(); AnnotateIgnoreWritesBegin("/tmp/buildd/llvm-toolchain-snapshot-3.7~svn240924/lib/Target/AMDGPU/AMDILCFGStructurizer.cpp" , 1908); AnnotateHappensBefore("/tmp/buildd/llvm-toolchain-snapshot-3.7~svn240924/lib/Target/AMDGPU/AMDILCFGStructurizer.cpp" , 1908, &initialized); initialized = 2; AnnotateIgnoreWritesEnd ("/tmp/buildd/llvm-toolchain-snapshot-3.7~svn240924/lib/Target/AMDGPU/AMDILCFGStructurizer.cpp" , 1908); } else { sys::cas_flag tmp = initialized; sys::MemoryFence (); while (tmp != 2) { tmp = initialized; sys::MemoryFence(); } } AnnotateHappensAfter("/tmp/buildd/llvm-toolchain-snapshot-3.7~svn240924/lib/Target/AMDGPU/AMDILCFGStructurizer.cpp" , 1908, &initialized); } |
1908 | "AMDGPU CFG Structurizer", false, false)PassInfo *PI = new PassInfo("AMDGPU CFG Structurizer", "amdgpustructurizer" , & AMDGPUCFGStructurizer ::ID, PassInfo::NormalCtor_t(callDefaultCtor < AMDGPUCFGStructurizer >), false, false); Registry.registerPass (*PI, true); return PI; } void llvm::initializeAMDGPUCFGStructurizerPass (PassRegistry &Registry) { static volatile sys::cas_flag initialized = 0; sys::cas_flag old_val = sys::CompareAndSwap(&initialized , 1, 0); if (old_val == 0) { initializeAMDGPUCFGStructurizerPassOnce (Registry); sys::MemoryFence(); AnnotateIgnoreWritesBegin("/tmp/buildd/llvm-toolchain-snapshot-3.7~svn240924/lib/Target/AMDGPU/AMDILCFGStructurizer.cpp" , 1908); AnnotateHappensBefore("/tmp/buildd/llvm-toolchain-snapshot-3.7~svn240924/lib/Target/AMDGPU/AMDILCFGStructurizer.cpp" , 1908, &initialized); initialized = 2; AnnotateIgnoreWritesEnd ("/tmp/buildd/llvm-toolchain-snapshot-3.7~svn240924/lib/Target/AMDGPU/AMDILCFGStructurizer.cpp" , 1908); } else { sys::cas_flag tmp = initialized; sys::MemoryFence (); while (tmp != 2) { tmp = initialized; sys::MemoryFence(); } } AnnotateHappensAfter("/tmp/buildd/llvm-toolchain-snapshot-3.7~svn240924/lib/Target/AMDGPU/AMDILCFGStructurizer.cpp" , 1908, &initialized); } |
1909 | |
1910 | FunctionPass *llvm::createAMDGPUCFGStructurizerPass() { |
1911 | return new AMDGPUCFGStructurizer(); |
1912 | } |