//
// The LLVM Compiler Infrastructure
//
-// This file was developed by Reid Spencer and is distributed under the
+// This file was developed by Reid Spencer and is distributed under the
// University of Illinois Open Source License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
-// This file implements a variety of small optimizations for calls to specific
-// well-known (e.g. runtime library) function calls. For example, a call to the
-// function "exit(3)" that occurs within the main() function can be transformed
-// into a simple "return 3" instruction. Any optimization that takes this form
-// (replace call to library function with simpler code that provides same
-// result) belongs in this file.
+// This file implements a module pass that applies a variety of small
+// optimizations for calls to specific well-known function calls (e.g. runtime
+// library functions). For example, a call to the function "exit(3)" that
+// occurs within the main() function can be transformed into a simple "return 3"
+// instruction. Any optimization that takes this form (replace call to library
+// function with simpler code that provides the same result) belongs in this
+// file.
//
//===----------------------------------------------------------------------===//
/// This statistic keeps track of the total number of library calls that have
/// been simplified regardless of which call it is.
-Statistic<> SimplifiedLibCalls("simplify-libcalls",
- "Number of well-known library calls simplified");
+Statistic<> SimplifiedLibCalls("simplify-libcalls",
+ "Number of library calls simplified");
// Forward declarations
class LibCallOptimization;
class SimplifyLibCalls;
+/// This hash map is populated by the constructor for LibCallOptimization class.
+/// Therefore all subclasses are registered here at static initialization time
+/// and this list is what the SimplifyLibCalls pass uses to apply the individual
+/// optimizations to the call sites.
/// @brief The list of optimizations deriving from LibCallOptimization
-hash_map<std::string,LibCallOptimization*> optlist;
+static hash_map<std::string,LibCallOptimization*> optlist;
/// This class is the abstract base class for the set of optimizations that
/// corresponds to one library call. The SimplifyLibCalls pass will call the
/// ValidateCalledFunction method to ask the optimization if a given Function
/// is the kind that the optimization can handle. If the subclass returns true,
-/// then SImplifyLibCalls will also call the OptimizeCall method to perform,
+/// then SImplifyLibCalls will also call the OptimizeCall method to perform,
/// or attempt to perform, the optimization(s) for the library call. Otherwise,
/// OptimizeCall won't be called. Subclasses are responsible for providing the
/// name of the library call (strlen, strcpy, etc.) to the LibCallOptimization
/// constructor. This is used to efficiently select which call instructions to
-/// optimize. The criteria for a "lib call" is "anything with well known
+/// optimize. The criteria for a "lib call" is "anything with well known
/// semantics", typically a library function that is defined by an international
-/// standard. Because the semantics are well known, the optimizations can
+/// standard. Because the semantics are well known, the optimizations can
/// generally short-circuit actually calling the function if there's a simpler
/// way (e.g. strlen(X) can be reduced to a constant if X is a constant global).
/// @brief Base class for library call optimizations
class LibCallOptimization
{
public:
- /// The \p fname argument must be the name of the library function being
+ /// The \p fname argument must be the name of the library function being
/// optimized by the subclass.
/// @brief Constructor that registers the optimization.
- LibCallOptimization(const char* fname,
- const char* stat_name, const char* description )
+ LibCallOptimization(const char* fname, const char* description )
: func_name(fname)
#ifndef NDEBUG
- , occurrences(stat_name,description)
+ , occurrences("simplify-libcalls",description)
#endif
{
// Register this call optimizer in the optlist (a hash_map)
virtual ~LibCallOptimization() { optlist.erase(func_name); }
/// The implementation of this function in subclasses should determine if
- /// \p F is suitable for the optimization. This method is called by
- /// SimplifyLibCalls::runOnModule to short circuit visiting all the call
- /// sites of such a function if that function is not suitable in the first
+ /// \p F is suitable for the optimization. This method is called by
+ /// SimplifyLibCalls::runOnModule to short circuit visiting all the call
+ /// sites of such a function if that function is not suitable in the first
/// place. If the called function is suitabe, this method should return true;
- /// false, otherwise. This function should also perform any lazy
- /// initialization that the LibCallOptimization needs to do, if its to return
+ /// false, otherwise. This function should also perform any lazy
+ /// initialization that the LibCallOptimization needs to do, if its to return
/// true. This avoids doing initialization until the optimizer is actually
/// going to be called upon to do some optimization.
/// @brief Determine if the function is suitable for optimization
SimplifyLibCalls& SLC ///< The pass object invoking us
) = 0;
- /// The implementations of this function in subclasses is the heart of the
- /// SimplifyLibCalls algorithm. Sublcasses of this class implement
+ /// The implementations of this function in subclasses is the heart of the
+ /// SimplifyLibCalls algorithm. Sublcasses of this class implement
/// OptimizeCall to determine if (a) the conditions are right for optimizing
- /// the call and (b) to perform the optimization. If an action is taken
+ /// the call and (b) to perform the optimization. If an action is taken
/// against ci, the subclass is responsible for returning true and ensuring
/// that ci is erased from its parent.
/// @brief Optimize a call, if possible.
#ifndef NDEBUG
/// @brief Called by SimplifyLibCalls to update the occurrences statistic.
- void succeeded() { ++occurrences; }
+ void succeeded() { DEBUG(++occurrences); }
#endif
private:
#endif
};
-/// This class is an LLVM Pass that applies each of the LibCallOptimization
+/// This class is an LLVM Pass that applies each of the LibCallOptimization
/// instances to all the call sites in a module, relatively efficiently. The
-/// purpose of this pass is to provide optimizations for calls to well-known
+/// purpose of this pass is to provide optimizations for calls to well-known
/// functions with well-known semantics, such as those in the c library. The
-/// class provides the basic infrastructure for handling runOnModule. Whenever /// this pass finds a function call, it asks the appropriate optimizer to
+/// class provides the basic infrastructure for handling runOnModule. Whenever
+/// this pass finds a function call, it asks the appropriate optimizer to
/// validate the call (ValidateLibraryCall). If it is validated, then
/// the OptimizeCall method is also called.
/// @brief A ModulePass for optimizing well-known function calls.
-class SimplifyLibCalls : public ModulePass
+class SimplifyLibCalls : public ModulePass
{
public:
/// We need some target data for accurate signature details that are
// The call optimizations can be recursive. That is, the optimization might
// generate a call to another function which can also be optimized. This way
- // we make the LibCallOptimization instances very specific to the case they
- // handle. It also means we need to keep running over the function calls in
+ // we make the LibCallOptimization instances very specific to the case they
+ // handle. It also means we need to keep running over the function calls in
// the module until we don't get any more optimizations possible.
bool found_optimization = false;
do
for (Module::iterator FI = M.begin(), FE = M.end(); FI != FE; ++FI)
{
// All the "well-known" functions are external and have external linkage
- // because they live in a runtime library somewhere and were (probably)
- // not compiled by LLVM. So, we only act on external functions that
+ // because they live in a runtime library somewhere and were (probably)
+ // not compiled by LLVM. So, we only act on external functions that
// have external linkage and non-empty uses.
if (!FI->isExternal() || !FI->hasExternalLinkage() || FI->use_empty())
continue;
continue;
// Loop over each of the uses of the function
- for (Value::use_iterator UI = FI->use_begin(), UE = FI->use_end();
+ for (Value::use_iterator UI = FI->use_begin(), UE = FI->use_end();
UI != UE ; )
{
// If the use of the function is a call instruction
std::vector<const Type*> args;
args.push_back(Type::IntTy);
args.push_back(FILEptr_type);
- FunctionType* fputc_type =
+ FunctionType* fputc_type =
FunctionType::get(Type::IntTy, args, false);
fputc_func = M->getOrInsertFunction("fputc",fputc_type);
}
args.push_back(TD->getIntPtrType());
args.push_back(TD->getIntPtrType());
args.push_back(FILEptr_type);
- FunctionType* fwrite_type =
+ FunctionType* fwrite_type =
FunctionType::get(TD->getIntPtrType(), args, false);
fwrite_func = M->getOrInsertFunction("fwrite",fwrite_type);
}
{
std::vector<const Type*> args;
args.push_back(Type::DoubleTy);
- FunctionType* sqrt_type =
+ FunctionType* sqrt_type =
FunctionType::get(Type::DoubleTy, args, false);
sqrt_func = M->getOrInsertFunction("sqrt",sqrt_type);
}
std::vector<const Type*> args;
args.push_back(PointerType::get(Type::SByteTy));
args.push_back(PointerType::get(Type::SByteTy));
- FunctionType* strcpy_type =
+ FunctionType* strcpy_type =
FunctionType::get(PointerType::get(Type::SByteTy), args, false);
strcpy_func = M->getOrInsertFunction("strcpy",strcpy_type);
}
{
std::vector<const Type*> args;
args.push_back(PointerType::get(Type::SByteTy));
- FunctionType* strlen_type =
+ FunctionType* strlen_type =
FunctionType::get(TD->getIntPtrType(), args, false);
strlen_func = M->getOrInsertFunction("strlen",strlen_type);
}
}
/// @brief Return a Function* for the memcpy libcall
- Function* get_memcpy()
- {
- if (!memcpy_func)
- {
- // Note: this is for llvm.memcpy intrinsic
- std::vector<const Type*> args;
- args.push_back(PointerType::get(Type::SByteTy));
- args.push_back(PointerType::get(Type::SByteTy));
- args.push_back(Type::UIntTy);
- args.push_back(Type::UIntTy);
- FunctionType* memcpy_type = FunctionType::get(Type::VoidTy, args, false);
- memcpy_func = M->getOrInsertFunction("llvm.memcpy",memcpy_type);
+ Function* get_memcpy() {
+ if (!memcpy_func) {
+ const Type *SBP = PointerType::get(Type::SByteTy);
+ memcpy_func = M->getOrInsertFunction("llvm.memcpy", Type::VoidTy,SBP, SBP,
+ Type::UIntTy, Type::UIntTy,
+ (Type *)0);
}
return memcpy_func;
}
+ Function* get_floorf() {
+ if (!floorf_func)
+ floorf_func = M->getOrInsertFunction("floorf", Type::FloatTy,
+ Type::FloatTy, (Type *)0);
+ return floorf_func;
+ }
+
private:
/// @brief Reset our cached data for a new Module
void reset(Module& mod)
sqrt_func = 0;
strcpy_func = 0;
strlen_func = 0;
+ floorf_func = 0;
}
private:
Function* sqrt_func; ///< Cached sqrt function
Function* strcpy_func; ///< Cached strcpy function
Function* strlen_func; ///< Cached strlen function
+ Function* floorf_func; ///< Cached floorf function
Module* M; ///< Cached Module
TargetData* TD; ///< Cached TargetData
};
// Register the pass
-RegisterOpt<SimplifyLibCalls>
+RegisterOpt<SimplifyLibCalls>
X("simplify-libcalls","Simplify well-known library calls");
} // anonymous namespace
// The only public symbol in this file which just instantiates the pass object
-ModulePass *llvm::createSimplifyLibCallsPass()
-{
- return new SimplifyLibCalls();
+ModulePass *llvm::createSimplifyLibCallsPass()
+{
+ return new SimplifyLibCalls();
}
// Classes below here, in the anonymous namespace, are all subclasses of the
// LibCallOptimization class, each implementing all optimizations possible for a
// single well-known library call. Each has a static singleton instance that
-// auto registers it into the "optlist" global above.
+// auto registers it into the "optlist" global above.
namespace {
-// Forward declare a utility function.
+// Forward declare utility functions.
bool getConstantStringLength(Value* V, uint64_t& len, ConstantArray** A = 0 );
+Value *CastToCStr(Value *V, Instruction &IP);
/// This LibCallOptimization will find instances of a call to "exit" that occurs
/// within the "main" function and change it to a simple "ret" instruction with
struct ExitInMainOptimization : public LibCallOptimization
{
ExitInMainOptimization() : LibCallOptimization("exit",
- "simplify-libcalls:exit","Number of 'exit' calls simplified") {}
- virtual ~ExitInMainOptimization() {}
+ "Number of 'exit' calls simplified") {}
// Make sure the called function looks like exit (int argument, int return
- // type, external linkage, not varargs).
+ // type, external linkage, not varargs).
virtual bool ValidateCalledFunction(const Function* f, SimplifyLibCalls& SLC)
{
if (f->arg_size() >= 1)
{
// To be careful, we check that the call to exit is coming from "main", that
// main has external linkage, and the return type of main and the argument
- // to exit have the same type.
+ // to exit have the same type.
Function *from = ci->getParent()->getParent();
if (from->hasExternalLinkage())
if (from->getReturnType() == ci->getOperand(1)->getType())
if (from->getName() == "main")
{
- // Okay, time to actually do the optimization. First, get the basic
+ // Okay, time to actually do the optimization. First, get the basic
// block of the call instruction
BasicBlock* bb = ci->getParent();
- // Create a return instruction that we'll replace the call with.
- // Note that the argument of the return is the argument of the call
+ // Create a return instruction that we'll replace the call with.
+ // Note that the argument of the return is the argument of the call
// instruction.
ReturnInst* ri = new ReturnInst(ci->getOperand(1), ci);
}
} ExitInMainOptimizer;
-/// This LibCallOptimization will simplify a call to the strcat library
-/// function. The simplification is possible only if the string being
-/// concatenated is a constant array or a constant expression that results in
-/// a constant string. In this case we can replace it with strlen + llvm.memcpy
+/// This LibCallOptimization will simplify a call to the strcat library
+/// function. The simplification is possible only if the string being
+/// concatenated is a constant array or a constant expression that results in
+/// a constant string. In this case we can replace it with strlen + llvm.memcpy
/// of the constant string. Both of these calls are further reduced, if possible
/// on subsequent passes.
/// @brief Simplify the strcat library function.
public:
/// @brief Default constructor
StrCatOptimization() : LibCallOptimization("strcat",
- "simplify-libcalls:strcat","Number of 'strcat' calls simplified") {}
+ "Number of 'strcat' calls simplified") {}
public:
- /// @breif Destructor
- virtual ~StrCatOptimization() {}
/// @brief Make sure that the "strcat" function has the right prototype
- virtual bool ValidateCalledFunction(const Function* f, SimplifyLibCalls& SLC)
+ virtual bool ValidateCalledFunction(const Function* f, SimplifyLibCalls& SLC)
{
if (f->getReturnType() == PointerType::get(Type::SByteTy))
- if (f->arg_size() == 2)
+ if (f->arg_size() == 2)
{
Function::const_arg_iterator AI = f->arg_begin();
if (AI++->getType() == PointerType::get(Type::SByteTy))
Value* dest = ci->getOperand(1);
Value* src = ci->getOperand(2);
- // Extract the initializer (while making numerous checks) from the
+ // Extract the initializer (while making numerous checks) from the
// source operand of the call to strcat. If we get null back, one of
// a variety of checks in get_GVInitializer failed
uint64_t len = 0;
// terminator as well.
len++;
- // We need to find the end of the destination string. That's where the
- // memory is to be moved to. We just generate a call to strlen (further
- // optimized in another pass). Note that the SLC.get_strlen() call
+ // We need to find the end of the destination string. That's where the
+ // memory is to be moved to. We just generate a call to strlen (further
+ // optimized in another pass). Note that the SLC.get_strlen() call
// caches the Function* for us.
- CallInst* strlen_inst =
+ CallInst* strlen_inst =
new CallInst(SLC.get_strlen(), dest, dest->getName()+".len",ci);
- // Now that we have the destination's length, we must index into the
+ // Now that we have the destination's length, we must index into the
// destination's pointer to get the actual memcpy destination (end of
// the string .. we're concatenating).
std::vector<Value*> idx;
idx.push_back(strlen_inst);
- GetElementPtrInst* gep =
+ GetElementPtrInst* gep =
new GetElementPtrInst(dest,idx,dest->getName()+".indexed",ci);
// We have enough information to now generate the memcpy call to
vals.push_back(ConstantUInt::get(Type::UIntTy,1)); // alignment
new CallInst(SLC.get_memcpy(), vals, "", ci);
- // Finally, substitute the first operand of the strcat call for the
- // strcat call itself since strcat returns its first operand; and,
+ // Finally, substitute the first operand of the strcat call for the
+ // strcat call itself since strcat returns its first operand; and,
// kill the strcat CallInst.
ci->replaceAllUsesWith(dest);
ci->eraseFromParent();
}
} StrCatOptimizer;
-/// This LibCallOptimization will simplify a call to the strchr library
+/// This LibCallOptimization will simplify a call to the strchr library
/// function. It optimizes out cases where the arguments are both constant
/// and the result can be determined statically.
/// @brief Simplify the strcmp library function.
{
public:
StrChrOptimization() : LibCallOptimization("strchr",
- "simplify-libcalls:strchr","Number of 'strchr' calls simplified") {}
- virtual ~StrChrOptimization() {}
+ "Number of 'strchr' calls simplified") {}
/// @brief Make sure that the "strchr" function has the right prototype
- virtual bool ValidateCalledFunction(const Function* f, SimplifyLibCalls& SLC)
+ virtual bool ValidateCalledFunction(const Function* f, SimplifyLibCalls& SLC)
{
- if (f->getReturnType() == PointerType::get(Type::SByteTy) &&
+ if (f->getReturnType() == PointerType::get(Type::SByteTy) &&
f->arg_size() == 2)
return true;
return false;
}
- /// @brief Perform the strcpy optimization
+ /// @brief Perform the strchr optimizations
virtual bool OptimizeCall(CallInst* ci, SimplifyLibCalls& SLC)
{
// If there aren't three operands, bail
}
} StrChrOptimizer;
-/// This LibCallOptimization will simplify a call to the strcmp library
+/// This LibCallOptimization will simplify a call to the strcmp library
/// function. It optimizes out cases where one or both arguments are constant
/// and the result can be determined statically.
/// @brief Simplify the strcmp library function.
{
public:
StrCmpOptimization() : LibCallOptimization("strcmp",
- "simplify-libcalls:strcmp","Number of 'strcmp' calls simplified") {}
- virtual ~StrCmpOptimization() {}
+ "Number of 'strcmp' calls simplified") {}
- /// @brief Make sure that the "strcpy" function has the right prototype
- virtual bool ValidateCalledFunction(const Function* f, SimplifyLibCalls& SLC)
+ /// @brief Make sure that the "strcmp" function has the right prototype
+ virtual bool ValidateCalledFunction(const Function* f, SimplifyLibCalls& SLC)
{
if (f->getReturnType() == Type::IntTy && f->arg_size() == 2)
return true;
return false;
}
- /// @brief Perform the strcpy optimization
+ /// @brief Perform the strcmp optimization
virtual bool OptimizeCall(CallInst* ci, SimplifyLibCalls& SLC)
{
// First, check to see if src and destination are the same. If they are,
// then the optimization is to replace the CallInst with a constant 0
- // because the call is a no-op.
+ // because the call is a no-op.
Value* s1 = ci->getOperand(1);
Value* s2 = ci->getOperand(2);
if (s1 == s2)
if (len_1 == 0)
{
// strcmp("",x) -> *x
- LoadInst* load = new LoadInst(s1,ci->getName()+".load",ci);
- CastInst* cast =
+ LoadInst* load =
+ new LoadInst(CastToCStr(s2,*ci), ci->getName()+".load",ci);
+ CastInst* cast =
new CastInst(load,Type::IntTy,ci->getName()+".int",ci);
ci->replaceAllUsesWith(cast);
ci->eraseFromParent();
if (len_2 == 0)
{
// strcmp(x,"") -> *x
- LoadInst* load = new LoadInst(s2,ci->getName()+".val",ci);
- CastInst* cast =
+ LoadInst* load =
+ new LoadInst(CastToCStr(s1,*ci),ci->getName()+".val",ci);
+ CastInst* cast =
new CastInst(load,Type::IntTy,ci->getName()+".int",ci);
ci->replaceAllUsesWith(cast);
ci->eraseFromParent();
}
} StrCmpOptimizer;
-/// This LibCallOptimization will simplify a call to the strncmp library
+/// This LibCallOptimization will simplify a call to the strncmp library
/// function. It optimizes out cases where one or both arguments are constant
/// and the result can be determined statically.
/// @brief Simplify the strncmp library function.
{
public:
StrNCmpOptimization() : LibCallOptimization("strncmp",
- "simplify-libcalls:strncmp","Number of 'strncmp' calls simplified") {}
- virtual ~StrNCmpOptimization() {}
+ "Number of 'strncmp' calls simplified") {}
- /// @brief Make sure that the "strcpy" function has the right prototype
- virtual bool ValidateCalledFunction(const Function* f, SimplifyLibCalls& SLC)
+ /// @brief Make sure that the "strncmp" function has the right prototype
+ virtual bool ValidateCalledFunction(const Function* f, SimplifyLibCalls& SLC)
{
if (f->getReturnType() == Type::IntTy && f->arg_size() == 3)
return true;
{
// First, check to see if src and destination are the same. If they are,
// then the optimization is to replace the CallInst with a constant 0
- // because the call is a no-op.
+ // because the call is a no-op.
Value* s1 = ci->getOperand(1);
Value* s2 = ci->getOperand(2);
if (s1 == s2)
ci->replaceAllUsesWith(ConstantInt::get(Type::IntTy,0));
ci->eraseFromParent();
return true;
- }
+ }
}
bool isstr_1 = false;
{
// strncmp("",x) -> *x
LoadInst* load = new LoadInst(s1,ci->getName()+".load",ci);
- CastInst* cast =
+ CastInst* cast =
new CastInst(load,Type::IntTy,ci->getName()+".int",ci);
ci->replaceAllUsesWith(cast);
ci->eraseFromParent();
{
// strncmp(x,"") -> *x
LoadInst* load = new LoadInst(s2,ci->getName()+".val",ci);
- CastInst* cast =
+ CastInst* cast =
new CastInst(load,Type::IntTy,ci->getName()+".int",ci);
ci->replaceAllUsesWith(cast);
ci->eraseFromParent();
}
} StrNCmpOptimizer;
-/// This LibCallOptimization will simplify a call to the strcpy library
-/// function. Two optimizations are possible:
+/// This LibCallOptimization will simplify a call to the strcpy library
+/// function. Two optimizations are possible:
/// (1) If src and dest are the same and not volatile, just return dest
/// (2) If the src is a constant then we can convert to llvm.memmove
/// @brief Simplify the strcpy library function.
{
public:
StrCpyOptimization() : LibCallOptimization("strcpy",
- "simplify-libcalls:strcpy","Number of 'strcpy' calls simplified") {}
- virtual ~StrCpyOptimization() {}
+ "Number of 'strcpy' calls simplified") {}
/// @brief Make sure that the "strcpy" function has the right prototype
- virtual bool ValidateCalledFunction(const Function* f, SimplifyLibCalls& SLC)
+ virtual bool ValidateCalledFunction(const Function* f, SimplifyLibCalls& SLC)
{
if (f->getReturnType() == PointerType::get(Type::SByteTy))
- if (f->arg_size() == 2)
+ if (f->arg_size() == 2)
{
Function::const_arg_iterator AI = f->arg_begin();
if (AI++->getType() == PointerType::get(Type::SByteTy))
{
// First, check to see if src and destination are the same. If they are,
// then the optimization is to replace the CallInst with the destination
- // because the call is a no-op. Note that this corresponds to the
+ // because the call is a no-op. Note that this corresponds to the
// degenerate strcpy(X,X) case which should have "undefined" results
// according to the C specification. However, it occurs sometimes and
// we optimize it as a no-op.
ci->eraseFromParent();
return true;
}
-
+
// Get the length of the constant string referenced by the second operand,
// the "src" parameter. Fail the optimization if we can't get the length
// (note that getConstantStringLength does lots of checks to make sure this
vals.push_back(ConstantUInt::get(Type::UIntTy,1)); // alignment
new CallInst(SLC.get_memcpy(), vals, "", ci);
- // Finally, substitute the first operand of the strcat call for the
- // strcat call itself since strcat returns its first operand; and,
+ // Finally, substitute the first operand of the strcat call for the
+ // strcat call itself since strcat returns its first operand; and,
// kill the strcat CallInst.
ci->replaceAllUsesWith(dest);
ci->eraseFromParent();
}
} StrCpyOptimizer;
-/// This LibCallOptimization will simplify a call to the strlen library
-/// function by replacing it with a constant value if the string provided to
+/// This LibCallOptimization will simplify a call to the strlen library
+/// function by replacing it with a constant value if the string provided to
/// it is a constant array.
/// @brief Simplify the strlen library function.
struct StrLenOptimization : public LibCallOptimization
{
StrLenOptimization() : LibCallOptimization("strlen",
- "simplify-libcalls:strlen","Number of 'strlen' calls simplified") {}
- virtual ~StrLenOptimization() {}
+ "Number of 'strlen' calls simplified") {}
/// @brief Make sure that the "strlen" function has the right prototype
virtual bool ValidateCalledFunction(const Function* f, SimplifyLibCalls& SLC)
{
if (f->getReturnType() == SLC.getTargetData()->getIntPtrType())
- if (f->arg_size() == 1)
+ if (f->arg_size() == 1)
if (Function::const_arg_iterator AI = f->arg_begin())
if (AI->getType() == PointerType::get(Type::SByteTy))
return true;
/// @brief Perform the strlen optimization
virtual bool OptimizeCall(CallInst* ci, SimplifyLibCalls& SLC)
{
- // Get the length of the string
+ // Make sure we're dealing with an sbyte* here.
+ Value* str = ci->getOperand(1);
+ if (str->getType() != PointerType::get(Type::SByteTy))
+ return false;
+
+ // Does the call to strlen have exactly one use?
+ if (ci->hasOneUse())
+ // Is that single use a binary operator?
+ if (BinaryOperator* bop = dyn_cast<BinaryOperator>(ci->use_back()))
+ // Is it compared against a constant integer?
+ if (ConstantInt* CI = dyn_cast<ConstantInt>(bop->getOperand(1)))
+ {
+ // Get the value the strlen result is compared to
+ uint64_t val = CI->getRawValue();
+
+ // If its compared against length 0 with == or !=
+ if (val == 0 &&
+ (bop->getOpcode() == Instruction::SetEQ ||
+ bop->getOpcode() == Instruction::SetNE))
+ {
+ // strlen(x) != 0 -> *x != 0
+ // strlen(x) == 0 -> *x == 0
+ LoadInst* load = new LoadInst(str,str->getName()+".first",ci);
+ BinaryOperator* rbop = BinaryOperator::create(bop->getOpcode(),
+ load, ConstantSInt::get(Type::SByteTy,0),
+ bop->getName()+".strlen", ci);
+ bop->replaceAllUsesWith(rbop);
+ bop->eraseFromParent();
+ ci->eraseFromParent();
+ return true;
+ }
+ }
+
+ // Get the length of the constant string operand
uint64_t len = 0;
if (!getConstantStringLength(ci->getOperand(1),len))
return false;
- ci->replaceAllUsesWith(
- ConstantInt::get(SLC.getTargetData()->getIntPtrType(),len));
+ // strlen("xyz") -> 3 (for example)
+ const Type *Ty = SLC.getTargetData()->getIntPtrType();
+ if (Ty->isSigned())
+ ci->replaceAllUsesWith(ConstantSInt::get(Ty, len));
+ else
+ ci->replaceAllUsesWith(ConstantUInt::get(Ty, len));
+
ci->eraseFromParent();
return true;
}
} StrLenOptimizer;
-/// This LibCallOptimization will simplify a call to the memcpy library
-/// function by expanding it out to a single store of size 0, 1, 2, 4, or 8
+/// IsOnlyUsedInEqualsComparison - Return true if it only matters that the value
+/// is equal or not-equal to zero.
+static bool IsOnlyUsedInEqualsZeroComparison(Instruction *I) {
+ for (Value::use_iterator UI = I->use_begin(), E = I->use_end();
+ UI != E; ++UI) {
+ Instruction *User = cast<Instruction>(*UI);
+ if (User->getOpcode() == Instruction::SetNE ||
+ User->getOpcode() == Instruction::SetEQ) {
+ if (isa<Constant>(User->getOperand(1)) &&
+ cast<Constant>(User->getOperand(1))->isNullValue())
+ continue;
+ } else if (CastInst *CI = dyn_cast<CastInst>(User))
+ if (CI->getType() == Type::BoolTy)
+ continue;
+ // Unknown instruction.
+ return false;
+ }
+ return true;
+}
+
+/// This memcmpOptimization will simplify a call to the memcmp library
+/// function.
+struct memcmpOptimization : public LibCallOptimization {
+ /// @brief Default Constructor
+ memcmpOptimization()
+ : LibCallOptimization("memcmp", "Number of 'memcmp' calls simplified") {}
+
+ /// @brief Make sure that the "memcmp" function has the right prototype
+ virtual bool ValidateCalledFunction(const Function *F, SimplifyLibCalls &TD) {
+ Function::const_arg_iterator AI = F->arg_begin();
+ if (F->arg_size() != 3 || !isa<PointerType>(AI->getType())) return false;
+ if (!isa<PointerType>((++AI)->getType())) return false;
+ if (!(++AI)->getType()->isInteger()) return false;
+ if (!F->getReturnType()->isInteger()) return false;
+ return true;
+ }
+
+ /// Because of alignment and instruction information that we don't have, we
+ /// leave the bulk of this to the code generators.
+ ///
+ /// Note that we could do much more if we could force alignment on otherwise
+ /// small aligned allocas, or if we could indicate that loads have a small
+ /// alignment.
+ virtual bool OptimizeCall(CallInst *CI, SimplifyLibCalls &TD) {
+ Value *LHS = CI->getOperand(1), *RHS = CI->getOperand(2);
+
+ // If the two operands are the same, return zero.
+ if (LHS == RHS) {
+ // memcmp(s,s,x) -> 0
+ CI->replaceAllUsesWith(Constant::getNullValue(CI->getType()));
+ CI->eraseFromParent();
+ return true;
+ }
+
+ // Make sure we have a constant length.
+ ConstantInt *LenC = dyn_cast<ConstantInt>(CI->getOperand(3));
+ if (!LenC) return false;
+ uint64_t Len = LenC->getRawValue();
+
+ // If the length is zero, this returns 0.
+ switch (Len) {
+ case 0:
+ // memcmp(s1,s2,0) -> 0
+ CI->replaceAllUsesWith(Constant::getNullValue(CI->getType()));
+ CI->eraseFromParent();
+ return true;
+ case 1: {
+ // memcmp(S1,S2,1) -> *(ubyte*)S1 - *(ubyte*)S2
+ const Type *UCharPtr = PointerType::get(Type::UByteTy);
+ CastInst *Op1Cast = new CastInst(LHS, UCharPtr, LHS->getName(), CI);
+ CastInst *Op2Cast = new CastInst(RHS, UCharPtr, RHS->getName(), CI);
+ Value *S1V = new LoadInst(Op1Cast, LHS->getName()+".val", CI);
+ Value *S2V = new LoadInst(Op2Cast, RHS->getName()+".val", CI);
+ Value *RV = BinaryOperator::createSub(S1V, S2V, CI->getName()+".diff",CI);
+ if (RV->getType() != CI->getType())
+ RV = new CastInst(RV, CI->getType(), RV->getName(), CI);
+ CI->replaceAllUsesWith(RV);
+ CI->eraseFromParent();
+ return true;
+ }
+ case 2:
+ if (IsOnlyUsedInEqualsZeroComparison(CI)) {
+ // TODO: IF both are aligned, use a short load/compare.
+
+ // memcmp(S1,S2,2) -> S1[0]-S2[0] | S1[1]-S2[1] iff only ==/!= 0 matters
+ const Type *UCharPtr = PointerType::get(Type::UByteTy);
+ CastInst *Op1Cast = new CastInst(LHS, UCharPtr, LHS->getName(), CI);
+ CastInst *Op2Cast = new CastInst(RHS, UCharPtr, RHS->getName(), CI);
+ Value *S1V1 = new LoadInst(Op1Cast, LHS->getName()+".val1", CI);
+ Value *S2V1 = new LoadInst(Op2Cast, RHS->getName()+".val1", CI);
+ Value *D1 = BinaryOperator::createSub(S1V1, S2V1,
+ CI->getName()+".d1", CI);
+ Constant *One = ConstantInt::get(Type::IntTy, 1);
+ Value *G1 = new GetElementPtrInst(Op1Cast, One, "next1v", CI);
+ Value *G2 = new GetElementPtrInst(Op2Cast, One, "next2v", CI);
+ Value *S1V2 = new LoadInst(G1, LHS->getName()+".val2", CI);
+ Value *S2V2 = new LoadInst(G1, RHS->getName()+".val2", CI);
+ Value *D2 = BinaryOperator::createSub(S1V2, S2V2,
+ CI->getName()+".d1", CI);
+ Value *Or = BinaryOperator::createOr(D1, D2, CI->getName()+".res", CI);
+ if (Or->getType() != CI->getType())
+ Or = new CastInst(Or, CI->getType(), Or->getName(), CI);
+ CI->replaceAllUsesWith(Or);
+ CI->eraseFromParent();
+ return true;
+ }
+ break;
+ default:
+ break;
+ }
+
+
+
+ return false;
+ }
+} memcmpOptimizer;
+
+
+
+
+
+/// This LibCallOptimization will simplify a call to the memcpy library
+/// function by expanding it out to a single store of size 0, 1, 2, 4, or 8
/// bytes depending on the length of the string and the alignment. Additional
/// optimizations are possible in code generation (sequence of immediate store)
/// @brief Simplify the memcpy library function.
{
/// @brief Default Constructor
LLVMMemCpyOptimization() : LibCallOptimization("llvm.memcpy",
- "simplify-libcalls:llvm.memcpy",
"Number of 'llvm.memcpy' calls simplified") {}
protected:
- /// @brief Subclass Constructor
- LLVMMemCpyOptimization(const char* fname, const char* sname, const char* desc)
- : LibCallOptimization(fname, sname, desc) {}
+ /// @brief Subclass Constructor
+ LLVMMemCpyOptimization(const char* fname, const char* desc)
+ : LibCallOptimization(fname, desc) {}
public:
- /// @brief Destructor
- virtual ~LLVMMemCpyOptimization() {}
/// @brief Make sure that the "memcpy" function has the right prototype
virtual bool ValidateCalledFunction(const Function* f, SimplifyLibCalls& TD)
}
// Cast source and dest to the right sized primitive and then load/store
- CastInst* SrcCast =
+ CastInst* SrcCast =
new CastInst(src,PointerType::get(castType),src->getName()+".cast",ci);
- CastInst* DestCast =
+ CastInst* DestCast =
new CastInst(dest,PointerType::get(castType),dest->getName()+".cast",ci);
LoadInst* LI = new LoadInst(SrcCast,SrcCast->getName()+".val",ci);
StoreInst* SI = new StoreInst(LI, DestCast, ci);
}
} LLVMMemCpyOptimizer;
-/// This LibCallOptimization will simplify a call to the memmove library
-/// function. It is identical to MemCopyOptimization except for the name of
+/// This LibCallOptimization will simplify a call to the memmove library
+/// function. It is identical to MemCopyOptimization except for the name of
/// the intrinsic.
/// @brief Simplify the memmove library function.
struct LLVMMemMoveOptimization : public LLVMMemCpyOptimization
{
/// @brief Default Constructor
LLVMMemMoveOptimization() : LLVMMemCpyOptimization("llvm.memmove",
- "simplify-libcalls:llvm.memmove",
"Number of 'llvm.memmove' calls simplified") {}
} LLVMMemMoveOptimizer;
-/// This LibCallOptimization will simplify a call to the memset library
-/// function by expanding it out to a single store of size 0, 1, 2, 4, or 8
-/// bytes depending on the length argument.
+/// This LibCallOptimization will simplify a call to the memset library
+/// function by expanding it out to a single store of size 0, 1, 2, 4, or 8
+/// bytes depending on the length argument.
struct LLVMMemSetOptimization : public LibCallOptimization
{
/// @brief Default Constructor
LLVMMemSetOptimization() : LibCallOptimization("llvm.memset",
- "simplify-libcalls:llvm.memset",
"Number of 'llvm.memset' calls simplified") {}
public:
- /// @brief Destructor
- virtual ~LLVMMemSetOptimization() {}
/// @brief Make sure that the "memset" function has the right prototype
virtual bool ValidateCalledFunction(const Function* f, SimplifyLibCalls& TD)
/// Because of alignment and instruction information that we don't have, we
/// leave the bulk of this to the code generators. The optimization here just
/// deals with a few degenerate cases where the length parameter is constant
- /// and the alignment matches the sizes of our intrinsic types so we can do
+ /// and the alignment matches the sizes of our intrinsic types so we can do
/// store instead of the memcpy call. Other calls are transformed into the
/// llvm.memset intrinsic.
/// @brief Perform the memset optimization.
return false;
// memset(s,c,n) -> store s, c (for n=1,2,4,8)
-
+
// Extract the fill character
uint64_t fill_char = FILL->getValue();
uint64_t fill_value = fill_char;
Type* castType = 0;
switch (len)
{
- case 1:
- castType = Type::UByteTy;
+ case 1:
+ castType = Type::UByteTy;
break;
- case 2:
- castType = Type::UShortTy;
+ case 2:
+ castType = Type::UShortTy;
fill_value |= fill_char << 8;
break;
- case 4:
+ case 4:
castType = Type::UIntTy;
fill_value |= fill_char << 8 | fill_char << 16 | fill_char << 24;
break;
- case 8:
+ case 8:
castType = Type::ULongTy;
fill_value |= fill_char << 8 | fill_char << 16 | fill_char << 24;
fill_value |= fill_char << 32 | fill_char << 40 | fill_char << 48;
}
// Cast dest to the right sized primitive and then load/store
- CastInst* DestCast =
+ CastInst* DestCast =
new CastInst(dest,PointerType::get(castType),dest->getName()+".cast",ci);
new StoreInst(ConstantUInt::get(castType,fill_value),DestCast, ci);
ci->eraseFromParent();
}
} LLVMMemSetOptimizer;
-/// This LibCallOptimization will simplify calls to the "pow" library
-/// function. It looks for cases where the result of pow is well known and
+/// This LibCallOptimization will simplify calls to the "pow" library
+/// function. It looks for cases where the result of pow is well known and
/// substitutes the appropriate value.
/// @brief Simplify the pow library function.
struct PowOptimization : public LibCallOptimization
public:
/// @brief Default Constructor
PowOptimization() : LibCallOptimization("pow",
- "simplify-libcalls:pow", "Number of 'pow' calls simplified") {}
-
- /// @brief Destructor
- virtual ~PowOptimization() {}
+ "Number of 'pow' calls simplified") {}
/// @brief Make sure that the "pow" function has the right prototype
virtual bool ValidateCalledFunction(const Function* f, SimplifyLibCalls& SLC)
ci->eraseFromParent();
return true;
}
- }
- else if (ConstantFP* Op2 = dyn_cast<ConstantFP>(expn))
+ }
+ else if (ConstantFP* Op2 = dyn_cast<ConstantFP>(expn))
{
double Op2V = Op2->getValue();
if (Op2V == 0.0)
else if (Op2V == -1.0)
{
// pow(x,-1.0) -> 1.0/x
- BinaryOperator* div_inst= BinaryOperator::create(Instruction::Div,
+ BinaryOperator* div_inst= BinaryOperator::createDiv(
ConstantFP::get(Ty,1.0), base, ci->getName()+".pow", ci);
ci->replaceAllUsesWith(div_inst);
ci->eraseFromParent();
}
} PowOptimizer;
-/// This LibCallOptimization will simplify calls to the "fprintf" library
+/// This LibCallOptimization will simplify calls to the "fprintf" library
/// function. It looks for cases where the result of fprintf is not used and the
/// operation can be reduced to something simpler.
/// @brief Simplify the pow library function.
public:
/// @brief Default Constructor
FPrintFOptimization() : LibCallOptimization("fprintf",
- "simplify-libcalls:fprintf", "Number of 'fprintf' calls simplified") {}
-
- /// @brief Destructor
- virtual ~FPrintFOptimization() {}
+ "Number of 'fprintf' calls simplified") {}
/// @brief Make sure that the "fprintf" function has the right prototype
virtual bool ValidateCalledFunction(const Function* f, SimplifyLibCalls& SLC)
if (ci->getNumOperands() > 4 || ci->getNumOperands() <= 2)
return false;
- // If the result of the fprintf call is used, none of these optimizations
+ // If the result of the fprintf call is used, none of these optimizations
// can be made.
- if (!ci->hasNUses(0))
+ if (!ci->use_empty())
return false;
// All the optimizations depend on the length of the second argument and the
// fact that it is a constant string array. Check that now
- uint64_t len = 0;
+ uint64_t len = 0;
ConstantArray* CA = 0;
if (!getConstantStringLength(ci->getOperand(2), len, &CA))
return false;
if (CI->getRawValue() == '%')
return false; // we found end of string
}
- else
+ else
return false;
}
- // fprintf(file,fmt) -> fwrite(fmt,strlen(fmt),1file)
+ // fprintf(file,fmt) -> fwrite(fmt,strlen(fmt),file)
const Type* FILEptr_type = ci->getOperand(1)->getType();
Function* fwrite_func = SLC.get_fwrite(FILEptr_type);
if (!fwrite_func)
return false;
+
+ // Make sure that the fprintf() and fwrite() functions both take the
+ // same type of char pointer.
+ if (ci->getOperand(2)->getType() !=
+ fwrite_func->getFunctionType()->getParamType(0))
+ return false;
+
std::vector<Value*> args;
args.push_back(ci->getOperand(2));
args.push_back(ConstantUInt::get(SLC.getIntPtrType(),len));
{
case 's':
{
- uint64_t len = 0;
+ uint64_t len = 0;
ConstantArray* CA = 0;
if (!getConstantStringLength(ci->getOperand(3), len, &CA))
return false;
- // fprintf(file,"%s",str) -> fwrite(fmt,strlen(fmt),1,file)
+ // fprintf(file,"%s",str) -> fwrite(fmt,strlen(fmt),1,file)
const Type* FILEptr_type = ci->getOperand(1)->getType();
Function* fwrite_func = SLC.get_fwrite(FILEptr_type);
if (!fwrite_func)
return false;
std::vector<Value*> args;
- args.push_back(ci->getOperand(3));
+ args.push_back(CastToCStr(ci->getOperand(3), *ci));
args.push_back(ConstantUInt::get(SLC.getIntPtrType(),len));
args.push_back(ConstantUInt::get(SLC.getIntPtrType(),1));
args.push_back(ci->getOperand(1));
}
} FPrintFOptimizer;
-
-/// This LibCallOptimization will simplify calls to the "sprintf" library
+/// This LibCallOptimization will simplify calls to the "sprintf" library
/// function. It looks for cases where the result of sprintf is not used and the
/// operation can be reduced to something simpler.
/// @brief Simplify the pow library function.
public:
/// @brief Default Constructor
SPrintFOptimization() : LibCallOptimization("sprintf",
- "simplify-libcalls:sprintf", "Number of 'sprintf' calls simplified") {}
-
- /// @brief Destructor
- virtual ~SPrintFOptimization() {}
+ "Number of 'sprintf' calls simplified") {}
/// @brief Make sure that the "fprintf" function has the right prototype
virtual bool ValidateCalledFunction(const Function* f, SimplifyLibCalls& SLC)
// All the optimizations depend on the length of the second argument and the
// fact that it is a constant string array. Check that now
- uint64_t len = 0;
+ uint64_t len = 0;
ConstantArray* CA = 0;
if (!getConstantStringLength(ci->getOperand(2), len, &CA))
return false;
if (CI->getRawValue() == '%')
return false; // we found a %, can't optimize
}
- else
+ else
return false; // initializer is not constant int, can't optimize
}
// Increment length because we want to copy the null byte too
len++;
- // sprintf(str,fmt) -> llvm.memcpy(str,fmt,strlen(fmt),1)
+ // sprintf(str,fmt) -> llvm.memcpy(str,fmt,strlen(fmt),1)
Function* memcpy_func = SLC.get_memcpy();
if (!memcpy_func)
return false;
// Get the second character and switch on its value
ConstantInt* CI = dyn_cast<ConstantInt>(CA->getOperand(1));
- switch (CI->getRawValue())
- {
- case 's':
- {
- uint64_t len = 0;
- if (ci->hasNUses(0))
- {
- // sprintf(dest,"%s",str) -> strcpy(dest,str)
- Function* strcpy_func = SLC.get_strcpy();
- if (!strcpy_func)
- return false;
- std::vector<Value*> args;
- args.push_back(ci->getOperand(1));
- args.push_back(ci->getOperand(3));
- new CallInst(strcpy_func,args,"",ci);
- }
- else if (getConstantStringLength(ci->getOperand(3),len))
- {
- // sprintf(dest,"%s",cstr) -> llvm.memcpy(dest,str,strlen(str),1)
- len++; // get the null-terminator
- Function* memcpy_func = SLC.get_memcpy();
- if (!memcpy_func)
- return false;
- std::vector<Value*> args;
- args.push_back(ci->getOperand(1));
- args.push_back(ci->getOperand(3));
- args.push_back(ConstantUInt::get(Type::UIntTy,len));
- args.push_back(ConstantUInt::get(Type::UIntTy,1));
- new CallInst(memcpy_func,args,"",ci);
- ci->replaceAllUsesWith(ConstantSInt::get(Type::IntTy,len));
- }
- break;
- }
- case 'c':
- {
- // sprintf(dest,"%c",chr) -> store chr, dest
- CastInst* cast =
- new CastInst(ci->getOperand(3),Type::SByteTy,"char",ci);
- new StoreInst(cast, ci->getOperand(1), ci);
- GetElementPtrInst* gep = new GetElementPtrInst(ci->getOperand(1),
- ConstantUInt::get(Type::UIntTy,1),ci->getOperand(1)->getName()+".end",
- ci);
- new StoreInst(ConstantInt::get(Type::SByteTy,0),gep,ci);
- ci->replaceAllUsesWith(ConstantSInt::get(Type::IntTy,1));
- break;
- }
- default:
+ switch (CI->getRawValue()) {
+ case 's': {
+ // sprintf(dest,"%s",str) -> llvm.memcpy(dest, str, strlen(str)+1, 1)
+ Function* strlen_func = SLC.get_strlen();
+ Function* memcpy_func = SLC.get_memcpy();
+ if (!strlen_func || !memcpy_func)
return false;
+
+ Value *Len = new CallInst(strlen_func, CastToCStr(ci->getOperand(3), *ci),
+ ci->getOperand(3)->getName()+".len", ci);
+ Value *Len1 = BinaryOperator::createAdd(Len,
+ ConstantInt::get(Len->getType(), 1),
+ Len->getName()+"1", ci);
+ if (Len1->getType() != Type::UIntTy)
+ Len1 = new CastInst(Len1, Type::UIntTy, Len1->getName(), ci);
+ std::vector<Value*> args;
+ args.push_back(CastToCStr(ci->getOperand(1), *ci));
+ args.push_back(CastToCStr(ci->getOperand(3), *ci));
+ args.push_back(Len1);
+ args.push_back(ConstantUInt::get(Type::UIntTy,1));
+ new CallInst(memcpy_func, args, "", ci);
+
+ // The strlen result is the unincremented number of bytes in the string.
+ if (!ci->use_empty()) {
+ if (Len->getType() != ci->getType())
+ Len = new CastInst(Len, ci->getType(), Len->getName(), ci);
+ ci->replaceAllUsesWith(Len);
+ }
+ ci->eraseFromParent();
+ return true;
}
- ci->eraseFromParent();
- return true;
+ case 'c': {
+ // sprintf(dest,"%c",chr) -> store chr, dest
+ CastInst* cast = new CastInst(ci->getOperand(3),Type::SByteTy,"char",ci);
+ new StoreInst(cast, ci->getOperand(1), ci);
+ GetElementPtrInst* gep = new GetElementPtrInst(ci->getOperand(1),
+ ConstantUInt::get(Type::UIntTy,1),ci->getOperand(1)->getName()+".end",
+ ci);
+ new StoreInst(ConstantInt::get(Type::SByteTy,0),gep,ci);
+ ci->replaceAllUsesWith(ConstantSInt::get(Type::IntTy,1));
+ ci->eraseFromParent();
+ return true;
+ }
+ }
+ return false;
}
} SPrintFOptimizer;
-/// This LibCallOptimization will simplify calls to the "fputs" library
+/// This LibCallOptimization will simplify calls to the "fputs" library
/// function. It looks for cases where the result of fputs is not used and the
/// operation can be reduced to something simpler.
/// @brief Simplify the pow library function.
public:
/// @brief Default Constructor
PutsOptimization() : LibCallOptimization("fputs",
- "simplify-libcalls:fputs", "Number of 'fputs' calls simplified") {}
-
- /// @brief Destructor
- virtual ~PutsOptimization() {}
+ "Number of 'fputs' calls simplified") {}
/// @brief Make sure that the "fputs" function has the right prototype
virtual bool ValidateCalledFunction(const Function* f, SimplifyLibCalls& SLC)
virtual bool OptimizeCall(CallInst* ci, SimplifyLibCalls& SLC)
{
// If the result is used, none of these optimizations work
- if (!ci->hasNUses(0))
+ if (!ci->use_empty())
return false;
// All the optimizations depend on the length of the first argument and the
// fact that it is a constant string array. Check that now
- uint64_t len = 0;
+ uint64_t len = 0;
if (!getConstantStringLength(ci->getOperand(1), len))
return false;
break;
}
default:
- {
+ {
// fputs(s,F) -> fwrite(s,1,len,F) (if s is constant and strlen(s) > 1)
const Type* FILEptr_type = ci->getOperand(2)->getType();
Function* fwrite_func = SLC.get_fwrite(FILEptr_type);
}
} PutsOptimizer;
-/// This LibCallOptimization will simplify calls to the "toascii" library
+/// This LibCallOptimization will simplify calls to the "isdigit" library
+/// function. It simply does range checks the parameter explicitly.
+/// @brief Simplify the isdigit library function.
+struct isdigitOptimization : public LibCallOptimization {
+public:
+ isdigitOptimization() : LibCallOptimization("isdigit",
+ "Number of 'isdigit' calls simplified") {}
+
+ /// @brief Make sure that the "isdigit" function has the right prototype
+ virtual bool ValidateCalledFunction(const Function* f, SimplifyLibCalls& SLC)
+ {
+ // Just make sure this has 1 argument
+ return (f->arg_size() == 1);
+ }
+
+ /// @brief Perform the toascii optimization.
+ virtual bool OptimizeCall(CallInst* ci, SimplifyLibCalls& SLC)
+ {
+ if (ConstantInt* CI = dyn_cast<ConstantInt>(ci->getOperand(1)))
+ {
+ // isdigit(c) -> 0 or 1, if 'c' is constant
+ uint64_t val = CI->getRawValue();
+ if (val >= '0' && val <='9')
+ ci->replaceAllUsesWith(ConstantSInt::get(Type::IntTy,1));
+ else
+ ci->replaceAllUsesWith(ConstantSInt::get(Type::IntTy,0));
+ ci->eraseFromParent();
+ return true;
+ }
+
+ // isdigit(c) -> (unsigned)c - '0' <= 9
+ CastInst* cast =
+ new CastInst(ci->getOperand(1),Type::UIntTy,
+ ci->getOperand(1)->getName()+".uint",ci);
+ BinaryOperator* sub_inst = BinaryOperator::createSub(cast,
+ ConstantUInt::get(Type::UIntTy,0x30),
+ ci->getOperand(1)->getName()+".sub",ci);
+ SetCondInst* setcond_inst = new SetCondInst(Instruction::SetLE,sub_inst,
+ ConstantUInt::get(Type::UIntTy,9),
+ ci->getOperand(1)->getName()+".cmp",ci);
+ CastInst* c2 =
+ new CastInst(setcond_inst,Type::IntTy,
+ ci->getOperand(1)->getName()+".isdigit",ci);
+ ci->replaceAllUsesWith(c2);
+ ci->eraseFromParent();
+ return true;
+ }
+} isdigitOptimizer;
+
+struct isasciiOptimization : public LibCallOptimization {
+public:
+ isasciiOptimization()
+ : LibCallOptimization("isascii", "Number of 'isascii' calls simplified") {}
+
+ virtual bool ValidateCalledFunction(const Function *F, SimplifyLibCalls &SLC){
+ return F->arg_size() == 1 && F->arg_begin()->getType()->isInteger() &&
+ F->getReturnType()->isInteger();
+ }
+
+ /// @brief Perform the isascii optimization.
+ virtual bool OptimizeCall(CallInst *CI, SimplifyLibCalls &SLC) {
+ // isascii(c) -> (unsigned)c < 128
+ Value *V = CI->getOperand(1);
+ if (V->getType()->isSigned())
+ V = new CastInst(V, V->getType()->getUnsignedVersion(), V->getName(), CI);
+ Value *Cmp = BinaryOperator::createSetLT(V, ConstantUInt::get(V->getType(),
+ 128),
+ V->getName()+".isascii", CI);
+ if (Cmp->getType() != CI->getType())
+ Cmp = new CastInst(Cmp, CI->getType(), Cmp->getName(), CI);
+ CI->replaceAllUsesWith(Cmp);
+ CI->eraseFromParent();
+ return true;
+ }
+} isasciiOptimizer;
+
+
+/// This LibCallOptimization will simplify calls to the "toascii" library
/// function. It simply does the corresponding and operation to restrict the
/// range of values to the ASCII character set (0-127).
/// @brief Simplify the toascii library function.
public:
/// @brief Default Constructor
ToAsciiOptimization() : LibCallOptimization("toascii",
- "simplify-libcalls:toascii", "Number of 'toascii' calls simplified") {}
-
- /// @brief Destructor
- virtual ~ToAsciiOptimization() {}
+ "Number of 'toascii' calls simplified") {}
/// @brief Make sure that the "fputs" function has the right prototype
virtual bool ValidateCalledFunction(const Function* f, SimplifyLibCalls& SLC)
{
// toascii(c) -> (c & 0x7f)
Value* chr = ci->getOperand(1);
- BinaryOperator* and_inst = BinaryOperator::create(Instruction::And,chr,
+ BinaryOperator* and_inst = BinaryOperator::createAnd(chr,
ConstantInt::get(chr->getType(),0x7F),ci->getName()+".toascii",ci);
ci->replaceAllUsesWith(and_inst);
ci->eraseFromParent();
}
} ToAsciiOptimizer;
+/// This LibCallOptimization will simplify calls to the "ffs" library
+/// calls which find the first set bit in an int, long, or long long. The
+/// optimization is to compute the result at compile time if the argument is
+/// a constant.
+/// @brief Simplify the ffs library function.
+struct FFSOptimization : public LibCallOptimization
+{
+protected:
+ /// @brief Subclass Constructor
+ FFSOptimization(const char* funcName, const char* description)
+ : LibCallOptimization(funcName, description)
+ {}
+
+public:
+ /// @brief Default Constructor
+ FFSOptimization() : LibCallOptimization("ffs",
+ "Number of 'ffs' calls simplified") {}
+
+ /// @brief Make sure that the "fputs" function has the right prototype
+ virtual bool ValidateCalledFunction(const Function* f, SimplifyLibCalls& SLC)
+ {
+ // Just make sure this has 2 arguments
+ return (f->arg_size() == 1 && f->getReturnType() == Type::IntTy);
+ }
+
+ /// @brief Perform the ffs optimization.
+ virtual bool OptimizeCall(CallInst* ci, SimplifyLibCalls& SLC)
+ {
+ if (ConstantInt* CI = dyn_cast<ConstantInt>(ci->getOperand(1)))
+ {
+ // ffs(cnst) -> bit#
+ // ffsl(cnst) -> bit#
+ // ffsll(cnst) -> bit#
+ uint64_t val = CI->getRawValue();
+ int result = 0;
+ while (val != 0) {
+ result +=1;
+ if (val&1)
+ break;
+ val >>= 1;
+ }
+ ci->replaceAllUsesWith(ConstantSInt::get(Type::IntTy, result));
+ ci->eraseFromParent();
+ return true;
+ }
+
+ // ffs(x) -> ( x == 0 ? 0 : llvm.cttz(x)+1)
+ // ffsl(x) -> ( x == 0 ? 0 : llvm.cttz(x)+1)
+ // ffsll(x) -> ( x == 0 ? 0 : llvm.cttz(x)+1)
+ const Type* arg_type = ci->getOperand(1)->getType();
+ std::vector<const Type*> args;
+ args.push_back(arg_type);
+ FunctionType* llvm_cttz_type = FunctionType::get(arg_type,args,false);
+ Function* F =
+ SLC.getModule()->getOrInsertFunction("llvm.cttz",llvm_cttz_type);
+ std::string inst_name(ci->getName()+".ffs");
+ Instruction* call =
+ new CallInst(F, ci->getOperand(1), inst_name, ci);
+ if (arg_type != Type::IntTy)
+ call = new CastInst(call, Type::IntTy, inst_name, ci);
+ BinaryOperator* add = BinaryOperator::createAdd(call,
+ ConstantSInt::get(Type::IntTy,1), inst_name, ci);
+ SetCondInst* eq = new SetCondInst(Instruction::SetEQ,ci->getOperand(1),
+ ConstantSInt::get(ci->getOperand(1)->getType(),0),inst_name,ci);
+ SelectInst* select = new SelectInst(eq,ConstantSInt::get(Type::IntTy,0),add,
+ inst_name,ci);
+ ci->replaceAllUsesWith(select);
+ ci->eraseFromParent();
+ return true;
+ }
+} FFSOptimizer;
+
+/// This LibCallOptimization will simplify calls to the "ffsl" library
+/// calls. It simply uses FFSOptimization for which the transformation is
+/// identical.
+/// @brief Simplify the ffsl library function.
+struct FFSLOptimization : public FFSOptimization
+{
+public:
+ /// @brief Default Constructor
+ FFSLOptimization() : FFSOptimization("ffsl",
+ "Number of 'ffsl' calls simplified") {}
+
+} FFSLOptimizer;
+
+/// This LibCallOptimization will simplify calls to the "ffsll" library
+/// calls. It simply uses FFSOptimization for which the transformation is
+/// identical.
+/// @brief Simplify the ffsl library function.
+struct FFSLLOptimization : public FFSOptimization
+{
+public:
+ /// @brief Default Constructor
+ FFSLLOptimization() : FFSOptimization("ffsll",
+ "Number of 'ffsll' calls simplified") {}
+
+} FFSLLOptimizer;
+
+
+/// This LibCallOptimization will simplify calls to the "floor" library
+/// function.
+/// @brief Simplify the floor library function.
+struct FloorOptimization : public LibCallOptimization {
+ FloorOptimization()
+ : LibCallOptimization("floor", "Number of 'floor' calls simplified") {}
+
+ /// @brief Make sure that the "floor" function has the right prototype
+ virtual bool ValidateCalledFunction(const Function *F, SimplifyLibCalls &SLC){
+ return F->arg_size() == 1 && F->arg_begin()->getType() == Type::DoubleTy &&
+ F->getReturnType() == Type::DoubleTy;
+ }
+
+ virtual bool OptimizeCall(CallInst *CI, SimplifyLibCalls &SLC) {
+ // If this is a float argument passed in, convert to floorf.
+ // e.g. floor((double)FLT) -> (double)floorf(FLT). There can be no loss of
+ // precision due to this.
+ if (CastInst *Cast = dyn_cast<CastInst>(CI->getOperand(1)))
+ if (Cast->getOperand(0)->getType() == Type::FloatTy) {
+ Value *New = new CallInst(SLC.get_floorf(), Cast->getOperand(0),
+ CI->getName(), CI);
+ New = new CastInst(New, Type::DoubleTy, CI->getName(), CI);
+ CI->replaceAllUsesWith(New);
+ CI->eraseFromParent();
+ if (Cast->use_empty())
+ Cast->eraseFromParent();
+ return true;
+ }
+ return false; // opt failed
+ }
+} FloorOptimizer;
+
+
+
/// A function to compute the length of a null-terminated constant array of
-/// integers. This function can't rely on the size of the constant array
-/// because there could be a null terminator in the middle of the array.
-/// We also have to bail out if we find a non-integer constant initializer
-/// of one of the elements or if there is no null-terminator. The logic
+/// integers. This function can't rely on the size of the constant array
+/// because there could be a null terminator in the middle of the array.
+/// We also have to bail out if we find a non-integer constant initializer
+/// of one of the elements or if there is no null-terminator. The logic
/// below checks each of these conditions and will return true only if all
/// conditions are met. In that case, the \p len parameter is set to the length
/// of the null-terminated string. If false is returned, the conditions were
bool getConstantStringLength(Value* V, uint64_t& len, ConstantArray** CA )
{
assert(V != 0 && "Invalid args to getConstantStringLength");
- len = 0; // make sure we initialize this
+ len = 0; // make sure we initialize this
User* GEP = 0;
- // If the value is not a GEP instruction nor a constant expression with a
- // GEP instruction, then return false because ConstantArray can't occur
+ // If the value is not a GEP instruction nor a constant expression with a
+ // GEP instruction, then return false because ConstantArray can't occur
// any other way
if (GetElementPtrInst* GEPI = dyn_cast<GetElementPtrInst>(V))
GEP = GEPI;
return false;
// Check to make sure that the first operand of the GEP is an integer and
- // has value 0 so that we are sure we're indexing into the initializer.
+ // has value 0 so that we are sure we're indexing into the initializer.
if (ConstantInt* op1 = dyn_cast<ConstantInt>(GEP->getOperand(1)))
{
if (!op1->isNullValue())
return false;
// Ensure that the second operand is a ConstantInt. If it isn't then this
- // GEP is wonky and we're not really sure what were referencing into and
+ // GEP is wonky and we're not really sure what were referencing into and
// better of not optimizing it. While we're at it, get the second index
// value. We'll need this later for indexing the ConstantArray.
uint64_t start_idx = 0;
uint64_t max_elems = A->getType()->getNumElements();
// Traverse the constant array from start_idx (derived above) which is
- // the place the GEP refers to in the array.
+ // the place the GEP refers to in the array.
for ( len = start_idx; len < max_elems; len++)
{
if (ConstantInt* CI = dyn_cast<ConstantInt>(A->getOperand(len)))
return true; // success!
}
-// TODO:
+/// CastToCStr - Return V if it is an sbyte*, otherwise cast it to sbyte*,
+/// inserting the cast before IP, and return the cast.
+/// @brief Cast a value to a "C" string.
+Value *CastToCStr(Value *V, Instruction &IP) {
+ const Type *SBPTy = PointerType::get(Type::SByteTy);
+ if (V->getType() != SBPTy)
+ return new CastInst(V, SBPTy, V->getName(), &IP);
+ return V;
+}
+
+// TODO:
// Additional cases that we need to add to this file:
//
// cbrt:
// exp, expf, expl:
// * exp(log(x)) -> x
//
-// ffs, ffsl, ffsll:
-// * ffs(cnst) -> cnst'
-//
-// isascii:
-// * isascii(c) -> ((c & ~0x7f) == 0)
-//
-// isdigit:
-// * isdigit(c) -> (unsigned)(c) - '0' <= 9
-//
// log, logf, logl:
// * log(exp(x)) -> x
// * log(x**y) -> y*log(x)
// * lround(cnst) -> cnst'
//
// memcmp:
-// * memcmp(s1,s2,0) -> 0
-// * memcmp(x,x,l) -> 0
// * memcmp(x,y,l) -> cnst
// (if all arguments are constant and strlen(x) <= l and strlen(y) <= l)
-// * memcmp(x,y,1) -> *x - *y
//
// memmove:
-// * memmove(d,s,l,a) -> memcpy(d,s,l,a)
+// * memmove(d,s,l,a) -> memcpy(d,s,l,a)
// (if s is a global constant array)
//
// pow, powf, powl:
// * signbit(cnst) -> cnst'
// * signbit(nncst) -> 0 (if pstv is a non-negative constant)
//
-// sprintf:
-// * sprintf(dest,fmt) -> strcpy(dest,fmt)
-// (if fmt is constant and constains no % characters)
-// * sprintf(dest,"%s",orig) -> strcpy(dest,orig)
-// (only if the sprintf result is not used)
-//
// sqrt, sqrtf, sqrtl:
// * sqrt(expN(x)) -> expN(x*0.5)
// * sqrt(Nroot(x)) -> pow(x,1/(2*N))
// * sqrt(pow(x,y)) -> pow(|x|,y*0.5)
//
+// stpcpy:
+// * stpcpy(str, "literal") ->
+// llvm.memcpy(str,"literal",strlen("literal")+1,1)
// strrchr:
// * strrchr(s,c) -> reverse_offset_of_in(c,s)
// (if c is a constant integer and s is a constant string)
//
// strstr:
// * strstr(x,x) -> x
-// * strstr(s1,s2) -> offset_of_s2_in(s1)
+// * strstr(s1,s2) -> offset_of_s2_in(s1)
// (if s1 and s2 are constant strings)
-//
+//
// tan, tanf, tanl:
// * tan(atan(x)) -> x
-//
+//
// trunc, truncf, truncl:
// * trunc(cnst) -> cnst'
//
-//
+//
}
projects / oota-llvm.git / blobdiff