LLVM API Documentation

GlobalOpt.cpp File Reference

#include "llvm/Transforms/IPO.h"
#include "llvm/CallingConv.h"
#include "llvm/Constants.h"
#include "llvm/DerivedTypes.h"
#include "llvm/Instructions.h"
#include "llvm/IntrinsicInst.h"
#include "llvm/Module.h"
#include "llvm/Pass.h"
#include "llvm/Support/Debug.h"
#include "llvm/Target/TargetData.h"
#include "llvm/Transforms/Utils/Local.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/StringExtras.h"
#include <algorithm>
#include <iostream>
#include <set>

Include dependency graph for GlobalOpt.cpp:

Go to the source code of this file.

Classes

struct  GlobalStatus

Defines

#define DEBUG_TYPE   "globalopt"

Functions

ModulePassllvm::createGlobalOptimizerPass ()
static bool ConstantIsDead (Constant *C)
static bool AnalyzeGlobal (Value *V, GlobalStatus &GS, std::set< PHINode * > &PHIUsers)
static ConstantgetAggregateConstantElement (Constant *Agg, Constant *Idx)
static bool CleanupConstantGlobalUsers (Value *V, Constant *Init)
static GlobalVariableSRAGlobal (GlobalVariable *GV)
static bool AllUsesOfValueWillTrapIfNull (Value *V)
static bool AllUsesOfLoadedValueWillTrapIfNull (GlobalVariable *GV)
static bool OptimizeAwayTrappingUsesOfValue (Value *V, Constant *NewV)
static bool OptimizeAwayTrappingUsesOfLoads (GlobalVariable *GV, Constant *LV)
static void ConstantPropUsersOf (Value *V)
static GlobalVariableOptimizeGlobalAddressOfMalloc (GlobalVariable *GV, MallocInst *MI)
static bool ValueIsOnlyUsedLocallyOrStoredToOneGlobal (Instruction *V, GlobalVariable *GV)
static bool OptimizeOnceStoredGlobal (GlobalVariable *GV, Value *StoredOnceVal, Module::global_iterator &GVI, TargetData &TD)
static void ShrinkGlobalToBoolean (GlobalVariable *GV, Constant *OtherVal)
static bool OnlyCalledDirectly (Function *F)
static void ChangeCalleesToFastCall (Function *F)
static std::vector< Function * > ParseGlobalCtors (GlobalVariable *GV)
static GlobalVariableInstallGlobalCtors (GlobalVariable *GCL, const std::vector< Function * > &Ctors)
static ConstantgetVal (std::map< Value *, Constant * > &ComputedValues, Value *V)
static bool isSimpleEnoughPointerToCommit (Constant *C)
static ConstantEvaluateStoreInto (Constant *Init, Constant *Val, ConstantExpr *Addr, unsigned OpNo)
static void CommitValueTo (Constant *Val, Constant *Addr)
static ConstantComputeLoadResult (Constant *P, const std::map< Constant *, Constant * > &Memory)
static bool EvaluateFunction (Function *F, Constant *&RetVal, const std::vector< Constant * > &ActualArgs, std::vector< Function * > &CallStack, std::map< Constant *, Constant * > &MutatedMemory, std::vector< GlobalVariable * > &AllocaTmps)
static bool EvaluateStaticConstructor (Function *F)

Variables

Statistic NumMarked ("globalopt","Number of globals marked constant")
Statistic NumSRA ("globalopt","Number of aggregate globals broken ""into scalars")
Statistic NumSubstitute ("globalopt","Number of globals with initializers stored into them")
Statistic NumDeleted ("globalopt","Number of globals deleted")
Statistic NumFnDeleted ("globalopt","Number of functions deleted")
Statistic NumGlobUses ("globalopt","Number of global uses devirtualized")
Statistic NumLocalized ("globalopt","Number of globals localized")
Statistic NumShrunkToBool ("globalopt","Number of global vars shrunk to booleans")
Statistic NumFastCallFns ("globalopt","Number of functions converted to fastcc")
Statistic NumCtorsEvaluated ("globalopt","Number of static ctors evaluated")
RegisterOpt< GlobalOpt > X ("globalopt","Global Variable Optimizer")


