Chris Lattner | 156bcf3 | 2003-04-18 04:34:29 +0000 | [diff] [blame] | 1 | //===- ConstantMerge.cpp - Merge duplicate global constants ---------------===// |
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 | // |
Chris Lattner | 4ee451d | 2007-12-29 20:36:04 +0000 | [diff] [blame^] | 5 | // This file is distributed under the University of Illinois Open Source |
| 6 | // 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 | 475becb | 2001-10-18 20:05:37 +0000 | [diff] [blame] | 9 | // |
| 10 | // This file defines the interface to a pass that merges duplicate global |
| 11 | // constants together into a single constant that is shared. This is useful |
| 12 | // because some passes (ie TraceValues) insert a lot of string constants into |
Chris Lattner | e4314ed | 2002-09-23 23:00:46 +0000 | [diff] [blame] | 13 | // the program, regardless of whether or not an existing string is available. |
Chris Lattner | 475becb | 2001-10-18 20:05:37 +0000 | [diff] [blame] | 14 | // |
| 15 | // Algorithm: ConstantMerge is designed to build up a map of available constants |
Chris Lattner | e4314ed | 2002-09-23 23:00:46 +0000 | [diff] [blame] | 16 | // and eliminate duplicates when it is initialized. |
Chris Lattner | 475becb | 2001-10-18 20:05:37 +0000 | [diff] [blame] | 17 | // |
| 18 | //===----------------------------------------------------------------------===// |
| 19 | |
Chris Lattner | 86453c5 | 2006-12-19 22:09:18 +0000 | [diff] [blame] | 20 | #define DEBUG_TYPE "constmerge" |
Chris Lattner | 9cfea85 | 2002-07-23 19:57:40 +0000 | [diff] [blame] | 21 | #include "llvm/Transforms/IPO.h" |
Chris Lattner | 793c6b8 | 2002-01-31 00:45:11 +0000 | [diff] [blame] | 22 | #include "llvm/Module.h" |
Chris Lattner | bd0ef77 | 2002-02-26 21:46:54 +0000 | [diff] [blame] | 23 | #include "llvm/Pass.h" |
Reid Spencer | 551ccae | 2004-09-01 22:55:40 +0000 | [diff] [blame] | 24 | #include "llvm/ADT/Statistic.h" |
Reid Spencer | 9133fe2 | 2007-02-05 23:32:05 +0000 | [diff] [blame] | 25 | #include "llvm/Support/Compiler.h" |
Chris Lattner | 1e2385b | 2003-11-21 21:54:22 +0000 | [diff] [blame] | 26 | using namespace llvm; |
Brian Gaeke | d0fde30 | 2003-11-11 22:41:34 +0000 | [diff] [blame] | 27 | |
Chris Lattner | 86453c5 | 2006-12-19 22:09:18 +0000 | [diff] [blame] | 28 | STATISTIC(NumMerged, "Number of global constants merged"); |
Chris Lattner | c67ebfa | 2002-10-09 23:16:04 +0000 | [diff] [blame] | 29 | |
Chris Lattner | 86453c5 | 2006-12-19 22:09:18 +0000 | [diff] [blame] | 30 | namespace { |
Reid Spencer | 9133fe2 | 2007-02-05 23:32:05 +0000 | [diff] [blame] | 31 | struct VISIBILITY_HIDDEN ConstantMerge : public ModulePass { |
Nick Lewycky | ecd94c8 | 2007-05-06 13:37:16 +0000 | [diff] [blame] | 32 | static char ID; // Pass identification, replacement for typeid |
Devang Patel | 794fd75 | 2007-05-01 21:15:47 +0000 | [diff] [blame] | 33 | ConstantMerge() : ModulePass((intptr_t)&ID) {} |
| 34 | |
Chris Lattner | 9234d03 | 2002-06-25 15:55:29 +0000 | [diff] [blame] | 35 | // run - For this pass, process all of the globals in the module, |
| 36 | // eliminating duplicate constants. |
| 37 | // |
Chris Lattner | b12914b | 2004-09-20 04:48:05 +0000 | [diff] [blame] | 38 | bool runOnModule(Module &M); |
Chris Lattner | 9234d03 | 2002-06-25 15:55:29 +0000 | [diff] [blame] | 39 | }; |
Chris Lattner | af41a12 | 2002-07-23 18:06:30 +0000 | [diff] [blame] | 40 | |
Devang Patel | 1997473 | 2007-05-03 01:11:54 +0000 | [diff] [blame] | 41 | char ConstantMerge::ID = 0; |
Chris Lattner | 7f8897f | 2006-08-27 22:42:52 +0000 | [diff] [blame] | 42 | RegisterPass<ConstantMerge>X("constmerge","Merge Duplicate Global Constants"); |
Chris Lattner | 9234d03 | 2002-06-25 15:55:29 +0000 | [diff] [blame] | 43 | } |
| 44 | |
Chris Lattner | b12914b | 2004-09-20 04:48:05 +0000 | [diff] [blame] | 45 | ModulePass *llvm::createConstantMergePass() { return new ConstantMerge(); } |
Chris Lattner | 9234d03 | 2002-06-25 15:55:29 +0000 | [diff] [blame] | 46 | |
Chris Lattner | b12914b | 2004-09-20 04:48:05 +0000 | [diff] [blame] | 47 | bool ConstantMerge::runOnModule(Module &M) { |
Chris Lattner | e1c173b | 2006-03-07 17:56:59 +0000 | [diff] [blame] | 48 | // Map unique constant/section pairs to globals. We don't want to merge |
| 49 | // globals in different sections. |
| 50 | std::map<std::pair<Constant*, std::string>, GlobalVariable*> CMap; |
Chris Lattner | b972380 | 2003-12-22 23:49:36 +0000 | [diff] [blame] | 51 | |
| 52 | // Replacements - This vector contains a list of replacements to perform. |
| 53 | std::vector<std::pair<GlobalVariable*, GlobalVariable*> > Replacements; |
| 54 | |
Chris Lattner | 0898c78 | 2003-12-28 07:19:08 +0000 | [diff] [blame] | 55 | bool MadeChange = false; |
Chris Lattner | 475becb | 2001-10-18 20:05:37 +0000 | [diff] [blame] | 56 | |
Chris Lattner | 0898c78 | 2003-12-28 07:19:08 +0000 | [diff] [blame] | 57 | // Iterate constant merging while we are still making progress. Merging two |
| 58 | // constants together may allow us to merge other constants together if the |
| 59 | // second level constants have initializers which point to the globals that |
| 60 | // were just merged. |
| 61 | while (1) { |
| 62 | // First pass: identify all globals that can be merged together, filling in |
| 63 | // the Replacements vector. We cannot do the replacement in this pass |
| 64 | // because doing so may cause initializers of other globals to be rewritten, |
| 65 | // invalidating the Constant* pointers in CMap. |
| 66 | // |
Chris Lattner | ae143ce | 2007-04-14 18:06:52 +0000 | [diff] [blame] | 67 | for (Module::global_iterator GVI = M.global_begin(), E = M.global_end(); |
| 68 | GVI != E; ) { |
| 69 | GlobalVariable *GV = GVI++; |
| 70 | |
Chris Lattner | 8264a9f | 2007-04-14 01:11:54 +0000 | [diff] [blame] | 71 | // If this GV is dead, remove it. |
| 72 | GV->removeDeadConstantUsers(); |
| 73 | if (GV->use_empty() && GV->hasInternalLinkage()) { |
Jeff Cohen | 98a7220 | 2007-04-14 17:18:29 +0000 | [diff] [blame] | 74 | GV->eraseFromParent(); |
| 75 | continue; |
Chris Lattner | 8264a9f | 2007-04-14 01:11:54 +0000 | [diff] [blame] | 76 | } |
| 77 | |
Chris Lattner | e1c173b | 2006-03-07 17:56:59 +0000 | [diff] [blame] | 78 | // Only process constants with initializers. |
Chris Lattner | 0898c78 | 2003-12-28 07:19:08 +0000 | [diff] [blame] | 79 | if (GV->isConstant() && GV->hasInitializer()) { |
| 80 | Constant *Init = GV->getInitializer(); |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 81 | |
Chris Lattner | e1c173b | 2006-03-07 17:56:59 +0000 | [diff] [blame] | 82 | // Check to see if the initializer is already known. |
| 83 | GlobalVariable *&Slot = CMap[std::make_pair(Init, GV->getSection())]; |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 84 | |
Chris Lattner | e1c173b | 2006-03-07 17:56:59 +0000 | [diff] [blame] | 85 | if (Slot == 0) { // Nope, add it to the map. |
| 86 | Slot = GV; |
Chris Lattner | 0898c78 | 2003-12-28 07:19:08 +0000 | [diff] [blame] | 87 | } else if (GV->hasInternalLinkage()) { // Yup, this is a duplicate! |
| 88 | // Make all uses of the duplicate constant use the canonical version. |
Chris Lattner | e1c173b | 2006-03-07 17:56:59 +0000 | [diff] [blame] | 89 | Replacements.push_back(std::make_pair(GV, Slot)); |
| 90 | } else if (GV->hasInternalLinkage()) { |
Chris Lattner | 0898c78 | 2003-12-28 07:19:08 +0000 | [diff] [blame] | 91 | // Make all uses of the duplicate constant use the canonical version. |
Chris Lattner | e1c173b | 2006-03-07 17:56:59 +0000 | [diff] [blame] | 92 | Replacements.push_back(std::make_pair(Slot, GV)); |
| 93 | Slot = GV; |
Chris Lattner | 0898c78 | 2003-12-28 07:19:08 +0000 | [diff] [blame] | 94 | } |
Chris Lattner | 475becb | 2001-10-18 20:05:37 +0000 | [diff] [blame] | 95 | } |
Chris Lattner | 8264a9f | 2007-04-14 01:11:54 +0000 | [diff] [blame] | 96 | } |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 97 | |
Chris Lattner | 0898c78 | 2003-12-28 07:19:08 +0000 | [diff] [blame] | 98 | if (Replacements.empty()) |
| 99 | return MadeChange; |
| 100 | CMap.clear(); |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 101 | |
Chris Lattner | 0898c78 | 2003-12-28 07:19:08 +0000 | [diff] [blame] | 102 | // Now that we have figured out which replacements must be made, do them all |
| 103 | // now. This avoid invalidating the pointers in CMap, which are unneeded |
| 104 | // now. |
| 105 | for (unsigned i = 0, e = Replacements.size(); i != e; ++i) { |
| 106 | // Eliminate any uses of the dead global... |
| 107 | Replacements[i].first->replaceAllUsesWith(Replacements[i].second); |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 108 | |
Chris Lattner | 0898c78 | 2003-12-28 07:19:08 +0000 | [diff] [blame] | 109 | // Delete the global value from the module... |
| 110 | M.getGlobalList().erase(Replacements[i].first); |
| 111 | } |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 112 | |
Chris Lattner | 0898c78 | 2003-12-28 07:19:08 +0000 | [diff] [blame] | 113 | NumMerged += Replacements.size(); |
| 114 | Replacements.clear(); |
Chris Lattner | b972380 | 2003-12-22 23:49:36 +0000 | [diff] [blame] | 115 | } |
Chris Lattner | b972380 | 2003-12-22 23:49:36 +0000 | [diff] [blame] | 116 | } |