Reid Spencer | 9bbaa2a | 2005-04-25 03:59:26 +0000 | [diff] [blame] | 1 | //===- SimplifyLibCalls.cpp - Optimize specific well-known library calls --===// |
Reid Spencer | 39a762d | 2005-04-25 02:53:12 +0000 | [diff] [blame] | 2 | // |
| 3 | // The LLVM Compiler Infrastructure |
| 4 | // |
Reid Spencer | 9bbaa2a | 2005-04-25 03:59:26 +0000 | [diff] [blame] | 5 | // This file was developed by Reid Spencer and is distributed under the |
| 6 | // University of Illinois Open Source License. See LICENSE.TXT for details. |
Reid Spencer | 39a762d | 2005-04-25 02:53:12 +0000 | [diff] [blame] | 7 | // |
| 8 | //===----------------------------------------------------------------------===// |
| 9 | // |
| 10 | // This file implements a variety of small optimizations for calls to specific |
| 11 | // well-known (e.g. runtime library) function calls. For example, a call to the |
| 12 | // function "exit(3)" that occurs within the main() function can be transformed |
Reid Spencer | 9bbaa2a | 2005-04-25 03:59:26 +0000 | [diff] [blame] | 13 | // into a simple "return 3" instruction. Any optimization that takes this form |
| 14 | // (replace call to library function with simpler code that provides same |
| 15 | // result) belongs in this file. |
Reid Spencer | 39a762d | 2005-04-25 02:53:12 +0000 | [diff] [blame] | 16 | // |
| 17 | //===----------------------------------------------------------------------===// |
| 18 | |
Reid Spencer | 18b9981 | 2005-04-26 23:05:17 +0000 | [diff] [blame] | 19 | #define DEBUG_TYPE "simplify-libcalls" |
Reid Spencer | 2bc7a4f | 2005-04-26 23:02:16 +0000 | [diff] [blame] | 20 | #include "llvm/Constants.h" |
| 21 | #include "llvm/DerivedTypes.h" |
| 22 | #include "llvm/Instructions.h" |
Reid Spencer | 39a762d | 2005-04-25 02:53:12 +0000 | [diff] [blame] | 23 | #include "llvm/Module.h" |
| 24 | #include "llvm/Pass.h" |
Reid Spencer | 9bbaa2a | 2005-04-25 03:59:26 +0000 | [diff] [blame] | 25 | #include "llvm/ADT/hash_map" |
Reid Spencer | 2bc7a4f | 2005-04-26 23:02:16 +0000 | [diff] [blame] | 26 | #include "llvm/ADT/Statistic.h" |
| 27 | #include "llvm/Support/Debug.h" |
Reid Spencer | bb92b4f | 2005-04-26 19:13:17 +0000 | [diff] [blame] | 28 | #include "llvm/Target/TargetData.h" |
Reid Spencer | 2bc7a4f | 2005-04-26 23:02:16 +0000 | [diff] [blame] | 29 | #include "llvm/Transforms/IPO.h" |
Reid Spencer | f2534c7 | 2005-04-25 21:11:48 +0000 | [diff] [blame] | 30 | #include <iostream> |
Reid Spencer | 39a762d | 2005-04-25 02:53:12 +0000 | [diff] [blame] | 31 | using namespace llvm; |
| 32 | |
| 33 | namespace { |
| 34 | Statistic<> SimplifiedLibCalls("simplified-lib-calls", |
| 35 | "Number of well-known library calls simplified"); |
| 36 | |
| 37 | /// This class is the base class for a set of small but important |
| 38 | /// optimizations of calls to well-known functions, such as those in the c |
| 39 | /// library. This class provides the basic infrastructure for handling |
| 40 | /// runOnModule. Subclasses register themselves and provide two methods: |
| 41 | /// RecognizeCall and OptimizeCall. Whenever this class finds a function call, |
| 42 | /// it asks the subclasses to recognize the call. If it is recognized, then |
| 43 | /// the OptimizeCall method is called on that subclass instance. In this way |
| 44 | /// the subclasses implement the calling conditions on which they trigger and |
| 45 | /// the action to perform, making it easy to add new optimizations of this |
| 46 | /// form. |
| 47 | /// @brief A ModulePass for optimizing well-known function calls |
| 48 | struct SimplifyLibCalls : public ModulePass { |
| 49 | |
Reid Spencer | bb92b4f | 2005-04-26 19:13:17 +0000 | [diff] [blame] | 50 | /// We need some target data for accurate signature details that are |
| 51 | /// target dependent. So we require target data in our AnalysisUsage. |
| 52 | virtual void getAnalysisUsage(AnalysisUsage& Info) const; |
Reid Spencer | 39a762d | 2005-04-25 02:53:12 +0000 | [diff] [blame] | 53 | |
| 54 | /// For this pass, process all of the function calls in the module, calling |
| 55 | /// RecognizeCall and OptimizeCall as appropriate. |
| 56 | virtual bool runOnModule(Module &M); |
| 57 | |
| 58 | }; |
| 59 | |
| 60 | RegisterOpt<SimplifyLibCalls> |
| 61 | X("simplify-libcalls","Simplify well-known library calls"); |
| 62 | |
| 63 | struct CallOptimizer |
| 64 | { |
| 65 | /// @brief Constructor that registers the optimization |
Reid Spencer | 9bbaa2a | 2005-04-25 03:59:26 +0000 | [diff] [blame] | 66 | CallOptimizer(const char * fname ); |
Reid Spencer | 39a762d | 2005-04-25 02:53:12 +0000 | [diff] [blame] | 67 | |
| 68 | virtual ~CallOptimizer(); |
| 69 | |
Reid Spencer | f2534c7 | 2005-04-25 21:11:48 +0000 | [diff] [blame] | 70 | /// The implementation of this function in subclasses should determine if |
| 71 | /// \p F is suitable for the optimization. This method is called by |
| 72 | /// runOnModule to short circuit visiting all the call sites of such a |
| 73 | /// function if that function is not suitable in the first place. |
| 74 | /// If the called function is suitabe, this method should return true; |
| 75 | /// false, otherwise. This function should also perform any lazy |
| 76 | /// initialization that the CallOptimizer needs to do, if its to return |
| 77 | /// true. This avoids doing initialization until the optimizer is actually |
| 78 | /// going to be called upon to do some optimization. |
| 79 | virtual bool ValidateCalledFunction( |
Reid Spencer | bb92b4f | 2005-04-26 19:13:17 +0000 | [diff] [blame] | 80 | const Function* F, ///< The function that is the target of call sites |
| 81 | const TargetData& TD ///< Information about the target |
Reid Spencer | 8ee5aac | 2005-04-26 03:26:15 +0000 | [diff] [blame] | 82 | ) = 0; |
Reid Spencer | f2534c7 | 2005-04-25 21:11:48 +0000 | [diff] [blame] | 83 | |
Reid Spencer | 39a762d | 2005-04-25 02:53:12 +0000 | [diff] [blame] | 84 | /// The implementations of this function in subclasses is the heart of the |
| 85 | /// SimplifyLibCalls algorithm. Sublcasses of this class implement |
| 86 | /// OptimizeCall to determine if (a) the conditions are right for optimizing |
| 87 | /// the call and (b) to perform the optimization. If an action is taken |
| 88 | /// against ci, the subclass is responsible for returning true and ensuring |
| 89 | /// that ci is erased from its parent. |
| 90 | /// @param ci the call instruction under consideration |
| 91 | /// @param f the function that ci calls. |
| 92 | /// @brief Optimize a call, if possible. |
Reid Spencer | f2534c7 | 2005-04-25 21:11:48 +0000 | [diff] [blame] | 93 | virtual bool OptimizeCall( |
Reid Spencer | bb92b4f | 2005-04-26 19:13:17 +0000 | [diff] [blame] | 94 | CallInst* ci, ///< The call instruction that should be optimized. |
| 95 | const TargetData& TD ///< Information about the target |
Reid Spencer | 8ee5aac | 2005-04-26 03:26:15 +0000 | [diff] [blame] | 96 | ) = 0; |
Reid Spencer | 9bbaa2a | 2005-04-25 03:59:26 +0000 | [diff] [blame] | 97 | |
Reid Spencer | f2534c7 | 2005-04-25 21:11:48 +0000 | [diff] [blame] | 98 | const char * getFunctionName() const { return func_name; } |
Reid Spencer | e95a647 | 2005-04-27 00:05:45 +0000 | [diff] [blame^] | 99 | |
| 100 | #ifndef NDEBUG |
| 101 | void activate() { ++activations; } |
| 102 | #endif |
| 103 | |
Reid Spencer | 9bbaa2a | 2005-04-25 03:59:26 +0000 | [diff] [blame] | 104 | private: |
Reid Spencer | f2534c7 | 2005-04-25 21:11:48 +0000 | [diff] [blame] | 105 | const char* func_name; |
Reid Spencer | e95a647 | 2005-04-27 00:05:45 +0000 | [diff] [blame^] | 106 | #ifndef NDEBUG |
| 107 | Statistic<> activations; |
| 108 | #endif |
Reid Spencer | 39a762d | 2005-04-25 02:53:12 +0000 | [diff] [blame] | 109 | }; |
| 110 | |
| 111 | /// @brief The list of optimizations deriving from CallOptimizer |
Reid Spencer | f2534c7 | 2005-04-25 21:11:48 +0000 | [diff] [blame] | 112 | |
Reid Spencer | 9bbaa2a | 2005-04-25 03:59:26 +0000 | [diff] [blame] | 113 | hash_map<std::string,CallOptimizer*> optlist; |
Reid Spencer | 39a762d | 2005-04-25 02:53:12 +0000 | [diff] [blame] | 114 | |
Reid Spencer | 9bbaa2a | 2005-04-25 03:59:26 +0000 | [diff] [blame] | 115 | CallOptimizer::CallOptimizer(const char* fname) |
| 116 | : func_name(fname) |
Reid Spencer | e95a647 | 2005-04-27 00:05:45 +0000 | [diff] [blame^] | 117 | #ifndef NDEBUG |
| 118 | , activations(fname,"Number of calls simplified") |
| 119 | #endif |
Reid Spencer | 39a762d | 2005-04-25 02:53:12 +0000 | [diff] [blame] | 120 | { |
| 121 | // Register this call optimizer |
Reid Spencer | 9bbaa2a | 2005-04-25 03:59:26 +0000 | [diff] [blame] | 122 | optlist[func_name] = this; |
Reid Spencer | 39a762d | 2005-04-25 02:53:12 +0000 | [diff] [blame] | 123 | } |
| 124 | |
| 125 | /// Make sure we get our virtual table in this file. |
Reid Spencer | fe91dfe | 2005-04-25 21:20:38 +0000 | [diff] [blame] | 126 | CallOptimizer::~CallOptimizer() { } |
Reid Spencer | 8ee5aac | 2005-04-26 03:26:15 +0000 | [diff] [blame] | 127 | |
Reid Spencer | bb92b4f | 2005-04-26 19:13:17 +0000 | [diff] [blame] | 128 | } |
| 129 | |
| 130 | ModulePass *llvm::createSimplifyLibCallsPass() |
| 131 | { |
| 132 | return new SimplifyLibCalls(); |
| 133 | } |
| 134 | |
| 135 | void SimplifyLibCalls::getAnalysisUsage(AnalysisUsage& Info) const |
| 136 | { |
| 137 | // Ask that the TargetData analysis be performed before us so we can use |
| 138 | // the target data. |
| 139 | Info.addRequired<TargetData>(); |
| 140 | } |
| 141 | |
| 142 | bool SimplifyLibCalls::runOnModule(Module &M) |
| 143 | { |
| 144 | TargetData& TD = getAnalysis<TargetData>(); |
| 145 | |
| 146 | bool result = false; |
| 147 | |
| 148 | // The call optimizations can be recursive. That is, the optimization might |
| 149 | // generate a call to another function which can also be optimized. This way |
| 150 | // we make the CallOptimizer instances very specific to the case they handle. |
| 151 | // It also means we need to keep running over the function calls in the module |
| 152 | // until we don't get any more optimizations possible. |
| 153 | bool found_optimization = false; |
| 154 | do |
| 155 | { |
| 156 | found_optimization = false; |
| 157 | for (Module::iterator FI = M.begin(), FE = M.end(); FI != FE; ++FI) |
| 158 | { |
| 159 | // All the "well-known" functions are external and have external linkage |
| 160 | // because they live in a runtime library somewhere and were (probably) |
| 161 | // not compiled by LLVM. So, we only act on external functions that have |
| 162 | // external linkage and non-empty uses. |
Reid Spencer | e95a647 | 2005-04-27 00:05:45 +0000 | [diff] [blame^] | 163 | if (!FI->isExternal() || !FI->hasExternalLinkage() || FI->use_empty()) |
| 164 | continue; |
| 165 | |
| 166 | // Get the optimization class that pertains to this function |
| 167 | CallOptimizer* CO = optlist[FI->getName().c_str()]; |
| 168 | if (!CO) |
| 169 | continue; |
| 170 | |
| 171 | // Make sure the called function is suitable for the optimization |
| 172 | if (!CO->ValidateCalledFunction(FI,TD)) |
| 173 | continue; |
| 174 | |
| 175 | // Loop over each of the uses of the function |
| 176 | for (Value::use_iterator UI = FI->use_begin(), UE = FI->use_end(); |
| 177 | UI != UE ; ) |
Reid Spencer | bb92b4f | 2005-04-26 19:13:17 +0000 | [diff] [blame] | 178 | { |
Reid Spencer | e95a647 | 2005-04-27 00:05:45 +0000 | [diff] [blame^] | 179 | // If the use of the function is a call instruction |
| 180 | if (CallInst* CI = dyn_cast<CallInst>(*UI++)) |
Reid Spencer | bb92b4f | 2005-04-26 19:13:17 +0000 | [diff] [blame] | 181 | { |
Reid Spencer | e95a647 | 2005-04-27 00:05:45 +0000 | [diff] [blame^] | 182 | // Do the optimization on the CallOptimizer. |
| 183 | if (CO->OptimizeCall(CI,TD)) |
Reid Spencer | bb92b4f | 2005-04-26 19:13:17 +0000 | [diff] [blame] | 184 | { |
Reid Spencer | e95a647 | 2005-04-27 00:05:45 +0000 | [diff] [blame^] | 185 | ++SimplifiedLibCalls; |
| 186 | found_optimization = result = true; |
| 187 | #ifndef NDEBUG |
| 188 | CO->activate(); |
| 189 | #endif |
Reid Spencer | bb92b4f | 2005-04-26 19:13:17 +0000 | [diff] [blame] | 190 | } |
| 191 | } |
| 192 | } |
| 193 | } |
| 194 | } while (found_optimization); |
| 195 | return result; |
| 196 | } |
| 197 | |
| 198 | namespace { |
| 199 | |
Reid Spencer | 8ee5aac | 2005-04-26 03:26:15 +0000 | [diff] [blame] | 200 | /// Provide some functions for accessing standard library prototypes and |
| 201 | /// caching them so we don't have to keep recomputing them |
Reid Spencer | bb92b4f | 2005-04-26 19:13:17 +0000 | [diff] [blame] | 202 | FunctionType* get_strlen(const Type* IntPtrTy) |
Reid Spencer | 8ee5aac | 2005-04-26 03:26:15 +0000 | [diff] [blame] | 203 | { |
| 204 | static FunctionType* strlen_type = 0; |
| 205 | if (!strlen_type) |
| 206 | { |
| 207 | std::vector<const Type*> args; |
| 208 | args.push_back(PointerType::get(Type::SByteTy)); |
Reid Spencer | bb92b4f | 2005-04-26 19:13:17 +0000 | [diff] [blame] | 209 | strlen_type = FunctionType::get(IntPtrTy, args, false); |
Reid Spencer | 8ee5aac | 2005-04-26 03:26:15 +0000 | [diff] [blame] | 210 | } |
| 211 | return strlen_type; |
| 212 | } |
| 213 | |
| 214 | FunctionType* get_memcpy() |
| 215 | { |
| 216 | static FunctionType* memcpy_type = 0; |
| 217 | if (!memcpy_type) |
| 218 | { |
| 219 | // Note: this is for llvm.memcpy intrinsic |
| 220 | std::vector<const Type*> args; |
| 221 | args.push_back(PointerType::get(Type::SByteTy)); |
| 222 | args.push_back(PointerType::get(Type::SByteTy)); |
| 223 | args.push_back(Type::IntTy); |
| 224 | args.push_back(Type::IntTy); |
Reid Spencer | aaca170 | 2005-04-26 22:46:23 +0000 | [diff] [blame] | 225 | memcpy_type = FunctionType::get(Type::VoidTy, args, false); |
Reid Spencer | 8ee5aac | 2005-04-26 03:26:15 +0000 | [diff] [blame] | 226 | } |
| 227 | return memcpy_type; |
| 228 | } |
Reid Spencer | 76dab9a | 2005-04-26 05:24:00 +0000 | [diff] [blame] | 229 | |
Reid Spencer | b4f7b83 | 2005-04-26 07:45:18 +0000 | [diff] [blame] | 230 | /// A function to compute the length of a null-terminated string of integers. |
| 231 | /// This function can't rely on the size of the constant array because there |
| 232 | /// could be a null terminator in the middle of the array. We also have to |
| 233 | /// bail out if we find a non-integer constant initializer of one of the |
| 234 | /// elements or if there is no null-terminator. The logic below checks |
| 235 | bool getConstantStringLength(Value* V, uint64_t& len ) |
Reid Spencer | 76dab9a | 2005-04-26 05:24:00 +0000 | [diff] [blame] | 236 | { |
Reid Spencer | bb92b4f | 2005-04-26 19:13:17 +0000 | [diff] [blame] | 237 | assert(V != 0 && "Invalid args to getConstantStringLength"); |
Reid Spencer | b4f7b83 | 2005-04-26 07:45:18 +0000 | [diff] [blame] | 238 | len = 0; // make sure we initialize this |
Reid Spencer | 76dab9a | 2005-04-26 05:24:00 +0000 | [diff] [blame] | 239 | User* GEP = 0; |
Reid Spencer | b4f7b83 | 2005-04-26 07:45:18 +0000 | [diff] [blame] | 240 | // If the value is not a GEP instruction nor a constant expression with a |
| 241 | // GEP instruction, then return false because ConstantArray can't occur |
| 242 | // any other way |
Reid Spencer | 76dab9a | 2005-04-26 05:24:00 +0000 | [diff] [blame] | 243 | if (GetElementPtrInst* GEPI = dyn_cast<GetElementPtrInst>(V)) |
| 244 | GEP = GEPI; |
| 245 | else if (ConstantExpr* CE = dyn_cast<ConstantExpr>(V)) |
| 246 | if (CE->getOpcode() == Instruction::GetElementPtr) |
| 247 | GEP = CE; |
| 248 | else |
Reid Spencer | b4f7b83 | 2005-04-26 07:45:18 +0000 | [diff] [blame] | 249 | return false; |
Reid Spencer | 76dab9a | 2005-04-26 05:24:00 +0000 | [diff] [blame] | 250 | else |
Reid Spencer | b4f7b83 | 2005-04-26 07:45:18 +0000 | [diff] [blame] | 251 | return false; |
Reid Spencer | 76dab9a | 2005-04-26 05:24:00 +0000 | [diff] [blame] | 252 | |
Reid Spencer | bb92b4f | 2005-04-26 19:13:17 +0000 | [diff] [blame] | 253 | // Make sure the GEP has exactly three arguments. |
| 254 | if (GEP->getNumOperands() != 3) |
| 255 | return false; |
| 256 | |
Reid Spencer | 76dab9a | 2005-04-26 05:24:00 +0000 | [diff] [blame] | 257 | // Check to make sure that the first operand of the GEP is an integer and |
| 258 | // has value 0 so that we are sure we're indexing into the initializer. |
| 259 | if (ConstantInt* op1 = dyn_cast<ConstantInt>(GEP->getOperand(1))) |
Reid Spencer | b4f7b83 | 2005-04-26 07:45:18 +0000 | [diff] [blame] | 260 | { |
| 261 | if (!op1->isNullValue()) |
Reid Spencer | 76dab9a | 2005-04-26 05:24:00 +0000 | [diff] [blame] | 262 | return false; |
Reid Spencer | b4f7b83 | 2005-04-26 07:45:18 +0000 | [diff] [blame] | 263 | } |
Reid Spencer | 76dab9a | 2005-04-26 05:24:00 +0000 | [diff] [blame] | 264 | else |
| 265 | return false; |
| 266 | |
| 267 | // Ensure that the second operand is a ConstantInt. If it isn't then this |
| 268 | // GEP is wonky and we're not really sure what were referencing into and |
Reid Spencer | b4f7b83 | 2005-04-26 07:45:18 +0000 | [diff] [blame] | 269 | // better of not optimizing it. While we're at it, get the second index |
| 270 | // value. We'll need this later for indexing the ConstantArray. |
| 271 | uint64_t start_idx = 0; |
| 272 | if (ConstantInt* CI = dyn_cast<ConstantInt>(GEP->getOperand(2))) |
| 273 | start_idx = CI->getRawValue(); |
| 274 | else |
| 275 | return false; |
Reid Spencer | 76dab9a | 2005-04-26 05:24:00 +0000 | [diff] [blame] | 276 | |
| 277 | // The GEP instruction, constant or instruction, must reference a global |
| 278 | // variable that is a constant and is initialized. The referenced constant |
| 279 | // initializer is the array that we'll use for optimization. |
| 280 | GlobalVariable* GV = dyn_cast<GlobalVariable>(GEP->getOperand(0)); |
| 281 | if (!GV || !GV->isConstant() || !GV->hasInitializer()) |
Reid Spencer | b4f7b83 | 2005-04-26 07:45:18 +0000 | [diff] [blame] | 282 | return false; |
Reid Spencer | 76dab9a | 2005-04-26 05:24:00 +0000 | [diff] [blame] | 283 | |
Reid Spencer | bb92b4f | 2005-04-26 19:13:17 +0000 | [diff] [blame] | 284 | // Get the initializer. |
Reid Spencer | b4f7b83 | 2005-04-26 07:45:18 +0000 | [diff] [blame] | 285 | Constant* INTLZR = GV->getInitializer(); |
Reid Spencer | 76dab9a | 2005-04-26 05:24:00 +0000 | [diff] [blame] | 286 | |
Reid Spencer | b4f7b83 | 2005-04-26 07:45:18 +0000 | [diff] [blame] | 287 | // Handle the ConstantAggregateZero case |
| 288 | if (ConstantAggregateZero* CAZ = dyn_cast<ConstantAggregateZero>(INTLZR)) |
| 289 | { |
| 290 | // This is a degenerate case. The initializer is constant zero so the |
| 291 | // length of the string must be zero. |
| 292 | len = 0; |
| 293 | return true; |
| 294 | } |
| 295 | |
| 296 | // Must be a Constant Array |
| 297 | ConstantArray* A = dyn_cast<ConstantArray>(INTLZR); |
| 298 | if (!A) |
| 299 | return false; |
| 300 | |
| 301 | // Get the number of elements in the array |
| 302 | uint64_t max_elems = A->getType()->getNumElements(); |
| 303 | |
| 304 | // Traverse the constant array from start_idx (derived above) which is |
| 305 | // the place the GEP refers to in the array. |
| 306 | for ( len = start_idx; len < max_elems; len++) |
Reid Spencer | 76dab9a | 2005-04-26 05:24:00 +0000 | [diff] [blame] | 307 | { |
| 308 | if (ConstantInt* CI = dyn_cast<ConstantInt>(A->getOperand(len))) |
| 309 | { |
| 310 | // Check for the null terminator |
| 311 | if (CI->isNullValue()) |
| 312 | break; // we found end of string |
| 313 | } |
| 314 | else |
| 315 | return false; // This array isn't suitable, non-int initializer |
| 316 | } |
| 317 | if (len >= max_elems) |
| 318 | return false; // This array isn't null terminated |
Reid Spencer | b4f7b83 | 2005-04-26 07:45:18 +0000 | [diff] [blame] | 319 | |
| 320 | // Subtract out the initial value from the length |
| 321 | len -= start_idx; |
Reid Spencer | 76dab9a | 2005-04-26 05:24:00 +0000 | [diff] [blame] | 322 | return true; // success! |
| 323 | } |
Reid Spencer | 39a762d | 2005-04-25 02:53:12 +0000 | [diff] [blame] | 324 | |
| 325 | /// This CallOptimizer will find instances of a call to "exit" that occurs |
| 326 | /// within the "main" function and change it to a simple "ret" instruction with |
| 327 | /// the same value as passed to the exit function. It assumes that the |
| 328 | /// instructions after the call to exit(3) can be deleted since they are |
| 329 | /// unreachable anyway. |
| 330 | /// @brief Replace calls to exit in main with a simple return |
| 331 | struct ExitInMainOptimization : public CallOptimizer |
| 332 | { |
Reid Spencer | 9bbaa2a | 2005-04-25 03:59:26 +0000 | [diff] [blame] | 333 | ExitInMainOptimization() : CallOptimizer("exit") {} |
| 334 | virtual ~ExitInMainOptimization() {} |
Reid Spencer | f2534c7 | 2005-04-25 21:11:48 +0000 | [diff] [blame] | 335 | |
| 336 | // Make sure the called function looks like exit (int argument, int return |
| 337 | // type, external linkage, not varargs). |
Reid Spencer | bb92b4f | 2005-04-26 19:13:17 +0000 | [diff] [blame] | 338 | virtual bool ValidateCalledFunction(const Function* f, const TargetData& TD) |
Reid Spencer | f2534c7 | 2005-04-25 21:11:48 +0000 | [diff] [blame] | 339 | { |
Reid Spencer | b4f7b83 | 2005-04-26 07:45:18 +0000 | [diff] [blame] | 340 | if (f->arg_size() >= 1) |
| 341 | if (f->arg_begin()->getType()->isInteger()) |
| 342 | return true; |
Reid Spencer | f2534c7 | 2005-04-25 21:11:48 +0000 | [diff] [blame] | 343 | return false; |
| 344 | } |
| 345 | |
Reid Spencer | bb92b4f | 2005-04-26 19:13:17 +0000 | [diff] [blame] | 346 | virtual bool OptimizeCall(CallInst* ci, const TargetData& TD) |
Reid Spencer | 9bbaa2a | 2005-04-25 03:59:26 +0000 | [diff] [blame] | 347 | { |
Reid Spencer | f2534c7 | 2005-04-25 21:11:48 +0000 | [diff] [blame] | 348 | // To be careful, we check that the call to exit is coming from "main", that |
| 349 | // main has external linkage, and the return type of main and the argument |
| 350 | // to exit have the same type. |
| 351 | Function *from = ci->getParent()->getParent(); |
| 352 | if (from->hasExternalLinkage()) |
| 353 | if (from->getReturnType() == ci->getOperand(1)->getType()) |
| 354 | if (from->getName() == "main") |
| 355 | { |
| 356 | // Okay, time to actually do the optimization. First, get the basic |
| 357 | // block of the call instruction |
| 358 | BasicBlock* bb = ci->getParent(); |
Reid Spencer | 39a762d | 2005-04-25 02:53:12 +0000 | [diff] [blame] | 359 | |
Reid Spencer | f2534c7 | 2005-04-25 21:11:48 +0000 | [diff] [blame] | 360 | // Create a return instruction that we'll replace the call with. |
| 361 | // Note that the argument of the return is the argument of the call |
| 362 | // instruction. |
| 363 | ReturnInst* ri = new ReturnInst(ci->getOperand(1), ci); |
Reid Spencer | 39a762d | 2005-04-25 02:53:12 +0000 | [diff] [blame] | 364 | |
Reid Spencer | f2534c7 | 2005-04-25 21:11:48 +0000 | [diff] [blame] | 365 | // Split the block at the call instruction which places it in a new |
| 366 | // basic block. |
Reid Spencer | 8ee5aac | 2005-04-26 03:26:15 +0000 | [diff] [blame] | 367 | bb->splitBasicBlock(ci); |
Reid Spencer | 39a762d | 2005-04-25 02:53:12 +0000 | [diff] [blame] | 368 | |
Reid Spencer | f2534c7 | 2005-04-25 21:11:48 +0000 | [diff] [blame] | 369 | // The block split caused a branch instruction to be inserted into |
| 370 | // the end of the original block, right after the return instruction |
| 371 | // that we put there. That's not a valid block, so delete the branch |
| 372 | // instruction. |
Reid Spencer | 8ee5aac | 2005-04-26 03:26:15 +0000 | [diff] [blame] | 373 | bb->getInstList().pop_back(); |
Reid Spencer | 39a762d | 2005-04-25 02:53:12 +0000 | [diff] [blame] | 374 | |
Reid Spencer | f2534c7 | 2005-04-25 21:11:48 +0000 | [diff] [blame] | 375 | // Now we can finally get rid of the call instruction which now lives |
| 376 | // in the new basic block. |
| 377 | ci->eraseFromParent(); |
| 378 | |
| 379 | // Optimization succeeded, return true. |
| 380 | return true; |
| 381 | } |
| 382 | // We didn't pass the criteria for this optimization so return false |
| 383 | return false; |
Reid Spencer | 9bbaa2a | 2005-04-25 03:59:26 +0000 | [diff] [blame] | 384 | } |
Reid Spencer | 39a762d | 2005-04-25 02:53:12 +0000 | [diff] [blame] | 385 | } ExitInMainOptimizer; |
| 386 | |
Reid Spencer | f2534c7 | 2005-04-25 21:11:48 +0000 | [diff] [blame] | 387 | /// This CallOptimizer will simplify a call to the strcat library function. The |
| 388 | /// simplification is possible only if the string being concatenated is a |
| 389 | /// constant array or a constant expression that results in a constant array. In |
| 390 | /// this case, if the array is small, we can generate a series of inline store |
| 391 | /// instructions to effect the concatenation without calling strcat. |
| 392 | /// @brief Simplify the strcat library function. |
Reid Spencer | 9bbaa2a | 2005-04-25 03:59:26 +0000 | [diff] [blame] | 393 | struct StrCatOptimization : public CallOptimizer |
| 394 | { |
Reid Spencer | 8ee5aac | 2005-04-26 03:26:15 +0000 | [diff] [blame] | 395 | private: |
| 396 | Function* strlen_func; |
| 397 | Function* memcpy_func; |
| 398 | public: |
| 399 | StrCatOptimization() |
| 400 | : CallOptimizer("strcat") |
| 401 | , strlen_func(0) |
| 402 | , memcpy_func(0) |
| 403 | {} |
Reid Spencer | 9bbaa2a | 2005-04-25 03:59:26 +0000 | [diff] [blame] | 404 | virtual ~StrCatOptimization() {} |
Reid Spencer | f2534c7 | 2005-04-25 21:11:48 +0000 | [diff] [blame] | 405 | |
Reid Spencer | bb92b4f | 2005-04-26 19:13:17 +0000 | [diff] [blame] | 406 | inline Function* get_strlen_func(Module*M,const Type* IntPtrTy) |
Reid Spencer | 8ee5aac | 2005-04-26 03:26:15 +0000 | [diff] [blame] | 407 | { |
| 408 | if (strlen_func) |
| 409 | return strlen_func; |
Reid Spencer | bb92b4f | 2005-04-26 19:13:17 +0000 | [diff] [blame] | 410 | return strlen_func = M->getOrInsertFunction("strlen",get_strlen(IntPtrTy)); |
Reid Spencer | 8ee5aac | 2005-04-26 03:26:15 +0000 | [diff] [blame] | 411 | } |
| 412 | |
| 413 | inline Function* get_memcpy_func(Module* M) |
| 414 | { |
| 415 | if (memcpy_func) |
| 416 | return memcpy_func; |
| 417 | return memcpy_func = M->getOrInsertFunction("llvm.memcpy",get_memcpy()); |
| 418 | } |
| 419 | |
Reid Spencer | f2534c7 | 2005-04-25 21:11:48 +0000 | [diff] [blame] | 420 | /// @brief Make sure that the "strcat" function has the right prototype |
Reid Spencer | bb92b4f | 2005-04-26 19:13:17 +0000 | [diff] [blame] | 421 | virtual bool ValidateCalledFunction(const Function* f, const TargetData& TD) |
Reid Spencer | f2534c7 | 2005-04-25 21:11:48 +0000 | [diff] [blame] | 422 | { |
| 423 | if (f->getReturnType() == PointerType::get(Type::SByteTy)) |
| 424 | if (f->arg_size() == 2) |
| 425 | { |
| 426 | Function::const_arg_iterator AI = f->arg_begin(); |
| 427 | if (AI++->getType() == PointerType::get(Type::SByteTy)) |
| 428 | if (AI->getType() == PointerType::get(Type::SByteTy)) |
Reid Spencer | 8ee5aac | 2005-04-26 03:26:15 +0000 | [diff] [blame] | 429 | { |
| 430 | // Invalidate the pre-computed strlen_func and memcpy_func Functions |
| 431 | // because, by definition, this method is only called when a new |
| 432 | // Module is being traversed. Invalidation causes re-computation for |
| 433 | // the new Module (if necessary). |
| 434 | strlen_func = 0; |
| 435 | memcpy_func = 0; |
| 436 | |
| 437 | // Indicate this is a suitable call type. |
Reid Spencer | f2534c7 | 2005-04-25 21:11:48 +0000 | [diff] [blame] | 438 | return true; |
Reid Spencer | 8ee5aac | 2005-04-26 03:26:15 +0000 | [diff] [blame] | 439 | } |
Reid Spencer | f2534c7 | 2005-04-25 21:11:48 +0000 | [diff] [blame] | 440 | } |
| 441 | return false; |
| 442 | } |
| 443 | |
| 444 | /// Perform the optimization if the length of the string concatenated |
| 445 | /// is reasonably short and it is a constant array. |
Reid Spencer | bb92b4f | 2005-04-26 19:13:17 +0000 | [diff] [blame] | 446 | virtual bool OptimizeCall(CallInst* ci, const TargetData& TD) |
Reid Spencer | 9bbaa2a | 2005-04-25 03:59:26 +0000 | [diff] [blame] | 447 | { |
Reid Spencer | 76dab9a | 2005-04-26 05:24:00 +0000 | [diff] [blame] | 448 | // Extract the initializer (while making numerous checks) from the |
| 449 | // source operand of the call to strcat. If we get null back, one of |
| 450 | // a variety of checks in get_GVInitializer failed |
Reid Spencer | b4f7b83 | 2005-04-26 07:45:18 +0000 | [diff] [blame] | 451 | uint64_t len = 0; |
| 452 | if (!getConstantStringLength(ci->getOperand(2),len)) |
Reid Spencer | 8ee5aac | 2005-04-26 03:26:15 +0000 | [diff] [blame] | 453 | return false; |
| 454 | |
Reid Spencer | b4f7b83 | 2005-04-26 07:45:18 +0000 | [diff] [blame] | 455 | // Handle the simple, do-nothing case |
| 456 | if (len == 0) |
Reid Spencer | 8ee5aac | 2005-04-26 03:26:15 +0000 | [diff] [blame] | 457 | { |
Reid Spencer | 8ee5aac | 2005-04-26 03:26:15 +0000 | [diff] [blame] | 458 | ci->replaceAllUsesWith(ci->getOperand(1)); |
| 459 | ci->eraseFromParent(); |
| 460 | return true; |
| 461 | } |
| 462 | |
Reid Spencer | b4f7b83 | 2005-04-26 07:45:18 +0000 | [diff] [blame] | 463 | // Increment the length because we actually want to memcpy the null |
| 464 | // terminator as well. |
| 465 | len++; |
Reid Spencer | f2534c7 | 2005-04-25 21:11:48 +0000 | [diff] [blame] | 466 | |
Reid Spencer | b4f7b83 | 2005-04-26 07:45:18 +0000 | [diff] [blame] | 467 | // Extract some information from the instruction |
| 468 | Module* M = ci->getParent()->getParent()->getParent(); |
| 469 | |
| 470 | // We need to find the end of the destination string. That's where the |
| 471 | // memory is to be moved to. We just generate a call to strlen (further |
| 472 | // optimized in another pass). Note that the get_strlen_func() call |
| 473 | // caches the Function* for us. |
| 474 | CallInst* strlen_inst = |
Reid Spencer | bb92b4f | 2005-04-26 19:13:17 +0000 | [diff] [blame] | 475 | new CallInst(get_strlen_func(M,TD.getIntPtrType()), |
| 476 | ci->getOperand(1),"",ci); |
Reid Spencer | b4f7b83 | 2005-04-26 07:45:18 +0000 | [diff] [blame] | 477 | |
| 478 | // Now that we have the destination's length, we must index into the |
| 479 | // destination's pointer to get the actual memcpy destination (end of |
| 480 | // the string .. we're concatenating). |
| 481 | std::vector<Value*> idx; |
| 482 | idx.push_back(strlen_inst); |
| 483 | GetElementPtrInst* gep = |
| 484 | new GetElementPtrInst(ci->getOperand(1),idx,"",ci); |
| 485 | |
| 486 | // We have enough information to now generate the memcpy call to |
| 487 | // do the concatenation for us. |
| 488 | std::vector<Value*> vals; |
| 489 | vals.push_back(gep); // destination |
| 490 | vals.push_back(ci->getOperand(2)); // source |
| 491 | vals.push_back(ConstantSInt::get(Type::IntTy,len)); // length |
| 492 | vals.push_back(ConstantSInt::get(Type::IntTy,1)); // alignment |
| 493 | CallInst* memcpy_inst = new CallInst(get_memcpy_func(M), vals, "", ci); |
| 494 | |
| 495 | // Finally, substitute the first operand of the strcat call for the |
| 496 | // strcat call itself since strcat returns its first operand; and, |
| 497 | // kill the strcat CallInst. |
| 498 | ci->replaceAllUsesWith(ci->getOperand(1)); |
| 499 | ci->eraseFromParent(); |
| 500 | return true; |
Reid Spencer | 9bbaa2a | 2005-04-25 03:59:26 +0000 | [diff] [blame] | 501 | } |
| 502 | } StrCatOptimizer; |
| 503 | |
Reid Spencer | 76dab9a | 2005-04-26 05:24:00 +0000 | [diff] [blame] | 504 | /// This CallOptimizer will simplify a call to the strlen library function by |
| 505 | /// replacing it with a constant value if the string provided to it is a |
| 506 | /// constant array. |
| 507 | /// @brief Simplify the strlen library function. |
| 508 | struct StrLenOptimization : public CallOptimizer |
| 509 | { |
| 510 | StrLenOptimization() : CallOptimizer("strlen") {} |
| 511 | virtual ~StrLenOptimization() {} |
| 512 | |
| 513 | /// @brief Make sure that the "strlen" function has the right prototype |
Reid Spencer | bb92b4f | 2005-04-26 19:13:17 +0000 | [diff] [blame] | 514 | virtual bool ValidateCalledFunction(const Function* f, const TargetData& TD) |
Reid Spencer | 76dab9a | 2005-04-26 05:24:00 +0000 | [diff] [blame] | 515 | { |
Reid Spencer | bb92b4f | 2005-04-26 19:13:17 +0000 | [diff] [blame] | 516 | if (f->getReturnType() == TD.getIntPtrType()) |
Reid Spencer | 76dab9a | 2005-04-26 05:24:00 +0000 | [diff] [blame] | 517 | if (f->arg_size() == 1) |
| 518 | if (Function::const_arg_iterator AI = f->arg_begin()) |
| 519 | if (AI->getType() == PointerType::get(Type::SByteTy)) |
| 520 | return true; |
| 521 | return false; |
| 522 | } |
| 523 | |
| 524 | /// @brief Perform the strlen optimization |
Reid Spencer | bb92b4f | 2005-04-26 19:13:17 +0000 | [diff] [blame] | 525 | virtual bool OptimizeCall(CallInst* ci, const TargetData& TD) |
Reid Spencer | 76dab9a | 2005-04-26 05:24:00 +0000 | [diff] [blame] | 526 | { |
Reid Spencer | b4f7b83 | 2005-04-26 07:45:18 +0000 | [diff] [blame] | 527 | // Get the length of the string |
| 528 | uint64_t len = 0; |
| 529 | if (!getConstantStringLength(ci->getOperand(1),len)) |
Reid Spencer | 76dab9a | 2005-04-26 05:24:00 +0000 | [diff] [blame] | 530 | return false; |
| 531 | |
Reid Spencer | bb92b4f | 2005-04-26 19:13:17 +0000 | [diff] [blame] | 532 | ci->replaceAllUsesWith(ConstantInt::get(TD.getIntPtrType(),len)); |
Reid Spencer | b4f7b83 | 2005-04-26 07:45:18 +0000 | [diff] [blame] | 533 | ci->eraseFromParent(); |
| 534 | return true; |
Reid Spencer | 76dab9a | 2005-04-26 05:24:00 +0000 | [diff] [blame] | 535 | } |
| 536 | } StrLenOptimizer; |
| 537 | |
Reid Spencer | f2534c7 | 2005-04-25 21:11:48 +0000 | [diff] [blame] | 538 | /// This CallOptimizer will simplify a call to the memcpy library function by |
| 539 | /// expanding it out to a small set of stores if the copy source is a constant |
| 540 | /// array. |
| 541 | /// @brief Simplify the memcpy library function. |
| 542 | struct MemCpyOptimization : public CallOptimizer |
| 543 | { |
Reid Spencer | 8ee5aac | 2005-04-26 03:26:15 +0000 | [diff] [blame] | 544 | MemCpyOptimization() : CallOptimizer("llvm.memcpy") {} |
Reid Spencer | bb92b4f | 2005-04-26 19:13:17 +0000 | [diff] [blame] | 545 | protected: |
| 546 | MemCpyOptimization(const char* fname) : CallOptimizer(fname) {} |
| 547 | public: |
Reid Spencer | f2534c7 | 2005-04-25 21:11:48 +0000 | [diff] [blame] | 548 | virtual ~MemCpyOptimization() {} |
| 549 | |
| 550 | /// @brief Make sure that the "memcpy" function has the right prototype |
Reid Spencer | bb92b4f | 2005-04-26 19:13:17 +0000 | [diff] [blame] | 551 | virtual bool ValidateCalledFunction(const Function* f, const TargetData& TD) |
Reid Spencer | f2534c7 | 2005-04-25 21:11:48 +0000 | [diff] [blame] | 552 | { |
Reid Spencer | bb92b4f | 2005-04-26 19:13:17 +0000 | [diff] [blame] | 553 | // Just make sure this has 4 arguments per LLVM spec. |
Reid Spencer | 2bc7a4f | 2005-04-26 23:02:16 +0000 | [diff] [blame] | 554 | return (f->arg_size() == 4); |
Reid Spencer | f2534c7 | 2005-04-25 21:11:48 +0000 | [diff] [blame] | 555 | } |
| 556 | |
Reid Spencer | b4f7b83 | 2005-04-26 07:45:18 +0000 | [diff] [blame] | 557 | /// Because of alignment and instruction information that we don't have, we |
| 558 | /// leave the bulk of this to the code generators. The optimization here just |
| 559 | /// deals with a few degenerate cases where the length of the string and the |
| 560 | /// alignment match the sizes of our intrinsic types so we can do a load and |
| 561 | /// store instead of the memcpy call. |
| 562 | /// @brief Perform the memcpy optimization. |
Reid Spencer | bb92b4f | 2005-04-26 19:13:17 +0000 | [diff] [blame] | 563 | virtual bool OptimizeCall(CallInst* ci, const TargetData& TD) |
Reid Spencer | f2534c7 | 2005-04-25 21:11:48 +0000 | [diff] [blame] | 564 | { |
Reid Spencer | 4855ebf | 2005-04-26 19:55:57 +0000 | [diff] [blame] | 565 | // Make sure we have constant int values to work with |
| 566 | ConstantInt* LEN = dyn_cast<ConstantInt>(ci->getOperand(3)); |
| 567 | if (!LEN) |
| 568 | return false; |
| 569 | ConstantInt* ALIGN = dyn_cast<ConstantInt>(ci->getOperand(4)); |
| 570 | if (!ALIGN) |
| 571 | return false; |
| 572 | |
| 573 | // If the length is larger than the alignment, we can't optimize |
| 574 | uint64_t len = LEN->getRawValue(); |
| 575 | uint64_t alignment = ALIGN->getRawValue(); |
Reid Spencer | bb92b4f | 2005-04-26 19:13:17 +0000 | [diff] [blame] | 576 | if (len > alignment) |
Reid Spencer | b4f7b83 | 2005-04-26 07:45:18 +0000 | [diff] [blame] | 577 | return false; |
| 578 | |
| 579 | Value* dest = ci->getOperand(1); |
| 580 | Value* src = ci->getOperand(2); |
Reid Spencer | b4f7b83 | 2005-04-26 07:45:18 +0000 | [diff] [blame] | 581 | CastInst* SrcCast = 0; |
| 582 | CastInst* DestCast = 0; |
| 583 | switch (len) |
| 584 | { |
Reid Spencer | bb92b4f | 2005-04-26 19:13:17 +0000 | [diff] [blame] | 585 | case 0: |
Reid Spencer | aaca170 | 2005-04-26 22:46:23 +0000 | [diff] [blame] | 586 | // The memcpy is a no-op so just dump its call. |
Reid Spencer | bb92b4f | 2005-04-26 19:13:17 +0000 | [diff] [blame] | 587 | ci->eraseFromParent(); |
| 588 | return true; |
Reid Spencer | b4f7b83 | 2005-04-26 07:45:18 +0000 | [diff] [blame] | 589 | case 1: |
| 590 | SrcCast = new CastInst(src,PointerType::get(Type::SByteTy),"",ci); |
| 591 | DestCast = new CastInst(dest,PointerType::get(Type::SByteTy),"",ci); |
Reid Spencer | b4f7b83 | 2005-04-26 07:45:18 +0000 | [diff] [blame] | 592 | break; |
| 593 | case 2: |
| 594 | SrcCast = new CastInst(src,PointerType::get(Type::ShortTy),"",ci); |
| 595 | DestCast = new CastInst(dest,PointerType::get(Type::ShortTy),"",ci); |
Reid Spencer | b4f7b83 | 2005-04-26 07:45:18 +0000 | [diff] [blame] | 596 | break; |
| 597 | case 4: |
| 598 | SrcCast = new CastInst(src,PointerType::get(Type::IntTy),"",ci); |
| 599 | DestCast = new CastInst(dest,PointerType::get(Type::IntTy),"",ci); |
Reid Spencer | b4f7b83 | 2005-04-26 07:45:18 +0000 | [diff] [blame] | 600 | break; |
| 601 | case 8: |
| 602 | SrcCast = new CastInst(src,PointerType::get(Type::LongTy),"",ci); |
| 603 | DestCast = new CastInst(dest,PointerType::get(Type::LongTy),"",ci); |
Reid Spencer | b4f7b83 | 2005-04-26 07:45:18 +0000 | [diff] [blame] | 604 | break; |
| 605 | default: |
| 606 | return false; |
| 607 | } |
Reid Spencer | bb92b4f | 2005-04-26 19:13:17 +0000 | [diff] [blame] | 608 | LoadInst* LI = new LoadInst(SrcCast,"",ci); |
Reid Spencer | b4f7b83 | 2005-04-26 07:45:18 +0000 | [diff] [blame] | 609 | StoreInst* SI = new StoreInst(LI, DestCast, ci); |
Reid Spencer | b4f7b83 | 2005-04-26 07:45:18 +0000 | [diff] [blame] | 610 | ci->eraseFromParent(); |
| 611 | return true; |
Reid Spencer | f2534c7 | 2005-04-25 21:11:48 +0000 | [diff] [blame] | 612 | } |
| 613 | } MemCpyOptimizer; |
Reid Spencer | bb92b4f | 2005-04-26 19:13:17 +0000 | [diff] [blame] | 614 | |
| 615 | /// This CallOptimizer will simplify a call to the memmove library function. It |
| 616 | /// is identical to MemCopyOptimization except for the name of the intrinsic. |
| 617 | /// @brief Simplify the memmove library function. |
| 618 | struct MemMoveOptimization : public MemCpyOptimization |
| 619 | { |
| 620 | MemMoveOptimization() : MemCpyOptimization("llvm.memmove") {} |
| 621 | |
| 622 | } MemMoveOptimizer; |
| 623 | |
Reid Spencer | 39a762d | 2005-04-25 02:53:12 +0000 | [diff] [blame] | 624 | } |