Define Documentation

#define DEBUG_TYPE   "globalopt"

Definition at line 16 of file GlobalOpt.cpp.


Function Documentation

static bool AllUsesOfLoadedValueWillTrapIfNull ( GlobalVariable GV  )  [static]

AllUsesOfLoadedValueWillTrapIfNull - Return true if all uses of any loads from GV will trap if the loaded value is null. Note that this also permits comparisons of the loaded value against null, as a special case.

Definition at line 523 of file GlobalOpt.cpp.

References AllUsesOfValueWillTrapIfNull(), E, GV, LI, llvm::Value::use_begin(), and llvm::Value::use_end().

Referenced by OptimizeOnceStoredGlobal().

static bool AllUsesOfValueWillTrapIfNull ( Value V  )  [static]

AllUsesOfValueWillTrapIfNull - Return true if all users of the specified value will trap if the value is dynamically null.

Definition at line 487 of file GlobalOpt.cpp.

References E, II, and V.

Referenced by AllUsesOfLoadedValueWillTrapIfNull().

static bool AnalyzeGlobal ( Value V,
GlobalStatus GS,
std::set< PHINode * > &  PHIUsers 
) [static]

AnalyzeGlobal - Look at all uses of the global and fill in the GlobalStatus structure. If the global has its address taken, return true to indicate we can't do anything with it.

Definition at line 149 of file GlobalOpt.cpp.

References E, GlobalStatus::HasNonInstructionUser, GlobalStatus::isNotSuitableForSRA, and V.

static void ChangeCalleesToFastCall ( Function F  )  [static]

ChangeCalleesToFastCall - Walk all of the direct calls of the specified function, changing them to FastCC.

Definition at line 1067 of file GlobalOpt.cpp.

References E, F, and llvm::CallingConv::Fast.

static bool CleanupConstantGlobalUsers ( Value V,
Constant Init 
) [static]

CleanupConstantGlobalUsers - We just marked GV constant. Loop over all users of the global, cleaning up the obvious ones. This is largely just a quick scan over the use list to clean up the easy and obvious cruft. This returns true if it made a change.

Definition at line 305 of file GlobalOpt.cpp.

References llvm::CallingConv::C, Changed, llvm::ConstantFoldInstruction(), llvm::ConstantFoldLoadThroughGEPConstantExpr(), ConstantIsDead(), E, llvm::ConstantExpr::getOpcode(), LI, MI, U, and V.

Referenced by OptimizeAwayTrappingUsesOfLoads().

static void CommitValueTo ( Constant Val,
Constant Addr 
) [static]

CommitValueTo - We have decided that Addr (which satisfies the predicate isSimpleEnoughPointerToCommit) should get Val as its value. Make it happen.

Definition at line 1330 of file GlobalOpt.cpp.

References EvaluateStoreInto(), llvm::ConstantExpr::getOperand(), GV, and Val.

Referenced by EvaluateStaticConstructor().

static Constant* ComputeLoadResult ( Constant P,
const std::map< Constant *, Constant * > &  Memory 
) [static]

ComputeLoadResult - Return the value that would be computed by a load from P after the stores reflected by 'memory' have been performed. If we can't decide, return null.

Definition at line 1348 of file GlobalOpt.cpp.

References llvm::ConstantFoldLoadThroughGEPConstantExpr(), and GV.

Referenced by EvaluateFunction().

static bool ConstantIsDead ( Constant C  )  [static]

ConstantIsDead - Return true if the specified constant is (transitively) dead. The constant may be used by other constants (e.g. constant arrays and constant exprs) as long as they are dead, but it cannot be used by anything else.

Definition at line 133 of file GlobalOpt.cpp.

References llvm::CallingConv::C, and E.

Referenced by CleanupConstantGlobalUsers().

