From b7c11e3966abbad0cf005ca87bcee46aafe48bed Mon Sep 17 00:00:00 2001 From: Reid Spencer Date: Mon, 25 Apr 2005 03:59:26 +0000 Subject: [PATCH] Post-Review Cleanup: * Fix comments at top of file * Change algorithm for running the call optimizations from n*n to something closer to n. * Use a hash_map to store and lookup the optimizations since there will eventually (or potentially) be a large number of them. This gets lookup based on the name of the function to O(1). Each CallOptimizer now has a std::string member named func_name that tracks the name of the function that it applies to. It is this string that is entered into the hash_map for fast comparison against the function names encountered in the module. * Cleanup some style issues pertaining to iterator invalidation * Don't pass the Function pointer to the OptimizeCall function because if the optimization needs it, it can get it from the CallInst passed in. * Add the skeleton for a new CallOptimizer, StrCatOptimizer which will eventually replace strcat's of constant strings with direct copies. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@21526 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Transforms/IPO/SimplifyLibCalls.cpp | 119 ++++++++++++++---------- 1 file changed, 68 insertions(+), 51 deletions(-) diff --git a/lib/Transforms/IPO/SimplifyLibCalls.cpp b/lib/Transforms/IPO/SimplifyLibCalls.cpp index f7b4eb9e425..cd7bb650548 100644 --- a/lib/Transforms/IPO/SimplifyLibCalls.cpp +++ b/lib/Transforms/IPO/SimplifyLibCalls.cpp @@ -1,18 +1,18 @@ -//===- SimplifyLibCalls.cpp - Optimize specific well-known librayr calls --===// +//===- SimplifyLibCalls.cpp - Optimize specific well-known library calls --===// // // The LLVM Compiler Infrastructure // -// This file was developed by Reid Spencer group and is distributed under -// the University of Illinois Open Source License. See LICENSE.TXT for details. +// 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. Many of the ideas for these -// optimizations were taken from GCC's "builtins.c" file but their -// implementation here is completely knew and LLVM-centric +// 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. // //===----------------------------------------------------------------------===// @@ -21,6 +21,7 @@ #include "llvm/Pass.h" #include "llvm/Instructions.h" #include "llvm/ADT/Statistic.h" +#include "llvm/ADT/hash_map" using namespace llvm; namespace { @@ -53,7 +54,7 @@ namespace { struct CallOptimizer { /// @brief Constructor that registers the optimization - CallOptimizer(); + CallOptimizer(const char * fname ); virtual ~CallOptimizer(); @@ -66,16 +67,21 @@ namespace { /// @param ci the call instruction under consideration /// @param f the function that ci calls. /// @brief Optimize a call, if possible. - virtual bool OptimizeCall(CallInst* ci, const Function* f) const = 0; + virtual bool OptimizeCall(CallInst* ci) const = 0; + + const std::string& getFunctionName() const { return func_name; } + private: + std::string func_name; }; /// @brief The list of optimizations deriving from CallOptimizer - std::vector optlist; + hash_map optlist; - CallOptimizer::CallOptimizer() + CallOptimizer::CallOptimizer(const char* fname) + : func_name(fname) { // Register this call optimizer - optlist.push_back(this); + optlist[func_name] = this; } /// Make sure we get our virtual table in this file. @@ -96,23 +102,18 @@ bool SimplifyLibCalls::runOnModule(Module &M) // So, we only act on external functions that have non-empty uses. if (FI->isExternal() && !FI->use_empty()) { - // Loop over each of the uses of the function - for (Value::use_iterator UI = FI->use_begin(), UE = FI->use_end(); - UI != UE ; ) + // Get the optimization class that pertains to this function + if (CallOptimizer* CO = optlist[FI->getName()] ) { - CallInst* CI = dyn_cast(*UI); - ++UI; - - // If the use of the function is a call instruction - if (CI) + // Loop over each of the uses of the function + for (Value::use_iterator UI = FI->use_begin(), UE = FI->use_end(); + UI != UE ; ) { - // Loop over each of the registered optimizations and find the one - // that can optimize this call. - std::vector::iterator OI = optlist.begin(); - std::vector::iterator OE = optlist.end(); - for ( ; OI != OE ; ++OI) + // If the use of the function is a call instruction + if (CallInst* CI = dyn_cast(*UI++)) { - if ((*OI)->OptimizeCall(CI,&(*FI))) + // Do the optimization on the CallOptimizer we found earlier. + if (CO->OptimizeCall(CI)) { ++SimplifiedLibCalls; break; @@ -135,33 +136,49 @@ namespace { /// @brief Replace calls to exit in main with a simple return struct ExitInMainOptimization : public CallOptimizer { -virtual ~ExitInMainOptimization() {} -bool OptimizeCall(CallInst* ci, const Function* func) const + ExitInMainOptimization() : CallOptimizer("exit") {} + virtual ~ExitInMainOptimization() {} + virtual bool OptimizeCall(CallInst* ci) const + { + // If the call isn't coming from main or main doesn't have external linkage + // or the return type of main is not the same as the type of the exit(3) + // argument then we don't act + if (const Function* f = ci->getParent()->getParent()) + if (!(f->hasExternalLinkage() && + (f->getReturnType() == ci->getOperand(1)->getType()) && + (f->getName() == "main"))) + return false; + + // Okay, time to replace it. 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 instruction. + ReturnInst* ri = new ReturnInst(ci->getOperand(1), ci); + + // Erase everything from the call instruction to the end of the block. There + // really shouldn't be anything other than the call instruction, but just in + // case there is we delete it all because its now dead. + bb->getInstList().erase(ci, bb->end()); + + return true; + } +} ExitInMainOptimizer; + +/// This CallOptimizer will find instances of a call to "exit" that occurs +/// within the "main" function and change it to a simple "ret" instruction with +/// the same value as passed to the exit function. It assumes that the +/// instructions after the call to exit(3) can be deleted since they are +/// unreachable anyway. +/// @brief Replace calls to exit in main with a simple return +struct StrCatOptimization : public CallOptimizer { - // If this isn't the exit function then we don't act - if (func->getName() != "exit") + StrCatOptimization() : CallOptimizer("strcat") {} + virtual ~StrCatOptimization() {} + virtual bool OptimizeCall(CallInst* ci) const + { return false; - - // If the call isn't coming from main then we don't act - if (const Function* f = ci->getParent()->getParent()) - if (f->getName() != "main") - return false; - - // Okay, time to replace it. 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 instruction. - ReturnInst* ri = new ReturnInst(ci->getOperand(1), ci); - - // Erase everything from the call instruction to the end of the block. There - // really shouldn't be anything other than the call instruction, but just in - // case there is we delete it all because its now dead. - bb->getInstList().erase(ci, bb->end()); - - return true; -} - -} ExitInMainOptimizer; + } +} StrCatOptimizer; } -- 2.34.1