Local.h revision dce94d92df77da125a1c1256a9294db891a9db9c
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; 3012ddd409535b52a7fa5157ded9a4cedd161fedb6Benjamin Kramerclass LLVMContext; 31aff9c270de8de7d1a0bc138d391bc67136bad58eCedric Venetstruct DbgInfoIntrinsic; 32d68a07650cdb2e18f18f362ba533459aa10e01b6Dan Gohman 33d68a07650cdb2e18f18f362ba533459aa10e01b6Dan Gohmantemplate<typename T> class SmallVectorImpl; 344f02c74a8ec8f4ca83b823146cb9c987ed79b3f6Chris Lattner 35148a0bfcea5d3267eac02613cfcc8b5fe8894f2cChris Lattner//===----------------------------------------------------------------------===// 366cc8a93c486f889c5767278508bc655942ba408eChris Lattner// Local analysis. 376cc8a93c486f889c5767278508bc655942ba408eChris Lattner// 386cc8a93c486f889c5767278508bc655942ba408eChris Lattner 396cc8a93c486f889c5767278508bc655942ba408eChris Lattner/// isSafeToLoadUnconditionally - Return true if we know that executing a load 406cc8a93c486f889c5767278508bc655942ba408eChris Lattner/// from this value cannot trap. If it is not obviously safe to load from the 416cc8a93c486f889c5767278508bc655942ba408eChris Lattner/// specified pointer, we do a quick local scan of the basic block containing 426cc8a93c486f889c5767278508bc655942ba408eChris Lattner/// ScanFrom, to determine if the address is already accessed. 436cc8a93c486f889c5767278508bc655942ba408eChris Lattnerbool isSafeToLoadUnconditionally(Value *V, Instruction *ScanFrom); 446cc8a93c486f889c5767278508bc655942ba408eChris Lattner 456cc8a93c486f889c5767278508bc655942ba408eChris Lattner//===----------------------------------------------------------------------===// 463481f24c06b3c9de48bdd99c37547471ca8e761eChris Lattner// Local constant propagation. 47148a0bfcea5d3267eac02613cfcc8b5fe8894f2cChris Lattner// 48148a0bfcea5d3267eac02613cfcc8b5fe8894f2cChris Lattner 493e57cb98bde04a65623493738d51f2a41e601748Chris Lattner/// ConstantFoldTerminator - If a terminator instruction is predicated on a 503e57cb98bde04a65623493738d51f2a41e601748Chris Lattner/// constant value, convert it into an unconditional branch to the constant 513e57cb98bde04a65623493738d51f2a41e601748Chris Lattner/// destination. This is a nontrivial operation because the successors of this 523e57cb98bde04a65623493738d51f2a41e601748Chris Lattner/// basic block must have their PHI nodes updated. 533e57cb98bde04a65623493738d51f2a41e601748Chris Lattner/// 5476ae3445f81164aaff9f95123426109c119f27c0Chris Lattnerbool ConstantFoldTerminator(BasicBlock *BB); 55148a0bfcea5d3267eac02613cfcc8b5fe8894f2cChris Lattner 56148a0bfcea5d3267eac02613cfcc8b5fe8894f2cChris Lattner//===----------------------------------------------------------------------===// 573481f24c06b3c9de48bdd99c37547471ca8e761eChris Lattner// Local dead code elimination. 58148a0bfcea5d3267eac02613cfcc8b5fe8894f2cChris Lattner// 59148a0bfcea5d3267eac02613cfcc8b5fe8894f2cChris Lattner 603e57cb98bde04a65623493738d51f2a41e601748Chris Lattner/// isInstructionTriviallyDead - Return true if the result produced by the 613e57cb98bde04a65623493738d51f2a41e601748Chris Lattner/// instruction is not used, and the instruction has no side effects. 623e57cb98bde04a65623493738d51f2a41e601748Chris Lattner/// 63148a0bfcea5d3267eac02613cfcc8b5fe8894f2cChris Lattnerbool isInstructionTriviallyDead(Instruction *I); 64148a0bfcea5d3267eac02613cfcc8b5fe8894f2cChris Lattner 653481f24c06b3c9de48bdd99c37547471ca8e761eChris Lattner/// RecursivelyDeleteTriviallyDeadInstructions - If the specified value is a 663481f24c06b3c9de48bdd99c37547471ca8e761eChris Lattner/// trivially dead instruction, delete it. If that makes any of its operands 673481f24c06b3c9de48bdd99c37547471ca8e761eChris Lattner/// trivially dead, delete them too, recursively. 6835738ac150afafe2359268d4b2169498c6c98c5fDan Gohmanvoid RecursivelyDeleteTriviallyDeadInstructions(Value *V); 69afc36a9520971832dfbebc0333593bf5d3098296Dan Gohman 70afc36a9520971832dfbebc0333593bf5d3098296Dan Gohman/// RecursivelyDeleteDeadPHINode - If the specified value is an effectively 71afc36a9520971832dfbebc0333593bf5d3098296Dan Gohman/// dead PHI node, due to being a def-use chain of single-use nodes that 72afc36a9520971832dfbebc0333593bf5d3098296Dan Gohman/// either forms a cycle or is terminated by a trivially dead instruction, 73afc36a9520971832dfbebc0333593bf5d3098296Dan Gohman/// delete it. If that makes any of its operands trivially dead, delete them 74afc36a9520971832dfbebc0333593bf5d3098296Dan Gohman/// too, recursively. 7535738ac150afafe2359268d4b2169498c6c98c5fDan Gohmanvoid RecursivelyDeleteDeadPHINode(PHINode *PN); 76afc36a9520971832dfbebc0333593bf5d3098296Dan Gohman 77abbc2dd77908f146f73f4cd1abfdfe47faacf43dChris Lattner//===----------------------------------------------------------------------===// 7829874e0dc6c4e55bc384611273343bb358982cc3Chris Lattner// Control Flow Graph Restructuring. 79148a0bfcea5d3267eac02613cfcc8b5fe8894f2cChris Lattner// 80148a0bfcea5d3267eac02613cfcc8b5fe8894f2cChris Lattner 81b29714a10af94b6daae437e48a82ae32675f79cbChris Lattner/// MergeBasicBlockIntoOnlyPred - BB is a block with one predecessor and its 82b29714a10af94b6daae437e48a82ae32675f79cbChris Lattner/// predecessor is known to have one successor (BB!). Eliminate the edge 83b29714a10af94b6daae437e48a82ae32675f79cbChris Lattner/// between them, moving the instructions in the predecessor into BB. This 84b29714a10af94b6daae437e48a82ae32675f79cbChris Lattner/// deletes the predecessor block. 85b29714a10af94b6daae437e48a82ae32675f79cbChris Lattner/// 86ad80981a106c9d0ec83351e63ee3ac75ed646bf4Andreas Neustiftervoid MergeBasicBlockIntoOnlyPred(BasicBlock *BB, Pass *P = 0); 87b29714a10af94b6daae437e48a82ae32675f79cbChris Lattner 88dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner 89dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner/// TryToSimplifyUncondBranchFromEmptyBlock - BB is known to contain an 90dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner/// unconditional branch, and contains no instructions other than PHI nodes, 91dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner/// potential debug intrinsics and the branch. If possible, eliminate BB by 92dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner/// rewriting all the predecessors to branch to the successor block and return 93dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner/// true. If we can't transform, return false. 94dce94d92df77da125a1c1256a9294db891a9db9cChris Lattnerbool TryToSimplifyUncondBranchFromEmptyBlock(BasicBlock *BB); 95dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner 963e57cb98bde04a65623493738d51f2a41e601748Chris Lattner/// SimplifyCFG - This function is used to do simplification of a CFG. For 973e57cb98bde04a65623493738d51f2a41e601748Chris Lattner/// example, it adjusts branches to branches to eliminate the extra hop, it 983e57cb98bde04a65623493738d51f2a41e601748Chris Lattner/// eliminates unreachable basic blocks, and does other "peephole" optimization 993e57cb98bde04a65623493738d51f2a41e601748Chris Lattner/// of the CFG. It returns true if a modification was made, possibly deleting 1003e57cb98bde04a65623493738d51f2a41e601748Chris Lattner/// the basic block that was pointed to. 1013e57cb98bde04a65623493738d51f2a41e601748Chris Lattner/// 1023e57cb98bde04a65623493738d51f2a41e601748Chris Lattner/// WARNING: The entry node of a method may not be simplified. 1033e57cb98bde04a65623493738d51f2a41e601748Chris Lattner/// 10418961504fc2b299578dba817900a0696cf3ccc4dChris Lattnerbool SimplifyCFG(BasicBlock *BB); 105148a0bfcea5d3267eac02613cfcc8b5fe8894f2cChris Lattner 1064b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman/// FoldBranchToCommonDest - If this basic block is ONLY a setcc and a branch, 1074b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman/// and if a predecessor branches to us and one of our successors, fold the 1084b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman/// setcc into the predecessor and use logical operations to pick the right 1094b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman/// destination. 1104b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohmanbool FoldBranchToCommonDest(BranchInst *BI); 1114b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohman 112cbf99ee973b6c6e6cd9537dae12031382783bc61Chris Lattner/// DemoteRegToStack - This function takes a virtual register computed by an 1138f71b63bead24de7acc6fe7f0487bf56da22d745Chris Lattner/// Instruction and replaces it with a slot in the stack frame, allocated via 114cbf99ee973b6c6e6cd9537dae12031382783bc61Chris Lattner/// alloca. This allows the CFG to be changed around without fear of 115cbf99ee973b6c6e6cd9537dae12031382783bc61Chris Lattner/// invalidating the SSA information for the value. It returns the pointer to 116cbf99ee973b6c6e6cd9537dae12031382783bc61Chris Lattner/// the alloca inserted to create a stack slot for X. 117cbf99ee973b6c6e6cd9537dae12031382783bc61Chris Lattner/// 11850dead06ffc107edb7e84857baaeeb09039c631cOwen AndersonAllocaInst *DemoteRegToStack(Instruction &X, 1199adc0abad3c3ed40a268ccbcee0c74cb9e1359feOwen Anderson bool VolatileLoads = false, 120d68a07650cdb2e18f18f362ba533459aa10e01b6Dan Gohman Instruction *AllocaPoint = 0); 121cbf99ee973b6c6e6cd9537dae12031382783bc61Chris Lattner 12208d14d2469c4f0465f610a204353220ee2ccde9cTanya Lattner/// DemotePHIToStack - This function takes a virtual register computed by a phi 12308d14d2469c4f0465f610a204353220ee2ccde9cTanya Lattner/// node and replaces it with a slot in the stack frame, allocated via alloca. 12408d14d2469c4f0465f610a204353220ee2ccde9cTanya Lattner/// The phi node is deleted and it returns the pointer to the alloca inserted. 12550dead06ffc107edb7e84857baaeeb09039c631cOwen AndersonAllocaInst *DemotePHIToStack(PHINode *P, Instruction *AllocaPoint = 0); 12608d14d2469c4f0465f610a204353220ee2ccde9cTanya Lattner 1274afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel/// OnlyUsedByDbgIntrinsics - Return true if the instruction I is only used 1284afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel/// by DbgIntrinsics. If DbgInUses is specified then the vector is filled 1294afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel/// with DbgInfoIntrinsic that use the instruction I. 1304afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patelbool OnlyUsedByDbgInfoIntrinsics(Instruction *I, 1314afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel SmallVectorImpl<DbgInfoIntrinsic *> *DbgInUses = 0); 132c79e1182470ed12f1f3d0d35c1725366519a9af7Devang Patel 133d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke} // End llvm namespace 134d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 135148a0bfcea5d3267eac02613cfcc8b5fe8894f2cChris Lattner#endif 136