| //===- OptimizeChecks.cpp - Optimize SAFECode Checks ---------------------- --// |
| // |
| // The SAFECode Compiler |
| // |
| // This file was developed by the LLVM research group and is distributed under |
| // the University of Illinois Open Source License. See LICENSE.TXT for details. |
| // |
| //===----------------------------------------------------------------------===// |
| // |
| // This pass performs optimizations on the SAFECode checks. |
| // |
| //===----------------------------------------------------------------------===// |
| |
| #define DEBUG_TYPE "opt-safecode" |
| |
| #include "llvm/ADT/Statistic.h" |
| #include "llvm/Constants.h" |
| #include "llvm/Instruction.h" |
| #include "llvm/Instructions.h" |
| |
| #include "safecode/OptimizeChecks.h" |
| #include "SCUtils.h" |
| |
| #include "dsa/DSSupport.h" |
| |
| #include <iostream> |
| #include <set> |
| |
| char NAMESPACE_SC::OptimizeChecks::ID = 0; |
| |
| namespace { |
| STATISTIC (Removed, "Number of Bounds Checks Removed"); |
| } |
| |
| NAMESPACE_SC_BEGIN |
| |
| static RegisterPass<OptimizeChecks> X ("opt-checks", "Optimize run-time checks", true); |
| |
| |
| // |
| // Function: onlyUsedInCompares() |
| // |
| // Description: |
| // Determine whether the result of the given instruction is only used in |
| // comparisons. |
| // |
| // Return value: |
| // true - The instruction is only used in comparisons. |
| // false - The instruction has some other use besides comparisons. |
| // |
| // Preconditions: |
| // This function requires that the intrinPass and GEPCheckingFunctions |
| // variables be initialized. |
| // |
| bool |
| OptimizeChecks::onlyUsedInCompares (Value * Val) { |
| // The worklist |
| std::vector<Value *> Worklist; |
| |
| // The set of processed values |
| std::set<Value *> Processed; |
| |
| // |
| // Initialize the worklist. |
| // |
| Worklist.push_back(Val); |
| |
| // |
| // Process each item in the work list. |
| // |
| while (Worklist.size()) { |
| Value * V = Worklist.back(); |
| Worklist.pop_back(); |
| |
| // |
| // Check whether we have already processed this value. If not, mark it as |
| // processed. |
| // |
| if (Processed.find (V) != Processed.end()) continue; |
| Processed.insert (V); |
| |
| // |
| // Scan through all the uses of this value. Some uses may be safe. Other |
| // uses may generate uses we need to check. Still others are known-bad |
| // uses. Handle each appropriately. |
| // |
| for (Value::use_iterator U = V->use_begin(); U != V->use_end(); ++U) { |
| // Compares are okay |
| if (isa<CmpInst>(U)) continue; |
| |
| // Casts, Phi nodes, and GEPs require that we check the result, too. |
| if (isa<CastInst>(U) || |
| isa<PHINode>(U) || |
| isa<BinaryOperator>(U) || |
| isa<SelectInst>(U) || |
| isa<SwitchInst>(U) || |
| isa<GetElementPtrInst>(U)) { |
| Worklist.push_back(*U); |
| continue; |
| } |
| |
| // Calls to run-time functions are okay; others are not. |
| if (CallInst * CI = dyn_cast<CallInst>(U)) { |
| if (Value * V = dyn_cast<Value>(CI)) |
| if (intrinPass->isSCIntrinsicWithFlags(V, InsertSCIntrinsic::SC_INTRINSIC_CHECK)) continue; |
| } |
| |
| // |
| // We don't know what this is; just assume it is bad. |
| // |
| return false; |
| } |
| } |
| |
| // |
| // All uses are comparisons. Return true. |
| // |
| return true; |
| } |
| |
| // |
| // Method: processFunction() |
| // |
| // Description: |
| // Look for calls of the specified function (which is a SAFECode run-time |
| // check), determine whether the call can be eliminated, and eliminate it |
| // if possible. |
| // |
| // Inputs: |
| // F - The function for the SAFECode run-time check. |
| // |
| // Return value: |
| // false - No modifications were made to the Module. |
| // true - One or more modifications were made to the module. |
| // |
| bool |
| OptimizeChecks::processFunction (Function * F) { |
| // |
| // Iterate though all calls to the function and search for pointers that are |
| // checked but only used in comparisons. If so, then schedule the check |
| // (i.e., the call) for removal. |
| // |
| bool modified = false; |
| std::vector<Instruction *> CallsToDelete; |
| for (Value::use_iterator FU = F->use_begin(); FU != F->use_end(); ++FU) { |
| // |
| // We are only concerned about call instructions; any other use is of |
| // no interest to the organization. |
| // |
| if (CallInst * CI = dyn_cast<CallInst>(FU)) { |
| // |
| // If the call instruction has any uses, we cannot remove it. |
| // |
| if (CI->use_begin() != CI->use_end()) continue; |
| |
| // |
| // Get the operand that needs to be replaced as well as the operand |
| // with all of the casts peeled away. Increment the operand index by |
| // one because a call instruction's first operand is the function to |
| // call. |
| // |
| std::set<Value *> Chain; |
| Value * Operand = peelCasts (intrinPass->getValuePointer (CI), Chain); |
| |
| // |
| // If the operand is only used in comparisons, mark the run-time check |
| // for removal. |
| // |
| if (onlyUsedInCompares (Operand)) { |
| CallsToDelete.push_back (CI); |
| modified = true; |
| } |
| } |
| } |
| |
| // |
| // Update the statistics |
| // |
| Removed += CallsToDelete.size(); |
| |
| // |
| // Remove all of the instructions that we found to be unnecessary. |
| // |
| while (CallsToDelete.size()) { |
| Instruction * I = CallsToDelete.back(); |
| CallsToDelete.pop_back(); |
| I->eraseFromParent(); |
| } |
| |
| return modified; |
| } |
| |
| bool |
| OptimizeChecks::runOnModule (Module & M) { |
| // |
| // Get prerequisite analysis results. |
| // |
| intrinPass = &getAnalysis<InsertSCIntrinsic>(); |
| |
| InsertSCIntrinsic::intrinsic_const_iterator i, e; |
| for (i = intrinPass->intrinsic_begin(), e = intrinPass->intrinsic_end(); i != e; ++i) { |
| if (i->flag & InsertSCIntrinsic::SC_INTRINSIC_BOUNDSCHECK) |
| GEPCheckingFunctions.push_back (i->F); |
| } |
| |
| // |
| // Optimize all of the run-time GEP checks. |
| // |
| bool modified = false; |
| while (GEPCheckingFunctions.size()) { |
| // Remove a function from the set of functions to process |
| Function * F = GEPCheckingFunctions.back(); |
| GEPCheckingFunctions.pop_back(); |
| |
| // |
| // Transform the function into its debug version. |
| // |
| modified |= processFunction (F); |
| } |
| |
| return modified; |
| } |
| |
| NAMESPACE_SC_END |
| |