static void ConstantPropUsersOf ( Value V  )  [static]

ConstantPropUsersOf - Walk the use list of V, constant folding all of the instructions that are foldable.

Definition at line 651 of file GlobalOpt.cpp.

References llvm::ConstantFoldInstruction(), E, and V.

Referenced by OptimizeGlobalAddressOfMalloc().

static bool EvaluateFunction ( Function F,
Constant *&  RetVal,
const std::vector< Constant * > &  ActualArgs,
std::vector< Function * > &  CallStack,
std::map< Constant *, Constant * > &  MutatedMemory,
std::vector< GlobalVariable * > &  AllocaTmps 
) [static]

EvaluateFunction - Evaluate a call to function F, returning true if successful, false if we can't evaluate it. ActualArgs contains the formal arguments for the function.

Values - As we compute SSA register values, we store their contents here.

ExecutedBlocks - We only handle non-looping, non-recursive code. As such, we can only evaluate any one basic block at most once. This set keeps track of what we have executed so we can detect recursive cases etc.

Definition at line 1377 of file GlobalOpt.cpp.

References AI, llvm::BasicBlock::begin(), llvm::CallingConv::C, ComputeLoadResult(), llvm::ConstantFoldCall(), E, F, llvm::SequentialType::getElementType(), llvm::Function::getFunctionType(), llvm::PHINode::getIncomingValueForBlock(), llvm::Value::getName(), llvm::AllocationInst::getType(), llvm::Value::getType(), getVal(), llvm::ConstantBool::getValue(), llvm::AllocationInst::isArrayAllocation(), llvm::Function::isExternal(), isSimpleEnoughPointerToCommit(), llvm::FunctionType::isVarArg(), LI, Ty, and Val.

Referenced by EvaluateStaticConstructor().

static bool EvaluateStaticConstructor ( Function F  )  [static]

EvaluateStaticConstructor - Evaluate static constructors in the function, if we can. Return true if we can, false otherwise.

MutatedMemory - For each store we execute, we update this map. Loads check this to get the most up-to-date value. If evaluation is successful, this state is committed to the process.

AllocaTmps - To 'execute' an alloca, we create a temporary global variable to represent its body. This vector is needed so we can delete the temporary globals when we are done.

CallStack - This is used to detect recursion. In pathological situations we could hit exponential behavior, but at least there is nothing unbounded.

Definition at line 1539 of file GlobalOpt.cpp.

References CommitValueTo(), DEBUG, E, EvaluateFunction(), and F.

static Constant* EvaluateStoreInto ( Constant Init,
Constant Val,
ConstantExpr Addr,
unsigned  OpNo 
) [static]

EvaluateStoreInto - Evaluate a piece of a constantexpr store into a global initializer. This returns 'Init' modified to reflect 'Val' stored into it. At this point, the GEP operands of Addr [0, OpNo) have been stepped into.

Definition at line 1266 of file GlobalOpt.cpp.

References llvm::StructType::getElementType(), llvm::StructType::getNumElements(), llvm::User::getNumOperands(), llvm::Constant::getOperand(), llvm::ConstantExpr::getOperand(), llvm::ConstantIntegral::getRawValue(), llvm::Value::getType(), llvm::ConstantUInt::getValue(), Idx, and Val.

Referenced by CommitValueTo().

static Constant* getAggregateConstantElement ( Constant Agg,
Constant Idx 
) [static]

Definition at line 269 of file GlobalOpt.cpp.

References CP, llvm::Constant::getOperand(), llvm::ConstantIntegral::getRawValue(), and Idx.

Referenced by SRAGlobal().

static Constant* getVal ( std::map< Value *, Constant * > &  ComputedValues,
Value V 
) [static]

Definition at line 1232 of file GlobalOpt.cpp.

References R, and V.

static GlobalVariable* InstallGlobalCtors ( GlobalVariable GCL,
const std::vector< Function * > &  Ctors 
) [static]

InstallGlobalCtors - Given a specified llvm.global_ctors list, install the specified array, returning the new global to use.

