16b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard//===-- AMDGPUStructurizeCFG.cpp - ------------------===// 26b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard// 36b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard// The LLVM Compiler Infrastructure 46b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard// 56b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard// This file is distributed under the University of Illinois Open Source 66b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard// License. See LICENSE.TXT for details. 76b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard// 86b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard//===----------------------------------------------------------------------===// 96b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard// 106b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard/// \file 116b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard/// The pass implemented in this file transforms the programs control flow 126b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard/// graph into a form that's suitable for code generation on hardware that 136b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard/// implements control flow by execution masking. This currently includes all 146b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard/// AMD GPUs but may as well be useful for other types of hardware. 156b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard// 166b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard//===----------------------------------------------------------------------===// 176b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 186b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard#include "AMDGPU.h" 196b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard#include "llvm/ADT/SCCIterator.h" 206b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard#include "llvm/Analysis/RegionInfo.h" 2158a2cbef4aac9ee7d530dfb690c78d6fc11a2371Chandler Carruth#include "llvm/Analysis/RegionIterator.h" 226b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard#include "llvm/Analysis/RegionPass.h" 230b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Module.h" 246b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard#include "llvm/Transforms/Utils/SSAUpdater.h" 25ef6b24856d39ca69381d445c8363a86f5e0945dbChristian Konig#include "llvm/Support/PatternMatch.h" 266b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 276b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellardusing namespace llvm; 28ef6b24856d39ca69381d445c8363a86f5e0945dbChristian Konigusing namespace llvm::PatternMatch; 296b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 306b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellardnamespace { 316b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 326b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard// Definition of the complex types used in this pass. 336b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 346b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellardtypedef std::pair<BasicBlock *, Value *> BBValuePair; 356b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 366b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellardtypedef SmallVector<RegionNode*, 8> RNVector; 376b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellardtypedef SmallVector<BasicBlock*, 8> BBVector; 3827f5d0618188a4a51cc222a0d71c5aa845f31189Tom Stellardtypedef SmallVector<BranchInst*, 8> BranchVector; 396b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellardtypedef SmallVector<BBValuePair, 2> BBValueVector; 406b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 4127f5d0618188a4a51cc222a0d71c5aa845f31189Tom Stellardtypedef SmallPtrSet<BasicBlock *, 8> BBSet; 4227f5d0618188a4a51cc222a0d71c5aa845f31189Tom Stellard 436b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellardtypedef DenseMap<PHINode *, BBValueVector> PhiMap; 44f0e469bcaf65dddeadb5ccb400b4a712c5f763beChristian Konigtypedef DenseMap<DomTreeNode *, unsigned> DTN2UnsignedMap; 456b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellardtypedef DenseMap<BasicBlock *, PhiMap> BBPhiMap; 466b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellardtypedef DenseMap<BasicBlock *, Value *> BBPredicates; 476b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellardtypedef DenseMap<BasicBlock *, BBPredicates> PredMap; 48623977d9ba064a6f3b46edee1cb2246716a33397Christian Konigtypedef DenseMap<BasicBlock *, BasicBlock*> BB2BBMap; 4913cf6cb57ad6e0bcd66c0ff11b4c4c568ee2f164Tom Stellardtypedef DenseMap<BasicBlock *, BBVector> BB2BBVecMap; 506b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 516b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard// The name for newly created blocks. 526b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 536b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellardstatic const char *FlowBlockName = "Flow"; 546b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 55f0e469bcaf65dddeadb5ccb400b4a712c5f763beChristian Konig/// @brief Find the nearest common dominator for multiple BasicBlocks 56f0e469bcaf65dddeadb5ccb400b4a712c5f763beChristian Konig/// 57f0e469bcaf65dddeadb5ccb400b4a712c5f763beChristian Konig/// Helper class for AMDGPUStructurizeCFG 58f0e469bcaf65dddeadb5ccb400b4a712c5f763beChristian Konig/// TODO: Maybe move into common code 59f0e469bcaf65dddeadb5ccb400b4a712c5f763beChristian Konigclass NearestCommonDominator { 60f0e469bcaf65dddeadb5ccb400b4a712c5f763beChristian Konig 61f0e469bcaf65dddeadb5ccb400b4a712c5f763beChristian Konig DominatorTree *DT; 62f0e469bcaf65dddeadb5ccb400b4a712c5f763beChristian Konig 63f0e469bcaf65dddeadb5ccb400b4a712c5f763beChristian Konig DTN2UnsignedMap IndexMap; 64f0e469bcaf65dddeadb5ccb400b4a712c5f763beChristian Konig 65f0e469bcaf65dddeadb5ccb400b4a712c5f763beChristian Konig BasicBlock *Result; 66f0e469bcaf65dddeadb5ccb400b4a712c5f763beChristian Konig unsigned ResultIndex; 67f0e469bcaf65dddeadb5ccb400b4a712c5f763beChristian Konig bool ExplicitMentioned; 68f0e469bcaf65dddeadb5ccb400b4a712c5f763beChristian Konig 69f0e469bcaf65dddeadb5ccb400b4a712c5f763beChristian Konigpublic: 70f0e469bcaf65dddeadb5ccb400b4a712c5f763beChristian Konig /// \brief Start a new query 71f0e469bcaf65dddeadb5ccb400b4a712c5f763beChristian Konig NearestCommonDominator(DominatorTree *DomTree) { 72f0e469bcaf65dddeadb5ccb400b4a712c5f763beChristian Konig DT = DomTree; 73f0e469bcaf65dddeadb5ccb400b4a712c5f763beChristian Konig Result = 0; 74f0e469bcaf65dddeadb5ccb400b4a712c5f763beChristian Konig } 75f0e469bcaf65dddeadb5ccb400b4a712c5f763beChristian Konig 76f0e469bcaf65dddeadb5ccb400b4a712c5f763beChristian Konig /// \brief Add BB to the resulting dominator 77f0e469bcaf65dddeadb5ccb400b4a712c5f763beChristian Konig void addBlock(BasicBlock *BB, bool Remember = true) { 78f0e469bcaf65dddeadb5ccb400b4a712c5f763beChristian Konig 79f0e469bcaf65dddeadb5ccb400b4a712c5f763beChristian Konig DomTreeNode *Node = DT->getNode(BB); 80f0e469bcaf65dddeadb5ccb400b4a712c5f763beChristian Konig 81f0e469bcaf65dddeadb5ccb400b4a712c5f763beChristian Konig if (Result == 0) { 82f0e469bcaf65dddeadb5ccb400b4a712c5f763beChristian Konig unsigned Numbering = 0; 83f0e469bcaf65dddeadb5ccb400b4a712c5f763beChristian Konig for (;Node;Node = Node->getIDom()) 84f0e469bcaf65dddeadb5ccb400b4a712c5f763beChristian Konig IndexMap[Node] = ++Numbering; 85f0e469bcaf65dddeadb5ccb400b4a712c5f763beChristian Konig Result = BB; 86f0e469bcaf65dddeadb5ccb400b4a712c5f763beChristian Konig ResultIndex = 1; 87f0e469bcaf65dddeadb5ccb400b4a712c5f763beChristian Konig ExplicitMentioned = Remember; 88f0e469bcaf65dddeadb5ccb400b4a712c5f763beChristian Konig return; 89f0e469bcaf65dddeadb5ccb400b4a712c5f763beChristian Konig } 90f0e469bcaf65dddeadb5ccb400b4a712c5f763beChristian Konig 91f0e469bcaf65dddeadb5ccb400b4a712c5f763beChristian Konig for (;Node;Node = Node->getIDom()) 92f0e469bcaf65dddeadb5ccb400b4a712c5f763beChristian Konig if (IndexMap.count(Node)) 93f0e469bcaf65dddeadb5ccb400b4a712c5f763beChristian Konig break; 94f0e469bcaf65dddeadb5ccb400b4a712c5f763beChristian Konig else 95f0e469bcaf65dddeadb5ccb400b4a712c5f763beChristian Konig IndexMap[Node] = 0; 96f0e469bcaf65dddeadb5ccb400b4a712c5f763beChristian Konig 97f0e469bcaf65dddeadb5ccb400b4a712c5f763beChristian Konig assert(Node && "Dominator tree invalid!"); 98f0e469bcaf65dddeadb5ccb400b4a712c5f763beChristian Konig 99f0e469bcaf65dddeadb5ccb400b4a712c5f763beChristian Konig unsigned Numbering = IndexMap[Node]; 100f0e469bcaf65dddeadb5ccb400b4a712c5f763beChristian Konig if (Numbering > ResultIndex) { 101f0e469bcaf65dddeadb5ccb400b4a712c5f763beChristian Konig Result = Node->getBlock(); 102f0e469bcaf65dddeadb5ccb400b4a712c5f763beChristian Konig ResultIndex = Numbering; 103f0e469bcaf65dddeadb5ccb400b4a712c5f763beChristian Konig ExplicitMentioned = Remember && (Result == BB); 104f0e469bcaf65dddeadb5ccb400b4a712c5f763beChristian Konig } else if (Numbering == ResultIndex) { 105f0e469bcaf65dddeadb5ccb400b4a712c5f763beChristian Konig ExplicitMentioned |= Remember; 106f0e469bcaf65dddeadb5ccb400b4a712c5f763beChristian Konig } 107f0e469bcaf65dddeadb5ccb400b4a712c5f763beChristian Konig } 108f0e469bcaf65dddeadb5ccb400b4a712c5f763beChristian Konig 109f0e469bcaf65dddeadb5ccb400b4a712c5f763beChristian Konig /// \brief Is "Result" one of the BBs added with "Remember" = True? 110f0e469bcaf65dddeadb5ccb400b4a712c5f763beChristian Konig bool wasResultExplicitMentioned() { 111f0e469bcaf65dddeadb5ccb400b4a712c5f763beChristian Konig return ExplicitMentioned; 112f0e469bcaf65dddeadb5ccb400b4a712c5f763beChristian Konig } 113f0e469bcaf65dddeadb5ccb400b4a712c5f763beChristian Konig 114f0e469bcaf65dddeadb5ccb400b4a712c5f763beChristian Konig /// \brief Get the query result 115f0e469bcaf65dddeadb5ccb400b4a712c5f763beChristian Konig BasicBlock *getResult() { 116f0e469bcaf65dddeadb5ccb400b4a712c5f763beChristian Konig return Result; 117f0e469bcaf65dddeadb5ccb400b4a712c5f763beChristian Konig } 118f0e469bcaf65dddeadb5ccb400b4a712c5f763beChristian Konig}; 119f0e469bcaf65dddeadb5ccb400b4a712c5f763beChristian Konig 1206b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard/// @brief Transforms the control flow graph on one single entry/exit region 1216b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard/// at a time. 1226b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard/// 1236b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard/// After the transform all "If"/"Then"/"Else" style control flow looks like 1246b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard/// this: 1256b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard/// 1266b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard/// \verbatim 1276b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard/// 1 1286b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard/// || 1296b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard/// | | 1306b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard/// 2 | 1316b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard/// | / 1326b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard/// |/ 1336b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard/// 3 1346b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard/// || Where: 1356b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard/// | | 1 = "If" block, calculates the condition 1366b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard/// 4 | 2 = "Then" subregion, runs if the condition is true 1376b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard/// | / 3 = "Flow" blocks, newly inserted flow blocks, rejoins the flow 1386b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard/// |/ 4 = "Else" optional subregion, runs if the condition is false 1396b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard/// 5 5 = "End" block, also rejoins the control flow 1406b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard/// \endverbatim 1416b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard/// 1426b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard/// Control flow is expressed as a branch where the true exit goes into the 1436b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard/// "Then"/"Else" region, while the false exit skips the region 1446b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard/// The condition for the optional "Else" region is expressed as a PHI node. 1456b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard/// The incomming values of the PHI node are true for the "If" edge and false 1466b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard/// for the "Then" edge. 1476b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard/// 1486b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard/// Additionally to that even complicated loops look like this: 1496b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard/// 1506b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard/// \verbatim 1516b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard/// 1 1526b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard/// || 1536b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard/// | | 1546b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard/// 2 ^ Where: 1556b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard/// | / 1 = "Entry" block 1566b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard/// |/ 2 = "Loop" optional subregion, with all exits at "Flow" block 1576b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard/// 3 3 = "Flow" block, with back edge to entry block 1586b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard/// | 1596b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard/// \endverbatim 1606b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard/// 1616b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard/// The back edge of the "Flow" block is always on the false side of the branch 1626b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard/// while the true side continues the general flow. So the loop condition 1636b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard/// consist of a network of PHI nodes where the true incoming values expresses 1646b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard/// breaks and the false values expresses continue states. 1656b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellardclass AMDGPUStructurizeCFG : public RegionPass { 1666b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 1676b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard static char ID; 1686b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 1696b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard Type *Boolean; 1706b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard ConstantInt *BoolTrue; 1716b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard ConstantInt *BoolFalse; 1726b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard UndefValue *BoolUndef; 1736b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 1746b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard Function *Func; 1756b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard Region *ParentRegion; 1766b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 1776b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard DominatorTree *DT; 1786b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 1796b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard RNVector Order; 180f4e471a49ed6d8e957aeb62972b8dae5304b4440Tom Stellard BBSet Visited; 181623977d9ba064a6f3b46edee1cb2246716a33397Christian Konig 1826b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard BBPhiMap DeletedPhis; 18313cf6cb57ad6e0bcd66c0ff11b4c4c568ee2f164Tom Stellard BB2BBVecMap AddedPhis; 184623977d9ba064a6f3b46edee1cb2246716a33397Christian Konig 185623977d9ba064a6f3b46edee1cb2246716a33397Christian Konig PredMap Predicates; 18627f5d0618188a4a51cc222a0d71c5aa845f31189Tom Stellard BranchVector Conditions; 1876b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 188623977d9ba064a6f3b46edee1cb2246716a33397Christian Konig BB2BBMap Loops; 189623977d9ba064a6f3b46edee1cb2246716a33397Christian Konig PredMap LoopPreds; 190623977d9ba064a6f3b46edee1cb2246716a33397Christian Konig BranchVector LoopConds; 1916b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 192623977d9ba064a6f3b46edee1cb2246716a33397Christian Konig RegionNode *PrevNode; 1936b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 194623977d9ba064a6f3b46edee1cb2246716a33397Christian Konig void orderNodes(); 19527f5d0618188a4a51cc222a0d71c5aa845f31189Tom Stellard 196623977d9ba064a6f3b46edee1cb2246716a33397Christian Konig void analyzeLoops(RegionNode *N); 1976b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 198ef6b24856d39ca69381d445c8363a86f5e0945dbChristian Konig Value *invert(Value *Condition); 199ef6b24856d39ca69381d445c8363a86f5e0945dbChristian Konig 200623977d9ba064a6f3b46edee1cb2246716a33397Christian Konig Value *buildCondition(BranchInst *Term, unsigned Idx, bool Invert); 2016b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 202623977d9ba064a6f3b46edee1cb2246716a33397Christian Konig void gatherPredicates(RegionNode *N); 2036b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 2046b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard void collectInfos(); 2056b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 206623977d9ba064a6f3b46edee1cb2246716a33397Christian Konig void insertConditions(bool Loops); 20727f5d0618188a4a51cc222a0d71c5aa845f31189Tom Stellard 20813cf6cb57ad6e0bcd66c0ff11b4c4c568ee2f164Tom Stellard void delPhiValues(BasicBlock *From, BasicBlock *To); 20913cf6cb57ad6e0bcd66c0ff11b4c4c568ee2f164Tom Stellard 21013cf6cb57ad6e0bcd66c0ff11b4c4c568ee2f164Tom Stellard void addPhiValues(BasicBlock *From, BasicBlock *To); 21113cf6cb57ad6e0bcd66c0ff11b4c4c568ee2f164Tom Stellard 21213cf6cb57ad6e0bcd66c0ff11b4c4c568ee2f164Tom Stellard void setPhiValues(); 21313cf6cb57ad6e0bcd66c0ff11b4c4c568ee2f164Tom Stellard 2146b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard void killTerminator(BasicBlock *BB); 2156b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 216f4e471a49ed6d8e957aeb62972b8dae5304b4440Tom Stellard void changeExit(RegionNode *Node, BasicBlock *NewExit, 217f4e471a49ed6d8e957aeb62972b8dae5304b4440Tom Stellard bool IncludeDominator); 218f4e471a49ed6d8e957aeb62972b8dae5304b4440Tom Stellard 219f4e471a49ed6d8e957aeb62972b8dae5304b4440Tom Stellard BasicBlock *getNextFlow(BasicBlock *Dominator); 220f4e471a49ed6d8e957aeb62972b8dae5304b4440Tom Stellard 221623977d9ba064a6f3b46edee1cb2246716a33397Christian Konig BasicBlock *needPrefix(bool NeedEmpty); 2226b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 223f4e471a49ed6d8e957aeb62972b8dae5304b4440Tom Stellard BasicBlock *needPostfix(BasicBlock *Flow, bool ExitUseAllowed); 2246b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 225623977d9ba064a6f3b46edee1cb2246716a33397Christian Konig void setPrevNode(BasicBlock *BB); 2266b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 227f4e471a49ed6d8e957aeb62972b8dae5304b4440Tom Stellard bool dominatesPredicates(BasicBlock *BB, RegionNode *Node); 228f4e471a49ed6d8e957aeb62972b8dae5304b4440Tom Stellard 229623977d9ba064a6f3b46edee1cb2246716a33397Christian Konig bool isPredictableTrue(RegionNode *Node); 230623977d9ba064a6f3b46edee1cb2246716a33397Christian Konig 231623977d9ba064a6f3b46edee1cb2246716a33397Christian Konig void wireFlow(bool ExitUseAllowed, BasicBlock *LoopEnd); 232f4e471a49ed6d8e957aeb62972b8dae5304b4440Tom Stellard 233623977d9ba064a6f3b46edee1cb2246716a33397Christian Konig void handleLoops(bool ExitUseAllowed, BasicBlock *LoopEnd); 2346b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 2356b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard void createFlow(); 2366b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 2376b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard void rebuildSSA(); 2386b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 2396b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellardpublic: 2406b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard AMDGPUStructurizeCFG(): 2416b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard RegionPass(ID) { 2426b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 2436b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard initializeRegionInfoPass(*PassRegistry::getPassRegistry()); 2446b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard } 2456b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 246777962fddf436f6794fac3e605ff5afafbf90f1cChristian Konig using Pass::doInitialization; 2476b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard virtual bool doInitialization(Region *R, RGPassManager &RGM); 2486b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 2496b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard virtual bool runOnRegion(Region *R, RGPassManager &RGM); 2506b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 2516b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard virtual const char *getPassName() const { 2526b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard return "AMDGPU simplify control flow"; 2536b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard } 2546b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 2556b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard void getAnalysisUsage(AnalysisUsage &AU) const { 2566b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 2576b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard AU.addRequired<DominatorTree>(); 2586b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard AU.addPreserved<DominatorTree>(); 2596b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard RegionPass::getAnalysisUsage(AU); 2606b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard } 2616b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 2626b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard}; 2636b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 2646b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard} // end anonymous namespace 2656b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 2666b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellardchar AMDGPUStructurizeCFG::ID = 0; 2676b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 2686b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard/// \brief Initialize the types and constants used in the pass 2696b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellardbool AMDGPUStructurizeCFG::doInitialization(Region *R, RGPassManager &RGM) { 2706b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard LLVMContext &Context = R->getEntry()->getContext(); 2716b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 2726b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard Boolean = Type::getInt1Ty(Context); 2736b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard BoolTrue = ConstantInt::getTrue(Context); 2746b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard BoolFalse = ConstantInt::getFalse(Context); 2756b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard BoolUndef = UndefValue::get(Boolean); 2766b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 2776b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard return false; 2786b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard} 2796b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 2806b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard/// \brief Build up the general order of nodes 2816b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellardvoid AMDGPUStructurizeCFG::orderNodes() { 2826b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard scc_iterator<Region *> I = scc_begin(ParentRegion), 2836b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard E = scc_end(ParentRegion); 2846b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard for (Order.clear(); I != E; ++I) { 2856b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard std::vector<RegionNode *> &Nodes = *I; 2866b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard Order.append(Nodes.begin(), Nodes.end()); 2876b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard } 2886b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard} 2896b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 290623977d9ba064a6f3b46edee1cb2246716a33397Christian Konig/// \brief Determine the end of the loops 291623977d9ba064a6f3b46edee1cb2246716a33397Christian Konigvoid AMDGPUStructurizeCFG::analyzeLoops(RegionNode *N) { 292623977d9ba064a6f3b46edee1cb2246716a33397Christian Konig 293623977d9ba064a6f3b46edee1cb2246716a33397Christian Konig if (N->isSubRegion()) { 294623977d9ba064a6f3b46edee1cb2246716a33397Christian Konig // Test for exit as back edge 295623977d9ba064a6f3b46edee1cb2246716a33397Christian Konig BasicBlock *Exit = N->getNodeAs<Region>()->getExit(); 296623977d9ba064a6f3b46edee1cb2246716a33397Christian Konig if (Visited.count(Exit)) 297623977d9ba064a6f3b46edee1cb2246716a33397Christian Konig Loops[Exit] = N->getEntry(); 298623977d9ba064a6f3b46edee1cb2246716a33397Christian Konig 299623977d9ba064a6f3b46edee1cb2246716a33397Christian Konig } else { 300623977d9ba064a6f3b46edee1cb2246716a33397Christian Konig // Test for sucessors as back edge 301623977d9ba064a6f3b46edee1cb2246716a33397Christian Konig BasicBlock *BB = N->getNodeAs<BasicBlock>(); 302623977d9ba064a6f3b46edee1cb2246716a33397Christian Konig BranchInst *Term = cast<BranchInst>(BB->getTerminator()); 303623977d9ba064a6f3b46edee1cb2246716a33397Christian Konig 304623977d9ba064a6f3b46edee1cb2246716a33397Christian Konig for (unsigned i = 0, e = Term->getNumSuccessors(); i != e; ++i) { 305623977d9ba064a6f3b46edee1cb2246716a33397Christian Konig BasicBlock *Succ = Term->getSuccessor(i); 306623977d9ba064a6f3b46edee1cb2246716a33397Christian Konig 307623977d9ba064a6f3b46edee1cb2246716a33397Christian Konig if (Visited.count(Succ)) 308623977d9ba064a6f3b46edee1cb2246716a33397Christian Konig Loops[Succ] = BB; 309623977d9ba064a6f3b46edee1cb2246716a33397Christian Konig } 310623977d9ba064a6f3b46edee1cb2246716a33397Christian Konig } 311623977d9ba064a6f3b46edee1cb2246716a33397Christian Konig} 312623977d9ba064a6f3b46edee1cb2246716a33397Christian Konig 313ef6b24856d39ca69381d445c8363a86f5e0945dbChristian Konig/// \brief Invert the given condition 314ef6b24856d39ca69381d445c8363a86f5e0945dbChristian KonigValue *AMDGPUStructurizeCFG::invert(Value *Condition) { 315ef6b24856d39ca69381d445c8363a86f5e0945dbChristian Konig 316ef6b24856d39ca69381d445c8363a86f5e0945dbChristian Konig // First: Check if it's a constant 317ef6b24856d39ca69381d445c8363a86f5e0945dbChristian Konig if (Condition == BoolTrue) 318ef6b24856d39ca69381d445c8363a86f5e0945dbChristian Konig return BoolFalse; 319ef6b24856d39ca69381d445c8363a86f5e0945dbChristian Konig 320ef6b24856d39ca69381d445c8363a86f5e0945dbChristian Konig if (Condition == BoolFalse) 321ef6b24856d39ca69381d445c8363a86f5e0945dbChristian Konig return BoolTrue; 322ef6b24856d39ca69381d445c8363a86f5e0945dbChristian Konig 323ef6b24856d39ca69381d445c8363a86f5e0945dbChristian Konig if (Condition == BoolUndef) 324ef6b24856d39ca69381d445c8363a86f5e0945dbChristian Konig return BoolUndef; 325ef6b24856d39ca69381d445c8363a86f5e0945dbChristian Konig 326ef6b24856d39ca69381d445c8363a86f5e0945dbChristian Konig // Second: If the condition is already inverted, return the original value 327ef6b24856d39ca69381d445c8363a86f5e0945dbChristian Konig if (match(Condition, m_Not(m_Value(Condition)))) 328ef6b24856d39ca69381d445c8363a86f5e0945dbChristian Konig return Condition; 329ef6b24856d39ca69381d445c8363a86f5e0945dbChristian Konig 330ef6b24856d39ca69381d445c8363a86f5e0945dbChristian Konig // Third: Check all the users for an invert 331ef6b24856d39ca69381d445c8363a86f5e0945dbChristian Konig BasicBlock *Parent = cast<Instruction>(Condition)->getParent(); 332ef6b24856d39ca69381d445c8363a86f5e0945dbChristian Konig for (Value::use_iterator I = Condition->use_begin(), 333ef6b24856d39ca69381d445c8363a86f5e0945dbChristian Konig E = Condition->use_end(); I != E; ++I) { 334ef6b24856d39ca69381d445c8363a86f5e0945dbChristian Konig 335ef6b24856d39ca69381d445c8363a86f5e0945dbChristian Konig Instruction *User = dyn_cast<Instruction>(*I); 336ef6b24856d39ca69381d445c8363a86f5e0945dbChristian Konig if (!User || User->getParent() != Parent) 337ef6b24856d39ca69381d445c8363a86f5e0945dbChristian Konig continue; 338ef6b24856d39ca69381d445c8363a86f5e0945dbChristian Konig 339ef6b24856d39ca69381d445c8363a86f5e0945dbChristian Konig if (match(*I, m_Not(m_Specific(Condition)))) 340ef6b24856d39ca69381d445c8363a86f5e0945dbChristian Konig return *I; 341ef6b24856d39ca69381d445c8363a86f5e0945dbChristian Konig } 342ef6b24856d39ca69381d445c8363a86f5e0945dbChristian Konig 343ef6b24856d39ca69381d445c8363a86f5e0945dbChristian Konig // Last option: Create a new instruction 344ef6b24856d39ca69381d445c8363a86f5e0945dbChristian Konig return BinaryOperator::CreateNot(Condition, "", Parent->getTerminator()); 345ef6b24856d39ca69381d445c8363a86f5e0945dbChristian Konig} 346ef6b24856d39ca69381d445c8363a86f5e0945dbChristian Konig 34727f5d0618188a4a51cc222a0d71c5aa845f31189Tom Stellard/// \brief Build the condition for one edge 34827f5d0618188a4a51cc222a0d71c5aa845f31189Tom StellardValue *AMDGPUStructurizeCFG::buildCondition(BranchInst *Term, unsigned Idx, 34927f5d0618188a4a51cc222a0d71c5aa845f31189Tom Stellard bool Invert) { 35027f5d0618188a4a51cc222a0d71c5aa845f31189Tom Stellard Value *Cond = Invert ? BoolFalse : BoolTrue; 35127f5d0618188a4a51cc222a0d71c5aa845f31189Tom Stellard if (Term->isConditional()) { 35227f5d0618188a4a51cc222a0d71c5aa845f31189Tom Stellard Cond = Term->getCondition(); 3536b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 35427f5d0618188a4a51cc222a0d71c5aa845f31189Tom Stellard if (Idx != Invert) 355ef6b24856d39ca69381d445c8363a86f5e0945dbChristian Konig Cond = invert(Cond); 35627f5d0618188a4a51cc222a0d71c5aa845f31189Tom Stellard } 35727f5d0618188a4a51cc222a0d71c5aa845f31189Tom Stellard return Cond; 35827f5d0618188a4a51cc222a0d71c5aa845f31189Tom Stellard} 3596b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 36027f5d0618188a4a51cc222a0d71c5aa845f31189Tom Stellard/// \brief Analyze the predecessors of each block and build up predicates 361623977d9ba064a6f3b46edee1cb2246716a33397Christian Konigvoid AMDGPUStructurizeCFG::gatherPredicates(RegionNode *N) { 362623977d9ba064a6f3b46edee1cb2246716a33397Christian Konig 36327f5d0618188a4a51cc222a0d71c5aa845f31189Tom Stellard RegionInfo *RI = ParentRegion->getRegionInfo(); 36427f5d0618188a4a51cc222a0d71c5aa845f31189Tom Stellard BasicBlock *BB = N->getEntry(); 36527f5d0618188a4a51cc222a0d71c5aa845f31189Tom Stellard BBPredicates &Pred = Predicates[BB]; 366623977d9ba064a6f3b46edee1cb2246716a33397Christian Konig BBPredicates &LPred = LoopPreds[BB]; 3676b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 36827f5d0618188a4a51cc222a0d71c5aa845f31189Tom Stellard for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); 36927f5d0618188a4a51cc222a0d71c5aa845f31189Tom Stellard PI != PE; ++PI) { 3706b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 371623977d9ba064a6f3b46edee1cb2246716a33397Christian Konig // Ignore it if it's a branch from outside into our region entry 372623977d9ba064a6f3b46edee1cb2246716a33397Christian Konig if (!ParentRegion->contains(*PI)) 37327f5d0618188a4a51cc222a0d71c5aa845f31189Tom Stellard continue; 3746b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 37527f5d0618188a4a51cc222a0d71c5aa845f31189Tom Stellard Region *R = RI->getRegionFor(*PI); 37627f5d0618188a4a51cc222a0d71c5aa845f31189Tom Stellard if (R == ParentRegion) { 3776b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 37827f5d0618188a4a51cc222a0d71c5aa845f31189Tom Stellard // It's a top level block in our region 37927f5d0618188a4a51cc222a0d71c5aa845f31189Tom Stellard BranchInst *Term = cast<BranchInst>((*PI)->getTerminator()); 38027f5d0618188a4a51cc222a0d71c5aa845f31189Tom Stellard for (unsigned i = 0, e = Term->getNumSuccessors(); i != e; ++i) { 38127f5d0618188a4a51cc222a0d71c5aa845f31189Tom Stellard BasicBlock *Succ = Term->getSuccessor(i); 38227f5d0618188a4a51cc222a0d71c5aa845f31189Tom Stellard if (Succ != BB) 38327f5d0618188a4a51cc222a0d71c5aa845f31189Tom Stellard continue; 3846b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 38527f5d0618188a4a51cc222a0d71c5aa845f31189Tom Stellard if (Visited.count(*PI)) { 38627f5d0618188a4a51cc222a0d71c5aa845f31189Tom Stellard // Normal forward edge 38727f5d0618188a4a51cc222a0d71c5aa845f31189Tom Stellard if (Term->isConditional()) { 38827f5d0618188a4a51cc222a0d71c5aa845f31189Tom Stellard // Try to treat it like an ELSE block 38927f5d0618188a4a51cc222a0d71c5aa845f31189Tom Stellard BasicBlock *Other = Term->getSuccessor(!i); 390623977d9ba064a6f3b46edee1cb2246716a33397Christian Konig if (Visited.count(Other) && !Loops.count(Other) && 39127f5d0618188a4a51cc222a0d71c5aa845f31189Tom Stellard !Pred.count(Other) && !Pred.count(*PI)) { 39227f5d0618188a4a51cc222a0d71c5aa845f31189Tom Stellard 39327f5d0618188a4a51cc222a0d71c5aa845f31189Tom Stellard Pred[Other] = BoolFalse; 39427f5d0618188a4a51cc222a0d71c5aa845f31189Tom Stellard Pred[*PI] = BoolTrue; 39527f5d0618188a4a51cc222a0d71c5aa845f31189Tom Stellard continue; 39627f5d0618188a4a51cc222a0d71c5aa845f31189Tom Stellard } 39727f5d0618188a4a51cc222a0d71c5aa845f31189Tom Stellard } 398623977d9ba064a6f3b46edee1cb2246716a33397Christian Konig Pred[*PI] = buildCondition(Term, i, false); 399623977d9ba064a6f3b46edee1cb2246716a33397Christian Konig 40027f5d0618188a4a51cc222a0d71c5aa845f31189Tom Stellard } else { 40127f5d0618188a4a51cc222a0d71c5aa845f31189Tom Stellard // Back edge 402623977d9ba064a6f3b46edee1cb2246716a33397Christian Konig LPred[*PI] = buildCondition(Term, i, true); 40327f5d0618188a4a51cc222a0d71c5aa845f31189Tom Stellard } 40427f5d0618188a4a51cc222a0d71c5aa845f31189Tom Stellard } 4056b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 40627f5d0618188a4a51cc222a0d71c5aa845f31189Tom Stellard } else { 4076b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 40827f5d0618188a4a51cc222a0d71c5aa845f31189Tom Stellard // It's an exit from a sub region 40927f5d0618188a4a51cc222a0d71c5aa845f31189Tom Stellard while(R->getParent() != ParentRegion) 41027f5d0618188a4a51cc222a0d71c5aa845f31189Tom Stellard R = R->getParent(); 41127f5d0618188a4a51cc222a0d71c5aa845f31189Tom Stellard 41227f5d0618188a4a51cc222a0d71c5aa845f31189Tom Stellard // Edge from inside a subregion to its entry, ignore it 41327f5d0618188a4a51cc222a0d71c5aa845f31189Tom Stellard if (R == N) 4146b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard continue; 41527f5d0618188a4a51cc222a0d71c5aa845f31189Tom Stellard 41627f5d0618188a4a51cc222a0d71c5aa845f31189Tom Stellard BasicBlock *Entry = R->getEntry(); 417623977d9ba064a6f3b46edee1cb2246716a33397Christian Konig if (Visited.count(Entry)) 418623977d9ba064a6f3b46edee1cb2246716a33397Christian Konig Pred[Entry] = BoolTrue; 419623977d9ba064a6f3b46edee1cb2246716a33397Christian Konig else 420623977d9ba064a6f3b46edee1cb2246716a33397Christian Konig LPred[Entry] = BoolFalse; 4216b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard } 4226b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard } 4236b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard} 4246b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 4256b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard/// \brief Collect various loop and predicate infos 4266b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellardvoid AMDGPUStructurizeCFG::collectInfos() { 4276b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 4286b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard // Reset predicate 4296b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard Predicates.clear(); 4306b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 4316b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard // and loop infos 432623977d9ba064a6f3b46edee1cb2246716a33397Christian Konig Loops.clear(); 433623977d9ba064a6f3b46edee1cb2246716a33397Christian Konig LoopPreds.clear(); 4346b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 43527f5d0618188a4a51cc222a0d71c5aa845f31189Tom Stellard // Reset the visited nodes 43627f5d0618188a4a51cc222a0d71c5aa845f31189Tom Stellard Visited.clear(); 43727f5d0618188a4a51cc222a0d71c5aa845f31189Tom Stellard 43827f5d0618188a4a51cc222a0d71c5aa845f31189Tom Stellard for (RNVector::reverse_iterator OI = Order.rbegin(), OE = Order.rend(); 43927f5d0618188a4a51cc222a0d71c5aa845f31189Tom Stellard OI != OE; ++OI) { 4406b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 4416b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard // Analyze all the conditions leading to a node 442623977d9ba064a6f3b46edee1cb2246716a33397Christian Konig gatherPredicates(*OI); 4436b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 44427f5d0618188a4a51cc222a0d71c5aa845f31189Tom Stellard // Remember that we've seen this node 445f4e471a49ed6d8e957aeb62972b8dae5304b4440Tom Stellard Visited.insert((*OI)->getEntry()); 4466b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 447623977d9ba064a6f3b46edee1cb2246716a33397Christian Konig // Find the last back edges 448623977d9ba064a6f3b46edee1cb2246716a33397Christian Konig analyzeLoops(*OI); 44927f5d0618188a4a51cc222a0d71c5aa845f31189Tom Stellard } 45027f5d0618188a4a51cc222a0d71c5aa845f31189Tom Stellard} 45127f5d0618188a4a51cc222a0d71c5aa845f31189Tom Stellard 45227f5d0618188a4a51cc222a0d71c5aa845f31189Tom Stellard/// \brief Insert the missing branch conditions 453623977d9ba064a6f3b46edee1cb2246716a33397Christian Konigvoid AMDGPUStructurizeCFG::insertConditions(bool Loops) { 454623977d9ba064a6f3b46edee1cb2246716a33397Christian Konig BranchVector &Conds = Loops ? LoopConds : Conditions; 455623977d9ba064a6f3b46edee1cb2246716a33397Christian Konig Value *Default = Loops ? BoolTrue : BoolFalse; 45627f5d0618188a4a51cc222a0d71c5aa845f31189Tom Stellard SSAUpdater PhiInserter; 45727f5d0618188a4a51cc222a0d71c5aa845f31189Tom Stellard 458623977d9ba064a6f3b46edee1cb2246716a33397Christian Konig for (BranchVector::iterator I = Conds.begin(), 459623977d9ba064a6f3b46edee1cb2246716a33397Christian Konig E = Conds.end(); I != E; ++I) { 46027f5d0618188a4a51cc222a0d71c5aa845f31189Tom Stellard 46127f5d0618188a4a51cc222a0d71c5aa845f31189Tom Stellard BranchInst *Term = *I; 46227f5d0618188a4a51cc222a0d71c5aa845f31189Tom Stellard assert(Term->isConditional()); 46327f5d0618188a4a51cc222a0d71c5aa845f31189Tom Stellard 464623977d9ba064a6f3b46edee1cb2246716a33397Christian Konig BasicBlock *Parent = Term->getParent(); 465623977d9ba064a6f3b46edee1cb2246716a33397Christian Konig BasicBlock *SuccTrue = Term->getSuccessor(0); 466623977d9ba064a6f3b46edee1cb2246716a33397Christian Konig BasicBlock *SuccFalse = Term->getSuccessor(1); 46725bd884c3d0e9803dfafda10e7ecede152ad156fChristian Konig 46827f5d0618188a4a51cc222a0d71c5aa845f31189Tom Stellard PhiInserter.Initialize(Boolean, ""); 46925bd884c3d0e9803dfafda10e7ecede152ad156fChristian Konig PhiInserter.AddAvailableValue(&Func->getEntryBlock(), Default); 470623977d9ba064a6f3b46edee1cb2246716a33397Christian Konig PhiInserter.AddAvailableValue(Loops ? SuccFalse : Parent, Default); 47127f5d0618188a4a51cc222a0d71c5aa845f31189Tom Stellard 472623977d9ba064a6f3b46edee1cb2246716a33397Christian Konig BBPredicates &Preds = Loops ? LoopPreds[SuccFalse] : Predicates[SuccTrue]; 47325bd884c3d0e9803dfafda10e7ecede152ad156fChristian Konig 47425bd884c3d0e9803dfafda10e7ecede152ad156fChristian Konig NearestCommonDominator Dominator(DT); 47525bd884c3d0e9803dfafda10e7ecede152ad156fChristian Konig Dominator.addBlock(Parent, false); 47625bd884c3d0e9803dfafda10e7ecede152ad156fChristian Konig 47725bd884c3d0e9803dfafda10e7ecede152ad156fChristian Konig Value *ParentValue = 0; 47827f5d0618188a4a51cc222a0d71c5aa845f31189Tom Stellard for (BBPredicates::iterator PI = Preds.begin(), PE = Preds.end(); 47927f5d0618188a4a51cc222a0d71c5aa845f31189Tom Stellard PI != PE; ++PI) { 48027f5d0618188a4a51cc222a0d71c5aa845f31189Tom Stellard 48125bd884c3d0e9803dfafda10e7ecede152ad156fChristian Konig if (PI->first == Parent) { 48225bd884c3d0e9803dfafda10e7ecede152ad156fChristian Konig ParentValue = PI->second; 48325bd884c3d0e9803dfafda10e7ecede152ad156fChristian Konig break; 48425bd884c3d0e9803dfafda10e7ecede152ad156fChristian Konig } 48527f5d0618188a4a51cc222a0d71c5aa845f31189Tom Stellard PhiInserter.AddAvailableValue(PI->first, PI->second); 48625bd884c3d0e9803dfafda10e7ecede152ad156fChristian Konig Dominator.addBlock(PI->first); 48727f5d0618188a4a51cc222a0d71c5aa845f31189Tom Stellard } 48827f5d0618188a4a51cc222a0d71c5aa845f31189Tom Stellard 48925bd884c3d0e9803dfafda10e7ecede152ad156fChristian Konig if (ParentValue) { 49025bd884c3d0e9803dfafda10e7ecede152ad156fChristian Konig Term->setCondition(ParentValue); 49125bd884c3d0e9803dfafda10e7ecede152ad156fChristian Konig } else { 49225bd884c3d0e9803dfafda10e7ecede152ad156fChristian Konig if (!Dominator.wasResultExplicitMentioned()) 49325bd884c3d0e9803dfafda10e7ecede152ad156fChristian Konig PhiInserter.AddAvailableValue(Dominator.getResult(), Default); 49425bd884c3d0e9803dfafda10e7ecede152ad156fChristian Konig 49527f5d0618188a4a51cc222a0d71c5aa845f31189Tom Stellard Term->setCondition(PhiInserter.GetValueInMiddleOfBlock(Parent)); 49625bd884c3d0e9803dfafda10e7ecede152ad156fChristian Konig } 4976b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard } 4986b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard} 4996b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 50013cf6cb57ad6e0bcd66c0ff11b4c4c568ee2f164Tom Stellard/// \brief Remove all PHI values coming from "From" into "To" and remember 50113cf6cb57ad6e0bcd66c0ff11b4c4c568ee2f164Tom Stellard/// them in DeletedPhis 50213cf6cb57ad6e0bcd66c0ff11b4c4c568ee2f164Tom Stellardvoid AMDGPUStructurizeCFG::delPhiValues(BasicBlock *From, BasicBlock *To) { 50313cf6cb57ad6e0bcd66c0ff11b4c4c568ee2f164Tom Stellard PhiMap &Map = DeletedPhis[To]; 50413cf6cb57ad6e0bcd66c0ff11b4c4c568ee2f164Tom Stellard for (BasicBlock::iterator I = To->begin(), E = To->end(); 50513cf6cb57ad6e0bcd66c0ff11b4c4c568ee2f164Tom Stellard I != E && isa<PHINode>(*I);) { 50613cf6cb57ad6e0bcd66c0ff11b4c4c568ee2f164Tom Stellard 50713cf6cb57ad6e0bcd66c0ff11b4c4c568ee2f164Tom Stellard PHINode &Phi = cast<PHINode>(*I++); 50813cf6cb57ad6e0bcd66c0ff11b4c4c568ee2f164Tom Stellard while (Phi.getBasicBlockIndex(From) != -1) { 50913cf6cb57ad6e0bcd66c0ff11b4c4c568ee2f164Tom Stellard Value *Deleted = Phi.removeIncomingValue(From, false); 51013cf6cb57ad6e0bcd66c0ff11b4c4c568ee2f164Tom Stellard Map[&Phi].push_back(std::make_pair(From, Deleted)); 51113cf6cb57ad6e0bcd66c0ff11b4c4c568ee2f164Tom Stellard } 51213cf6cb57ad6e0bcd66c0ff11b4c4c568ee2f164Tom Stellard } 51313cf6cb57ad6e0bcd66c0ff11b4c4c568ee2f164Tom Stellard} 51413cf6cb57ad6e0bcd66c0ff11b4c4c568ee2f164Tom Stellard 51513cf6cb57ad6e0bcd66c0ff11b4c4c568ee2f164Tom Stellard/// \brief Add a dummy PHI value as soon as we knew the new predecessor 51613cf6cb57ad6e0bcd66c0ff11b4c4c568ee2f164Tom Stellardvoid AMDGPUStructurizeCFG::addPhiValues(BasicBlock *From, BasicBlock *To) { 51713cf6cb57ad6e0bcd66c0ff11b4c4c568ee2f164Tom Stellard for (BasicBlock::iterator I = To->begin(), E = To->end(); 51813cf6cb57ad6e0bcd66c0ff11b4c4c568ee2f164Tom Stellard I != E && isa<PHINode>(*I);) { 51913cf6cb57ad6e0bcd66c0ff11b4c4c568ee2f164Tom Stellard 52013cf6cb57ad6e0bcd66c0ff11b4c4c568ee2f164Tom Stellard PHINode &Phi = cast<PHINode>(*I++); 52113cf6cb57ad6e0bcd66c0ff11b4c4c568ee2f164Tom Stellard Value *Undef = UndefValue::get(Phi.getType()); 52213cf6cb57ad6e0bcd66c0ff11b4c4c568ee2f164Tom Stellard Phi.addIncoming(Undef, From); 52313cf6cb57ad6e0bcd66c0ff11b4c4c568ee2f164Tom Stellard } 52413cf6cb57ad6e0bcd66c0ff11b4c4c568ee2f164Tom Stellard AddedPhis[To].push_back(From); 52513cf6cb57ad6e0bcd66c0ff11b4c4c568ee2f164Tom Stellard} 52613cf6cb57ad6e0bcd66c0ff11b4c4c568ee2f164Tom Stellard 52713cf6cb57ad6e0bcd66c0ff11b4c4c568ee2f164Tom Stellard/// \brief Add the real PHI value as soon as everything is set up 52813cf6cb57ad6e0bcd66c0ff11b4c4c568ee2f164Tom Stellardvoid AMDGPUStructurizeCFG::setPhiValues() { 52913cf6cb57ad6e0bcd66c0ff11b4c4c568ee2f164Tom Stellard 53013cf6cb57ad6e0bcd66c0ff11b4c4c568ee2f164Tom Stellard SSAUpdater Updater; 53113cf6cb57ad6e0bcd66c0ff11b4c4c568ee2f164Tom Stellard for (BB2BBVecMap::iterator AI = AddedPhis.begin(), AE = AddedPhis.end(); 53213cf6cb57ad6e0bcd66c0ff11b4c4c568ee2f164Tom Stellard AI != AE; ++AI) { 53313cf6cb57ad6e0bcd66c0ff11b4c4c568ee2f164Tom Stellard 53413cf6cb57ad6e0bcd66c0ff11b4c4c568ee2f164Tom Stellard BasicBlock *To = AI->first; 53513cf6cb57ad6e0bcd66c0ff11b4c4c568ee2f164Tom Stellard BBVector &From = AI->second; 53613cf6cb57ad6e0bcd66c0ff11b4c4c568ee2f164Tom Stellard 53713cf6cb57ad6e0bcd66c0ff11b4c4c568ee2f164Tom Stellard if (!DeletedPhis.count(To)) 53813cf6cb57ad6e0bcd66c0ff11b4c4c568ee2f164Tom Stellard continue; 53913cf6cb57ad6e0bcd66c0ff11b4c4c568ee2f164Tom Stellard 54013cf6cb57ad6e0bcd66c0ff11b4c4c568ee2f164Tom Stellard PhiMap &Map = DeletedPhis[To]; 54113cf6cb57ad6e0bcd66c0ff11b4c4c568ee2f164Tom Stellard for (PhiMap::iterator PI = Map.begin(), PE = Map.end(); 54213cf6cb57ad6e0bcd66c0ff11b4c4c568ee2f164Tom Stellard PI != PE; ++PI) { 54313cf6cb57ad6e0bcd66c0ff11b4c4c568ee2f164Tom Stellard 54413cf6cb57ad6e0bcd66c0ff11b4c4c568ee2f164Tom Stellard PHINode *Phi = PI->first; 54513cf6cb57ad6e0bcd66c0ff11b4c4c568ee2f164Tom Stellard Value *Undef = UndefValue::get(Phi->getType()); 54613cf6cb57ad6e0bcd66c0ff11b4c4c568ee2f164Tom Stellard Updater.Initialize(Phi->getType(), ""); 54713cf6cb57ad6e0bcd66c0ff11b4c4c568ee2f164Tom Stellard Updater.AddAvailableValue(&Func->getEntryBlock(), Undef); 54813cf6cb57ad6e0bcd66c0ff11b4c4c568ee2f164Tom Stellard Updater.AddAvailableValue(To, Undef); 54913cf6cb57ad6e0bcd66c0ff11b4c4c568ee2f164Tom Stellard 5504c79c71d99336baf312e2784311b257c5d9eebceChristian Konig NearestCommonDominator Dominator(DT); 5514c79c71d99336baf312e2784311b257c5d9eebceChristian Konig Dominator.addBlock(To, false); 55213cf6cb57ad6e0bcd66c0ff11b4c4c568ee2f164Tom Stellard for (BBValueVector::iterator VI = PI->second.begin(), 55313cf6cb57ad6e0bcd66c0ff11b4c4c568ee2f164Tom Stellard VE = PI->second.end(); VI != VE; ++VI) { 55413cf6cb57ad6e0bcd66c0ff11b4c4c568ee2f164Tom Stellard 55513cf6cb57ad6e0bcd66c0ff11b4c4c568ee2f164Tom Stellard Updater.AddAvailableValue(VI->first, VI->second); 5564c79c71d99336baf312e2784311b257c5d9eebceChristian Konig Dominator.addBlock(VI->first); 55713cf6cb57ad6e0bcd66c0ff11b4c4c568ee2f164Tom Stellard } 55813cf6cb57ad6e0bcd66c0ff11b4c4c568ee2f164Tom Stellard 5594c79c71d99336baf312e2784311b257c5d9eebceChristian Konig if (!Dominator.wasResultExplicitMentioned()) 5604c79c71d99336baf312e2784311b257c5d9eebceChristian Konig Updater.AddAvailableValue(Dominator.getResult(), Undef); 5614c79c71d99336baf312e2784311b257c5d9eebceChristian Konig 56213cf6cb57ad6e0bcd66c0ff11b4c4c568ee2f164Tom Stellard for (BBVector::iterator FI = From.begin(), FE = From.end(); 56313cf6cb57ad6e0bcd66c0ff11b4c4c568ee2f164Tom Stellard FI != FE; ++FI) { 56413cf6cb57ad6e0bcd66c0ff11b4c4c568ee2f164Tom Stellard 56513cf6cb57ad6e0bcd66c0ff11b4c4c568ee2f164Tom Stellard int Idx = Phi->getBasicBlockIndex(*FI); 56613cf6cb57ad6e0bcd66c0ff11b4c4c568ee2f164Tom Stellard assert(Idx != -1); 56713cf6cb57ad6e0bcd66c0ff11b4c4c568ee2f164Tom Stellard Phi->setIncomingValue(Idx, Updater.GetValueAtEndOfBlock(*FI)); 56813cf6cb57ad6e0bcd66c0ff11b4c4c568ee2f164Tom Stellard } 56913cf6cb57ad6e0bcd66c0ff11b4c4c568ee2f164Tom Stellard } 57013cf6cb57ad6e0bcd66c0ff11b4c4c568ee2f164Tom Stellard 57113cf6cb57ad6e0bcd66c0ff11b4c4c568ee2f164Tom Stellard DeletedPhis.erase(To); 57213cf6cb57ad6e0bcd66c0ff11b4c4c568ee2f164Tom Stellard } 57313cf6cb57ad6e0bcd66c0ff11b4c4c568ee2f164Tom Stellard assert(DeletedPhis.empty()); 57413cf6cb57ad6e0bcd66c0ff11b4c4c568ee2f164Tom Stellard} 57513cf6cb57ad6e0bcd66c0ff11b4c4c568ee2f164Tom Stellard 576f4e471a49ed6d8e957aeb62972b8dae5304b4440Tom Stellard/// \brief Remove phi values from all successors and then remove the terminator. 5776b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellardvoid AMDGPUStructurizeCFG::killTerminator(BasicBlock *BB) { 5786b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard TerminatorInst *Term = BB->getTerminator(); 5796b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard if (!Term) 5806b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard return; 5816b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 5826b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB); 5836b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard SI != SE; ++SI) { 5846b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 5856b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard delPhiValues(BB, *SI); 5866b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard } 5876b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 5886b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard Term->eraseFromParent(); 5896b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard} 5906b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 591f4e471a49ed6d8e957aeb62972b8dae5304b4440Tom Stellard/// \brief Let node exit(s) point to NewExit 592f4e471a49ed6d8e957aeb62972b8dae5304b4440Tom Stellardvoid AMDGPUStructurizeCFG::changeExit(RegionNode *Node, BasicBlock *NewExit, 593f4e471a49ed6d8e957aeb62972b8dae5304b4440Tom Stellard bool IncludeDominator) { 5946b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 595f4e471a49ed6d8e957aeb62972b8dae5304b4440Tom Stellard if (Node->isSubRegion()) { 596f4e471a49ed6d8e957aeb62972b8dae5304b4440Tom Stellard Region *SubRegion = Node->getNodeAs<Region>(); 597f4e471a49ed6d8e957aeb62972b8dae5304b4440Tom Stellard BasicBlock *OldExit = SubRegion->getExit(); 598f4e471a49ed6d8e957aeb62972b8dae5304b4440Tom Stellard BasicBlock *Dominator = 0; 5996b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 600f4e471a49ed6d8e957aeb62972b8dae5304b4440Tom Stellard // Find all the edges from the sub region to the exit 601f4e471a49ed6d8e957aeb62972b8dae5304b4440Tom Stellard for (pred_iterator I = pred_begin(OldExit), E = pred_end(OldExit); 602f4e471a49ed6d8e957aeb62972b8dae5304b4440Tom Stellard I != E;) { 6036b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 604f4e471a49ed6d8e957aeb62972b8dae5304b4440Tom Stellard BasicBlock *BB = *I++; 605f4e471a49ed6d8e957aeb62972b8dae5304b4440Tom Stellard if (!SubRegion->contains(BB)) 606f4e471a49ed6d8e957aeb62972b8dae5304b4440Tom Stellard continue; 6076b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 608f4e471a49ed6d8e957aeb62972b8dae5304b4440Tom Stellard // Modify the edges to point to the new exit 609f4e471a49ed6d8e957aeb62972b8dae5304b4440Tom Stellard delPhiValues(BB, OldExit); 610f4e471a49ed6d8e957aeb62972b8dae5304b4440Tom Stellard BB->getTerminator()->replaceUsesOfWith(OldExit, NewExit); 611f4e471a49ed6d8e957aeb62972b8dae5304b4440Tom Stellard addPhiValues(BB, NewExit); 612f4e471a49ed6d8e957aeb62972b8dae5304b4440Tom Stellard 613f4e471a49ed6d8e957aeb62972b8dae5304b4440Tom Stellard // Find the new dominator (if requested) 614f4e471a49ed6d8e957aeb62972b8dae5304b4440Tom Stellard if (IncludeDominator) { 615f4e471a49ed6d8e957aeb62972b8dae5304b4440Tom Stellard if (!Dominator) 616f4e471a49ed6d8e957aeb62972b8dae5304b4440Tom Stellard Dominator = BB; 617f4e471a49ed6d8e957aeb62972b8dae5304b4440Tom Stellard else 618f4e471a49ed6d8e957aeb62972b8dae5304b4440Tom Stellard Dominator = DT->findNearestCommonDominator(Dominator, BB); 619f4e471a49ed6d8e957aeb62972b8dae5304b4440Tom Stellard } 620f4e471a49ed6d8e957aeb62972b8dae5304b4440Tom Stellard } 6216b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 622f4e471a49ed6d8e957aeb62972b8dae5304b4440Tom Stellard // Change the dominator (if requested) 623f4e471a49ed6d8e957aeb62972b8dae5304b4440Tom Stellard if (Dominator) 624f4e471a49ed6d8e957aeb62972b8dae5304b4440Tom Stellard DT->changeImmediateDominator(NewExit, Dominator); 6256b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 626f4e471a49ed6d8e957aeb62972b8dae5304b4440Tom Stellard // Update the region info 627f4e471a49ed6d8e957aeb62972b8dae5304b4440Tom Stellard SubRegion->replaceExit(NewExit); 6286b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 6296b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard } else { 630f4e471a49ed6d8e957aeb62972b8dae5304b4440Tom Stellard BasicBlock *BB = Node->getNodeAs<BasicBlock>(); 631f4e471a49ed6d8e957aeb62972b8dae5304b4440Tom Stellard killTerminator(BB); 632f4e471a49ed6d8e957aeb62972b8dae5304b4440Tom Stellard BranchInst::Create(NewExit, BB); 633f4e471a49ed6d8e957aeb62972b8dae5304b4440Tom Stellard addPhiValues(BB, NewExit); 634f4e471a49ed6d8e957aeb62972b8dae5304b4440Tom Stellard if (IncludeDominator) 635f4e471a49ed6d8e957aeb62972b8dae5304b4440Tom Stellard DT->changeImmediateDominator(NewExit, BB); 6366b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard } 6376b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard} 6386b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 6396b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard/// \brief Create a new flow node and update dominator tree and region info 640f4e471a49ed6d8e957aeb62972b8dae5304b4440Tom StellardBasicBlock *AMDGPUStructurizeCFG::getNextFlow(BasicBlock *Dominator) { 6416b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard LLVMContext &Context = Func->getContext(); 6426b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard BasicBlock *Insert = Order.empty() ? ParentRegion->getExit() : 6436b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard Order.back()->getEntry(); 6446b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard BasicBlock *Flow = BasicBlock::Create(Context, FlowBlockName, 6456b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard Func, Insert); 646f4e471a49ed6d8e957aeb62972b8dae5304b4440Tom Stellard DT->addNewBlock(Flow, Dominator); 6476b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard ParentRegion->getRegionInfo()->setRegionFor(Flow, ParentRegion); 6486b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard return Flow; 6496b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard} 6506b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 651f4e471a49ed6d8e957aeb62972b8dae5304b4440Tom Stellard/// \brief Create a new or reuse the previous node as flow node 652623977d9ba064a6f3b46edee1cb2246716a33397Christian KonigBasicBlock *AMDGPUStructurizeCFG::needPrefix(bool NeedEmpty) { 653f4e471a49ed6d8e957aeb62972b8dae5304b4440Tom Stellard 654623977d9ba064a6f3b46edee1cb2246716a33397Christian Konig BasicBlock *Entry = PrevNode->getEntry(); 655f4e471a49ed6d8e957aeb62972b8dae5304b4440Tom Stellard 656623977d9ba064a6f3b46edee1cb2246716a33397Christian Konig if (!PrevNode->isSubRegion()) { 657623977d9ba064a6f3b46edee1cb2246716a33397Christian Konig killTerminator(Entry); 658623977d9ba064a6f3b46edee1cb2246716a33397Christian Konig if (!NeedEmpty || Entry->getFirstInsertionPt() == Entry->end()) 659623977d9ba064a6f3b46edee1cb2246716a33397Christian Konig return Entry; 660f4e471a49ed6d8e957aeb62972b8dae5304b4440Tom Stellard 661623977d9ba064a6f3b46edee1cb2246716a33397Christian Konig } 662f4e471a49ed6d8e957aeb62972b8dae5304b4440Tom Stellard 663623977d9ba064a6f3b46edee1cb2246716a33397Christian Konig // create a new flow node 664623977d9ba064a6f3b46edee1cb2246716a33397Christian Konig BasicBlock *Flow = getNextFlow(Entry); 665f4e471a49ed6d8e957aeb62972b8dae5304b4440Tom Stellard 666623977d9ba064a6f3b46edee1cb2246716a33397Christian Konig // and wire it up 667623977d9ba064a6f3b46edee1cb2246716a33397Christian Konig changeExit(PrevNode, Flow, true); 668623977d9ba064a6f3b46edee1cb2246716a33397Christian Konig PrevNode = ParentRegion->getBBNode(Flow); 669623977d9ba064a6f3b46edee1cb2246716a33397Christian Konig return Flow; 670f4e471a49ed6d8e957aeb62972b8dae5304b4440Tom Stellard} 671f4e471a49ed6d8e957aeb62972b8dae5304b4440Tom Stellard 672f4e471a49ed6d8e957aeb62972b8dae5304b4440Tom Stellard/// \brief Returns the region exit if possible, otherwise just a new flow node 673f4e471a49ed6d8e957aeb62972b8dae5304b4440Tom StellardBasicBlock *AMDGPUStructurizeCFG::needPostfix(BasicBlock *Flow, 674f4e471a49ed6d8e957aeb62972b8dae5304b4440Tom Stellard bool ExitUseAllowed) { 675f4e471a49ed6d8e957aeb62972b8dae5304b4440Tom Stellard 676f4e471a49ed6d8e957aeb62972b8dae5304b4440Tom Stellard if (Order.empty() && ExitUseAllowed) { 677f4e471a49ed6d8e957aeb62972b8dae5304b4440Tom Stellard BasicBlock *Exit = ParentRegion->getExit(); 678f4e471a49ed6d8e957aeb62972b8dae5304b4440Tom Stellard DT->changeImmediateDominator(Exit, Flow); 679f4e471a49ed6d8e957aeb62972b8dae5304b4440Tom Stellard addPhiValues(Flow, Exit); 680f4e471a49ed6d8e957aeb62972b8dae5304b4440Tom Stellard return Exit; 681f4e471a49ed6d8e957aeb62972b8dae5304b4440Tom Stellard } 682f4e471a49ed6d8e957aeb62972b8dae5304b4440Tom Stellard return getNextFlow(Flow); 683f4e471a49ed6d8e957aeb62972b8dae5304b4440Tom Stellard} 684f4e471a49ed6d8e957aeb62972b8dae5304b4440Tom Stellard 685623977d9ba064a6f3b46edee1cb2246716a33397Christian Konig/// \brief Set the previous node 686623977d9ba064a6f3b46edee1cb2246716a33397Christian Konigvoid AMDGPUStructurizeCFG::setPrevNode(BasicBlock *BB) { 687623977d9ba064a6f3b46edee1cb2246716a33397Christian Konig PrevNode = ParentRegion->contains(BB) ? ParentRegion->getBBNode(BB) : 0; 688f4e471a49ed6d8e957aeb62972b8dae5304b4440Tom Stellard} 689f4e471a49ed6d8e957aeb62972b8dae5304b4440Tom Stellard 690f4e471a49ed6d8e957aeb62972b8dae5304b4440Tom Stellard/// \brief Does BB dominate all the predicates of Node ? 691f4e471a49ed6d8e957aeb62972b8dae5304b4440Tom Stellardbool AMDGPUStructurizeCFG::dominatesPredicates(BasicBlock *BB, RegionNode *Node) { 692f4e471a49ed6d8e957aeb62972b8dae5304b4440Tom Stellard BBPredicates &Preds = Predicates[Node->getEntry()]; 693f4e471a49ed6d8e957aeb62972b8dae5304b4440Tom Stellard for (BBPredicates::iterator PI = Preds.begin(), PE = Preds.end(); 694f4e471a49ed6d8e957aeb62972b8dae5304b4440Tom Stellard PI != PE; ++PI) { 695f4e471a49ed6d8e957aeb62972b8dae5304b4440Tom Stellard 696f4e471a49ed6d8e957aeb62972b8dae5304b4440Tom Stellard if (!DT->dominates(BB, PI->first)) 697f4e471a49ed6d8e957aeb62972b8dae5304b4440Tom Stellard return false; 698f4e471a49ed6d8e957aeb62972b8dae5304b4440Tom Stellard } 699f4e471a49ed6d8e957aeb62972b8dae5304b4440Tom Stellard return true; 700f4e471a49ed6d8e957aeb62972b8dae5304b4440Tom Stellard} 701f4e471a49ed6d8e957aeb62972b8dae5304b4440Tom Stellard 7026b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard/// \brief Can we predict that this node will always be called? 703623977d9ba064a6f3b46edee1cb2246716a33397Christian Konigbool AMDGPUStructurizeCFG::isPredictableTrue(RegionNode *Node) { 704f4e471a49ed6d8e957aeb62972b8dae5304b4440Tom Stellard 705623977d9ba064a6f3b46edee1cb2246716a33397Christian Konig BBPredicates &Preds = Predicates[Node->getEntry()]; 706623977d9ba064a6f3b46edee1cb2246716a33397Christian Konig bool Dominated = false; 707623977d9ba064a6f3b46edee1cb2246716a33397Christian Konig 708623977d9ba064a6f3b46edee1cb2246716a33397Christian Konig // Regionentry is always true 709623977d9ba064a6f3b46edee1cb2246716a33397Christian Konig if (PrevNode == 0) 710623977d9ba064a6f3b46edee1cb2246716a33397Christian Konig return true; 7116b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 7126b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard for (BBPredicates::iterator I = Preds.begin(), E = Preds.end(); 7136b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard I != E; ++I) { 7146b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 7156b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard if (I->second != BoolTrue) 7166b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard return false; 7176b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 718623977d9ba064a6f3b46edee1cb2246716a33397Christian Konig if (!Dominated && DT->dominates(I->first, PrevNode->getEntry())) 7196b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard Dominated = true; 7206b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard } 721f4e471a49ed6d8e957aeb62972b8dae5304b4440Tom Stellard 722f4e471a49ed6d8e957aeb62972b8dae5304b4440Tom Stellard // TODO: The dominator check is too strict 7236b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard return Dominated; 7246b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard} 7256b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 726f4e471a49ed6d8e957aeb62972b8dae5304b4440Tom Stellard/// Take one node from the order vector and wire it up 727623977d9ba064a6f3b46edee1cb2246716a33397Christian Konigvoid AMDGPUStructurizeCFG::wireFlow(bool ExitUseAllowed, 728623977d9ba064a6f3b46edee1cb2246716a33397Christian Konig BasicBlock *LoopEnd) { 7296b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 730f4e471a49ed6d8e957aeb62972b8dae5304b4440Tom Stellard RegionNode *Node = Order.pop_back_val(); 731623977d9ba064a6f3b46edee1cb2246716a33397Christian Konig Visited.insert(Node->getEntry()); 7326b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 733623977d9ba064a6f3b46edee1cb2246716a33397Christian Konig if (isPredictableTrue(Node)) { 734f4e471a49ed6d8e957aeb62972b8dae5304b4440Tom Stellard // Just a linear flow 735623977d9ba064a6f3b46edee1cb2246716a33397Christian Konig if (PrevNode) { 736623977d9ba064a6f3b46edee1cb2246716a33397Christian Konig changeExit(PrevNode, Node->getEntry(), true); 737f4e471a49ed6d8e957aeb62972b8dae5304b4440Tom Stellard } 738623977d9ba064a6f3b46edee1cb2246716a33397Christian Konig PrevNode = Node; 7396b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 7406b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard } else { 741f4e471a49ed6d8e957aeb62972b8dae5304b4440Tom Stellard // Insert extra prefix node (or reuse last one) 742623977d9ba064a6f3b46edee1cb2246716a33397Christian Konig BasicBlock *Flow = needPrefix(false); 7436b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 744f4e471a49ed6d8e957aeb62972b8dae5304b4440Tom Stellard // Insert extra postfix node (or use exit instead) 745f4e471a49ed6d8e957aeb62972b8dae5304b4440Tom Stellard BasicBlock *Entry = Node->getEntry(); 746623977d9ba064a6f3b46edee1cb2246716a33397Christian Konig BasicBlock *Next = needPostfix(Flow, ExitUseAllowed); 747f4e471a49ed6d8e957aeb62972b8dae5304b4440Tom Stellard 748f4e471a49ed6d8e957aeb62972b8dae5304b4440Tom Stellard // let it point to entry and next block 749f4e471a49ed6d8e957aeb62972b8dae5304b4440Tom Stellard Conditions.push_back(BranchInst::Create(Entry, Next, BoolUndef, Flow)); 750f4e471a49ed6d8e957aeb62972b8dae5304b4440Tom Stellard addPhiValues(Flow, Entry); 751f4e471a49ed6d8e957aeb62972b8dae5304b4440Tom Stellard DT->changeImmediateDominator(Entry, Flow); 752f4e471a49ed6d8e957aeb62972b8dae5304b4440Tom Stellard 753623977d9ba064a6f3b46edee1cb2246716a33397Christian Konig PrevNode = Node; 754623977d9ba064a6f3b46edee1cb2246716a33397Christian Konig while (!Order.empty() && !Visited.count(LoopEnd) && 755f4e471a49ed6d8e957aeb62972b8dae5304b4440Tom Stellard dominatesPredicates(Entry, Order.back())) { 756623977d9ba064a6f3b46edee1cb2246716a33397Christian Konig handleLoops(false, LoopEnd); 7576b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard } 7586b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 759623977d9ba064a6f3b46edee1cb2246716a33397Christian Konig changeExit(PrevNode, Next, false); 760623977d9ba064a6f3b46edee1cb2246716a33397Christian Konig setPrevNode(Next); 7616b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard } 762623977d9ba064a6f3b46edee1cb2246716a33397Christian Konig} 7636b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 764623977d9ba064a6f3b46edee1cb2246716a33397Christian Konigvoid AMDGPUStructurizeCFG::handleLoops(bool ExitUseAllowed, 765623977d9ba064a6f3b46edee1cb2246716a33397Christian Konig BasicBlock *LoopEnd) { 766623977d9ba064a6f3b46edee1cb2246716a33397Christian Konig RegionNode *Node = Order.back(); 767623977d9ba064a6f3b46edee1cb2246716a33397Christian Konig BasicBlock *LoopStart = Node->getEntry(); 768623977d9ba064a6f3b46edee1cb2246716a33397Christian Konig 769623977d9ba064a6f3b46edee1cb2246716a33397Christian Konig if (!Loops.count(LoopStart)) { 770623977d9ba064a6f3b46edee1cb2246716a33397Christian Konig wireFlow(ExitUseAllowed, LoopEnd); 771623977d9ba064a6f3b46edee1cb2246716a33397Christian Konig return; 772623977d9ba064a6f3b46edee1cb2246716a33397Christian Konig } 773623977d9ba064a6f3b46edee1cb2246716a33397Christian Konig 774623977d9ba064a6f3b46edee1cb2246716a33397Christian Konig if (!isPredictableTrue(Node)) 775623977d9ba064a6f3b46edee1cb2246716a33397Christian Konig LoopStart = needPrefix(true); 776623977d9ba064a6f3b46edee1cb2246716a33397Christian Konig 777623977d9ba064a6f3b46edee1cb2246716a33397Christian Konig LoopEnd = Loops[Node->getEntry()]; 778623977d9ba064a6f3b46edee1cb2246716a33397Christian Konig wireFlow(false, LoopEnd); 779623977d9ba064a6f3b46edee1cb2246716a33397Christian Konig while (!Visited.count(LoopEnd)) { 780623977d9ba064a6f3b46edee1cb2246716a33397Christian Konig handleLoops(false, LoopEnd); 781623977d9ba064a6f3b46edee1cb2246716a33397Christian Konig } 782623977d9ba064a6f3b46edee1cb2246716a33397Christian Konig 783623977d9ba064a6f3b46edee1cb2246716a33397Christian Konig // Create an extra loop end node 784623977d9ba064a6f3b46edee1cb2246716a33397Christian Konig LoopEnd = needPrefix(false); 785623977d9ba064a6f3b46edee1cb2246716a33397Christian Konig BasicBlock *Next = needPostfix(LoopEnd, ExitUseAllowed); 786623977d9ba064a6f3b46edee1cb2246716a33397Christian Konig LoopConds.push_back(BranchInst::Create(Next, LoopStart, 787623977d9ba064a6f3b46edee1cb2246716a33397Christian Konig BoolUndef, LoopEnd)); 788623977d9ba064a6f3b46edee1cb2246716a33397Christian Konig addPhiValues(LoopEnd, LoopStart); 789623977d9ba064a6f3b46edee1cb2246716a33397Christian Konig setPrevNode(Next); 7906b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard} 7916b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 7926b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard/// After this function control flow looks like it should be, but 793f4e471a49ed6d8e957aeb62972b8dae5304b4440Tom Stellard/// branches and PHI nodes only have undefined conditions. 7946b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellardvoid AMDGPUStructurizeCFG::createFlow() { 795f4e471a49ed6d8e957aeb62972b8dae5304b4440Tom Stellard 796f4e471a49ed6d8e957aeb62972b8dae5304b4440Tom Stellard BasicBlock *Exit = ParentRegion->getExit(); 797f4e471a49ed6d8e957aeb62972b8dae5304b4440Tom Stellard bool EntryDominatesExit = DT->dominates(ParentRegion->getEntry(), Exit); 798f4e471a49ed6d8e957aeb62972b8dae5304b4440Tom Stellard 7996b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard DeletedPhis.clear(); 80013cf6cb57ad6e0bcd66c0ff11b4c4c568ee2f164Tom Stellard AddedPhis.clear(); 801f4e471a49ed6d8e957aeb62972b8dae5304b4440Tom Stellard Conditions.clear(); 802623977d9ba064a6f3b46edee1cb2246716a33397Christian Konig LoopConds.clear(); 8036b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 804623977d9ba064a6f3b46edee1cb2246716a33397Christian Konig PrevNode = 0; 805623977d9ba064a6f3b46edee1cb2246716a33397Christian Konig Visited.clear(); 806f4e471a49ed6d8e957aeb62972b8dae5304b4440Tom Stellard 807623977d9ba064a6f3b46edee1cb2246716a33397Christian Konig while (!Order.empty()) { 808623977d9ba064a6f3b46edee1cb2246716a33397Christian Konig handleLoops(EntryDominatesExit, 0); 8096b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard } 8106b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 811623977d9ba064a6f3b46edee1cb2246716a33397Christian Konig if (PrevNode) 812623977d9ba064a6f3b46edee1cb2246716a33397Christian Konig changeExit(PrevNode, Exit, EntryDominatesExit); 813f4e471a49ed6d8e957aeb62972b8dae5304b4440Tom Stellard else 814f4e471a49ed6d8e957aeb62972b8dae5304b4440Tom Stellard assert(EntryDominatesExit); 8156b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard} 8166b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 8176b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard/// Handle a rare case where the disintegrated nodes instructions 8186b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard/// no longer dominate all their uses. Not sure if this is really nessasary 8196b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellardvoid AMDGPUStructurizeCFG::rebuildSSA() { 8206b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard SSAUpdater Updater; 8216b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard for (Region::block_iterator I = ParentRegion->block_begin(), 8226b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard E = ParentRegion->block_end(); 8236b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard I != E; ++I) { 8246b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 8256b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard BasicBlock *BB = *I; 8266b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard for (BasicBlock::iterator II = BB->begin(), IE = BB->end(); 8276b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard II != IE; ++II) { 8286b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 8296b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard bool Initialized = false; 8306b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard for (Use *I = &II->use_begin().getUse(), *Next; I; I = Next) { 8316b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 8326b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard Next = I->getNext(); 8336b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 8346b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard Instruction *User = cast<Instruction>(I->getUser()); 8356b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard if (User->getParent() == BB) { 8366b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard continue; 8376b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 8386b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard } else if (PHINode *UserPN = dyn_cast<PHINode>(User)) { 8396b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard if (UserPN->getIncomingBlock(*I) == BB) 8406b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard continue; 8416b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard } 8426b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 8436b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard if (DT->dominates(II, User)) 8446b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard continue; 8456b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 8466b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard if (!Initialized) { 8476b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard Value *Undef = UndefValue::get(II->getType()); 8486b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard Updater.Initialize(II->getType(), ""); 8496b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard Updater.AddAvailableValue(&Func->getEntryBlock(), Undef); 8506b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard Updater.AddAvailableValue(BB, II); 8516b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard Initialized = true; 8526b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard } 8536b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard Updater.RewriteUseAfterInsertions(*I); 8546b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard } 8556b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard } 8566b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard } 8576b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard} 8586b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 8596b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard/// \brief Run the transformation for each region found 8606b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellardbool AMDGPUStructurizeCFG::runOnRegion(Region *R, RGPassManager &RGM) { 8616b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard if (R->isTopLevelRegion()) 8626b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard return false; 8636b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 8646b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard Func = R->getEntry()->getParent(); 8656b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard ParentRegion = R; 8666b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 8676b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard DT = &getAnalysis<DominatorTree>(); 8686b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 8696b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard orderNodes(); 8706b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard collectInfos(); 8716b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard createFlow(); 872623977d9ba064a6f3b46edee1cb2246716a33397Christian Konig insertConditions(false); 873623977d9ba064a6f3b46edee1cb2246716a33397Christian Konig insertConditions(true); 87413cf6cb57ad6e0bcd66c0ff11b4c4c568ee2f164Tom Stellard setPhiValues(); 8756b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard rebuildSSA(); 8766b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 87727f5d0618188a4a51cc222a0d71c5aa845f31189Tom Stellard // Cleanup 8786b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard Order.clear(); 8796b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard Visited.clear(); 8806b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard DeletedPhis.clear(); 88113cf6cb57ad6e0bcd66c0ff11b4c4c568ee2f164Tom Stellard AddedPhis.clear(); 882623977d9ba064a6f3b46edee1cb2246716a33397Christian Konig Predicates.clear(); 88327f5d0618188a4a51cc222a0d71c5aa845f31189Tom Stellard Conditions.clear(); 884623977d9ba064a6f3b46edee1cb2246716a33397Christian Konig Loops.clear(); 885623977d9ba064a6f3b46edee1cb2246716a33397Christian Konig LoopPreds.clear(); 886623977d9ba064a6f3b46edee1cb2246716a33397Christian Konig LoopConds.clear(); 8876b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 8886b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard return true; 8896b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard} 8906b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard 8916b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard/// \brief Create the pass 8926b7d99d47321ebb478b22afd2e317fe89d2149dbTom StellardPass *llvm::createAMDGPUStructurizeCFGPass() { 8936b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard return new AMDGPUStructurizeCFG(); 8946b7d99d47321ebb478b22afd2e317fe89d2149dbTom Stellard} 895