Misha Brukman | 82c89b9 | 2003-05-20 21:01:22 +0000 | [diff] [blame] | 1 | //===- ConstantProp.cpp - Code to perform Simple Constant Propagation -----===// |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 2 | // |
John Criswell | b576c94 | 2003-10-20 19:43:21 +0000 | [diff] [blame] | 3 | // The LLVM Compiler Infrastructure |
| 4 | // |
| 5 | // This file was developed by the LLVM research group and is distributed under |
| 6 | // the University of Illinois Open Source License. See LICENSE.TXT for details. |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 7 | // |
John Criswell | b576c94 | 2003-10-20 19:43:21 +0000 | [diff] [blame] | 8 | //===----------------------------------------------------------------------===// |
Chris Lattner | 0095054 | 2001-06-06 20:29:01 +0000 | [diff] [blame] | 9 | // |
Misha Brukman | 82c89b9 | 2003-05-20 21:01:22 +0000 | [diff] [blame] | 10 | // This file implements constant propagation and merging: |
Chris Lattner | 0095054 | 2001-06-06 20:29:01 +0000 | [diff] [blame] | 11 | // |
| 12 | // Specifically, this: |
Chris Lattner | 89df1b5 | 2002-05-06 18:21:31 +0000 | [diff] [blame] | 13 | // * Converts instructions like "add int 1, 2" into 3 |
Chris Lattner | 0095054 | 2001-06-06 20:29:01 +0000 | [diff] [blame] | 14 | // |
| 15 | // Notice that: |
| 16 | // * This pass has a habit of making definitions be dead. It is a good idea |
Chris Lattner | 89df1b5 | 2002-05-06 18:21:31 +0000 | [diff] [blame] | 17 | // to to run a DIE pass sometime after running this pass. |
Chris Lattner | 0095054 | 2001-06-06 20:29:01 +0000 | [diff] [blame] | 18 | // |
| 19 | //===----------------------------------------------------------------------===// |
| 20 | |
Chris Lattner | 0e5f499 | 2006-12-19 21:40:18 +0000 | [diff] [blame] | 21 | #define DEBUG_TYPE "constprop" |
Chris Lattner | 022103b | 2002-05-07 20:03:00 +0000 | [diff] [blame] | 22 | #include "llvm/Transforms/Scalar.h" |
Chris Lattner | 79066fa | 2007-01-30 23:46:24 +0000 | [diff] [blame] | 23 | #include "llvm/Analysis/ConstantFolding.h" |
Chris Lattner | b6ac8bc | 2004-01-12 19:15:20 +0000 | [diff] [blame] | 24 | #include "llvm/Constant.h" |
Chris Lattner | 2ed01d8 | 2002-05-07 18:10:55 +0000 | [diff] [blame] | 25 | #include "llvm/Instruction.h" |
Chris Lattner | bd0ef77 | 2002-02-26 21:46:54 +0000 | [diff] [blame] | 26 | #include "llvm/Pass.h" |
Reid Spencer | 9133fe2 | 2007-02-05 23:32:05 +0000 | [diff] [blame] | 27 | #include "llvm/Support/Compiler.h" |
Chris Lattner | 89df1b5 | 2002-05-06 18:21:31 +0000 | [diff] [blame] | 28 | #include "llvm/Support/InstIterator.h" |
Reid Spencer | 551ccae | 2004-09-01 22:55:40 +0000 | [diff] [blame] | 29 | #include "llvm/ADT/Statistic.h" |
Chris Lattner | 89df1b5 | 2002-05-06 18:21:31 +0000 | [diff] [blame] | 30 | #include <set> |
Chris Lattner | d745602 | 2004-01-09 06:02:20 +0000 | [diff] [blame] | 31 | using namespace llvm; |
Brian Gaeke | d0fde30 | 2003-11-11 22:41:34 +0000 | [diff] [blame] | 32 | |
Chris Lattner | 0e5f499 | 2006-12-19 21:40:18 +0000 | [diff] [blame] | 33 | STATISTIC(NumInstKilled, "Number of instructions killed"); |
Chris Lattner | a92f696 | 2002-10-01 22:38:41 +0000 | [diff] [blame] | 34 | |
Chris Lattner | 0e5f499 | 2006-12-19 21:40:18 +0000 | [diff] [blame] | 35 | namespace { |
Reid Spencer | 9133fe2 | 2007-02-05 23:32:05 +0000 | [diff] [blame] | 36 | struct VISIBILITY_HIDDEN ConstantPropagation : public FunctionPass { |
Devang Patel | 1997473 | 2007-05-03 01:11:54 +0000 | [diff] [blame^] | 37 | static char ID; // Pass identifcation, replacement for typeid |
Devang Patel | 794fd75 | 2007-05-01 21:15:47 +0000 | [diff] [blame] | 38 | ConstantPropagation() : FunctionPass((intptr_t)&ID) {} |
| 39 | |
Chris Lattner | 7e70829 | 2002-06-25 16:13:24 +0000 | [diff] [blame] | 40 | bool runOnFunction(Function &F); |
Chris Lattner | 97e52e4 | 2002-04-28 21:27:06 +0000 | [diff] [blame] | 41 | |
| 42 | virtual void getAnalysisUsage(AnalysisUsage &AU) const { |
Chris Lattner | cb2610e | 2002-10-21 20:00:28 +0000 | [diff] [blame] | 43 | AU.setPreservesCFG(); |
Chris Lattner | 97e52e4 | 2002-04-28 21:27:06 +0000 | [diff] [blame] | 44 | } |
Chris Lattner | bd0ef77 | 2002-02-26 21:46:54 +0000 | [diff] [blame] | 45 | }; |
Chris Lattner | f629309 | 2002-07-23 18:06:35 +0000 | [diff] [blame] | 46 | |
Devang Patel | 1997473 | 2007-05-03 01:11:54 +0000 | [diff] [blame^] | 47 | char ConstantPropagation::ID = 0; |
Chris Lattner | 7f8897f | 2006-08-27 22:42:52 +0000 | [diff] [blame] | 48 | RegisterPass<ConstantPropagation> X("constprop", |
| 49 | "Simple constant propagation"); |
Chris Lattner | 0095054 | 2001-06-06 20:29:01 +0000 | [diff] [blame] | 50 | } |
Chris Lattner | bd0ef77 | 2002-02-26 21:46:54 +0000 | [diff] [blame] | 51 | |
Chris Lattner | 4b50156 | 2004-09-20 04:43:15 +0000 | [diff] [blame] | 52 | FunctionPass *llvm::createConstantPropagationPass() { |
Misha Brukman | 82c89b9 | 2003-05-20 21:01:22 +0000 | [diff] [blame] | 53 | return new ConstantPropagation(); |
Chris Lattner | bd0ef77 | 2002-02-26 21:46:54 +0000 | [diff] [blame] | 54 | } |
| 55 | |
Chris Lattner | 89df1b5 | 2002-05-06 18:21:31 +0000 | [diff] [blame] | 56 | |
Misha Brukman | 82c89b9 | 2003-05-20 21:01:22 +0000 | [diff] [blame] | 57 | bool ConstantPropagation::runOnFunction(Function &F) { |
Chris Lattner | 89df1b5 | 2002-05-06 18:21:31 +0000 | [diff] [blame] | 58 | // Initialize the worklist to all of the instructions ready to process... |
Chris Lattner | 6ffe551 | 2004-04-27 15:13:33 +0000 | [diff] [blame] | 59 | std::set<Instruction*> WorkList; |
| 60 | for(inst_iterator i = inst_begin(F), e = inst_end(F); i != e; ++i) { |
| 61 | WorkList.insert(&*i); |
| 62 | } |
Chris Lattner | 89df1b5 | 2002-05-06 18:21:31 +0000 | [diff] [blame] | 63 | bool Changed = false; |
| 64 | |
| 65 | while (!WorkList.empty()) { |
| 66 | Instruction *I = *WorkList.begin(); |
| 67 | WorkList.erase(WorkList.begin()); // Get an element from the worklist... |
| 68 | |
| 69 | if (!I->use_empty()) // Don't muck with dead instructions... |
| 70 | if (Constant *C = ConstantFoldInstruction(I)) { |
| 71 | // Add all of the users of this instruction to the worklist, they might |
Misha Brukman | 82c89b9 | 2003-05-20 21:01:22 +0000 | [diff] [blame] | 72 | // be constant propagatable now... |
Chris Lattner | 89df1b5 | 2002-05-06 18:21:31 +0000 | [diff] [blame] | 73 | for (Value::use_iterator UI = I->use_begin(), UE = I->use_end(); |
| 74 | UI != UE; ++UI) |
| 75 | WorkList.insert(cast<Instruction>(*UI)); |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 76 | |
Chris Lattner | 89df1b5 | 2002-05-06 18:21:31 +0000 | [diff] [blame] | 77 | // Replace all of the uses of a variable with uses of the constant. |
| 78 | I->replaceAllUsesWith(C); |
Chris Lattner | 3dec1f2 | 2002-05-10 15:38:35 +0000 | [diff] [blame] | 79 | |
Chris Lattner | 4647b7c | 2004-04-13 19:28:20 +0000 | [diff] [blame] | 80 | // Remove the dead instruction. |
| 81 | WorkList.erase(I); |
| 82 | I->getParent()->getInstList().erase(I); |
| 83 | |
Chris Lattner | 89df1b5 | 2002-05-06 18:21:31 +0000 | [diff] [blame] | 84 | // We made a change to the function... |
| 85 | Changed = true; |
Chris Lattner | 3dec1f2 | 2002-05-10 15:38:35 +0000 | [diff] [blame] | 86 | ++NumInstKilled; |
Chris Lattner | 89df1b5 | 2002-05-06 18:21:31 +0000 | [diff] [blame] | 87 | } |
| 88 | } |
| 89 | return Changed; |
| 90 | } |