Chris Lattner | 156bcf3 | 2003-04-18 04:34:29 +0000 | [diff] [blame] | 1 | //===- ConstantMerge.cpp - Merge duplicate global constants ---------------===// |
John Criswell | b576c94 | 2003-10-20 19:43:21 +0000 | [diff] [blame] | 2 | // |
| 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. |
| 7 | // |
| 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 | 9cfea85 | 2002-07-23 19:57:40 +0000 | [diff] [blame] | 20 | #include "llvm/Transforms/IPO.h" |
Chris Lattner | 793c6b8 | 2002-01-31 00:45:11 +0000 | [diff] [blame] | 21 | #include "llvm/Module.h" |
Chris Lattner | bd0ef77 | 2002-02-26 21:46:54 +0000 | [diff] [blame] | 22 | #include "llvm/Pass.h" |
Reid Spencer | 551ccae | 2004-09-01 22:55:40 +0000 | [diff] [blame] | 23 | #include "llvm/ADT/Statistic.h" |
Chris Lattner | 1e2385b | 2003-11-21 21:54:22 +0000 | [diff] [blame] | 24 | using namespace llvm; |
Brian Gaeke | d0fde30 | 2003-11-11 22:41:34 +0000 | [diff] [blame] | 25 | |
Chris Lattner | 9234d03 | 2002-06-25 15:55:29 +0000 | [diff] [blame] | 26 | namespace { |
Chris Lattner | c67ebfa | 2002-10-09 23:16:04 +0000 | [diff] [blame] | 27 | Statistic<> NumMerged("constmerge", "Number of global constants merged"); |
| 28 | |
Chris Lattner | b12914b | 2004-09-20 04:48:05 +0000 | [diff] [blame] | 29 | struct ConstantMerge : public ModulePass { |
Chris Lattner | 9234d03 | 2002-06-25 15:55:29 +0000 | [diff] [blame] | 30 | // run - For this pass, process all of the globals in the module, |
| 31 | // eliminating duplicate constants. |
| 32 | // |
Chris Lattner | b12914b | 2004-09-20 04:48:05 +0000 | [diff] [blame] | 33 | bool runOnModule(Module &M); |
Chris Lattner | 9234d03 | 2002-06-25 15:55:29 +0000 | [diff] [blame] | 34 | }; |
Chris Lattner | af41a12 | 2002-07-23 18:06:30 +0000 | [diff] [blame] | 35 | |
Chris Lattner | 1e43516 | 2002-07-26 21:12:44 +0000 | [diff] [blame] | 36 | RegisterOpt<ConstantMerge> X("constmerge","Merge Duplicate Global Constants"); |
Chris Lattner | 9234d03 | 2002-06-25 15:55:29 +0000 | [diff] [blame] | 37 | } |
| 38 | |
Chris Lattner | b12914b | 2004-09-20 04:48:05 +0000 | [diff] [blame] | 39 | ModulePass *llvm::createConstantMergePass() { return new ConstantMerge(); } |
Chris Lattner | 9234d03 | 2002-06-25 15:55:29 +0000 | [diff] [blame] | 40 | |
Chris Lattner | b12914b | 2004-09-20 04:48:05 +0000 | [diff] [blame] | 41 | bool ConstantMerge::runOnModule(Module &M) { |
Chris Lattner | 9234d03 | 2002-06-25 15:55:29 +0000 | [diff] [blame] | 42 | std::map<Constant*, GlobalVariable*> CMap; |
Chris Lattner | b972380 | 2003-12-22 23:49:36 +0000 | [diff] [blame] | 43 | |
| 44 | // Replacements - This vector contains a list of replacements to perform. |
| 45 | std::vector<std::pair<GlobalVariable*, GlobalVariable*> > Replacements; |
| 46 | |
Chris Lattner | 0898c78 | 2003-12-28 07:19:08 +0000 | [diff] [blame] | 47 | bool MadeChange = false; |
Chris Lattner | 475becb | 2001-10-18 20:05:37 +0000 | [diff] [blame] | 48 | |
Chris Lattner | 0898c78 | 2003-12-28 07:19:08 +0000 | [diff] [blame] | 49 | // Iterate constant merging while we are still making progress. Merging two |
| 50 | // constants together may allow us to merge other constants together if the |
| 51 | // second level constants have initializers which point to the globals that |
| 52 | // were just merged. |
| 53 | while (1) { |
| 54 | // First pass: identify all globals that can be merged together, filling in |
| 55 | // the Replacements vector. We cannot do the replacement in this pass |
| 56 | // because doing so may cause initializers of other globals to be rewritten, |
| 57 | // invalidating the Constant* pointers in CMap. |
| 58 | // |
Chris Lattner | e4d5c44 | 2005-03-15 04:54:21 +0000 | [diff] [blame^] | 59 | for (Module::global_iterator GV = M.global_begin(), E = M.global_end(); GV != E; ++GV) |
Chris Lattner | 0898c78 | 2003-12-28 07:19:08 +0000 | [diff] [blame] | 60 | // Only process constants with initializers |
| 61 | if (GV->isConstant() && GV->hasInitializer()) { |
| 62 | Constant *Init = GV->getInitializer(); |
| 63 | |
| 64 | // Check to see if the initializer is already known... |
| 65 | std::map<Constant*, GlobalVariable*>::iterator I = CMap.find(Init); |
| 66 | |
| 67 | if (I == CMap.end()) { // Nope, add it to the map |
| 68 | CMap.insert(I, std::make_pair(Init, GV)); |
| 69 | } else if (GV->hasInternalLinkage()) { // Yup, this is a duplicate! |
| 70 | // Make all uses of the duplicate constant use the canonical version. |
| 71 | Replacements.push_back(std::make_pair(GV, I->second)); |
| 72 | } else if (I->second->hasInternalLinkage()) { |
| 73 | // Make all uses of the duplicate constant use the canonical version. |
| 74 | Replacements.push_back(std::make_pair(I->second, GV)); |
| 75 | I->second = GV; |
| 76 | } |
Chris Lattner | 475becb | 2001-10-18 20:05:37 +0000 | [diff] [blame] | 77 | } |
Chris Lattner | b972380 | 2003-12-22 23:49:36 +0000 | [diff] [blame] | 78 | |
Chris Lattner | 0898c78 | 2003-12-28 07:19:08 +0000 | [diff] [blame] | 79 | if (Replacements.empty()) |
| 80 | return MadeChange; |
| 81 | CMap.clear(); |
| 82 | |
| 83 | // Now that we have figured out which replacements must be made, do them all |
| 84 | // now. This avoid invalidating the pointers in CMap, which are unneeded |
| 85 | // now. |
| 86 | for (unsigned i = 0, e = Replacements.size(); i != e; ++i) { |
| 87 | // Eliminate any uses of the dead global... |
| 88 | Replacements[i].first->replaceAllUsesWith(Replacements[i].second); |
| 89 | |
| 90 | // Delete the global value from the module... |
| 91 | M.getGlobalList().erase(Replacements[i].first); |
| 92 | } |
| 93 | |
| 94 | NumMerged += Replacements.size(); |
| 95 | Replacements.clear(); |
Chris Lattner | b972380 | 2003-12-22 23:49:36 +0000 | [diff] [blame] | 96 | } |
Chris Lattner | b972380 | 2003-12-22 23:49:36 +0000 | [diff] [blame] | 97 | } |