diff options
author | Roman Divacky <rdivacky@FreeBSD.org> | 2010-05-04 16:11:02 +0000 |
---|---|---|
committer | Roman Divacky <rdivacky@FreeBSD.org> | 2010-05-04 16:11:02 +0000 |
commit | d7f7719e5e082c0b8ea2182dcbd2242b7834aa26 (patch) | |
tree | 70fbd90da02177c8e6ef82adba9fa8ace285a5e3 /include/llvm/Analysis | |
parent | 9f4a1da9a0a56a0b0a7f8249f34b3cdea6179c41 (diff) |
Notes
Diffstat (limited to 'include/llvm/Analysis')
-rw-r--r-- | include/llvm/Analysis/CallGraph.h | 8 | ||||
-rw-r--r-- | include/llvm/Analysis/DebugInfo.h | 8 | ||||
-rw-r--r-- | include/llvm/Analysis/IVUsers.h | 74 | ||||
-rw-r--r-- | include/llvm/Analysis/InlineCost.h | 20 | ||||
-rw-r--r-- | include/llvm/Analysis/InstructionSimplify.h | 4 | ||||
-rw-r--r-- | include/llvm/Analysis/Lint.h | 52 | ||||
-rw-r--r-- | include/llvm/Analysis/PointerTracking.h | 2 | ||||
-rw-r--r-- | include/llvm/Analysis/ScalarEvolution.h | 29 | ||||
-rw-r--r-- | include/llvm/Analysis/ScalarEvolutionExpander.h | 29 | ||||
-rw-r--r-- | include/llvm/Analysis/ScalarEvolutionNormalization.h | 78 | ||||
-rw-r--r-- | include/llvm/Analysis/ValueTracking.h | 3 | ||||
-rw-r--r-- | include/llvm/Analysis/Verifier.h | 2 |
12 files changed, 231 insertions, 78 deletions
diff --git a/include/llvm/Analysis/CallGraph.h b/include/llvm/Analysis/CallGraph.h index 287fe4faa4f56..a4884edd5bd6b 100644 --- a/include/llvm/Analysis/CallGraph.h +++ b/include/llvm/Analysis/CallGraph.h @@ -187,6 +187,9 @@ public: // CallGraphNode ctor - Create a node for the specified function. inline CallGraphNode(Function *f) : F(f), NumReferences(0) {} + ~CallGraphNode() { + assert(NumReferences == 0 && "Node deleted while references remain"); + } //===--------------------------------------------------------------------- // Accessor methods. @@ -277,6 +280,11 @@ public: /// time, so it should be used sparingly. void replaceCallEdge(CallSite CS, CallSite NewCS, CallGraphNode *NewNode); + /// allReferencesDropped - This is a special function that should only be + /// used by the CallGraph class. + void allReferencesDropped() { + NumReferences = 0; + } }; //===----------------------------------------------------------------------===// diff --git a/include/llvm/Analysis/DebugInfo.h b/include/llvm/Analysis/DebugInfo.h index d68bfa3c0dfed..9b1379d90ae4a 100644 --- a/include/llvm/Analysis/DebugInfo.h +++ b/include/llvm/Analysis/DebugInfo.h @@ -392,6 +392,7 @@ namespace llvm { return getFieldAs<DICompositeType>(13); } unsigned isArtificial() const { return getUnsignedField(14); } + unsigned isOptimized() const; StringRef getFilename() const { if (getVersion() == llvm::LLVMDebugVersion7) @@ -474,6 +475,10 @@ namespace llvm { return getType().isBlockByrefStruct(); } + /// isInlinedFnArgument - Return trule if this variable provides debugging + /// information for an inlined function arguments. + bool isInlinedFnArgument(const Function *CurFn); + /// dump - print variable. void dump() const; }; @@ -638,7 +643,8 @@ namespace llvm { unsigned VK = 0, unsigned VIndex = 0, DIType = DIType(), - bool isArtificial = 0); + bool isArtificial = 0, + bool isOptimized = false); /// CreateSubprogramDefinition - Create new subprogram descriptor for the /// given declaration. diff --git a/include/llvm/Analysis/IVUsers.h b/include/llvm/Analysis/IVUsers.h index dc616ca2fd3a3..578e6aba83385 100644 --- a/include/llvm/Analysis/IVUsers.h +++ b/include/llvm/Analysis/IVUsers.h @@ -16,6 +16,7 @@ #define LLVM_ANALYSIS_IVUSERS_H #include "llvm/Analysis/LoopPass.h" +#include "llvm/Analysis/ScalarEvolutionNormalization.h" #include "llvm/Support/ValueHandle.h" namespace llvm { @@ -26,17 +27,17 @@ class Value; class IVUsers; class ScalarEvolution; class SCEV; +class IVUsers; /// IVStrideUse - Keep track of one use of a strided induction variable. /// The Expr member keeps track of the expression, User is the actual user /// instruction of the operand, and 'OperandValToReplace' is the operand of /// the User that is the use. class IVStrideUse : public CallbackVH, public ilist_node<IVStrideUse> { + friend class IVUsers; public: - IVStrideUse(IVUsers *P, const SCEV *S, const SCEV *Off, - Instruction* U, Value *O) - : CallbackVH(U), Parent(P), Stride(S), Offset(Off), - OperandValToReplace(O), IsUseOfPostIncrementedValue(false) { + IVStrideUse(IVUsers *P, Instruction* U, Value *O) + : CallbackVH(U), Parent(P), OperandValToReplace(O) { } /// getUser - Return the user instruction for this use. @@ -49,28 +50,6 @@ public: setValPtr(NewUser); } - /// getParent - Return a pointer to the IVUsers that owns - /// this IVStrideUse. - IVUsers *getParent() const { return Parent; } - - /// getStride - Return the expression for the stride for the use. - const SCEV *getStride() const { return Stride; } - - /// setStride - Assign a new stride to this use. - void setStride(const SCEV *Val) { - Stride = Val; - } - - /// getOffset - Return the offset to add to a theoretical induction - /// variable that starts at zero and counts up by the stride to compute - /// the value for the use. This always has the same type as the stride. - const SCEV *getOffset() const { return Offset; } - - /// setOffset - Assign a new offset to this use. - void setOffset(const SCEV *Val) { - Offset = Val; - } - /// getOperandValToReplace - Return the Value of the operand in the user /// instruction that this IVStrideUse is representing. Value *getOperandValToReplace() const { @@ -83,37 +62,27 @@ public: OperandValToReplace = Op; } - /// isUseOfPostIncrementedValue - True if this should use the - /// post-incremented version of this IV, not the preincremented version. - /// This can only be set in special cases, such as the terminating setcc - /// instruction for a loop or uses dominated by the loop. - bool isUseOfPostIncrementedValue() const { - return IsUseOfPostIncrementedValue; + /// getPostIncLoops - Return the set of loops for which the expression has + /// been adjusted to use post-inc mode. + const PostIncLoopSet &getPostIncLoops() const { + return PostIncLoops; } - /// setIsUseOfPostIncrmentedValue - set the flag that indicates whether - /// this is a post-increment use. - void setIsUseOfPostIncrementedValue(bool Val) { - IsUseOfPostIncrementedValue = Val; - } + /// transformToPostInc - Transform the expression to post-inc form for the + /// given loop. + void transformToPostInc(const Loop *L); private: /// Parent - a pointer to the IVUsers that owns this IVStrideUse. IVUsers *Parent; - /// Stride - The stride for this use. - const SCEV *Stride; - - /// Offset - The offset to add to the base induction expression. - const SCEV *Offset; - /// OperandValToReplace - The Value of the operand in the user instruction /// that this IVStrideUse is representing. WeakVH OperandValToReplace; - /// IsUseOfPostIncrementedValue - True if this should use the - /// post-incremented version of this IV, not the preincremented version. - bool IsUseOfPostIncrementedValue; + /// PostIncLoops - The set of loops for which Expr has been adjusted to + /// use post-inc mode. This corresponds with SCEVExpander's post-inc concept. + PostIncLoopSet PostIncLoops; /// Deleted - Implementation of CallbackVH virtual function to /// receive notification when the User is deleted. @@ -174,17 +143,16 @@ public: /// return true. Otherwise, return false. bool AddUsersIfInteresting(Instruction *I); - IVStrideUse &AddUser(const SCEV *Stride, const SCEV *Offset, - Instruction *User, Value *Operand); + IVStrideUse &AddUser(Instruction *User, Value *Operand); /// getReplacementExpr - Return a SCEV expression which computes the /// value of the OperandValToReplace of the given IVStrideUse. - const SCEV *getReplacementExpr(const IVStrideUse &U) const; + const SCEV *getReplacementExpr(const IVStrideUse &IU) const; + + /// getExpr - Return the expression for the use. + const SCEV *getExpr(const IVStrideUse &IU) const; - /// getCanonicalExpr - Return a SCEV expression which computes the - /// value of the SCEV of the given IVStrideUse, ignoring the - /// isUseOfPostIncrementedValue flag. - const SCEV *getCanonicalExpr(const IVStrideUse &U) const; + const SCEV *getStride(const IVStrideUse &IU, const Loop *L) const; typedef ilist<IVStrideUse>::iterator iterator; typedef ilist<IVStrideUse>::const_iterator const_iterator; diff --git a/include/llvm/Analysis/InlineCost.h b/include/llvm/Analysis/InlineCost.h index a0c521d7ed3b9..d51dd6cbd6fd0 100644 --- a/include/llvm/Analysis/InlineCost.h +++ b/include/llvm/Analysis/InlineCost.h @@ -1,4 +1,4 @@ -//===- InlineCost.cpp - Cost analysis for inliner ---------------*- C++ -*-===// +//===- InlineCost.h - Cost analysis for inliner -----------------*- C++ -*-===// // // The LLVM Compiler Infrastructure // @@ -16,9 +16,9 @@ #include <cassert> #include <climits> -#include <map> #include <vector> #include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/ValueMap.h" namespace llvm { @@ -165,7 +165,9 @@ namespace llvm { void analyzeFunction(Function *F); }; - std::map<const Function *, FunctionInfo> CachedFunctionInfo; + // The Function* for a function can be changed (by ArgumentPromotion); + // the ValueMap will update itself when this happens. + ValueMap<const Function *, FunctionInfo> CachedFunctionInfo; public: @@ -174,6 +176,14 @@ namespace llvm { /// InlineCost getInlineCost(CallSite CS, SmallPtrSet<const Function *, 16> &NeverInline); + /// getCalledFunction - The heuristic used to determine if we should inline + /// the function call or not. The callee is explicitly specified, to allow + /// you to calculate the cost of inlining a function via a pointer. The + /// result assumes that the inlined version will always be used. You should + /// weight it yourself in cases where this callee will not always be called. + InlineCost getInlineCost(CallSite CS, + Function *Callee, + SmallPtrSet<const Function *, 16> &NeverInline); /// getInlineFudgeFactor - Return a > 1.0 factor if the inliner should use a /// higher threshold to determine if the function call should be inlined. @@ -189,6 +199,10 @@ namespace llvm { /// eliminated. void growCachedCostInfo(Function* Caller, Function* Callee); }; + + /// callIsSmall - If a call is likely to lower to a single target instruction, + /// or is otherwise deemed small return true. + bool callIsSmall(const Function *Callee); } #endif diff --git a/include/llvm/Analysis/InstructionSimplify.h b/include/llvm/Analysis/InstructionSimplify.h index 13314e6ea0e5e..f47e740a741f0 100644 --- a/include/llvm/Analysis/InstructionSimplify.h +++ b/include/llvm/Analysis/InstructionSimplify.h @@ -46,6 +46,10 @@ namespace llvm { Value *SimplifyFCmpInst(unsigned Predicate, Value *LHS, Value *RHS, const TargetData *TD = 0); + /// SimplifySelectInst - Given operands for a SelectInst, see if we can fold + /// the result. If not, this returns null. + Value *SimplifySelectInst(Value *Cond, Value *TrueVal, Value *FalseVal, + const TargetData *TD = 0); /// SimplifyGEPInst - Given operands for an GetElementPtrInst, see if we can /// fold the result. If not, this returns null. diff --git a/include/llvm/Analysis/Lint.h b/include/llvm/Analysis/Lint.h new file mode 100644 index 0000000000000..2f0136608d3c8 --- /dev/null +++ b/include/llvm/Analysis/Lint.h @@ -0,0 +1,52 @@ +//===-- llvm/Analysis/Lint.h - LLVM IR Lint ---------------------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file defines lint interfaces that can be used for some sanity checking +// of input to the system, and for checking that transformations +// haven't done something bad. In contrast to the Verifier, the Lint checker +// checks for undefined behavior or constructions with likely unintended +// behavior. +// +// To see what specifically is checked, look at Lint.cpp +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_ANALYSIS_LINT_H +#define LLVM_ANALYSIS_LINT_H + +#include <string> + +namespace llvm { + +class FunctionPass; +class Module; +class Function; + +/// @brief Create a lint pass. +/// +/// Check a module or function. +FunctionPass *createLintPass(); + +/// @brief Check a module. +/// +/// This should only be used for debugging, because it plays games with +/// PassManagers and stuff. +void lintModule( + const Module &M, ///< The module to be checked + std::string *ErrorInfo = 0 ///< Information about failures. +); + +// lintFunction - Check a function. +void lintFunction( + const Function &F ///< The function to be checked +); + +} // End llvm namespace + +#endif diff --git a/include/llvm/Analysis/PointerTracking.h b/include/llvm/Analysis/PointerTracking.h index a14bbf0290ea5..6c4f838430b63 100644 --- a/include/llvm/Analysis/PointerTracking.h +++ b/include/llvm/Analysis/PointerTracking.h @@ -27,7 +27,7 @@ #ifndef LLVM_ANALYSIS_POINTERTRACKING_H #define LLVM_ANALYSIS_POINTERTRACKING_H -#include "llvm/ADT/SmallSet.h" +#include "llvm/ADT/SmallPtrSet.h" #include "llvm/Analysis/Dominators.h" #include "llvm/Instructions.h" #include "llvm/Pass.h" diff --git a/include/llvm/Analysis/ScalarEvolution.h b/include/llvm/Analysis/ScalarEvolution.h index ab13a9dfa4e56..d3a8d8f4fe511 100644 --- a/include/llvm/Analysis/ScalarEvolution.h +++ b/include/llvm/Analysis/ScalarEvolution.h @@ -351,7 +351,8 @@ namespace llvm { /// (which may not be an immediate predecessor) which has exactly one /// successor from which BB is reachable, or null if no such block is /// found. - BasicBlock* getPredecessorWithUniqueSuccessorForBB(BasicBlock *BB); + std::pair<BasicBlock *, BasicBlock *> + getPredecessorWithUniqueSuccessorForBB(BasicBlock *BB); /// isImpliedCond - Test whether the condition described by Pred, LHS, /// and RHS is true whenever the given Cond value evaluates to true. @@ -380,6 +381,13 @@ namespace llvm { Constant *getConstantEvolutionLoopExitValue(PHINode *PN, const APInt& BEs, const Loop *L); + /// isKnownPredicateWithRanges - Test if the given expression is known to + /// satisfy the condition described by Pred and the known constant ranges + /// of LHS and RHS. + /// + bool isKnownPredicateWithRanges(ICmpInst::Predicate Pred, + const SCEV *LHS, const SCEV *RHS); + public: static char ID; // Pass identification, replacement for typeid ScalarEvolution(); @@ -554,11 +562,11 @@ namespace llvm { /// getSCEVAtScope(getSCEV(V), L). const SCEV *getSCEVAtScope(Value *V, const Loop *L); - /// isLoopGuardedByCond - Test whether entry to the loop is protected by - /// a conditional between LHS and RHS. This is used to help avoid max + /// isLoopEntryGuardedByCond - Test whether entry to the loop is protected + /// by a conditional between LHS and RHS. This is used to help avoid max /// expressions in loop trip counts, and to eliminate casts. - bool isLoopGuardedByCond(const Loop *L, ICmpInst::Predicate Pred, - const SCEV *LHS, const SCEV *RHS); + bool isLoopEntryGuardedByCond(const Loop *L, ICmpInst::Predicate Pred, + const SCEV *LHS, const SCEV *RHS); /// isLoopBackedgeGuardedByCond - Test whether the backedge of the loop is /// protected by a conditional between LHS and RHS. This is used to @@ -636,12 +644,21 @@ namespace llvm { /// bool isKnownNonZero(const SCEV *S); - /// isKnownNonZero - Test if the given expression is known to satisfy + /// isKnownPredicate - Test if the given expression is known to satisfy /// the condition described by Pred, LHS, and RHS. /// bool isKnownPredicate(ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS); + /// SimplifyICmpOperands - Simplify LHS and RHS in a comparison with + /// predicate Pred. Return true iff any changes were made. If the + /// operands are provably equal or inequal, LHS and RHS are set to + /// the same value and Pred is set to either ICMP_EQ or ICMP_NE. + /// + bool SimplifyICmpOperands(ICmpInst::Predicate &Pred, + const SCEV *&LHS, + const SCEV *&RHS); + virtual bool runOnFunction(Function &F); virtual void releaseMemory(); virtual void getAnalysisUsage(AnalysisUsage &AU) const; diff --git a/include/llvm/Analysis/ScalarEvolutionExpander.h b/include/llvm/Analysis/ScalarEvolutionExpander.h index dc9b73bd566d7..baf6946b8cf81 100644 --- a/include/llvm/Analysis/ScalarEvolutionExpander.h +++ b/include/llvm/Analysis/ScalarEvolutionExpander.h @@ -15,6 +15,7 @@ #define LLVM_ANALYSIS_SCALAREVOLUTION_EXPANDER_H #include "llvm/Analysis/ScalarEvolutionExpressions.h" +#include "llvm/Analysis/ScalarEvolutionNormalization.h" #include "llvm/Support/IRBuilder.h" #include "llvm/Support/TargetFolder.h" #include <set> @@ -32,12 +33,12 @@ namespace llvm { InsertedExpressions; std::set<Value*> InsertedValues; - /// PostIncLoop - When non-null, expanded addrecs referring to the given - /// loop expanded in post-inc mode. For example, expanding {1,+,1}<L> in - /// post-inc mode returns the add instruction that adds one to the phi - /// for {0,+,1}<L>, as opposed to a new phi starting at 1. This is only - /// supported in non-canonical mode. - const Loop *PostIncLoop; + /// PostIncLoops - Addrecs referring to any of the given loops are expanded + /// in post-inc mode. For example, expanding {1,+,1}<L> in post-inc mode + /// returns the add instruction that adds one to the phi for {0,+,1}<L>, + /// as opposed to a new phi starting at 1. This is only supported in + /// non-canonical mode. + PostIncLoopSet PostIncLoops; /// IVIncInsertPos - When this is non-null, addrecs expanded in the /// loop it indicates should be inserted with increments at @@ -62,7 +63,7 @@ namespace llvm { public: /// SCEVExpander - Construct a SCEVExpander in "canonical" mode. explicit SCEVExpander(ScalarEvolution &se) - : SE(se), PostIncLoop(0), IVIncInsertLoop(0), CanonicalMode(true), + : SE(se), IVIncInsertLoop(0), CanonicalMode(true), Builder(se.getContext(), TargetFolder(se.TD)) {} /// clear - Erase the contents of the InsertedExpressions map so that users @@ -89,14 +90,18 @@ namespace llvm { IVIncInsertPos = Pos; } - /// setPostInc - If L is non-null, enable post-inc expansion for addrecs - /// referring to the given loop. If L is null, disable post-inc expansion - /// completely. Post-inc expansion is only supported in non-canonical + /// setPostInc - Enable post-inc expansion for addrecs referring to the + /// given loops. Post-inc expansion is only supported in non-canonical /// mode. - void setPostInc(const Loop *L) { + void setPostInc(const PostIncLoopSet &L) { assert(!CanonicalMode && "Post-inc expansion is not supported in CanonicalMode"); - PostIncLoop = L; + PostIncLoops = L; + } + + /// clearPostInc - Disable all post-inc expansion. + void clearPostInc() { + PostIncLoops.clear(); } /// disableCanonicalMode - Disable the behavior of expanding expressions in diff --git a/include/llvm/Analysis/ScalarEvolutionNormalization.h b/include/llvm/Analysis/ScalarEvolutionNormalization.h new file mode 100644 index 0000000000000..342e5937891a7 --- /dev/null +++ b/include/llvm/Analysis/ScalarEvolutionNormalization.h @@ -0,0 +1,78 @@ +//===- llvm/Analysis/ScalarEvolutionNormalization.h - See below -*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file defines utilities for working with "normalized" ScalarEvolution +// expressions. +// +// The following example illustrates post-increment uses and how normalized +// expressions help. +// +// for (i=0; i!=n; ++i) { +// ... +// } +// use(i); +// +// While the expression for most uses of i inside the loop is {0,+,1}<%L>, the +// expression for the use of i outside the loop is {1,+,1}<%L>, since i is +// incremented at the end of the loop body. This is inconveient, since it +// suggests that we need two different induction variables, one that starts +// at 0 and one that starts at 1. We'd prefer to be able to think of these as +// the same induction variable, with uses inside the loop using the +// "pre-incremented" value, and uses after the loop using the +// "post-incremented" value. +// +// Expressions for post-incremented uses are represented as an expression +// paired with a set of loops for which the expression is in "post-increment" +// mode (there may be multiple loops). +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_ANALYSIS_SCALAREVOLUTION_NORMALIZATION_H +#define LLVM_ANALYSIS_SCALAREVOLUTION_NORMALIZATION_H + +#include "llvm/ADT/SmallPtrSet.h" + +namespace llvm { + +class Instruction; +class DominatorTree; +class Loop; +class ScalarEvolution; +class SCEV; +class Value; + +/// TransformKind - Different types of transformations that +/// TransformForPostIncUse can do. +enum TransformKind { + /// Normalize - Normalize according to the given loops. + Normalize, + /// NormalizeAutodetect - Detect post-inc opportunities on new expressions, + /// update the given loop set, and normalize. + NormalizeAutodetect, + /// Denormalize - Perform the inverse transform on the expression with the + /// given loop set. + Denormalize +}; + +/// PostIncLoopSet - A set of loops. +typedef SmallPtrSet<const Loop *, 2> PostIncLoopSet; + +/// TransformForPostIncUse - Transform the given expression according to the +/// given transformation kind. +const SCEV *TransformForPostIncUse(TransformKind Kind, + const SCEV *S, + Instruction *User, + Value *OperandValToReplace, + PostIncLoopSet &Loops, + ScalarEvolution &SE, + DominatorTree &DT); + +} + +#endif diff --git a/include/llvm/Analysis/ValueTracking.h b/include/llvm/Analysis/ValueTracking.h index 0791b7bd4c14d..d58089748413d 100644 --- a/include/llvm/Analysis/ValueTracking.h +++ b/include/llvm/Analysis/ValueTracking.h @@ -122,7 +122,8 @@ namespace llvm { /// StopAtNul is set to true (the default), the returned string is truncated /// by a nul character in the global. If StopAtNul is false, the nul /// character is included in the result string. - bool GetConstantStringInfo(Value *V, std::string &Str, uint64_t Offset = 0, + bool GetConstantStringInfo(const Value *V, std::string &Str, + uint64_t Offset = 0, bool StopAtNul = true); /// GetStringLength - If we can compute the length of the string pointed to by diff --git a/include/llvm/Analysis/Verifier.h b/include/llvm/Analysis/Verifier.h index a6b2a6df21af1..ce8aeef07645b 100644 --- a/include/llvm/Analysis/Verifier.h +++ b/include/llvm/Analysis/Verifier.h @@ -1,4 +1,4 @@ -//===-- llvm/Analysis/Verifier.h - Module Verifier --------------*- C++ -*-===// +//===-- llvm/Analysis/Verifier.h - LLVM IR Verifier -------------*- C++ -*-===// // // The LLVM Compiler Infrastructure // |