148486893f46d2e12e926682a3ecb908716bc66c4Chris Lattner//===-- Local.h - Functions to perform local transformations ----*- C++ -*-===// 234695381d626485a560594f162701088079589dfMisha Brukman// 36fbcc26f1460eaee4e0eb8b426fc1ff0c7af11beJohn Criswell// The LLVM Compiler Infrastructure 46fbcc26f1460eaee4e0eb8b426fc1ff0c7af11beJohn Criswell// 57ed47a13356daed2a34cd2209a31f92552e3bdd8Chris Lattner// This file is distributed under the University of Illinois Open Source 67ed47a13356daed2a34cd2209a31f92552e3bdd8Chris Lattner// License. See LICENSE.TXT for details. 734695381d626485a560594f162701088079589dfMisha Brukman// 86fbcc26f1460eaee4e0eb8b426fc1ff0c7af11beJohn Criswell//===----------------------------------------------------------------------===// 9148a0bfcea5d3267eac02613cfcc8b5fe8894f2cChris Lattner// 10148a0bfcea5d3267eac02613cfcc8b5fe8894f2cChris Lattner// This family of functions perform various local transformations to the 11148a0bfcea5d3267eac02613cfcc8b5fe8894f2cChris Lattner// program. 12148a0bfcea5d3267eac02613cfcc8b5fe8894f2cChris Lattner// 13148a0bfcea5d3267eac02613cfcc8b5fe8894f2cChris Lattner//===----------------------------------------------------------------------===// 14148a0bfcea5d3267eac02613cfcc8b5fe8894f2cChris Lattner 15148a0bfcea5d3267eac02613cfcc8b5fe8894f2cChris Lattner#ifndef LLVM_TRANSFORMS_UTILS_LOCAL_H 16148a0bfcea5d3267eac02613cfcc8b5fe8894f2cChris Lattner#define LLVM_TRANSFORMS_UTILS_LOCAL_H 17148a0bfcea5d3267eac02613cfcc8b5fe8894f2cChris Lattner 180b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/DataLayout.h" 1936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/IR/GetElementPtrTypeIterator.h" 200b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/IRBuilder.h" 210b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Operator.h" 225c525b59d5e0036a778d278eeff4832edfd41357Nuno Lopes 23d0fde30ce850b78371fd1386338350591f9ff494Brian Gaekenamespace llvm { 24d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 25c79e1182470ed12f1f3d0d35c1725366519a9af7Devang Patelclass User; 26d68a07650cdb2e18f18f362ba533459aa10e01b6Dan Gohmanclass BasicBlock; 27813c9a0f19c0d27085a3ea81eb44033747007741Devang Patelclass Function; 284b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohmanclass BranchInst; 29d68a07650cdb2e18f18f362ba533459aa10e01b6Dan Gohmanclass Instruction; 305ee20680c7ebc765950983633e19fafab5235245Devang Patelclass DbgDeclareInst; 315ee20680c7ebc765950983633e19fafab5235245Devang Patelclass StoreInst; 3236fae67831517f132255118b45b21a8cf199a012Devang Patelclass LoadInst; 33d68a07650cdb2e18f18f362ba533459aa10e01b6Dan Gohmanclass Value; 343e57cb98bde04a65623493738d51f2a41e601748Chris Lattnerclass Pass; 35abbc2dd77908f146f73f4cd1abfdfe47faacf43dChris Lattnerclass PHINode; 36cbf99ee973b6c6e6cd9537dae12031382783bc61Chris Lattnerclass AllocaInst; 37c5406b55d58b7378822d5f6316bf253ad0eaa82dChris Lattnerclass ConstantExpr; 383574eca1b02600bac4e625297f4ecf745f4c4f32Micah Villmowclass DataLayout; 398e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramerclass TargetLibraryInfo; 4004d7d13d301df66f6c232e41611145c062183bf3Hans Wennborgclass TargetTransformInfo; 415ee20680c7ebc765950983633e19fafab5235245Devang Patelclass DIBuilder; 4257e6b2d1f3de0bf459e96f7038e692d624f7e580Tom Stellardclass AliasAnalysis; 43d68a07650cdb2e18f18f362ba533459aa10e01b6Dan Gohman 44d68a07650cdb2e18f18f362ba533459aa10e01b6Dan Gohmantemplate<typename T> class SmallVectorImpl; 4538140c2bbe80d146f59863b96947e83f4942bda0Matt Arsenault 46148a0bfcea5d3267eac02613cfcc8b5fe8894f2cChris Lattner//===----------------------------------------------------------------------===// 473481f24c06b3c9de48bdd99c37547471ca8e761eChris Lattner// Local constant propagation. 48148a0bfcea5d3267eac02613cfcc8b5fe8894f2cChris Lattner// 49148a0bfcea5d3267eac02613cfcc8b5fe8894f2cChris Lattner 503e57cb98bde04a65623493738d51f2a41e601748Chris Lattner/// ConstantFoldTerminator - If a terminator instruction is predicated on a 513e57cb98bde04a65623493738d51f2a41e601748Chris Lattner/// constant value, convert it into an unconditional branch to the constant 523e57cb98bde04a65623493738d51f2a41e601748Chris Lattner/// destination. This is a nontrivial operation because the successors of this 533e57cb98bde04a65623493738d51f2a41e601748Chris Lattner/// basic block must have their PHI nodes updated. 545649ba70fb39f2fda4791d255ae8bb373071874fFrits van Bommel/// Also calls RecursivelyDeleteTriviallyDeadInstructions() on any branch/switch 555649ba70fb39f2fda4791d255ae8bb373071874fFrits van Bommel/// conditions and indirectbr addresses this might make dead if 565649ba70fb39f2fda4791d255ae8bb373071874fFrits van Bommel/// DeleteDeadConditions is true. 578e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramerbool ConstantFoldTerminator(BasicBlock *BB, bool DeleteDeadConditions = false, 58dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines const TargetLibraryInfo *TLI = nullptr); 59148a0bfcea5d3267eac02613cfcc8b5fe8894f2cChris Lattner 60148a0bfcea5d3267eac02613cfcc8b5fe8894f2cChris Lattner//===----------------------------------------------------------------------===// 613481f24c06b3c9de48bdd99c37547471ca8e761eChris Lattner// Local dead code elimination. 62148a0bfcea5d3267eac02613cfcc8b5fe8894f2cChris Lattner// 63148a0bfcea5d3267eac02613cfcc8b5fe8894f2cChris Lattner 643e57cb98bde04a65623493738d51f2a41e601748Chris Lattner/// isInstructionTriviallyDead - Return true if the result produced by the 653e57cb98bde04a65623493738d51f2a41e601748Chris Lattner/// instruction is not used, and the instruction has no side effects. 663e57cb98bde04a65623493738d51f2a41e601748Chris Lattner/// 67dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hinesbool isInstructionTriviallyDead(Instruction *I, 68dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines const TargetLibraryInfo *TLI = nullptr); 69148a0bfcea5d3267eac02613cfcc8b5fe8894f2cChris Lattner 703481f24c06b3c9de48bdd99c37547471ca8e761eChris Lattner/// RecursivelyDeleteTriviallyDeadInstructions - If the specified value is a 713481f24c06b3c9de48bdd99c37547471ca8e761eChris Lattner/// trivially dead instruction, delete it. If that makes any of its operands 7290fe0bd68cdbeb980c08628c4992dffad0dc728fDan Gohman/// trivially dead, delete them too, recursively. Return true if any 7390fe0bd68cdbeb980c08628c4992dffad0dc728fDan Gohman/// instructions were deleted. 748e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramerbool RecursivelyDeleteTriviallyDeadInstructions(Value *V, 75dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines const TargetLibraryInfo *TLI = nullptr); 76afc36a9520971832dfbebc0333593bf5d3098296Dan Gohman 77afc36a9520971832dfbebc0333593bf5d3098296Dan Gohman/// RecursivelyDeleteDeadPHINode - If the specified value is an effectively 78afc36a9520971832dfbebc0333593bf5d3098296Dan Gohman/// dead PHI node, due to being a def-use chain of single-use nodes that 79afc36a9520971832dfbebc0333593bf5d3098296Dan Gohman/// either forms a cycle or is terminated by a trivially dead instruction, 80afc36a9520971832dfbebc0333593bf5d3098296Dan Gohman/// delete it. If that makes any of its operands trivially dead, delete them 812cfbf018a938d14126b9cb10c600e025f9831d2dDuncan Sands/// too, recursively. Return true if a change was made. 82dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hinesbool RecursivelyDeleteDeadPHINode(PHINode *PN, 83dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines const TargetLibraryInfo *TLI = nullptr); 8438140c2bbe80d146f59863b96947e83f4942bda0Matt Arsenault 85e234a30a282f1aaec4aa63460fe8bba6416832a8Chris Lattner/// SimplifyInstructionsInBlock - Scan the specified basic block and try to 86e234a30a282f1aaec4aa63460fe8bba6416832a8Chris Lattner/// simplify any instructions in it and recursively delete dead instructions. 87e234a30a282f1aaec4aa63460fe8bba6416832a8Chris Lattner/// 88e234a30a282f1aaec4aa63460fe8bba6416832a8Chris Lattner/// This returns true if it changed the code, note that it can delete 89e234a30a282f1aaec4aa63460fe8bba6416832a8Chris Lattner/// instructions in other blocks as well in this block. 90dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hinesbool SimplifyInstructionsInBlock(BasicBlock *BB, const DataLayout *TD = nullptr, 91dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines const TargetLibraryInfo *TLI = nullptr); 9238140c2bbe80d146f59863b96947e83f4942bda0Matt Arsenault 93abbc2dd77908f146f73f4cd1abfdfe47faacf43dChris Lattner//===----------------------------------------------------------------------===// 9429874e0dc6c4e55bc384611273343bb358982cc3Chris Lattner// Control Flow Graph Restructuring. 95148a0bfcea5d3267eac02613cfcc8b5fe8894f2cChris Lattner// 96148a0bfcea5d3267eac02613cfcc8b5fe8894f2cChris Lattner 9740d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner/// RemovePredecessorAndSimplify - Like BasicBlock::removePredecessor, this 9840d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner/// method is called when we're about to delete Pred as a predecessor of BB. If 9940d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner/// BB contains any PHI nodes, this drops the entries in the PHI nodes for Pred. 10040d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner/// 10140d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner/// Unlike the removePredecessor method, this attempts to simplify uses of PHI 10240d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner/// nodes that collapse into identity values. For example, if we have: 10340d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner/// x = phi(1, 0, 0, 0) 10440d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner/// y = and x, z 10540d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner/// 10640d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner/// .. and delete the predecessor corresponding to the '1', this will attempt to 10740d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner/// recursively fold the 'and' to 0. 10840d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattnervoid RemovePredecessorAndSimplify(BasicBlock *BB, BasicBlock *Pred, 109dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines DataLayout *TD = nullptr); 11038140c2bbe80d146f59863b96947e83f4942bda0Matt Arsenault 111b29714a10af94b6daae437e48a82ae32675f79cbChris Lattner/// MergeBasicBlockIntoOnlyPred - BB is a block with one predecessor and its 112b29714a10af94b6daae437e48a82ae32675f79cbChris Lattner/// predecessor is known to have one successor (BB!). Eliminate the edge 113b29714a10af94b6daae437e48a82ae32675f79cbChris Lattner/// between them, moving the instructions in the predecessor into BB. This 114b29714a10af94b6daae437e48a82ae32675f79cbChris Lattner/// deletes the predecessor block. 115b29714a10af94b6daae437e48a82ae32675f79cbChris Lattner/// 116dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hinesvoid MergeBasicBlockIntoOnlyPred(BasicBlock *BB, Pass *P = nullptr); 117dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner 118dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner/// TryToSimplifyUncondBranchFromEmptyBlock - BB is known to contain an 119dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner/// unconditional branch, and contains no instructions other than PHI nodes, 120dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner/// potential debug intrinsics and the branch. If possible, eliminate BB by 121dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner/// rewriting all the predecessors to branch to the successor block and return 122dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner/// true. If we can't transform, return false. 123dce94d92df77da125a1c1256a9294db891a9db9cChris Lattnerbool TryToSimplifyUncondBranchFromEmptyBlock(BasicBlock *BB); 12420f4d34fe3609cda8b70956a36080e9cbcd327d4Jim Grosbach 12520f4d34fe3609cda8b70956a36080e9cbcd327d4Jim Grosbach/// EliminateDuplicatePHINodes - Check for and eliminate duplicate PHI 12620f4d34fe3609cda8b70956a36080e9cbcd327d4Jim Grosbach/// nodes in this block. This doesn't try to be clever about PHI nodes 12720f4d34fe3609cda8b70956a36080e9cbcd327d4Jim Grosbach/// which differ only in the order of the incoming values, but instcombine 12820f4d34fe3609cda8b70956a36080e9cbcd327d4Jim Grosbach/// orders them so it usually won't matter. 12920f4d34fe3609cda8b70956a36080e9cbcd327d4Jim Grosbach/// 13020f4d34fe3609cda8b70956a36080e9cbcd327d4Jim Grosbachbool EliminateDuplicatePHINodes(BasicBlock *BB); 13120f4d34fe3609cda8b70956a36080e9cbcd327d4Jim Grosbach 1323e57cb98bde04a65623493738d51f2a41e601748Chris Lattner/// SimplifyCFG - This function is used to do simplification of a CFG. For 1333e57cb98bde04a65623493738d51f2a41e601748Chris Lattner/// example, it adjusts branches to branches to eliminate the extra hop, it 1343e57cb98bde04a65623493738d51f2a41e601748Chris Lattner/// eliminates unreachable basic blocks, and does other "peephole" optimization 1353e57cb98bde04a65623493738d51f2a41e601748Chris Lattner/// of the CFG. It returns true if a modification was made, possibly deleting 1363e57cb98bde04a65623493738d51f2a41e601748Chris Lattner/// the basic block that was pointed to. 1373e57cb98bde04a65623493738d51f2a41e601748Chris Lattner/// 1385f46c3c2e8d13c6ac8d3863d84e887f84c73f27aChandler Carruthbool SimplifyCFG(BasicBlock *BB, const TargetTransformInfo &TTI, 139dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines const DataLayout *TD = nullptr); 14001d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard 14101d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard/// FlatternCFG - This function is used to flatten a CFG. For 14201d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard/// example, it uses parallel-and and parallel-or mode to collapse 14301d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard// if-conditions and merge if-regions with identical statements. 14401d7203ef8316fdd71c3cec59f8e68fb869e0dbfTom Stellard/// 145dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hinesbool FlattenCFG(BasicBlock *BB, AliasAnalysis *AA = nullptr); 146148a0bfcea5d3267eac02613cfcc8b5fe8894f2cChris Lattner 1474b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman/// FoldBranchToCommonDest - If this basic block is ONLY a setcc and a branch, 1484b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman/// and if a predecessor branches to us and one of our successors, fold the 1494b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman/// setcc into the predecessor and use logical operations to pick the right 1504b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman/// destination. 151cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hinesbool FoldBranchToCommonDest(BranchInst *BI, const DataLayout *DL = nullptr); 1524b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman 153cbf99ee973b6c6e6cd9537dae12031382783bc61Chris Lattner/// DemoteRegToStack - This function takes a virtual register computed by an 1548f71b63bead24de7acc6fe7f0487bf56da22d745Chris Lattner/// Instruction and replaces it with a slot in the stack frame, allocated via 155cbf99ee973b6c6e6cd9537dae12031382783bc61Chris Lattner/// alloca. This allows the CFG to be changed around without fear of 156cbf99ee973b6c6e6cd9537dae12031382783bc61Chris Lattner/// invalidating the SSA information for the value. It returns the pointer to 157cbf99ee973b6c6e6cd9537dae12031382783bc61Chris Lattner/// the alloca inserted to create a stack slot for X. 158cbf99ee973b6c6e6cd9537dae12031382783bc61Chris Lattner/// 15950dead06ffc107edb7e84857baaeeb09039c631cOwen AndersonAllocaInst *DemoteRegToStack(Instruction &X, 1609adc0abad3c3ed40a268ccbcee0c74cb9e1359feOwen Anderson bool VolatileLoads = false, 161dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Instruction *AllocaPoint = nullptr); 162cbf99ee973b6c6e6cd9537dae12031382783bc61Chris Lattner 16308d14d2469c4f0465f610a204353220ee2ccde9cTanya Lattner/// DemotePHIToStack - This function takes a virtual register computed by a phi 16408d14d2469c4f0465f610a204353220ee2ccde9cTanya Lattner/// node and replaces it with a slot in the stack frame, allocated via alloca. 16538140c2bbe80d146f59863b96947e83f4942bda0Matt Arsenault/// The phi node is deleted and it returns the pointer to the alloca inserted. 166dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen HinesAllocaInst *DemotePHIToStack(PHINode *P, Instruction *AllocaPoint = nullptr); 16708d14d2469c4f0465f610a204353220ee2ccde9cTanya Lattner 168687140c818ba4b896329a83324714140b6580ef8Chris Lattner/// getOrEnforceKnownAlignment - If the specified pointer has an alignment that 169687140c818ba4b896329a83324714140b6580ef8Chris Lattner/// we can determine, return it, otherwise return 0. If PrefAlign is specified, 170687140c818ba4b896329a83324714140b6580ef8Chris Lattner/// and it is more than the alignment of the ultimate object, see if we can 171687140c818ba4b896329a83324714140b6580ef8Chris Lattner/// increase the alignment of the ultimate object, making this check succeed. 172687140c818ba4b896329a83324714140b6580ef8Chris Lattnerunsigned getOrEnforceKnownAlignment(Value *V, unsigned PrefAlign, 173dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines const DataLayout *TD = nullptr); 174687140c818ba4b896329a83324714140b6580ef8Chris Lattner 175687140c818ba4b896329a83324714140b6580ef8Chris Lattner/// getKnownAlignment - Try to infer an alignment for the specified pointer. 176dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hinesstatic inline unsigned getKnownAlignment(Value *V, 177dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines const DataLayout *TD = nullptr) { 178687140c818ba4b896329a83324714140b6580ef8Chris Lattner return getOrEnforceKnownAlignment(V, 0, TD); 179687140c818ba4b896329a83324714140b6580ef8Chris Lattner} 180687140c818ba4b896329a83324714140b6580ef8Chris Lattner 1815c525b59d5e0036a778d278eeff4832edfd41357Nuno Lopes/// EmitGEPOffset - Given a getelementptr instruction/constantexpr, emit the 1825c525b59d5e0036a778d278eeff4832edfd41357Nuno Lopes/// code necessary to compute the offset from the base pointer (without adding 1835c525b59d5e0036a778d278eeff4832edfd41357Nuno Lopes/// in the base pointer). Return the result as a signed integer of intptr size. 184c606c3ff911eddcbf8bab95e67c7d8c1f69a493eNuno Lopes/// When NoAssumptions is true, no assumptions about index computation not 185c606c3ff911eddcbf8bab95e67c7d8c1f69a493eNuno Lopes/// overflowing is made. 1865c525b59d5e0036a778d278eeff4832edfd41357Nuno Lopestemplate<typename IRBuilderTy> 1873574eca1b02600bac4e625297f4ecf745f4c4f32Micah VillmowValue *EmitGEPOffset(IRBuilderTy *Builder, const DataLayout &TD, User *GEP, 188c606c3ff911eddcbf8bab95e67c7d8c1f69a493eNuno Lopes bool NoAssumptions = false) { 18938140c2bbe80d146f59863b96947e83f4942bda0Matt Arsenault GEPOperator *GEPOp = cast<GEPOperator>(GEP); 1906b4dde71cfdcb2e1f2105dd8a677c14d8c3bb4b4Matt Arsenault Type *IntPtrTy = TD.getIntPtrType(GEP->getType()); 1915c525b59d5e0036a778d278eeff4832edfd41357Nuno Lopes Value *Result = Constant::getNullValue(IntPtrTy); 1925c525b59d5e0036a778d278eeff4832edfd41357Nuno Lopes 1935c525b59d5e0036a778d278eeff4832edfd41357Nuno Lopes // If the GEP is inbounds, we know that none of the addressing operations will 1945c525b59d5e0036a778d278eeff4832edfd41357Nuno Lopes // overflow in an unsigned sense. 19538140c2bbe80d146f59863b96947e83f4942bda0Matt Arsenault bool isInBounds = GEPOp->isInBounds() && !NoAssumptions; 1965c525b59d5e0036a778d278eeff4832edfd41357Nuno Lopes 1975c525b59d5e0036a778d278eeff4832edfd41357Nuno Lopes // Build a mask for high order bits. 1986b4dde71cfdcb2e1f2105dd8a677c14d8c3bb4b4Matt Arsenault unsigned IntPtrWidth = IntPtrTy->getScalarType()->getIntegerBitWidth(); 19938140c2bbe80d146f59863b96947e83f4942bda0Matt Arsenault uint64_t PtrSizeMask = ~0ULL >> (64 - IntPtrWidth); 2005c525b59d5e0036a778d278eeff4832edfd41357Nuno Lopes 20138140c2bbe80d146f59863b96947e83f4942bda0Matt Arsenault gep_type_iterator GTI = gep_type_begin(GEP); 2025c525b59d5e0036a778d278eeff4832edfd41357Nuno Lopes for (User::op_iterator i = GEP->op_begin() + 1, e = GEP->op_end(); i != e; 2035c525b59d5e0036a778d278eeff4832edfd41357Nuno Lopes ++i, ++GTI) { 2045c525b59d5e0036a778d278eeff4832edfd41357Nuno Lopes Value *Op = *i; 2055c525b59d5e0036a778d278eeff4832edfd41357Nuno Lopes uint64_t Size = TD.getTypeAllocSize(GTI.getIndexedType()) & PtrSizeMask; 206c4d070ad07c606f77af15604dbbe817edd11ca9cMatt Arsenault if (Constant *OpC = dyn_cast<Constant>(Op)) { 207c4d070ad07c606f77af15604dbbe817edd11ca9cMatt Arsenault if (OpC->isZeroValue()) 208c4d070ad07c606f77af15604dbbe817edd11ca9cMatt Arsenault continue; 2095c525b59d5e0036a778d278eeff4832edfd41357Nuno Lopes 2105c525b59d5e0036a778d278eeff4832edfd41357Nuno Lopes // Handle a struct index, which adds its field offset to the pointer. 2115c525b59d5e0036a778d278eeff4832edfd41357Nuno Lopes if (StructType *STy = dyn_cast<StructType>(*GTI)) { 212c4d070ad07c606f77af15604dbbe817edd11ca9cMatt Arsenault if (OpC->getType()->isVectorTy()) 213c4d070ad07c606f77af15604dbbe817edd11ca9cMatt Arsenault OpC = OpC->getSplatValue(); 214c4d070ad07c606f77af15604dbbe817edd11ca9cMatt Arsenault 215c4d070ad07c606f77af15604dbbe817edd11ca9cMatt Arsenault uint64_t OpValue = cast<ConstantInt>(OpC)->getZExtValue(); 216c4d070ad07c606f77af15604dbbe817edd11ca9cMatt Arsenault Size = TD.getStructLayout(STy)->getElementOffset(OpValue); 2175c525b59d5e0036a778d278eeff4832edfd41357Nuno Lopes 2185c525b59d5e0036a778d278eeff4832edfd41357Nuno Lopes if (Size) 2195c525b59d5e0036a778d278eeff4832edfd41357Nuno Lopes Result = Builder->CreateAdd(Result, ConstantInt::get(IntPtrTy, Size), 2205c525b59d5e0036a778d278eeff4832edfd41357Nuno Lopes GEP->getName()+".offs"); 2215c525b59d5e0036a778d278eeff4832edfd41357Nuno Lopes continue; 2225c525b59d5e0036a778d278eeff4832edfd41357Nuno Lopes } 2235c525b59d5e0036a778d278eeff4832edfd41357Nuno Lopes 2245c525b59d5e0036a778d278eeff4832edfd41357Nuno Lopes Constant *Scale = ConstantInt::get(IntPtrTy, Size); 2255c525b59d5e0036a778d278eeff4832edfd41357Nuno Lopes Constant *OC = ConstantExpr::getIntegerCast(OpC, IntPtrTy, true /*SExt*/); 2265c525b59d5e0036a778d278eeff4832edfd41357Nuno Lopes Scale = ConstantExpr::getMul(OC, Scale, isInBounds/*NUW*/); 2275c525b59d5e0036a778d278eeff4832edfd41357Nuno Lopes // Emit an add instruction. 2285c525b59d5e0036a778d278eeff4832edfd41357Nuno Lopes Result = Builder->CreateAdd(Result, Scale, GEP->getName()+".offs"); 2295c525b59d5e0036a778d278eeff4832edfd41357Nuno Lopes continue; 2305c525b59d5e0036a778d278eeff4832edfd41357Nuno Lopes } 2315c525b59d5e0036a778d278eeff4832edfd41357Nuno Lopes // Convert to correct type. 2325c525b59d5e0036a778d278eeff4832edfd41357Nuno Lopes if (Op->getType() != IntPtrTy) 2335c525b59d5e0036a778d278eeff4832edfd41357Nuno Lopes Op = Builder->CreateIntCast(Op, IntPtrTy, true, Op->getName()+".c"); 2345c525b59d5e0036a778d278eeff4832edfd41357Nuno Lopes if (Size != 1) { 2355c525b59d5e0036a778d278eeff4832edfd41357Nuno Lopes // We'll let instcombine(mul) convert this to a shl if possible. 2365c525b59d5e0036a778d278eeff4832edfd41357Nuno Lopes Op = Builder->CreateMul(Op, ConstantInt::get(IntPtrTy, Size), 2375c525b59d5e0036a778d278eeff4832edfd41357Nuno Lopes GEP->getName()+".idx", isInBounds /*NUW*/); 2385c525b59d5e0036a778d278eeff4832edfd41357Nuno Lopes } 2395c525b59d5e0036a778d278eeff4832edfd41357Nuno Lopes 2405c525b59d5e0036a778d278eeff4832edfd41357Nuno Lopes // Emit an add instruction. 2415c525b59d5e0036a778d278eeff4832edfd41357Nuno Lopes Result = Builder->CreateAdd(Op, Result, GEP->getName()+".offs"); 2425c525b59d5e0036a778d278eeff4832edfd41357Nuno Lopes } 2435c525b59d5e0036a778d278eeff4832edfd41357Nuno Lopes return Result; 2445c525b59d5e0036a778d278eeff4832edfd41357Nuno Lopes} 2455c525b59d5e0036a778d278eeff4832edfd41357Nuno Lopes 2465ee20680c7ebc765950983633e19fafab5235245Devang Patel///===---------------------------------------------------------------------===// 2475ee20680c7ebc765950983633e19fafab5235245Devang Patel/// Dbg Intrinsic utilities 2485ee20680c7ebc765950983633e19fafab5235245Devang Patel/// 2495ee20680c7ebc765950983633e19fafab5235245Devang Patel 2509d5d58a49b23d4145c8bdb12dd10fc88e37bb8f8Adrian Prantl/// Inserts a llvm.dbg.value intrinsic before a store to an alloca'd value 2515ee20680c7ebc765950983633e19fafab5235245Devang Patel/// that has an associated llvm.dbg.decl intrinsic. 2525ee20680c7ebc765950983633e19fafab5235245Devang Patelbool ConvertDebugDeclareToDebugValue(DbgDeclareInst *DDI, 2535ee20680c7ebc765950983633e19fafab5235245Devang Patel StoreInst *SI, DIBuilder &Builder); 2545ee20680c7ebc765950983633e19fafab5235245Devang Patel 2559d5d58a49b23d4145c8bdb12dd10fc88e37bb8f8Adrian Prantl/// Inserts a llvm.dbg.value intrinsic before a load of an alloca'd value 25636fae67831517f132255118b45b21a8cf199a012Devang Patel/// that has an associated llvm.dbg.decl intrinsic. 25736fae67831517f132255118b45b21a8cf199a012Devang Patelbool ConvertDebugDeclareToDebugValue(DbgDeclareInst *DDI, 25836fae67831517f132255118b45b21a8cf199a012Devang Patel LoadInst *LI, DIBuilder &Builder); 25936fae67831517f132255118b45b21a8cf199a012Devang Patel 260813c9a0f19c0d27085a3ea81eb44033747007741Devang Patel/// LowerDbgDeclare - Lowers llvm.dbg.declare intrinsics into appropriate set 261813c9a0f19c0d27085a3ea81eb44033747007741Devang Patel/// of llvm.dbg.value intrinsics. 262813c9a0f19c0d27085a3ea81eb44033747007741Devang Patelbool LowerDbgDeclare(Function &F); 263813c9a0f19c0d27085a3ea81eb44033747007741Devang Patel 264c827939046670a9800659b83e2048f1d3a79a531Cameron Zwarich/// FindAllocaDbgDeclare - Finds the llvm.dbg.declare intrinsic corresponding to 265c827939046670a9800659b83e2048f1d3a79a531Cameron Zwarich/// an alloca, if any. 266c827939046670a9800659b83e2048f1d3a79a531Cameron ZwarichDbgDeclareInst *FindAllocaDbgDeclare(Value *V); 267c827939046670a9800659b83e2048f1d3a79a531Cameron Zwarich 2681afbb517965e29b07cb42e2335d5eadd87de6535Alexey Samsonov/// replaceDbgDeclareForAlloca - Replaces llvm.dbg.declare instruction when 2691afbb517965e29b07cb42e2335d5eadd87de6535Alexey Samsonov/// alloca is replaced with a new value. 2701afbb517965e29b07cb42e2335d5eadd87de6535Alexey Samsonovbool replaceDbgDeclareForAlloca(AllocaInst *AI, Value *NewAllocaAddress, 2711afbb517965e29b07cb42e2335d5eadd87de6535Alexey Samsonov DIBuilder &Builder); 2721afbb517965e29b07cb42e2335d5eadd87de6535Alexey Samsonov 2733333e668221f52f8c708df0037ee9c4bf2417929Evgeniy Stepanov/// \brief Remove all blocks that can not be reached from the function's entry. 2743333e668221f52f8c708df0037ee9c4bf2417929Evgeniy Stepanov/// 2753333e668221f52f8c708df0037ee9c4bf2417929Evgeniy Stepanov/// Returns true if any basic block was removed. 2763333e668221f52f8c708df0037ee9c4bf2417929Evgeniy Stepanovbool removeUnreachableBlocks(Function &F); 2773333e668221f52f8c708df0037ee9c4bf2417929Evgeniy Stepanov 278d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke} // End llvm namespace 279d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 280148a0bfcea5d3267eac02613cfcc8b5fe8894f2cChris Lattner#endif 281