Local.h revision 2cfbf018a938d14126b9cb10c600e025f9831d2d
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 18d0fde30ce850b78371fd1386338350591f9ff494Brian Gaekenamespace llvm { 19d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 20c79e1182470ed12f1f3d0d35c1725366519a9af7Devang Patelclass User; 21d68a07650cdb2e18f18f362ba533459aa10e01b6Dan Gohmanclass BasicBlock; 224b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohmanclass BranchInst; 23d68a07650cdb2e18f18f362ba533459aa10e01b6Dan Gohmanclass Instruction; 24d68a07650cdb2e18f18f362ba533459aa10e01b6Dan Gohmanclass Value; 253e57cb98bde04a65623493738d51f2a41e601748Chris Lattnerclass Pass; 26abbc2dd77908f146f73f4cd1abfdfe47faacf43dChris Lattnerclass PHINode; 27cbf99ee973b6c6e6cd9537dae12031382783bc61Chris Lattnerclass AllocaInst; 28c5406b55d58b7378822d5f6316bf253ad0eaa82dChris Lattnerclass ConstantExpr; 2973259caa44b03206d1e39e77a7aa375250b1a193Chris Lattnerclass TargetData; 30d68a07650cdb2e18f18f362ba533459aa10e01b6Dan Gohman 31d68a07650cdb2e18f18f362ba533459aa10e01b6Dan Gohmantemplate<typename T> class SmallVectorImpl; 324f02c74a8ec8f4ca83b823146cb9c987ed79b3f6Chris Lattner 33148a0bfcea5d3267eac02613cfcc8b5fe8894f2cChris Lattner//===----------------------------------------------------------------------===// 343481f24c06b3c9de48bdd99c37547471ca8e761eChris Lattner// Local constant propagation. 35148a0bfcea5d3267eac02613cfcc8b5fe8894f2cChris Lattner// 36148a0bfcea5d3267eac02613cfcc8b5fe8894f2cChris Lattner 373e57cb98bde04a65623493738d51f2a41e601748Chris Lattner/// ConstantFoldTerminator - If a terminator instruction is predicated on a 383e57cb98bde04a65623493738d51f2a41e601748Chris Lattner/// constant value, convert it into an unconditional branch to the constant 393e57cb98bde04a65623493738d51f2a41e601748Chris Lattner/// destination. This is a nontrivial operation because the successors of this 403e57cb98bde04a65623493738d51f2a41e601748Chris Lattner/// basic block must have their PHI nodes updated. 413e57cb98bde04a65623493738d51f2a41e601748Chris Lattner/// 4276ae3445f81164aaff9f95123426109c119f27c0Chris Lattnerbool ConstantFoldTerminator(BasicBlock *BB); 43148a0bfcea5d3267eac02613cfcc8b5fe8894f2cChris Lattner 44148a0bfcea5d3267eac02613cfcc8b5fe8894f2cChris Lattner//===----------------------------------------------------------------------===// 453481f24c06b3c9de48bdd99c37547471ca8e761eChris Lattner// Local dead code elimination. 46148a0bfcea5d3267eac02613cfcc8b5fe8894f2cChris Lattner// 47148a0bfcea5d3267eac02613cfcc8b5fe8894f2cChris Lattner 483e57cb98bde04a65623493738d51f2a41e601748Chris Lattner/// isInstructionTriviallyDead - Return true if the result produced by the 493e57cb98bde04a65623493738d51f2a41e601748Chris Lattner/// instruction is not used, and the instruction has no side effects. 503e57cb98bde04a65623493738d51f2a41e601748Chris Lattner/// 51148a0bfcea5d3267eac02613cfcc8b5fe8894f2cChris Lattnerbool isInstructionTriviallyDead(Instruction *I); 52148a0bfcea5d3267eac02613cfcc8b5fe8894f2cChris Lattner 533481f24c06b3c9de48bdd99c37547471ca8e761eChris Lattner/// RecursivelyDeleteTriviallyDeadInstructions - If the specified value is a 543481f24c06b3c9de48bdd99c37547471ca8e761eChris Lattner/// trivially dead instruction, delete it. If that makes any of its operands 5590fe0bd68cdbeb980c08628c4992dffad0dc728fDan Gohman/// trivially dead, delete them too, recursively. Return true if any 5690fe0bd68cdbeb980c08628c4992dffad0dc728fDan Gohman/// instructions were deleted. 5790fe0bd68cdbeb980c08628c4992dffad0dc728fDan Gohmanbool RecursivelyDeleteTriviallyDeadInstructions(Value *V); 58afc36a9520971832dfbebc0333593bf5d3098296Dan Gohman 59afc36a9520971832dfbebc0333593bf5d3098296Dan Gohman/// RecursivelyDeleteDeadPHINode - If the specified value is an effectively 60afc36a9520971832dfbebc0333593bf5d3098296Dan Gohman/// dead PHI node, due to being a def-use chain of single-use nodes that 61afc36a9520971832dfbebc0333593bf5d3098296Dan Gohman/// either forms a cycle or is terminated by a trivially dead instruction, 62afc36a9520971832dfbebc0333593bf5d3098296Dan Gohman/// delete it. If that makes any of its operands trivially dead, delete them 632cfbf018a938d14126b9cb10c600e025f9831d2dDuncan Sands/// too, recursively. Return true if a change was made. 6490fe0bd68cdbeb980c08628c4992dffad0dc728fDan Gohmanbool RecursivelyDeleteDeadPHINode(PHINode *PN); 65afc36a9520971832dfbebc0333593bf5d3098296Dan Gohman 66e234a30a282f1aaec4aa63460fe8bba6416832a8Chris Lattner 67e234a30a282f1aaec4aa63460fe8bba6416832a8Chris Lattner/// SimplifyInstructionsInBlock - Scan the specified basic block and try to 68e234a30a282f1aaec4aa63460fe8bba6416832a8Chris Lattner/// simplify any instructions in it and recursively delete dead instructions. 69e234a30a282f1aaec4aa63460fe8bba6416832a8Chris Lattner/// 70e234a30a282f1aaec4aa63460fe8bba6416832a8Chris Lattner/// This returns true if it changed the code, note that it can delete 71e234a30a282f1aaec4aa63460fe8bba6416832a8Chris Lattner/// instructions in other blocks as well in this block. 724e282decf3960bfa6b1fe3fd77bb51ff96121515Owen Anderson/// 734e282decf3960bfa6b1fe3fd77bb51ff96121515Owen Anderson/// WARNING: Do not use this function on unreachable blocks, as recursive 744e282decf3960bfa6b1fe3fd77bb51ff96121515Owen Anderson/// simplification is not able to handle corner-case scenarios that can 754e282decf3960bfa6b1fe3fd77bb51ff96121515Owen Anderson/// arise in them. 76e234a30a282f1aaec4aa63460fe8bba6416832a8Chris Lattnerbool SimplifyInstructionsInBlock(BasicBlock *BB, const TargetData *TD = 0); 77e234a30a282f1aaec4aa63460fe8bba6416832a8Chris Lattner 78abbc2dd77908f146f73f4cd1abfdfe47faacf43dChris Lattner//===----------------------------------------------------------------------===// 7929874e0dc6c4e55bc384611273343bb358982cc3Chris Lattner// Control Flow Graph Restructuring. 80148a0bfcea5d3267eac02613cfcc8b5fe8894f2cChris Lattner// 81148a0bfcea5d3267eac02613cfcc8b5fe8894f2cChris Lattner 8240d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner/// RemovePredecessorAndSimplify - Like BasicBlock::removePredecessor, this 8340d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner/// method is called when we're about to delete Pred as a predecessor of BB. If 8440d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner/// BB contains any PHI nodes, this drops the entries in the PHI nodes for Pred. 8540d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner/// 8640d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner/// Unlike the removePredecessor method, this attempts to simplify uses of PHI 8740d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner/// nodes that collapse into identity values. For example, if we have: 8840d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner/// x = phi(1, 0, 0, 0) 8940d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner/// y = and x, z 9040d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner/// 9140d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner/// .. and delete the predecessor corresponding to the '1', this will attempt to 9240d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner/// recursively fold the 'and' to 0. 9340d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattnervoid RemovePredecessorAndSimplify(BasicBlock *BB, BasicBlock *Pred, 9440d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner TargetData *TD = 0); 9540d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner 9640d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner 97b29714a10af94b6daae437e48a82ae32675f79cbChris Lattner/// MergeBasicBlockIntoOnlyPred - BB is a block with one predecessor and its 98b29714a10af94b6daae437e48a82ae32675f79cbChris Lattner/// predecessor is known to have one successor (BB!). Eliminate the edge 99b29714a10af94b6daae437e48a82ae32675f79cbChris Lattner/// between them, moving the instructions in the predecessor into BB. This 100b29714a10af94b6daae437e48a82ae32675f79cbChris Lattner/// deletes the predecessor block. 101b29714a10af94b6daae437e48a82ae32675f79cbChris Lattner/// 102ad80981a106c9d0ec83351e63ee3ac75ed646bf4Andreas Neustiftervoid MergeBasicBlockIntoOnlyPred(BasicBlock *BB, Pass *P = 0); 103b29714a10af94b6daae437e48a82ae32675f79cbChris Lattner 104dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner 105dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner/// TryToSimplifyUncondBranchFromEmptyBlock - BB is known to contain an 106dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner/// unconditional branch, and contains no instructions other than PHI nodes, 107dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner/// potential debug intrinsics and the branch. If possible, eliminate BB by 108dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner/// rewriting all the predecessors to branch to the successor block and return 109dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner/// true. If we can't transform, return false. 110dce94d92df77da125a1c1256a9294db891a9db9cChris Lattnerbool TryToSimplifyUncondBranchFromEmptyBlock(BasicBlock *BB); 11120f4d34fe3609cda8b70956a36080e9cbcd327d4Jim Grosbach 11220f4d34fe3609cda8b70956a36080e9cbcd327d4Jim Grosbach/// EliminateDuplicatePHINodes - Check for and eliminate duplicate PHI 11320f4d34fe3609cda8b70956a36080e9cbcd327d4Jim Grosbach/// nodes in this block. This doesn't try to be clever about PHI nodes 11420f4d34fe3609cda8b70956a36080e9cbcd327d4Jim Grosbach/// which differ only in the order of the incoming values, but instcombine 11520f4d34fe3609cda8b70956a36080e9cbcd327d4Jim Grosbach/// orders them so it usually won't matter. 11620f4d34fe3609cda8b70956a36080e9cbcd327d4Jim Grosbach/// 11720f4d34fe3609cda8b70956a36080e9cbcd327d4Jim Grosbachbool EliminateDuplicatePHINodes(BasicBlock *BB); 11820f4d34fe3609cda8b70956a36080e9cbcd327d4Jim Grosbach 1193e57cb98bde04a65623493738d51f2a41e601748Chris Lattner/// SimplifyCFG - This function is used to do simplification of a CFG. For 1203e57cb98bde04a65623493738d51f2a41e601748Chris Lattner/// example, it adjusts branches to branches to eliminate the extra hop, it 1213e57cb98bde04a65623493738d51f2a41e601748Chris Lattner/// eliminates unreachable basic blocks, and does other "peephole" optimization 1223e57cb98bde04a65623493738d51f2a41e601748Chris Lattner/// of the CFG. It returns true if a modification was made, possibly deleting 1233e57cb98bde04a65623493738d51f2a41e601748Chris Lattner/// the basic block that was pointed to. 1243e57cb98bde04a65623493738d51f2a41e601748Chris Lattner/// 12558e9ee85fda5083e2eea987917e8eab6ba31fe5eJakob Stoklund Olesenbool SimplifyCFG(BasicBlock *BB, const TargetData *TD = 0); 126148a0bfcea5d3267eac02613cfcc8b5fe8894f2cChris Lattner 1274b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman/// FoldBranchToCommonDest - If this basic block is ONLY a setcc and a branch, 1284b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman/// and if a predecessor branches to us and one of our successors, fold the 1294b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman/// setcc into the predecessor and use logical operations to pick the right 1304b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman/// destination. 1314b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohmanbool FoldBranchToCommonDest(BranchInst *BI); 1324b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman 133cbf99ee973b6c6e6cd9537dae12031382783bc61Chris Lattner/// DemoteRegToStack - This function takes a virtual register computed by an 1348f71b63bead24de7acc6fe7f0487bf56da22d745Chris Lattner/// Instruction and replaces it with a slot in the stack frame, allocated via 135cbf99ee973b6c6e6cd9537dae12031382783bc61Chris Lattner/// alloca. This allows the CFG to be changed around without fear of 136cbf99ee973b6c6e6cd9537dae12031382783bc61Chris Lattner/// invalidating the SSA information for the value. It returns the pointer to 137cbf99ee973b6c6e6cd9537dae12031382783bc61Chris Lattner/// the alloca inserted to create a stack slot for X. 138cbf99ee973b6c6e6cd9537dae12031382783bc61Chris Lattner/// 13950dead06ffc107edb7e84857baaeeb09039c631cOwen AndersonAllocaInst *DemoteRegToStack(Instruction &X, 1409adc0abad3c3ed40a268ccbcee0c74cb9e1359feOwen Anderson bool VolatileLoads = false, 141d68a07650cdb2e18f18f362ba533459aa10e01b6Dan Gohman Instruction *AllocaPoint = 0); 142cbf99ee973b6c6e6cd9537dae12031382783bc61Chris Lattner 14308d14d2469c4f0465f610a204353220ee2ccde9cTanya Lattner/// DemotePHIToStack - This function takes a virtual register computed by a phi 14408d14d2469c4f0465f610a204353220ee2ccde9cTanya Lattner/// node and replaces it with a slot in the stack frame, allocated via alloca. 14508d14d2469c4f0465f610a204353220ee2ccde9cTanya Lattner/// The phi node is deleted and it returns the pointer to the alloca inserted. 14650dead06ffc107edb7e84857baaeeb09039c631cOwen AndersonAllocaInst *DemotePHIToStack(PHINode *P, Instruction *AllocaPoint = 0); 14708d14d2469c4f0465f610a204353220ee2ccde9cTanya Lattner 148687140c818ba4b896329a83324714140b6580ef8Chris Lattner/// getOrEnforceKnownAlignment - If the specified pointer has an alignment that 149687140c818ba4b896329a83324714140b6580ef8Chris Lattner/// we can determine, return it, otherwise return 0. If PrefAlign is specified, 150687140c818ba4b896329a83324714140b6580ef8Chris Lattner/// and it is more than the alignment of the ultimate object, see if we can 151687140c818ba4b896329a83324714140b6580ef8Chris Lattner/// increase the alignment of the ultimate object, making this check succeed. 152687140c818ba4b896329a83324714140b6580ef8Chris Lattnerunsigned getOrEnforceKnownAlignment(Value *V, unsigned PrefAlign, 153687140c818ba4b896329a83324714140b6580ef8Chris Lattner const TargetData *TD = 0); 154687140c818ba4b896329a83324714140b6580ef8Chris Lattner 155687140c818ba4b896329a83324714140b6580ef8Chris Lattner/// getKnownAlignment - Try to infer an alignment for the specified pointer. 156687140c818ba4b896329a83324714140b6580ef8Chris Lattnerstatic inline unsigned getKnownAlignment(Value *V, const TargetData *TD = 0) { 157687140c818ba4b896329a83324714140b6580ef8Chris Lattner return getOrEnforceKnownAlignment(V, 0, TD); 158687140c818ba4b896329a83324714140b6580ef8Chris Lattner} 159687140c818ba4b896329a83324714140b6580ef8Chris Lattner 160d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke} // End llvm namespace 161d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 162148a0bfcea5d3267eac02613cfcc8b5fe8894f2cChris Lattner#endif 163