Definition at line 1175 of file GlobalOpt.cpp.

References llvm::GlobalVariable::eraseFromParent(), llvm::SequentialType::getElementType(), llvm::Module::getGlobalList(), llvm::GlobalVariable::getInitializer(), llvm::GlobalValue::getLinkage(), llvm::Value::getName(), llvm::GlobalValue::getParent(), llvm::Value::getType(), llvm::GlobalValue::getType(), llvm::GlobalVariable::isConstant(), llvm::Value::replaceAllUsesWith(), llvm::GlobalVariable::setInitializer(), llvm::Value::setName(), llvm::Value::use_empty(), and V.

static bool isSimpleEnoughPointerToCommit ( Constant C  )  [static]

isSimpleEnoughPointerToCommit - Return true if this constant is simple enough for us to understand. In particular, if it is a cast of something, we punt. We basically just support direct accesses to globals and GEP's of globals. This should be kept up to date with CommitValueTo.

Definition at line 1244 of file GlobalOpt.cpp.

References llvm::CallingConv::C, llvm::ConstantFoldLoadThroughGEPConstantExpr(), GV, llvm::GlobalValue::hasExternalLinkage(), llvm::GlobalValue::hasInternalLinkage(), and llvm::GlobalValue::isExternal().

Referenced by EvaluateFunction().

static bool OnlyCalledDirectly ( Function F  )  [static]

OnlyCalledDirectly - Return true if the specified function is only called directly. In other words, its address is never taken.

Definition at line 1052 of file GlobalOpt.cpp.

References E, and F.

static bool OptimizeAwayTrappingUsesOfLoads ( GlobalVariable GV,
Constant LV 
) [static]

OptimizeAwayTrappingUsesOfLoads - The specified global has only one non-null value stored into it. If there are uses of the loaded value that would trap if the loaded value is dynamically null, then we know that they cannot be reachable with a null optimize away the load.

Definition at line 603 of file GlobalOpt.cpp.

References Changed, CleanupConstantGlobalUsers(), DEBUG, E, GV, LI, LV, NumDeleted, NumGlobUses, OptimizeAwayTrappingUsesOfValue(), llvm::Value::use_begin(), llvm::Value::use_empty(), and llvm::Value::use_end().

Referenced by OptimizeOnceStoredGlobal().

static bool OptimizeAwayTrappingUsesOfValue ( Value V,
Constant NewV 
) [static]

Definition at line 539 of file GlobalOpt.cpp.

References llvm::CallingConv::C, Changed, E, llvm::Value::getType(), LI, and V.

Referenced by OptimizeAwayTrappingUsesOfLoads().

static GlobalVariable* OptimizeGlobalAddressOfMalloc ( GlobalVariable GV,
MallocInst MI 
) [static]

OptimizeGlobalAddressOfMalloc - This function takes the specified global variable, and transforms the program as if it always contained the result of the specified malloc. Because it is always the result of the specified malloc, there is no reason to actually DO the malloc. Instead, turn the malloc into a global, and any laods of GV as uses of the new global.

Definition at line 670 of file GlobalOpt.cpp.

References ConstantPropUsersOf(), DEBUG, llvm::Instruction::eraseFromParent(), False, llvm::SequentialType::getElementType(), llvm::Module::getGlobalList(), llvm::Value::getName(), llvm::BinaryOperator::getOpcode(), llvm::GlobalValue::getParent(), llvm::ConstantIntegral::getRawValue(), llvm::GlobalValue::getType(), GV, LI, LV, MI, llvm::Value::replaceAllUsesWith(), True, llvm::Value::use_back(), and llvm::Value::use_empty().

Referenced by OptimizeOnceStoredGlobal().

static bool OptimizeOnceStoredGlobal ( GlobalVariable GV,
Value StoredOnceVal,
Module::global_iterator &  GVI,
TargetData TD 
) [static]

Definition at line 802 of file GlobalOpt.cpp.

