blob: 5be5ace315f0d315731b07250f9824577b628905 [file] [log] [blame]
Chris Lattner25db5802004-10-07 04:16:33 +00001//===- GlobalOpt.cpp - Optimize Global Variables --------------------------===//
Misha Brukmanb1c93172005-04-21 23:48:37 +00002//
Chris Lattner25db5802004-10-07 04:16:33 +00003// 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 Brukmanb1c93172005-04-21 23:48:37 +00007//
Chris Lattner25db5802004-10-07 04:16:33 +00008//===----------------------------------------------------------------------===//
9//
10// This pass transforms simple global variables that never have their address
11// taken. If obviously true, it marks read/write globals as constant, deletes
12// variables only stored to, etc.
13//
14//===----------------------------------------------------------------------===//
15
16#define DEBUG_TYPE "globalopt"
17#include "llvm/Transforms/IPO.h"
Chris Lattnera4c80222005-05-08 22:18:06 +000018#include "llvm/CallingConv.h"
Chris Lattner25db5802004-10-07 04:16:33 +000019#include "llvm/Constants.h"
20#include "llvm/DerivedTypes.h"
21#include "llvm/Instructions.h"
Chris Lattner7561ca12005-02-27 18:58:52 +000022#include "llvm/IntrinsicInst.h"
Chris Lattner25db5802004-10-07 04:16:33 +000023#include "llvm/Module.h"
24#include "llvm/Pass.h"
Chris Lattner024f4ab2007-01-30 23:46:24 +000025#include "llvm/Analysis/ConstantFolding.h"
Chris Lattner004e2502004-10-11 05:54:41 +000026#include "llvm/Target/TargetData.h"
Reid Spencer557ab152007-02-05 23:32:05 +000027#include "llvm/Support/Compiler.h"
Chris Lattner024f4ab2007-01-30 23:46:24 +000028#include "llvm/Support/Debug.h"
Chris Lattnerf96f4a82007-01-31 04:40:53 +000029#include "llvm/ADT/SmallVector.h"
Chris Lattner25db5802004-10-07 04:16:33 +000030#include "llvm/ADT/Statistic.h"
Chris Lattnerabab0712004-10-08 17:32:09 +000031#include "llvm/ADT/StringExtras.h"
Chris Lattner25db5802004-10-07 04:16:33 +000032#include <algorithm>
Chris Lattnerc597b8a2006-01-22 23:32:06 +000033#include <set>
Chris Lattner25db5802004-10-07 04:16:33 +000034using namespace llvm;
35
Chris Lattner1631bcb2006-12-19 22:09:18 +000036STATISTIC(NumMarked , "Number of globals marked constant");
37STATISTIC(NumSRA , "Number of aggregate globals broken into scalars");
38STATISTIC(NumHeapSRA , "Number of heap objects SRA'd");
39STATISTIC(NumSubstitute,"Number of globals with initializers stored into them");
40STATISTIC(NumDeleted , "Number of globals deleted");
41STATISTIC(NumFnDeleted , "Number of functions deleted");
42STATISTIC(NumGlobUses , "Number of global uses devirtualized");
43STATISTIC(NumLocalized , "Number of globals localized");
44STATISTIC(NumShrunkToBool , "Number of global vars shrunk to booleans");
45STATISTIC(NumFastCallFns , "Number of functions converted to fastcc");
46STATISTIC(NumCtorsEvaluated, "Number of static ctors evaluated");
Chris Lattner25db5802004-10-07 04:16:33 +000047
Chris Lattner1631bcb2006-12-19 22:09:18 +000048namespace {
Reid Spencer557ab152007-02-05 23:32:05 +000049 struct VISIBILITY_HIDDEN GlobalOpt : public ModulePass {
Chris Lattner004e2502004-10-11 05:54:41 +000050 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
51 AU.addRequired<TargetData>();
52 }
Misha Brukmanb1c93172005-04-21 23:48:37 +000053
Chris Lattner25db5802004-10-07 04:16:33 +000054 bool runOnModule(Module &M);
Chris Lattner004e2502004-10-11 05:54:41 +000055
56 private:
Chris Lattner41b6a5a2005-09-26 01:43:45 +000057 GlobalVariable *FindGlobalCtors(Module &M);
58 bool OptimizeFunctions(Module &M);
59 bool OptimizeGlobalVars(Module &M);
60 bool OptimizeGlobalCtorsList(GlobalVariable *&GCL);
Chris Lattnerc2d3d312006-08-27 22:42:52 +000061 bool ProcessInternalGlobal(GlobalVariable *GV,Module::global_iterator &GVI);
Chris Lattner25db5802004-10-07 04:16:33 +000062 };
63
Chris Lattnerc2d3d312006-08-27 22:42:52 +000064 RegisterPass<GlobalOpt> X("globalopt", "Global Variable Optimizer");
Chris Lattner25db5802004-10-07 04:16:33 +000065}
66
67ModulePass *llvm::createGlobalOptimizerPass() { return new GlobalOpt(); }
68
69/// GlobalStatus - As we analyze each global, keep track of some information
70/// about it. If we find out that the address of the global is taken, none of
Chris Lattner617f1a32004-10-07 21:30:30 +000071/// this info will be accurate.
Reid Spencer557ab152007-02-05 23:32:05 +000072struct VISIBILITY_HIDDEN GlobalStatus {
Chris Lattner617f1a32004-10-07 21:30:30 +000073 /// isLoaded - True if the global is ever loaded. If the global isn't ever
74 /// loaded it can be deleted.
Chris Lattner25db5802004-10-07 04:16:33 +000075 bool isLoaded;
Chris Lattner617f1a32004-10-07 21:30:30 +000076
77 /// StoredType - Keep track of what stores to the global look like.
78 ///
Chris Lattner25db5802004-10-07 04:16:33 +000079 enum StoredType {
Chris Lattner617f1a32004-10-07 21:30:30 +000080 /// NotStored - There is no store to this global. It can thus be marked
81 /// constant.
82 NotStored,
83
84 /// isInitializerStored - This global is stored to, but the only thing
85 /// stored is the constant it was initialized with. This is only tracked
86 /// for scalar globals.
87 isInitializerStored,
88
89 /// isStoredOnce - This global is stored to, but only its initializer and
90 /// one other value is ever stored to it. If this global isStoredOnce, we
91 /// track the value stored to it in StoredOnceValue below. This is only
92 /// tracked for scalar globals.
93 isStoredOnce,
94
95 /// isStored - This global is stored to by multiple values or something else
96 /// that we cannot track.
97 isStored
Chris Lattner25db5802004-10-07 04:16:33 +000098 } StoredType;
Chris Lattner617f1a32004-10-07 21:30:30 +000099
100 /// StoredOnceValue - If only one value (besides the initializer constant) is
101 /// ever stored to this global, keep track of what value it is.
102 Value *StoredOnceValue;
103
Chris Lattner5a0bd612006-11-01 18:03:33 +0000104 /// AccessingFunction/HasMultipleAccessingFunctions - These start out
105 /// null/false. When the first accessing function is noticed, it is recorded.
106 /// When a second different accessing function is noticed,
107 /// HasMultipleAccessingFunctions is set to true.
Alkis Evlogimenosc4a44c62005-02-10 18:36:30 +0000108 Function *AccessingFunction;
109 bool HasMultipleAccessingFunctions;
110
Chris Lattner5a0bd612006-11-01 18:03:33 +0000111 /// HasNonInstructionUser - Set to true if this global has a user that is not
112 /// an instruction (e.g. a constant expr or GV initializer).
Chris Lattner50bdfcb2005-06-15 21:11:48 +0000113 bool HasNonInstructionUser;
114
Chris Lattner5a0bd612006-11-01 18:03:33 +0000115 /// HasPHIUser - Set to true if this global has a user that is a PHI node.
116 bool HasPHIUser;
117
Chris Lattner617f1a32004-10-07 21:30:30 +0000118 /// isNotSuitableForSRA - Keep track of whether any SRA preventing users of
119 /// the global exist. Such users include GEP instruction with variable
120 /// indexes, and non-gep/load/store users like constant expr casts.
Chris Lattner25db5802004-10-07 04:16:33 +0000121 bool isNotSuitableForSRA;
122
Chris Lattner617f1a32004-10-07 21:30:30 +0000123 GlobalStatus() : isLoaded(false), StoredType(NotStored), StoredOnceValue(0),
Alkis Evlogimenosc4a44c62005-02-10 18:36:30 +0000124 AccessingFunction(0), HasMultipleAccessingFunctions(false),
Chris Lattner5a0bd612006-11-01 18:03:33 +0000125 HasNonInstructionUser(false), HasPHIUser(false),
126 isNotSuitableForSRA(false) {}
Chris Lattner25db5802004-10-07 04:16:33 +0000127};
128
Chris Lattner1c4bddc2004-10-08 20:59:28 +0000129
130
131/// ConstantIsDead - Return true if the specified constant is (transitively)
132/// dead. The constant may be used by other constants (e.g. constant arrays and
133/// constant exprs) as long as they are dead, but it cannot be used by anything
134/// else.
135static bool ConstantIsDead(Constant *C) {
136 if (isa<GlobalValue>(C)) return false;
137
138 for (Value::use_iterator UI = C->use_begin(), E = C->use_end(); UI != E; ++UI)
139 if (Constant *CU = dyn_cast<Constant>(*UI)) {
140 if (!ConstantIsDead(CU)) return false;
141 } else
142 return false;
143 return true;
144}
145
146
Chris Lattner25db5802004-10-07 04:16:33 +0000147/// AnalyzeGlobal - Look at all uses of the global and fill in the GlobalStatus
148/// structure. If the global has its address taken, return true to indicate we
149/// can't do anything with it.
150///
151static bool AnalyzeGlobal(Value *V, GlobalStatus &GS,
152 std::set<PHINode*> &PHIUsers) {
153 for (Value::use_iterator UI = V->use_begin(), E = V->use_end(); UI != E; ++UI)
154 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(*UI)) {
Chris Lattner50bdfcb2005-06-15 21:11:48 +0000155 GS.HasNonInstructionUser = true;
156
Chris Lattner25db5802004-10-07 04:16:33 +0000157 if (AnalyzeGlobal(CE, GS, PHIUsers)) return true;
158 if (CE->getOpcode() != Instruction::GetElementPtr)
159 GS.isNotSuitableForSRA = true;
Chris Lattnerabab0712004-10-08 17:32:09 +0000160 else if (!GS.isNotSuitableForSRA) {
161 // Check to see if this ConstantExpr GEP is SRA'able. In particular, we
162 // don't like < 3 operand CE's, and we don't like non-constant integer
163 // indices.
164 if (CE->getNumOperands() < 3 || !CE->getOperand(1)->isNullValue())
165 GS.isNotSuitableForSRA = true;
166 else {
167 for (unsigned i = 1, e = CE->getNumOperands(); i != e; ++i)
168 if (!isa<ConstantInt>(CE->getOperand(i))) {
169 GS.isNotSuitableForSRA = true;
170 break;
171 }
172 }
173 }
174
Chris Lattner25db5802004-10-07 04:16:33 +0000175 } else if (Instruction *I = dyn_cast<Instruction>(*UI)) {
Alkis Evlogimenosc4a44c62005-02-10 18:36:30 +0000176 if (!GS.HasMultipleAccessingFunctions) {
177 Function *F = I->getParent()->getParent();
178 if (GS.AccessingFunction == 0)
179 GS.AccessingFunction = F;
180 else if (GS.AccessingFunction != F)
181 GS.HasMultipleAccessingFunctions = true;
182 }
Chris Lattner25db5802004-10-07 04:16:33 +0000183 if (isa<LoadInst>(I)) {
184 GS.isLoaded = true;
185 } else if (StoreInst *SI = dyn_cast<StoreInst>(I)) {
Chris Lattner02b6c912004-10-07 06:01:25 +0000186 // Don't allow a store OF the address, only stores TO the address.
187 if (SI->getOperand(0) == V) return true;
188
Chris Lattner617f1a32004-10-07 21:30:30 +0000189 // If this is a direct store to the global (i.e., the global is a scalar
190 // value, not an aggregate), keep more specific information about
191 // stores.
192 if (GS.StoredType != GlobalStatus::isStored)
193 if (GlobalVariable *GV = dyn_cast<GlobalVariable>(SI->getOperand(1))){
Chris Lattner28eeb732004-11-14 20:50:30 +0000194 Value *StoredVal = SI->getOperand(0);
195 if (StoredVal == GV->getInitializer()) {
196 if (GS.StoredType < GlobalStatus::isInitializerStored)
197 GS.StoredType = GlobalStatus::isInitializerStored;
198 } else if (isa<LoadInst>(StoredVal) &&
199 cast<LoadInst>(StoredVal)->getOperand(0) == GV) {
200 // G = G
Chris Lattner617f1a32004-10-07 21:30:30 +0000201 if (GS.StoredType < GlobalStatus::isInitializerStored)
202 GS.StoredType = GlobalStatus::isInitializerStored;
203 } else if (GS.StoredType < GlobalStatus::isStoredOnce) {
204 GS.StoredType = GlobalStatus::isStoredOnce;
Chris Lattner28eeb732004-11-14 20:50:30 +0000205 GS.StoredOnceValue = StoredVal;
Chris Lattner617f1a32004-10-07 21:30:30 +0000206 } else if (GS.StoredType == GlobalStatus::isStoredOnce &&
Chris Lattner28eeb732004-11-14 20:50:30 +0000207 GS.StoredOnceValue == StoredVal) {
Chris Lattner617f1a32004-10-07 21:30:30 +0000208 // noop.
209 } else {
210 GS.StoredType = GlobalStatus::isStored;
211 }
212 } else {
Chris Lattner25db5802004-10-07 04:16:33 +0000213 GS.StoredType = GlobalStatus::isStored;
Chris Lattner617f1a32004-10-07 21:30:30 +0000214 }
Chris Lattner7561ca12005-02-27 18:58:52 +0000215 } else if (isa<GetElementPtrInst>(I)) {
Chris Lattner25db5802004-10-07 04:16:33 +0000216 if (AnalyzeGlobal(I, GS, PHIUsers)) return true;
Chris Lattner004e2502004-10-11 05:54:41 +0000217
218 // If the first two indices are constants, this can be SRA'd.
219 if (isa<GlobalVariable>(I->getOperand(0))) {
220 if (I->getNumOperands() < 3 || !isa<Constant>(I->getOperand(1)) ||
Misha Brukmanb1c93172005-04-21 23:48:37 +0000221 !cast<Constant>(I->getOperand(1))->isNullValue() ||
Chris Lattner004e2502004-10-11 05:54:41 +0000222 !isa<ConstantInt>(I->getOperand(2)))
223 GS.isNotSuitableForSRA = true;
224 } else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(I->getOperand(0))){
225 if (CE->getOpcode() != Instruction::GetElementPtr ||
226 CE->getNumOperands() < 3 || I->getNumOperands() < 2 ||
227 !isa<Constant>(I->getOperand(0)) ||
228 !cast<Constant>(I->getOperand(0))->isNullValue())
229 GS.isNotSuitableForSRA = true;
230 } else {
231 GS.isNotSuitableForSRA = true;
232 }
Chris Lattner7561ca12005-02-27 18:58:52 +0000233 } else if (isa<SelectInst>(I)) {
Chris Lattner25db5802004-10-07 04:16:33 +0000234 if (AnalyzeGlobal(I, GS, PHIUsers)) return true;
235 GS.isNotSuitableForSRA = true;
236 } else if (PHINode *PN = dyn_cast<PHINode>(I)) {
237 // PHI nodes we can check just like select or GEP instructions, but we
238 // have to be careful about infinite recursion.
239 if (PHIUsers.insert(PN).second) // Not already visited.
240 if (AnalyzeGlobal(I, GS, PHIUsers)) return true;
241 GS.isNotSuitableForSRA = true;
Chris Lattner5a0bd612006-11-01 18:03:33 +0000242 GS.HasPHIUser = true;
Reid Spencer266e42b2006-12-23 06:05:41 +0000243 } else if (isa<CmpInst>(I)) {
Chris Lattner25db5802004-10-07 04:16:33 +0000244 GS.isNotSuitableForSRA = true;
Chris Lattner7561ca12005-02-27 18:58:52 +0000245 } else if (isa<MemCpyInst>(I) || isa<MemMoveInst>(I)) {
246 if (I->getOperand(1) == V)
247 GS.StoredType = GlobalStatus::isStored;
248 if (I->getOperand(2) == V)
249 GS.isLoaded = true;
250 GS.isNotSuitableForSRA = true;
251 } else if (isa<MemSetInst>(I)) {
252 assert(I->getOperand(1) == V && "Memset only takes one pointer!");
253 GS.StoredType = GlobalStatus::isStored;
254 GS.isNotSuitableForSRA = true;
Chris Lattner25db5802004-10-07 04:16:33 +0000255 } else {
256 return true; // Any other non-load instruction might take address!
257 }
Chris Lattner1c4bddc2004-10-08 20:59:28 +0000258 } else if (Constant *C = dyn_cast<Constant>(*UI)) {
Chris Lattner50bdfcb2005-06-15 21:11:48 +0000259 GS.HasNonInstructionUser = true;
Chris Lattner1c4bddc2004-10-08 20:59:28 +0000260 // We might have a dead and dangling constant hanging off of here.
261 if (!ConstantIsDead(C))
262 return true;
Chris Lattner25db5802004-10-07 04:16:33 +0000263 } else {
Chris Lattner50bdfcb2005-06-15 21:11:48 +0000264 GS.HasNonInstructionUser = true;
265 // Otherwise must be some other user.
Chris Lattner25db5802004-10-07 04:16:33 +0000266 return true;
267 }
268
269 return false;
270}
271
Chris Lattnerabab0712004-10-08 17:32:09 +0000272static Constant *getAggregateConstantElement(Constant *Agg, Constant *Idx) {
273 ConstantInt *CI = dyn_cast<ConstantInt>(Idx);
274 if (!CI) return 0;
Reid Spencere0fc4df2006-10-20 07:07:24 +0000275 unsigned IdxV = CI->getZExtValue();
Chris Lattner25db5802004-10-07 04:16:33 +0000276
Chris Lattnerabab0712004-10-08 17:32:09 +0000277 if (ConstantStruct *CS = dyn_cast<ConstantStruct>(Agg)) {
278 if (IdxV < CS->getNumOperands()) return CS->getOperand(IdxV);
279 } else if (ConstantArray *CA = dyn_cast<ConstantArray>(Agg)) {
280 if (IdxV < CA->getNumOperands()) return CA->getOperand(IdxV);
281 } else if (ConstantPacked *CP = dyn_cast<ConstantPacked>(Agg)) {
282 if (IdxV < CP->getNumOperands()) return CP->getOperand(IdxV);
Chris Lattner8e71c6a2004-10-16 18:09:00 +0000283 } else if (isa<ConstantAggregateZero>(Agg)) {
Chris Lattnerabab0712004-10-08 17:32:09 +0000284 if (const StructType *STy = dyn_cast<StructType>(Agg->getType())) {
285 if (IdxV < STy->getNumElements())
286 return Constant::getNullValue(STy->getElementType(IdxV));
287 } else if (const SequentialType *STy =
288 dyn_cast<SequentialType>(Agg->getType())) {
289 return Constant::getNullValue(STy->getElementType());
290 }
Chris Lattner8e71c6a2004-10-16 18:09:00 +0000291 } else if (isa<UndefValue>(Agg)) {
292 if (const StructType *STy = dyn_cast<StructType>(Agg->getType())) {
293 if (IdxV < STy->getNumElements())
294 return UndefValue::get(STy->getElementType(IdxV));
295 } else if (const SequentialType *STy =
296 dyn_cast<SequentialType>(Agg->getType())) {
297 return UndefValue::get(STy->getElementType());
298 }
Chris Lattnerabab0712004-10-08 17:32:09 +0000299 }
300 return 0;
301}
Chris Lattner25db5802004-10-07 04:16:33 +0000302
Chris Lattner25db5802004-10-07 04:16:33 +0000303
304/// CleanupConstantGlobalUsers - We just marked GV constant. Loop over all
305/// users of the global, cleaning up the obvious ones. This is largely just a
Chris Lattnercb9f1522004-10-10 16:43:46 +0000306/// quick scan over the use list to clean up the easy and obvious cruft. This
307/// returns true if it made a change.
308static bool CleanupConstantGlobalUsers(Value *V, Constant *Init) {
309 bool Changed = false;
Chris Lattner25db5802004-10-07 04:16:33 +0000310 for (Value::use_iterator UI = V->use_begin(), E = V->use_end(); UI != E;) {
311 User *U = *UI++;
Misha Brukmanb1c93172005-04-21 23:48:37 +0000312
Chris Lattner25db5802004-10-07 04:16:33 +0000313 if (LoadInst *LI = dyn_cast<LoadInst>(U)) {
Chris Lattner7561ca12005-02-27 18:58:52 +0000314 if (Init) {
315 // Replace the load with the initializer.
316 LI->replaceAllUsesWith(Init);
317 LI->eraseFromParent();
318 Changed = true;
319 }
Chris Lattner25db5802004-10-07 04:16:33 +0000320 } else if (StoreInst *SI = dyn_cast<StoreInst>(U)) {
321 // Store must be unreachable or storing Init into the global.
Chris Lattner8e71c6a2004-10-16 18:09:00 +0000322 SI->eraseFromParent();
Chris Lattnercb9f1522004-10-10 16:43:46 +0000323 Changed = true;
Chris Lattner25db5802004-10-07 04:16:33 +0000324 } else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(U)) {
325 if (CE->getOpcode() == Instruction::GetElementPtr) {
Chris Lattner46d9ff082005-09-26 07:34:35 +0000326 Constant *SubInit = 0;
327 if (Init)
328 SubInit = ConstantFoldLoadThroughGEPConstantExpr(Init, CE);
Chris Lattner7561ca12005-02-27 18:58:52 +0000329 Changed |= CleanupConstantGlobalUsers(CE, SubInit);
Reid Spencer6c38f0b2006-11-27 01:05:10 +0000330 } else if (CE->getOpcode() == Instruction::BitCast &&
Chris Lattner7561ca12005-02-27 18:58:52 +0000331 isa<PointerType>(CE->getType())) {
332 // Pointer cast, delete any stores and memsets to the global.
333 Changed |= CleanupConstantGlobalUsers(CE, 0);
334 }
335
336 if (CE->use_empty()) {
337 CE->destroyConstant();
338 Changed = true;
Chris Lattner25db5802004-10-07 04:16:33 +0000339 }
340 } else if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(U)) {
Chris Lattner61ff32c2005-09-26 05:34:07 +0000341 Constant *SubInit = 0;
Chris Lattner46af55e2005-09-26 06:52:44 +0000342 ConstantExpr *CE =
343 dyn_cast_or_null<ConstantExpr>(ConstantFoldInstruction(GEP));
Chris Lattnereb953f02005-09-27 22:28:11 +0000344 if (Init && CE && CE->getOpcode() == Instruction::GetElementPtr)
Chris Lattner61ff32c2005-09-26 05:34:07 +0000345 SubInit = ConstantFoldLoadThroughGEPConstantExpr(Init, CE);
Chris Lattner7561ca12005-02-27 18:58:52 +0000346 Changed |= CleanupConstantGlobalUsers(GEP, SubInit);
Chris Lattnera0e769c2004-10-10 16:47:33 +0000347
Chris Lattnercb9f1522004-10-10 16:43:46 +0000348 if (GEP->use_empty()) {
Chris Lattner8e71c6a2004-10-16 18:09:00 +0000349 GEP->eraseFromParent();
Chris Lattnercb9f1522004-10-10 16:43:46 +0000350 Changed = true;
351 }
Chris Lattner7561ca12005-02-27 18:58:52 +0000352 } else if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(U)) { // memset/cpy/mv
353 if (MI->getRawDest() == V) {
354 MI->eraseFromParent();
355 Changed = true;
356 }
357
Chris Lattner1c4bddc2004-10-08 20:59:28 +0000358 } else if (Constant *C = dyn_cast<Constant>(U)) {
359 // If we have a chain of dead constantexprs or other things dangling from
360 // us, and if they are all dead, nuke them without remorse.
361 if (ConstantIsDead(C)) {
362 C->destroyConstant();
Chris Lattner7561ca12005-02-27 18:58:52 +0000363 // This could have invalidated UI, start over from scratch.
Chris Lattner1c4bddc2004-10-08 20:59:28 +0000364 CleanupConstantGlobalUsers(V, Init);
Chris Lattnercb9f1522004-10-10 16:43:46 +0000365 return true;
Chris Lattner1c4bddc2004-10-08 20:59:28 +0000366 }
Chris Lattner25db5802004-10-07 04:16:33 +0000367 }
368 }
Chris Lattnercb9f1522004-10-10 16:43:46 +0000369 return Changed;
Chris Lattner25db5802004-10-07 04:16:33 +0000370}
371
Chris Lattnerabab0712004-10-08 17:32:09 +0000372/// SRAGlobal - Perform scalar replacement of aggregates on the specified global
373/// variable. This opens the door for other optimizations by exposing the
374/// behavior of the program in a more fine-grained way. We have determined that
375/// this transformation is safe already. We return the first global variable we
376/// insert so that the caller can reprocess it.
377static GlobalVariable *SRAGlobal(GlobalVariable *GV) {
378 assert(GV->hasInternalLinkage() && !GV->isConstant());
379 Constant *Init = GV->getInitializer();
380 const Type *Ty = Init->getType();
Misha Brukmanb1c93172005-04-21 23:48:37 +0000381
Chris Lattnerabab0712004-10-08 17:32:09 +0000382 std::vector<GlobalVariable*> NewGlobals;
383 Module::GlobalListType &Globals = GV->getParent()->getGlobalList();
384
385 if (const StructType *STy = dyn_cast<StructType>(Ty)) {
386 NewGlobals.reserve(STy->getNumElements());
387 for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) {
388 Constant *In = getAggregateConstantElement(Init,
Reid Spencerc635f472006-12-31 05:48:39 +0000389 ConstantInt::get(Type::Int32Ty, i));
Chris Lattnerabab0712004-10-08 17:32:09 +0000390 assert(In && "Couldn't get element of initializer?");
391 GlobalVariable *NGV = new GlobalVariable(STy->getElementType(i), false,
392 GlobalVariable::InternalLinkage,
393 In, GV->getName()+"."+utostr(i));
394 Globals.insert(GV, NGV);
395 NewGlobals.push_back(NGV);
396 }
397 } else if (const SequentialType *STy = dyn_cast<SequentialType>(Ty)) {
398 unsigned NumElements = 0;
399 if (const ArrayType *ATy = dyn_cast<ArrayType>(STy))
400 NumElements = ATy->getNumElements();
401 else if (const PackedType *PTy = dyn_cast<PackedType>(STy))
402 NumElements = PTy->getNumElements();
403 else
404 assert(0 && "Unknown aggregate sequential type!");
405
Chris Lattner25169ca2005-02-23 16:53:04 +0000406 if (NumElements > 16 && GV->hasNUsesOrMore(16))
Chris Lattnerd6a44922005-02-01 01:23:31 +0000407 return 0; // It's not worth it.
Chris Lattnerabab0712004-10-08 17:32:09 +0000408 NewGlobals.reserve(NumElements);
409 for (unsigned i = 0, e = NumElements; i != e; ++i) {
410 Constant *In = getAggregateConstantElement(Init,
Reid Spencerc635f472006-12-31 05:48:39 +0000411 ConstantInt::get(Type::Int32Ty, i));
Chris Lattnerabab0712004-10-08 17:32:09 +0000412 assert(In && "Couldn't get element of initializer?");
413
414 GlobalVariable *NGV = new GlobalVariable(STy->getElementType(), false,
415 GlobalVariable::InternalLinkage,
416 In, GV->getName()+"."+utostr(i));
417 Globals.insert(GV, NGV);
418 NewGlobals.push_back(NGV);
419 }
420 }
421
422 if (NewGlobals.empty())
423 return 0;
424
Bill Wendling8f13b5c2006-11-26 10:02:32 +0000425 DOUT << "PERFORMING GLOBAL SRA ON: " << *GV;
Chris Lattner004e2502004-10-11 05:54:41 +0000426
Reid Spencerc635f472006-12-31 05:48:39 +0000427 Constant *NullInt = Constant::getNullValue(Type::Int32Ty);
Chris Lattnerabab0712004-10-08 17:32:09 +0000428
429 // Loop over all of the uses of the global, replacing the constantexpr geps,
430 // with smaller constantexpr geps or direct references.
431 while (!GV->use_empty()) {
Chris Lattner004e2502004-10-11 05:54:41 +0000432 User *GEP = GV->use_back();
433 assert(((isa<ConstantExpr>(GEP) &&
434 cast<ConstantExpr>(GEP)->getOpcode()==Instruction::GetElementPtr)||
435 isa<GetElementPtrInst>(GEP)) && "NonGEP CE's are not SRAable!");
Misha Brukmanb1c93172005-04-21 23:48:37 +0000436
Chris Lattnerabab0712004-10-08 17:32:09 +0000437 // Ignore the 1th operand, which has to be zero or else the program is quite
438 // broken (undefined). Get the 2nd operand, which is the structure or array
439 // index.
Reid Spencere0fc4df2006-10-20 07:07:24 +0000440 unsigned Val = cast<ConstantInt>(GEP->getOperand(2))->getZExtValue();
Chris Lattnerabab0712004-10-08 17:32:09 +0000441 if (Val >= NewGlobals.size()) Val = 0; // Out of bound array access.
442
Chris Lattner004e2502004-10-11 05:54:41 +0000443 Value *NewPtr = NewGlobals[Val];
Chris Lattnerabab0712004-10-08 17:32:09 +0000444
445 // Form a shorter GEP if needed.
Chris Lattner004e2502004-10-11 05:54:41 +0000446 if (GEP->getNumOperands() > 3)
447 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(GEP)) {
Chris Lattnerf96f4a82007-01-31 04:40:53 +0000448 SmallVector<Constant*, 8> Idxs;
Chris Lattner004e2502004-10-11 05:54:41 +0000449 Idxs.push_back(NullInt);
450 for (unsigned i = 3, e = CE->getNumOperands(); i != e; ++i)
451 Idxs.push_back(CE->getOperand(i));
Chris Lattnerf96f4a82007-01-31 04:40:53 +0000452 NewPtr = ConstantExpr::getGetElementPtr(cast<Constant>(NewPtr),
453 &Idxs[0], Idxs.size());
Chris Lattner004e2502004-10-11 05:54:41 +0000454 } else {
455 GetElementPtrInst *GEPI = cast<GetElementPtrInst>(GEP);
Chris Lattner927653f2007-01-31 19:59:55 +0000456 SmallVector<Value*, 8> Idxs;
Chris Lattner004e2502004-10-11 05:54:41 +0000457 Idxs.push_back(NullInt);
458 for (unsigned i = 3, e = GEPI->getNumOperands(); i != e; ++i)
459 Idxs.push_back(GEPI->getOperand(i));
Chris Lattner927653f2007-01-31 19:59:55 +0000460 NewPtr = new GetElementPtrInst(NewPtr, &Idxs[0], Idxs.size(),
Chris Lattner004e2502004-10-11 05:54:41 +0000461 GEPI->getName()+"."+utostr(Val), GEPI);
462 }
463 GEP->replaceAllUsesWith(NewPtr);
464
465 if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(GEP))
Chris Lattner8e71c6a2004-10-16 18:09:00 +0000466 GEPI->eraseFromParent();
Chris Lattner004e2502004-10-11 05:54:41 +0000467 else
468 cast<ConstantExpr>(GEP)->destroyConstant();
Chris Lattnerabab0712004-10-08 17:32:09 +0000469 }
470
Chris Lattner73ad73e2004-10-08 20:25:55 +0000471 // Delete the old global, now that it is dead.
472 Globals.erase(GV);
Chris Lattnerabab0712004-10-08 17:32:09 +0000473 ++NumSRA;
Chris Lattner004e2502004-10-11 05:54:41 +0000474
475 // Loop over the new globals array deleting any globals that are obviously
476 // dead. This can arise due to scalarization of a structure or an array that
477 // has elements that are dead.
478 unsigned FirstGlobal = 0;
479 for (unsigned i = 0, e = NewGlobals.size(); i != e; ++i)
480 if (NewGlobals[i]->use_empty()) {
481 Globals.erase(NewGlobals[i]);
482 if (FirstGlobal == i) ++FirstGlobal;
483 }
484
485 return FirstGlobal != NewGlobals.size() ? NewGlobals[FirstGlobal] : 0;
Chris Lattnerabab0712004-10-08 17:32:09 +0000486}
487
Chris Lattner09a52722004-10-09 21:48:45 +0000488/// AllUsesOfValueWillTrapIfNull - Return true if all users of the specified
489/// value will trap if the value is dynamically null.
490static bool AllUsesOfValueWillTrapIfNull(Value *V) {
491 for (Value::use_iterator UI = V->use_begin(), E = V->use_end(); UI != E; ++UI)
492 if (isa<LoadInst>(*UI)) {
493 // Will trap.
494 } else if (StoreInst *SI = dyn_cast<StoreInst>(*UI)) {
495 if (SI->getOperand(0) == V) {
Bill Wendlingf3baad32006-12-07 01:30:32 +0000496 //cerr << "NONTRAPPING USE: " << **UI;
Chris Lattner09a52722004-10-09 21:48:45 +0000497 return false; // Storing the value.
498 }
499 } else if (CallInst *CI = dyn_cast<CallInst>(*UI)) {
500 if (CI->getOperand(0) != V) {
Bill Wendlingf3baad32006-12-07 01:30:32 +0000501 //cerr << "NONTRAPPING USE: " << **UI;
Chris Lattner09a52722004-10-09 21:48:45 +0000502 return false; // Not calling the ptr
503 }
504 } else if (InvokeInst *II = dyn_cast<InvokeInst>(*UI)) {
505 if (II->getOperand(0) != V) {
Bill Wendlingf3baad32006-12-07 01:30:32 +0000506 //cerr << "NONTRAPPING USE: " << **UI;
Chris Lattner09a52722004-10-09 21:48:45 +0000507 return false; // Not calling the ptr
508 }
509 } else if (CastInst *CI = dyn_cast<CastInst>(*UI)) {
510 if (!AllUsesOfValueWillTrapIfNull(CI)) return false;
511 } else if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(*UI)) {
512 if (!AllUsesOfValueWillTrapIfNull(GEPI)) return false;
Reid Spencer266e42b2006-12-23 06:05:41 +0000513 } else if (isa<ICmpInst>(*UI) &&
Chris Lattnerfe9abf92004-10-22 06:43:28 +0000514 isa<ConstantPointerNull>(UI->getOperand(1))) {
515 // Ignore setcc X, null
Chris Lattner09a52722004-10-09 21:48:45 +0000516 } else {
Bill Wendlingf3baad32006-12-07 01:30:32 +0000517 //cerr << "NONTRAPPING USE: " << **UI;
Chris Lattner09a52722004-10-09 21:48:45 +0000518 return false;
519 }
520 return true;
521}
522
523/// AllUsesOfLoadedValueWillTrapIfNull - Return true if all uses of any loads
Chris Lattnerfe9abf92004-10-22 06:43:28 +0000524/// from GV will trap if the loaded value is null. Note that this also permits
525/// comparisons of the loaded value against null, as a special case.
Chris Lattner09a52722004-10-09 21:48:45 +0000526static bool AllUsesOfLoadedValueWillTrapIfNull(GlobalVariable *GV) {
527 for (Value::use_iterator UI = GV->use_begin(), E = GV->use_end(); UI!=E; ++UI)
528 if (LoadInst *LI = dyn_cast<LoadInst>(*UI)) {
529 if (!AllUsesOfValueWillTrapIfNull(LI))
530 return false;
531 } else if (isa<StoreInst>(*UI)) {
532 // Ignore stores to the global.
533 } else {
534 // We don't know or understand this user, bail out.
Bill Wendlingf3baad32006-12-07 01:30:32 +0000535 //cerr << "UNKNOWN USER OF GLOBAL!: " << **UI;
Chris Lattner09a52722004-10-09 21:48:45 +0000536 return false;
537 }
538
539 return true;
540}
541
Chris Lattnere42eb312004-10-10 23:14:11 +0000542static bool OptimizeAwayTrappingUsesOfValue(Value *V, Constant *NewV) {
543 bool Changed = false;
544 for (Value::use_iterator UI = V->use_begin(), E = V->use_end(); UI != E; ) {
545 Instruction *I = cast<Instruction>(*UI++);
546 if (LoadInst *LI = dyn_cast<LoadInst>(I)) {
547 LI->setOperand(0, NewV);
548 Changed = true;
549 } else if (StoreInst *SI = dyn_cast<StoreInst>(I)) {
550 if (SI->getOperand(1) == V) {
551 SI->setOperand(1, NewV);
552 Changed = true;
553 }
554 } else if (isa<CallInst>(I) || isa<InvokeInst>(I)) {
555 if (I->getOperand(0) == V) {
556 // Calling through the pointer! Turn into a direct call, but be careful
557 // that the pointer is not also being passed as an argument.
558 I->setOperand(0, NewV);
559 Changed = true;
560 bool PassedAsArg = false;
561 for (unsigned i = 1, e = I->getNumOperands(); i != e; ++i)
562 if (I->getOperand(i) == V) {
563 PassedAsArg = true;
564 I->setOperand(i, NewV);
565 }
566
567 if (PassedAsArg) {
568 // Being passed as an argument also. Be careful to not invalidate UI!
569 UI = V->use_begin();
570 }
571 }
572 } else if (CastInst *CI = dyn_cast<CastInst>(I)) {
573 Changed |= OptimizeAwayTrappingUsesOfValue(CI,
Chris Lattner3ede00b2006-11-30 17:32:29 +0000574 ConstantExpr::getCast(CI->getOpcode(),
575 NewV, CI->getType()));
Chris Lattnere42eb312004-10-10 23:14:11 +0000576 if (CI->use_empty()) {
577 Changed = true;
Chris Lattner8e71c6a2004-10-16 18:09:00 +0000578 CI->eraseFromParent();
Chris Lattnere42eb312004-10-10 23:14:11 +0000579 }
580 } else if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(I)) {
581 // Should handle GEP here.
Chris Lattnerf96f4a82007-01-31 04:40:53 +0000582 SmallVector<Constant*, 8> Idxs;
583 Idxs.reserve(GEPI->getNumOperands()-1);
Chris Lattnere42eb312004-10-10 23:14:11 +0000584 for (unsigned i = 1, e = GEPI->getNumOperands(); i != e; ++i)
585 if (Constant *C = dyn_cast<Constant>(GEPI->getOperand(i)))
Chris Lattnerf96f4a82007-01-31 04:40:53 +0000586 Idxs.push_back(C);
Chris Lattnere42eb312004-10-10 23:14:11 +0000587 else
588 break;
Chris Lattnerf96f4a82007-01-31 04:40:53 +0000589 if (Idxs.size() == GEPI->getNumOperands()-1)
Chris Lattnere42eb312004-10-10 23:14:11 +0000590 Changed |= OptimizeAwayTrappingUsesOfValue(GEPI,
Chris Lattnerf96f4a82007-01-31 04:40:53 +0000591 ConstantExpr::getGetElementPtr(NewV, &Idxs[0],
592 Idxs.size()));
Chris Lattnere42eb312004-10-10 23:14:11 +0000593 if (GEPI->use_empty()) {
594 Changed = true;
Chris Lattner8e71c6a2004-10-16 18:09:00 +0000595 GEPI->eraseFromParent();
Chris Lattnere42eb312004-10-10 23:14:11 +0000596 }
597 }
598 }
599
600 return Changed;
601}
602
603
604/// OptimizeAwayTrappingUsesOfLoads - The specified global has only one non-null
605/// value stored into it. If there are uses of the loaded value that would trap
606/// if the loaded value is dynamically null, then we know that they cannot be
607/// reachable with a null optimize away the load.
608static bool OptimizeAwayTrappingUsesOfLoads(GlobalVariable *GV, Constant *LV) {
609 std::vector<LoadInst*> Loads;
610 bool Changed = false;
611
612 // Replace all uses of loads with uses of uses of the stored value.
613 for (Value::use_iterator GUI = GV->use_begin(), E = GV->use_end();
614 GUI != E; ++GUI)
615 if (LoadInst *LI = dyn_cast<LoadInst>(*GUI)) {
616 Loads.push_back(LI);
617 Changed |= OptimizeAwayTrappingUsesOfValue(LI, LV);
618 } else {
619 assert(isa<StoreInst>(*GUI) && "Only expect load and stores!");
620 }
621
622 if (Changed) {
Bill Wendling8f13b5c2006-11-26 10:02:32 +0000623 DOUT << "OPTIMIZED LOADS FROM STORED ONCE POINTER: " << *GV;
Chris Lattnere42eb312004-10-10 23:14:11 +0000624 ++NumGlobUses;
625 }
626
627 // Delete all of the loads we can, keeping track of whether we nuked them all!
628 bool AllLoadsGone = true;
629 while (!Loads.empty()) {
630 LoadInst *L = Loads.back();
631 if (L->use_empty()) {
Chris Lattner8e71c6a2004-10-16 18:09:00 +0000632 L->eraseFromParent();
Chris Lattnere42eb312004-10-10 23:14:11 +0000633 Changed = true;
634 } else {
635 AllLoadsGone = false;
636 }
637 Loads.pop_back();
638 }
639
640 // If we nuked all of the loads, then none of the stores are needed either,
641 // nor is the global.
642 if (AllLoadsGone) {
Bill Wendling8f13b5c2006-11-26 10:02:32 +0000643 DOUT << " *** GLOBAL NOW DEAD!\n";
Chris Lattnere42eb312004-10-10 23:14:11 +0000644 CleanupConstantGlobalUsers(GV, 0);
645 if (GV->use_empty()) {
Chris Lattner8e71c6a2004-10-16 18:09:00 +0000646 GV->eraseFromParent();
Chris Lattnere42eb312004-10-10 23:14:11 +0000647 ++NumDeleted;
648 }
649 Changed = true;
650 }
651 return Changed;
652}
653
Chris Lattner004e2502004-10-11 05:54:41 +0000654/// ConstantPropUsersOf - Walk the use list of V, constant folding all of the
655/// instructions that are foldable.
656static void ConstantPropUsersOf(Value *V) {
657 for (Value::use_iterator UI = V->use_begin(), E = V->use_end(); UI != E; )
658 if (Instruction *I = dyn_cast<Instruction>(*UI++))
659 if (Constant *NewC = ConstantFoldInstruction(I)) {
660 I->replaceAllUsesWith(NewC);
661
Chris Lattnerd6a44922005-02-01 01:23:31 +0000662 // Advance UI to the next non-I use to avoid invalidating it!
663 // Instructions could multiply use V.
664 while (UI != E && *UI == I)
Chris Lattner004e2502004-10-11 05:54:41 +0000665 ++UI;
Chris Lattnerd6a44922005-02-01 01:23:31 +0000666 I->eraseFromParent();
Chris Lattner004e2502004-10-11 05:54:41 +0000667 }
668}
669
670/// OptimizeGlobalAddressOfMalloc - This function takes the specified global
671/// variable, and transforms the program as if it always contained the result of
672/// the specified malloc. Because it is always the result of the specified
673/// malloc, there is no reason to actually DO the malloc. Instead, turn the
Chris Lattner3ede00b2006-11-30 17:32:29 +0000674/// malloc into a global, and any loads of GV as uses of the new global.
Chris Lattner004e2502004-10-11 05:54:41 +0000675static GlobalVariable *OptimizeGlobalAddressOfMalloc(GlobalVariable *GV,
676 MallocInst *MI) {
Bill Wendling8f13b5c2006-11-26 10:02:32 +0000677 DOUT << "PROMOTING MALLOC GLOBAL: " << *GV << " MALLOC = " << *MI;
Chris Lattner004e2502004-10-11 05:54:41 +0000678 ConstantInt *NElements = cast<ConstantInt>(MI->getArraySize());
679
Reid Spencere0fc4df2006-10-20 07:07:24 +0000680 if (NElements->getZExtValue() != 1) {
Chris Lattner004e2502004-10-11 05:54:41 +0000681 // If we have an array allocation, transform it to a single element
682 // allocation to make the code below simpler.
683 Type *NewTy = ArrayType::get(MI->getAllocatedType(),
Reid Spencere0fc4df2006-10-20 07:07:24 +0000684 NElements->getZExtValue());
Chris Lattner004e2502004-10-11 05:54:41 +0000685 MallocInst *NewMI =
Reid Spencerc635f472006-12-31 05:48:39 +0000686 new MallocInst(NewTy, Constant::getNullValue(Type::Int32Ty),
Nate Begeman848622f2005-11-05 09:21:28 +0000687 MI->getAlignment(), MI->getName(), MI);
Chris Lattner927653f2007-01-31 19:59:55 +0000688 Value* Indices[2];
689 Indices[0] = Indices[1] = Constant::getNullValue(Type::Int32Ty);
690 Value *NewGEP = new GetElementPtrInst(NewMI, Indices, 2,
Chris Lattner004e2502004-10-11 05:54:41 +0000691 NewMI->getName()+".el0", MI);
692 MI->replaceAllUsesWith(NewGEP);
Chris Lattner8e71c6a2004-10-16 18:09:00 +0000693 MI->eraseFromParent();
Chris Lattner004e2502004-10-11 05:54:41 +0000694 MI = NewMI;
695 }
Misha Brukmanb1c93172005-04-21 23:48:37 +0000696
Chris Lattner8e71c6a2004-10-16 18:09:00 +0000697 // Create the new global variable. The contents of the malloc'd memory is
698 // undefined, so initialize with an undef value.
699 Constant *Init = UndefValue::get(MI->getAllocatedType());
Chris Lattner004e2502004-10-11 05:54:41 +0000700 GlobalVariable *NewGV = new GlobalVariable(MI->getAllocatedType(), false,
701 GlobalValue::InternalLinkage, Init,
702 GV->getName()+".body");
703 GV->getParent()->getGlobalList().insert(GV, NewGV);
Misha Brukmanb1c93172005-04-21 23:48:37 +0000704
Chris Lattner004e2502004-10-11 05:54:41 +0000705 // Anything that used the malloc now uses the global directly.
706 MI->replaceAllUsesWith(NewGV);
Chris Lattner004e2502004-10-11 05:54:41 +0000707
708 Constant *RepValue = NewGV;
709 if (NewGV->getType() != GV->getType()->getElementType())
Reid Spencerbb65ebf2006-12-12 23:36:14 +0000710 RepValue = ConstantExpr::getBitCast(RepValue,
711 GV->getType()->getElementType());
Chris Lattner004e2502004-10-11 05:54:41 +0000712
Chris Lattnerfe9abf92004-10-22 06:43:28 +0000713 // If there is a comparison against null, we will insert a global bool to
714 // keep track of whether the global was initialized yet or not.
Misha Brukmanb1c93172005-04-21 23:48:37 +0000715 GlobalVariable *InitBool =
Reid Spencer542964f2007-01-11 18:21:29 +0000716 new GlobalVariable(Type::Int1Ty, false, GlobalValue::InternalLinkage,
Zhou Sheng75b871f2007-01-11 12:24:14 +0000717 ConstantInt::getFalse(), GV->getName()+".init");
Chris Lattner3b181392004-12-02 06:25:58 +0000718 bool InitBoolUsed = false;
Chris Lattnerfe9abf92004-10-22 06:43:28 +0000719
Chris Lattner004e2502004-10-11 05:54:41 +0000720 // Loop over all uses of GV, processing them in turn.
Chris Lattner3b181392004-12-02 06:25:58 +0000721 std::vector<StoreInst*> Stores;
Chris Lattner004e2502004-10-11 05:54:41 +0000722 while (!GV->use_empty())
723 if (LoadInst *LI = dyn_cast<LoadInst>(GV->use_back())) {
Chris Lattnerfe9abf92004-10-22 06:43:28 +0000724 while (!LI->use_empty()) {
Chris Lattnerd6a44922005-02-01 01:23:31 +0000725 Use &LoadUse = LI->use_begin().getUse();
Reid Spencer266e42b2006-12-23 06:05:41 +0000726 if (!isa<ICmpInst>(LoadUse.getUser()))
Chris Lattnerfe9abf92004-10-22 06:43:28 +0000727 LoadUse = RepValue;
728 else {
Reid Spencer266e42b2006-12-23 06:05:41 +0000729 ICmpInst *CI = cast<ICmpInst>(LoadUse.getUser());
730 // Replace the cmp X, 0 with a use of the bool value.
731 Value *LV = new LoadInst(InitBool, InitBool->getName()+".val", CI);
Chris Lattner3b181392004-12-02 06:25:58 +0000732 InitBoolUsed = true;
Reid Spencer266e42b2006-12-23 06:05:41 +0000733 switch (CI->getPredicate()) {
734 default: assert(0 && "Unknown ICmp Predicate!");
735 case ICmpInst::ICMP_ULT:
736 case ICmpInst::ICMP_SLT:
Zhou Sheng75b871f2007-01-11 12:24:14 +0000737 LV = ConstantInt::getFalse(); // X < null -> always false
Chris Lattnerfe9abf92004-10-22 06:43:28 +0000738 break;
Reid Spencer266e42b2006-12-23 06:05:41 +0000739 case ICmpInst::ICMP_ULE:
740 case ICmpInst::ICMP_SLE:
741 case ICmpInst::ICMP_EQ:
742 LV = BinaryOperator::createNot(LV, "notinit", CI);
Chris Lattnerfe9abf92004-10-22 06:43:28 +0000743 break;
Reid Spencer266e42b2006-12-23 06:05:41 +0000744 case ICmpInst::ICMP_NE:
745 case ICmpInst::ICMP_UGE:
746 case ICmpInst::ICMP_SGE:
747 case ICmpInst::ICMP_UGT:
748 case ICmpInst::ICMP_SGT:
Chris Lattnerfe9abf92004-10-22 06:43:28 +0000749 break; // no change.
750 }
Reid Spencer266e42b2006-12-23 06:05:41 +0000751 CI->replaceAllUsesWith(LV);
752 CI->eraseFromParent();
Chris Lattnerfe9abf92004-10-22 06:43:28 +0000753 }
754 }
Chris Lattner8e71c6a2004-10-16 18:09:00 +0000755 LI->eraseFromParent();
Chris Lattner004e2502004-10-11 05:54:41 +0000756 } else {
757 StoreInst *SI = cast<StoreInst>(GV->use_back());
Chris Lattner3b181392004-12-02 06:25:58 +0000758 // The global is initialized when the store to it occurs.
Zhou Sheng75b871f2007-01-11 12:24:14 +0000759 new StoreInst(ConstantInt::getTrue(), InitBool, SI);
Chris Lattner8e71c6a2004-10-16 18:09:00 +0000760 SI->eraseFromParent();
Chris Lattner004e2502004-10-11 05:54:41 +0000761 }
762
Chris Lattner3b181392004-12-02 06:25:58 +0000763 // If the initialization boolean was used, insert it, otherwise delete it.
764 if (!InitBoolUsed) {
765 while (!InitBool->use_empty()) // Delete initializations
766 cast<Instruction>(InitBool->use_back())->eraseFromParent();
767 delete InitBool;
768 } else
769 GV->getParent()->getGlobalList().insert(GV, InitBool);
770
771
Chris Lattnerfe9abf92004-10-22 06:43:28 +0000772 // Now the GV is dead, nuke it and the malloc.
Chris Lattner8e71c6a2004-10-16 18:09:00 +0000773 GV->eraseFromParent();
Chris Lattnerfe9abf92004-10-22 06:43:28 +0000774 MI->eraseFromParent();
Chris Lattner004e2502004-10-11 05:54:41 +0000775
776 // To further other optimizations, loop over all users of NewGV and try to
777 // constant prop them. This will promote GEP instructions with constant
778 // indices into GEP constant-exprs, which will allow global-opt to hack on it.
779 ConstantPropUsersOf(NewGV);
780 if (RepValue != NewGV)
781 ConstantPropUsersOf(RepValue);
782
783 return NewGV;
784}
Chris Lattnere42eb312004-10-10 23:14:11 +0000785
Chris Lattnerc0677c02004-12-02 07:11:07 +0000786/// ValueIsOnlyUsedLocallyOrStoredToOneGlobal - Scan the use-list of V checking
787/// to make sure that there are no complex uses of V. We permit simple things
788/// like dereferencing the pointer, but not storing through the address, unless
789/// it is to the specified global.
790static bool ValueIsOnlyUsedLocallyOrStoredToOneGlobal(Instruction *V,
791 GlobalVariable *GV) {
792 for (Value::use_iterator UI = V->use_begin(), E = V->use_end(); UI != E;++UI)
Reid Spencer266e42b2006-12-23 06:05:41 +0000793 if (isa<LoadInst>(*UI) || isa<CmpInst>(*UI)) {
Chris Lattnerc0677c02004-12-02 07:11:07 +0000794 // Fine, ignore.
795 } else if (StoreInst *SI = dyn_cast<StoreInst>(*UI)) {
796 if (SI->getOperand(0) == V && SI->getOperand(1) != GV)
797 return false; // Storing the pointer itself... bad.
798 // Otherwise, storing through it, or storing into GV... fine.
799 } else if (isa<GetElementPtrInst>(*UI) || isa<SelectInst>(*UI)) {
800 if (!ValueIsOnlyUsedLocallyOrStoredToOneGlobal(cast<Instruction>(*UI),GV))
801 return false;
802 } else {
803 return false;
804 }
805 return true;
Chris Lattnerc0677c02004-12-02 07:11:07 +0000806}
807
Chris Lattner24d3d422006-09-30 23:32:09 +0000808/// ReplaceUsesOfMallocWithGlobal - The Alloc pointer is stored into GV
809/// somewhere. Transform all uses of the allocation into loads from the
810/// global and uses of the resultant pointer. Further, delete the store into
811/// GV. This assumes that these value pass the
812/// 'ValueIsOnlyUsedLocallyOrStoredToOneGlobal' predicate.
813static void ReplaceUsesOfMallocWithGlobal(Instruction *Alloc,
814 GlobalVariable *GV) {
815 while (!Alloc->use_empty()) {
816 Instruction *U = Alloc->use_back();
817 if (StoreInst *SI = dyn_cast<StoreInst>(U)) {
818 // If this is the store of the allocation into the global, remove it.
819 if (SI->getOperand(1) == GV) {
820 SI->eraseFromParent();
821 continue;
822 }
823 }
824
825 // Insert a load from the global, and use it instead of the malloc.
826 Value *NL = new LoadInst(GV, GV->getName()+".val", U);
827 U->replaceUsesOfWith(Alloc, NL);
828 }
829}
830
831/// GlobalLoadUsesSimpleEnoughForHeapSRA - If all users of values loaded from
832/// GV are simple enough to perform HeapSRA, return true.
833static bool GlobalLoadUsesSimpleEnoughForHeapSRA(GlobalVariable *GV) {
834 for (Value::use_iterator UI = GV->use_begin(), E = GV->use_end(); UI != E;
835 ++UI)
836 if (LoadInst *LI = dyn_cast<LoadInst>(*UI)) {
837 // We permit two users of the load: setcc comparing against the null
838 // pointer, and a getelementptr of a specific form.
839 for (Value::use_iterator UI = LI->use_begin(), E = LI->use_end(); UI != E;
840 ++UI) {
841 // Comparison against null is ok.
Reid Spencer266e42b2006-12-23 06:05:41 +0000842 if (ICmpInst *ICI = dyn_cast<ICmpInst>(*UI)) {
843 if (!isa<ConstantPointerNull>(ICI->getOperand(1)))
Chris Lattner24d3d422006-09-30 23:32:09 +0000844 return false;
845 continue;
846 }
847
848 // getelementptr is also ok, but only a simple form.
849 GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(*UI);
850 if (!GEPI) return false;
851
852 // Must index into the array and into the struct.
853 if (GEPI->getNumOperands() < 3)
854 return false;
855
856 // Otherwise the GEP is ok.
857 continue;
858 }
859 }
860 return true;
861}
862
863/// RewriteUsesOfLoadForHeapSRoA - We are performing Heap SRoA on a global. Ptr
864/// is a value loaded from the global. Eliminate all uses of Ptr, making them
865/// use FieldGlobals instead. All uses of loaded values satisfy
866/// GlobalLoadUsesSimpleEnoughForHeapSRA.
867static void RewriteUsesOfLoadForHeapSRoA(LoadInst *Ptr,
868 const std::vector<GlobalVariable*> &FieldGlobals) {
869 std::vector<Value *> InsertedLoadsForPtr;
870 //InsertedLoadsForPtr.resize(FieldGlobals.size());
871 while (!Ptr->use_empty()) {
872 Instruction *User = Ptr->use_back();
873
874 // If this is a comparison against null, handle it.
Reid Spencer266e42b2006-12-23 06:05:41 +0000875 if (ICmpInst *SCI = dyn_cast<ICmpInst>(User)) {
Chris Lattner24d3d422006-09-30 23:32:09 +0000876 assert(isa<ConstantPointerNull>(SCI->getOperand(1)));
877 // If we have a setcc of the loaded pointer, we can use a setcc of any
878 // field.
879 Value *NPtr;
880 if (InsertedLoadsForPtr.empty()) {
881 NPtr = new LoadInst(FieldGlobals[0], Ptr->getName()+".f0", Ptr);
882 InsertedLoadsForPtr.push_back(Ptr);
883 } else {
884 NPtr = InsertedLoadsForPtr.back();
885 }
886
Reid Spencer266e42b2006-12-23 06:05:41 +0000887 Value *New = new ICmpInst(SCI->getPredicate(), NPtr,
888 Constant::getNullValue(NPtr->getType()),
889 SCI->getName(), SCI);
Chris Lattner24d3d422006-09-30 23:32:09 +0000890 SCI->replaceAllUsesWith(New);
891 SCI->eraseFromParent();
892 continue;
893 }
894
895 // Otherwise, this should be: 'getelementptr Ptr, Idx, uint FieldNo ...'
896 GetElementPtrInst *GEPI = cast<GetElementPtrInst>(User);
Reid Spencere0fc4df2006-10-20 07:07:24 +0000897 assert(GEPI->getNumOperands() >= 3 && isa<ConstantInt>(GEPI->getOperand(2))
Chris Lattner24d3d422006-09-30 23:32:09 +0000898 && "Unexpected GEPI!");
899
900 // Load the pointer for this field.
Reid Spencere0fc4df2006-10-20 07:07:24 +0000901 unsigned FieldNo = cast<ConstantInt>(GEPI->getOperand(2))->getZExtValue();
Chris Lattner24d3d422006-09-30 23:32:09 +0000902 if (InsertedLoadsForPtr.size() <= FieldNo)
903 InsertedLoadsForPtr.resize(FieldNo+1);
904 if (InsertedLoadsForPtr[FieldNo] == 0)
905 InsertedLoadsForPtr[FieldNo] = new LoadInst(FieldGlobals[FieldNo],
906 Ptr->getName()+".f" +
907 utostr(FieldNo), Ptr);
908 Value *NewPtr = InsertedLoadsForPtr[FieldNo];
909
910 // Create the new GEP idx vector.
911 std::vector<Value*> GEPIdx;
912 GEPIdx.push_back(GEPI->getOperand(1));
913 GEPIdx.insert(GEPIdx.end(), GEPI->op_begin()+3, GEPI->op_end());
914
915 Value *NGEPI = new GetElementPtrInst(NewPtr, GEPIdx, GEPI->getName(), GEPI);
916 GEPI->replaceAllUsesWith(NGEPI);
917 GEPI->eraseFromParent();
918 }
919}
920
921/// PerformHeapAllocSRoA - MI is an allocation of an array of structures. Break
922/// it up into multiple allocations of arrays of the fields.
923static GlobalVariable *PerformHeapAllocSRoA(GlobalVariable *GV, MallocInst *MI){
Bill Wendling8f13b5c2006-11-26 10:02:32 +0000924 DOUT << "SROA HEAP ALLOC: " << *GV << " MALLOC = " << *MI;
Chris Lattner24d3d422006-09-30 23:32:09 +0000925 const StructType *STy = cast<StructType>(MI->getAllocatedType());
926
927 // There is guaranteed to be at least one use of the malloc (storing
928 // it into GV). If there are other uses, change them to be uses of
929 // the global to simplify later code. This also deletes the store
930 // into GV.
931 ReplaceUsesOfMallocWithGlobal(MI, GV);
932
933 // Okay, at this point, there are no users of the malloc. Insert N
934 // new mallocs at the same place as MI, and N globals.
935 std::vector<GlobalVariable*> FieldGlobals;
936 std::vector<MallocInst*> FieldMallocs;
937
938 for (unsigned FieldNo = 0, e = STy->getNumElements(); FieldNo != e;++FieldNo){
939 const Type *FieldTy = STy->getElementType(FieldNo);
940 const Type *PFieldTy = PointerType::get(FieldTy);
941
942 GlobalVariable *NGV =
943 new GlobalVariable(PFieldTy, false, GlobalValue::InternalLinkage,
944 Constant::getNullValue(PFieldTy),
945 GV->getName() + ".f" + utostr(FieldNo), GV);
946 FieldGlobals.push_back(NGV);
947
948 MallocInst *NMI = new MallocInst(FieldTy, MI->getArraySize(),
949 MI->getName() + ".f" + utostr(FieldNo),MI);
950 FieldMallocs.push_back(NMI);
951 new StoreInst(NMI, NGV, MI);
952 }
953
954 // The tricky aspect of this transformation is handling the case when malloc
955 // fails. In the original code, malloc failing would set the result pointer
956 // of malloc to null. In this case, some mallocs could succeed and others
957 // could fail. As such, we emit code that looks like this:
958 // F0 = malloc(field0)
959 // F1 = malloc(field1)
960 // F2 = malloc(field2)
961 // if (F0 == 0 || F1 == 0 || F2 == 0) {
962 // if (F0) { free(F0); F0 = 0; }
963 // if (F1) { free(F1); F1 = 0; }
964 // if (F2) { free(F2); F2 = 0; }
965 // }
966 Value *RunningOr = 0;
967 for (unsigned i = 0, e = FieldMallocs.size(); i != e; ++i) {
Reid Spencer266e42b2006-12-23 06:05:41 +0000968 Value *Cond = new ICmpInst(ICmpInst::ICMP_EQ, FieldMallocs[i],
Chris Lattner24d3d422006-09-30 23:32:09 +0000969 Constant::getNullValue(FieldMallocs[i]->getType()),
970 "isnull", MI);
971 if (!RunningOr)
972 RunningOr = Cond; // First seteq
973 else
974 RunningOr = BinaryOperator::createOr(RunningOr, Cond, "tmp", MI);
975 }
976
977 // Split the basic block at the old malloc.
978 BasicBlock *OrigBB = MI->getParent();
979 BasicBlock *ContBB = OrigBB->splitBasicBlock(MI, "malloc_cont");
980
981 // Create the block to check the first condition. Put all these blocks at the
982 // end of the function as they are unlikely to be executed.
983 BasicBlock *NullPtrBlock = new BasicBlock("malloc_ret_null",
984 OrigBB->getParent());
985
986 // Remove the uncond branch from OrigBB to ContBB, turning it into a cond
987 // branch on RunningOr.
988 OrigBB->getTerminator()->eraseFromParent();
989 new BranchInst(NullPtrBlock, ContBB, RunningOr, OrigBB);
990
991 // Within the NullPtrBlock, we need to emit a comparison and branch for each
992 // pointer, because some may be null while others are not.
993 for (unsigned i = 0, e = FieldGlobals.size(); i != e; ++i) {
994 Value *GVVal = new LoadInst(FieldGlobals[i], "tmp", NullPtrBlock);
Reid Spencer266e42b2006-12-23 06:05:41 +0000995 Value *Cmp = new ICmpInst(ICmpInst::ICMP_NE, GVVal,
996 Constant::getNullValue(GVVal->getType()),
997 "tmp", NullPtrBlock);
Chris Lattner24d3d422006-09-30 23:32:09 +0000998 BasicBlock *FreeBlock = new BasicBlock("free_it", OrigBB->getParent());
999 BasicBlock *NextBlock = new BasicBlock("next", OrigBB->getParent());
1000 new BranchInst(FreeBlock, NextBlock, Cmp, NullPtrBlock);
1001
1002 // Fill in FreeBlock.
1003 new FreeInst(GVVal, FreeBlock);
1004 new StoreInst(Constant::getNullValue(GVVal->getType()), FieldGlobals[i],
1005 FreeBlock);
1006 new BranchInst(NextBlock, FreeBlock);
1007
1008 NullPtrBlock = NextBlock;
1009 }
1010
1011 new BranchInst(ContBB, NullPtrBlock);
1012
1013
1014 // MI is no longer needed, remove it.
1015 MI->eraseFromParent();
1016
1017
1018 // Okay, the malloc site is completely handled. All of the uses of GV are now
1019 // loads, and all uses of those loads are simple. Rewrite them to use loads
1020 // of the per-field globals instead.
1021 while (!GV->use_empty()) {
Chris Lattner8571caa2007-01-09 23:29:37 +00001022 if (LoadInst *LI = dyn_cast<LoadInst>(GV->use_back())) {
1023 RewriteUsesOfLoadForHeapSRoA(LI, FieldGlobals);
1024 LI->eraseFromParent();
1025 } else {
1026 // Must be a store of null.
1027 StoreInst *SI = cast<StoreInst>(GV->use_back());
1028 assert(isa<Constant>(SI->getOperand(0)) &&
1029 cast<Constant>(SI->getOperand(0))->isNullValue() &&
1030 "Unexpected heap-sra user!");
1031
1032 // Insert a store of null into each global.
1033 for (unsigned i = 0, e = FieldGlobals.size(); i != e; ++i) {
1034 Constant *Null =
1035 Constant::getNullValue(FieldGlobals[i]->getType()->getElementType());
1036 new StoreInst(Null, FieldGlobals[i], SI);
1037 }
1038 // Erase the original store.
1039 SI->eraseFromParent();
1040 }
Chris Lattner24d3d422006-09-30 23:32:09 +00001041 }
1042
1043 // The old global is now dead, remove it.
1044 GV->eraseFromParent();
1045
1046 ++NumHeapSRA;
1047 return FieldGlobals[0];
1048}
1049
1050
Chris Lattner09a52722004-10-09 21:48:45 +00001051// OptimizeOnceStoredGlobal - Try to optimize globals based on the knowledge
1052// that only one value (besides its initializer) is ever stored to the global.
Chris Lattner004e2502004-10-11 05:54:41 +00001053static bool OptimizeOnceStoredGlobal(GlobalVariable *GV, Value *StoredOnceVal,
Chris Lattnerc2d3d312006-08-27 22:42:52 +00001054 Module::global_iterator &GVI,
1055 TargetData &TD) {
Chris Lattner09a52722004-10-09 21:48:45 +00001056 if (CastInst *CI = dyn_cast<CastInst>(StoredOnceVal))
1057 StoredOnceVal = CI->getOperand(0);
1058 else if (GetElementPtrInst *GEPI =dyn_cast<GetElementPtrInst>(StoredOnceVal)){
Chris Lattnere42eb312004-10-10 23:14:11 +00001059 // "getelementptr Ptr, 0, 0, 0" is really just a cast.
Chris Lattner09a52722004-10-09 21:48:45 +00001060 bool IsJustACast = true;
1061 for (unsigned i = 1, e = GEPI->getNumOperands(); i != e; ++i)
1062 if (!isa<Constant>(GEPI->getOperand(i)) ||
1063 !cast<Constant>(GEPI->getOperand(i))->isNullValue()) {
1064 IsJustACast = false;
1065 break;
1066 }
1067 if (IsJustACast)
1068 StoredOnceVal = GEPI->getOperand(0);
1069 }
1070
Chris Lattnere42eb312004-10-10 23:14:11 +00001071 // If we are dealing with a pointer global that is initialized to null and
1072 // only has one (non-null) value stored into it, then we can optimize any
1073 // users of the loaded value (often calls and loads) that would trap if the
1074 // value was null.
Chris Lattner09a52722004-10-09 21:48:45 +00001075 if (isa<PointerType>(GV->getInitializer()->getType()) &&
1076 GV->getInitializer()->isNullValue()) {
Chris Lattnere42eb312004-10-10 23:14:11 +00001077 if (Constant *SOVC = dyn_cast<Constant>(StoredOnceVal)) {
1078 if (GV->getInitializer()->getType() != SOVC->getType())
Reid Spencerbb65ebf2006-12-12 23:36:14 +00001079 SOVC = ConstantExpr::getBitCast(SOVC, GV->getInitializer()->getType());
Misha Brukmanb1c93172005-04-21 23:48:37 +00001080
Chris Lattnere42eb312004-10-10 23:14:11 +00001081 // Optimize away any trapping uses of the loaded value.
1082 if (OptimizeAwayTrappingUsesOfLoads(GV, SOVC))
Chris Lattner604ed7a2004-10-10 17:07:12 +00001083 return true;
Chris Lattner004e2502004-10-11 05:54:41 +00001084 } else if (MallocInst *MI = dyn_cast<MallocInst>(StoredOnceVal)) {
Chris Lattner80a01ef2006-09-30 19:40:30 +00001085 // If this is a malloc of an abstract type, don't touch it.
1086 if (!MI->getAllocatedType()->isSized())
1087 return false;
1088
Chris Lattner24d3d422006-09-30 23:32:09 +00001089 // We can't optimize this global unless all uses of it are *known* to be
1090 // of the malloc value, not of the null initializer value (consider a use
1091 // that compares the global's value against zero to see if the malloc has
1092 // been reached). To do this, we check to see if all uses of the global
1093 // would trap if the global were null: this proves that they must all
1094 // happen after the malloc.
1095 if (!AllUsesOfLoadedValueWillTrapIfNull(GV))
1096 return false;
1097
1098 // We can't optimize this if the malloc itself is used in a complex way,
1099 // for example, being stored into multiple globals. This allows the
1100 // malloc to be stored into the specified global, loaded setcc'd, and
1101 // GEP'd. These are all things we could transform to using the global
1102 // for.
1103 if (!ValueIsOnlyUsedLocallyOrStoredToOneGlobal(MI, GV))
1104 return false;
1105
1106
Chris Lattner004e2502004-10-11 05:54:41 +00001107 // If we have a global that is only initialized with a fixed size malloc,
Chris Lattner24d3d422006-09-30 23:32:09 +00001108 // transform the program to use global memory instead of malloc'd memory.
1109 // This eliminates dynamic allocation, avoids an indirection accessing the
1110 // data, and exposes the resultant global to further GlobalOpt.
Chris Lattner80a01ef2006-09-30 19:40:30 +00001111 if (ConstantInt *NElements = dyn_cast<ConstantInt>(MI->getArraySize())) {
Chris Lattner24d3d422006-09-30 23:32:09 +00001112 // Restrict this transformation to only working on small allocations
1113 // (2048 bytes currently), as we don't want to introduce a 16M global or
1114 // something.
Reid Spencere0fc4df2006-10-20 07:07:24 +00001115 if (NElements->getZExtValue()*
Chris Lattner24d3d422006-09-30 23:32:09 +00001116 TD.getTypeSize(MI->getAllocatedType()) < 2048) {
Chris Lattner004e2502004-10-11 05:54:41 +00001117 GVI = OptimizeGlobalAddressOfMalloc(GV, MI);
1118 return true;
1119 }
Chris Lattner80a01ef2006-09-30 19:40:30 +00001120 }
Chris Lattner24d3d422006-09-30 23:32:09 +00001121
1122 // If the allocation is an array of structures, consider transforming this
1123 // into multiple malloc'd arrays, one for each field. This is basically
1124 // SRoA for malloc'd memory.
1125 if (const StructType *AllocTy =
1126 dyn_cast<StructType>(MI->getAllocatedType())) {
1127 // This the structure has an unreasonable number of fields, leave it
1128 // alone.
1129 if (AllocTy->getNumElements() <= 16 && AllocTy->getNumElements() > 0 &&
1130 GlobalLoadUsesSimpleEnoughForHeapSRA(GV)) {
1131 GVI = PerformHeapAllocSRoA(GV, MI);
1132 return true;
1133 }
1134 }
Chris Lattnere42eb312004-10-10 23:14:11 +00001135 }
Chris Lattner09a52722004-10-09 21:48:45 +00001136 }
Chris Lattner004e2502004-10-11 05:54:41 +00001137
Chris Lattner09a52722004-10-09 21:48:45 +00001138 return false;
1139}
Chris Lattner1c4bddc2004-10-08 20:59:28 +00001140
Chris Lattner40e4cec2004-12-12 05:53:50 +00001141/// ShrinkGlobalToBoolean - At this point, we have learned that the only two
Misha Brukmanb1c93172005-04-21 23:48:37 +00001142/// values ever stored into GV are its initializer and OtherVal.
Chris Lattner40e4cec2004-12-12 05:53:50 +00001143static void ShrinkGlobalToBoolean(GlobalVariable *GV, Constant *OtherVal) {
1144 // Create the new global, initializing it to false.
Reid Spencer542964f2007-01-11 18:21:29 +00001145 GlobalVariable *NewGV = new GlobalVariable(Type::Int1Ty, false,
Zhou Sheng75b871f2007-01-11 12:24:14 +00001146 GlobalValue::InternalLinkage, ConstantInt::getFalse(),
Chris Lattner6ab03f62006-09-28 23:35:22 +00001147 GV->getName()+".b");
Chris Lattner40e4cec2004-12-12 05:53:50 +00001148 GV->getParent()->getGlobalList().insert(GV, NewGV);
1149
1150 Constant *InitVal = GV->getInitializer();
Reid Spencer542964f2007-01-11 18:21:29 +00001151 assert(InitVal->getType() != Type::Int1Ty && "No reason to shrink to bool!");
Chris Lattner40e4cec2004-12-12 05:53:50 +00001152
1153 // If initialized to zero and storing one into the global, we can use a cast
1154 // instead of a select to synthesize the desired value.
1155 bool IsOneZero = false;
1156 if (ConstantInt *CI = dyn_cast<ConstantInt>(OtherVal))
1157 IsOneZero = InitVal->isNullValue() && CI->equalsInt(1);
1158
1159 while (!GV->use_empty()) {
1160 Instruction *UI = cast<Instruction>(GV->use_back());
1161 if (StoreInst *SI = dyn_cast<StoreInst>(UI)) {
1162 // Change the store into a boolean store.
1163 bool StoringOther = SI->getOperand(0) == OtherVal;
1164 // Only do this if we weren't storing a loaded value.
Chris Lattner745196a2004-12-12 19:34:41 +00001165 Value *StoreVal;
Chris Lattner40e4cec2004-12-12 05:53:50 +00001166 if (StoringOther || SI->getOperand(0) == InitVal)
Reid Spencercddc9df2007-01-12 04:24:46 +00001167 StoreVal = ConstantInt::get(Type::Int1Ty, StoringOther);
Chris Lattner745196a2004-12-12 19:34:41 +00001168 else {
1169 // Otherwise, we are storing a previously loaded copy. To do this,
1170 // change the copy from copying the original value to just copying the
1171 // bool.
1172 Instruction *StoredVal = cast<Instruction>(SI->getOperand(0));
1173
1174 // If we're already replaced the input, StoredVal will be a cast or
1175 // select instruction. If not, it will be a load of the original
1176 // global.
1177 if (LoadInst *LI = dyn_cast<LoadInst>(StoredVal)) {
1178 assert(LI->getOperand(0) == GV && "Not a copy!");
1179 // Insert a new load, to preserve the saved value.
1180 StoreVal = new LoadInst(NewGV, LI->getName()+".b", LI);
1181 } else {
1182 assert((isa<CastInst>(StoredVal) || isa<SelectInst>(StoredVal)) &&
1183 "This is not a form that we understand!");
1184 StoreVal = StoredVal->getOperand(0);
1185 assert(isa<LoadInst>(StoreVal) && "Not a load of NewGV!");
1186 }
1187 }
1188 new StoreInst(StoreVal, NewGV, SI);
1189 } else if (!UI->use_empty()) {
Chris Lattner40e4cec2004-12-12 05:53:50 +00001190 // Change the load into a load of bool then a select.
1191 LoadInst *LI = cast<LoadInst>(UI);
Misha Brukmanb1c93172005-04-21 23:48:37 +00001192
Chris Lattner40e4cec2004-12-12 05:53:50 +00001193 std::string Name = LI->getName(); LI->setName("");
1194 LoadInst *NLI = new LoadInst(NewGV, Name+".b", LI);
1195 Value *NSI;
1196 if (IsOneZero)
Chris Lattnerc8978c52006-11-30 17:35:08 +00001197 NSI = new ZExtInst(NLI, LI->getType(), Name, LI);
Misha Brukmanb1c93172005-04-21 23:48:37 +00001198 else
Chris Lattner40e4cec2004-12-12 05:53:50 +00001199 NSI = new SelectInst(NLI, OtherVal, InitVal, Name, LI);
1200 LI->replaceAllUsesWith(NSI);
1201 }
1202 UI->eraseFromParent();
1203 }
1204
1205 GV->eraseFromParent();
1206}
1207
1208
Chris Lattner1c4bddc2004-10-08 20:59:28 +00001209/// ProcessInternalGlobal - Analyze the specified global variable and optimize
1210/// it if possible. If we make a change, return true.
Chris Lattner004e2502004-10-11 05:54:41 +00001211bool GlobalOpt::ProcessInternalGlobal(GlobalVariable *GV,
Chris Lattner531f9e92005-03-15 04:54:21 +00001212 Module::global_iterator &GVI) {
Chris Lattner1c4bddc2004-10-08 20:59:28 +00001213 std::set<PHINode*> PHIUsers;
1214 GlobalStatus GS;
Chris Lattner1c4bddc2004-10-08 20:59:28 +00001215 GV->removeDeadConstantUsers();
1216
1217 if (GV->use_empty()) {
Bill Wendling8f13b5c2006-11-26 10:02:32 +00001218 DOUT << "GLOBAL DEAD: " << *GV;
Chris Lattner8e71c6a2004-10-16 18:09:00 +00001219 GV->eraseFromParent();
Chris Lattner1c4bddc2004-10-08 20:59:28 +00001220 ++NumDeleted;
1221 return true;
1222 }
1223
1224 if (!AnalyzeGlobal(GV, GS, PHIUsers)) {
Chris Lattner80a01ef2006-09-30 19:40:30 +00001225#if 0
Bill Wendlingf3baad32006-12-07 01:30:32 +00001226 cerr << "Global: " << *GV;
1227 cerr << " isLoaded = " << GS.isLoaded << "\n";
1228 cerr << " StoredType = ";
Chris Lattner80a01ef2006-09-30 19:40:30 +00001229 switch (GS.StoredType) {
Bill Wendlingf3baad32006-12-07 01:30:32 +00001230 case GlobalStatus::NotStored: cerr << "NEVER STORED\n"; break;
1231 case GlobalStatus::isInitializerStored: cerr << "INIT STORED\n"; break;
1232 case GlobalStatus::isStoredOnce: cerr << "STORED ONCE\n"; break;
1233 case GlobalStatus::isStored: cerr << "stored\n"; break;
Chris Lattner80a01ef2006-09-30 19:40:30 +00001234 }
1235 if (GS.StoredType == GlobalStatus::isStoredOnce && GS.StoredOnceValue)
Bill Wendlingf3baad32006-12-07 01:30:32 +00001236 cerr << " StoredOnceValue = " << *GS.StoredOnceValue << "\n";
Chris Lattner80a01ef2006-09-30 19:40:30 +00001237 if (GS.AccessingFunction && !GS.HasMultipleAccessingFunctions)
Bill Wendlingf3baad32006-12-07 01:30:32 +00001238 cerr << " AccessingFunction = " << GS.AccessingFunction->getName()
Chris Lattner80a01ef2006-09-30 19:40:30 +00001239 << "\n";
Bill Wendlingf3baad32006-12-07 01:30:32 +00001240 cerr << " HasMultipleAccessingFunctions = "
Chris Lattner80a01ef2006-09-30 19:40:30 +00001241 << GS.HasMultipleAccessingFunctions << "\n";
Bill Wendlingf3baad32006-12-07 01:30:32 +00001242 cerr << " HasNonInstructionUser = " << GS.HasNonInstructionUser<<"\n";
1243 cerr << " isNotSuitableForSRA = " << GS.isNotSuitableForSRA << "\n";
1244 cerr << "\n";
Chris Lattner80a01ef2006-09-30 19:40:30 +00001245#endif
1246
Alkis Evlogimenosc4a44c62005-02-10 18:36:30 +00001247 // If this is a first class global and has only one accessing function
1248 // and this function is main (which we know is not recursive we can make
1249 // this global a local variable) we replace the global with a local alloca
1250 // in this function.
1251 //
1252 // NOTE: It doesn't make sense to promote non first class types since we
1253 // are just replacing static memory to stack memory.
1254 if (!GS.HasMultipleAccessingFunctions &&
Chris Lattner50bdfcb2005-06-15 21:11:48 +00001255 GS.AccessingFunction && !GS.HasNonInstructionUser &&
Alkis Evlogimenosc4a44c62005-02-10 18:36:30 +00001256 GV->getType()->getElementType()->isFirstClassType() &&
1257 GS.AccessingFunction->getName() == "main" &&
1258 GS.AccessingFunction->hasExternalLinkage()) {
Bill Wendling8f13b5c2006-11-26 10:02:32 +00001259 DOUT << "LOCALIZING GLOBAL: " << *GV;
Alkis Evlogimenosc4a44c62005-02-10 18:36:30 +00001260 Instruction* FirstI = GS.AccessingFunction->getEntryBlock().begin();
1261 const Type* ElemTy = GV->getType()->getElementType();
Nate Begeman848622f2005-11-05 09:21:28 +00001262 // FIXME: Pass Global's alignment when globals have alignment
Alkis Evlogimenosc4a44c62005-02-10 18:36:30 +00001263 AllocaInst* Alloca = new AllocaInst(ElemTy, NULL, GV->getName(), FirstI);
1264 if (!isa<UndefValue>(GV->getInitializer()))
1265 new StoreInst(GV->getInitializer(), Alloca, FirstI);
Misha Brukmanb1c93172005-04-21 23:48:37 +00001266
Alkis Evlogimenosc4a44c62005-02-10 18:36:30 +00001267 GV->replaceAllUsesWith(Alloca);
1268 GV->eraseFromParent();
1269 ++NumLocalized;
1270 return true;
1271 }
Chris Lattner80a01ef2006-09-30 19:40:30 +00001272
Chris Lattner1c4bddc2004-10-08 20:59:28 +00001273 // If the global is never loaded (but may be stored to), it is dead.
1274 // Delete it now.
1275 if (!GS.isLoaded) {
Bill Wendling8f13b5c2006-11-26 10:02:32 +00001276 DOUT << "GLOBAL NEVER LOADED: " << *GV;
Chris Lattnerf369b382004-10-09 03:32:52 +00001277
Chris Lattner1c4bddc2004-10-08 20:59:28 +00001278 // Delete any stores we can find to the global. We may not be able to
1279 // make it completely dead though.
Chris Lattnercb9f1522004-10-10 16:43:46 +00001280 bool Changed = CleanupConstantGlobalUsers(GV, GV->getInitializer());
Chris Lattnerf369b382004-10-09 03:32:52 +00001281
Chris Lattner1c4bddc2004-10-08 20:59:28 +00001282 // If the global is dead now, delete it.
1283 if (GV->use_empty()) {
Chris Lattner8e71c6a2004-10-16 18:09:00 +00001284 GV->eraseFromParent();
Chris Lattner1c4bddc2004-10-08 20:59:28 +00001285 ++NumDeleted;
Chris Lattnerf369b382004-10-09 03:32:52 +00001286 Changed = true;
Chris Lattner1c4bddc2004-10-08 20:59:28 +00001287 }
Chris Lattnerf369b382004-10-09 03:32:52 +00001288 return Changed;
Misha Brukmanb1c93172005-04-21 23:48:37 +00001289
Chris Lattner1c4bddc2004-10-08 20:59:28 +00001290 } else if (GS.StoredType <= GlobalStatus::isInitializerStored) {
Bill Wendling8f13b5c2006-11-26 10:02:32 +00001291 DOUT << "MARKING CONSTANT: " << *GV;
Chris Lattner1c4bddc2004-10-08 20:59:28 +00001292 GV->setConstant(true);
Misha Brukmanb1c93172005-04-21 23:48:37 +00001293
Chris Lattner1c4bddc2004-10-08 20:59:28 +00001294 // Clean up any obviously simplifiable users now.
1295 CleanupConstantGlobalUsers(GV, GV->getInitializer());
Misha Brukmanb1c93172005-04-21 23:48:37 +00001296
Chris Lattner1c4bddc2004-10-08 20:59:28 +00001297 // If the global is dead now, just nuke it.
1298 if (GV->use_empty()) {
Bill Wendling8f13b5c2006-11-26 10:02:32 +00001299 DOUT << " *** Marking constant allowed us to simplify "
1300 << "all users and delete global!\n";
Chris Lattner8e71c6a2004-10-16 18:09:00 +00001301 GV->eraseFromParent();
Chris Lattner1c4bddc2004-10-08 20:59:28 +00001302 ++NumDeleted;
1303 }
Misha Brukmanb1c93172005-04-21 23:48:37 +00001304
Chris Lattner1c4bddc2004-10-08 20:59:28 +00001305 ++NumMarked;
1306 return true;
1307 } else if (!GS.isNotSuitableForSRA &&
1308 !GV->getInitializer()->getType()->isFirstClassType()) {
Chris Lattner1c4bddc2004-10-08 20:59:28 +00001309 if (GlobalVariable *FirstNewGV = SRAGlobal(GV)) {
1310 GVI = FirstNewGV; // Don't skip the newly produced globals!
1311 return true;
1312 }
Chris Lattner09a52722004-10-09 21:48:45 +00001313 } else if (GS.StoredType == GlobalStatus::isStoredOnce) {
Chris Lattner40e4cec2004-12-12 05:53:50 +00001314 // If the initial value for the global was an undef value, and if only
1315 // one other value was stored into it, we can just change the
1316 // initializer to be an undef value, then delete all stores to the
1317 // global. This allows us to mark it constant.
1318 if (Constant *SOVConstant = dyn_cast<Constant>(GS.StoredOnceValue))
1319 if (isa<UndefValue>(GV->getInitializer())) {
1320 // Change the initial value here.
1321 GV->setInitializer(SOVConstant);
Misha Brukmanb1c93172005-04-21 23:48:37 +00001322
Chris Lattner40e4cec2004-12-12 05:53:50 +00001323 // Clean up any obviously simplifiable users now.
1324 CleanupConstantGlobalUsers(GV, GV->getInitializer());
Misha Brukmanb1c93172005-04-21 23:48:37 +00001325
Chris Lattner40e4cec2004-12-12 05:53:50 +00001326 if (GV->use_empty()) {
Bill Wendling8f13b5c2006-11-26 10:02:32 +00001327 DOUT << " *** Substituting initializer allowed us to "
1328 << "simplify all users and delete global!\n";
Chris Lattner40e4cec2004-12-12 05:53:50 +00001329 GV->eraseFromParent();
1330 ++NumDeleted;
1331 } else {
1332 GVI = GV;
1333 }
1334 ++NumSubstitute;
1335 return true;
Chris Lattner8e71c6a2004-10-16 18:09:00 +00001336 }
Chris Lattner8e71c6a2004-10-16 18:09:00 +00001337
Chris Lattner09a52722004-10-09 21:48:45 +00001338 // Try to optimize globals based on the knowledge that only one value
1339 // (besides its initializer) is ever stored to the global.
Chris Lattner004e2502004-10-11 05:54:41 +00001340 if (OptimizeOnceStoredGlobal(GV, GS.StoredOnceValue, GVI,
1341 getAnalysis<TargetData>()))
Chris Lattner09a52722004-10-09 21:48:45 +00001342 return true;
Chris Lattner40e4cec2004-12-12 05:53:50 +00001343
1344 // Otherwise, if the global was not a boolean, we can shrink it to be a
1345 // boolean.
1346 if (Constant *SOVConstant = dyn_cast<Constant>(GS.StoredOnceValue))
Reid Spencer542964f2007-01-11 18:21:29 +00001347 if (GV->getType()->getElementType() != Type::Int1Ty &&
Chris Lattner5a0bd612006-11-01 18:03:33 +00001348 !GV->getType()->getElementType()->isFloatingPoint() &&
Reid Spencer2eadb532007-01-21 00:29:26 +00001349 !isa<PackedType>(GV->getType()->getElementType()) &&
Chris Lattner5a0bd612006-11-01 18:03:33 +00001350 !GS.HasPHIUser) {
Bill Wendling8f13b5c2006-11-26 10:02:32 +00001351 DOUT << " *** SHRINKING TO BOOL: " << *GV;
Chris Lattner40e4cec2004-12-12 05:53:50 +00001352 ShrinkGlobalToBoolean(GV, SOVConstant);
1353 ++NumShrunkToBool;
1354 return true;
1355 }
Chris Lattner1c4bddc2004-10-08 20:59:28 +00001356 }
1357 }
1358 return false;
1359}
1360
Chris Lattnera4c80222005-05-08 22:18:06 +00001361/// OnlyCalledDirectly - Return true if the specified function is only called
1362/// directly. In other words, its address is never taken.
1363static bool OnlyCalledDirectly(Function *F) {
1364 for (Value::use_iterator UI = F->use_begin(), E = F->use_end(); UI != E;++UI){
1365 Instruction *User = dyn_cast<Instruction>(*UI);
1366 if (!User) return false;
1367 if (!isa<CallInst>(User) && !isa<InvokeInst>(User)) return false;
1368
1369 // See if the function address is passed as an argument.
1370 for (unsigned i = 1, e = User->getNumOperands(); i != e; ++i)
1371 if (User->getOperand(i) == F) return false;
1372 }
1373 return true;
1374}
1375
1376/// ChangeCalleesToFastCall - Walk all of the direct calls of the specified
1377/// function, changing them to FastCC.
1378static void ChangeCalleesToFastCall(Function *F) {
1379 for (Value::use_iterator UI = F->use_begin(), E = F->use_end(); UI != E;++UI){
1380 Instruction *User = cast<Instruction>(*UI);
1381 if (CallInst *CI = dyn_cast<CallInst>(User))
1382 CI->setCallingConv(CallingConv::Fast);
1383 else
1384 cast<InvokeInst>(User)->setCallingConv(CallingConv::Fast);
1385 }
1386}
Chris Lattner1c4bddc2004-10-08 20:59:28 +00001387
Chris Lattner41b6a5a2005-09-26 01:43:45 +00001388bool GlobalOpt::OptimizeFunctions(Module &M) {
1389 bool Changed = false;
1390 // Optimize functions.
1391 for (Module::iterator FI = M.begin(), E = M.end(); FI != E; ) {
1392 Function *F = FI++;
1393 F->removeDeadConstantUsers();
1394 if (F->use_empty() && (F->hasInternalLinkage() ||
1395 F->hasLinkOnceLinkage())) {
1396 M.getFunctionList().erase(F);
1397 Changed = true;
1398 ++NumFnDeleted;
1399 } else if (F->hasInternalLinkage() &&
1400 F->getCallingConv() == CallingConv::C && !F->isVarArg() &&
1401 OnlyCalledDirectly(F)) {
1402 // If this function has C calling conventions, is not a varargs
1403 // function, and is only called directly, promote it to use the Fast
1404 // calling convention.
1405 F->setCallingConv(CallingConv::Fast);
1406 ChangeCalleesToFastCall(F);
1407 ++NumFastCallFns;
1408 Changed = true;
1409 }
1410 }
1411 return Changed;
1412}
1413
1414bool GlobalOpt::OptimizeGlobalVars(Module &M) {
1415 bool Changed = false;
1416 for (Module::global_iterator GVI = M.global_begin(), E = M.global_end();
1417 GVI != E; ) {
1418 GlobalVariable *GV = GVI++;
1419 if (!GV->isConstant() && GV->hasInternalLinkage() &&
1420 GV->hasInitializer())
1421 Changed |= ProcessInternalGlobal(GV, GVI);
1422 }
1423 return Changed;
1424}
1425
1426/// FindGlobalCtors - Find the llvm.globalctors list, verifying that all
1427/// initializers have an init priority of 65535.
1428GlobalVariable *GlobalOpt::FindGlobalCtors(Module &M) {
Alkis Evlogimenoscb67b652005-10-25 11:18:06 +00001429 for (Module::global_iterator I = M.global_begin(), E = M.global_end();
1430 I != E; ++I)
Chris Lattner41b6a5a2005-09-26 01:43:45 +00001431 if (I->getName() == "llvm.global_ctors") {
1432 // Found it, verify it's an array of { int, void()* }.
1433 const ArrayType *ATy =dyn_cast<ArrayType>(I->getType()->getElementType());
1434 if (!ATy) return 0;
1435 const StructType *STy = dyn_cast<StructType>(ATy->getElementType());
1436 if (!STy || STy->getNumElements() != 2 ||
Reid Spencerc635f472006-12-31 05:48:39 +00001437 STy->getElementType(0) != Type::Int32Ty) return 0;
Chris Lattner41b6a5a2005-09-26 01:43:45 +00001438 const PointerType *PFTy = dyn_cast<PointerType>(STy->getElementType(1));
1439 if (!PFTy) return 0;
1440 const FunctionType *FTy = dyn_cast<FunctionType>(PFTy->getElementType());
1441 if (!FTy || FTy->getReturnType() != Type::VoidTy || FTy->isVarArg() ||
1442 FTy->getNumParams() != 0)
1443 return 0;
1444
1445 // Verify that the initializer is simple enough for us to handle.
1446 if (!I->hasInitializer()) return 0;
1447 ConstantArray *CA = dyn_cast<ConstantArray>(I->getInitializer());
1448 if (!CA) return 0;
1449 for (unsigned i = 0, e = CA->getNumOperands(); i != e; ++i)
1450 if (ConstantStruct *CS = dyn_cast<ConstantStruct>(CA->getOperand(i))) {
Chris Lattner838bdc12005-09-26 02:19:27 +00001451 if (isa<ConstantPointerNull>(CS->getOperand(1)))
1452 continue;
1453
1454 // Must have a function or null ptr.
1455 if (!isa<Function>(CS->getOperand(1)))
1456 return 0;
1457
Chris Lattner41b6a5a2005-09-26 01:43:45 +00001458 // Init priority must be standard.
1459 ConstantInt *CI = dyn_cast<ConstantInt>(CS->getOperand(0));
Reid Spencere0fc4df2006-10-20 07:07:24 +00001460 if (!CI || CI->getZExtValue() != 65535)
Chris Lattner41b6a5a2005-09-26 01:43:45 +00001461 return 0;
Chris Lattner41b6a5a2005-09-26 01:43:45 +00001462 } else {
1463 return 0;
1464 }
1465
1466 return I;
1467 }
1468 return 0;
1469}
1470
Chris Lattner696beef2005-09-26 02:31:18 +00001471/// ParseGlobalCtors - Given a llvm.global_ctors list that we can understand,
1472/// return a list of the functions and null terminator as a vector.
Chris Lattner41b6a5a2005-09-26 01:43:45 +00001473static std::vector<Function*> ParseGlobalCtors(GlobalVariable *GV) {
1474 ConstantArray *CA = cast<ConstantArray>(GV->getInitializer());
1475 std::vector<Function*> Result;
1476 Result.reserve(CA->getNumOperands());
1477 for (unsigned i = 0, e = CA->getNumOperands(); i != e; ++i) {
1478 ConstantStruct *CS = cast<ConstantStruct>(CA->getOperand(i));
1479 Result.push_back(dyn_cast<Function>(CS->getOperand(1)));
1480 }
1481 return Result;
1482}
1483
Chris Lattner696beef2005-09-26 02:31:18 +00001484/// InstallGlobalCtors - Given a specified llvm.global_ctors list, install the
1485/// specified array, returning the new global to use.
1486static GlobalVariable *InstallGlobalCtors(GlobalVariable *GCL,
1487 const std::vector<Function*> &Ctors) {
1488 // If we made a change, reassemble the initializer list.
1489 std::vector<Constant*> CSVals;
Reid Spencerc635f472006-12-31 05:48:39 +00001490 CSVals.push_back(ConstantInt::get(Type::Int32Ty, 65535));
Chris Lattner696beef2005-09-26 02:31:18 +00001491 CSVals.push_back(0);
1492
1493 // Create the new init list.
1494 std::vector<Constant*> CAList;
1495 for (unsigned i = 0, e = Ctors.size(); i != e; ++i) {
Chris Lattner99e23fa2005-09-26 04:44:35 +00001496 if (Ctors[i]) {
Chris Lattner696beef2005-09-26 02:31:18 +00001497 CSVals[1] = Ctors[i];
Chris Lattner99e23fa2005-09-26 04:44:35 +00001498 } else {
Chris Lattner696beef2005-09-26 02:31:18 +00001499 const Type *FTy = FunctionType::get(Type::VoidTy,
1500 std::vector<const Type*>(), false);
1501 const PointerType *PFTy = PointerType::get(FTy);
1502 CSVals[1] = Constant::getNullValue(PFTy);
Reid Spencerc635f472006-12-31 05:48:39 +00001503 CSVals[0] = ConstantInt::get(Type::Int32Ty, 2147483647);
Chris Lattner696beef2005-09-26 02:31:18 +00001504 }
1505 CAList.push_back(ConstantStruct::get(CSVals));
1506 }
1507
1508 // Create the array initializer.
1509 const Type *StructTy =
1510 cast<ArrayType>(GCL->getType()->getElementType())->getElementType();
1511 Constant *CA = ConstantArray::get(ArrayType::get(StructTy, CAList.size()),
1512 CAList);
1513
1514 // If we didn't change the number of elements, don't create a new GV.
1515 if (CA->getType() == GCL->getInitializer()->getType()) {
1516 GCL->setInitializer(CA);
1517 return GCL;
1518 }
1519
1520 // Create the new global and insert it next to the existing list.
1521 GlobalVariable *NGV = new GlobalVariable(CA->getType(), GCL->isConstant(),
1522 GCL->getLinkage(), CA,
1523 GCL->getName());
1524 GCL->setName("");
1525 GCL->getParent()->getGlobalList().insert(GCL, NGV);
1526
1527 // Nuke the old list, replacing any uses with the new one.
1528 if (!GCL->use_empty()) {
1529 Constant *V = NGV;
1530 if (V->getType() != GCL->getType())
Reid Spencerbb65ebf2006-12-12 23:36:14 +00001531 V = ConstantExpr::getBitCast(V, GCL->getType());
Chris Lattner696beef2005-09-26 02:31:18 +00001532 GCL->replaceAllUsesWith(V);
1533 }
1534 GCL->eraseFromParent();
1535
1536 if (Ctors.size())
1537 return NGV;
1538 else
1539 return 0;
1540}
Chris Lattner99e23fa2005-09-26 04:44:35 +00001541
1542
1543static Constant *getVal(std::map<Value*, Constant*> &ComputedValues,
1544 Value *V) {
1545 if (Constant *CV = dyn_cast<Constant>(V)) return CV;
1546 Constant *R = ComputedValues[V];
1547 assert(R && "Reference to an uncomputed value!");
1548 return R;
1549}
1550
1551/// isSimpleEnoughPointerToCommit - Return true if this constant is simple
1552/// enough for us to understand. In particular, if it is a cast of something,
1553/// we punt. We basically just support direct accesses to globals and GEP's of
1554/// globals. This should be kept up to date with CommitValueTo.
1555static bool isSimpleEnoughPointerToCommit(Constant *C) {
Chris Lattner29b27802005-09-27 04:50:03 +00001556 if (GlobalVariable *GV = dyn_cast<GlobalVariable>(C)) {
1557 if (!GV->hasExternalLinkage() && !GV->hasInternalLinkage())
Anton Korobeynikovd61d39e2006-09-14 18:23:27 +00001558 return false; // do not allow weak/linkonce/dllimport/dllexport linkage.
Reid Spencer5301e7c2007-01-30 20:08:39 +00001559 return !GV->isDeclaration(); // reject external globals.
Chris Lattner29b27802005-09-27 04:50:03 +00001560 }
Chris Lattner46af55e2005-09-26 06:52:44 +00001561 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(C))
1562 // Handle a constantexpr gep.
1563 if (CE->getOpcode() == Instruction::GetElementPtr &&
1564 isa<GlobalVariable>(CE->getOperand(0))) {
1565 GlobalVariable *GV = cast<GlobalVariable>(CE->getOperand(0));
Chris Lattner29b27802005-09-27 04:50:03 +00001566 if (!GV->hasExternalLinkage() && !GV->hasInternalLinkage())
Anton Korobeynikovd61d39e2006-09-14 18:23:27 +00001567 return false; // do not allow weak/linkonce/dllimport/dllexport linkage.
Chris Lattner46af55e2005-09-26 06:52:44 +00001568 return GV->hasInitializer() &&
1569 ConstantFoldLoadThroughGEPConstantExpr(GV->getInitializer(), CE);
1570 }
Chris Lattner99e23fa2005-09-26 04:44:35 +00001571 return false;
1572}
1573
Chris Lattner46af55e2005-09-26 06:52:44 +00001574/// EvaluateStoreInto - Evaluate a piece of a constantexpr store into a global
1575/// initializer. This returns 'Init' modified to reflect 'Val' stored into it.
1576/// At this point, the GEP operands of Addr [0, OpNo) have been stepped into.
1577static Constant *EvaluateStoreInto(Constant *Init, Constant *Val,
1578 ConstantExpr *Addr, unsigned OpNo) {
1579 // Base case of the recursion.
1580 if (OpNo == Addr->getNumOperands()) {
1581 assert(Val->getType() == Init->getType() && "Type mismatch!");
1582 return Val;
1583 }
1584
1585 if (const StructType *STy = dyn_cast<StructType>(Init->getType())) {
1586 std::vector<Constant*> Elts;
1587
1588 // Break up the constant into its elements.
1589 if (ConstantStruct *CS = dyn_cast<ConstantStruct>(Init)) {
1590 for (unsigned i = 0, e = CS->getNumOperands(); i != e; ++i)
1591 Elts.push_back(CS->getOperand(i));
1592 } else if (isa<ConstantAggregateZero>(Init)) {
1593 for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i)
1594 Elts.push_back(Constant::getNullValue(STy->getElementType(i)));
1595 } else if (isa<UndefValue>(Init)) {
1596 for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i)
1597 Elts.push_back(UndefValue::get(STy->getElementType(i)));
1598 } else {
1599 assert(0 && "This code is out of sync with "
1600 " ConstantFoldLoadThroughGEPConstantExpr");
1601 }
1602
1603 // Replace the element that we are supposed to.
Reid Spencere0fc4df2006-10-20 07:07:24 +00001604 ConstantInt *CU = cast<ConstantInt>(Addr->getOperand(OpNo));
1605 unsigned Idx = CU->getZExtValue();
1606 assert(Idx < STy->getNumElements() && "Struct index out of range!");
Chris Lattner46af55e2005-09-26 06:52:44 +00001607 Elts[Idx] = EvaluateStoreInto(Elts[Idx], Val, Addr, OpNo+1);
1608
1609 // Return the modified struct.
1610 return ConstantStruct::get(Elts);
1611 } else {
1612 ConstantInt *CI = cast<ConstantInt>(Addr->getOperand(OpNo));
1613 const ArrayType *ATy = cast<ArrayType>(Init->getType());
1614
1615 // Break up the array into elements.
1616 std::vector<Constant*> Elts;
1617 if (ConstantArray *CA = dyn_cast<ConstantArray>(Init)) {
1618 for (unsigned i = 0, e = CA->getNumOperands(); i != e; ++i)
1619 Elts.push_back(CA->getOperand(i));
1620 } else if (isa<ConstantAggregateZero>(Init)) {
1621 Constant *Elt = Constant::getNullValue(ATy->getElementType());
1622 Elts.assign(ATy->getNumElements(), Elt);
1623 } else if (isa<UndefValue>(Init)) {
1624 Constant *Elt = UndefValue::get(ATy->getElementType());
1625 Elts.assign(ATy->getNumElements(), Elt);
1626 } else {
1627 assert(0 && "This code is out of sync with "
1628 " ConstantFoldLoadThroughGEPConstantExpr");
1629 }
1630
Reid Spencere0fc4df2006-10-20 07:07:24 +00001631 assert(CI->getZExtValue() < ATy->getNumElements());
1632 Elts[CI->getZExtValue()] =
1633 EvaluateStoreInto(Elts[CI->getZExtValue()], Val, Addr, OpNo+1);
Chris Lattner46af55e2005-09-26 06:52:44 +00001634 return ConstantArray::get(ATy, Elts);
1635 }
1636}
1637
Chris Lattner99e23fa2005-09-26 04:44:35 +00001638/// CommitValueTo - We have decided that Addr (which satisfies the predicate
1639/// isSimpleEnoughPointerToCommit) should get Val as its value. Make it happen.
1640static void CommitValueTo(Constant *Val, Constant *Addr) {
Chris Lattner46af55e2005-09-26 06:52:44 +00001641 if (GlobalVariable *GV = dyn_cast<GlobalVariable>(Addr)) {
1642 assert(GV->hasInitializer());
1643 GV->setInitializer(Val);
1644 return;
1645 }
1646
1647 ConstantExpr *CE = cast<ConstantExpr>(Addr);
1648 GlobalVariable *GV = cast<GlobalVariable>(CE->getOperand(0));
1649
1650 Constant *Init = GV->getInitializer();
1651 Init = EvaluateStoreInto(Init, Val, CE, 2);
1652 GV->setInitializer(Init);
Chris Lattner99e23fa2005-09-26 04:44:35 +00001653}
1654
Chris Lattnerb0096632005-09-26 05:16:34 +00001655/// ComputeLoadResult - Return the value that would be computed by a load from
1656/// P after the stores reflected by 'memory' have been performed. If we can't
1657/// decide, return null.
Chris Lattner4b05c322005-09-26 05:15:37 +00001658static Constant *ComputeLoadResult(Constant *P,
1659 const std::map<Constant*, Constant*> &Memory) {
1660 // If this memory location has been recently stored, use the stored value: it
1661 // is the most up-to-date.
1662 std::map<Constant*, Constant*>::const_iterator I = Memory.find(P);
1663 if (I != Memory.end()) return I->second;
1664
1665 // Access it.
1666 if (GlobalVariable *GV = dyn_cast<GlobalVariable>(P)) {
1667 if (GV->hasInitializer())
1668 return GV->getInitializer();
1669 return 0;
Chris Lattner4b05c322005-09-26 05:15:37 +00001670 }
Chris Lattner46af55e2005-09-26 06:52:44 +00001671
1672 // Handle a constantexpr getelementptr.
1673 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(P))
1674 if (CE->getOpcode() == Instruction::GetElementPtr &&
1675 isa<GlobalVariable>(CE->getOperand(0))) {
1676 GlobalVariable *GV = cast<GlobalVariable>(CE->getOperand(0));
1677 if (GV->hasInitializer())
1678 return ConstantFoldLoadThroughGEPConstantExpr(GV->getInitializer(), CE);
1679 }
1680
1681 return 0; // don't know how to evaluate.
Chris Lattner4b05c322005-09-26 05:15:37 +00001682}
1683
Chris Lattnerda1889b2005-09-27 04:27:01 +00001684/// EvaluateFunction - Evaluate a call to function F, returning true if
1685/// successful, false if we can't evaluate it. ActualArgs contains the formal
1686/// arguments for the function.
Chris Lattner65a3a092005-09-27 04:45:34 +00001687static bool EvaluateFunction(Function *F, Constant *&RetVal,
Chris Lattnerda1889b2005-09-27 04:27:01 +00001688 const std::vector<Constant*> &ActualArgs,
1689 std::vector<Function*> &CallStack,
1690 std::map<Constant*, Constant*> &MutatedMemory,
1691 std::vector<GlobalVariable*> &AllocaTmps) {
Chris Lattner65a3a092005-09-27 04:45:34 +00001692 // Check to see if this function is already executing (recursion). If so,
1693 // bail out. TODO: we might want to accept limited recursion.
1694 if (std::find(CallStack.begin(), CallStack.end(), F) != CallStack.end())
1695 return false;
1696
1697 CallStack.push_back(F);
1698
Chris Lattner99e23fa2005-09-26 04:44:35 +00001699 /// Values - As we compute SSA register values, we store their contents here.
1700 std::map<Value*, Constant*> Values;
Chris Lattner65a3a092005-09-27 04:45:34 +00001701
1702 // Initialize arguments to the incoming values specified.
1703 unsigned ArgNo = 0;
1704 for (Function::arg_iterator AI = F->arg_begin(), E = F->arg_end(); AI != E;
1705 ++AI, ++ArgNo)
1706 Values[AI] = ActualArgs[ArgNo];
Chris Lattnerda1889b2005-09-27 04:27:01 +00001707
Chris Lattner3e9ea5f2005-09-26 04:57:38 +00001708 /// ExecutedBlocks - We only handle non-looping, non-recursive code. As such,
1709 /// we can only evaluate any one basic block at most once. This set keeps
1710 /// track of what we have executed so we can detect recursive cases etc.
1711 std::set<BasicBlock*> ExecutedBlocks;
Chris Lattner6bf2cd52005-09-26 17:07:09 +00001712
Chris Lattner99e23fa2005-09-26 04:44:35 +00001713 // CurInst - The current instruction we're evaluating.
1714 BasicBlock::iterator CurInst = F->begin()->begin();
1715
1716 // This is the main evaluation loop.
1717 while (1) {
1718 Constant *InstResult = 0;
1719
1720 if (StoreInst *SI = dyn_cast<StoreInst>(CurInst)) {
Chris Lattner65a3a092005-09-27 04:45:34 +00001721 if (SI->isVolatile()) return false; // no volatile accesses.
Chris Lattner99e23fa2005-09-26 04:44:35 +00001722 Constant *Ptr = getVal(Values, SI->getOperand(1));
1723 if (!isSimpleEnoughPointerToCommit(Ptr))
1724 // If this is too complex for us to commit, reject it.
Chris Lattner65a3a092005-09-27 04:45:34 +00001725 return false;
Chris Lattner99e23fa2005-09-26 04:44:35 +00001726 Constant *Val = getVal(Values, SI->getOperand(0));
1727 MutatedMemory[Ptr] = Val;
1728 } else if (BinaryOperator *BO = dyn_cast<BinaryOperator>(CurInst)) {
1729 InstResult = ConstantExpr::get(BO->getOpcode(),
1730 getVal(Values, BO->getOperand(0)),
1731 getVal(Values, BO->getOperand(1)));
Reid Spencer266e42b2006-12-23 06:05:41 +00001732 } else if (CmpInst *CI = dyn_cast<CmpInst>(CurInst)) {
1733 InstResult = ConstantExpr::getCompare(CI->getPredicate(),
1734 getVal(Values, CI->getOperand(0)),
1735 getVal(Values, CI->getOperand(1)));
Chris Lattner99e23fa2005-09-26 04:44:35 +00001736 } else if (CastInst *CI = dyn_cast<CastInst>(CurInst)) {
Chris Lattner0390b9e2006-11-30 17:26:08 +00001737 InstResult = ConstantExpr::getCast(CI->getOpcode(),
1738 getVal(Values, CI->getOperand(0)),
Chris Lattner99e23fa2005-09-26 04:44:35 +00001739 CI->getType());
1740 } else if (SelectInst *SI = dyn_cast<SelectInst>(CurInst)) {
1741 InstResult = ConstantExpr::getSelect(getVal(Values, SI->getOperand(0)),
1742 getVal(Values, SI->getOperand(1)),
1743 getVal(Values, SI->getOperand(2)));
Chris Lattner4b05c322005-09-26 05:15:37 +00001744 } else if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(CurInst)) {
1745 Constant *P = getVal(Values, GEP->getOperand(0));
Chris Lattnerf96f4a82007-01-31 04:40:53 +00001746 SmallVector<Constant*, 8> GEPOps;
Chris Lattner4b05c322005-09-26 05:15:37 +00001747 for (unsigned i = 1, e = GEP->getNumOperands(); i != e; ++i)
1748 GEPOps.push_back(getVal(Values, GEP->getOperand(i)));
Chris Lattnerf96f4a82007-01-31 04:40:53 +00001749 InstResult = ConstantExpr::getGetElementPtr(P, &GEPOps[0], GEPOps.size());
Chris Lattner4b05c322005-09-26 05:15:37 +00001750 } else if (LoadInst *LI = dyn_cast<LoadInst>(CurInst)) {
Chris Lattner65a3a092005-09-27 04:45:34 +00001751 if (LI->isVolatile()) return false; // no volatile accesses.
Chris Lattner4b05c322005-09-26 05:15:37 +00001752 InstResult = ComputeLoadResult(getVal(Values, LI->getOperand(0)),
1753 MutatedMemory);
Chris Lattner65a3a092005-09-27 04:45:34 +00001754 if (InstResult == 0) return false; // Could not evaluate load.
Chris Lattner6bf2cd52005-09-26 17:07:09 +00001755 } else if (AllocaInst *AI = dyn_cast<AllocaInst>(CurInst)) {
Chris Lattner65a3a092005-09-27 04:45:34 +00001756 if (AI->isArrayAllocation()) return false; // Cannot handle array allocs.
Chris Lattner6bf2cd52005-09-26 17:07:09 +00001757 const Type *Ty = AI->getType()->getElementType();
1758 AllocaTmps.push_back(new GlobalVariable(Ty, false,
1759 GlobalValue::InternalLinkage,
1760 UndefValue::get(Ty),
1761 AI->getName()));
Chris Lattner65a3a092005-09-27 04:45:34 +00001762 InstResult = AllocaTmps.back();
1763 } else if (CallInst *CI = dyn_cast<CallInst>(CurInst)) {
Chris Lattnerfd2e13b2006-07-07 21:37:01 +00001764 // Cannot handle inline asm.
1765 if (isa<InlineAsm>(CI->getOperand(0))) return false;
1766
Chris Lattner65a3a092005-09-27 04:45:34 +00001767 // Resolve function pointers.
1768 Function *Callee = dyn_cast<Function>(getVal(Values, CI->getOperand(0)));
1769 if (!Callee) return false; // Cannot resolve.
Chris Lattner3d27e7f2005-09-27 05:02:43 +00001770
Chris Lattner65a3a092005-09-27 04:45:34 +00001771 std::vector<Constant*> Formals;
1772 for (unsigned i = 1, e = CI->getNumOperands(); i != e; ++i)
1773 Formals.push_back(getVal(Values, CI->getOperand(i)));
Chris Lattner65a3a092005-09-27 04:45:34 +00001774
Reid Spencer5301e7c2007-01-30 20:08:39 +00001775 if (Callee->isDeclaration()) {
Chris Lattner3d27e7f2005-09-27 05:02:43 +00001776 // If this is a function we can constant fold, do it.
Chris Lattner6fc4b462007-01-30 23:14:52 +00001777 if (Constant *C = ConstantFoldCall(Callee, &Formals[0],
1778 Formals.size())) {
Chris Lattner3d27e7f2005-09-27 05:02:43 +00001779 InstResult = C;
1780 } else {
1781 return false;
1782 }
1783 } else {
1784 if (Callee->getFunctionType()->isVarArg())
1785 return false;
1786
1787 Constant *RetVal;
1788
1789 // Execute the call, if successful, use the return value.
1790 if (!EvaluateFunction(Callee, RetVal, Formals, CallStack,
1791 MutatedMemory, AllocaTmps))
1792 return false;
1793 InstResult = RetVal;
1794 }
Reid Spencerde46e482006-11-02 20:25:50 +00001795 } else if (isa<TerminatorInst>(CurInst)) {
Chris Lattner3e9ea5f2005-09-26 04:57:38 +00001796 BasicBlock *NewBB = 0;
1797 if (BranchInst *BI = dyn_cast<BranchInst>(CurInst)) {
1798 if (BI->isUnconditional()) {
1799 NewBB = BI->getSuccessor(0);
1800 } else {
Zhou Sheng75b871f2007-01-11 12:24:14 +00001801 ConstantInt *Cond =
1802 dyn_cast<ConstantInt>(getVal(Values, BI->getCondition()));
Chris Lattner15649082007-01-12 18:30:11 +00001803 if (!Cond) return false; // Cannot determine.
Zhou Sheng75b871f2007-01-11 12:24:14 +00001804
Reid Spencercddc9df2007-01-12 04:24:46 +00001805 NewBB = BI->getSuccessor(!Cond->getZExtValue());
Chris Lattner3e9ea5f2005-09-26 04:57:38 +00001806 }
1807 } else if (SwitchInst *SI = dyn_cast<SwitchInst>(CurInst)) {
1808 ConstantInt *Val =
1809 dyn_cast<ConstantInt>(getVal(Values, SI->getCondition()));
Chris Lattner65a3a092005-09-27 04:45:34 +00001810 if (!Val) return false; // Cannot determine.
Chris Lattner3e9ea5f2005-09-26 04:57:38 +00001811 NewBB = SI->getSuccessor(SI->findCaseValue(Val));
1812 } else if (ReturnInst *RI = dyn_cast<ReturnInst>(CurInst)) {
Chris Lattner65a3a092005-09-27 04:45:34 +00001813 if (RI->getNumOperands())
1814 RetVal = getVal(Values, RI->getOperand(0));
1815
1816 CallStack.pop_back(); // return from fn.
Chris Lattnerda1889b2005-09-27 04:27:01 +00001817 return true; // We succeeded at evaluating this ctor!
Chris Lattner3e9ea5f2005-09-26 04:57:38 +00001818 } else {
Chris Lattner65a3a092005-09-27 04:45:34 +00001819 // invoke, unwind, unreachable.
1820 return false; // Cannot handle this terminator.
Chris Lattner3e9ea5f2005-09-26 04:57:38 +00001821 }
1822
1823 // Okay, we succeeded in evaluating this control flow. See if we have
Chris Lattner65a3a092005-09-27 04:45:34 +00001824 // executed the new block before. If so, we have a looping function,
1825 // which we cannot evaluate in reasonable time.
Chris Lattner3e9ea5f2005-09-26 04:57:38 +00001826 if (!ExecutedBlocks.insert(NewBB).second)
Chris Lattner65a3a092005-09-27 04:45:34 +00001827 return false; // looped!
Chris Lattner3e9ea5f2005-09-26 04:57:38 +00001828
1829 // Okay, we have never been in this block before. Check to see if there
1830 // are any PHI nodes. If so, evaluate them with information about where
1831 // we came from.
1832 BasicBlock *OldBB = CurInst->getParent();
1833 CurInst = NewBB->begin();
1834 PHINode *PN;
1835 for (; (PN = dyn_cast<PHINode>(CurInst)); ++CurInst)
1836 Values[PN] = getVal(Values, PN->getIncomingValueForBlock(OldBB));
1837
1838 // Do NOT increment CurInst. We know that the terminator had no value.
1839 continue;
Chris Lattner99e23fa2005-09-26 04:44:35 +00001840 } else {
Chris Lattner99e23fa2005-09-26 04:44:35 +00001841 // Did not know how to evaluate this!
Chris Lattner65a3a092005-09-27 04:45:34 +00001842 return false;
Chris Lattner99e23fa2005-09-26 04:44:35 +00001843 }
1844
1845 if (!CurInst->use_empty())
1846 Values[CurInst] = InstResult;
1847
1848 // Advance program counter.
1849 ++CurInst;
1850 }
Chris Lattnerda1889b2005-09-27 04:27:01 +00001851}
1852
1853/// EvaluateStaticConstructor - Evaluate static constructors in the function, if
1854/// we can. Return true if we can, false otherwise.
1855static bool EvaluateStaticConstructor(Function *F) {
1856 /// MutatedMemory - For each store we execute, we update this map. Loads
1857 /// check this to get the most up-to-date value. If evaluation is successful,
1858 /// this state is committed to the process.
1859 std::map<Constant*, Constant*> MutatedMemory;
1860
1861 /// AllocaTmps - To 'execute' an alloca, we create a temporary global variable
1862 /// to represent its body. This vector is needed so we can delete the
1863 /// temporary globals when we are done.
1864 std::vector<GlobalVariable*> AllocaTmps;
1865
1866 /// CallStack - This is used to detect recursion. In pathological situations
1867 /// we could hit exponential behavior, but at least there is nothing
1868 /// unbounded.
1869 std::vector<Function*> CallStack;
1870
1871 // Call the function.
Chris Lattner65a3a092005-09-27 04:45:34 +00001872 Constant *RetValDummy;
1873 bool EvalSuccess = EvaluateFunction(F, RetValDummy, std::vector<Constant*>(),
1874 CallStack, MutatedMemory, AllocaTmps);
Chris Lattnerda1889b2005-09-27 04:27:01 +00001875 if (EvalSuccess) {
Chris Lattner6bf2cd52005-09-26 17:07:09 +00001876 // We succeeded at evaluation: commit the result.
Bill Wendling8f13b5c2006-11-26 10:02:32 +00001877 DOUT << "FULLY EVALUATED GLOBAL CTOR FUNCTION '"
1878 << F->getName() << "' to " << MutatedMemory.size()
1879 << " stores.\n";
Chris Lattner6bf2cd52005-09-26 17:07:09 +00001880 for (std::map<Constant*, Constant*>::iterator I = MutatedMemory.begin(),
1881 E = MutatedMemory.end(); I != E; ++I)
1882 CommitValueTo(I->second, I->first);
1883 }
Chris Lattner99e23fa2005-09-26 04:44:35 +00001884
Chris Lattner6bf2cd52005-09-26 17:07:09 +00001885 // At this point, we are done interpreting. If we created any 'alloca'
1886 // temporaries, release them now.
1887 while (!AllocaTmps.empty()) {
1888 GlobalVariable *Tmp = AllocaTmps.back();
1889 AllocaTmps.pop_back();
Chris Lattnerda1889b2005-09-27 04:27:01 +00001890
Chris Lattner6bf2cd52005-09-26 17:07:09 +00001891 // If there are still users of the alloca, the program is doing something
1892 // silly, e.g. storing the address of the alloca somewhere and using it
1893 // later. Since this is undefined, we'll just make it be null.
1894 if (!Tmp->use_empty())
1895 Tmp->replaceAllUsesWith(Constant::getNullValue(Tmp->getType()));
1896 delete Tmp;
1897 }
Chris Lattner46d9ff082005-09-26 07:34:35 +00001898
Chris Lattnerda1889b2005-09-27 04:27:01 +00001899 return EvalSuccess;
Chris Lattner99e23fa2005-09-26 04:44:35 +00001900}
1901
Chris Lattner696beef2005-09-26 02:31:18 +00001902
Chris Lattnerda1889b2005-09-27 04:27:01 +00001903
Chris Lattner41b6a5a2005-09-26 01:43:45 +00001904/// OptimizeGlobalCtorsList - Simplify and evaluation global ctors if possible.
1905/// Return true if anything changed.
1906bool GlobalOpt::OptimizeGlobalCtorsList(GlobalVariable *&GCL) {
1907 std::vector<Function*> Ctors = ParseGlobalCtors(GCL);
1908 bool MadeChange = false;
1909 if (Ctors.empty()) return false;
1910
1911 // Loop over global ctors, optimizing them when we can.
1912 for (unsigned i = 0; i != Ctors.size(); ++i) {
1913 Function *F = Ctors[i];
1914 // Found a null terminator in the middle of the list, prune off the rest of
1915 // the list.
Chris Lattner838bdc12005-09-26 02:19:27 +00001916 if (F == 0) {
1917 if (i != Ctors.size()-1) {
1918 Ctors.resize(i+1);
1919 MadeChange = true;
1920 }
Chris Lattner41b6a5a2005-09-26 01:43:45 +00001921 break;
1922 }
1923
Chris Lattner99e23fa2005-09-26 04:44:35 +00001924 // We cannot simplify external ctor functions.
1925 if (F->empty()) continue;
1926
1927 // If we can evaluate the ctor at compile time, do.
1928 if (EvaluateStaticConstructor(F)) {
1929 Ctors.erase(Ctors.begin()+i);
1930 MadeChange = true;
1931 --i;
1932 ++NumCtorsEvaluated;
1933 continue;
1934 }
Chris Lattner41b6a5a2005-09-26 01:43:45 +00001935 }
1936
1937 if (!MadeChange) return false;
1938
Chris Lattner696beef2005-09-26 02:31:18 +00001939 GCL = InstallGlobalCtors(GCL, Ctors);
Chris Lattner41b6a5a2005-09-26 01:43:45 +00001940 return true;
1941}
1942
1943
Chris Lattner25db5802004-10-07 04:16:33 +00001944bool GlobalOpt::runOnModule(Module &M) {
1945 bool Changed = false;
Chris Lattner41b6a5a2005-09-26 01:43:45 +00001946
1947 // Try to find the llvm.globalctors list.
1948 GlobalVariable *GlobalCtors = FindGlobalCtors(M);
Chris Lattner25db5802004-10-07 04:16:33 +00001949
Chris Lattner25db5802004-10-07 04:16:33 +00001950 bool LocalChange = true;
1951 while (LocalChange) {
1952 LocalChange = false;
Chris Lattner41b6a5a2005-09-26 01:43:45 +00001953
1954 // Delete functions that are trivially dead, ccc -> fastcc
1955 LocalChange |= OptimizeFunctions(M);
1956
1957 // Optimize global_ctors list.
1958 if (GlobalCtors)
1959 LocalChange |= OptimizeGlobalCtorsList(GlobalCtors);
1960
1961 // Optimize non-address-taken globals.
1962 LocalChange |= OptimizeGlobalVars(M);
Chris Lattner25db5802004-10-07 04:16:33 +00001963 Changed |= LocalChange;
1964 }
Chris Lattner41b6a5a2005-09-26 01:43:45 +00001965
1966 // TODO: Move all global ctors functions to the end of the module for code
1967 // layout.
1968
Chris Lattner25db5802004-10-07 04:16:33 +00001969 return Changed;
1970}