# HG changeset patch # User Frits van Bommel # Date 1240948686 -7200 # Node ID bedf0bfb8fdbddff2db629873c725fb4ebfb1835 # Parent 4ff9ab0d472c24ed2ad1e3ab529c78b881d52931 Implement first D-specific optimization pass: -simplify-drtcalls. It uses the machinery of the standard -simplify-libcalls pass, but optimizes calls to the D runtime instead of calls to C libraries. At the moment, these optimizations are implemented by this pass: - Avoid the runtime call for `arr.length = newlen` if it can determine that the new length isn't longer than the old one. - Ditto for `cast(T[]) arr` if it will clearly always succeed. (e.g. if the length of the original array is zero, or if the old element size is a multiple of the new element size) diff -r 4ff9ab0d472c -r bedf0bfb8fdb CMakeLists.txt --- a/CMakeLists.txt Mon Apr 27 22:34:36 2009 +0200 +++ b/CMakeLists.txt Tue Apr 28 21:58:06 2009 +0200 @@ -135,7 +135,7 @@ file(GLOB FE_SRC ${DMDFE_PATH}/*.c) file(GLOB FE_SRC_ROOT ${DMDFE_PATH}/root/*.c) -file(GLOB GEN_SRC gen/*.cpp) +file(GLOB_RECURSE GEN_SRC gen/*.cpp) file(GLOB IR_SRC ir/*.cpp) # exclude idgen and impcnvgen and generated sources, just in case list(REMOVE_ITEM FE_SRC diff -r 4ff9ab0d472c -r bedf0bfb8fdb gen/optimizer.cpp --- a/gen/optimizer.cpp Mon Apr 27 22:34:36 2009 +0200 +++ b/gen/optimizer.cpp Tue Apr 28 21:58:06 2009 +0200 @@ -1,6 +1,8 @@ #include "gen/optimizer.h" #include "gen/cl_helpers.h" +#include "gen/passes/Passes.h" + #include "llvm/PassManager.h" #include "llvm/LinkAllPasses.h" #include "llvm/Analysis/LoopPass.h" @@ -33,9 +35,19 @@ clEnumValEnd), cl::init(0)); +static cl::opt +disableLangSpecificPasses("disable-d-passes", + cl::desc("Disable D-specific passes in -O"), + cl::ZeroOrMore); + +static cl::opt +disableSimplifyRuntimeCalls("disable-simplify-drtcalls", + cl::desc("Disable simplification of runtime calls in -O"), + cl::ZeroOrMore); + static cl::opt enableInlining("inlining", - cl::desc("(*) Enable function inlining (in -O, if given)"), + cl::desc("(*) Enable function inlining in -O"), cl::ZeroOrMore); // Determine whether or not to run the inliner as part of the default list of @@ -103,6 +115,11 @@ } } + if (optimizeLevel >= 2 && !disableLangSpecificPasses + && !disableSimplifyRuntimeCalls) { + pm.add(createSimplifyDRuntimeCalls()); + } + // -O3 if (optimizeLevel >= 3) { diff -r 4ff9ab0d472c -r bedf0bfb8fdb gen/passes/Passes.h --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/gen/passes/Passes.h Tue Apr 28 21:58:06 2009 +0200 @@ -0,0 +1,12 @@ +#ifndef LDC_PASSES_H +#define LDC_PASSES_H + +namespace llvm { + class FunctionPass; +} + +// Performs simplifications on runtime calls. +llvm::FunctionPass* createSimplifyDRuntimeCalls(); + + +#endif diff -r 4ff9ab0d472c -r bedf0bfb8fdb gen/passes/SimplifyDRuntimeCalls.cpp --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/gen/passes/SimplifyDRuntimeCalls.cpp Tue Apr 28 21:58:06 2009 +0200 @@ -0,0 +1,255 @@ +//===- SimplifyDRuntimeCalls - Optimize calls to the D runtime library ----===// +// +// The LLVM D Compiler +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file implements a simple pass that applies a variety of small +// optimizations for calls to specific functions in the D runtime. +// +// The machinery was copied from the standard -simplify-libcalls LLVM pass. +// +//===----------------------------------------------------------------------===// + +#define DEBUG_TYPE "simplify-drtcalls" + +#include "Passes.h" + +#include "llvm/Pass.h" +#include "llvm/Support/IRBuilder.h" +#include "llvm/Analysis/ValueTracking.h" +#include "llvm/Target/TargetData.h" +#include "llvm/ADT/StringMap.h" +#include "llvm/ADT/Statistic.h" +#include "llvm/Support/Compiler.h" +#include "llvm/Support/Debug.h" +using namespace llvm; + +STATISTIC(NumSimplified, "Number of runtime calls simplified"); + +//===----------------------------------------------------------------------===// +// Optimizer Base Class +//===----------------------------------------------------------------------===// + +/// This class is the abstract base class for the set of optimizations that +/// corresponds to one library call. +namespace { + class VISIBILITY_HIDDEN LibCallOptimization { + protected: + Function *Caller; + const TargetData *TD; + public: + LibCallOptimization() { } + virtual ~LibCallOptimization() {} + + /// CallOptimizer - This pure virtual method is implemented by base classes to + /// do various optimizations. If this returns null then no transformation was + /// performed. If it returns CI, then it transformed the call and CI is to be + /// deleted. If it returns something else, replace CI with the new value and + /// delete CI. + virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B)=0; + + Value *OptimizeCall(CallInst *CI, const TargetData &TD, IRBuilder<> &B) { + Caller = CI->getParent()->getParent(); + this->TD = &TD; + return CallOptimizer(CI->getCalledFunction(), CI, B); + } + }; +} // End anonymous namespace. + + +//===----------------------------------------------------------------------===// +// Miscellaneous LibCall Optimizations +//===----------------------------------------------------------------------===// + +namespace { +//===---------------------------------------===// +// '_d_arraysetlengthT'/'_d_arraysetlengthiT' Optimizations + +/// ArraySetLengthOpt - remove libcall for arr.length = N if N <= arr.length +struct VISIBILITY_HIDDEN ArraySetLengthOpt : public LibCallOptimization { + virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) { + // Verify we have a reasonable prototype for _d_arraysetlength[i]T + const FunctionType *FT = Callee->getFunctionType(); + if (Callee->arg_size() != 4 || !isa(FT->getReturnType()) || + !isa(FT->getParamType(1)) || + FT->getParamType(1) != FT->getParamType(2) || + FT->getParamType(3) != FT->getReturnType()) + return 0; + + Value* NewLen = CI->getOperand(2); + if (Constant* NewCst = dyn_cast(NewLen)) { + Value* Data = CI->getOperand(4); + + // For now, we just catch the simplest of cases. + // + // TODO: Implement a more general way to compare old and new + // lengths, to catch cases like "arr.length = arr.length - 1;" + // (But beware of unsigned overflow! For example, we can't + // safely transform that example if arr.length may be 0) + + // Setting length to 0 never reallocates, so replace by data argument + if (NewCst->isNullValue()) + return Data; + + // If both lengths are constant integers, see if NewLen <= OldLen + Value* OldLen = CI->getOperand(3); + if (ConstantInt* OldInt = dyn_cast(OldLen)) + if (ConstantInt* NewInt = dyn_cast(NewCst)) + if (NewInt->getValue().ule(OldInt->getValue())) + return Data; + } + return 0; + } +}; + +/// ArrayCastLenOpt - remove libcall for cast(T[]) arr if it's safe to do so. +struct VISIBILITY_HIDDEN ArrayCastLenOpt : public LibCallOptimization { + virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) { + // Verify we have a reasonable prototype for _d_array_cast_len + const FunctionType *FT = Callee->getFunctionType(); + const Type* RetTy = FT->getReturnType(); + if (Callee->arg_size() != 3 || !isa(RetTy) || + FT->getParamType(1) != RetTy || FT->getParamType(2) != RetTy) + return 0; + + Value* OldLen = CI->getOperand(1); + Value* OldSize = CI->getOperand(2); + Value* NewSize = CI->getOperand(3); + + // If the old length was zero, always return zero. + if (Constant* LenCst = dyn_cast(OldLen)) + if (LenCst->isNullValue()) + return OldLen; + + // Equal sizes are much faster to check for, so do so now. + if (OldSize == NewSize) + return OldLen; + + // If both sizes are constant integers, see if OldSize is a multiple of NewSize + if (ConstantInt* OldInt = dyn_cast(OldSize)) + if (ConstantInt* NewInt = dyn_cast(NewSize)) { + // Don't crash on NewSize == 0, even though it shouldn't happen. + if (NewInt->isNullValue()) + return 0; + + APInt Quot, Rem; + APInt::udivrem(OldInt->getValue(), NewInt->getValue(), Quot, Rem); + if (Rem == 0) + return B.CreateMul(OldLen, ConstantInt::get(Quot)); + } + return 0; + } +}; + +// TODO: More optimizations! :) + +} // end anonymous namespace. + +//===----------------------------------------------------------------------===// +// SimplifyDRuntimeCalls Pass Implementation +//===----------------------------------------------------------------------===// + +namespace { + /// This pass optimizes library functions from the D runtime as used by LDC. + /// + class VISIBILITY_HIDDEN SimplifyDRuntimeCalls : public FunctionPass { + StringMap Optimizations; + + // Array operations + ArraySetLengthOpt ArraySetLength; + ArrayCastLenOpt ArrayCastLen; + + public: + static char ID; // Pass identification + SimplifyDRuntimeCalls() : FunctionPass(&ID) {} + + void InitOptimizations(); + bool runOnFunction(Function &F); + + virtual void getAnalysisUsage(AnalysisUsage &AU) const { + AU.addRequired(); + } + }; + char SimplifyDRuntimeCalls::ID = 0; +} // end anonymous namespace. + +static RegisterPass +X("simplify-drtcalls", "Simplify calls to D runtime"); + +// Public interface to the pass. +FunctionPass *createSimplifyDRuntimeCalls() { + return new SimplifyDRuntimeCalls(); +} + +/// Optimizations - Populate the Optimizations map with all the optimizations +/// we know. +void SimplifyDRuntimeCalls::InitOptimizations() { + Optimizations["_d_arraysetlengthT"] = &ArraySetLength; + Optimizations["_d_arraysetlengthiT"] = &ArraySetLength; + Optimizations["_d_array_cast_len"] = &ArrayCastLen; +} + + +/// runOnFunction - Top level algorithm. +/// +bool SimplifyDRuntimeCalls::runOnFunction(Function &F) { + if (Optimizations.empty()) + InitOptimizations(); + + const TargetData &TD = getAnalysis(); + + IRBuilder<> Builder; + + bool Changed = false; + for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) { + for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ) { + // Ignore non-calls. + CallInst *CI = dyn_cast(I++); + if (!CI) continue; + + // Ignore indirect calls and calls to non-external functions. + Function *Callee = CI->getCalledFunction(); + if (Callee == 0 || !Callee->isDeclaration() || + !(Callee->hasExternalLinkage() || Callee->hasDLLImportLinkage())) + continue; + + DEBUG(DOUT << "SimplifyDRuntimeCalls inspecting: " << *CI); + + // Ignore unknown calls. + const char *CalleeName = Callee->getNameStart(); + StringMap::iterator OMI = + Optimizations.find(CalleeName, CalleeName+Callee->getNameLen()); + if (OMI == Optimizations.end()) continue; + + // Set the builder to the instruction after the call. + Builder.SetInsertPoint(BB, I); + + // Try to optimize this call. + Value *Result = OMI->second->OptimizeCall(CI, TD, Builder); + if (Result == 0) continue; + + DEBUG(DOUT << "SimplifyDRuntimeCalls simplified: " << *CI; + DOUT << " into: " << *Result << "\n"); + + // Something changed! + Changed = true; + ++NumSimplified; + + // Inspect the instruction after the call (which was potentially just + // added) next. + I = CI; ++I; + + if (CI != Result && !CI->use_empty()) { + CI->replaceAllUsesWith(Result); + if (!Result->hasName()) + Result->takeName(CI); + } + CI->eraseFromParent(); + } + } + return Changed; +}