References AllUsesOfLoadedValueWillTrapIfNull(), llvm::GlobalValue::getType(), llvm::TargetData::getTypeSize(), GV, llvm::GlobalValue::isNullValue(), MI, OptimizeAwayTrappingUsesOfLoads(), OptimizeGlobalAddressOfMalloc(), TD, and ValueIsOnlyUsedLocallyOrStoredToOneGlobal().

static std::vector<Function*> ParseGlobalCtors ( GlobalVariable GV  )  [static]

ParseGlobalCtors - Given a llvm.global_ctors list that we can understand, return a list of the functions and null terminator as a vector.

Definition at line 1162 of file GlobalOpt.cpp.

References llvm::User::getNumOperands(), llvm::Constant::getOperand(), and GV.

static void ShrinkGlobalToBoolean ( GlobalVariable GV,
Constant OtherVal 
) [static]

ShrinkGlobalToBoolean - At this point, we have learned that the only two values ever stored into GV are its initializer and OtherVal.

Definition at line 858 of file GlobalOpt.cpp.

References False, llvm::Module::getGlobalList(), llvm::Value::getName(), llvm::GlobalValue::getParent(), llvm::Value::getType(), GV, llvm::Constant::isNullValue(), LI, Name, llvm::Value::use_back(), and llvm::Value::use_empty().

static GlobalVariable* SRAGlobal ( GlobalVariable GV  )  [static]

SRAGlobal - Perform scalar replacement of aggregates on the specified global variable. This opens the door for other optimizations by exposing the behavior of the program in a more fine-grained way. We have determined that this transformation is safe already. We return the first global variable we insert so that the caller can reprocess it.

Definition at line 374 of file GlobalOpt.cpp.

References DEBUG, getAggregateConstantElement(), llvm::Module::getGlobalList(), llvm::Value::getName(), llvm::User::getNumOperands(), llvm::User::getOperand(), llvm::GlobalValue::getParent(), GV, llvm::GlobalValue::hasInternalLinkage(), llvm::Value::hasNUsesOrMore(), NumSRA, llvm::Value::replaceAllUsesWith(), Ty, llvm::Value::use_back(), llvm::Value::use_empty(), llvm::utostr(), and Val.

static bool ValueIsOnlyUsedLocallyOrStoredToOneGlobal ( Instruction V,
GlobalVariable GV 
) [static]

ValueIsOnlyUsedLocallyOrStoredToOneGlobal - Scan the use-list of V checking to make sure that there are no complex uses of V. We permit simple things like dereferencing the pointer, but not storing through the address, unless it is to the specified global.

Definition at line 781 of file GlobalOpt.cpp.

References E, GV, and V.

Referenced by OptimizeOnceStoredGlobal().


Variable Documentation

Statistic NumCtorsEvaluated("globalopt","Number of static ctors evaluated") [static]

Statistic NumDeleted("globalopt","Number of globals deleted") [static]

Referenced by llvm::Inliner::doFinalization(), InlineCallIfPossible(), OptimizeAwayTrappingUsesOfLoads(), removeIdenticalCalls(), and llvm::SelectionDAG::ReplaceAllUsesOfValueWith().

Statistic NumFastCallFns("globalopt","Number of functions converted to fastcc") [static]

Statistic NumFnDeleted("globalopt","Number of functions deleted") [static]

Statistic NumGlobUses("globalopt","Number of global uses devirtualized") [static]

Referenced by OptimizeAwayTrappingUsesOfLoads().

Statistic NumLocalized("globalopt","Number of globals localized") [static]

Statistic NumMarked("globalopt","Number of globals marked constant") [static]

Statistic NumShrunkToBool("globalopt","Number of global vars shrunk to booleans") [static]

Statistic NumSRA("globalopt","Number of aggregate globals broken ""into scalars") [static]

Referenced by SRAGlobal().

Statistic NumSubstitute("globalopt","Number of globals with initializers stored into them") [static]

RegisterOpt<GlobalOpt> X("globalopt","Global Variable Optimizer") [static]