summaryrefslogtreecommitdiff
path: root/include/llvm/Analysis
diff options
context:
space:
mode:
authorEd Schouten <ed@FreeBSD.org>2009-06-02 17:52:33 +0000
committerEd Schouten <ed@FreeBSD.org>2009-06-02 17:52:33 +0000
commit009b1c42aa6266385f2c37e227516b24077e6dd7 (patch)
tree64ba909838c23261cace781ece27d106134ea451 /include/llvm/Analysis
downloadsrc-test2-009b1c42aa6266385f2c37e227516b24077e6dd7.tar.gz
src-test2-009b1c42aa6266385f2c37e227516b24077e6dd7.zip
Notes
Diffstat (limited to 'include/llvm/Analysis')
-rw-r--r--include/llvm/Analysis/AliasAnalysis.h363
-rw-r--r--include/llvm/Analysis/AliasSetTracker.h393
-rw-r--r--include/llvm/Analysis/CFGPrinter.h24
-rw-r--r--include/llvm/Analysis/CallGraph.h326
-rw-r--r--include/llvm/Analysis/CaptureTracking.h29
-rw-r--r--include/llvm/Analysis/ConstantFolding.h73
-rw-r--r--include/llvm/Analysis/ConstantsScanner.h93
-rw-r--r--include/llvm/Analysis/DebugInfo.h555
-rw-r--r--include/llvm/Analysis/DominatorInternals.h363
-rw-r--r--include/llvm/Analysis/Dominators.h1055
-rw-r--r--include/llvm/Analysis/FindUsedTypes.h65
-rw-r--r--include/llvm/Analysis/IVUsers.h235
-rw-r--r--include/llvm/Analysis/Interval.h154
-rw-r--r--include/llvm/Analysis/IntervalIterator.h258
-rw-r--r--include/llvm/Analysis/IntervalPartition.h112
-rw-r--r--include/llvm/Analysis/LibCallAliasAnalysis.h61
-rw-r--r--include/llvm/Analysis/LibCallSemantics.h166
-rw-r--r--include/llvm/Analysis/LiveValues.h103
-rw-r--r--include/llvm/Analysis/LoopInfo.h1095
-rw-r--r--include/llvm/Analysis/LoopPass.h150
-rw-r--r--include/llvm/Analysis/LoopVR.h90
-rw-r--r--include/llvm/Analysis/MemoryDependenceAnalysis.h287
-rw-r--r--include/llvm/Analysis/Passes.h128
-rw-r--r--include/llvm/Analysis/PostDominators.h98
-rw-r--r--include/llvm/Analysis/ProfileInfo.h67
-rw-r--r--include/llvm/Analysis/ProfileInfoLoader.h89
-rw-r--r--include/llvm/Analysis/ProfileInfoTypes.h28
-rw-r--r--include/llvm/Analysis/ScalarEvolution.h546
-rw-r--r--include/llvm/Analysis/ScalarEvolutionExpander.h147
-rw-r--r--include/llvm/Analysis/ScalarEvolutionExpressions.h588
-rw-r--r--include/llvm/Analysis/SparsePropagation.h200
-rw-r--r--include/llvm/Analysis/Trace.h120
-rw-r--r--include/llvm/Analysis/ValueTracking.h87
-rw-r--r--include/llvm/Analysis/Verifier.h75
34 files changed, 8223 insertions, 0 deletions
diff --git a/include/llvm/Analysis/AliasAnalysis.h b/include/llvm/Analysis/AliasAnalysis.h
new file mode 100644
index 000000000000..ba040e1393bf
--- /dev/null
+++ b/include/llvm/Analysis/AliasAnalysis.h
@@ -0,0 +1,363 @@
+//===- llvm/Analysis/AliasAnalysis.h - Alias Analysis Interface -*- 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 the generic AliasAnalysis interface, which is used as the
+// common interface used by all clients of alias analysis information, and
+// implemented by all alias analysis implementations. Mod/Ref information is
+// also captured by this interface.
+//
+// Implementations of this interface must implement the various virtual methods,
+// which automatically provides functionality for the entire suite of client
+// APIs.
+//
+// This API represents memory as a (Pointer, Size) pair. The Pointer component
+// specifies the base memory address of the region, the Size specifies how large
+// of an area is being queried. If Size is 0, two pointers only alias if they
+// are exactly equal. If size is greater than zero, but small, the two pointers
+// alias if the areas pointed to overlap. If the size is very large (ie, ~0U),
+// then the two pointers alias if they may be pointing to components of the same
+// memory object. Pointers that point to two completely different objects in
+// memory never alias, regardless of the value of the Size component.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ANALYSIS_ALIAS_ANALYSIS_H
+#define LLVM_ANALYSIS_ALIAS_ANALYSIS_H
+
+#include "llvm/Support/CallSite.h"
+#include "llvm/System/IncludeFile.h"
+#include <vector>
+
+namespace llvm {
+
+class LoadInst;
+class StoreInst;
+class VAArgInst;
+class TargetData;
+class Pass;
+class AnalysisUsage;
+
+class AliasAnalysis {
+protected:
+ const TargetData *TD;
+ AliasAnalysis *AA; // Previous Alias Analysis to chain to.
+
+ /// InitializeAliasAnalysis - Subclasses must call this method to initialize
+ /// the AliasAnalysis interface before any other methods are called. This is
+ /// typically called by the run* methods of these subclasses. This may be
+ /// called multiple times.
+ ///
+ void InitializeAliasAnalysis(Pass *P);
+
+ /// getAnalysisUsage - All alias analysis implementations should invoke this
+ /// directly (using AliasAnalysis::getAnalysisUsage(AU)) to make sure that
+ /// TargetData is required by the pass.
+ virtual void getAnalysisUsage(AnalysisUsage &AU) const;
+
+public:
+ static char ID; // Class identification, replacement for typeinfo
+ AliasAnalysis() : TD(0), AA(0) {}
+ virtual ~AliasAnalysis(); // We want to be subclassed
+
+ /// getTargetData - Every alias analysis implementation depends on the size of
+ /// data items in the current Target. This provides a uniform way to handle
+ /// it.
+ ///
+ const TargetData &getTargetData() const { return *TD; }
+
+ //===--------------------------------------------------------------------===//
+ /// Alias Queries...
+ ///
+
+ /// Alias analysis result - Either we know for sure that it does not alias, we
+ /// know for sure it must alias, or we don't know anything: The two pointers
+ /// _might_ alias. This enum is designed so you can do things like:
+ /// if (AA.alias(P1, P2)) { ... }
+ /// to check to see if two pointers might alias.
+ ///
+ enum AliasResult { NoAlias = 0, MayAlias = 1, MustAlias = 2 };
+
+ /// alias - The main low level interface to the alias analysis implementation.
+ /// Returns a Result indicating whether the two pointers are aliased to each
+ /// other. This is the interface that must be implemented by specific alias
+ /// analysis implementations.
+ ///
+ virtual AliasResult alias(const Value *V1, unsigned V1Size,
+ const Value *V2, unsigned V2Size);
+
+ /// getMustAliases - If there are any pointers known that must alias this
+ /// pointer, return them now. This allows alias-set based alias analyses to
+ /// perform a form a value numbering (which is exposed by load-vn). If an
+ /// alias analysis supports this, it should ADD any must aliased pointers to
+ /// the specified vector.
+ ///
+ virtual void getMustAliases(Value *P, std::vector<Value*> &RetVals);
+
+ /// pointsToConstantMemory - If the specified pointer is known to point into
+ /// constant global memory, return true. This allows disambiguation of store
+ /// instructions from constant pointers.
+ ///
+ virtual bool pointsToConstantMemory(const Value *P);
+
+ //===--------------------------------------------------------------------===//
+ /// Simple mod/ref information...
+ ///
+
+ /// ModRefResult - Represent the result of a mod/ref query. Mod and Ref are
+ /// bits which may be or'd together.
+ ///
+ enum ModRefResult { NoModRef = 0, Ref = 1, Mod = 2, ModRef = 3 };
+
+
+ /// ModRefBehavior - Summary of how a function affects memory in the program.
+ /// Loads from constant globals are not considered memory accesses for this
+ /// interface. Also, functions may freely modify stack space local to their
+ /// invocation without having to report it through these interfaces.
+ enum ModRefBehavior {
+ // DoesNotAccessMemory - This function does not perform any non-local loads
+ // or stores to memory.
+ //
+ // This property corresponds to the GCC 'const' attribute.
+ DoesNotAccessMemory,
+
+ // AccessesArguments - This function accesses function arguments in well
+ // known (possibly volatile) ways, but does not access any other memory.
+ //
+ // Clients may use the Info parameter of getModRefBehavior to get specific
+ // information about how pointer arguments are used.
+ AccessesArguments,
+
+ // AccessesArgumentsAndGlobals - This function has accesses function
+ // arguments and global variables well known (possibly volatile) ways, but
+ // does not access any other memory.
+ //
+ // Clients may use the Info parameter of getModRefBehavior to get specific
+ // information about how pointer arguments are used.
+ AccessesArgumentsAndGlobals,
+
+ // OnlyReadsMemory - This function does not perform any non-local stores or
+ // volatile loads, but may read from any memory location.
+ //
+ // This property corresponds to the GCC 'pure' attribute.
+ OnlyReadsMemory,
+
+ // UnknownModRefBehavior - This indicates that the function could not be
+ // classified into one of the behaviors above.
+ UnknownModRefBehavior
+ };
+
+ /// PointerAccessInfo - This struct is used to return results for pointers,
+ /// globals, and the return value of a function.
+ struct PointerAccessInfo {
+ /// V - The value this record corresponds to. This may be an Argument for
+ /// the function, a GlobalVariable, or null, corresponding to the return
+ /// value for the function.
+ Value *V;
+
+ /// ModRefInfo - Whether the pointer is loaded or stored to/from.
+ ///
+ ModRefResult ModRefInfo;
+
+ /// AccessType - Specific fine-grained access information for the argument.
+ /// If none of these classifications is general enough, the
+ /// getModRefBehavior method should not return AccessesArguments*. If a
+ /// record is not returned for a particular argument, the argument is never
+ /// dead and never dereferenced.
+ enum AccessType {
+ /// ScalarAccess - The pointer is dereferenced.
+ ///
+ ScalarAccess,
+
+ /// ArrayAccess - The pointer is indexed through as an array of elements.
+ ///
+ ArrayAccess,
+
+ /// ElementAccess ?? P->F only?
+
+ /// CallsThrough - Indirect calls are made through the specified function
+ /// pointer.
+ CallsThrough
+ };
+ };
+
+ /// getModRefBehavior - Return the behavior when calling the given call site.
+ virtual ModRefBehavior getModRefBehavior(CallSite CS,
+ std::vector<PointerAccessInfo> *Info = 0);
+
+ /// getModRefBehavior - Return the behavior when calling the given function.
+ /// For use when the call site is not known.
+ virtual ModRefBehavior getModRefBehavior(Function *F,
+ std::vector<PointerAccessInfo> *Info = 0);
+
+ /// doesNotAccessMemory - If the specified call is known to never read or
+ /// write memory, return true. If the call only reads from known-constant
+ /// memory, it is also legal to return true. Calls that unwind the stack
+ /// are legal for this predicate.
+ ///
+ /// Many optimizations (such as CSE and LICM) can be performed on such calls
+ /// without worrying about aliasing properties, and many calls have this
+ /// property (e.g. calls to 'sin' and 'cos').
+ ///
+ /// This property corresponds to the GCC 'const' attribute.
+ ///
+ bool doesNotAccessMemory(CallSite CS) {
+ return getModRefBehavior(CS) == DoesNotAccessMemory;
+ }
+
+ /// doesNotAccessMemory - If the specified function is known to never read or
+ /// write memory, return true. For use when the call site is not known.
+ ///
+ bool doesNotAccessMemory(Function *F) {
+ return getModRefBehavior(F) == DoesNotAccessMemory;
+ }
+
+ /// onlyReadsMemory - If the specified call is known to only read from
+ /// non-volatile memory (or not access memory at all), return true. Calls
+ /// that unwind the stack are legal for this predicate.
+ ///
+ /// This property allows many common optimizations to be performed in the
+ /// absence of interfering store instructions, such as CSE of strlen calls.
+ ///
+ /// This property corresponds to the GCC 'pure' attribute.
+ ///
+ bool onlyReadsMemory(CallSite CS) {
+ ModRefBehavior MRB = getModRefBehavior(CS);
+ return MRB == DoesNotAccessMemory || MRB == OnlyReadsMemory;
+ }
+
+ /// onlyReadsMemory - If the specified function is known to only read from
+ /// non-volatile memory (or not access memory at all), return true. For use
+ /// when the call site is not known.
+ ///
+ bool onlyReadsMemory(Function *F) {
+ ModRefBehavior MRB = getModRefBehavior(F);
+ return MRB == DoesNotAccessMemory || MRB == OnlyReadsMemory;
+ }
+
+
+ /// getModRefInfo - Return information about whether or not an instruction may
+ /// read or write memory specified by the pointer operand. An instruction
+ /// that doesn't read or write memory may be trivially LICM'd for example.
+
+ /// getModRefInfo (for call sites) - Return whether information about whether
+ /// a particular call site modifies or reads the memory specified by the
+ /// pointer.
+ ///
+ virtual ModRefResult getModRefInfo(CallSite CS, Value *P, unsigned Size);
+
+ /// getModRefInfo - Return information about whether two call sites may refer
+ /// to the same set of memory locations. This function returns NoModRef if
+ /// the two calls refer to disjoint memory locations, Ref if CS1 reads memory
+ /// written by CS2, Mod if CS1 writes to memory read or written by CS2, or
+ /// ModRef if CS1 might read or write memory accessed by CS2.
+ ///
+ virtual ModRefResult getModRefInfo(CallSite CS1, CallSite CS2);
+
+ /// hasNoModRefInfoForCalls - Return true if the analysis has no mod/ref
+ /// information for pairs of function calls (other than "pure" and "const"
+ /// functions). This can be used by clients to avoid many pointless queries.
+ /// Remember that if you override this and chain to another analysis, you must
+ /// make sure that it doesn't have mod/ref info either.
+ ///
+ virtual bool hasNoModRefInfoForCalls() const;
+
+public:
+ /// Convenience functions...
+ ModRefResult getModRefInfo(LoadInst *L, Value *P, unsigned Size);
+ ModRefResult getModRefInfo(StoreInst *S, Value *P, unsigned Size);
+ ModRefResult getModRefInfo(CallInst *C, Value *P, unsigned Size) {
+ return getModRefInfo(CallSite(C), P, Size);
+ }
+ ModRefResult getModRefInfo(InvokeInst *I, Value *P, unsigned Size) {
+ return getModRefInfo(CallSite(I), P, Size);
+ }
+ ModRefResult getModRefInfo(VAArgInst* I, Value* P, unsigned Size) {
+ return AliasAnalysis::ModRef;
+ }
+ ModRefResult getModRefInfo(Instruction *I, Value *P, unsigned Size) {
+ switch (I->getOpcode()) {
+ case Instruction::VAArg: return getModRefInfo((VAArgInst*)I, P, Size);
+ case Instruction::Load: return getModRefInfo((LoadInst*)I, P, Size);
+ case Instruction::Store: return getModRefInfo((StoreInst*)I, P, Size);
+ case Instruction::Call: return getModRefInfo((CallInst*)I, P, Size);
+ case Instruction::Invoke: return getModRefInfo((InvokeInst*)I, P, Size);
+ default: return NoModRef;
+ }
+ }
+
+ //===--------------------------------------------------------------------===//
+ /// Higher level methods for querying mod/ref information.
+ ///
+
+ /// canBasicBlockModify - Return true if it is possible for execution of the
+ /// specified basic block to modify the value pointed to by Ptr.
+ ///
+ bool canBasicBlockModify(const BasicBlock &BB, const Value *P, unsigned Size);
+
+ /// canInstructionRangeModify - Return true if it is possible for the
+ /// execution of the specified instructions to modify the value pointed to by
+ /// Ptr. The instructions to consider are all of the instructions in the
+ /// range of [I1,I2] INCLUSIVE. I1 and I2 must be in the same basic block.
+ ///
+ bool canInstructionRangeModify(const Instruction &I1, const Instruction &I2,
+ const Value *Ptr, unsigned Size);
+
+ //===--------------------------------------------------------------------===//
+ /// Methods that clients should call when they transform the program to allow
+ /// alias analyses to update their internal data structures. Note that these
+ /// methods may be called on any instruction, regardless of whether or not
+ /// they have pointer-analysis implications.
+ ///
+
+ /// deleteValue - This method should be called whenever an LLVM Value is
+ /// deleted from the program, for example when an instruction is found to be
+ /// redundant and is eliminated.
+ ///
+ virtual void deleteValue(Value *V);
+
+ /// copyValue - This method should be used whenever a preexisting value in the
+ /// program is copied or cloned, introducing a new value. Note that analysis
+ /// implementations should tolerate clients that use this method to introduce
+ /// the same value multiple times: if the analysis already knows about a
+ /// value, it should ignore the request.
+ ///
+ virtual void copyValue(Value *From, Value *To);
+
+ /// replaceWithNewValue - This method is the obvious combination of the two
+ /// above, and it provided as a helper to simplify client code.
+ ///
+ void replaceWithNewValue(Value *Old, Value *New) {
+ copyValue(Old, New);
+ deleteValue(Old);
+ }
+};
+
+/// isNoAliasCall - Return true if this pointer is returned by a noalias
+/// function.
+bool isNoAliasCall(const Value *V);
+
+/// isIdentifiedObject - Return true if this pointer refers to a distinct and
+/// identifiable object. This returns true for:
+/// Global Variables and Functions
+/// Allocas and Mallocs
+/// ByVal and NoAlias Arguments
+/// NoAlias returns
+///
+bool isIdentifiedObject(const Value *V);
+
+} // End llvm namespace
+
+// Because of the way .a files work, we must force the BasicAA implementation to
+// be pulled in if the AliasAnalysis header is included. Otherwise we run
+// the risk of AliasAnalysis being used, but the default implementation not
+// being linked into the tool that uses it.
+FORCE_DEFINING_FILE_TO_BE_LINKED(AliasAnalysis)
+FORCE_DEFINING_FILE_TO_BE_LINKED(BasicAliasAnalysis)
+
+#endif
diff --git a/include/llvm/Analysis/AliasSetTracker.h b/include/llvm/Analysis/AliasSetTracker.h
new file mode 100644
index 000000000000..786c1d15ba1a
--- /dev/null
+++ b/include/llvm/Analysis/AliasSetTracker.h
@@ -0,0 +1,393 @@
+//===- llvm/Analysis/AliasSetTracker.h - Build Alias Sets -------*- 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 two classes: AliasSetTracker and AliasSet. These interface
+// are used to classify a collection of pointer references into a maximal number
+// of disjoint sets. Each AliasSet object constructed by the AliasSetTracker
+// object refers to memory disjoint from the other sets.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ANALYSIS_ALIASSETTRACKER_H
+#define LLVM_ANALYSIS_ALIASSETTRACKER_H
+
+#include "llvm/Support/CallSite.h"
+#include "llvm/Support/Streams.h"
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/iterator.h"
+#include "llvm/ADT/ilist.h"
+#include "llvm/ADT/ilist_node.h"
+#include <vector>
+
+namespace llvm {
+
+class AliasAnalysis;
+class LoadInst;
+class StoreInst;
+class FreeInst;
+class VAArgInst;
+class AliasSetTracker;
+class AliasSet;
+
+class AliasSet : public ilist_node<AliasSet> {
+ friend class AliasSetTracker;
+
+ class PointerRec {
+ Value *Val; // The pointer this record corresponds to.
+ PointerRec **PrevInList, *NextInList;
+ AliasSet *AS;
+ unsigned Size;
+ public:
+ PointerRec(Value *V)
+ : Val(V), PrevInList(0), NextInList(0), AS(0), Size(0) {}
+
+ Value *getValue() const { return Val; }
+
+ PointerRec *getNext() const { return NextInList; }
+ bool hasAliasSet() const { return AS != 0; }
+
+ PointerRec** setPrevInList(PointerRec **PIL) {
+ PrevInList = PIL;
+ return &NextInList;
+ }
+
+ void updateSize(unsigned NewSize) {
+ if (NewSize > Size) Size = NewSize;
+ }
+
+ unsigned getSize() const { return Size; }
+
+ AliasSet *getAliasSet(AliasSetTracker &AST) {
+ assert(AS && "No AliasSet yet!");
+ if (AS->Forward) {
+ AliasSet *OldAS = AS;
+ AS = OldAS->getForwardedTarget(AST);
+ AS->addRef();
+ OldAS->dropRef(AST);
+ }
+ return AS;
+ }
+
+ void setAliasSet(AliasSet *as) {
+ assert(AS == 0 && "Already have an alias set!");
+ AS = as;
+ }
+
+ void eraseFromList() {
+ if (NextInList) NextInList->PrevInList = PrevInList;
+ *PrevInList = NextInList;
+ if (AS->PtrListEnd == &NextInList) {
+ AS->PtrListEnd = PrevInList;
+ assert(*AS->PtrListEnd == 0 && "List not terminated right!");
+ }
+ delete this;
+ }
+ };
+
+ PointerRec *PtrList, **PtrListEnd; // Doubly linked list of nodes.
+ AliasSet *Forward; // Forwarding pointer.
+ AliasSet *Next, *Prev; // Doubly linked list of AliasSets.
+
+ std::vector<CallSite> CallSites; // All calls & invokes in this alias set.
+
+ // RefCount - Number of nodes pointing to this AliasSet plus the number of
+ // AliasSets forwarding to it.
+ unsigned RefCount : 28;
+
+ /// AccessType - Keep track of whether this alias set merely refers to the
+ /// locations of memory, whether it modifies the memory, or whether it does
+ /// both. The lattice goes from "NoModRef" to either Refs or Mods, then to
+ /// ModRef as necessary.
+ ///
+ enum AccessType {
+ NoModRef = 0, Refs = 1, // Ref = bit 1
+ Mods = 2, ModRef = 3 // Mod = bit 2
+ };
+ unsigned AccessTy : 2;
+
+ /// AliasType - Keep track the relationships between the pointers in the set.
+ /// Lattice goes from MustAlias to MayAlias.
+ ///
+ enum AliasType {
+ MustAlias = 0, MayAlias = 1
+ };
+ unsigned AliasTy : 1;
+
+ // Volatile - True if this alias set contains volatile loads or stores.
+ bool Volatile : 1;
+
+ void addRef() { ++RefCount; }
+ void dropRef(AliasSetTracker &AST) {
+ assert(RefCount >= 1 && "Invalid reference count detected!");
+ if (--RefCount == 0)
+ removeFromTracker(AST);
+ }
+
+public:
+ /// Accessors...
+ bool isRef() const { return AccessTy & Refs; }
+ bool isMod() const { return AccessTy & Mods; }
+ bool isMustAlias() const { return AliasTy == MustAlias; }
+ bool isMayAlias() const { return AliasTy == MayAlias; }
+
+ // isVolatile - Return true if this alias set contains volatile loads or
+ // stores.
+ bool isVolatile() const { return Volatile; }
+
+ /// isForwardingAliasSet - Return true if this alias set should be ignored as
+ /// part of the AliasSetTracker object.
+ bool isForwardingAliasSet() const { return Forward; }
+
+ /// mergeSetIn - Merge the specified alias set into this alias set...
+ ///
+ void mergeSetIn(AliasSet &AS, AliasSetTracker &AST);
+
+ // Alias Set iteration - Allow access to all of the pointer which are part of
+ // this alias set...
+ class iterator;
+ iterator begin() const { return iterator(PtrList); }
+ iterator end() const { return iterator(); }
+ bool empty() const { return PtrList == 0; }
+
+ void print(std::ostream &OS) const;
+ void print(std::ostream *OS) const { if (OS) print(*OS); }
+ void dump() const;
+
+ /// Define an iterator for alias sets... this is just a forward iterator.
+ class iterator : public forward_iterator<PointerRec, ptrdiff_t> {
+ PointerRec *CurNode;
+ public:
+ explicit iterator(PointerRec *CN = 0) : CurNode(CN) {}
+
+ bool operator==(const iterator& x) const {
+ return CurNode == x.CurNode;
+ }
+ bool operator!=(const iterator& x) const { return !operator==(x); }
+
+ const iterator &operator=(const iterator &I) {
+ CurNode = I.CurNode;
+ return *this;
+ }
+
+ value_type &operator*() const {
+ assert(CurNode && "Dereferencing AliasSet.end()!");
+ return *CurNode;
+ }
+ value_type *operator->() const { return &operator*(); }
+
+ Value *getPointer() const { return CurNode->getValue(); }
+ unsigned getSize() const { return CurNode->getSize(); }
+
+ iterator& operator++() { // Preincrement
+ assert(CurNode && "Advancing past AliasSet.end()!");
+ CurNode = CurNode->getNext();
+ return *this;
+ }
+ iterator operator++(int) { // Postincrement
+ iterator tmp = *this; ++*this; return tmp;
+ }
+ };
+
+private:
+ // Can only be created by AliasSetTracker. Also, ilist creates one
+ // to serve as a sentinel.
+ friend struct ilist_sentinel_traits<AliasSet>;
+ AliasSet() : PtrList(0), PtrListEnd(&PtrList), Forward(0), RefCount(0),
+ AccessTy(NoModRef), AliasTy(MustAlias), Volatile(false) {
+ }
+
+ AliasSet(const AliasSet &AS); // do not implement
+ void operator=(const AliasSet &AS); // do not implement
+
+ PointerRec *getSomePointer() const {
+ return PtrList;
+ }
+
+ /// getForwardedTarget - Return the real alias set this represents. If this
+ /// has been merged with another set and is forwarding, return the ultimate
+ /// destination set. This also implements the union-find collapsing as well.
+ AliasSet *getForwardedTarget(AliasSetTracker &AST) {
+ if (!Forward) return this;
+
+ AliasSet *Dest = Forward->getForwardedTarget(AST);
+ if (Dest != Forward) {
+ Dest->addRef();
+ Forward->dropRef(AST);
+ Forward = Dest;
+ }
+ return Dest;
+ }
+
+ void removeFromTracker(AliasSetTracker &AST);
+
+ void addPointer(AliasSetTracker &AST, PointerRec &Entry, unsigned Size,
+ bool KnownMustAlias = false);
+ void addCallSite(CallSite CS, AliasAnalysis &AA);
+ void removeCallSite(CallSite CS) {
+ for (size_t i = 0, e = CallSites.size(); i != e; ++i)
+ if (CallSites[i].getInstruction() == CS.getInstruction()) {
+ CallSites[i] = CallSites.back();
+ CallSites.pop_back();
+ }
+ }
+ void setVolatile() { Volatile = true; }
+
+ /// aliasesPointer - Return true if the specified pointer "may" (or must)
+ /// alias one of the members in the set.
+ ///
+ bool aliasesPointer(const Value *Ptr, unsigned Size, AliasAnalysis &AA) const;
+ bool aliasesCallSite(CallSite CS, AliasAnalysis &AA) const;
+};
+
+inline std::ostream& operator<<(std::ostream &OS, const AliasSet &AS) {
+ AS.print(OS);
+ return OS;
+}
+
+
+class AliasSetTracker {
+ AliasAnalysis &AA;
+ ilist<AliasSet> AliasSets;
+
+ // Map from pointers to their node
+ DenseMap<Value*, AliasSet::PointerRec*> PointerMap;
+public:
+ /// AliasSetTracker ctor - Create an empty collection of AliasSets, and use
+ /// the specified alias analysis object to disambiguate load and store
+ /// addresses.
+ explicit AliasSetTracker(AliasAnalysis &aa) : AA(aa) {}
+ ~AliasSetTracker() { clear(); }
+
+ /// add methods - These methods are used to add different types of
+ /// instructions to the alias sets. Adding a new instruction can result in
+ /// one of three actions happening:
+ ///
+ /// 1. If the instruction doesn't alias any other sets, create a new set.
+ /// 2. If the instruction aliases exactly one set, add it to the set
+ /// 3. If the instruction aliases multiple sets, merge the sets, and add
+ /// the instruction to the result.
+ ///
+ /// These methods return true if inserting the instruction resulted in the
+ /// addition of a new alias set (i.e., the pointer did not alias anything).
+ ///
+ bool add(Value *Ptr, unsigned Size); // Add a location
+ bool add(LoadInst *LI);
+ bool add(StoreInst *SI);
+ bool add(FreeInst *FI);
+ bool add(VAArgInst *VAAI);
+ bool add(CallSite CS); // Call/Invoke instructions
+ bool add(CallInst *CI) { return add(CallSite(CI)); }
+ bool add(InvokeInst *II) { return add(CallSite(II)); }
+ bool add(Instruction *I); // Dispatch to one of the other add methods...
+ void add(BasicBlock &BB); // Add all instructions in basic block
+ void add(const AliasSetTracker &AST); // Add alias relations from another AST
+
+ /// remove methods - These methods are used to remove all entries that might
+ /// be aliased by the specified instruction. These methods return true if any
+ /// alias sets were eliminated.
+ bool remove(Value *Ptr, unsigned Size); // Remove a location
+ bool remove(LoadInst *LI);
+ bool remove(StoreInst *SI);
+ bool remove(FreeInst *FI);
+ bool remove(VAArgInst *VAAI);
+ bool remove(CallSite CS);
+ bool remove(CallInst *CI) { return remove(CallSite(CI)); }
+ bool remove(InvokeInst *II) { return remove(CallSite(II)); }
+ bool remove(Instruction *I);
+ void remove(AliasSet &AS);
+
+ void clear();
+
+ /// getAliasSets - Return the alias sets that are active.
+ ///
+ const ilist<AliasSet> &getAliasSets() const { return AliasSets; }
+
+ /// getAliasSetForPointer - Return the alias set that the specified pointer
+ /// lives in. If the New argument is non-null, this method sets the value to
+ /// true if a new alias set is created to contain the pointer (because the
+ /// pointer didn't alias anything).
+ AliasSet &getAliasSetForPointer(Value *P, unsigned Size, bool *New = 0);
+
+ /// getAliasSetForPointerIfExists - Return the alias set containing the
+ /// location specified if one exists, otherwise return null.
+ AliasSet *getAliasSetForPointerIfExists(Value *P, unsigned Size) {
+ return findAliasSetForPointer(P, Size);
+ }
+
+ /// containsPointer - Return true if the specified location is represented by
+ /// this alias set, false otherwise. This does not modify the AST object or
+ /// alias sets.
+ bool containsPointer(Value *P, unsigned Size) const;
+
+ /// getAliasAnalysis - Return the underlying alias analysis object used by
+ /// this tracker.
+ AliasAnalysis &getAliasAnalysis() const { return AA; }
+
+ /// deleteValue method - This method is used to remove a pointer value from
+ /// the AliasSetTracker entirely. It should be used when an instruction is
+ /// deleted from the program to update the AST. If you don't use this, you
+ /// would have dangling pointers to deleted instructions.
+ ///
+ void deleteValue(Value *PtrVal);
+
+ /// copyValue - This method should be used whenever a preexisting value in the
+ /// program is copied or cloned, introducing a new value. Note that it is ok
+ /// for clients that use this method to introduce the same value multiple
+ /// times: if the tracker already knows about a value, it will ignore the
+ /// request.
+ ///
+ void copyValue(Value *From, Value *To);
+
+
+ typedef ilist<AliasSet>::iterator iterator;
+ typedef ilist<AliasSet>::const_iterator const_iterator;
+
+ const_iterator begin() const { return AliasSets.begin(); }
+ const_iterator end() const { return AliasSets.end(); }
+
+ iterator begin() { return AliasSets.begin(); }
+ iterator end() { return AliasSets.end(); }
+
+ void print(std::ostream &OS) const;
+ void print(std::ostream *OS) const { if (OS) print(*OS); }
+ void dump() const;
+
+private:
+ friend class AliasSet;
+ void removeAliasSet(AliasSet *AS);
+
+ // getEntryFor - Just like operator[] on the map, except that it creates an
+ // entry for the pointer if it doesn't already exist.
+ AliasSet::PointerRec &getEntryFor(Value *V) {
+ AliasSet::PointerRec *&Entry = PointerMap[V];
+ if (Entry == 0)
+ Entry = new AliasSet::PointerRec(V);
+ return *Entry;
+ }
+
+ AliasSet &addPointer(Value *P, unsigned Size, AliasSet::AccessType E,
+ bool &NewSet) {
+ NewSet = false;
+ AliasSet &AS = getAliasSetForPointer(P, Size, &NewSet);
+ AS.AccessTy |= E;
+ return AS;
+ }
+ AliasSet *findAliasSetForPointer(const Value *Ptr, unsigned Size);
+
+ AliasSet *findAliasSetForCallSite(CallSite CS);
+};
+
+inline std::ostream& operator<<(std::ostream &OS, const AliasSetTracker &AST) {
+ AST.print(OS);
+ return OS;
+}
+
+} // End llvm namespace
+
+#endif
diff --git a/include/llvm/Analysis/CFGPrinter.h b/include/llvm/Analysis/CFGPrinter.h
new file mode 100644
index 000000000000..6a479d199c8e
--- /dev/null
+++ b/include/llvm/Analysis/CFGPrinter.h
@@ -0,0 +1,24 @@
+//===-- CFGPrinter.h - CFG printer external interface ------------*- 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 external functions that can be called to explicitly
+// instantiate the CFG printer.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ANALYSIS_CFGPRINTER_H
+#define LLVM_ANALYSIS_CFGPRINTER_H
+
+namespace llvm {
+ class FunctionPass;
+ FunctionPass *createCFGPrinterPass ();
+ FunctionPass *createCFGOnlyPrinterPass ();
+} // End llvm namespace
+
+#endif
diff --git a/include/llvm/Analysis/CallGraph.h b/include/llvm/Analysis/CallGraph.h
new file mode 100644
index 000000000000..de839694dc8a
--- /dev/null
+++ b/include/llvm/Analysis/CallGraph.h
@@ -0,0 +1,326 @@
+//===- CallGraph.h - Build a Module's call graph ----------------*- C++ -*-===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This interface is used to build and manipulate a call graph, which is a very
+// useful tool for interprocedural optimization.
+//
+// Every function in a module is represented as a node in the call graph. The
+// callgraph node keeps track of which functions the are called by the function
+// corresponding to the node.
+//
+// A call graph may contain nodes where the function that they correspond to is
+// null. These 'external' nodes are used to represent control flow that is not
+// represented (or analyzable) in the module. In particular, this analysis
+// builds one external node such that:
+// 1. All functions in the module without internal linkage will have edges
+// from this external node, indicating that they could be called by
+// functions outside of the module.
+// 2. All functions whose address is used for something more than a direct
+// call, for example being stored into a memory location will also have an
+// edge from this external node. Since they may be called by an unknown
+// caller later, they must be tracked as such.
+//
+// There is a second external node added for calls that leave this module.
+// Functions have a call edge to the external node iff:
+// 1. The function is external, reflecting the fact that they could call
+// anything without internal linkage or that has its address taken.
+// 2. The function contains an indirect function call.
+//
+// As an extension in the future, there may be multiple nodes with a null
+// function. These will be used when we can prove (through pointer analysis)
+// that an indirect call site can call only a specific set of functions.
+//
+// Because of these properties, the CallGraph captures a conservative superset
+// of all of the caller-callee relationships, which is useful for
+// transformations.
+//
+// The CallGraph class also attempts to figure out what the root of the
+// CallGraph is, which it currently does by looking for a function named 'main'.
+// If no function named 'main' is found, the external node is used as the entry
+// node, reflecting the fact that any function without internal linkage could
+// be called into (which is common for libraries).
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ANALYSIS_CALLGRAPH_H
+#define LLVM_ANALYSIS_CALLGRAPH_H
+
+#include "llvm/ADT/GraphTraits.h"
+#include "llvm/ADT/STLExtras.h"
+#include "llvm/Pass.h"
+#include "llvm/Support/CallSite.h"
+#include "llvm/System/IncludeFile.h"
+#include <map>
+
+namespace llvm {
+
+class Function;
+class Module;
+class CallGraphNode;
+
+//===----------------------------------------------------------------------===//
+// CallGraph class definition
+//
+class CallGraph {
+protected:
+ Module *Mod; // The module this call graph represents
+
+ typedef std::map<const Function *, CallGraphNode *> FunctionMapTy;
+ FunctionMapTy FunctionMap; // Map from a function to its node
+
+public:
+ static char ID; // Class identification, replacement for typeinfo
+ //===---------------------------------------------------------------------
+ // Accessors...
+ //
+ typedef FunctionMapTy::iterator iterator;
+ typedef FunctionMapTy::const_iterator const_iterator;
+
+ /// getModule - Return the module the call graph corresponds to.
+ ///
+ Module &getModule() const { return *Mod; }
+
+ inline iterator begin() { return FunctionMap.begin(); }
+ inline iterator end() { return FunctionMap.end(); }
+ inline const_iterator begin() const { return FunctionMap.begin(); }
+ inline const_iterator end() const { return FunctionMap.end(); }
+
+ // Subscripting operators, return the call graph node for the provided
+ // function
+ inline const CallGraphNode *operator[](const Function *F) const {
+ const_iterator I = FunctionMap.find(F);
+ assert(I != FunctionMap.end() && "Function not in callgraph!");
+ return I->second;
+ }
+ inline CallGraphNode *operator[](const Function *F) {
+ const_iterator I = FunctionMap.find(F);
+ assert(I != FunctionMap.end() && "Function not in callgraph!");
+ return I->second;
+ }
+
+ /// Returns the CallGraphNode which is used to represent undetermined calls
+ /// into the callgraph. Override this if you want behavioral inheritance.
+ virtual CallGraphNode* getExternalCallingNode() const { return 0; }
+
+ /// Return the root/main method in the module, or some other root node, such
+ /// as the externalcallingnode. Overload these if you behavioral
+ /// inheritance.
+ virtual CallGraphNode* getRoot() { return 0; }
+ virtual const CallGraphNode* getRoot() const { return 0; }
+
+ //===---------------------------------------------------------------------
+ // Functions to keep a call graph up to date with a function that has been
+ // modified.
+ //
+
+ /// removeFunctionFromModule - Unlink the function from this module, returning
+ /// it. Because this removes the function from the module, the call graph
+ /// node is destroyed. This is only valid if the function does not call any
+ /// other functions (ie, there are no edges in it's CGN). The easiest way to
+ /// do this is to dropAllReferences before calling this.
+ ///
+ Function *removeFunctionFromModule(CallGraphNode *CGN);
+ Function *removeFunctionFromModule(Function *F) {
+ return removeFunctionFromModule((*this)[F]);
+ }
+
+ /// changeFunction - This method changes the function associated with this
+ /// CallGraphNode, for use by transformations that need to change the
+ /// prototype of a Function (thus they must create a new Function and move the
+ /// old code over).
+ void changeFunction(Function *OldF, Function *NewF);
+
+ /// getOrInsertFunction - This method is identical to calling operator[], but
+ /// it will insert a new CallGraphNode for the specified function if one does
+ /// not already exist.
+ CallGraphNode *getOrInsertFunction(const Function *F);
+
+ //===---------------------------------------------------------------------
+ // Pass infrastructure interface glue code...
+ //
+protected:
+ CallGraph() {}
+
+public:
+ virtual ~CallGraph() { destroy(); }
+
+ /// initialize - Call this method before calling other methods,
+ /// re/initializes the state of the CallGraph.
+ ///
+ void initialize(Module &M);
+
+ virtual void print(std::ostream &o, const Module *M) const;
+ void print(std::ostream *o, const Module *M) const { if (o) print(*o, M); }
+ void dump() const;
+
+protected:
+ // destroy - Release memory for the call graph
+ virtual void destroy();
+};
+
+//===----------------------------------------------------------------------===//
+// CallGraphNode class definition
+//
+class CallGraphNode {
+ Function *F;
+ typedef std::pair<CallSite,CallGraphNode*> CallRecord;
+ std::vector<CallRecord> CalledFunctions;
+
+ CallGraphNode(const CallGraphNode &); // Do not implement
+public:
+ typedef std::vector<CallRecord> CalledFunctionsVector;
+
+ //===---------------------------------------------------------------------
+ // Accessor methods...
+ //
+
+ typedef std::vector<CallRecord>::iterator iterator;
+ typedef std::vector<CallRecord>::const_iterator const_iterator;
+
+ // getFunction - Return the function that this call graph node represents...
+ Function *getFunction() const { return F; }
+
+ inline iterator begin() { return CalledFunctions.begin(); }
+ inline iterator end() { return CalledFunctions.end(); }
+ inline const_iterator begin() const { return CalledFunctions.begin(); }
+ inline const_iterator end() const { return CalledFunctions.end(); }
+ inline bool empty() const { return CalledFunctions.empty(); }
+ inline unsigned size() const { return (unsigned)CalledFunctions.size(); }
+
+ // Subscripting operator - Return the i'th called function...
+ //
+ CallGraphNode *operator[](unsigned i) const {
+ return CalledFunctions[i].second;
+ }
+
+ /// dump - Print out this call graph node.
+ ///
+ void dump() const;
+ void print(std::ostream &OS) const;
+ void print(std::ostream *OS) const { if (OS) print(*OS); }
+
+ //===---------------------------------------------------------------------
+ // Methods to keep a call graph up to date with a function that has been
+ // modified
+ //
+
+ /// removeAllCalledFunctions - As the name implies, this removes all edges
+ /// from this CallGraphNode to any functions it calls.
+ void removeAllCalledFunctions() {
+ CalledFunctions.clear();
+ }
+
+ /// addCalledFunction - Add a function to the list of functions called by this
+ /// one.
+ void addCalledFunction(CallSite CS, CallGraphNode *M) {
+ CalledFunctions.push_back(std::make_pair(CS, M));
+ }
+
+ /// removeCallEdgeFor - This method removes the edge in the node for the
+ /// specified call site. Note that this method takes linear time, so it
+ /// should be used sparingly.
+ void removeCallEdgeFor(CallSite CS);
+
+ /// removeAnyCallEdgeTo - This method removes all call edges from this node
+ /// to the specified callee function. This takes more time to execute than
+ /// removeCallEdgeTo, so it should not be used unless necessary.
+ void removeAnyCallEdgeTo(CallGraphNode *Callee);
+
+ /// removeOneAbstractEdgeTo - Remove one edge associated with a null callsite
+ /// from this node to the specified callee function.
+ void removeOneAbstractEdgeTo(CallGraphNode *Callee);
+
+ /// replaceCallSite - Make the edge in the node for Old CallSite be for
+ /// New CallSite instead. Note that this method takes linear time, so it
+ /// should be used sparingly.
+ void replaceCallSite(CallSite Old, CallSite New);
+
+ friend class CallGraph;
+
+ // CallGraphNode ctor - Create a node for the specified function.
+ inline CallGraphNode(Function *f) : F(f) {}
+};
+
+//===----------------------------------------------------------------------===//
+// GraphTraits specializations for call graphs so that they can be treated as
+// graphs by the generic graph algorithms.
+//
+
+// Provide graph traits for tranversing call graphs using standard graph
+// traversals.
+template <> struct GraphTraits<CallGraphNode*> {
+ typedef CallGraphNode NodeType;
+
+ typedef std::pair<CallSite, CallGraphNode*> CGNPairTy;
+ typedef std::pointer_to_unary_function<CGNPairTy, CallGraphNode*> CGNDerefFun;
+
+ static NodeType *getEntryNode(CallGraphNode *CGN) { return CGN; }
+
+ typedef mapped_iterator<NodeType::iterator, CGNDerefFun> ChildIteratorType;
+
+ static inline ChildIteratorType child_begin(NodeType *N) {
+ return map_iterator(N->begin(), CGNDerefFun(CGNDeref));
+ }
+ static inline ChildIteratorType child_end (NodeType *N) {
+ return map_iterator(N->end(), CGNDerefFun(CGNDeref));
+ }
+
+ static CallGraphNode *CGNDeref(CGNPairTy P) {
+ return P.second;
+ }
+
+};
+
+template <> struct GraphTraits<const CallGraphNode*> {
+ typedef const CallGraphNode NodeType;
+ typedef NodeType::const_iterator ChildIteratorType;
+
+ static NodeType *getEntryNode(const CallGraphNode *CGN) { return CGN; }
+ static inline ChildIteratorType child_begin(NodeType *N) { return N->begin();}
+ static inline ChildIteratorType child_end (NodeType *N) { return N->end(); }
+};
+
+template<> struct GraphTraits<CallGraph*> : public GraphTraits<CallGraphNode*> {
+ static NodeType *getEntryNode(CallGraph *CGN) {
+ return CGN->getExternalCallingNode(); // Start at the external node!
+ }
+ typedef std::pair<const Function*, CallGraphNode*> PairTy;
+ typedef std::pointer_to_unary_function<PairTy, CallGraphNode&> DerefFun;
+
+ // nodes_iterator/begin/end - Allow iteration over all nodes in the graph
+ typedef mapped_iterator<CallGraph::iterator, DerefFun> nodes_iterator;
+ static nodes_iterator nodes_begin(CallGraph *CG) {
+ return map_iterator(CG->begin(), DerefFun(CGdereference));
+ }
+ static nodes_iterator nodes_end (CallGraph *CG) {
+ return map_iterator(CG->end(), DerefFun(CGdereference));
+ }
+
+ static CallGraphNode &CGdereference(PairTy P) {
+ return *P.second;
+ }
+};
+
+template<> struct GraphTraits<const CallGraph*> :
+ public GraphTraits<const CallGraphNode*> {
+ static NodeType *getEntryNode(const CallGraph *CGN) {
+ return CGN->getExternalCallingNode();
+ }
+ // nodes_iterator/begin/end - Allow iteration over all nodes in the graph
+ typedef CallGraph::const_iterator nodes_iterator;
+ static nodes_iterator nodes_begin(const CallGraph *CG) { return CG->begin(); }
+ static nodes_iterator nodes_end (const CallGraph *CG) { return CG->end(); }
+};
+
+} // End llvm namespace
+
+// Make sure that any clients of this file link in CallGraph.cpp
+FORCE_DEFINING_FILE_TO_BE_LINKED(CallGraph)
+
+#endif
diff --git a/include/llvm/Analysis/CaptureTracking.h b/include/llvm/Analysis/CaptureTracking.h
new file mode 100644
index 000000000000..a0ff503a0393
--- /dev/null
+++ b/include/llvm/Analysis/CaptureTracking.h
@@ -0,0 +1,29 @@
+//===----- llvm/Analysis/CaptureTracking.h - Pointer capture ----*- C++ -*-===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file contains routines that help determine which pointers are captured.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ANALYSIS_CAPTURETRACKING_H
+#define LLVM_ANALYSIS_CAPTURETRACKING_H
+
+namespace llvm {
+ class Value;
+
+ /// PointerMayBeCaptured - Return true if this pointer value may be captured
+ /// by the enclosing function (which is required to exist). This routine can
+ /// be expensive, so consider caching the results. The boolean ReturnCaptures
+ /// specifies whether returning the value (or part of it) from the function
+ /// counts as capturing it or not.
+ bool PointerMayBeCaptured(const Value *V, bool ReturnCaptures);
+
+} // end namespace llvm
+
+#endif
diff --git a/include/llvm/Analysis/ConstantFolding.h b/include/llvm/Analysis/ConstantFolding.h
new file mode 100644
index 000000000000..bf360f7e8847
--- /dev/null
+++ b/include/llvm/Analysis/ConstantFolding.h
@@ -0,0 +1,73 @@
+//===-- ConstantFolding.h - Analyze constant folding possibilities --------===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This family of functions determines the possibility of performing constant
+// folding.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ANALYSIS_CONSTANTFOLDING_H
+#define LLVM_ANALYSIS_CONSTANTFOLDING_H
+
+namespace llvm {
+ class Constant;
+ class ConstantExpr;
+ class Instruction;
+ class TargetData;
+ class Function;
+ class Type;
+
+/// ConstantFoldInstruction - Attempt to constant fold the specified
+/// instruction. If successful, the constant result is returned, if not, null
+/// is returned. Note that this function can only fail when attempting to fold
+/// instructions like loads and stores, which have no constant expression form.
+///
+Constant *ConstantFoldInstruction(Instruction *I, const TargetData *TD = 0);
+
+/// ConstantFoldConstantExpression - Attempt to fold the constant expression
+/// using the specified TargetData. If successful, the constant result is
+/// result is returned, if not, null is returned.
+Constant *ConstantFoldConstantExpression(ConstantExpr *CE,
+ const TargetData *TD);
+
+/// ConstantFoldInstOperands - Attempt to constant fold an instruction with the
+/// specified operands. If successful, the constant result is returned, if not,
+/// null is returned. Note that this function can fail when attempting to
+/// fold instructions like loads and stores, which have no constant expression
+/// form.
+///
+Constant *ConstantFoldInstOperands(unsigned Opcode, const Type *DestTy,
+ Constant*const * Ops, unsigned NumOps,
+ const TargetData *TD = 0);
+
+/// ConstantFoldCompareInstOperands - Attempt to constant fold a compare
+/// instruction (icmp/fcmp) with the specified operands. If it fails, it
+/// returns a constant expression of the specified operands.
+///
+Constant *ConstantFoldCompareInstOperands(unsigned Predicate,
+ Constant*const * Ops, unsigned NumOps,
+ const TargetData *TD = 0);
+
+
+/// ConstantFoldLoadThroughGEPConstantExpr - Given a constant and a
+/// getelementptr constantexpr, return the constant value being addressed by the
+/// constant expression, or null if something is funny and we can't decide.
+Constant *ConstantFoldLoadThroughGEPConstantExpr(Constant *C, ConstantExpr *CE);
+
+/// canConstantFoldCallTo - Return true if its even possible to fold a call to
+/// the specified function.
+bool canConstantFoldCallTo(const Function *F);
+
+/// ConstantFoldCall - Attempt to constant fold a call to the specified function
+/// with the specified arguments, returning null if unsuccessful.
+Constant *
+ConstantFoldCall(Function *F, Constant* const* Operands, unsigned NumOperands);
+}
+
+#endif
diff --git a/include/llvm/Analysis/ConstantsScanner.h b/include/llvm/Analysis/ConstantsScanner.h
new file mode 100644
index 000000000000..bac551f0492a
--- /dev/null
+++ b/include/llvm/Analysis/ConstantsScanner.h
@@ -0,0 +1,93 @@
+//==- llvm/Analysis/ConstantsScanner.h - Iterate over constants -*- C++ -*-===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This class implements an iterator to walk through the constants referenced by
+// a method. This is used by the Bitcode & Assembly writers to build constant
+// pools.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ANALYSIS_CONSTANTSSCANNER_H
+#define LLVM_ANALYSIS_CONSTANTSSCANNER_H
+
+#include "llvm/Support/InstIterator.h"
+#include "llvm/ADT/iterator.h"
+
+namespace llvm {
+
+class Constant;
+
+class constant_iterator : public forward_iterator<const Constant, ptrdiff_t> {
+ const_inst_iterator InstI; // Method instruction iterator
+ unsigned OpIdx; // Operand index
+
+ typedef constant_iterator _Self;
+
+ inline bool isAtConstant() const {
+ assert(!InstI.atEnd() && OpIdx < InstI->getNumOperands() &&
+ "isAtConstant called with invalid arguments!");
+ return isa<Constant>(InstI->getOperand(OpIdx));
+ }
+
+public:
+ inline constant_iterator(const Function *F) : InstI(inst_begin(F)), OpIdx(0) {
+ // Advance to first constant... if we are not already at constant or end
+ if (InstI != inst_end(F) && // InstI is valid?
+ (InstI->getNumOperands() == 0 || !isAtConstant())) // Not at constant?
+ operator++();
+ }
+
+ inline constant_iterator(const Function *F, bool) // end ctor
+ : InstI(inst_end(F)), OpIdx(0) {
+ }
+
+ inline bool operator==(const _Self& x) const { return OpIdx == x.OpIdx &&
+ InstI == x.InstI; }
+ inline bool operator!=(const _Self& x) const { return !operator==(x); }
+
+ inline pointer operator*() const {
+ assert(isAtConstant() && "Dereferenced an iterator at the end!");
+ return cast<Constant>(InstI->getOperand(OpIdx));
+ }
+ inline pointer operator->() const { return operator*(); }
+
+ inline _Self& operator++() { // Preincrement implementation
+ ++OpIdx;
+ do {
+ unsigned NumOperands = InstI->getNumOperands();
+ while (OpIdx < NumOperands && !isAtConstant()) {
+ ++OpIdx;
+ }
+
+ if (OpIdx < NumOperands) return *this; // Found a constant!
+ ++InstI;
+ OpIdx = 0;
+ } while (!InstI.atEnd());
+
+ return *this; // At the end of the method
+ }
+
+ inline _Self operator++(int) { // Postincrement
+ _Self tmp = *this; ++*this; return tmp;
+ }
+
+ inline bool atEnd() const { return InstI.atEnd(); }
+};
+
+inline constant_iterator constant_begin(const Function *F) {
+ return constant_iterator(F);
+}
+
+inline constant_iterator constant_end(const Function *F) {
+ return constant_iterator(F, true);
+}
+
+} // End llvm namespace
+
+#endif
diff --git a/include/llvm/Analysis/DebugInfo.h b/include/llvm/Analysis/DebugInfo.h
new file mode 100644
index 000000000000..972bb07196e4
--- /dev/null
+++ b/include/llvm/Analysis/DebugInfo.h
@@ -0,0 +1,555 @@
+//===--- llvm/Analysis/DebugInfo.h - Debug Information Helpers --*- 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 a bunch of datatypes that are useful for creating and
+// walking debug info in LLVM IR form. They essentially provide wrappers around
+// the information in the global variables that's needed when constructing the
+// DWARF information.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ANALYSIS_DEBUGINFO_H
+#define LLVM_ANALYSIS_DEBUGINFO_H
+
+#include "llvm/Target/TargetMachine.h"
+#include "llvm/ADT/StringMap.h"
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/Support/Dwarf.h"
+
+namespace llvm {
+ class BasicBlock;
+ class Constant;
+ class Function;
+ class GlobalVariable;
+ class Module;
+ class Type;
+ class Value;
+ struct DbgStopPointInst;
+ struct DbgDeclareInst;
+ class Instruction;
+
+ class DIDescriptor {
+ protected:
+ GlobalVariable *GV;
+
+ /// DIDescriptor constructor. If the specified GV is non-null, this checks
+ /// to make sure that the tag in the descriptor matches 'RequiredTag'. If
+ /// not, the debug info is corrupt and we ignore it.
+ DIDescriptor(GlobalVariable *GV, unsigned RequiredTag);
+
+ const std::string &getStringField(unsigned Elt, std::string &Result) const;
+ unsigned getUnsignedField(unsigned Elt) const {
+ return (unsigned)getUInt64Field(Elt);
+ }
+ uint64_t getUInt64Field(unsigned Elt) const;
+ DIDescriptor getDescriptorField(unsigned Elt) const;
+
+ template <typename DescTy>
+ DescTy getFieldAs(unsigned Elt) const {
+ return DescTy(getDescriptorField(Elt).getGV());
+ }
+
+ GlobalVariable *getGlobalVariableField(unsigned Elt) const;
+
+ public:
+ explicit DIDescriptor() : GV(0) {}
+ explicit DIDescriptor(GlobalVariable *gv) : GV(gv) {}
+
+ bool isNull() const { return GV == 0; }
+
+ GlobalVariable *getGV() const { return GV; }
+
+ unsigned getVersion() const {
+ return getUnsignedField(0) & LLVMDebugVersionMask;
+ }
+
+ unsigned getTag() const {
+ return getUnsignedField(0) & ~LLVMDebugVersionMask;
+ }
+
+ /// ValidDebugInfo - Return true if V represents valid debug info value.
+ static bool ValidDebugInfo(Value *V, CodeGenOpt::Level OptLevel);
+
+ /// dump - print descriptor.
+ void dump() const;
+ };
+
+ /// DIAnchor - A wrapper for various anchor descriptors.
+ class DIAnchor : public DIDescriptor {
+ public:
+ explicit DIAnchor(GlobalVariable *GV = 0)
+ : DIDescriptor(GV, dwarf::DW_TAG_anchor) {}
+
+ unsigned getAnchorTag() const { return getUnsignedField(1); }
+ };
+
+ /// DISubrange - This is used to represent ranges, for array bounds.
+ class DISubrange : public DIDescriptor {
+ public:
+ explicit DISubrange(GlobalVariable *GV = 0)
+ : DIDescriptor(GV, dwarf::DW_TAG_subrange_type) {}
+
+ int64_t getLo() const { return (int64_t)getUInt64Field(1); }
+ int64_t getHi() const { return (int64_t)getUInt64Field(2); }
+ };
+
+ /// DIArray - This descriptor holds an array of descriptors.
+ class DIArray : public DIDescriptor {
+ public:
+ explicit DIArray(GlobalVariable *GV = 0) : DIDescriptor(GV) {}
+
+ unsigned getNumElements() const;
+ DIDescriptor getElement(unsigned Idx) const {
+ return getDescriptorField(Idx);
+ }
+ };
+
+ /// DICompileUnit - A wrapper for a compile unit.
+ class DICompileUnit : public DIDescriptor {
+ public:
+ explicit DICompileUnit(GlobalVariable *GV = 0)
+ : DIDescriptor(GV, dwarf::DW_TAG_compile_unit) {}
+
+ unsigned getLanguage() const { return getUnsignedField(2); }
+ const std::string &getFilename(std::string &F) const {
+ return getStringField(3, F);
+ }
+ const std::string &getDirectory(std::string &F) const {
+ return getStringField(4, F);
+ }
+ const std::string &getProducer(std::string &F) const {
+ return getStringField(5, F);
+ }
+
+ /// isMain - Each input file is encoded as a separate compile unit in LLVM
+ /// debugging information output. However, many target specific tool chains
+ /// prefer to encode only one compile unit in an object file. In this
+ /// situation, the LLVM code generator will include debugging information
+ /// entities in the compile unit that is marked as main compile unit. The
+ /// code generator accepts maximum one main compile unit per module. If a
+ /// module does not contain any main compile unit then the code generator
+ /// will emit multiple compile units in the output object file.
+
+ bool isMain() const { return getUnsignedField(6); }
+ bool isOptimized() const { return getUnsignedField(7); }
+ const std::string &getFlags(std::string &F) const {
+ return getStringField(8, F);
+ }
+ unsigned getRunTimeVersion() const { return getUnsignedField(9); }
+
+ /// Verify - Verify that a compile unit is well formed.
+ bool Verify() const;
+
+ /// dump - print compile unit.
+ void dump() const;
+ };
+
+ /// DIEnumerator - A wrapper for an enumerator (e.g. X and Y in 'enum {X,Y}').
+ /// FIXME: it seems strange that this doesn't have either a reference to the
+ /// type/precision or a file/line pair for location info.
+ class DIEnumerator : public DIDescriptor {
+ public:
+ explicit DIEnumerator(GlobalVariable *GV = 0)
+ : DIDescriptor(GV, dwarf::DW_TAG_enumerator) {}
+
+ const std::string &getName(std::string &F) const {
+ return getStringField(1, F);
+ }
+ uint64_t getEnumValue() const { return getUInt64Field(2); }
+ };
+
+ /// DIType - This is a wrapper for a type.
+ /// FIXME: Types should be factored much better so that CV qualifiers and
+ /// others do not require a huge and empty descriptor full of zeros.
+ class DIType : public DIDescriptor {
+ public:
+ enum {
+ FlagPrivate = 1 << 0,
+ FlagProtected = 1 << 1,
+ FlagFwdDecl = 1 << 2
+ };
+
+ protected:
+ DIType(GlobalVariable *GV, unsigned Tag) : DIDescriptor(GV, Tag) {}
+ // This ctor is used when the Tag has already been validated by a derived
+ // ctor.
+ DIType(GlobalVariable *GV, bool, bool) : DIDescriptor(GV) {}
+
+ public:
+ /// isDerivedType - Return true if the specified tag is legal for
+ /// DIDerivedType.
+ static bool isDerivedType(unsigned TAG);
+
+ /// isCompositeType - Return true if the specified tag is legal for
+ /// DICompositeType.
+ static bool isCompositeType(unsigned TAG);
+
+ /// isBasicType - Return true if the specified tag is legal for
+ /// DIBasicType.
+ static bool isBasicType(unsigned TAG) {
+ return TAG == dwarf::DW_TAG_base_type;
+ }
+
+ /// Verify - Verify that a type descriptor is well formed.
+ bool Verify() const;
+ public:
+ explicit DIType(GlobalVariable *GV);
+ explicit DIType() {}
+ virtual ~DIType() {}
+
+ DIDescriptor getContext() const { return getDescriptorField(1); }
+ const std::string &getName(std::string &F) const {
+ return getStringField(2, F);
+ }
+ DICompileUnit getCompileUnit() const{ return getFieldAs<DICompileUnit>(3); }
+ unsigned getLineNumber() const { return getUnsignedField(4); }
+ uint64_t getSizeInBits() const { return getUInt64Field(5); }
+ uint64_t getAlignInBits() const { return getUInt64Field(6); }
+ // FIXME: Offset is only used for DW_TAG_member nodes. Making every type
+ // carry this is just plain insane.
+ uint64_t getOffsetInBits() const { return getUInt64Field(7); }
+ unsigned getFlags() const { return getUnsignedField(8); }
+ bool isPrivate() const { return (getFlags() & FlagPrivate) != 0; }
+ bool isProtected() const { return (getFlags() & FlagProtected) != 0; }
+ bool isForwardDecl() const { return (getFlags() & FlagFwdDecl) != 0; }
+
+ /// dump - print type.
+ void dump() const;
+ };
+
+ /// DIBasicType - A basic type, like 'int' or 'float'.
+ class DIBasicType : public DIType {
+ public:
+ explicit DIBasicType(GlobalVariable *GV)
+ : DIType(GV, dwarf::DW_TAG_base_type) {}
+
+ unsigned getEncoding() const { return getUnsignedField(9); }
+
+ /// dump - print basic type.
+ void dump() const;
+ };
+
+ /// DIDerivedType - A simple derived type, like a const qualified type,
+ /// a typedef, a pointer or reference, etc.
+ class DIDerivedType : public DIType {
+ protected:
+ explicit DIDerivedType(GlobalVariable *GV, bool, bool)
+ : DIType(GV, true, true) {}
+ public:
+ explicit DIDerivedType(GlobalVariable *GV)
+ : DIType(GV, true, true) {
+ if (GV && !isDerivedType(getTag()))
+ GV = 0;
+ }
+
+ DIType getTypeDerivedFrom() const { return getFieldAs<DIType>(9); }
+
+ /// getOriginalTypeSize - If this type is derived from a base type then
+ /// return base type size.
+ uint64_t getOriginalTypeSize() const;
+ /// dump - print derived type.
+ void dump() const;
+ };
+
+ /// DICompositeType - This descriptor holds a type that can refer to multiple
+ /// other types, like a function or struct.
+ /// FIXME: Why is this a DIDerivedType??
+ class DICompositeType : public DIDerivedType {
+ public:
+ explicit DICompositeType(GlobalVariable *GV)
+ : DIDerivedType(GV, true, true) {
+ if (GV && !isCompositeType(getTag()))
+ GV = 0;
+ }
+
+ DIArray getTypeArray() const { return getFieldAs<DIArray>(10); }
+ unsigned getRunTimeLang() const { return getUnsignedField(11); }
+
+ /// Verify - Verify that a composite type descriptor is well formed.
+ bool Verify() const;
+
+ /// dump - print composite type.
+ void dump() const;
+ };
+
+ /// DIGlobal - This is a common class for global variables and subprograms.
+ class DIGlobal : public DIDescriptor {
+ protected:
+ explicit DIGlobal(GlobalVariable *GV, unsigned RequiredTag)
+ : DIDescriptor(GV, RequiredTag) {}
+
+ /// isSubprogram - Return true if the specified tag is legal for
+ /// DISubprogram.
+ static bool isSubprogram(unsigned TAG) {
+ return TAG == dwarf::DW_TAG_subprogram;
+ }
+
+ /// isGlobalVariable - Return true if the specified tag is legal for
+ /// DIGlobalVariable.
+ static bool isGlobalVariable(unsigned TAG) {
+ return TAG == dwarf::DW_TAG_variable;
+ }
+
+ public:
+ virtual ~DIGlobal() {}
+
+ DIDescriptor getContext() const { return getDescriptorField(2); }
+ const std::string &getName(std::string &F) const {
+ return getStringField(3, F);
+ }
+ const std::string &getDisplayName(std::string &F) const {
+ return getStringField(4, F);
+ }
+ const std::string &getLinkageName(std::string &F) const {
+ return getStringField(5, F);
+ }
+ DICompileUnit getCompileUnit() const{ return getFieldAs<DICompileUnit>(6); }
+ unsigned getLineNumber() const { return getUnsignedField(7); }
+ DIType getType() const { return getFieldAs<DIType>(8); }
+
+ /// isLocalToUnit - Return true if this subprogram is local to the current
+ /// compile unit, like 'static' in C.
+ unsigned isLocalToUnit() const { return getUnsignedField(9); }
+ unsigned isDefinition() const { return getUnsignedField(10); }
+
+ /// dump - print global.
+ void dump() const;
+ };
+
+ /// DISubprogram - This is a wrapper for a subprogram (e.g. a function).
+ class DISubprogram : public DIGlobal {
+ public:
+ explicit DISubprogram(GlobalVariable *GV = 0)
+ : DIGlobal(GV, dwarf::DW_TAG_subprogram) {}
+
+ DICompositeType getType() const { return getFieldAs<DICompositeType>(8); }
+
+ /// Verify - Verify that a subprogram descriptor is well formed.
+ bool Verify() const;
+
+ /// dump - print subprogram.
+ void dump() const;
+
+ /// describes - Return true if this subprogram provides debugging
+ /// information for the function F.
+ bool describes(const Function *F);
+ };
+
+ /// DIGlobalVariable - This is a wrapper for a global variable.
+ class DIGlobalVariable : public DIGlobal {
+ public:
+ explicit DIGlobalVariable(GlobalVariable *GV = 0)
+ : DIGlobal(GV, dwarf::DW_TAG_variable) {}
+
+ GlobalVariable *getGlobal() const { return getGlobalVariableField(11); }
+
+ /// Verify - Verify that a global variable descriptor is well formed.
+ bool Verify() const;
+
+ /// dump - print global variable.
+ void dump() const;
+ };
+
+ /// DIVariable - This is a wrapper for a variable (e.g. parameter, local,
+ /// global etc).
+ class DIVariable : public DIDescriptor {
+ public:
+ explicit DIVariable(GlobalVariable *gv = 0)
+ : DIDescriptor(gv) {
+ if (gv && !isVariable(getTag()))
+ GV = 0;
+ }
+
+ DIDescriptor getContext() const { return getDescriptorField(1); }
+ const std::string &getName(std::string &F) const {
+ return getStringField(2, F);
+ }
+ DICompileUnit getCompileUnit() const{ return getFieldAs<DICompileUnit>(3); }
+ unsigned getLineNumber() const { return getUnsignedField(4); }
+ DIType getType() const { return getFieldAs<DIType>(5); }
+
+ /// isVariable - Return true if the specified tag is legal for DIVariable.
+ static bool isVariable(unsigned Tag);
+
+ /// Verify - Verify that a variable descriptor is well formed.
+ bool Verify() const;
+
+ /// dump - print variable.
+ void dump() const;
+ };
+
+ /// DIBlock - This is a wrapper for a block (e.g. a function, scope, etc).
+ class DIBlock : public DIDescriptor {
+ public:
+ explicit DIBlock(GlobalVariable *GV = 0)
+ : DIDescriptor(GV, dwarf::DW_TAG_lexical_block) {}
+
+ DIDescriptor getContext() const { return getDescriptorField(1); }
+ };
+
+ /// DIFactory - This object assists with the construction of the various
+ /// descriptors.
+ class DIFactory {
+ Module &M;
+ // Cached values for uniquing and faster lookups.
+ DIAnchor CompileUnitAnchor, SubProgramAnchor, GlobalVariableAnchor;
+ const Type *EmptyStructPtr; // "{}*".
+ Function *StopPointFn; // llvm.dbg.stoppoint
+ Function *FuncStartFn; // llvm.dbg.func.start
+ Function *RegionStartFn; // llvm.dbg.region.start
+ Function *RegionEndFn; // llvm.dbg.region.end
+ Function *DeclareFn; // llvm.dbg.declare
+ StringMap<Constant*> StringCache;
+ DenseMap<Constant*, DIDescriptor> SimpleConstantCache;
+
+ DIFactory(const DIFactory &); // DO NOT IMPLEMENT
+ void operator=(const DIFactory&); // DO NOT IMPLEMENT
+ public:
+ explicit DIFactory(Module &m);
+
+ /// GetOrCreateCompileUnitAnchor - Return the anchor for compile units,
+ /// creating a new one if there isn't already one in the module.
+ DIAnchor GetOrCreateCompileUnitAnchor();
+
+ /// GetOrCreateSubprogramAnchor - Return the anchor for subprograms,
+ /// creating a new one if there isn't already one in the module.
+ DIAnchor GetOrCreateSubprogramAnchor();
+
+ /// GetOrCreateGlobalVariableAnchor - Return the anchor for globals,
+ /// creating a new one if there isn't already one in the module.
+ DIAnchor GetOrCreateGlobalVariableAnchor();
+
+ /// GetOrCreateArray - Create an descriptor for an array of descriptors.
+ /// This implicitly uniques the arrays created.
+ DIArray GetOrCreateArray(DIDescriptor *Tys, unsigned NumTys);
+
+ /// GetOrCreateSubrange - Create a descriptor for a value range. This
+ /// implicitly uniques the values returned.
+ DISubrange GetOrCreateSubrange(int64_t Lo, int64_t Hi);
+
+ /// CreateCompileUnit - Create a new descriptor for the specified compile
+ /// unit.
+ DICompileUnit CreateCompileUnit(unsigned LangID,
+ const std::string &Filename,
+ const std::string &Directory,
+ const std::string &Producer,
+ bool isMain = false,
+ bool isOptimized = false,
+ const char *Flags = "",
+ unsigned RunTimeVer = 0);
+
+ /// CreateEnumerator - Create a single enumerator value.
+ DIEnumerator CreateEnumerator(const std::string &Name, uint64_t Val);
+
+ /// CreateBasicType - Create a basic type like int, float, etc.
+ DIBasicType CreateBasicType(DIDescriptor Context, const std::string &Name,
+ DICompileUnit CompileUnit, unsigned LineNumber,
+ uint64_t SizeInBits, uint64_t AlignInBits,
+ uint64_t OffsetInBits, unsigned Flags,
+ unsigned Encoding);
+
+ /// CreateDerivedType - Create a derived type like const qualified type,
+ /// pointer, typedef, etc.
+ DIDerivedType CreateDerivedType(unsigned Tag, DIDescriptor Context,
+ const std::string &Name,
+ DICompileUnit CompileUnit,
+ unsigned LineNumber,
+ uint64_t SizeInBits, uint64_t AlignInBits,
+ uint64_t OffsetInBits, unsigned Flags,
+ DIType DerivedFrom);
+
+ /// CreateCompositeType - Create a composite type like array, struct, etc.
+ DICompositeType CreateCompositeType(unsigned Tag, DIDescriptor Context,
+ const std::string &Name,
+ DICompileUnit CompileUnit,
+ unsigned LineNumber,
+ uint64_t SizeInBits,
+ uint64_t AlignInBits,
+ uint64_t OffsetInBits, unsigned Flags,
+ DIType DerivedFrom,
+ DIArray Elements,
+ unsigned RunTimeLang = 0);
+
+ /// CreateSubprogram - Create a new descriptor for the specified subprogram.
+ /// See comments in DISubprogram for descriptions of these fields.
+ DISubprogram CreateSubprogram(DIDescriptor Context, const std::string &Name,
+ const std::string &DisplayName,
+ const std::string &LinkageName,
+ DICompileUnit CompileUnit, unsigned LineNo,
+ DIType Type, bool isLocalToUnit,
+ bool isDefinition);
+
+ /// CreateGlobalVariable - Create a new descriptor for the specified global.
+ DIGlobalVariable
+ CreateGlobalVariable(DIDescriptor Context, const std::string &Name,
+ const std::string &DisplayName,
+ const std::string &LinkageName,
+ DICompileUnit CompileUnit,
+ unsigned LineNo, DIType Type, bool isLocalToUnit,
+ bool isDefinition, llvm::GlobalVariable *GV);
+
+ /// CreateVariable - Create a new descriptor for the specified variable.
+ DIVariable CreateVariable(unsigned Tag, DIDescriptor Context,
+ const std::string &Name,
+ DICompileUnit CompileUnit, unsigned LineNo,
+ DIType Type);
+
+ /// CreateBlock - This creates a descriptor for a lexical block with the
+ /// specified parent context.
+ DIBlock CreateBlock(DIDescriptor Context);
+
+ /// InsertStopPoint - Create a new llvm.dbg.stoppoint intrinsic invocation,
+ /// inserting it at the end of the specified basic block.
+ void InsertStopPoint(DICompileUnit CU, unsigned LineNo, unsigned ColNo,
+ BasicBlock *BB);
+
+ /// InsertSubprogramStart - Create a new llvm.dbg.func.start intrinsic to
+ /// mark the start of the specified subprogram.
+ void InsertSubprogramStart(DISubprogram SP, BasicBlock *BB);
+
+ /// InsertRegionStart - Insert a new llvm.dbg.region.start intrinsic call to
+ /// mark the start of a region for the specified scoping descriptor.
+ void InsertRegionStart(DIDescriptor D, BasicBlock *BB);
+
+ /// InsertRegionEnd - Insert a new llvm.dbg.region.end intrinsic call to
+ /// mark the end of a region for the specified scoping descriptor.
+ void InsertRegionEnd(DIDescriptor D, BasicBlock *BB);
+
+ /// InsertDeclare - Insert a new llvm.dbg.declare intrinsic call.
+ void InsertDeclare(llvm::Value *Storage, DIVariable D, BasicBlock *BB);
+
+ private:
+ Constant *GetTagConstant(unsigned TAG);
+ Constant *GetStringConstant(const std::string &String);
+ DIAnchor GetOrCreateAnchor(unsigned TAG, const char *Name);
+
+ /// getCastToEmpty - Return the descriptor as a Constant* with type '{}*'.
+ Constant *getCastToEmpty(DIDescriptor D);
+ };
+
+ /// Finds the stoppoint coressponding to this instruction, that is the
+ /// stoppoint that dominates this instruction
+ const DbgStopPointInst *findStopPoint(const Instruction *Inst);
+
+ /// Finds the stoppoint corresponding to first real (non-debug intrinsic)
+ /// instruction in this Basic Block, and returns the stoppoint for it.
+ const DbgStopPointInst *findBBStopPoint(const BasicBlock *BB);
+
+ /// Finds the dbg.declare intrinsic corresponding to this value if any.
+ /// It looks through pointer casts too.
+ const DbgDeclareInst *findDbgDeclare(const Value *V, bool stripCasts = true);
+
+ /// Find the debug info descriptor corresponding to this global variable.
+ Value *findDbgGlobalDeclare(GlobalVariable *V);
+
+ bool getLocationInfo(const Value *V, std::string &DisplayName, std::string &Type,
+ unsigned &LineNo, std::string &File, std::string &Dir);
+} // end namespace llvm
+
+#endif
diff --git a/include/llvm/Analysis/DominatorInternals.h b/include/llvm/Analysis/DominatorInternals.h
new file mode 100644
index 000000000000..cca0d502b69c
--- /dev/null
+++ b/include/llvm/Analysis/DominatorInternals.h
@@ -0,0 +1,363 @@
+//=== llvm/Analysis/DominatorInternals.h - Dominator Calculation -*- C++ -*-==//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ANALYSIS_DOMINATOR_INTERNALS_H
+#define LLVM_ANALYSIS_DOMINATOR_INTERNALS_H
+
+#include "llvm/Analysis/Dominators.h"
+#include "llvm/ADT/SmallPtrSet.h"
+
+//===----------------------------------------------------------------------===//
+//
+// DominatorTree construction - This pass constructs immediate dominator
+// information for a flow-graph based on the algorithm described in this
+// document:
+//
+// A Fast Algorithm for Finding Dominators in a Flowgraph
+// T. Lengauer & R. Tarjan, ACM TOPLAS July 1979, pgs 121-141.
+//
+// This implements both the O(n*ack(n)) and the O(n*log(n)) versions of EVAL and
+// LINK, but it turns out that the theoretically slower O(n*log(n))
+// implementation is actually faster than the "efficient" algorithm (even for
+// large CFGs) because the constant overheads are substantially smaller. The
+// lower-complexity version can be enabled with the following #define:
+//
+#define BALANCE_IDOM_TREE 0
+//
+//===----------------------------------------------------------------------===//
+
+namespace llvm {
+
+template<class GraphT>
+unsigned DFSPass(DominatorTreeBase<typename GraphT::NodeType>& DT,
+ typename GraphT::NodeType* V, unsigned N) {
+ // This is more understandable as a recursive algorithm, but we can't use the
+ // recursive algorithm due to stack depth issues. Keep it here for
+ // documentation purposes.
+#if 0
+ InfoRec &VInfo = DT.Info[DT.Roots[i]];
+ VInfo.DFSNum = VInfo.Semi = ++N;
+ VInfo.Label = V;
+
+ Vertex.push_back(V); // Vertex[n] = V;
+ //Info[V].Ancestor = 0; // Ancestor[n] = 0
+ //Info[V].Child = 0; // Child[v] = 0
+ VInfo.Size = 1; // Size[v] = 1
+
+ for (succ_iterator SI = succ_begin(V), E = succ_end(V); SI != E; ++SI) {
+ InfoRec &SuccVInfo = DT.Info[*SI];
+ if (SuccVInfo.Semi == 0) {
+ SuccVInfo.Parent = V;
+ N = DTDFSPass(DT, *SI, N);
+ }
+ }
+#else
+ bool IsChilOfArtificialExit = (N != 0);
+
+ std::vector<std::pair<typename GraphT::NodeType*,
+ typename GraphT::ChildIteratorType> > Worklist;
+ Worklist.push_back(std::make_pair(V, GraphT::child_begin(V)));
+ while (!Worklist.empty()) {
+ typename GraphT::NodeType* BB = Worklist.back().first;
+ typename GraphT::ChildIteratorType NextSucc = Worklist.back().second;
+
+ typename DominatorTreeBase<typename GraphT::NodeType>::InfoRec &BBInfo =
+ DT.Info[BB];
+
+ // First time we visited this BB?
+ if (NextSucc == GraphT::child_begin(BB)) {
+ BBInfo.DFSNum = BBInfo.Semi = ++N;
+ BBInfo.Label = BB;
+
+ DT.Vertex.push_back(BB); // Vertex[n] = V;
+ //BBInfo[V].Ancestor = 0; // Ancestor[n] = 0
+ //BBInfo[V].Child = 0; // Child[v] = 0
+ BBInfo.Size = 1; // Size[v] = 1
+
+ if (IsChilOfArtificialExit)
+ BBInfo.Parent = 1;
+
+ IsChilOfArtificialExit = false;
+ }
+
+ // store the DFS number of the current BB - the reference to BBInfo might
+ // get invalidated when processing the successors.
+ unsigned BBDFSNum = BBInfo.DFSNum;
+
+ // If we are done with this block, remove it from the worklist.
+ if (NextSucc == GraphT::child_end(BB)) {
+ Worklist.pop_back();
+ continue;
+ }
+
+ // Increment the successor number for the next time we get to it.
+ ++Worklist.back().second;
+
+ // Visit the successor next, if it isn't already visited.
+ typename GraphT::NodeType* Succ = *NextSucc;
+
+ typename DominatorTreeBase<typename GraphT::NodeType>::InfoRec &SuccVInfo =
+ DT.Info[Succ];
+ if (SuccVInfo.Semi == 0) {
+ SuccVInfo.Parent = BBDFSNum;
+ Worklist.push_back(std::make_pair(Succ, GraphT::child_begin(Succ)));
+ }
+ }
+#endif
+ return N;
+}
+
+template<class GraphT>
+void Compress(DominatorTreeBase<typename GraphT::NodeType>& DT,
+ typename GraphT::NodeType *VIn) {
+ std::vector<typename GraphT::NodeType*> Work;
+ SmallPtrSet<typename GraphT::NodeType*, 32> Visited;
+ typename DominatorTreeBase<typename GraphT::NodeType>::InfoRec &VInVAInfo =
+ DT.Info[DT.Vertex[DT.Info[VIn].Ancestor]];
+
+ if (VInVAInfo.Ancestor != 0)
+ Work.push_back(VIn);
+
+ while (!Work.empty()) {
+ typename GraphT::NodeType* V = Work.back();
+ typename DominatorTreeBase<typename GraphT::NodeType>::InfoRec &VInfo =
+ DT.Info[V];
+ typename GraphT::NodeType* VAncestor = DT.Vertex[VInfo.Ancestor];
+ typename DominatorTreeBase<typename GraphT::NodeType>::InfoRec &VAInfo =
+ DT.Info[VAncestor];
+
+ // Process Ancestor first
+ if (Visited.insert(VAncestor) &&
+ VAInfo.Ancestor != 0) {
+ Work.push_back(VAncestor);
+ continue;
+ }
+ Work.pop_back();
+
+ // Update VInfo based on Ancestor info
+ if (VAInfo.Ancestor == 0)
+ continue;
+ typename GraphT::NodeType* VAncestorLabel = VAInfo.Label;
+ typename GraphT::NodeType* VLabel = VInfo.Label;
+ if (DT.Info[VAncestorLabel].Semi < DT.Info[VLabel].Semi)
+ VInfo.Label = VAncestorLabel;
+ VInfo.Ancestor = VAInfo.Ancestor;
+ }
+}
+
+template<class GraphT>
+typename GraphT::NodeType* Eval(DominatorTreeBase<typename GraphT::NodeType>& DT,
+ typename GraphT::NodeType *V) {
+ typename DominatorTreeBase<typename GraphT::NodeType>::InfoRec &VInfo =
+ DT.Info[V];
+#if !BALANCE_IDOM_TREE
+ // Higher-complexity but faster implementation
+ if (VInfo.Ancestor == 0)
+ return V;
+ Compress<GraphT>(DT, V);
+ return VInfo.Label;
+#else
+ // Lower-complexity but slower implementation
+ if (VInfo.Ancestor == 0)
+ return VInfo.Label;
+ Compress<GraphT>(DT, V);
+ GraphT::NodeType* VLabel = VInfo.Label;
+
+ GraphT::NodeType* VAncestorLabel = DT.Info[VInfo.Ancestor].Label;
+ if (DT.Info[VAncestorLabel].Semi >= DT.Info[VLabel].Semi)
+ return VLabel;
+ else
+ return VAncestorLabel;
+#endif
+}
+
+template<class GraphT>
+void Link(DominatorTreeBase<typename GraphT::NodeType>& DT,
+ unsigned DFSNumV, typename GraphT::NodeType* W,
+ typename DominatorTreeBase<typename GraphT::NodeType>::InfoRec &WInfo) {
+#if !BALANCE_IDOM_TREE
+ // Higher-complexity but faster implementation
+ WInfo.Ancestor = DFSNumV;
+#else
+ // Lower-complexity but slower implementation
+ GraphT::NodeType* WLabel = WInfo.Label;
+ unsigned WLabelSemi = DT.Info[WLabel].Semi;
+ GraphT::NodeType* S = W;
+ InfoRec *SInfo = &DT.Info[S];
+
+ GraphT::NodeType* SChild = SInfo->Child;
+ InfoRec *SChildInfo = &DT.Info[SChild];
+
+ while (WLabelSemi < DT.Info[SChildInfo->Label].Semi) {
+ GraphT::NodeType* SChildChild = SChildInfo->Child;
+ if (SInfo->Size+DT.Info[SChildChild].Size >= 2*SChildInfo->Size) {
+ SChildInfo->Ancestor = S;
+ SInfo->Child = SChild = SChildChild;
+ SChildInfo = &DT.Info[SChild];
+ } else {
+ SChildInfo->Size = SInfo->Size;
+ S = SInfo->Ancestor = SChild;
+ SInfo = SChildInfo;
+ SChild = SChildChild;
+ SChildInfo = &DT.Info[SChild];
+ }
+ }
+
+ DominatorTreeBase::InfoRec &VInfo = DT.Info[V];
+ SInfo->Label = WLabel;
+
+ assert(V != W && "The optimization here will not work in this case!");
+ unsigned WSize = WInfo.Size;
+ unsigned VSize = (VInfo.Size += WSize);
+
+ if (VSize < 2*WSize)
+ std::swap(S, VInfo.Child);
+
+ while (S) {
+ SInfo = &DT.Info[S];
+ SInfo->Ancestor = V;
+ S = SInfo->Child;
+ }
+#endif
+}
+
+template<class FuncT, class NodeT>
+void Calculate(DominatorTreeBase<typename GraphTraits<NodeT>::NodeType>& DT,
+ FuncT& F) {
+ typedef GraphTraits<NodeT> GraphT;
+
+ unsigned N = 0;
+ bool MultipleRoots = (DT.Roots.size() > 1);
+ if (MultipleRoots) {
+ typename DominatorTreeBase<typename GraphT::NodeType>::InfoRec &BBInfo =
+ DT.Info[NULL];
+ BBInfo.DFSNum = BBInfo.Semi = ++N;
+ BBInfo.Label = NULL;
+
+ DT.Vertex.push_back(NULL); // Vertex[n] = V;
+ //BBInfo[V].Ancestor = 0; // Ancestor[n] = 0
+ //BBInfo[V].Child = 0; // Child[v] = 0
+ BBInfo.Size = 1; // Size[v] = 1
+ }
+
+ // Step #1: Number blocks in depth-first order and initialize variables used
+ // in later stages of the algorithm.
+ for (unsigned i = 0, e = static_cast<unsigned>(DT.Roots.size());
+ i != e; ++i)
+ N = DFSPass<GraphT>(DT, DT.Roots[i], N);
+
+ // it might be that some blocks did not get a DFS number (e.g., blocks of
+ // infinite loops). In these cases an artificial exit node is required.
+ MultipleRoots |= (DT.isPostDominator() && N != F.size());
+
+ for (unsigned i = N; i >= 2; --i) {
+ typename GraphT::NodeType* W = DT.Vertex[i];
+ typename DominatorTreeBase<typename GraphT::NodeType>::InfoRec &WInfo =
+ DT.Info[W];
+
+ // Step #2: Calculate the semidominators of all vertices
+ bool HasChildOutsideDFS = false;
+
+ // initialize the semi dominator to point to the parent node
+ WInfo.Semi = WInfo.Parent;
+ for (typename GraphTraits<Inverse<NodeT> >::ChildIteratorType CI =
+ GraphTraits<Inverse<NodeT> >::child_begin(W),
+ E = GraphTraits<Inverse<NodeT> >::child_end(W); CI != E; ++CI) {
+ if (DT.Info.count(*CI)) { // Only if this predecessor is reachable!
+ unsigned SemiU = DT.Info[Eval<GraphT>(DT, *CI)].Semi;
+ if (SemiU < WInfo.Semi)
+ WInfo.Semi = SemiU;
+ }
+ else {
+ // if the child has no DFS number it is not post-dominated by any exit,
+ // and so is the current block.
+ HasChildOutsideDFS = true;
+ }
+ }
+
+ // if some child has no DFS number it is not post-dominated by any exit,
+ // and so is the current block.
+ if (DT.isPostDominator() && HasChildOutsideDFS)
+ WInfo.Semi = 0;
+
+ DT.Info[DT.Vertex[WInfo.Semi]].Bucket.push_back(W);
+
+ typename GraphT::NodeType* WParent = DT.Vertex[WInfo.Parent];
+ Link<GraphT>(DT, WInfo.Parent, W, WInfo);
+
+ // Step #3: Implicitly define the immediate dominator of vertices
+ std::vector<typename GraphT::NodeType*> &WParentBucket =
+ DT.Info[WParent].Bucket;
+ while (!WParentBucket.empty()) {
+ typename GraphT::NodeType* V = WParentBucket.back();
+ WParentBucket.pop_back();
+ typename GraphT::NodeType* U = Eval<GraphT>(DT, V);
+ DT.IDoms[V] = DT.Info[U].Semi < DT.Info[V].Semi ? U : WParent;
+ }
+ }
+
+ // Step #4: Explicitly define the immediate dominator of each vertex
+ for (unsigned i = 2; i <= N; ++i) {
+ typename GraphT::NodeType* W = DT.Vertex[i];
+ typename GraphT::NodeType*& WIDom = DT.IDoms[W];
+ if (WIDom != DT.Vertex[DT.Info[W].Semi])
+ WIDom = DT.IDoms[WIDom];
+ }
+
+ if (DT.Roots.empty()) return;
+
+ // Add a node for the root. This node might be the actual root, if there is
+ // one exit block, or it may be the virtual exit (denoted by (BasicBlock *)0)
+ // which postdominates all real exits if there are multiple exit blocks, or
+ // an infinite loop.
+ typename GraphT::NodeType* Root = !MultipleRoots ? DT.Roots[0] : 0;
+
+ DT.DomTreeNodes[Root] = DT.RootNode =
+ new DomTreeNodeBase<typename GraphT::NodeType>(Root, 0);
+
+ // Loop over all of the reachable blocks in the function...
+ for (unsigned i = 2; i <= N; ++i) {
+ typename GraphT::NodeType* W = DT.Vertex[i];
+
+ DomTreeNodeBase<typename GraphT::NodeType> *BBNode = DT.DomTreeNodes[W];
+ if (BBNode) continue; // Haven't calculated this node yet?
+
+ typename GraphT::NodeType* ImmDom = DT.getIDom(W);
+
+ assert(ImmDom || DT.DomTreeNodes[NULL]);
+
+ // Get or calculate the node for the immediate dominator
+ DomTreeNodeBase<typename GraphT::NodeType> *IDomNode =
+ DT.getNodeForBlock(ImmDom);
+
+ // Add a new tree node for this BasicBlock, and link it as a child of
+ // IDomNode
+ DomTreeNodeBase<typename GraphT::NodeType> *C =
+ new DomTreeNodeBase<typename GraphT::NodeType>(W, IDomNode);
+ DT.DomTreeNodes[W] = IDomNode->addChild(C);
+ }
+
+ // Free temporary memory used to construct idom's
+ DT.IDoms.clear();
+ DT.Info.clear();
+ std::vector<typename GraphT::NodeType*>().swap(DT.Vertex);
+
+ // FIXME: This does not work on PostDomTrees. It seems likely that this is
+ // due to an error in the algorithm for post-dominators. This really should
+ // be investigated and fixed at some point.
+ // DT.updateDFSNumbers();
+
+ // Start out with the DFS numbers being invalid. Let them be computed if
+ // demanded.
+ DT.DFSInfoValid = false;
+}
+
+}
+
+#endif
diff --git a/include/llvm/Analysis/Dominators.h b/include/llvm/Analysis/Dominators.h
new file mode 100644
index 000000000000..b405f5b71ed7
--- /dev/null
+++ b/include/llvm/Analysis/Dominators.h
@@ -0,0 +1,1055 @@
+//===- llvm/Analysis/Dominators.h - Dominator Info Calculation --*- 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 the following classes:
+// 1. DominatorTree: Represent dominators as an explicit tree structure.
+// 2. DominanceFrontier: Calculate and hold the dominance frontier for a
+// function.
+//
+// These data structures are listed in increasing order of complexity. It
+// takes longer to calculate the dominator frontier, for example, than the
+// DominatorTree mapping.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ANALYSIS_DOMINATORS_H
+#define LLVM_ANALYSIS_DOMINATORS_H
+
+#include "llvm/Pass.h"
+#include "llvm/BasicBlock.h"
+#include "llvm/Function.h"
+#include "llvm/Instructions.h"
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/GraphTraits.h"
+#include "llvm/ADT/SmallPtrSet.h"
+#include "llvm/ADT/SmallVector.h"
+#include "llvm/Assembly/Writer.h"
+#include "llvm/Support/CFG.h"
+#include "llvm/Support/Compiler.h"
+#include <algorithm>
+#include <map>
+#include <set>
+
+namespace llvm {
+
+//===----------------------------------------------------------------------===//
+/// DominatorBase - Base class that other, more interesting dominator analyses
+/// inherit from.
+///
+template <class NodeT>
+class DominatorBase {
+protected:
+ std::vector<NodeT*> Roots;
+ const bool IsPostDominators;
+ inline explicit DominatorBase(bool isPostDom) :
+ Roots(), IsPostDominators(isPostDom) {}
+public:
+
+ /// getRoots - Return the root blocks of the current CFG. This may include
+ /// multiple blocks if we are computing post dominators. For forward
+ /// dominators, this will always be a single block (the entry node).
+ ///
+ inline const std::vector<NodeT*> &getRoots() const { return Roots; }
+
+ /// isPostDominator - Returns true if analysis based of postdoms
+ ///
+ bool isPostDominator() const { return IsPostDominators; }
+};
+
+
+//===----------------------------------------------------------------------===//
+// DomTreeNode - Dominator Tree Node
+template<class NodeT> class DominatorTreeBase;
+struct PostDominatorTree;
+class MachineBasicBlock;
+
+template <class NodeT>
+class DomTreeNodeBase {
+ NodeT *TheBB;
+ DomTreeNodeBase<NodeT> *IDom;
+ std::vector<DomTreeNodeBase<NodeT> *> Children;
+ int DFSNumIn, DFSNumOut;
+
+ template<class N> friend class DominatorTreeBase;
+ friend struct PostDominatorTree;
+public:
+ typedef typename std::vector<DomTreeNodeBase<NodeT> *>::iterator iterator;
+ typedef typename std::vector<DomTreeNodeBase<NodeT> *>::const_iterator
+ const_iterator;
+
+ iterator begin() { return Children.begin(); }
+ iterator end() { return Children.end(); }
+ const_iterator begin() const { return Children.begin(); }
+ const_iterator end() const { return Children.end(); }
+
+ NodeT *getBlock() const { return TheBB; }
+ DomTreeNodeBase<NodeT> *getIDom() const { return IDom; }
+ const std::vector<DomTreeNodeBase<NodeT>*> &getChildren() const {
+ return Children;
+ }
+
+ DomTreeNodeBase(NodeT *BB, DomTreeNodeBase<NodeT> *iDom)
+ : TheBB(BB), IDom(iDom), DFSNumIn(-1), DFSNumOut(-1) { }
+
+ DomTreeNodeBase<NodeT> *addChild(DomTreeNodeBase<NodeT> *C) {
+ Children.push_back(C);
+ return C;
+ }
+
+ size_t getNumChildren() const {
+ return Children.size();
+ }
+
+ void clearAllChildren() {
+ Children.clear();
+ }
+
+ bool compare(DomTreeNodeBase<NodeT> *Other) {
+ if (getNumChildren() != Other->getNumChildren())
+ return true;
+
+ SmallPtrSet<NodeT *, 4> OtherChildren;
+ for(iterator I = Other->begin(), E = Other->end(); I != E; ++I) {
+ NodeT *Nd = (*I)->getBlock();
+ OtherChildren.insert(Nd);
+ }
+
+ for(iterator I = begin(), E = end(); I != E; ++I) {
+ NodeT *N = (*I)->getBlock();
+ if (OtherChildren.count(N) == 0)
+ return true;
+ }
+ return false;
+ }
+
+ void setIDom(DomTreeNodeBase<NodeT> *NewIDom) {
+ assert(IDom && "No immediate dominator?");
+ if (IDom != NewIDom) {
+ typename std::vector<DomTreeNodeBase<NodeT>*>::iterator I =
+ std::find(IDom->Children.begin(), IDom->Children.end(), this);
+ assert(I != IDom->Children.end() &&
+ "Not in immediate dominator children set!");
+ // I am no longer your child...
+ IDom->Children.erase(I);
+
+ // Switch to new dominator
+ IDom = NewIDom;
+ IDom->Children.push_back(this);
+ }
+ }
+
+ /// getDFSNumIn/getDFSNumOut - These are an internal implementation detail, do
+ /// not call them.
+ unsigned getDFSNumIn() const { return DFSNumIn; }
+ unsigned getDFSNumOut() const { return DFSNumOut; }
+private:
+ // Return true if this node is dominated by other. Use this only if DFS info
+ // is valid.
+ bool DominatedBy(const DomTreeNodeBase<NodeT> *other) const {
+ return this->DFSNumIn >= other->DFSNumIn &&
+ this->DFSNumOut <= other->DFSNumOut;
+ }
+};
+
+EXTERN_TEMPLATE_INSTANTIATION(class DomTreeNodeBase<BasicBlock>);
+EXTERN_TEMPLATE_INSTANTIATION(class DomTreeNodeBase<MachineBasicBlock>);
+
+template<class NodeT>
+static std::ostream &operator<<(std::ostream &o,
+ const DomTreeNodeBase<NodeT> *Node) {
+ if (Node->getBlock())
+ WriteAsOperand(o, Node->getBlock(), false);
+ else
+ o << " <<exit node>>";
+
+ o << " {" << Node->getDFSNumIn() << "," << Node->getDFSNumOut() << "}";
+
+ return o << "\n";
+}
+
+template<class NodeT>
+static void PrintDomTree(const DomTreeNodeBase<NodeT> *N, std::ostream &o,
+ unsigned Lev) {
+ o << std::string(2*Lev, ' ') << "[" << Lev << "] " << N;
+ for (typename DomTreeNodeBase<NodeT>::const_iterator I = N->begin(),
+ E = N->end(); I != E; ++I)
+ PrintDomTree<NodeT>(*I, o, Lev+1);
+}
+
+typedef DomTreeNodeBase<BasicBlock> DomTreeNode;
+
+//===----------------------------------------------------------------------===//
+/// DominatorTree - Calculate the immediate dominator tree for a function.
+///
+
+template<class FuncT, class N>
+void Calculate(DominatorTreeBase<typename GraphTraits<N>::NodeType>& DT,
+ FuncT& F);
+
+template<class NodeT>
+class DominatorTreeBase : public DominatorBase<NodeT> {
+protected:
+ typedef DenseMap<NodeT*, DomTreeNodeBase<NodeT>*> DomTreeNodeMapType;
+ DomTreeNodeMapType DomTreeNodes;
+ DomTreeNodeBase<NodeT> *RootNode;
+
+ bool DFSInfoValid;
+ unsigned int SlowQueries;
+ // Information record used during immediate dominators computation.
+ struct InfoRec {
+ unsigned DFSNum;
+ unsigned Semi;
+ unsigned Size;
+ NodeT *Label, *Child;
+ unsigned Parent, Ancestor;
+
+ std::vector<NodeT*> Bucket;
+
+ InfoRec() : DFSNum(0), Semi(0), Size(0), Label(0), Child(0), Parent(0),
+ Ancestor(0) {}
+ };
+
+ DenseMap<NodeT*, NodeT*> IDoms;
+
+ // Vertex - Map the DFS number to the BasicBlock*
+ std::vector<NodeT*> Vertex;
+
+ // Info - Collection of information used during the computation of idoms.
+ DenseMap<NodeT*, InfoRec> Info;
+
+ void reset() {
+ for (typename DomTreeNodeMapType::iterator I = this->DomTreeNodes.begin(),
+ E = DomTreeNodes.end(); I != E; ++I)
+ delete I->second;
+ DomTreeNodes.clear();
+ IDoms.clear();
+ this->Roots.clear();
+ Vertex.clear();
+ RootNode = 0;
+ }
+
+ // NewBB is split and now it has one successor. Update dominator tree to
+ // reflect this change.
+ template<class N, class GraphT>
+ void Split(DominatorTreeBase<typename GraphT::NodeType>& DT,
+ typename GraphT::NodeType* NewBB) {
+ assert(std::distance(GraphT::child_begin(NewBB), GraphT::child_end(NewBB)) == 1
+ && "NewBB should have a single successor!");
+ typename GraphT::NodeType* NewBBSucc = *GraphT::child_begin(NewBB);
+
+ std::vector<typename GraphT::NodeType*> PredBlocks;
+ for (typename GraphTraits<Inverse<N> >::ChildIteratorType PI =
+ GraphTraits<Inverse<N> >::child_begin(NewBB),
+ PE = GraphTraits<Inverse<N> >::child_end(NewBB); PI != PE; ++PI)
+ PredBlocks.push_back(*PI);
+
+ assert(!PredBlocks.empty() && "No predblocks??");
+
+ bool NewBBDominatesNewBBSucc = true;
+ for (typename GraphTraits<Inverse<N> >::ChildIteratorType PI =
+ GraphTraits<Inverse<N> >::child_begin(NewBBSucc),
+ E = GraphTraits<Inverse<N> >::child_end(NewBBSucc); PI != E; ++PI)
+ if (*PI != NewBB && !DT.dominates(NewBBSucc, *PI) &&
+ DT.isReachableFromEntry(*PI)) {
+ NewBBDominatesNewBBSucc = false;
+ break;
+ }
+
+ // Find NewBB's immediate dominator and create new dominator tree node for
+ // NewBB.
+ NodeT *NewBBIDom = 0;
+ unsigned i = 0;
+ for (i = 0; i < PredBlocks.size(); ++i)
+ if (DT.isReachableFromEntry(PredBlocks[i])) {
+ NewBBIDom = PredBlocks[i];
+ break;
+ }
+ assert(i != PredBlocks.size() && "No reachable preds?");
+ for (i = i + 1; i < PredBlocks.size(); ++i) {
+ if (DT.isReachableFromEntry(PredBlocks[i]))
+ NewBBIDom = DT.findNearestCommonDominator(NewBBIDom, PredBlocks[i]);
+ }
+ assert(NewBBIDom && "No immediate dominator found??");
+
+ // Create the new dominator tree node... and set the idom of NewBB.
+ DomTreeNodeBase<NodeT> *NewBBNode = DT.addNewBlock(NewBB, NewBBIDom);
+
+ // If NewBB strictly dominates other blocks, then it is now the immediate
+ // dominator of NewBBSucc. Update the dominator tree as appropriate.
+ if (NewBBDominatesNewBBSucc) {
+ DomTreeNodeBase<NodeT> *NewBBSuccNode = DT.getNode(NewBBSucc);
+ DT.changeImmediateDominator(NewBBSuccNode, NewBBNode);
+ }
+ }
+
+public:
+ explicit DominatorTreeBase(bool isPostDom)
+ : DominatorBase<NodeT>(isPostDom), DFSInfoValid(false), SlowQueries(0) {}
+ virtual ~DominatorTreeBase() { reset(); }
+
+ // FIXME: Should remove this
+ virtual bool runOnFunction(Function &F) { return false; }
+
+ /// compare - Return false if the other dominator tree base matches this
+ /// dominator tree base. Otherwise return true.
+ bool compare(DominatorTreeBase &Other) const {
+
+ const DomTreeNodeMapType &OtherDomTreeNodes = Other.DomTreeNodes;
+ if (DomTreeNodes.size() != OtherDomTreeNodes.size())
+ return true;
+
+ SmallPtrSet<const NodeT *,4> MyBBs;
+ for (typename DomTreeNodeMapType::const_iterator
+ I = this->DomTreeNodes.begin(),
+ E = this->DomTreeNodes.end(); I != E; ++I) {
+ NodeT *BB = I->first;
+ typename DomTreeNodeMapType::const_iterator OI = OtherDomTreeNodes.find(BB);
+ if (OI == OtherDomTreeNodes.end())
+ return true;
+
+ DomTreeNodeBase<NodeT>* MyNd = I->second;
+ DomTreeNodeBase<NodeT>* OtherNd = OI->second;
+
+ if (MyNd->compare(OtherNd))
+ return true;
+ }
+
+ return false;
+ }
+
+ virtual void releaseMemory() { reset(); }
+
+ /// getNode - return the (Post)DominatorTree node for the specified basic
+ /// block. This is the same as using operator[] on this class.
+ ///
+ inline DomTreeNodeBase<NodeT> *getNode(NodeT *BB) const {
+ typename DomTreeNodeMapType::const_iterator I = DomTreeNodes.find(BB);
+ return I != DomTreeNodes.end() ? I->second : 0;
+ }
+
+ /// getRootNode - This returns the entry node for the CFG of the function. If
+ /// this tree represents the post-dominance relations for a function, however,
+ /// this root may be a node with the block == NULL. This is the case when
+ /// there are multiple exit nodes from a particular function. Consumers of
+ /// post-dominance information must be capable of dealing with this
+ /// possibility.
+ ///
+ DomTreeNodeBase<NodeT> *getRootNode() { return RootNode; }
+ const DomTreeNodeBase<NodeT> *getRootNode() const { return RootNode; }
+
+ /// properlyDominates - Returns true iff this dominates N and this != N.
+ /// Note that this is not a constant time operation!
+ ///
+ bool properlyDominates(const DomTreeNodeBase<NodeT> *A,
+ DomTreeNodeBase<NodeT> *B) const {
+ if (A == 0 || B == 0) return false;
+ return dominatedBySlowTreeWalk(A, B);
+ }
+
+ inline bool properlyDominates(NodeT *A, NodeT *B) {
+ return properlyDominates(getNode(A), getNode(B));
+ }
+
+ bool dominatedBySlowTreeWalk(const DomTreeNodeBase<NodeT> *A,
+ const DomTreeNodeBase<NodeT> *B) const {
+ const DomTreeNodeBase<NodeT> *IDom;
+ if (A == 0 || B == 0) return false;
+ while ((IDom = B->getIDom()) != 0 && IDom != A && IDom != B)
+ B = IDom; // Walk up the tree
+ return IDom != 0;
+ }
+
+
+ /// isReachableFromEntry - Return true if A is dominated by the entry
+ /// block of the function containing it.
+ bool isReachableFromEntry(NodeT* A) {
+ assert (!this->isPostDominator()
+ && "This is not implemented for post dominators");
+ return dominates(&A->getParent()->front(), A);
+ }
+
+ /// dominates - Returns true iff A dominates B. Note that this is not a
+ /// constant time operation!
+ ///
+ inline bool dominates(const DomTreeNodeBase<NodeT> *A,
+ DomTreeNodeBase<NodeT> *B) {
+ if (B == A)
+ return true; // A node trivially dominates itself.
+
+ if (A == 0 || B == 0)
+ return false;
+
+ if (DFSInfoValid)
+ return B->DominatedBy(A);
+
+ // If we end up with too many slow queries, just update the
+ // DFS numbers on the theory that we are going to keep querying.
+ SlowQueries++;
+ if (SlowQueries > 32) {
+ updateDFSNumbers();
+ return B->DominatedBy(A);
+ }
+
+ return dominatedBySlowTreeWalk(A, B);
+ }
+
+ inline bool dominates(NodeT *A, NodeT *B) {
+ if (A == B)
+ return true;
+
+ return dominates(getNode(A), getNode(B));
+ }
+
+ NodeT *getRoot() const {
+ assert(this->Roots.size() == 1 && "Should always have entry node!");
+ return this->Roots[0];
+ }
+
+ /// findNearestCommonDominator - Find nearest common dominator basic block
+ /// for basic block A and B. If there is no such block then return NULL.
+ NodeT *findNearestCommonDominator(NodeT *A, NodeT *B) {
+
+ assert (!this->isPostDominator()
+ && "This is not implemented for post dominators");
+ assert (A->getParent() == B->getParent()
+ && "Two blocks are not in same function");
+
+ // If either A or B is a entry block then it is nearest common dominator.
+ NodeT &Entry = A->getParent()->front();
+ if (A == &Entry || B == &Entry)
+ return &Entry;
+
+ // If B dominates A then B is nearest common dominator.
+ if (dominates(B, A))
+ return B;
+
+ // If A dominates B then A is nearest common dominator.
+ if (dominates(A, B))
+ return A;
+
+ DomTreeNodeBase<NodeT> *NodeA = getNode(A);
+ DomTreeNodeBase<NodeT> *NodeB = getNode(B);
+
+ // Collect NodeA dominators set.
+ SmallPtrSet<DomTreeNodeBase<NodeT>*, 16> NodeADoms;
+ NodeADoms.insert(NodeA);
+ DomTreeNodeBase<NodeT> *IDomA = NodeA->getIDom();
+ while (IDomA) {
+ NodeADoms.insert(IDomA);
+ IDomA = IDomA->getIDom();
+ }
+
+ // Walk NodeB immediate dominators chain and find common dominator node.
+ DomTreeNodeBase<NodeT> *IDomB = NodeB->getIDom();
+ while(IDomB) {
+ if (NodeADoms.count(IDomB) != 0)
+ return IDomB->getBlock();
+
+ IDomB = IDomB->getIDom();
+ }
+
+ return NULL;
+ }
+
+ //===--------------------------------------------------------------------===//
+ // API to update (Post)DominatorTree information based on modifications to
+ // the CFG...
+
+ /// addNewBlock - Add a new node to the dominator tree information. This
+ /// creates a new node as a child of DomBB dominator node,linking it into
+ /// the children list of the immediate dominator.
+ DomTreeNodeBase<NodeT> *addNewBlock(NodeT *BB, NodeT *DomBB) {
+ assert(getNode(BB) == 0 && "Block already in dominator tree!");
+ DomTreeNodeBase<NodeT> *IDomNode = getNode(DomBB);
+ assert(IDomNode && "Not immediate dominator specified for block!");
+ DFSInfoValid = false;
+ return DomTreeNodes[BB] =
+ IDomNode->addChild(new DomTreeNodeBase<NodeT>(BB, IDomNode));
+ }
+
+ /// changeImmediateDominator - This method is used to update the dominator
+ /// tree information when a node's immediate dominator changes.
+ ///
+ void changeImmediateDominator(DomTreeNodeBase<NodeT> *N,
+ DomTreeNodeBase<NodeT> *NewIDom) {
+ assert(N && NewIDom && "Cannot change null node pointers!");
+ DFSInfoValid = false;
+ N->setIDom(NewIDom);
+ }
+
+ void changeImmediateDominator(NodeT *BB, NodeT *NewBB) {
+ changeImmediateDominator(getNode(BB), getNode(NewBB));
+ }
+
+ /// eraseNode - Removes a node from the dominator tree. Block must not
+ /// domiante any other blocks. Removes node from its immediate dominator's
+ /// children list. Deletes dominator node associated with basic block BB.
+ void eraseNode(NodeT *BB) {
+ DomTreeNodeBase<NodeT> *Node = getNode(BB);
+ assert (Node && "Removing node that isn't in dominator tree.");
+ assert (Node->getChildren().empty() && "Node is not a leaf node.");
+
+ // Remove node from immediate dominator's children list.
+ DomTreeNodeBase<NodeT> *IDom = Node->getIDom();
+ if (IDom) {
+ typename std::vector<DomTreeNodeBase<NodeT>*>::iterator I =
+ std::find(IDom->Children.begin(), IDom->Children.end(), Node);
+ assert(I != IDom->Children.end() &&
+ "Not in immediate dominator children set!");
+ // I am no longer your child...
+ IDom->Children.erase(I);
+ }
+
+ DomTreeNodes.erase(BB);
+ delete Node;
+ }
+
+ /// removeNode - Removes a node from the dominator tree. Block must not
+ /// dominate any other blocks. Invalidates any node pointing to removed
+ /// block.
+ void removeNode(NodeT *BB) {
+ assert(getNode(BB) && "Removing node that isn't in dominator tree.");
+ DomTreeNodes.erase(BB);
+ }
+
+ /// splitBlock - BB is split and now it has one successor. Update dominator
+ /// tree to reflect this change.
+ void splitBlock(NodeT* NewBB) {
+ if (this->IsPostDominators)
+ this->Split<Inverse<NodeT*>, GraphTraits<Inverse<NodeT*> > >(*this, NewBB);
+ else
+ this->Split<NodeT*, GraphTraits<NodeT*> >(*this, NewBB);
+ }
+
+ /// print - Convert to human readable form
+ ///
+ virtual void print(std::ostream &o, const Module* ) const {
+ o << "=============================--------------------------------\n";
+ if (this->isPostDominator())
+ o << "Inorder PostDominator Tree: ";
+ else
+ o << "Inorder Dominator Tree: ";
+ if (this->DFSInfoValid)
+ o << "DFSNumbers invalid: " << SlowQueries << " slow queries.";
+ o << "\n";
+
+ PrintDomTree<NodeT>(getRootNode(), o, 1);
+ }
+
+ void print(std::ostream *OS, const Module* M = 0) const {
+ if (OS) print(*OS, M);
+ }
+
+ virtual void dump() {
+ print(llvm::cerr);
+ }
+
+protected:
+ template<class GraphT>
+ friend void Compress(DominatorTreeBase<typename GraphT::NodeType>& DT,
+ typename GraphT::NodeType* VIn);
+
+ template<class GraphT>
+ friend typename GraphT::NodeType* Eval(
+ DominatorTreeBase<typename GraphT::NodeType>& DT,
+ typename GraphT::NodeType* V);
+
+ template<class GraphT>
+ friend void Link(DominatorTreeBase<typename GraphT::NodeType>& DT,
+ unsigned DFSNumV, typename GraphT::NodeType* W,
+ typename DominatorTreeBase<typename GraphT::NodeType>::InfoRec &WInfo);
+
+ template<class GraphT>
+ friend unsigned DFSPass(DominatorTreeBase<typename GraphT::NodeType>& DT,
+ typename GraphT::NodeType* V,
+ unsigned N);
+
+ template<class FuncT, class N>
+ friend void Calculate(DominatorTreeBase<typename GraphTraits<N>::NodeType>& DT,
+ FuncT& F);
+
+ /// updateDFSNumbers - Assign In and Out numbers to the nodes while walking
+ /// dominator tree in dfs order.
+ void updateDFSNumbers() {
+ unsigned DFSNum = 0;
+
+ SmallVector<std::pair<DomTreeNodeBase<NodeT>*,
+ typename DomTreeNodeBase<NodeT>::iterator>, 32> WorkStack;
+
+ for (unsigned i = 0, e = (unsigned)this->Roots.size(); i != e; ++i) {
+ DomTreeNodeBase<NodeT> *ThisRoot = getNode(this->Roots[i]);
+ WorkStack.push_back(std::make_pair(ThisRoot, ThisRoot->begin()));
+ ThisRoot->DFSNumIn = DFSNum++;
+
+ while (!WorkStack.empty()) {
+ DomTreeNodeBase<NodeT> *Node = WorkStack.back().first;
+ typename DomTreeNodeBase<NodeT>::iterator ChildIt =
+ WorkStack.back().second;
+
+ // If we visited all of the children of this node, "recurse" back up the
+ // stack setting the DFOutNum.
+ if (ChildIt == Node->end()) {
+ Node->DFSNumOut = DFSNum++;
+ WorkStack.pop_back();
+ } else {
+ // Otherwise, recursively visit this child.
+ DomTreeNodeBase<NodeT> *Child = *ChildIt;
+ ++WorkStack.back().second;
+
+ WorkStack.push_back(std::make_pair(Child, Child->begin()));
+ Child->DFSNumIn = DFSNum++;
+ }
+ }
+ }
+
+ SlowQueries = 0;
+ DFSInfoValid = true;
+ }
+
+ DomTreeNodeBase<NodeT> *getNodeForBlock(NodeT *BB) {
+ if (DomTreeNodeBase<NodeT> *BBNode = this->DomTreeNodes[BB])
+ return BBNode;
+
+ // Haven't calculated this node yet? Get or calculate the node for the
+ // immediate dominator.
+ NodeT *IDom = getIDom(BB);
+
+ assert(IDom || this->DomTreeNodes[NULL]);
+ DomTreeNodeBase<NodeT> *IDomNode = getNodeForBlock(IDom);
+
+ // Add a new tree node for this BasicBlock, and link it as a child of
+ // IDomNode
+ DomTreeNodeBase<NodeT> *C = new DomTreeNodeBase<NodeT>(BB, IDomNode);
+ return this->DomTreeNodes[BB] = IDomNode->addChild(C);
+ }
+
+ inline NodeT *getIDom(NodeT *BB) const {
+ typename DenseMap<NodeT*, NodeT*>::const_iterator I = IDoms.find(BB);
+ return I != IDoms.end() ? I->second : 0;
+ }
+
+ inline void addRoot(NodeT* BB) {
+ this->Roots.push_back(BB);
+ }
+
+public:
+ /// recalculate - compute a dominator tree for the given function
+ template<class FT>
+ void recalculate(FT& F) {
+ if (!this->IsPostDominators) {
+ reset();
+
+ // Initialize roots
+ this->Roots.push_back(&F.front());
+ this->IDoms[&F.front()] = 0;
+ this->DomTreeNodes[&F.front()] = 0;
+ this->Vertex.push_back(0);
+
+ Calculate<FT, NodeT*>(*this, F);
+
+ updateDFSNumbers();
+ } else {
+ reset(); // Reset from the last time we were run...
+
+ // Initialize the roots list
+ for (typename FT::iterator I = F.begin(), E = F.end(); I != E; ++I) {
+ if (std::distance(GraphTraits<FT*>::child_begin(I),
+ GraphTraits<FT*>::child_end(I)) == 0)
+ addRoot(I);
+
+ // Prepopulate maps so that we don't get iterator invalidation issues later.
+ this->IDoms[I] = 0;
+ this->DomTreeNodes[I] = 0;
+ }
+
+ this->Vertex.push_back(0);
+
+ Calculate<FT, Inverse<NodeT*> >(*this, F);
+ }
+ }
+};
+
+EXTERN_TEMPLATE_INSTANTIATION(class DominatorTreeBase<BasicBlock>);
+
+//===-------------------------------------
+/// DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to
+/// compute a normal dominator tree.
+///
+class DominatorTree : public FunctionPass {
+public:
+ static char ID; // Pass ID, replacement for typeid
+ DominatorTreeBase<BasicBlock>* DT;
+
+ DominatorTree() : FunctionPass(&ID) {
+ DT = new DominatorTreeBase<BasicBlock>(false);
+ }
+
+ ~DominatorTree() {
+ DT->releaseMemory();
+ delete DT;
+ }
+
+ DominatorTreeBase<BasicBlock>& getBase() { return *DT; }
+
+ /// getRoots - Return the root blocks of the current CFG. This may include
+ /// multiple blocks if we are computing post dominators. For forward
+ /// dominators, this will always be a single block (the entry node).
+ ///
+ inline const std::vector<BasicBlock*> &getRoots() const {
+ return DT->getRoots();
+ }
+
+ inline BasicBlock *getRoot() const {
+ return DT->getRoot();
+ }
+
+ inline DomTreeNode *getRootNode() const {
+ return DT->getRootNode();
+ }
+
+ /// compare - Return false if the other dominator tree matches this
+ /// dominator tree. Otherwise return true.
+ inline bool compare(DominatorTree &Other) const {
+ DomTreeNode *R = getRootNode();
+ DomTreeNode *OtherR = Other.getRootNode();
+
+ if (!R || !OtherR || R->getBlock() != OtherR->getBlock())
+ return true;
+
+ if (DT->compare(Other.getBase()))
+ return true;
+
+ return false;
+ }
+
+ virtual bool runOnFunction(Function &F);
+
+ virtual void getAnalysisUsage(AnalysisUsage &AU) const {
+ AU.setPreservesAll();
+ }
+
+ inline bool dominates(DomTreeNode* A, DomTreeNode* B) const {
+ return DT->dominates(A, B);
+ }
+
+ inline bool dominates(BasicBlock* A, BasicBlock* B) const {
+ return DT->dominates(A, B);
+ }
+
+ // dominates - Return true if A dominates B. This performs the
+ // special checks necessary if A and B are in the same basic block.
+ bool dominates(Instruction *A, Instruction *B) const {
+ BasicBlock *BBA = A->getParent(), *BBB = B->getParent();
+ if (BBA != BBB) return DT->dominates(BBA, BBB);
+
+ // It is not possible to determine dominance between two PHI nodes
+ // based on their ordering.
+ if (isa<PHINode>(A) && isa<PHINode>(B))
+ return false;
+
+ // Loop through the basic block until we find A or B.
+ BasicBlock::iterator I = BBA->begin();
+ for (; &*I != A && &*I != B; ++I) /*empty*/;
+
+ //if(!DT.IsPostDominators) {
+ // A dominates B if it is found first in the basic block.
+ return &*I == A;
+ //} else {
+ // // A post-dominates B if B is found first in the basic block.
+ // return &*I == B;
+ //}
+ }
+
+ inline bool properlyDominates(const DomTreeNode* A, DomTreeNode* B) const {
+ return DT->properlyDominates(A, B);
+ }
+
+ inline bool properlyDominates(BasicBlock* A, BasicBlock* B) const {
+ return DT->properlyDominates(A, B);
+ }
+
+ /// findNearestCommonDominator - Find nearest common dominator basic block
+ /// for basic block A and B. If there is no such block then return NULL.
+ inline BasicBlock *findNearestCommonDominator(BasicBlock *A, BasicBlock *B) {
+ return DT->findNearestCommonDominator(A, B);
+ }
+
+ inline DomTreeNode *operator[](BasicBlock *BB) const {
+ return DT->getNode(BB);
+ }
+
+ /// getNode - return the (Post)DominatorTree node for the specified basic
+ /// block. This is the same as using operator[] on this class.
+ ///
+ inline DomTreeNode *getNode(BasicBlock *BB) const {
+ return DT->getNode(BB);
+ }
+
+ /// addNewBlock - Add a new node to the dominator tree information. This
+ /// creates a new node as a child of DomBB dominator node,linking it into
+ /// the children list of the immediate dominator.
+ inline DomTreeNode *addNewBlock(BasicBlock *BB, BasicBlock *DomBB) {
+ return DT->addNewBlock(BB, DomBB);
+ }
+
+ /// changeImmediateDominator - This method is used to update the dominator
+ /// tree information when a node's immediate dominator changes.
+ ///
+ inline void changeImmediateDominator(BasicBlock *N, BasicBlock* NewIDom) {
+ DT->changeImmediateDominator(N, NewIDom);
+ }
+
+ inline void changeImmediateDominator(DomTreeNode *N, DomTreeNode* NewIDom) {
+ DT->changeImmediateDominator(N, NewIDom);
+ }
+
+ /// eraseNode - Removes a node from the dominator tree. Block must not
+ /// domiante any other blocks. Removes node from its immediate dominator's
+ /// children list. Deletes dominator node associated with basic block BB.
+ inline void eraseNode(BasicBlock *BB) {
+ DT->eraseNode(BB);
+ }
+
+ /// splitBlock - BB is split and now it has one successor. Update dominator
+ /// tree to reflect this change.
+ inline void splitBlock(BasicBlock* NewBB) {
+ DT->splitBlock(NewBB);
+ }
+
+ bool isReachableFromEntry(BasicBlock* A) {
+ return DT->isReachableFromEntry(A);
+ }
+
+
+ virtual void releaseMemory() {
+ DT->releaseMemory();
+ }
+
+ virtual void print(std::ostream &OS, const Module* M= 0) const {
+ DT->print(OS, M);
+ }
+};
+
+//===-------------------------------------
+/// DominatorTree GraphTraits specialization so the DominatorTree can be
+/// iterable by generic graph iterators.
+///
+template <> struct GraphTraits<DomTreeNode *> {
+ typedef DomTreeNode NodeType;
+ typedef NodeType::iterator ChildIteratorType;
+
+ static NodeType *getEntryNode(NodeType *N) {
+ return N;
+ }
+ static inline ChildIteratorType child_begin(NodeType* N) {
+ return N->begin();
+ }
+ static inline ChildIteratorType child_end(NodeType* N) {
+ return N->end();
+ }
+};
+
+template <> struct GraphTraits<DominatorTree*>
+ : public GraphTraits<DomTreeNode *> {
+ static NodeType *getEntryNode(DominatorTree *DT) {
+ return DT->getRootNode();
+ }
+};
+
+
+//===----------------------------------------------------------------------===//
+/// DominanceFrontierBase - Common base class for computing forward and inverse
+/// dominance frontiers for a function.
+///
+class DominanceFrontierBase : public FunctionPass {
+public:
+ typedef std::set<BasicBlock*> DomSetType; // Dom set for a bb
+ typedef std::map<BasicBlock*, DomSetType> DomSetMapType; // Dom set map
+protected:
+ DomSetMapType Frontiers;
+ std::vector<BasicBlock*> Roots;
+ const bool IsPostDominators;
+
+public:
+ DominanceFrontierBase(void *ID, bool isPostDom)
+ : FunctionPass(ID), IsPostDominators(isPostDom) {}
+
+ /// getRoots - Return the root blocks of the current CFG. This may include
+ /// multiple blocks if we are computing post dominators. For forward
+ /// dominators, this will always be a single block (the entry node).
+ ///
+ inline const std::vector<BasicBlock*> &getRoots() const { return Roots; }
+
+ /// isPostDominator - Returns true if analysis based of postdoms
+ ///
+ bool isPostDominator() const { return IsPostDominators; }
+
+ virtual void releaseMemory() { Frontiers.clear(); }
+
+ // Accessor interface:
+ typedef DomSetMapType::iterator iterator;
+ typedef DomSetMapType::const_iterator const_iterator;
+ iterator begin() { return Frontiers.begin(); }
+ const_iterator begin() const { return Frontiers.begin(); }
+ iterator end() { return Frontiers.end(); }
+ const_iterator end() const { return Frontiers.end(); }
+ iterator find(BasicBlock *B) { return Frontiers.find(B); }
+ const_iterator find(BasicBlock *B) const { return Frontiers.find(B); }
+
+ void addBasicBlock(BasicBlock *BB, const DomSetType &frontier) {
+ assert(find(BB) == end() && "Block already in DominanceFrontier!");
+ Frontiers.insert(std::make_pair(BB, frontier));
+ }
+
+ /// removeBlock - Remove basic block BB's frontier.
+ void removeBlock(BasicBlock *BB) {
+ assert(find(BB) != end() && "Block is not in DominanceFrontier!");
+ for (iterator I = begin(), E = end(); I != E; ++I)
+ I->second.erase(BB);
+ Frontiers.erase(BB);
+ }
+
+ void addToFrontier(iterator I, BasicBlock *Node) {
+ assert(I != end() && "BB is not in DominanceFrontier!");
+ I->second.insert(Node);
+ }
+
+ void removeFromFrontier(iterator I, BasicBlock *Node) {
+ assert(I != end() && "BB is not in DominanceFrontier!");
+ assert(I->second.count(Node) && "Node is not in DominanceFrontier of BB");
+ I->second.erase(Node);
+ }
+
+ /// compareDomSet - Return false if two domsets match. Otherwise
+ /// return true;
+ bool compareDomSet(DomSetType &DS1, const DomSetType &DS2) const {
+ std::set<BasicBlock *> tmpSet;
+ for (DomSetType::const_iterator I = DS2.begin(),
+ E = DS2.end(); I != E; ++I)
+ tmpSet.insert(*I);
+
+ for (DomSetType::const_iterator I = DS1.begin(),
+ E = DS1.end(); I != E; ) {
+ BasicBlock *Node = *I++;
+
+ if (tmpSet.erase(Node) == 0)
+ // Node is in DS1 but not in DS2.
+ return true;
+ }
+
+ if(!tmpSet.empty())
+ // There are nodes that are in DS2 but not in DS1.
+ return true;
+
+ // DS1 and DS2 matches.
+ return false;
+ }
+
+ /// compare - Return true if the other dominance frontier base matches
+ /// this dominance frontier base. Otherwise return false.
+ bool compare(DominanceFrontierBase &Other) const {
+ DomSetMapType tmpFrontiers;
+ for (DomSetMapType::const_iterator I = Other.begin(),
+ E = Other.end(); I != E; ++I)
+ tmpFrontiers.insert(std::make_pair(I->first, I->second));
+
+ for (DomSetMapType::iterator I = tmpFrontiers.begin(),
+ E = tmpFrontiers.end(); I != E; ) {
+ BasicBlock *Node = I->first;
+ const_iterator DFI = find(Node);
+ if (DFI == end())
+ return true;
+
+ if (compareDomSet(I->second, DFI->second))
+ return true;
+
+ ++I;
+ tmpFrontiers.erase(Node);
+ }
+
+ if (!tmpFrontiers.empty())
+ return true;
+
+ return false;
+ }
+
+ /// print - Convert to human readable form
+ ///
+ virtual void print(std::ostream &OS, const Module* = 0) const;
+ void print(std::ostream *OS, const Module* M = 0) const {
+ if (OS) print(*OS, M);
+ }
+ virtual void dump();
+};
+
+
+//===-------------------------------------
+/// DominanceFrontier Class - Concrete subclass of DominanceFrontierBase that is
+/// used to compute a forward dominator frontiers.
+///
+class DominanceFrontier : public DominanceFrontierBase {
+public:
+ static char ID; // Pass ID, replacement for typeid
+ DominanceFrontier() :
+ DominanceFrontierBase(&ID, false) {}
+
+ BasicBlock *getRoot() const {
+ assert(Roots.size() == 1 && "Should always have entry node!");
+ return Roots[0];
+ }
+
+ virtual bool runOnFunction(Function &) {
+ Frontiers.clear();
+ DominatorTree &DT = getAnalysis<DominatorTree>();
+ Roots = DT.getRoots();
+ assert(Roots.size() == 1 && "Only one entry block for forward domfronts!");
+ calculate(DT, DT[Roots[0]]);
+ return false;
+ }
+
+ virtual void getAnalysisUsage(AnalysisUsage &AU) const {
+ AU.setPreservesAll();
+ AU.addRequired<DominatorTree>();
+ }
+
+ /// splitBlock - BB is split and now it has one successor. Update dominance
+ /// frontier to reflect this change.
+ void splitBlock(BasicBlock *BB);
+
+ /// BasicBlock BB's new dominator is NewBB. Update BB's dominance frontier
+ /// to reflect this change.
+ void changeImmediateDominator(BasicBlock *BB, BasicBlock *NewBB,
+ DominatorTree *DT) {
+ // NewBB is now dominating BB. Which means BB's dominance
+ // frontier is now part of NewBB's dominance frontier. However, BB
+ // itself is not member of NewBB's dominance frontier.
+ DominanceFrontier::iterator NewDFI = find(NewBB);
+ DominanceFrontier::iterator DFI = find(BB);
+ // If BB was an entry block then its frontier is empty.
+ if (DFI == end())
+ return;
+ DominanceFrontier::DomSetType BBSet = DFI->second;
+ for (DominanceFrontier::DomSetType::iterator BBSetI = BBSet.begin(),
+ BBSetE = BBSet.end(); BBSetI != BBSetE; ++BBSetI) {
+ BasicBlock *DFMember = *BBSetI;
+ // Insert only if NewBB dominates DFMember.
+ if (!DT->dominates(NewBB, DFMember))
+ NewDFI->second.insert(DFMember);
+ }
+ NewDFI->second.erase(BB);
+ }
+
+ const DomSetType &calculate(const DominatorTree &DT,
+ const DomTreeNode *Node);
+};
+
+
+} // End llvm namespace
+
+#endif
diff --git a/include/llvm/Analysis/FindUsedTypes.h b/include/llvm/Analysis/FindUsedTypes.h
new file mode 100644
index 000000000000..c897af3a58a6
--- /dev/null
+++ b/include/llvm/Analysis/FindUsedTypes.h
@@ -0,0 +1,65 @@
+//===- llvm/Analysis/FindUsedTypes.h - Find all Types in use ----*- C++ -*-===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This pass is used to seek out all of the types in use by the program.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ANALYSIS_FINDUSEDTYPES_H
+#define LLVM_ANALYSIS_FINDUSEDTYPES_H
+
+#include "llvm/Pass.h"
+#include <set>
+
+namespace llvm {
+
+class Type;
+class Value;
+
+class FindUsedTypes : public ModulePass {
+ std::set<const Type *> UsedTypes;
+public:
+ static char ID; // Pass identification, replacement for typeid
+ FindUsedTypes() : ModulePass(&ID) {}
+
+ /// getTypes - After the pass has been run, return the set containing all of
+ /// the types used in the module.
+ ///
+ const std::set<const Type *> &getTypes() const { return UsedTypes; }
+
+ /// Print the types found in the module. If the optional Module parameter is
+ /// passed in, then the types are printed symbolically if possible, using the
+ /// symbol table from the module.
+ ///
+ void print(std::ostream &o, const Module *M) const;
+ void print(std::ostream *o, const Module *M) const { if (o) print(*o, M); }
+
+private:
+ /// IncorporateType - Incorporate one type and all of its subtypes into the
+ /// collection of used types.
+ ///
+ void IncorporateType(const Type *Ty);
+
+ /// IncorporateValue - Incorporate all of the types used by this value.
+ ///
+ void IncorporateValue(const Value *V);
+
+public:
+ /// run - This incorporates all types used by the specified module
+ bool runOnModule(Module &M);
+
+ /// getAnalysisUsage - We do not modify anything.
+ virtual void getAnalysisUsage(AnalysisUsage &AU) const {
+ AU.setPreservesAll();
+ }
+};
+
+} // End llvm namespace
+
+#endif
diff --git a/include/llvm/Analysis/IVUsers.h b/include/llvm/Analysis/IVUsers.h
new file mode 100644
index 000000000000..36ff07b678e6
--- /dev/null
+++ b/include/llvm/Analysis/IVUsers.h
@@ -0,0 +1,235 @@
+//===- llvm/Analysis/IVUsers.h - Induction Variable Users -------*- C++ -*-===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file implements bookkeeping for "interesting" users of expressions
+// computed from induction variables.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ANALYSIS_IVUSERS_H
+#define LLVM_ANALYSIS_IVUSERS_H
+
+#include "llvm/Analysis/LoopPass.h"
+#include "llvm/Analysis/ScalarEvolution.h"
+#include <llvm/ADT/SmallVector.h>
+#include <map>
+
+namespace llvm {
+
+class DominatorTree;
+class Instruction;
+class Value;
+class IVUsersOfOneStride;
+
+/// IVStrideUse - Keep track of one use of a strided induction variable, where
+/// the stride is stored externally. The Offset member keeps track of the
+/// offset from the IV, User is the actual user of the operand, and
+/// 'OperandValToReplace' is the operand of the User that is the use.
+class IVStrideUse : public CallbackVH, public ilist_node<IVStrideUse> {
+public:
+ IVStrideUse(IVUsersOfOneStride *parent,
+ const SCEVHandle &offset,
+ Instruction* U, Value *O, bool issigned)
+ : CallbackVH(U), Parent(parent), Offset(offset),
+ OperandValToReplace(O), IsSigned(issigned),
+ IsUseOfPostIncrementedValue(false) {
+ }
+
+ /// getUser - Return the user instruction for this use.
+ Instruction *getUser() const {
+ return cast<Instruction>(getValPtr());
+ }
+
+ /// setUser - Assign a new user instruction for this use.
+ void setUser(Instruction *NewUser) {
+ setValPtr(NewUser);
+ }
+
+ /// getParent - Return a pointer to the IVUsersOfOneStride that owns
+ /// this IVStrideUse.
+ IVUsersOfOneStride *getParent() const { return Parent; }
+
+ /// getOffset - Return the offset to add to a theoeretical 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,
+ /// which may need to be casted to match the type of the use.
+ SCEVHandle getOffset() const { return Offset; }
+
+ /// setOffset - Assign a new offset to this use.
+ void setOffset(SCEVHandle Val) {
+ Offset = Val;
+ }
+
+ /// getOperandValToReplace - Return the Value of the operand in the user
+ /// instruction that this IVStrideUse is representing.
+ Value *getOperandValToReplace() const {
+ return OperandValToReplace;
+ }
+
+ /// setOperandValToReplace - Assign a new Value as the operand value
+ /// to replace.
+ void setOperandValToReplace(Value *Op) {
+ OperandValToReplace = Op;
+ }
+
+ /// isSigned - The stride (and thus also the Offset) of this use may be in
+ /// a narrower type than the use itself (OperandValToReplace->getType()).
+ /// When this is the case, isSigned() indicates whether the IV expression
+ /// should be signed-extended instead of zero-extended to fit the type of
+ /// the use.
+ bool isSigned() const { return IsSigned; }
+
+ /// 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;
+ }
+
+ /// setIsUseOfPostIncrmentedValue - set the flag that indicates whether
+ /// this is a post-increment use.
+ void setIsUseOfPostIncrementedValue(bool Val) {
+ IsUseOfPostIncrementedValue = Val;
+ }
+
+private:
+ /// Parent - a pointer to the IVUsersOfOneStride that owns this IVStrideUse.
+ IVUsersOfOneStride *Parent;
+
+ /// Offset - The offset to add to the base induction expression.
+ SCEVHandle Offset;
+
+ /// OperandValToReplace - The Value of the operand in the user instruction
+ /// that this IVStrideUse is representing.
+ WeakVH OperandValToReplace;
+
+ /// IsSigned - Determines whether the replacement value is sign or
+ /// zero extended to the type of the use.
+ bool IsSigned;
+
+ /// IsUseOfPostIncrementedValue - True if this should use the
+ /// post-incremented version of this IV, not the preincremented version.
+ bool IsUseOfPostIncrementedValue;
+
+ /// Deleted - Implementation of CallbackVH virtual function to
+ /// recieve notification when the User is deleted.
+ virtual void deleted();
+};
+
+template<> struct ilist_traits<IVStrideUse>
+ : public ilist_default_traits<IVStrideUse> {
+ // createSentinel is used to get hold of a node that marks the end of
+ // the list...
+ // The sentinel is relative to this instance, so we use a non-static
+ // method.
+ IVStrideUse *createSentinel() const {
+ // since i(p)lists always publicly derive from the corresponding
+ // traits, placing a data member in this class will augment i(p)list.
+ // But since the NodeTy is expected to publicly derive from
+ // ilist_node<NodeTy>, there is a legal viable downcast from it
+ // to NodeTy. We use this trick to superpose i(p)list with a "ghostly"
+ // NodeTy, which becomes the sentinel. Dereferencing the sentinel is
+ // forbidden (save the ilist_node<NodeTy>) so no one will ever notice
+ // the superposition.
+ return static_cast<IVStrideUse*>(&Sentinel);
+ }
+ static void destroySentinel(IVStrideUse*) {}
+
+ IVStrideUse *provideInitialHead() const { return createSentinel(); }
+ IVStrideUse *ensureHead(IVStrideUse*) const { return createSentinel(); }
+ static void noteHead(IVStrideUse*, IVStrideUse*) {}
+
+private:
+ mutable ilist_node<IVStrideUse> Sentinel;
+};
+
+/// IVUsersOfOneStride - This structure keeps track of all instructions that
+/// have an operand that is based on the trip count multiplied by some stride.
+struct IVUsersOfOneStride : public ilist_node<IVUsersOfOneStride> {
+private:
+ IVUsersOfOneStride(const IVUsersOfOneStride &I); // do not implement
+ void operator=(const IVUsersOfOneStride &I); // do not implement
+
+public:
+ IVUsersOfOneStride() : Stride(0) {}
+
+ explicit IVUsersOfOneStride(const SCEV *stride) : Stride(stride) {}
+
+ /// Stride - The stride for all the contained IVStrideUses. This is
+ /// a constant for affine strides.
+ const SCEV *Stride;
+
+ /// Users - Keep track of all of the users of this stride as well as the
+ /// initial value and the operand that uses the IV.
+ ilist<IVStrideUse> Users;
+
+ void addUser(const SCEVHandle &Offset,Instruction *User, Value *Operand,
+ bool isSigned) {
+ Users.push_back(new IVStrideUse(this, Offset, User, Operand, isSigned));
+ }
+};
+
+class IVUsers : public LoopPass {
+ friend class IVStrideUserVH;
+ Loop *L;
+ LoopInfo *LI;
+ DominatorTree *DT;
+ ScalarEvolution *SE;
+ SmallPtrSet<Instruction*,16> Processed;
+
+public:
+ /// IVUses - A list of all tracked IV uses of induction variable expressions
+ /// we are interested in.
+ ilist<IVUsersOfOneStride> IVUses;
+
+ /// IVUsesByStride - A mapping from the strides in StrideOrder to the
+ /// uses in IVUses.
+ std::map<SCEVHandle, IVUsersOfOneStride*> IVUsesByStride;
+
+ /// StrideOrder - An ordering of the keys in IVUsesByStride that is stable:
+ /// We use this to iterate over the IVUsesByStride collection without being
+ /// dependent on random ordering of pointers in the process.
+ SmallVector<SCEVHandle, 16> StrideOrder;
+
+private:
+ virtual void getAnalysisUsage(AnalysisUsage &AU) const;
+
+ virtual bool runOnLoop(Loop *L, LPPassManager &LPM);
+
+ virtual void releaseMemory();
+
+public:
+ static char ID; // Pass ID, replacement for typeid
+ IVUsers();
+
+ /// AddUsersIfInteresting - Inspect the specified Instruction. If it is a
+ /// reducible SCEV, recursively add its users to the IVUsesByStride set and
+ /// return true. Otherwise, return false.
+ bool AddUsersIfInteresting(Instruction *I);
+
+ /// getReplacementExpr - Return a SCEV expression which computes the
+ /// value of the OperandValToReplace of the given IVStrideUse.
+ SCEVHandle getReplacementExpr(const IVStrideUse &U) const;
+
+ void print(raw_ostream &OS, const Module* = 0) const;
+ virtual void print(std::ostream &OS, const Module* = 0) const;
+ void print(std::ostream *OS, const Module* M = 0) const {
+ if (OS) print(*OS, M);
+ }
+
+ /// dump - This method is used for debugging.
+ void dump() const;
+};
+
+Pass *createIVUsersPass();
+
+}
+
+#endif
diff --git a/include/llvm/Analysis/Interval.h b/include/llvm/Analysis/Interval.h
new file mode 100644
index 000000000000..1da2022f6961
--- /dev/null
+++ b/include/llvm/Analysis/Interval.h
@@ -0,0 +1,154 @@
+//===- llvm/Analysis/Interval.h - Interval Class Declaration ----*- C++ -*-===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file contains the declaration of the Interval class, which
+// represents a set of CFG nodes and is a portion of an interval partition.
+//
+// Intervals have some interesting and useful properties, including the
+// following:
+// 1. The header node of an interval dominates all of the elements of the
+// interval
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_INTERVAL_H
+#define LLVM_INTERVAL_H
+
+#include "llvm/ADT/GraphTraits.h"
+#include <vector>
+#include <iosfwd>
+
+namespace llvm {
+
+class BasicBlock;
+
+//===----------------------------------------------------------------------===//
+//
+/// Interval Class - An Interval is a set of nodes defined such that every node
+/// in the interval has all of its predecessors in the interval (except for the
+/// header)
+///
+class Interval {
+ /// HeaderNode - The header BasicBlock, which dominates all BasicBlocks in this
+ /// interval. Also, any loops in this interval must go through the HeaderNode.
+ ///
+ BasicBlock *HeaderNode;
+public:
+ typedef std::vector<BasicBlock*>::iterator succ_iterator;
+ typedef std::vector<BasicBlock*>::iterator pred_iterator;
+ typedef std::vector<BasicBlock*>::iterator node_iterator;
+
+ inline Interval(BasicBlock *Header) : HeaderNode(Header) {
+ Nodes.push_back(Header);
+ }
+
+ inline Interval(const Interval &I) // copy ctor
+ : HeaderNode(I.HeaderNode), Nodes(I.Nodes), Successors(I.Successors) {}
+
+ inline BasicBlock *getHeaderNode() const { return HeaderNode; }
+
+ /// Nodes - The basic blocks in this interval.
+ ///
+ std::vector<BasicBlock*> Nodes;
+
+ /// Successors - List of BasicBlocks that are reachable directly from nodes in
+ /// this interval, but are not in the interval themselves.
+ /// These nodes necessarily must be header nodes for other intervals.
+ ///
+ std::vector<BasicBlock*> Successors;
+
+ /// Predecessors - List of BasicBlocks that have this Interval's header block
+ /// as one of their successors.
+ ///
+ std::vector<BasicBlock*> Predecessors;
+
+ /// contains - Find out if a basic block is in this interval
+ inline bool contains(BasicBlock *BB) const {
+ for (unsigned i = 0; i < Nodes.size(); ++i)
+ if (Nodes[i] == BB) return true;
+ return false;
+ // I don't want the dependency on <algorithm>
+ //return find(Nodes.begin(), Nodes.end(), BB) != Nodes.end();
+ }
+
+ /// isSuccessor - find out if a basic block is a successor of this Interval
+ inline bool isSuccessor(BasicBlock *BB) const {
+ for (unsigned i = 0; i < Successors.size(); ++i)
+ if (Successors[i] == BB) return true;
+ return false;
+ // I don't want the dependency on <algorithm>
+ //return find(Successors.begin(), Successors.end(), BB) != Successors.end();
+ }
+
+ /// Equality operator. It is only valid to compare two intervals from the
+ /// same partition, because of this, all we have to check is the header node
+ /// for equality.
+ ///
+ inline bool operator==(const Interval &I) const {
+ return HeaderNode == I.HeaderNode;
+ }
+
+ /// isLoop - Find out if there is a back edge in this interval...
+ bool isLoop() const;
+
+ /// print - Show contents in human readable format...
+ void print(std::ostream &O) const;
+ void print(std::ostream *O) const { if (O) print(*O); }
+};
+
+/// succ_begin/succ_end - define methods so that Intervals may be used
+/// just like BasicBlocks can with the succ_* functions, and *::succ_iterator.
+///
+inline Interval::succ_iterator succ_begin(Interval *I) {
+ return I->Successors.begin();
+}
+inline Interval::succ_iterator succ_end(Interval *I) {
+ return I->Successors.end();
+}
+
+/// pred_begin/pred_end - define methods so that Intervals may be used
+/// just like BasicBlocks can with the pred_* functions, and *::pred_iterator.
+///
+inline Interval::pred_iterator pred_begin(Interval *I) {
+ return I->Predecessors.begin();
+}
+inline Interval::pred_iterator pred_end(Interval *I) {
+ return I->Predecessors.end();
+}
+
+template <> struct GraphTraits<Interval*> {
+ typedef Interval NodeType;
+ typedef Interval::succ_iterator ChildIteratorType;
+
+ static NodeType *getEntryNode(Interval *I) { return I; }
+
+ /// nodes_iterator/begin/end - Allow iteration over all nodes in the graph
+ static inline ChildIteratorType child_begin(NodeType *N) {
+ return succ_begin(N);
+ }
+ static inline ChildIteratorType child_end(NodeType *N) {
+ return succ_end(N);
+ }
+};
+
+template <> struct GraphTraits<Inverse<Interval*> > {
+ typedef Interval NodeType;
+ typedef Interval::pred_iterator ChildIteratorType;
+ static NodeType *getEntryNode(Inverse<Interval *> G) { return G.Graph; }
+ static inline ChildIteratorType child_begin(NodeType *N) {
+ return pred_begin(N);
+ }
+ static inline ChildIteratorType child_end(NodeType *N) {
+ return pred_end(N);
+ }
+};
+
+} // End llvm namespace
+
+#endif
diff --git a/include/llvm/Analysis/IntervalIterator.h b/include/llvm/Analysis/IntervalIterator.h
new file mode 100644
index 000000000000..551bb7243798
--- /dev/null
+++ b/include/llvm/Analysis/IntervalIterator.h
@@ -0,0 +1,258 @@
+//===- IntervalIterator.h - Interval Iterator Declaration -------*- 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 an iterator that enumerates the intervals in a control flow
+// graph of some sort. This iterator is parametric, allowing iterator over the
+// following types of graphs:
+//
+// 1. A Function* object, composed of BasicBlock nodes.
+// 2. An IntervalPartition& object, composed of Interval nodes.
+//
+// This iterator is defined to walk the control flow graph, returning intervals
+// in depth first order. These intervals are completely filled in except for
+// the predecessor fields (the successor information is filled in however).
+//
+// By default, the intervals created by this iterator are deleted after they
+// are no longer any use to the iterator. This behavior can be changed by
+// passing a false value into the intervals_begin() function. This causes the
+// IOwnMem member to be set, and the intervals to not be deleted.
+//
+// It is only safe to use this if all of the intervals are deleted by the caller
+// and all of the intervals are processed. However, the user of the iterator is
+// not allowed to modify or delete the intervals until after the iterator has
+// been used completely. The IntervalPartition class uses this functionality.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_INTERVAL_ITERATOR_H
+#define LLVM_INTERVAL_ITERATOR_H
+
+#include "llvm/Analysis/IntervalPartition.h"
+#include "llvm/Function.h"
+#include "llvm/Support/CFG.h"
+#include <stack>
+#include <set>
+#include <algorithm>
+
+namespace llvm {
+
+// getNodeHeader - Given a source graph node and the source graph, return the
+// BasicBlock that is the header node. This is the opposite of
+// getSourceGraphNode.
+//
+inline BasicBlock *getNodeHeader(BasicBlock *BB) { return BB; }
+inline BasicBlock *getNodeHeader(Interval *I) { return I->getHeaderNode(); }
+
+// getSourceGraphNode - Given a BasicBlock and the source graph, return the
+// source graph node that corresponds to the BasicBlock. This is the opposite
+// of getNodeHeader.
+//
+inline BasicBlock *getSourceGraphNode(Function *, BasicBlock *BB) {
+ return BB;
+}
+inline Interval *getSourceGraphNode(IntervalPartition *IP, BasicBlock *BB) {
+ return IP->getBlockInterval(BB);
+}
+
+// addNodeToInterval - This method exists to assist the generic ProcessNode
+// with the task of adding a node to the new interval, depending on the
+// type of the source node. In the case of a CFG source graph (BasicBlock
+// case), the BasicBlock itself is added to the interval.
+//
+inline void addNodeToInterval(Interval *Int, BasicBlock *BB) {
+ Int->Nodes.push_back(BB);
+}
+
+// addNodeToInterval - This method exists to assist the generic ProcessNode
+// with the task of adding a node to the new interval, depending on the
+// type of the source node. In the case of a CFG source graph (BasicBlock
+// case), the BasicBlock itself is added to the interval. In the case of
+// an IntervalPartition source graph (Interval case), all of the member
+// BasicBlocks are added to the interval.
+//
+inline void addNodeToInterval(Interval *Int, Interval *I) {
+ // Add all of the nodes in I as new nodes in Int.
+ copy(I->Nodes.begin(), I->Nodes.end(), back_inserter(Int->Nodes));
+}
+
+
+
+
+
+template<class NodeTy, class OrigContainer_t, class GT = GraphTraits<NodeTy*>,
+ class IGT = GraphTraits<Inverse<NodeTy*> > >
+class IntervalIterator {
+ std::stack<std::pair<Interval*, typename Interval::succ_iterator> > IntStack;
+ std::set<BasicBlock*> Visited;
+ OrigContainer_t *OrigContainer;
+ bool IOwnMem; // If True, delete intervals when done with them
+ // See file header for conditions of use
+public:
+ typedef IntervalIterator<NodeTy, OrigContainer_t> _Self;
+ typedef std::forward_iterator_tag iterator_category;
+
+ IntervalIterator() {} // End iterator, empty stack
+ IntervalIterator(Function *M, bool OwnMemory) : IOwnMem(OwnMemory) {
+ OrigContainer = M;
+ if (!ProcessInterval(&M->front())) {
+ assert(0 && "ProcessInterval should never fail for first interval!");
+ }
+ }
+
+ IntervalIterator(IntervalPartition &IP, bool OwnMemory) : IOwnMem(OwnMemory) {
+ OrigContainer = &IP;
+ if (!ProcessInterval(IP.getRootInterval())) {
+ assert(0 && "ProcessInterval should never fail for first interval!");
+ }
+ }
+
+ inline ~IntervalIterator() {
+ if (IOwnMem)
+ while (!IntStack.empty()) {
+ delete operator*();
+ IntStack.pop();
+ }
+ }
+
+ inline bool operator==(const _Self& x) const { return IntStack == x.IntStack;}
+ inline bool operator!=(const _Self& x) const { return !operator==(x); }
+
+ inline const Interval *operator*() const { return IntStack.top().first; }
+ inline Interval *operator*() { return IntStack.top().first; }
+ inline const Interval *operator->() const { return operator*(); }
+ inline Interval *operator->() { return operator*(); }
+
+ _Self& operator++() { // Preincrement
+ assert(!IntStack.empty() && "Attempting to use interval iterator at end!");
+ do {
+ // All of the intervals on the stack have been visited. Try visiting
+ // their successors now.
+ Interval::succ_iterator &SuccIt = IntStack.top().second,
+ EndIt = succ_end(IntStack.top().first);
+ while (SuccIt != EndIt) { // Loop over all interval succs
+ bool Done = ProcessInterval(getSourceGraphNode(OrigContainer, *SuccIt));
+ ++SuccIt; // Increment iterator
+ if (Done) return *this; // Found a new interval! Use it!
+ }
+
+ // Free interval memory... if necessary
+ if (IOwnMem) delete IntStack.top().first;
+
+ // We ran out of successors for this interval... pop off the stack
+ IntStack.pop();
+ } while (!IntStack.empty());
+
+ return *this;
+ }
+ inline _Self operator++(int) { // Postincrement
+ _Self tmp = *this; ++*this; return tmp;
+ }
+
+private:
+ // ProcessInterval - This method is used during the construction of the
+ // interval graph. It walks through the source graph, recursively creating
+ // an interval per invokation until the entire graph is covered. This uses
+ // the ProcessNode method to add all of the nodes to the interval.
+ //
+ // This method is templated because it may operate on two different source
+ // graphs: a basic block graph, or a preexisting interval graph.
+ //
+ bool ProcessInterval(NodeTy *Node) {
+ BasicBlock *Header = getNodeHeader(Node);
+ if (Visited.count(Header)) return false;
+
+ Interval *Int = new Interval(Header);
+ Visited.insert(Header); // The header has now been visited!
+
+ // Check all of our successors to see if they are in the interval...
+ for (typename GT::ChildIteratorType I = GT::child_begin(Node),
+ E = GT::child_end(Node); I != E; ++I)
+ ProcessNode(Int, getSourceGraphNode(OrigContainer, *I));
+
+ IntStack.push(std::make_pair(Int, succ_begin(Int)));
+ return true;
+ }
+
+ // ProcessNode - This method is called by ProcessInterval to add nodes to the
+ // interval being constructed, and it is also called recursively as it walks
+ // the source graph. A node is added to the current interval only if all of
+ // its predecessors are already in the graph. This also takes care of keeping
+ // the successor set of an interval up to date.
+ //
+ // This method is templated because it may operate on two different source
+ // graphs: a basic block graph, or a preexisting interval graph.
+ //
+ void ProcessNode(Interval *Int, NodeTy *Node) {
+ assert(Int && "Null interval == bad!");
+ assert(Node && "Null Node == bad!");
+
+ BasicBlock *NodeHeader = getNodeHeader(Node);
+
+ if (Visited.count(NodeHeader)) { // Node already been visited?
+ if (Int->contains(NodeHeader)) { // Already in this interval...
+ return;
+ } else { // In other interval, add as successor
+ if (!Int->isSuccessor(NodeHeader)) // Add only if not already in set
+ Int->Successors.push_back(NodeHeader);
+ }
+ } else { // Otherwise, not in interval yet
+ for (typename IGT::ChildIteratorType I = IGT::child_begin(Node),
+ E = IGT::child_end(Node); I != E; ++I) {
+ if (!Int->contains(*I)) { // If pred not in interval, we can't be
+ if (!Int->isSuccessor(NodeHeader)) // Add only if not already in set
+ Int->Successors.push_back(NodeHeader);
+ return; // See you later
+ }
+ }
+
+ // If we get here, then all of the predecessors of BB are in the interval
+ // already. In this case, we must add BB to the interval!
+ addNodeToInterval(Int, Node);
+ Visited.insert(NodeHeader); // The node has now been visited!
+
+ if (Int->isSuccessor(NodeHeader)) {
+ // If we were in the successor list from before... remove from succ list
+ Int->Successors.erase(std::remove(Int->Successors.begin(),
+ Int->Successors.end(), NodeHeader),
+ Int->Successors.end());
+ }
+
+ // Now that we have discovered that Node is in the interval, perhaps some
+ // of its successors are as well?
+ for (typename GT::ChildIteratorType It = GT::child_begin(Node),
+ End = GT::child_end(Node); It != End; ++It)
+ ProcessNode(Int, getSourceGraphNode(OrigContainer, *It));
+ }
+ }
+};
+
+typedef IntervalIterator<BasicBlock, Function> function_interval_iterator;
+typedef IntervalIterator<Interval, IntervalPartition> interval_part_interval_iterator;
+
+
+inline function_interval_iterator intervals_begin(Function *F,
+ bool DeleteInts = true) {
+ return function_interval_iterator(F, DeleteInts);
+}
+inline function_interval_iterator intervals_end(Function *) {
+ return function_interval_iterator();
+}
+
+inline interval_part_interval_iterator
+ intervals_begin(IntervalPartition &IP, bool DeleteIntervals = true) {
+ return interval_part_interval_iterator(IP, DeleteIntervals);
+}
+
+inline interval_part_interval_iterator intervals_end(IntervalPartition &IP) {
+ return interval_part_interval_iterator();
+}
+
+} // End llvm namespace
+
+#endif
diff --git a/include/llvm/Analysis/IntervalPartition.h b/include/llvm/Analysis/IntervalPartition.h
new file mode 100644
index 000000000000..feae6d82f82f
--- /dev/null
+++ b/include/llvm/Analysis/IntervalPartition.h
@@ -0,0 +1,112 @@
+//===- IntervalPartition.h - Interval partition Calculation -----*- C++ -*-===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file contains the declaration of the IntervalPartition class, which
+// calculates and represents the interval partition of a function, or a
+// preexisting interval partition.
+//
+// In this way, the interval partition may be used to reduce a flow graph down
+// to its degenerate single node interval partition (unless it is irreducible).
+//
+// TODO: The IntervalPartition class should take a bool parameter that tells
+// whether it should add the "tails" of an interval to an interval itself or if
+// they should be represented as distinct intervals.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_INTERVAL_PARTITION_H
+#define LLVM_INTERVAL_PARTITION_H
+
+#include "llvm/Analysis/Interval.h"
+#include "llvm/Pass.h"
+#include <map>
+
+namespace llvm {
+
+//===----------------------------------------------------------------------===//
+//
+// IntervalPartition - This class builds and holds an "interval partition" for
+// a function. This partition divides the control flow graph into a set of
+// maximal intervals, as defined with the properties above. Intuitively, a
+// BasicBlock is a (possibly nonexistent) loop with a "tail" of non looping
+// nodes following it.
+//
+class IntervalPartition : public FunctionPass {
+ typedef std::map<BasicBlock*, Interval*> IntervalMapTy;
+ IntervalMapTy IntervalMap;
+
+ typedef std::vector<Interval*> IntervalListTy;
+ Interval *RootInterval;
+ std::vector<Interval*> Intervals;
+
+public:
+ static char ID; // Pass identification, replacement for typeid
+
+ IntervalPartition() : FunctionPass(&ID), RootInterval(0) {}
+
+ // run - Calculate the interval partition for this function
+ virtual bool runOnFunction(Function &F);
+
+ // IntervalPartition ctor - Build a reduced interval partition from an
+ // existing interval graph. This takes an additional boolean parameter to
+ // distinguish it from a copy constructor. Always pass in false for now.
+ //
+ IntervalPartition(IntervalPartition &I, bool);
+
+ // print - Show contents in human readable format...
+ virtual void print(std::ostream &O, const Module* = 0) const;
+ void print(std::ostream *O, const Module* M = 0) const {
+ if (O) print(*O, M);
+ }
+
+ // getRootInterval() - Return the root interval that contains the starting
+ // block of the function.
+ inline Interval *getRootInterval() { return RootInterval; }
+
+ // isDegeneratePartition() - Returns true if the interval partition contains
+ // a single interval, and thus cannot be simplified anymore.
+ bool isDegeneratePartition() { return Intervals.size() == 1; }
+
+ // TODO: isIrreducible - look for triangle graph.
+
+ // getBlockInterval - Return the interval that a basic block exists in.
+ inline Interval *getBlockInterval(BasicBlock *BB) {
+ IntervalMapTy::iterator I = IntervalMap.find(BB);
+ return I != IntervalMap.end() ? I->second : 0;
+ }
+
+ // getAnalysisUsage - Implement the Pass API
+ virtual void getAnalysisUsage(AnalysisUsage &AU) const {
+ AU.setPreservesAll();
+ }
+
+ // Interface to Intervals vector...
+ const std::vector<Interval*> &getIntervals() const { return Intervals; }
+
+ // releaseMemory - Reset state back to before function was analyzed
+ void releaseMemory();
+
+private:
+ // addIntervalToPartition - Add an interval to the internal list of intervals,
+ // and then add mappings from all of the basic blocks in the interval to the
+ // interval itself (in the IntervalMap).
+ //
+ void addIntervalToPartition(Interval *I);
+
+ // updatePredecessors - Interval generation only sets the successor fields of
+ // the interval data structures. After interval generation is complete,
+ // run through all of the intervals and propagate successor info as
+ // predecessor info.
+ //
+ void updatePredecessors(Interval *Int);
+};
+
+} // End llvm namespace
+
+#endif
diff --git a/include/llvm/Analysis/LibCallAliasAnalysis.h b/include/llvm/Analysis/LibCallAliasAnalysis.h
new file mode 100644
index 000000000000..ea17a237caaa
--- /dev/null
+++ b/include/llvm/Analysis/LibCallAliasAnalysis.h
@@ -0,0 +1,61 @@
+//===- LibCallAliasAnalysis.h - Implement AliasAnalysis for libcalls ------===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file defines the LibCallAliasAnalysis class.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ANALYSIS_LIBCALL_AA_H
+#define LLVM_ANALYSIS_LIBCALL_AA_H
+
+#include "llvm/Analysis/AliasAnalysis.h"
+#include "llvm/Pass.h"
+
+namespace llvm {
+ class LibCallInfo;
+ struct LibCallFunctionInfo;
+
+ /// LibCallAliasAnalysis - Alias analysis driven from LibCallInfo.
+ struct LibCallAliasAnalysis : public FunctionPass, AliasAnalysis {
+ static char ID; // Class identification
+
+ LibCallInfo *LCI;
+
+ explicit LibCallAliasAnalysis(LibCallInfo *LC = 0)
+ : FunctionPass(&ID), LCI(LC) {
+ }
+ explicit LibCallAliasAnalysis(const void *ID, LibCallInfo *LC)
+ : FunctionPass(ID), LCI(LC) {
+ }
+ ~LibCallAliasAnalysis();
+
+ ModRefResult getModRefInfo(CallSite CS, Value *P, unsigned Size);
+
+ ModRefResult getModRefInfo(CallSite CS1, CallSite CS2) {
+ // TODO: Could compare two direct calls against each other if we cared to.
+ return AliasAnalysis::getModRefInfo(CS1,CS2);
+ }
+
+ virtual void getAnalysisUsage(AnalysisUsage &AU) const;
+
+ virtual bool runOnFunction(Function &F) {
+ InitializeAliasAnalysis(this); // set up super class
+ return false;
+ }
+
+ /// hasNoModRefInfoForCalls - We can provide mod/ref information against
+ /// non-escaping allocations.
+ virtual bool hasNoModRefInfoForCalls() const { return false; }
+ private:
+ ModRefResult AnalyzeLibCallDetails(const LibCallFunctionInfo *FI,
+ CallSite CS, Value *P, unsigned Size);
+ };
+} // End of llvm namespace
+
+#endif
diff --git a/include/llvm/Analysis/LibCallSemantics.h b/include/llvm/Analysis/LibCallSemantics.h
new file mode 100644
index 000000000000..74e8401a1fe6
--- /dev/null
+++ b/include/llvm/Analysis/LibCallSemantics.h
@@ -0,0 +1,166 @@
+//===- LibCallSemantics.h - Describe library semantics --------------------===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file defines interfaces that can be used to describe language specific
+// runtime library interfaces (e.g. libc, libm, etc) to LLVM optimizers.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ANALYSIS_LIBCALLSEMANTICS_H
+#define LLVM_ANALYSIS_LIBCALLSEMANTICS_H
+
+#include "llvm/Analysis/AliasAnalysis.h"
+
+namespace llvm {
+
+ /// LibCallLocationInfo - This struct describes a set of memory locations that
+ /// are accessed by libcalls. Identification of a location is doing with a
+ /// simple callback function.
+ ///
+ /// For example, the LibCallInfo may be set up to model the behavior of
+ /// standard libm functions. The location that they may be interested in is
+ /// an abstract location that represents errno for the current target. In
+ /// this case, a location for errno is anything such that the predicate
+ /// returns true. On Mac OS/X, this predicate would return true if the
+ /// pointer is the result of a call to "__error()".
+ ///
+ /// Locations can also be defined in a constant-sensitive way. For example,
+ /// it is possible to define a location that returns true iff it is passed
+ /// into the call as a specific argument. This is useful for modeling things
+ /// like "printf", which can store to memory, but only through pointers passed
+ /// with a '%n' constraint.
+ ///
+ struct LibCallLocationInfo {
+ // TODO: Flags: isContextSensitive etc.
+
+ /// isLocation - Return a LocResult if the specified pointer refers to this
+ /// location for the specified call site. This returns "Yes" if we can tell
+ /// that the pointer *does definitely* refer to the location, "No" if we can
+ /// tell that the location *definitely does not* refer to the location, and
+ /// returns "Unknown" if we cannot tell for certain.
+ enum LocResult {
+ Yes, No, Unknown
+ };
+ LocResult (*isLocation)(CallSite CS, const Value *Ptr, unsigned Size);
+ };
+
+ /// LibCallFunctionInfo - Each record in the array of FunctionInfo structs
+ /// records the behavior of one libcall that is known by the optimizer. This
+ /// captures things like the side effects of the call. Side effects are
+ /// modeled both universally (in the readnone/readonly) sense, but also
+ /// potentially against a set of abstract locations defined by the optimizer.
+ /// This allows an optimizer to define that some libcall (e.g. sqrt) is
+ /// side-effect free except that it might modify errno (thus, the call is
+ /// *not* universally readonly). Or it might say that the side effects
+ /// are unknown other than to say that errno is not modified.
+ ///
+ struct LibCallFunctionInfo {
+ /// Name - This is the name of the libcall this describes.
+ const char *Name;
+
+ /// TODO: Constant folding function: Constant* vector -> Constant*.
+
+ /// UniversalBehavior - This captures the absolute mod/ref behavior without
+ /// any specific context knowledge. For example, if the function is known
+ /// to be readonly, this would be set to 'ref'. If known to be readnone,
+ /// this is set to NoModRef.
+ AliasAnalysis::ModRefResult UniversalBehavior;
+
+ /// LocationMRInfo - This pair captures info about whether a specific
+ /// location is modified or referenced by a libcall.
+ struct LocationMRInfo {
+ /// LocationID - ID # of the accessed location or ~0U for array end.
+ unsigned LocationID;
+ /// MRInfo - Mod/Ref info for this location.
+ AliasAnalysis::ModRefResult MRInfo;
+ };
+
+ /// DetailsType - Indicate the sense of the LocationDetails array. This
+ /// controls how the LocationDetails array is interpreted.
+ enum {
+ /// DoesOnly - If DetailsType is set to DoesOnly, then we know that the
+ /// *only* mod/ref behavior of this function is captured by the
+ /// LocationDetails array. If we are trying to say that 'sqrt' can only
+ /// modify errno, we'd have the {errnoloc,mod} in the LocationDetails
+ /// array and have DetailsType set to DoesOnly.
+ DoesOnly,
+
+ /// DoesNot - If DetailsType is set to DoesNot, then the sense of the
+ /// LocationDetails array is completely inverted. This means that we *do
+ /// not* know everything about the side effects of this libcall, but we do
+ /// know things that the libcall cannot do. This is useful for complex
+ /// functions like 'ctime' which have crazy mod/ref behavior, but are
+ /// known to never read or write errno. In this case, we'd have
+ /// {errnoloc,modref} in the LocationDetails array and DetailsType would
+ /// be set to DoesNot, indicating that ctime does not read or write the
+ /// errno location.
+ DoesNot
+ } DetailsType;
+
+ /// LocationDetails - This is a pointer to an array of LocationMRInfo
+ /// structs which indicates the behavior of the libcall w.r.t. specific
+ /// locations. For example, if this libcall is known to only modify
+ /// 'errno', it would have a LocationDetails array with the errno ID and
+ /// 'mod' in it. See the DetailsType field for how this is interpreted.
+ ///
+ /// In the "DoesOnly" case, this information is 'may' information for: there
+ /// is no guarantee that the specified side effect actually does happen,
+ /// just that it could. In the "DoesNot" case, this is 'must not' info.
+ ///
+ /// If this pointer is null, no details are known.
+ ///
+ const LocationMRInfo *LocationDetails;
+ };
+
+
+ /// LibCallInfo - Abstract interface to query about library call information.
+ /// Instances of this class return known information about some set of
+ /// libcalls.
+ ///
+ class LibCallInfo {
+ // Implementation details of this object, private.
+ mutable void *Impl;
+ mutable const LibCallLocationInfo *Locations;
+ mutable unsigned NumLocations;
+ public:
+ LibCallInfo() : Impl(0), Locations(0), NumLocations(0) {}
+ virtual ~LibCallInfo();
+
+ //===------------------------------------------------------------------===//
+ // Accessor Methods: Efficient access to contained data.
+ //===------------------------------------------------------------------===//
+
+ /// getLocationInfo - Return information about the specified LocationID.
+ const LibCallLocationInfo &getLocationInfo(unsigned LocID) const;
+
+
+ /// getFunctionInfo - Return the LibCallFunctionInfo object corresponding to
+ /// the specified function if we have it. If not, return null.
+ const LibCallFunctionInfo *getFunctionInfo(Function *F) const;
+
+
+ //===------------------------------------------------------------------===//
+ // Implementation Methods: Subclasses should implement these.
+ //===------------------------------------------------------------------===//
+
+ /// getLocationInfo - Return descriptors for the locations referenced by
+ /// this set of libcalls.
+ virtual unsigned getLocationInfo(const LibCallLocationInfo *&Array) const {
+ return 0;
+ }
+
+ /// getFunctionInfoArray - Return an array of descriptors that describe the
+ /// set of libcalls represented by this LibCallInfo object. This array is
+ /// terminated by an entry with a NULL name.
+ virtual const LibCallFunctionInfo *getFunctionInfoArray() const = 0;
+ };
+
+} // end namespace llvm
+
+#endif
diff --git a/include/llvm/Analysis/LiveValues.h b/include/llvm/Analysis/LiveValues.h
new file mode 100644
index 000000000000..31b00d73dd2c
--- /dev/null
+++ b/include/llvm/Analysis/LiveValues.h
@@ -0,0 +1,103 @@
+//===- LiveValues.h - Liveness information for LLVM IR Values. ------------===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file defines the interface for the LLVM IR Value liveness
+// analysis pass.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ANALYSIS_LIVEVALUES_H
+#define LLVM_ANALYSIS_LIVEVALUES_H
+
+#include "llvm/Pass.h"
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/SmallPtrSet.h"
+
+namespace llvm {
+
+class DominatorTree;
+class LoopInfo;
+class Value;
+
+/// LiveValues - Analysis that provides liveness information for
+/// LLVM IR Values.
+///
+class LiveValues : public FunctionPass {
+ DominatorTree *DT;
+ LoopInfo *LI;
+
+ /// Memo - A bunch of state to be associated with a value.
+ ///
+ struct Memo {
+ /// Used - The set of blocks which contain a use of the value.
+ ///
+ SmallPtrSet<const BasicBlock *, 4> Used;
+
+ /// LiveThrough - A conservative approximation of the set of blocks in
+ /// which the value is live-through, meaning blocks properly dominated
+ /// by the definition, and from which blocks containing uses of the
+ /// value are reachable.
+ ///
+ SmallPtrSet<const BasicBlock *, 4> LiveThrough;
+
+ /// Killed - A conservative approximation of the set of blocks in which
+ /// the value is used and not live-out.
+ ///
+ SmallPtrSet<const BasicBlock *, 4> Killed;
+ };
+
+ /// Memos - Remembers the Memo for each Value. This is populated on
+ /// demand.
+ ///
+ DenseMap<const Value *, Memo> Memos;
+
+ /// getMemo - Retrieve an existing Memo for the given value if one
+ /// is available, otherwise compute a new one.
+ ///
+ Memo &getMemo(const Value *V);
+
+ /// compute - Compute a new Memo for the given value.
+ ///
+ Memo &compute(const Value *V);
+
+public:
+ static char ID;
+ LiveValues();
+
+ virtual void getAnalysisUsage(AnalysisUsage &AU) const;
+ virtual bool runOnFunction(Function &F);
+ virtual void releaseMemory();
+
+ /// isUsedInBlock - Test if the given value is used in the given block.
+ ///
+ bool isUsedInBlock(const Value *V, const BasicBlock *BB);
+
+ /// isLiveThroughBlock - Test if the given value is known to be
+ /// live-through the given block, meaning that the block is properly
+ /// dominated by the value's definition, and there exists a block
+ /// reachable from it that contains a use. This uses a conservative
+ /// approximation that errs on the side of returning false.
+ ///
+ bool isLiveThroughBlock(const Value *V, const BasicBlock *BB);
+
+ /// isKilledInBlock - Test if the given value is known to be killed in
+ /// the given block, meaning that the block contains a use of the value,
+ /// and no blocks reachable from the block contain a use. This uses a
+ /// conservative approximation that errs on the side of returning false.
+ ///
+ bool isKilledInBlock(const Value *V, const BasicBlock *BB);
+};
+
+/// createLiveValuesPass - This creates an instance of the LiveValues pass.
+///
+FunctionPass *createLiveValuesPass();
+
+}
+
+#endif
diff --git a/include/llvm/Analysis/LoopInfo.h b/include/llvm/Analysis/LoopInfo.h
new file mode 100644
index 000000000000..fb0b584d41cd
--- /dev/null
+++ b/include/llvm/Analysis/LoopInfo.h
@@ -0,0 +1,1095 @@
+//===- llvm/Analysis/LoopInfo.h - Natural Loop Calculator -------*- 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 the LoopInfo class that is used to identify natural loops
+// and determine the loop depth of various nodes of the CFG. Note that natural
+// loops may actually be several loops that share the same header node.
+//
+// This analysis calculates the nesting structure of loops in a function. For
+// each natural loop identified, this analysis identifies natural loops
+// contained entirely within the loop and the basic blocks the make up the loop.
+//
+// It can calculate on the fly various bits of information, for example:
+//
+// * whether there is a preheader for the loop
+// * the number of back edges to the header
+// * whether or not a particular block branches out of the loop
+// * the successor blocks of the loop
+// * the loop depth
+// * the trip count
+// * etc...
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ANALYSIS_LOOP_INFO_H
+#define LLVM_ANALYSIS_LOOP_INFO_H
+
+#include "llvm/Pass.h"
+#include "llvm/Constants.h"
+#include "llvm/Instructions.h"
+#include "llvm/ADT/DepthFirstIterator.h"
+#include "llvm/ADT/GraphTraits.h"
+#include "llvm/ADT/SmallPtrSet.h"
+#include "llvm/ADT/SmallVector.h"
+#include "llvm/Analysis/Dominators.h"
+#include "llvm/Support/CFG.h"
+#include "llvm/Support/Streams.h"
+#include <algorithm>
+#include <ostream>
+
+namespace llvm {
+
+template<typename T>
+static void RemoveFromVector(std::vector<T*> &V, T *N) {
+ typename std::vector<T*>::iterator I = std::find(V.begin(), V.end(), N);
+ assert(I != V.end() && "N is not in this list!");
+ V.erase(I);
+}
+
+class DominatorTree;
+class LoopInfo;
+template<class N> class LoopInfoBase;
+template<class N> class LoopBase;
+
+typedef LoopBase<BasicBlock> Loop;
+
+//===----------------------------------------------------------------------===//
+/// LoopBase class - Instances of this class are used to represent loops that
+/// are detected in the flow graph
+///
+template<class BlockT>
+class LoopBase {
+ LoopBase<BlockT> *ParentLoop;
+ // SubLoops - Loops contained entirely within this one.
+ std::vector<LoopBase<BlockT>*> SubLoops;
+
+ // Blocks - The list of blocks in this loop. First entry is the header node.
+ std::vector<BlockT*> Blocks;
+
+ LoopBase(const LoopBase<BlockT> &); // DO NOT IMPLEMENT
+ const LoopBase<BlockT>&operator=(const LoopBase<BlockT> &);// DO NOT IMPLEMENT
+public:
+ /// Loop ctor - This creates an empty loop.
+ LoopBase() : ParentLoop(0) {}
+ ~LoopBase() {
+ for (size_t i = 0, e = SubLoops.size(); i != e; ++i)
+ delete SubLoops[i];
+ }
+
+ /// getLoopDepth - Return the nesting level of this loop. An outer-most
+ /// loop has depth 1, for consistency with loop depth values used for basic
+ /// blocks, where depth 0 is used for blocks not inside any loops.
+ unsigned getLoopDepth() const {
+ unsigned D = 1;
+ for (const LoopBase<BlockT> *CurLoop = ParentLoop; CurLoop;
+ CurLoop = CurLoop->ParentLoop)
+ ++D;
+ return D;
+ }
+ BlockT *getHeader() const { return Blocks.front(); }
+ LoopBase<BlockT> *getParentLoop() const { return ParentLoop; }
+
+ /// contains - Return true if the specified basic block is in this loop
+ ///
+ bool contains(const BlockT *BB) const {
+ return std::find(block_begin(), block_end(), BB) != block_end();
+ }
+
+ /// iterator/begin/end - Return the loops contained entirely within this loop.
+ ///
+ const std::vector<LoopBase<BlockT>*> &getSubLoops() const { return SubLoops; }
+ typedef typename std::vector<LoopBase<BlockT>*>::const_iterator iterator;
+ iterator begin() const { return SubLoops.begin(); }
+ iterator end() const { return SubLoops.end(); }
+ bool empty() const { return SubLoops.empty(); }
+
+ /// getBlocks - Get a list of the basic blocks which make up this loop.
+ ///
+ const std::vector<BlockT*> &getBlocks() const { return Blocks; }
+ typedef typename std::vector<BlockT*>::const_iterator block_iterator;
+ block_iterator block_begin() const { return Blocks.begin(); }
+ block_iterator block_end() const { return Blocks.end(); }
+
+ /// isLoopExit - True if terminator in the block can branch to another block
+ /// that is outside of the current loop.
+ ///
+ bool isLoopExit(const BlockT *BB) const {
+ typedef GraphTraits<BlockT*> BlockTraits;
+ for (typename BlockTraits::ChildIteratorType SI =
+ BlockTraits::child_begin(const_cast<BlockT*>(BB)),
+ SE = BlockTraits::child_end(const_cast<BlockT*>(BB)); SI != SE; ++SI) {
+ if (!contains(*SI))
+ return true;
+ }
+ return false;
+ }
+
+ /// getNumBackEdges - Calculate the number of back edges to the loop header
+ ///
+ unsigned getNumBackEdges() const {
+ unsigned NumBackEdges = 0;
+ BlockT *H = getHeader();
+
+ typedef GraphTraits<Inverse<BlockT*> > InvBlockTraits;
+ for (typename InvBlockTraits::ChildIteratorType I =
+ InvBlockTraits::child_begin(const_cast<BlockT*>(H)),
+ E = InvBlockTraits::child_end(const_cast<BlockT*>(H)); I != E; ++I)
+ if (contains(*I))
+ ++NumBackEdges;
+
+ return NumBackEdges;
+ }
+
+ /// isLoopInvariant - Return true if the specified value is loop invariant
+ ///
+ inline bool isLoopInvariant(Value *V) const {
+ if (Instruction *I = dyn_cast<Instruction>(V))
+ return !contains(I->getParent());
+ return true; // All non-instructions are loop invariant
+ }
+
+ //===--------------------------------------------------------------------===//
+ // APIs for simple analysis of the loop.
+ //
+ // Note that all of these methods can fail on general loops (ie, there may not
+ // be a preheader, etc). For best success, the loop simplification and
+ // induction variable canonicalization pass should be used to normalize loops
+ // for easy analysis. These methods assume canonical loops.
+
+ /// getExitingBlocks - Return all blocks inside the loop that have successors
+ /// outside of the loop. These are the blocks _inside of the current loop_
+ /// which branch out. The returned list is always unique.
+ ///
+ void getExitingBlocks(SmallVectorImpl<BlockT *> &ExitingBlocks) const {
+ // Sort the blocks vector so that we can use binary search to do quick
+ // lookups.
+ SmallVector<BlockT*, 128> LoopBBs(block_begin(), block_end());
+ std::sort(LoopBBs.begin(), LoopBBs.end());
+
+ typedef GraphTraits<BlockT*> BlockTraits;
+ for (block_iterator BI = block_begin(), BE = block_end(); BI != BE; ++BI)
+ for (typename BlockTraits::ChildIteratorType I =
+ BlockTraits::child_begin(*BI), E = BlockTraits::child_end(*BI);
+ I != E; ++I)
+ if (!std::binary_search(LoopBBs.begin(), LoopBBs.end(), *I)) {
+ // Not in current loop? It must be an exit block.
+ ExitingBlocks.push_back(*BI);
+ break;
+ }
+ }
+
+ /// getExitingBlock - If getExitingBlocks would return exactly one block,
+ /// return that block. Otherwise return null.
+ BlockT *getExitingBlock() const {
+ SmallVector<BlockT*, 8> ExitingBlocks;
+ getExitingBlocks(ExitingBlocks);
+ if (ExitingBlocks.size() == 1)
+ return ExitingBlocks[0];
+ return 0;
+ }
+
+ /// getExitBlocks - Return all of the successor blocks of this loop. These
+ /// are the blocks _outside of the current loop_ which are branched to.
+ ///
+ void getExitBlocks(SmallVectorImpl<BlockT*> &ExitBlocks) const {
+ // Sort the blocks vector so that we can use binary search to do quick
+ // lookups.
+ SmallVector<BlockT*, 128> LoopBBs(block_begin(), block_end());
+ std::sort(LoopBBs.begin(), LoopBBs.end());
+
+ typedef GraphTraits<BlockT*> BlockTraits;
+ for (block_iterator BI = block_begin(), BE = block_end(); BI != BE; ++BI)
+ for (typename BlockTraits::ChildIteratorType I =
+ BlockTraits::child_begin(*BI), E = BlockTraits::child_end(*BI);
+ I != E; ++I)
+ if (!std::binary_search(LoopBBs.begin(), LoopBBs.end(), *I))
+ // Not in current loop? It must be an exit block.
+ ExitBlocks.push_back(*I);
+ }
+
+ /// getExitBlock - If getExitBlocks would return exactly one block,
+ /// return that block. Otherwise return null.
+ BlockT *getExitBlock() const {
+ SmallVector<BlockT*, 8> ExitBlocks;
+ getExitBlocks(ExitBlocks);
+ if (ExitBlocks.size() == 1)
+ return ExitBlocks[0];
+ return 0;
+ }
+
+ /// getUniqueExitBlocks - Return all unique successor blocks of this loop.
+ /// These are the blocks _outside of the current loop_ which are branched to.
+ /// This assumes that loop is in canonical form.
+ ///
+ void getUniqueExitBlocks(SmallVectorImpl<BlockT*> &ExitBlocks) const {
+ // Sort the blocks vector so that we can use binary search to do quick
+ // lookups.
+ SmallVector<BlockT*, 128> LoopBBs(block_begin(), block_end());
+ std::sort(LoopBBs.begin(), LoopBBs.end());
+
+ std::vector<BlockT*> switchExitBlocks;
+
+ for (block_iterator BI = block_begin(), BE = block_end(); BI != BE; ++BI) {
+
+ BlockT *current = *BI;
+ switchExitBlocks.clear();
+
+ typedef GraphTraits<BlockT*> BlockTraits;
+ typedef GraphTraits<Inverse<BlockT*> > InvBlockTraits;
+ for (typename BlockTraits::ChildIteratorType I =
+ BlockTraits::child_begin(*BI), E = BlockTraits::child_end(*BI);
+ I != E; ++I) {
+ if (std::binary_search(LoopBBs.begin(), LoopBBs.end(), *I))
+ // If block is inside the loop then it is not a exit block.
+ continue;
+
+ typename InvBlockTraits::ChildIteratorType PI =
+ InvBlockTraits::child_begin(*I);
+ BlockT *firstPred = *PI;
+
+ // If current basic block is this exit block's first predecessor
+ // then only insert exit block in to the output ExitBlocks vector.
+ // This ensures that same exit block is not inserted twice into
+ // ExitBlocks vector.
+ if (current != firstPred)
+ continue;
+
+ // If a terminator has more then two successors, for example SwitchInst,
+ // then it is possible that there are multiple edges from current block
+ // to one exit block.
+ if (std::distance(BlockTraits::child_begin(current),
+ BlockTraits::child_end(current)) <= 2) {
+ ExitBlocks.push_back(*I);
+ continue;
+ }
+
+ // In case of multiple edges from current block to exit block, collect
+ // only one edge in ExitBlocks. Use switchExitBlocks to keep track of
+ // duplicate edges.
+ if (std::find(switchExitBlocks.begin(), switchExitBlocks.end(), *I)
+ == switchExitBlocks.end()) {
+ switchExitBlocks.push_back(*I);
+ ExitBlocks.push_back(*I);
+ }
+ }
+ }
+ }
+
+ /// getLoopPreheader - If there is a preheader for this loop, return it. A
+ /// loop has a preheader if there is only one edge to the header of the loop
+ /// from outside of the loop. If this is the case, the block branching to the
+ /// header of the loop is the preheader node.
+ ///
+ /// This method returns null if there is no preheader for the loop.
+ ///
+ BlockT *getLoopPreheader() const {
+ // Keep track of nodes outside the loop branching to the header...
+ BlockT *Out = 0;
+
+ // Loop over the predecessors of the header node...
+ BlockT *Header = getHeader();
+ typedef GraphTraits<BlockT*> BlockTraits;
+ typedef GraphTraits<Inverse<BlockT*> > InvBlockTraits;
+ for (typename InvBlockTraits::ChildIteratorType PI =
+ InvBlockTraits::child_begin(Header),
+ PE = InvBlockTraits::child_end(Header); PI != PE; ++PI)
+ if (!contains(*PI)) { // If the block is not in the loop...
+ if (Out && Out != *PI)
+ return 0; // Multiple predecessors outside the loop
+ Out = *PI;
+ }
+
+ // Make sure there is only one exit out of the preheader.
+ assert(Out && "Header of loop has no predecessors from outside loop?");
+ typename BlockTraits::ChildIteratorType SI = BlockTraits::child_begin(Out);
+ ++SI;
+ if (SI != BlockTraits::child_end(Out))
+ return 0; // Multiple exits from the block, must not be a preheader.
+
+ // If there is exactly one preheader, return it. If there was zero, then
+ // Out is still null.
+ return Out;
+ }
+
+ /// getLoopLatch - If there is a single latch block for this loop, return it.
+ /// A latch block is a block that contains a branch back to the header.
+ /// A loop header in normal form has two edges into it: one from a preheader
+ /// and one from a latch block.
+ BlockT *getLoopLatch() const {
+ BlockT *Header = getHeader();
+ typedef GraphTraits<Inverse<BlockT*> > InvBlockTraits;
+ typename InvBlockTraits::ChildIteratorType PI =
+ InvBlockTraits::child_begin(Header);
+ typename InvBlockTraits::ChildIteratorType PE =
+ InvBlockTraits::child_end(Header);
+ if (PI == PE) return 0; // no preds?
+
+ BlockT *Latch = 0;
+ if (contains(*PI))
+ Latch = *PI;
+ ++PI;
+ if (PI == PE) return 0; // only one pred?
+
+ if (contains(*PI)) {
+ if (Latch) return 0; // multiple backedges
+ Latch = *PI;
+ }
+ ++PI;
+ if (PI != PE) return 0; // more than two preds
+
+ return Latch;
+ }
+
+ /// getCanonicalInductionVariable - Check to see if the loop has a canonical
+ /// induction variable: an integer recurrence that starts at 0 and increments
+ /// by one each time through the loop. If so, return the phi node that
+ /// corresponds to it.
+ ///
+ /// The IndVarSimplify pass transforms loops to have a canonical induction
+ /// variable.
+ ///
+ inline PHINode *getCanonicalInductionVariable() const {
+ BlockT *H = getHeader();
+
+ BlockT *Incoming = 0, *Backedge = 0;
+ typedef GraphTraits<Inverse<BlockT*> > InvBlockTraits;
+ typename InvBlockTraits::ChildIteratorType PI =
+ InvBlockTraits::child_begin(H);
+ assert(PI != InvBlockTraits::child_end(H) &&
+ "Loop must have at least one backedge!");
+ Backedge = *PI++;
+ if (PI == InvBlockTraits::child_end(H)) return 0; // dead loop
+ Incoming = *PI++;
+ if (PI != InvBlockTraits::child_end(H)) return 0; // multiple backedges?
+
+ if (contains(Incoming)) {
+ if (contains(Backedge))
+ return 0;
+ std::swap(Incoming, Backedge);
+ } else if (!contains(Backedge))
+ return 0;
+
+ // Loop over all of the PHI nodes, looking for a canonical indvar.
+ for (typename BlockT::iterator I = H->begin(); isa<PHINode>(I); ++I) {
+ PHINode *PN = cast<PHINode>(I);
+ if (ConstantInt *CI =
+ dyn_cast<ConstantInt>(PN->getIncomingValueForBlock(Incoming)))
+ if (CI->isNullValue())
+ if (Instruction *Inc =
+ dyn_cast<Instruction>(PN->getIncomingValueForBlock(Backedge)))
+ if (Inc->getOpcode() == Instruction::Add &&
+ Inc->getOperand(0) == PN)
+ if (ConstantInt *CI = dyn_cast<ConstantInt>(Inc->getOperand(1)))
+ if (CI->equalsInt(1))
+ return PN;
+ }
+ return 0;
+ }
+
+ /// getCanonicalInductionVariableIncrement - Return the LLVM value that holds
+ /// the canonical induction variable value for the "next" iteration of the
+ /// loop. This always succeeds if getCanonicalInductionVariable succeeds.
+ ///
+ inline Instruction *getCanonicalInductionVariableIncrement() const {
+ if (PHINode *PN = getCanonicalInductionVariable()) {
+ bool P1InLoop = contains(PN->getIncomingBlock(1));
+ return cast<Instruction>(PN->getIncomingValue(P1InLoop));
+ }
+ return 0;
+ }
+
+ /// getTripCount - Return a loop-invariant LLVM value indicating the number of
+ /// times the loop will be executed. Note that this means that the backedge
+ /// of the loop executes N-1 times. If the trip-count cannot be determined,
+ /// this returns null.
+ ///
+ /// The IndVarSimplify pass transforms loops to have a form that this
+ /// function easily understands.
+ ///
+ inline Value *getTripCount() const {
+ // Canonical loops will end with a 'cmp ne I, V', where I is the incremented
+ // canonical induction variable and V is the trip count of the loop.
+ Instruction *Inc = getCanonicalInductionVariableIncrement();
+ if (Inc == 0) return 0;
+ PHINode *IV = cast<PHINode>(Inc->getOperand(0));
+
+ BlockT *BackedgeBlock =
+ IV->getIncomingBlock(contains(IV->getIncomingBlock(1)));
+
+ if (BranchInst *BI = dyn_cast<BranchInst>(BackedgeBlock->getTerminator()))
+ if (BI->isConditional()) {
+ if (ICmpInst *ICI = dyn_cast<ICmpInst>(BI->getCondition())) {
+ if (ICI->getOperand(0) == Inc) {
+ if (BI->getSuccessor(0) == getHeader()) {
+ if (ICI->getPredicate() == ICmpInst::ICMP_NE)
+ return ICI->getOperand(1);
+ } else if (ICI->getPredicate() == ICmpInst::ICMP_EQ) {
+ return ICI->getOperand(1);
+ }
+ }
+ }
+ }
+
+ return 0;
+ }
+
+ /// getSmallConstantTripCount - Returns the trip count of this loop as a
+ /// normal unsigned value, if possible. Returns 0 if the trip count is unknown
+ /// of not constant. Will also return 0 if the trip count is very large
+ /// (>= 2^32)
+ inline unsigned getSmallConstantTripCount() const {
+ Value* TripCount = this->getTripCount();
+ if (TripCount) {
+ if (ConstantInt *TripCountC = dyn_cast<ConstantInt>(TripCount)) {
+ // Guard against huge trip counts.
+ if (TripCountC->getValue().getActiveBits() <= 32) {
+ return (unsigned)TripCountC->getZExtValue();
+ }
+ }
+ }
+ return 0;
+ }
+
+ /// getSmallConstantTripMultiple - Returns the largest constant divisor of the
+ /// trip count of this loop as a normal unsigned value, if possible. This
+ /// means that the actual trip count is always a multiple of the returned
+ /// value (don't forget the trip count could very well be zero as well!).
+ ///
+ /// Returns 1 if the trip count is unknown or not guaranteed to be the
+ /// multiple of a constant (which is also the case if the trip count is simply
+ /// constant, use getSmallConstantTripCount for that case), Will also return 1
+ /// if the trip count is very large (>= 2^32).
+ inline unsigned getSmallConstantTripMultiple() const {
+ Value* TripCount = this->getTripCount();
+ // This will hold the ConstantInt result, if any
+ ConstantInt *Result = NULL;
+ if (TripCount) {
+ // See if the trip count is constant itself
+ Result = dyn_cast<ConstantInt>(TripCount);
+ // if not, see if it is a multiplication
+ if (!Result)
+ if (BinaryOperator *BO = dyn_cast<BinaryOperator>(TripCount)) {
+ switch (BO->getOpcode()) {
+ case BinaryOperator::Mul:
+ Result = dyn_cast<ConstantInt>(BO->getOperand(1));
+ break;
+ default:
+ break;
+ }
+ }
+ }
+ // Guard against huge trip counts.
+ if (Result && Result->getValue().getActiveBits() <= 32) {
+ return (unsigned)Result->getZExtValue();
+ } else {
+ return 1;
+ }
+ }
+
+ /// isLCSSAForm - Return true if the Loop is in LCSSA form
+ inline bool isLCSSAForm() const {
+ // Sort the blocks vector so that we can use binary search to do quick
+ // lookups.
+ SmallPtrSet<BlockT*, 16> LoopBBs(block_begin(), block_end());
+
+ for (block_iterator BI = block_begin(), E = block_end(); BI != E; ++BI) {
+ BlockT *BB = *BI;
+ for (typename BlockT::iterator I = BB->begin(), E = BB->end(); I != E;++I)
+ for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); UI != E;
+ ++UI) {
+ BlockT *UserBB = cast<Instruction>(*UI)->getParent();
+ if (PHINode *P = dyn_cast<PHINode>(*UI)) {
+ UserBB = P->getIncomingBlock(UI);
+ }
+
+ // Check the current block, as a fast-path. Most values are used in
+ // the same block they are defined in.
+ if (UserBB != BB && !LoopBBs.count(UserBB))
+ return false;
+ }
+ }
+
+ return true;
+ }
+
+ //===--------------------------------------------------------------------===//
+ // APIs for updating loop information after changing the CFG
+ //
+
+ /// addBasicBlockToLoop - This method is used by other analyses to update loop
+ /// information. NewBB is set to be a new member of the current loop.
+ /// Because of this, it is added as a member of all parent loops, and is added
+ /// to the specified LoopInfo object as being in the current basic block. It
+ /// is not valid to replace the loop header with this method.
+ ///
+ void addBasicBlockToLoop(BlockT *NewBB, LoopInfoBase<BlockT> &LI);
+
+ /// replaceChildLoopWith - This is used when splitting loops up. It replaces
+ /// the OldChild entry in our children list with NewChild, and updates the
+ /// parent pointer of OldChild to be null and the NewChild to be this loop.
+ /// This updates the loop depth of the new child.
+ void replaceChildLoopWith(LoopBase<BlockT> *OldChild,
+ LoopBase<BlockT> *NewChild) {
+ assert(OldChild->ParentLoop == this && "This loop is already broken!");
+ assert(NewChild->ParentLoop == 0 && "NewChild already has a parent!");
+ typename std::vector<LoopBase<BlockT>*>::iterator I =
+ std::find(SubLoops.begin(), SubLoops.end(), OldChild);
+ assert(I != SubLoops.end() && "OldChild not in loop!");
+ *I = NewChild;
+ OldChild->ParentLoop = 0;
+ NewChild->ParentLoop = this;
+ }
+
+ /// addChildLoop - Add the specified loop to be a child of this loop. This
+ /// updates the loop depth of the new child.
+ ///
+ void addChildLoop(LoopBase<BlockT> *NewChild) {
+ assert(NewChild->ParentLoop == 0 && "NewChild already has a parent!");
+ NewChild->ParentLoop = this;
+ SubLoops.push_back(NewChild);
+ }
+
+ /// removeChildLoop - This removes the specified child from being a subloop of
+ /// this loop. The loop is not deleted, as it will presumably be inserted
+ /// into another loop.
+ LoopBase<BlockT> *removeChildLoop(iterator I) {
+ assert(I != SubLoops.end() && "Cannot remove end iterator!");
+ LoopBase<BlockT> *Child = *I;
+ assert(Child->ParentLoop == this && "Child is not a child of this loop!");
+ SubLoops.erase(SubLoops.begin()+(I-begin()));
+ Child->ParentLoop = 0;
+ return Child;
+ }
+
+ /// addBlockEntry - This adds a basic block directly to the basic block list.
+ /// This should only be used by transformations that create new loops. Other
+ /// transformations should use addBasicBlockToLoop.
+ void addBlockEntry(BlockT *BB) {
+ Blocks.push_back(BB);
+ }
+
+ /// moveToHeader - This method is used to move BB (which must be part of this
+ /// loop) to be the loop header of the loop (the block that dominates all
+ /// others).
+ void moveToHeader(BlockT *BB) {
+ if (Blocks[0] == BB) return;
+ for (unsigned i = 0; ; ++i) {
+ assert(i != Blocks.size() && "Loop does not contain BB!");
+ if (Blocks[i] == BB) {
+ Blocks[i] = Blocks[0];
+ Blocks[0] = BB;
+ return;
+ }
+ }
+ }
+
+ /// removeBlockFromLoop - This removes the specified basic block from the
+ /// current loop, updating the Blocks as appropriate. This does not update
+ /// the mapping in the LoopInfo class.
+ void removeBlockFromLoop(BlockT *BB) {
+ RemoveFromVector(Blocks, BB);
+ }
+
+ /// verifyLoop - Verify loop structure
+ void verifyLoop() const {
+#ifndef NDEBUG
+ assert (getHeader() && "Loop header is missing");
+ assert (getLoopPreheader() && "Loop preheader is missing");
+ assert (getLoopLatch() && "Loop latch is missing");
+ for (iterator I = SubLoops.begin(), E = SubLoops.end(); I != E; ++I)
+ (*I)->verifyLoop();
+#endif
+ }
+
+ void print(std::ostream &OS, unsigned Depth = 0) const {
+ OS << std::string(Depth*2, ' ') << "Loop at depth " << getLoopDepth()
+ << " containing: ";
+
+ for (unsigned i = 0; i < getBlocks().size(); ++i) {
+ if (i) OS << ",";
+ BlockT *BB = getBlocks()[i];
+ WriteAsOperand(OS, BB, false);
+ if (BB == getHeader()) OS << "<header>";
+ if (BB == getLoopLatch()) OS << "<latch>";
+ if (isLoopExit(BB)) OS << "<exit>";
+ }
+ OS << "\n";
+
+ for (iterator I = begin(), E = end(); I != E; ++I)
+ (*I)->print(OS, Depth+2);
+ }
+
+ void print(std::ostream *O, unsigned Depth = 0) const {
+ if (O) print(*O, Depth);
+ }
+
+ void dump() const {
+ print(cerr);
+ }
+
+private:
+ friend class LoopInfoBase<BlockT>;
+ explicit LoopBase(BlockT *BB) : ParentLoop(0) {
+ Blocks.push_back(BB);
+ }
+};
+
+
+//===----------------------------------------------------------------------===//
+/// LoopInfo - This class builds and contains all of the top level loop
+/// structures in the specified function.
+///
+
+template<class BlockT>
+class LoopInfoBase {
+ // BBMap - Mapping of basic blocks to the inner most loop they occur in
+ std::map<BlockT*, LoopBase<BlockT>*> BBMap;
+ std::vector<LoopBase<BlockT>*> TopLevelLoops;
+ friend class LoopBase<BlockT>;
+
+public:
+ LoopInfoBase() { }
+ ~LoopInfoBase() { releaseMemory(); }
+
+ void releaseMemory() {
+ for (typename std::vector<LoopBase<BlockT>* >::iterator I =
+ TopLevelLoops.begin(), E = TopLevelLoops.end(); I != E; ++I)
+ delete *I; // Delete all of the loops...
+
+ BBMap.clear(); // Reset internal state of analysis
+ TopLevelLoops.clear();
+ }
+
+ /// iterator/begin/end - The interface to the top-level loops in the current
+ /// function.
+ ///
+ typedef typename std::vector<LoopBase<BlockT>*>::const_iterator iterator;
+ iterator begin() const { return TopLevelLoops.begin(); }
+ iterator end() const { return TopLevelLoops.end(); }
+ bool empty() const { return TopLevelLoops.empty(); }
+
+ /// getLoopFor - Return the inner most loop that BB lives in. If a basic
+ /// block is in no loop (for example the entry node), null is returned.
+ ///
+ LoopBase<BlockT> *getLoopFor(const BlockT *BB) const {
+ typename std::map<BlockT *, LoopBase<BlockT>*>::const_iterator I=
+ BBMap.find(const_cast<BlockT*>(BB));
+ return I != BBMap.end() ? I->second : 0;
+ }
+
+ /// operator[] - same as getLoopFor...
+ ///
+ const LoopBase<BlockT> *operator[](const BlockT *BB) const {
+ return getLoopFor(BB);
+ }
+
+ /// getLoopDepth - Return the loop nesting level of the specified block. A
+ /// depth of 0 means the block is not inside any loop.
+ ///
+ unsigned getLoopDepth(const BlockT *BB) const {
+ const LoopBase<BlockT> *L = getLoopFor(BB);
+ return L ? L->getLoopDepth() : 0;
+ }
+
+ // isLoopHeader - True if the block is a loop header node
+ bool isLoopHeader(BlockT *BB) const {
+ const LoopBase<BlockT> *L = getLoopFor(BB);
+ return L && L->getHeader() == BB;
+ }
+
+ /// removeLoop - This removes the specified top-level loop from this loop info
+ /// object. The loop is not deleted, as it will presumably be inserted into
+ /// another loop.
+ LoopBase<BlockT> *removeLoop(iterator I) {
+ assert(I != end() && "Cannot remove end iterator!");
+ LoopBase<BlockT> *L = *I;
+ assert(L->getParentLoop() == 0 && "Not a top-level loop!");
+ TopLevelLoops.erase(TopLevelLoops.begin() + (I-begin()));
+ return L;
+ }
+
+ /// changeLoopFor - Change the top-level loop that contains BB to the
+ /// specified loop. This should be used by transformations that restructure
+ /// the loop hierarchy tree.
+ void changeLoopFor(BlockT *BB, LoopBase<BlockT> *L) {
+ LoopBase<BlockT> *&OldLoop = BBMap[BB];
+ assert(OldLoop && "Block not in a loop yet!");
+ OldLoop = L;
+ }
+
+ /// changeTopLevelLoop - Replace the specified loop in the top-level loops
+ /// list with the indicated loop.
+ void changeTopLevelLoop(LoopBase<BlockT> *OldLoop,
+ LoopBase<BlockT> *NewLoop) {
+ typename std::vector<LoopBase<BlockT>*>::iterator I =
+ std::find(TopLevelLoops.begin(), TopLevelLoops.end(), OldLoop);
+ assert(I != TopLevelLoops.end() && "Old loop not at top level!");
+ *I = NewLoop;
+ assert(NewLoop->ParentLoop == 0 && OldLoop->ParentLoop == 0 &&
+ "Loops already embedded into a subloop!");
+ }
+
+ /// addTopLevelLoop - This adds the specified loop to the collection of
+ /// top-level loops.
+ void addTopLevelLoop(LoopBase<BlockT> *New) {
+ assert(New->getParentLoop() == 0 && "Loop already in subloop!");
+ TopLevelLoops.push_back(New);
+ }
+
+ /// removeBlock - This method completely removes BB from all data structures,
+ /// including all of the Loop objects it is nested in and our mapping from
+ /// BasicBlocks to loops.
+ void removeBlock(BlockT *BB) {
+ typename std::map<BlockT *, LoopBase<BlockT>*>::iterator I = BBMap.find(BB);
+ if (I != BBMap.end()) {
+ for (LoopBase<BlockT> *L = I->second; L; L = L->getParentLoop())
+ L->removeBlockFromLoop(BB);
+
+ BBMap.erase(I);
+ }
+ }
+
+ // Internals
+
+ static bool isNotAlreadyContainedIn(const LoopBase<BlockT> *SubLoop,
+ const LoopBase<BlockT> *ParentLoop) {
+ if (SubLoop == 0) return true;
+ if (SubLoop == ParentLoop) return false;
+ return isNotAlreadyContainedIn(SubLoop->getParentLoop(), ParentLoop);
+ }
+
+ void Calculate(DominatorTreeBase<BlockT> &DT) {
+ BlockT *RootNode = DT.getRootNode()->getBlock();
+
+ for (df_iterator<BlockT*> NI = df_begin(RootNode),
+ NE = df_end(RootNode); NI != NE; ++NI)
+ if (LoopBase<BlockT> *L = ConsiderForLoop(*NI, DT))
+ TopLevelLoops.push_back(L);
+ }
+
+ LoopBase<BlockT> *ConsiderForLoop(BlockT *BB, DominatorTreeBase<BlockT> &DT) {
+ if (BBMap.find(BB) != BBMap.end()) return 0;// Haven't processed this node?
+
+ std::vector<BlockT *> TodoStack;
+
+ // Scan the predecessors of BB, checking to see if BB dominates any of
+ // them. This identifies backedges which target this node...
+ typedef GraphTraits<Inverse<BlockT*> > InvBlockTraits;
+ for (typename InvBlockTraits::ChildIteratorType I =
+ InvBlockTraits::child_begin(BB), E = InvBlockTraits::child_end(BB);
+ I != E; ++I)
+ if (DT.dominates(BB, *I)) // If BB dominates it's predecessor...
+ TodoStack.push_back(*I);
+
+ if (TodoStack.empty()) return 0; // No backedges to this block...
+
+ // Create a new loop to represent this basic block...
+ LoopBase<BlockT> *L = new LoopBase<BlockT>(BB);
+ BBMap[BB] = L;
+
+ BlockT *EntryBlock = BB->getParent()->begin();
+
+ while (!TodoStack.empty()) { // Process all the nodes in the loop
+ BlockT *X = TodoStack.back();
+ TodoStack.pop_back();
+
+ if (!L->contains(X) && // As of yet unprocessed??
+ DT.dominates(EntryBlock, X)) { // X is reachable from entry block?
+ // Check to see if this block already belongs to a loop. If this occurs
+ // then we have a case where a loop that is supposed to be a child of
+ // the current loop was processed before the current loop. When this
+ // occurs, this child loop gets added to a part of the current loop,
+ // making it a sibling to the current loop. We have to reparent this
+ // loop.
+ if (LoopBase<BlockT> *SubLoop =
+ const_cast<LoopBase<BlockT>*>(getLoopFor(X)))
+ if (SubLoop->getHeader() == X && isNotAlreadyContainedIn(SubLoop, L)){
+ // Remove the subloop from it's current parent...
+ assert(SubLoop->ParentLoop && SubLoop->ParentLoop != L);
+ LoopBase<BlockT> *SLP = SubLoop->ParentLoop; // SubLoopParent
+ typename std::vector<LoopBase<BlockT>*>::iterator I =
+ std::find(SLP->SubLoops.begin(), SLP->SubLoops.end(), SubLoop);
+ assert(I != SLP->SubLoops.end() &&"SubLoop not a child of parent?");
+ SLP->SubLoops.erase(I); // Remove from parent...
+
+ // Add the subloop to THIS loop...
+ SubLoop->ParentLoop = L;
+ L->SubLoops.push_back(SubLoop);
+ }
+
+ // Normal case, add the block to our loop...
+ L->Blocks.push_back(X);
+
+ typedef GraphTraits<Inverse<BlockT*> > InvBlockTraits;
+
+ // Add all of the predecessors of X to the end of the work stack...
+ TodoStack.insert(TodoStack.end(), InvBlockTraits::child_begin(X),
+ InvBlockTraits::child_end(X));
+ }
+ }
+
+ // If there are any loops nested within this loop, create them now!
+ for (typename std::vector<BlockT*>::iterator I = L->Blocks.begin(),
+ E = L->Blocks.end(); I != E; ++I)
+ if (LoopBase<BlockT> *NewLoop = ConsiderForLoop(*I, DT)) {
+ L->SubLoops.push_back(NewLoop);
+ NewLoop->ParentLoop = L;
+ }
+
+ // Add the basic blocks that comprise this loop to the BBMap so that this
+ // loop can be found for them.
+ //
+ for (typename std::vector<BlockT*>::iterator I = L->Blocks.begin(),
+ E = L->Blocks.end(); I != E; ++I) {
+ typename std::map<BlockT*, LoopBase<BlockT>*>::iterator BBMI =
+ BBMap.find(*I);
+ if (BBMI == BBMap.end()) // Not in map yet...
+ BBMap.insert(BBMI, std::make_pair(*I, L)); // Must be at this level
+ }
+
+ // Now that we have a list of all of the child loops of this loop, check to
+ // see if any of them should actually be nested inside of each other. We
+ // can accidentally pull loops our of their parents, so we must make sure to
+ // organize the loop nests correctly now.
+ {
+ std::map<BlockT*, LoopBase<BlockT>*> ContainingLoops;
+ for (unsigned i = 0; i != L->SubLoops.size(); ++i) {
+ LoopBase<BlockT> *Child = L->SubLoops[i];
+ assert(Child->getParentLoop() == L && "Not proper child loop?");
+
+ if (LoopBase<BlockT> *ContainingLoop =
+ ContainingLoops[Child->getHeader()]) {
+ // If there is already a loop which contains this loop, move this loop
+ // into the containing loop.
+ MoveSiblingLoopInto(Child, ContainingLoop);
+ --i; // The loop got removed from the SubLoops list.
+ } else {
+ // This is currently considered to be a top-level loop. Check to see
+ // if any of the contained blocks are loop headers for subloops we
+ // have already processed.
+ for (unsigned b = 0, e = Child->Blocks.size(); b != e; ++b) {
+ LoopBase<BlockT> *&BlockLoop = ContainingLoops[Child->Blocks[b]];
+ if (BlockLoop == 0) { // Child block not processed yet...
+ BlockLoop = Child;
+ } else if (BlockLoop != Child) {
+ LoopBase<BlockT> *SubLoop = BlockLoop;
+ // Reparent all of the blocks which used to belong to BlockLoops
+ for (unsigned j = 0, e = SubLoop->Blocks.size(); j != e; ++j)
+ ContainingLoops[SubLoop->Blocks[j]] = Child;
+
+ // There is already a loop which contains this block, that means
+ // that we should reparent the loop which the block is currently
+ // considered to belong to to be a child of this loop.
+ MoveSiblingLoopInto(SubLoop, Child);
+ --i; // We just shrunk the SubLoops list.
+ }
+ }
+ }
+ }
+ }
+
+ return L;
+ }
+
+ /// MoveSiblingLoopInto - This method moves the NewChild loop to live inside
+ /// of the NewParent Loop, instead of being a sibling of it.
+ void MoveSiblingLoopInto(LoopBase<BlockT> *NewChild,
+ LoopBase<BlockT> *NewParent) {
+ LoopBase<BlockT> *OldParent = NewChild->getParentLoop();
+ assert(OldParent && OldParent == NewParent->getParentLoop() &&
+ NewChild != NewParent && "Not sibling loops!");
+
+ // Remove NewChild from being a child of OldParent
+ typename std::vector<LoopBase<BlockT>*>::iterator I =
+ std::find(OldParent->SubLoops.begin(), OldParent->SubLoops.end(),
+ NewChild);
+ assert(I != OldParent->SubLoops.end() && "Parent fields incorrect??");
+ OldParent->SubLoops.erase(I); // Remove from parent's subloops list
+ NewChild->ParentLoop = 0;
+
+ InsertLoopInto(NewChild, NewParent);
+ }
+
+ /// InsertLoopInto - This inserts loop L into the specified parent loop. If
+ /// the parent loop contains a loop which should contain L, the loop gets
+ /// inserted into L instead.
+ void InsertLoopInto(LoopBase<BlockT> *L, LoopBase<BlockT> *Parent) {
+ BlockT *LHeader = L->getHeader();
+ assert(Parent->contains(LHeader) &&
+ "This loop should not be inserted here!");
+
+ // Check to see if it belongs in a child loop...
+ for (unsigned i = 0, e = static_cast<unsigned>(Parent->SubLoops.size());
+ i != e; ++i)
+ if (Parent->SubLoops[i]->contains(LHeader)) {
+ InsertLoopInto(L, Parent->SubLoops[i]);
+ return;
+ }
+
+ // If not, insert it here!
+ Parent->SubLoops.push_back(L);
+ L->ParentLoop = Parent;
+ }
+
+ // Debugging
+
+ void print(std::ostream &OS, const Module* ) const {
+ for (unsigned i = 0; i < TopLevelLoops.size(); ++i)
+ TopLevelLoops[i]->print(OS);
+ #if 0
+ for (std::map<BasicBlock*, Loop*>::const_iterator I = BBMap.begin(),
+ E = BBMap.end(); I != E; ++I)
+ OS << "BB '" << I->first->getName() << "' level = "
+ << I->second->getLoopDepth() << "\n";
+ #endif
+ }
+};
+
+class LoopInfo : public FunctionPass {
+ LoopInfoBase<BasicBlock>* LI;
+ friend class LoopBase<BasicBlock>;
+
+public:
+ static char ID; // Pass identification, replacement for typeid
+
+ LoopInfo() : FunctionPass(&ID) {
+ LI = new LoopInfoBase<BasicBlock>();
+ }
+
+ ~LoopInfo() { delete LI; }
+
+ LoopInfoBase<BasicBlock>& getBase() { return *LI; }
+
+ /// iterator/begin/end - The interface to the top-level loops in the current
+ /// function.
+ ///
+ typedef std::vector<Loop*>::const_iterator iterator;
+ inline iterator begin() const { return LI->begin(); }
+ inline iterator end() const { return LI->end(); }
+ bool empty() const { return LI->empty(); }
+
+ /// getLoopFor - Return the inner most loop that BB lives in. If a basic
+ /// block is in no loop (for example the entry node), null is returned.
+ ///
+ inline Loop *getLoopFor(const BasicBlock *BB) const {
+ return LI->getLoopFor(BB);
+ }
+
+ /// operator[] - same as getLoopFor...
+ ///
+ inline const Loop *operator[](const BasicBlock *BB) const {
+ return LI->getLoopFor(BB);
+ }
+
+ /// getLoopDepth - Return the loop nesting level of the specified block. A
+ /// depth of 0 means the block is not inside any loop.
+ ///
+ inline unsigned getLoopDepth(const BasicBlock *BB) const {
+ return LI->getLoopDepth(BB);
+ }
+
+ // isLoopHeader - True if the block is a loop header node
+ inline bool isLoopHeader(BasicBlock *BB) const {
+ return LI->isLoopHeader(BB);
+ }
+
+ /// runOnFunction - Calculate the natural loop information.
+ ///
+ virtual bool runOnFunction(Function &F);
+
+ virtual void releaseMemory() { LI->releaseMemory(); }
+
+ virtual void print(std::ostream &O, const Module* M = 0) const {
+ if (O) LI->print(O, M);
+ }
+
+ virtual void getAnalysisUsage(AnalysisUsage &AU) const;
+
+ /// removeLoop - This removes the specified top-level loop from this loop info
+ /// object. The loop is not deleted, as it will presumably be inserted into
+ /// another loop.
+ inline Loop *removeLoop(iterator I) { return LI->removeLoop(I); }
+
+ /// changeLoopFor - Change the top-level loop that contains BB to the
+ /// specified loop. This should be used by transformations that restructure
+ /// the loop hierarchy tree.
+ inline void changeLoopFor(BasicBlock *BB, Loop *L) {
+ LI->changeLoopFor(BB, L);
+ }
+
+ /// changeTopLevelLoop - Replace the specified loop in the top-level loops
+ /// list with the indicated loop.
+ inline void changeTopLevelLoop(Loop *OldLoop, Loop *NewLoop) {
+ LI->changeTopLevelLoop(OldLoop, NewLoop);
+ }
+
+ /// addTopLevelLoop - This adds the specified loop to the collection of
+ /// top-level loops.
+ inline void addTopLevelLoop(Loop *New) {
+ LI->addTopLevelLoop(New);
+ }
+
+ /// removeBlock - This method completely removes BB from all data structures,
+ /// including all of the Loop objects it is nested in and our mapping from
+ /// BasicBlocks to loops.
+ void removeBlock(BasicBlock *BB) {
+ LI->removeBlock(BB);
+ }
+};
+
+
+// Allow clients to walk the list of nested loops...
+template <> struct GraphTraits<const Loop*> {
+ typedef const Loop NodeType;
+ typedef std::vector<Loop*>::const_iterator ChildIteratorType;
+
+ static NodeType *getEntryNode(const Loop *L) { return L; }
+ static inline ChildIteratorType child_begin(NodeType *N) {
+ return N->begin();
+ }
+ static inline ChildIteratorType child_end(NodeType *N) {
+ return N->end();
+ }
+};
+
+template <> struct GraphTraits<Loop*> {
+ typedef Loop NodeType;
+ typedef std::vector<Loop*>::const_iterator ChildIteratorType;
+
+ static NodeType *getEntryNode(Loop *L) { return L; }
+ static inline ChildIteratorType child_begin(NodeType *N) {
+ return N->begin();
+ }
+ static inline ChildIteratorType child_end(NodeType *N) {
+ return N->end();
+ }
+};
+
+template<class BlockT>
+void LoopBase<BlockT>::addBasicBlockToLoop(BlockT *NewBB,
+ LoopInfoBase<BlockT> &LIB) {
+ assert((Blocks.empty() || LIB[getHeader()] == this) &&
+ "Incorrect LI specified for this loop!");
+ assert(NewBB && "Cannot add a null basic block to the loop!");
+ assert(LIB[NewBB] == 0 && "BasicBlock already in the loop!");
+
+ // Add the loop mapping to the LoopInfo object...
+ LIB.BBMap[NewBB] = this;
+
+ // Add the basic block to this loop and all parent loops...
+ LoopBase<BlockT> *L = this;
+ while (L) {
+ L->Blocks.push_back(NewBB);
+ L = L->getParentLoop();
+ }
+}
+
+} // End llvm namespace
+
+#endif
diff --git a/include/llvm/Analysis/LoopPass.h b/include/llvm/Analysis/LoopPass.h
new file mode 100644
index 000000000000..ca41e51aa0ca
--- /dev/null
+++ b/include/llvm/Analysis/LoopPass.h
@@ -0,0 +1,150 @@
+//===- LoopPass.h - LoopPass class ----------------------------------------===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file defines LoopPass class. All loop optimization
+// and transformation passes are derived from LoopPass.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_LOOP_PASS_H
+#define LLVM_LOOP_PASS_H
+
+#include "llvm/Analysis/LoopInfo.h"
+#include "llvm/Pass.h"
+#include "llvm/PassManagers.h"
+#include "llvm/Function.h"
+
+namespace llvm {
+
+class LPPassManager;
+class Function;
+class PMStack;
+
+class LoopPass : public Pass {
+public:
+ explicit LoopPass(intptr_t pid) : Pass(pid) {}
+ explicit LoopPass(void *pid) : Pass(pid) {}
+
+ // runOnLoop - This method should be implemented by the subclass to perform
+ // whatever action is necessary for the specified Loop.
+ virtual bool runOnLoop(Loop *L, LPPassManager &LPM) = 0;
+ virtual bool runOnFunctionBody(Function &F, LPPassManager &LPM) {
+ return false;
+ }
+
+ // Initialization and finalization hooks.
+ virtual bool doInitialization(Loop *L, LPPassManager &LPM) {
+ return false;
+ }
+
+ // Finalization hook does not supply Loop because at this time
+ // loop nest is completely different.
+ virtual bool doFinalization() { return false; }
+
+ // Check if this pass is suitable for the current LPPassManager, if
+ // available. This pass P is not suitable for a LPPassManager if P
+ // is not preserving higher level analysis info used by other
+ // LPPassManager passes. In such case, pop LPPassManager from the
+ // stack. This will force assignPassManager() to create new
+ // LPPassManger as expected.
+ void preparePassManager(PMStack &PMS);
+
+ /// Assign pass manager to manager this pass
+ virtual void assignPassManager(PMStack &PMS,
+ PassManagerType PMT = PMT_LoopPassManager);
+
+ /// Return what kind of Pass Manager can manage this pass.
+ virtual PassManagerType getPotentialPassManagerType() const {
+ return PMT_LoopPassManager;
+ }
+
+ //===--------------------------------------------------------------------===//
+ /// SimpleAnalysis - Provides simple interface to update analysis info
+ /// maintained by various passes. Note, if required this interface can
+ /// be extracted into a separate abstract class but it would require
+ /// additional use of multiple inheritance in Pass class hierarchy, something
+ /// we are trying to avoid.
+
+ /// Each loop pass can override these simple analysis hooks to update
+ /// desired analysis information.
+ /// cloneBasicBlockAnalysis - Clone analysis info associated with basic block.
+ virtual void cloneBasicBlockAnalysis(BasicBlock *F, BasicBlock *T, Loop *L) {}
+
+ /// deletekAnalysisValue - Delete analysis info associated with value V.
+ virtual void deleteAnalysisValue(Value *V, Loop *L) {}
+};
+
+class LPPassManager : public FunctionPass, public PMDataManager {
+public:
+ static char ID;
+ explicit LPPassManager(int Depth);
+
+ /// run - Execute all of the passes scheduled for execution. Keep track of
+ /// whether any of the passes modifies the module, and if so, return true.
+ bool runOnFunction(Function &F);
+
+ /// Pass Manager itself does not invalidate any analysis info.
+ // LPPassManager needs LoopInfo.
+ void getAnalysisUsage(AnalysisUsage &Info) const;
+
+ virtual const char *getPassName() const {
+ return "Loop Pass Manager";
+ }
+
+ /// Print passes managed by this manager
+ void dumpPassStructure(unsigned Offset);
+
+ Pass *getContainedPass(unsigned N) {
+ assert(N < PassVector.size() && "Pass number out of range!");
+ Pass *FP = static_cast<Pass *>(PassVector[N]);
+ return FP;
+ }
+
+ virtual PassManagerType getPassManagerType() const {
+ return PMT_LoopPassManager;
+ }
+
+public:
+ // Delete loop from the loop queue and loop nest (LoopInfo).
+ void deleteLoopFromQueue(Loop *L);
+
+ // Insert loop into the loop nest(LoopInfo) and loop queue(LQ).
+ void insertLoop(Loop *L, Loop *ParentLoop);
+
+ // Reoptimize this loop. LPPassManager will re-insert this loop into the
+ // queue. This allows LoopPass to change loop nest for the loop. This
+ // utility may send LPPassManager into infinite loops so use caution.
+ void redoLoop(Loop *L);
+
+ //===--------------------------------------------------------------------===//
+ /// SimpleAnalysis - Provides simple interface to update analysis info
+ /// maintained by various passes. Note, if required this interface can
+ /// be extracted into a separate abstract class but it would require
+ /// additional use of multiple inheritance in Pass class hierarchy, something
+ /// we are trying to avoid.
+
+ /// cloneBasicBlockSimpleAnalysis - Invoke cloneBasicBlockAnalysis hook for
+ /// all passes that implement simple analysis interface.
+ void cloneBasicBlockSimpleAnalysis(BasicBlock *From, BasicBlock *To, Loop *L);
+
+ /// deleteSimpleAnalysisValue - Invoke deleteAnalysisValue hook for all passes
+ /// that implement simple analysis interface.
+ void deleteSimpleAnalysisValue(Value *V, Loop *L);
+
+private:
+ std::deque<Loop *> LQ;
+ bool skipThisLoop;
+ bool redoThisLoop;
+ LoopInfo *LI;
+ Loop *CurrentLoop;
+};
+
+} // End llvm namespace
+
+#endif
diff --git a/include/llvm/Analysis/LoopVR.h b/include/llvm/Analysis/LoopVR.h
new file mode 100644
index 000000000000..1d806f83aa92
--- /dev/null
+++ b/include/llvm/Analysis/LoopVR.h
@@ -0,0 +1,90 @@
+//===- LoopVR.cpp - Value Range analysis driven by loop information -------===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file defines the interface for the loop-driven value range pass.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ANALYSIS_LOOPVR_H
+#define LLVM_ANALYSIS_LOOPVR_H
+
+#include "llvm/Pass.h"
+#include "llvm/Analysis/ScalarEvolution.h"
+#include "llvm/Support/ConstantRange.h"
+#include <iosfwd>
+#include <map>
+
+namespace llvm {
+
+/// LoopVR - This class maintains a mapping of Values to ConstantRanges.
+/// There are interfaces to look up and update ranges by value, and for
+/// accessing all values with range information.
+///
+class LoopVR : public FunctionPass {
+public:
+ static char ID; // Class identification, replacement for typeinfo
+
+ LoopVR() : FunctionPass(&ID) {}
+
+ bool runOnFunction(Function &F);
+ virtual void print(std::ostream &os, const Module *) const;
+ void releaseMemory();
+
+ void getAnalysisUsage(AnalysisUsage &AU) const {
+ AU.addRequiredTransitive<LoopInfo>();
+ AU.addRequiredTransitive<ScalarEvolution>();
+ AU.setPreservesAll();
+ }
+
+ //===---------------------------------------------------------------------
+ // Methods that are used to look up and update particular values.
+
+ /// get - return the ConstantRange for a given Value of IntegerType.
+ ConstantRange get(Value *V);
+
+ /// remove - remove a value from this analysis.
+ void remove(Value *V);
+
+ /// narrow - improve our unterstanding of a Value by pointing out that it
+ /// must fall within ConstantRange. To replace a range, remove it first.
+ void narrow(Value *V, const ConstantRange &CR);
+
+ //===---------------------------------------------------------------------
+ // Methods that are used to iterate across all values with information.
+
+ /// size - returns the number of Values with information
+ unsigned size() const { return Map.size(); }
+
+ typedef std::map<Value *, ConstantRange *>::iterator iterator;
+
+ /// begin - return an iterator to the first Value, ConstantRange pair
+ iterator begin() { return Map.begin(); }
+
+ /// end - return an iterator one past the last Value, ConstantRange pair
+ iterator end() { return Map.end(); }
+
+ /// getValue - return the Value referenced by an iterator
+ Value *getValue(iterator I) { return I->first; }
+
+ /// getConstantRange - return the ConstantRange referenced by an iterator
+ ConstantRange getConstantRange(iterator I) { return *I->second; }
+
+private:
+ ConstantRange compute(Value *V);
+
+ ConstantRange getRange(SCEVHandle S, Loop *L, ScalarEvolution &SE);
+
+ ConstantRange getRange(SCEVHandle S, SCEVHandle T, ScalarEvolution &SE);
+
+ std::map<Value *, ConstantRange *> Map;
+};
+
+} // end llvm namespace
+
+#endif
diff --git a/include/llvm/Analysis/MemoryDependenceAnalysis.h b/include/llvm/Analysis/MemoryDependenceAnalysis.h
new file mode 100644
index 000000000000..d7d795e08a16
--- /dev/null
+++ b/include/llvm/Analysis/MemoryDependenceAnalysis.h
@@ -0,0 +1,287 @@
+//===- llvm/Analysis/MemoryDependenceAnalysis.h - Memory Deps --*- 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 the MemoryDependenceAnalysis analysis pass.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ANALYSIS_MEMORY_DEPENDENCE_H
+#define LLVM_ANALYSIS_MEMORY_DEPENDENCE_H
+
+#include "llvm/BasicBlock.h"
+#include "llvm/Pass.h"
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/SmallPtrSet.h"
+#include "llvm/ADT/OwningPtr.h"
+#include "llvm/ADT/PointerIntPair.h"
+
+namespace llvm {
+ class Function;
+ class FunctionPass;
+ class Instruction;
+ class CallSite;
+ class AliasAnalysis;
+ class TargetData;
+ class MemoryDependenceAnalysis;
+ class PredIteratorCache;
+
+ /// MemDepResult - A memory dependence query can return one of three different
+ /// answers, described below.
+ class MemDepResult {
+ enum DepType {
+ /// Invalid - Clients of MemDep never see this.
+ Invalid = 0,
+
+ /// Clobber - This is a dependence on the specified instruction which
+ /// clobbers the desired value. The pointer member of the MemDepResult
+ /// pair holds the instruction that clobbers the memory. For example,
+ /// this occurs when we see a may-aliased store to the memory location we
+ /// care about.
+ Clobber,
+
+ /// Def - This is a dependence on the specified instruction which
+ /// defines/produces the desired memory location. The pointer member of
+ /// the MemDepResult pair holds the instruction that defines the memory.
+ /// Cases of interest:
+ /// 1. This could be a load or store for dependence queries on
+ /// load/store. The value loaded or stored is the produced value.
+ /// Note that the pointer operand may be different than that of the
+ /// queried pointer due to must aliases and phi translation. Note
+ /// that the def may not be the same type as the query, the pointers
+ /// may just be must aliases.
+ /// 2. For loads and stores, this could be an allocation instruction. In
+ /// this case, the load is loading an undef value or a store is the
+ /// first store to (that part of) the allocation.
+ /// 3. Dependence queries on calls return Def only when they are
+ /// readonly calls with identical callees and no intervening
+ /// clobbers. No validation is done that the operands to the calls
+ /// are the same.
+ Def,
+
+ /// NonLocal - This marker indicates that the query has no dependency in
+ /// the specified block. To find out more, the client should query other
+ /// predecessor blocks.
+ NonLocal
+ };
+ typedef PointerIntPair<Instruction*, 2, DepType> PairTy;
+ PairTy Value;
+ explicit MemDepResult(PairTy V) : Value(V) {}
+ public:
+ MemDepResult() : Value(0, Invalid) {}
+
+ /// get methods: These are static ctor methods for creating various
+ /// MemDepResult kinds.
+ static MemDepResult getDef(Instruction *Inst) {
+ return MemDepResult(PairTy(Inst, Def));
+ }
+ static MemDepResult getClobber(Instruction *Inst) {
+ return MemDepResult(PairTy(Inst, Clobber));
+ }
+ static MemDepResult getNonLocal() {
+ return MemDepResult(PairTy(0, NonLocal));
+ }
+
+ /// isClobber - Return true if this MemDepResult represents a query that is
+ /// a instruction clobber dependency.
+ bool isClobber() const { return Value.getInt() == Clobber; }
+
+ /// isDef - Return true if this MemDepResult represents a query that is
+ /// a instruction definition dependency.
+ bool isDef() const { return Value.getInt() == Def; }
+
+ /// isNonLocal - Return true if this MemDepResult represents an query that
+ /// is transparent to the start of the block, but where a non-local hasn't
+ /// been done.
+ bool isNonLocal() const { return Value.getInt() == NonLocal; }
+
+ /// getInst() - If this is a normal dependency, return the instruction that
+ /// is depended on. Otherwise, return null.
+ Instruction *getInst() const { return Value.getPointer(); }
+
+ bool operator==(const MemDepResult &M) const { return Value == M.Value; }
+ bool operator!=(const MemDepResult &M) const { return Value != M.Value; }
+ bool operator<(const MemDepResult &M) const { return Value < M.Value; }
+ bool operator>(const MemDepResult &M) const { return Value > M.Value; }
+ private:
+ friend class MemoryDependenceAnalysis;
+ /// Dirty - Entries with this marker occur in a LocalDeps map or
+ /// NonLocalDeps map when the instruction they previously referenced was
+ /// removed from MemDep. In either case, the entry may include an
+ /// instruction pointer. If so, the pointer is an instruction in the
+ /// block where scanning can start from, saving some work.
+ ///
+ /// In a default-constructed MemDepResult object, the type will be Dirty
+ /// and the instruction pointer will be null.
+ ///
+
+ /// isDirty - Return true if this is a MemDepResult in its dirty/invalid.
+ /// state.
+ bool isDirty() const { return Value.getInt() == Invalid; }
+
+ static MemDepResult getDirty(Instruction *Inst) {
+ return MemDepResult(PairTy(Inst, Invalid));
+ }
+ };
+
+ /// MemoryDependenceAnalysis - This is an analysis that determines, for a
+ /// given memory operation, what preceding memory operations it depends on.
+ /// It builds on alias analysis information, and tries to provide a lazy,
+ /// caching interface to a common kind of alias information query.
+ ///
+ /// The dependency information returned is somewhat unusual, but is pragmatic.
+ /// If queried about a store or call that might modify memory, the analysis
+ /// will return the instruction[s] that may either load from that memory or
+ /// store to it. If queried with a load or call that can never modify memory,
+ /// the analysis will return calls and stores that might modify the pointer,
+ /// but generally does not return loads unless a) they are volatile, or
+ /// b) they load from *must-aliased* pointers. Returning a dependence on
+ /// must-alias'd pointers instead of all pointers interacts well with the
+ /// internal caching mechanism.
+ ///
+ class MemoryDependenceAnalysis : public FunctionPass {
+ // A map from instructions to their dependency.
+ typedef DenseMap<Instruction*, MemDepResult> LocalDepMapType;
+ LocalDepMapType LocalDeps;
+
+ public:
+ typedef std::pair<BasicBlock*, MemDepResult> NonLocalDepEntry;
+ typedef std::vector<NonLocalDepEntry> NonLocalDepInfo;
+ private:
+ /// ValueIsLoadPair - This is a pair<Value*, bool> where the bool is true if
+ /// the dependence is a read only dependence, false if read/write.
+ typedef PointerIntPair<Value*, 1, bool> ValueIsLoadPair;
+
+ /// BBSkipFirstBlockPair - This pair is used when caching information for a
+ /// block. If the pointer is null, the cache value is not a full query that
+ /// starts at the specified block. If non-null, the bool indicates whether
+ /// or not the contents of the block was skipped.
+ typedef PointerIntPair<BasicBlock*, 1, bool> BBSkipFirstBlockPair;
+
+ /// CachedNonLocalPointerInfo - This map stores the cached results of doing
+ /// a pointer lookup at the bottom of a block. The key of this map is the
+ /// pointer+isload bit, the value is a list of <bb->result> mappings.
+ typedef DenseMap<ValueIsLoadPair, std::pair<BBSkipFirstBlockPair,
+ NonLocalDepInfo> > CachedNonLocalPointerInfo;
+ CachedNonLocalPointerInfo NonLocalPointerDeps;
+
+ // A map from instructions to their non-local pointer dependencies.
+ typedef DenseMap<Instruction*,
+ SmallPtrSet<ValueIsLoadPair, 4> > ReverseNonLocalPtrDepTy;
+ ReverseNonLocalPtrDepTy ReverseNonLocalPtrDeps;
+
+
+ /// PerInstNLInfo - This is the instruction we keep for each cached access
+ /// that we have for an instruction. The pointer is an owning pointer and
+ /// the bool indicates whether we have any dirty bits in the set.
+ typedef std::pair<NonLocalDepInfo, bool> PerInstNLInfo;
+
+ // A map from instructions to their non-local dependencies.
+ typedef DenseMap<Instruction*, PerInstNLInfo> NonLocalDepMapType;
+
+ NonLocalDepMapType NonLocalDeps;
+
+ // A reverse mapping from dependencies to the dependees. This is
+ // used when removing instructions to keep the cache coherent.
+ typedef DenseMap<Instruction*,
+ SmallPtrSet<Instruction*, 4> > ReverseDepMapType;
+ ReverseDepMapType ReverseLocalDeps;
+
+ // A reverse mapping form dependencies to the non-local dependees.
+ ReverseDepMapType ReverseNonLocalDeps;
+
+ /// Current AA implementation, just a cache.
+ AliasAnalysis *AA;
+ TargetData *TD;
+ OwningPtr<PredIteratorCache> PredCache;
+ public:
+ MemoryDependenceAnalysis();
+ ~MemoryDependenceAnalysis();
+ static char ID;
+
+ /// Pass Implementation stuff. This doesn't do any analysis eagerly.
+ bool runOnFunction(Function &);
+
+ /// Clean up memory in between runs
+ void releaseMemory();
+
+ /// getAnalysisUsage - Does not modify anything. It uses Value Numbering
+ /// and Alias Analysis.
+ ///
+ virtual void getAnalysisUsage(AnalysisUsage &AU) const;
+
+ /// getDependency - Return the instruction on which a memory operation
+ /// depends. See the class comment for more details. It is illegal to call
+ /// this on non-memory instructions.
+ MemDepResult getDependency(Instruction *QueryInst);
+
+ /// getNonLocalCallDependency - Perform a full dependency query for the
+ /// specified call, returning the set of blocks that the value is
+ /// potentially live across. The returned set of results will include a
+ /// "NonLocal" result for all blocks where the value is live across.
+ ///
+ /// This method assumes the instruction returns a "NonLocal" dependency
+ /// within its own block.
+ ///
+ /// This returns a reference to an internal data structure that may be
+ /// invalidated on the next non-local query or when an instruction is
+ /// removed. Clients must copy this data if they want it around longer than
+ /// that.
+ const NonLocalDepInfo &getNonLocalCallDependency(CallSite QueryCS);
+
+
+ /// getNonLocalPointerDependency - Perform a full dependency query for an
+ /// access to the specified (non-volatile) memory location, returning the
+ /// set of instructions that either define or clobber the value.
+ ///
+ /// This method assumes the pointer has a "NonLocal" dependency within BB.
+ void getNonLocalPointerDependency(Value *Pointer, bool isLoad,
+ BasicBlock *BB,
+ SmallVectorImpl<NonLocalDepEntry> &Result);
+
+ /// removeInstruction - Remove an instruction from the dependence analysis,
+ /// updating the dependence of instructions that previously depended on it.
+ void removeInstruction(Instruction *InstToRemove);
+
+ /// invalidateCachedPointerInfo - This method is used to invalidate cached
+ /// information about the specified pointer, because it may be too
+ /// conservative in memdep. This is an optional call that can be used when
+ /// the client detects an equivalence between the pointer and some other
+ /// value and replaces the other value with ptr. This can make Ptr available
+ /// in more places that cached info does not necessarily keep.
+ void invalidateCachedPointerInfo(Value *Ptr);
+
+ private:
+ MemDepResult getPointerDependencyFrom(Value *Pointer, uint64_t MemSize,
+ bool isLoad,
+ BasicBlock::iterator ScanIt,
+ BasicBlock *BB);
+ MemDepResult getCallSiteDependencyFrom(CallSite C, bool isReadOnlyCall,
+ BasicBlock::iterator ScanIt,
+ BasicBlock *BB);
+ bool getNonLocalPointerDepFromBB(Value *Pointer, uint64_t Size,
+ bool isLoad, BasicBlock *BB,
+ SmallVectorImpl<NonLocalDepEntry> &Result,
+ DenseMap<BasicBlock*, Value*> &Visited,
+ bool SkipFirstBlock = false);
+ MemDepResult GetNonLocalInfoForBlock(Value *Pointer, uint64_t PointeeSize,
+ bool isLoad, BasicBlock *BB,
+ NonLocalDepInfo *Cache,
+ unsigned NumSortedEntries);
+
+ void RemoveCachedNonLocalPointerDependencies(ValueIsLoadPair P);
+
+ /// verifyRemoved - Verify that the specified instruction does not occur
+ /// in our internal data structures.
+ void verifyRemoved(Instruction *Inst) const;
+
+ };
+
+} // End llvm namespace
+
+#endif
diff --git a/include/llvm/Analysis/Passes.h b/include/llvm/Analysis/Passes.h
new file mode 100644
index 000000000000..d9121a82a27f
--- /dev/null
+++ b/include/llvm/Analysis/Passes.h
@@ -0,0 +1,128 @@
+//===-- llvm/Analysis/Passes.h - Constructors for analyses ------*- C++ -*-===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This header file defines prototypes for accessor functions that expose passes
+// in the analysis libraries.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ANALYSIS_PASSES_H
+#define LLVM_ANALYSIS_PASSES_H
+
+namespace llvm {
+ class FunctionPass;
+ class ImmutablePass;
+ class ModulePass;
+ class Pass;
+ class LibCallInfo;
+
+ //===--------------------------------------------------------------------===//
+ //
+ // createGlobalsModRefPass - This pass provides alias and mod/ref info for
+ // global values that do not have their addresses taken.
+ //
+ Pass *createGlobalsModRefPass();
+
+ //===--------------------------------------------------------------------===//
+ //
+ // createAliasDebugger - This pass helps debug clients of AA
+ //
+ Pass *createAliasDebugger();
+
+ //===--------------------------------------------------------------------===//
+ //
+ // createAliasAnalysisCounterPass - This pass counts alias queries and how the
+ // alias analysis implementation responds.
+ //
+ ModulePass *createAliasAnalysisCounterPass();
+
+ //===--------------------------------------------------------------------===//
+ //
+ // createAAEvalPass - This pass implements a simple N^2 alias analysis
+ // accuracy evaluator.
+ //
+ FunctionPass *createAAEvalPass();
+
+ //===--------------------------------------------------------------------===//
+ //
+ // createNoAAPass - This pass implements a "I don't know" alias analysis.
+ //
+ ImmutablePass *createNoAAPass();
+
+ //===--------------------------------------------------------------------===//
+ //
+ // createBasicAliasAnalysisPass - This pass implements the default alias
+ // analysis.
+ //
+ ImmutablePass *createBasicAliasAnalysisPass();
+
+ //===--------------------------------------------------------------------===//
+ //
+ /// createLibCallAliasAnalysisPass - Create an alias analysis pass that knows
+ /// about the semantics of a set of libcalls specified by LCI. The newly
+ /// constructed pass takes ownership of the pointer that is provided.
+ ///
+ FunctionPass *createLibCallAliasAnalysisPass(LibCallInfo *LCI);
+
+ //===--------------------------------------------------------------------===//
+ //
+ // createAndersensPass - This pass implements Andersen's interprocedural alias
+ // analysis.
+ //
+ ModulePass *createAndersensPass();
+
+ //===--------------------------------------------------------------------===//
+ //
+ // createProfileLoaderPass - This pass loads information from a profile dump
+ // file.
+ //
+ ModulePass *createProfileLoaderPass();
+
+ //===--------------------------------------------------------------------===//
+ //
+ // createNoProfileInfoPass - This pass implements the default "no profile".
+ //
+ ImmutablePass *createNoProfileInfoPass();
+
+ //===--------------------------------------------------------------------===//
+ //
+ // createDSAAPass - This pass implements simple context sensitive alias
+ // analysis.
+ //
+ ModulePass *createDSAAPass();
+
+ //===--------------------------------------------------------------------===//
+ //
+ // createDSOptPass - This pass uses DSA to do a series of simple
+ // optimizations.
+ //
+ ModulePass *createDSOptPass();
+
+ //===--------------------------------------------------------------------===//
+ //
+ // createSteensgaardPass - This pass uses the data structure graphs to do a
+ // simple context insensitive alias analysis.
+ //
+ ModulePass *createSteensgaardPass();
+
+ //===--------------------------------------------------------------------===//
+ //
+ // createLiveValuesPass - This creates an instance of the LiveValues pass.
+ //
+ FunctionPass *createLiveValuesPass();
+
+ // Minor pass prototypes, allowing us to expose them through bugpoint and
+ // analyze.
+ FunctionPass *createInstCountPass();
+
+ // print debug info intrinsics in human readable form
+ FunctionPass *createDbgInfoPrinterPass();
+}
+
+#endif
diff --git a/include/llvm/Analysis/PostDominators.h b/include/llvm/Analysis/PostDominators.h
new file mode 100644
index 000000000000..cd6af74024a5
--- /dev/null
+++ b/include/llvm/Analysis/PostDominators.h
@@ -0,0 +1,98 @@
+//=- llvm/Analysis/PostDominators.h - Post Dominator Calculation-*- C++ -*-===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file exposes interfaces to post dominance information.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ANALYSIS_POST_DOMINATORS_H
+#define LLVM_ANALYSIS_POST_DOMINATORS_H
+
+#include "llvm/Analysis/Dominators.h"
+
+namespace llvm {
+
+/// PostDominatorTree Class - Concrete subclass of DominatorTree that is used to
+/// compute the a post-dominator tree.
+///
+struct PostDominatorTree : public FunctionPass {
+ static char ID; // Pass identification, replacement for typeid
+ DominatorTreeBase<BasicBlock>* DT;
+
+ PostDominatorTree() : FunctionPass(&ID) {
+ DT = new DominatorTreeBase<BasicBlock>(true);
+ }
+
+ ~PostDominatorTree();
+
+ virtual bool runOnFunction(Function &F);
+
+ virtual void getAnalysisUsage(AnalysisUsage &AU) const {
+ AU.setPreservesAll();
+ }
+
+ inline const std::vector<BasicBlock*> &getRoots() const {
+ return DT->getRoots();
+ }
+
+ inline DomTreeNode *getRootNode() const {
+ return DT->getRootNode();
+ }
+
+ inline DomTreeNode *operator[](BasicBlock *BB) const {
+ return DT->getNode(BB);
+ }
+
+ inline bool properlyDominates(const DomTreeNode* A, DomTreeNode* B) const {
+ return DT->properlyDominates(A, B);
+ }
+
+ inline bool properlyDominates(BasicBlock* A, BasicBlock* B) const {
+ return DT->properlyDominates(A, B);
+ }
+
+ virtual void print(std::ostream &OS, const Module* M= 0) const {
+ DT->print(OS, M);
+ }
+};
+
+FunctionPass* createPostDomTree();
+
+/// PostDominanceFrontier Class - Concrete subclass of DominanceFrontier that is
+/// used to compute the a post-dominance frontier.
+///
+struct PostDominanceFrontier : public DominanceFrontierBase {
+ static char ID;
+ PostDominanceFrontier()
+ : DominanceFrontierBase(&ID, true) {}
+
+ virtual bool runOnFunction(Function &) {
+ Frontiers.clear();
+ PostDominatorTree &DT = getAnalysis<PostDominatorTree>();
+ Roots = DT.getRoots();
+ if (const DomTreeNode *Root = DT.getRootNode())
+ calculate(DT, Root);
+ return false;
+ }
+
+ virtual void getAnalysisUsage(AnalysisUsage &AU) const {
+ AU.setPreservesAll();
+ AU.addRequired<PostDominatorTree>();
+ }
+
+private:
+ const DomSetType &calculate(const PostDominatorTree &DT,
+ const DomTreeNode *Node);
+};
+
+FunctionPass* createPostDomFrontier();
+
+} // End llvm namespace
+
+#endif
diff --git a/include/llvm/Analysis/ProfileInfo.h b/include/llvm/Analysis/ProfileInfo.h
new file mode 100644
index 000000000000..ff83f97ee042
--- /dev/null
+++ b/include/llvm/Analysis/ProfileInfo.h
@@ -0,0 +1,67 @@
+//===- llvm/Analysis/ProfileInfo.h - Profile Info Interface -----*- 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 the generic ProfileInfo interface, which is used as the
+// common interface used by all clients of profiling information, and
+// implemented either by making static guestimations, or by actually reading in
+// profiling information gathered by running the program.
+//
+// Note that to be useful, all profile-based optimizations should preserve
+// ProfileInfo, which requires that they notify it when changes to the CFG are
+// made.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ANALYSIS_PROFILEINFO_H
+#define LLVM_ANALYSIS_PROFILEINFO_H
+
+#include <string>
+#include <map>
+
+namespace llvm {
+ class BasicBlock;
+ class Pass;
+
+ /// ProfileInfo Class - This class holds and maintains edge profiling
+ /// information for some unit of code.
+ class ProfileInfo {
+ protected:
+ // EdgeCounts - Count the number of times a transition between two blocks is
+ // executed. As a special case, we also hold an edge from the null
+ // BasicBlock to the entry block to indicate how many times the function was
+ // entered.
+ std::map<std::pair<BasicBlock*, BasicBlock*>, unsigned> EdgeCounts;
+ public:
+ static char ID; // Class identification, replacement for typeinfo
+ virtual ~ProfileInfo(); // We want to be subclassed
+
+ //===------------------------------------------------------------------===//
+ /// Profile Information Queries
+ ///
+ unsigned getExecutionCount(BasicBlock *BB) const;
+
+ unsigned getEdgeWeight(BasicBlock *Src, BasicBlock *Dest) const {
+ std::map<std::pair<BasicBlock*, BasicBlock*>, unsigned>::const_iterator I=
+ EdgeCounts.find(std::make_pair(Src, Dest));
+ return I != EdgeCounts.end() ? I->second : 0;
+ }
+
+ //===------------------------------------------------------------------===//
+ /// Analysis Update Methods
+ ///
+
+ };
+
+ /// createProfileLoaderPass - This function returns a Pass that loads the
+ /// profiling information for the module from the specified filename, making
+ /// it available to the optimizers.
+ Pass *createProfileLoaderPass(const std::string &Filename);
+} // End llvm namespace
+
+#endif
diff --git a/include/llvm/Analysis/ProfileInfoLoader.h b/include/llvm/Analysis/ProfileInfoLoader.h
new file mode 100644
index 000000000000..8a5141ab2352
--- /dev/null
+++ b/include/llvm/Analysis/ProfileInfoLoader.h
@@ -0,0 +1,89 @@
+//===- ProfileInfoLoader.h - Load & convert profile information -*- C++ -*-===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// The ProfileInfoLoader class is used to load and represent profiling
+// information read in from the dump file. If conversions between formats are
+// needed, it can also do this.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ANALYSIS_PROFILEINFOLOADER_H
+#define LLVM_ANALYSIS_PROFILEINFOLOADER_H
+
+#include <vector>
+#include <string>
+#include <utility>
+
+namespace llvm {
+
+class Module;
+class Function;
+class BasicBlock;
+
+class ProfileInfoLoader {
+ Module &M;
+ std::vector<std::string> CommandLines;
+ std::vector<unsigned> FunctionCounts;
+ std::vector<unsigned> BlockCounts;
+ std::vector<unsigned> EdgeCounts;
+ std::vector<unsigned> BBTrace;
+public:
+ // ProfileInfoLoader ctor - Read the specified profiling data file, exiting
+ // the program if the file is invalid or broken.
+ ProfileInfoLoader(const char *ToolName, const std::string &Filename,
+ Module &M);
+
+ unsigned getNumExecutions() const { return CommandLines.size(); }
+ const std::string &getExecution(unsigned i) const { return CommandLines[i]; }
+
+ // getFunctionCounts - This method is used by consumers of function counting
+ // information. If we do not directly have function count information, we
+ // compute it from other, more refined, types of profile information.
+ //
+ void getFunctionCounts(std::vector<std::pair<Function*, unsigned> > &Counts);
+
+ // hasAccurateBlockCounts - Return true if we can synthesize accurate block
+ // frequency information from whatever we have.
+ //
+ bool hasAccurateBlockCounts() const {
+ return !BlockCounts.empty() || !EdgeCounts.empty();
+ }
+
+ // hasAccurateEdgeCounts - Return true if we can synthesize accurate edge
+ // frequency information from whatever we have.
+ //
+ bool hasAccurateEdgeCounts() const {
+ return !EdgeCounts.empty();
+ }
+
+ // getBlockCounts - This method is used by consumers of block counting
+ // information. If we do not directly have block count information, we
+ // compute it from other, more refined, types of profile information.
+ //
+ void getBlockCounts(std::vector<std::pair<BasicBlock*, unsigned> > &Counts);
+
+ // getEdgeCounts - This method is used by consumers of edge counting
+ // information. If we do not directly have edge count information, we compute
+ // it from other, more refined, types of profile information.
+ //
+ // Edges are represented as a pair, where the first element is the basic block
+ // and the second element is the successor number.
+ //
+ typedef std::pair<BasicBlock*, unsigned> Edge;
+ void getEdgeCounts(std::vector<std::pair<Edge, unsigned> > &Counts);
+
+ // getBBTrace - This method is used by consumers of basic-block trace
+ // information.
+ //
+ void getBBTrace(std::vector<BasicBlock *> &Trace);
+};
+
+} // End llvm namespace
+
+#endif
diff --git a/include/llvm/Analysis/ProfileInfoTypes.h b/include/llvm/Analysis/ProfileInfoTypes.h
new file mode 100644
index 000000000000..f311f8cb90c5
--- /dev/null
+++ b/include/llvm/Analysis/ProfileInfoTypes.h
@@ -0,0 +1,28 @@
+/*===-- ProfileInfoTypes.h - Profiling info shared constants ------*- 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 constants shared by the various different profiling
+|* runtime libraries and the LLVM C++ profile info loader. It must be a
+|* C header because, at present, the profiling runtimes are written in C.
+|*
+\*===----------------------------------------------------------------------===*/
+
+#ifndef LLVM_ANALYSIS_PROFILEINFOTYPES_H
+#define LLVM_ANALYSIS_PROFILEINFOTYPES_H
+
+enum ProfilingType {
+ ArgumentInfo = 1, /* The command line argument block */
+ FunctionInfo = 2, /* Function profiling information */
+ BlockInfo = 3, /* Block profiling information */
+ EdgeInfo = 4, /* Edge profiling information */
+ PathInfo = 5, /* Path profiling information */
+ BBTraceInfo = 6 /* Basic block trace information */
+};
+
+#endif /* LLVM_ANALYSIS_PROFILEINFOTYPES_H */
diff --git a/include/llvm/Analysis/ScalarEvolution.h b/include/llvm/Analysis/ScalarEvolution.h
new file mode 100644
index 000000000000..88002cb77530
--- /dev/null
+++ b/include/llvm/Analysis/ScalarEvolution.h
@@ -0,0 +1,546 @@
+//===- llvm/Analysis/ScalarEvolution.h - Scalar Evolution -------*- C++ -*-===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// The ScalarEvolution class is an LLVM pass which can be used to analyze and
+// catagorize scalar expressions in loops. It specializes in recognizing
+// general induction variables, representing them with the abstract and opaque
+// SCEV class. Given this analysis, trip counts of loops and other important
+// properties can be obtained.
+//
+// This analysis is primarily useful for induction variable substitution and
+// strength reduction.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ANALYSIS_SCALAREVOLUTION_H
+#define LLVM_ANALYSIS_SCALAREVOLUTION_H
+
+#include "llvm/Pass.h"
+#include "llvm/Analysis/LoopInfo.h"
+#include "llvm/Support/DataTypes.h"
+#include "llvm/Support/ValueHandle.h"
+#include <iosfwd>
+
+namespace llvm {
+ class APInt;
+ class ConstantInt;
+ class Type;
+ class SCEVHandle;
+ class ScalarEvolution;
+ class TargetData;
+
+ /// SCEV - This class represents an analyzed expression in the program. These
+ /// are reference-counted opaque objects that the client is not allowed to
+ /// do much with directly.
+ ///
+ class SCEV {
+ const unsigned SCEVType; // The SCEV baseclass this node corresponds to
+ mutable unsigned RefCount;
+
+ friend class SCEVHandle;
+ void addRef() const { ++RefCount; }
+ void dropRef() const {
+ if (--RefCount == 0)
+ delete this;
+ }
+
+ SCEV(const SCEV &); // DO NOT IMPLEMENT
+ void operator=(const SCEV &); // DO NOT IMPLEMENT
+ protected:
+ virtual ~SCEV();
+ public:
+ explicit SCEV(unsigned SCEVTy) : SCEVType(SCEVTy), RefCount(0) {}
+
+ unsigned getSCEVType() const { return SCEVType; }
+
+ /// isLoopInvariant - Return true if the value of this SCEV is unchanging in
+ /// the specified loop.
+ virtual bool isLoopInvariant(const Loop *L) const = 0;
+
+ /// hasComputableLoopEvolution - Return true if this SCEV changes value in a
+ /// known way in the specified loop. This property being true implies that
+ /// the value is variant in the loop AND that we can emit an expression to
+ /// compute the value of the expression at any particular loop iteration.
+ virtual bool hasComputableLoopEvolution(const Loop *L) const = 0;
+
+ /// getType - Return the LLVM type of this SCEV expression.
+ ///
+ virtual const Type *getType() const = 0;
+
+ /// isZero - Return true if the expression is a constant zero.
+ ///
+ bool isZero() const;
+
+ /// isOne - Return true if the expression is a constant one.
+ ///
+ bool isOne() const;
+
+ /// replaceSymbolicValuesWithConcrete - If this SCEV internally references
+ /// the symbolic value "Sym", construct and return a new SCEV that produces
+ /// the same value, but which uses the concrete value Conc instead of the
+ /// symbolic value. If this SCEV does not use the symbolic value, it
+ /// returns itself.
+ virtual SCEVHandle
+ replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym,
+ const SCEVHandle &Conc,
+ ScalarEvolution &SE) const = 0;
+
+ /// dominates - Return true if elements that makes up this SCEV dominates
+ /// the specified basic block.
+ virtual bool dominates(BasicBlock *BB, DominatorTree *DT) const = 0;
+
+ /// print - Print out the internal representation of this scalar to the
+ /// specified stream. This should really only be used for debugging
+ /// purposes.
+ virtual void print(raw_ostream &OS) const = 0;
+ void print(std::ostream &OS) const;
+ void print(std::ostream *OS) const { if (OS) print(*OS); }
+
+ /// dump - This method is used for debugging.
+ ///
+ void dump() const;
+ };
+
+ inline raw_ostream &operator<<(raw_ostream &OS, const SCEV &S) {
+ S.print(OS);
+ return OS;
+ }
+
+ inline std::ostream &operator<<(std::ostream &OS, const SCEV &S) {
+ S.print(OS);
+ return OS;
+ }
+
+ /// SCEVCouldNotCompute - An object of this class is returned by queries that
+ /// could not be answered. For example, if you ask for the number of
+ /// iterations of a linked-list traversal loop, you will get one of these.
+ /// None of the standard SCEV operations are valid on this class, it is just a
+ /// marker.
+ struct SCEVCouldNotCompute : public SCEV {
+ SCEVCouldNotCompute();
+ ~SCEVCouldNotCompute();
+
+ // None of these methods are valid for this object.
+ virtual bool isLoopInvariant(const Loop *L) const;
+ virtual const Type *getType() const;
+ virtual bool hasComputableLoopEvolution(const Loop *L) const;
+ virtual void print(raw_ostream &OS) const;
+ virtual SCEVHandle
+ replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym,
+ const SCEVHandle &Conc,
+ ScalarEvolution &SE) const;
+
+ virtual bool dominates(BasicBlock *BB, DominatorTree *DT) const {
+ return true;
+ }
+
+ /// Methods for support type inquiry through isa, cast, and dyn_cast:
+ static inline bool classof(const SCEVCouldNotCompute *S) { return true; }
+ static bool classof(const SCEV *S);
+ };
+
+ /// SCEVHandle - This class is used to maintain the SCEV object's refcounts,
+ /// freeing the objects when the last reference is dropped.
+ class SCEVHandle {
+ const SCEV *S;
+ SCEVHandle(); // DO NOT IMPLEMENT
+ public:
+ SCEVHandle(const SCEV *s) : S(s) {
+ assert(S && "Cannot create a handle to a null SCEV!");
+ S->addRef();
+ }
+ SCEVHandle(const SCEVHandle &RHS) : S(RHS.S) {
+ S->addRef();
+ }
+ ~SCEVHandle() { S->dropRef(); }
+
+ operator const SCEV*() const { return S; }
+
+ const SCEV &operator*() const { return *S; }
+ const SCEV *operator->() const { return S; }
+
+ bool operator==(const SCEV *RHS) const { return S == RHS; }
+ bool operator!=(const SCEV *RHS) const { return S != RHS; }
+
+ const SCEVHandle &operator=(SCEV *RHS) {
+ if (S != RHS) {
+ S->dropRef();
+ S = RHS;
+ S->addRef();
+ }
+ return *this;
+ }
+
+ const SCEVHandle &operator=(const SCEVHandle &RHS) {
+ if (S != RHS.S) {
+ S->dropRef();
+ S = RHS.S;
+ S->addRef();
+ }
+ return *this;
+ }
+ };
+
+ template<typename From> struct simplify_type;
+ template<> struct simplify_type<const SCEVHandle> {
+ typedef const SCEV* SimpleType;
+ static SimpleType getSimplifiedValue(const SCEVHandle &Node) {
+ return Node;
+ }
+ };
+ template<> struct simplify_type<SCEVHandle>
+ : public simplify_type<const SCEVHandle> {};
+
+ /// ScalarEvolution - This class is the main scalar evolution driver. Because
+ /// client code (intentionally) can't do much with the SCEV objects directly,
+ /// they must ask this class for services.
+ ///
+ class ScalarEvolution : public FunctionPass {
+ /// SCEVCallbackVH - A CallbackVH to arrange for ScalarEvolution to be
+ /// notified whenever a Value is deleted.
+ class SCEVCallbackVH : public CallbackVH {
+ ScalarEvolution *SE;
+ virtual void deleted();
+ virtual void allUsesReplacedWith(Value *New);
+ public:
+ SCEVCallbackVH(Value *V, ScalarEvolution *SE = 0);
+ };
+
+ friend class SCEVCallbackVH;
+ friend class SCEVExpander;
+
+ /// F - The function we are analyzing.
+ ///
+ Function *F;
+
+ /// LI - The loop information for the function we are currently analyzing.
+ ///
+ LoopInfo *LI;
+
+ /// TD - The target data information for the target we are targetting.
+ ///
+ TargetData *TD;
+
+ /// UnknownValue - This SCEV is used to represent unknown trip counts and
+ /// things.
+ SCEVHandle UnknownValue;
+
+ /// Scalars - This is a cache of the scalars we have analyzed so far.
+ ///
+ std::map<SCEVCallbackVH, SCEVHandle> Scalars;
+
+ /// BackedgeTakenInfo - Information about the backedge-taken count
+ /// of a loop. This currently inclues an exact count and a maximum count.
+ ///
+ struct BackedgeTakenInfo {
+ /// Exact - An expression indicating the exact backedge-taken count of
+ /// the loop if it is known, or a SCEVCouldNotCompute otherwise.
+ SCEVHandle Exact;
+
+ /// Exact - An expression indicating the least maximum backedge-taken
+ /// count of the loop that is known, or a SCEVCouldNotCompute.
+ SCEVHandle Max;
+
+ /*implicit*/ BackedgeTakenInfo(SCEVHandle exact) :
+ Exact(exact), Max(exact) {}
+
+ /*implicit*/ BackedgeTakenInfo(const SCEV *exact) :
+ Exact(exact), Max(exact) {}
+
+ BackedgeTakenInfo(SCEVHandle exact, SCEVHandle max) :
+ Exact(exact), Max(max) {}
+
+ /// hasAnyInfo - Test whether this BackedgeTakenInfo contains any
+ /// computed information, or whether it's all SCEVCouldNotCompute
+ /// values.
+ bool hasAnyInfo() const {
+ return !isa<SCEVCouldNotCompute>(Exact) ||
+ !isa<SCEVCouldNotCompute>(Max);
+ }
+ };
+
+ /// BackedgeTakenCounts - Cache the backedge-taken count of the loops for
+ /// this function as they are computed.
+ std::map<const Loop*, BackedgeTakenInfo> BackedgeTakenCounts;
+
+ /// ConstantEvolutionLoopExitValue - This map contains entries for all of
+ /// the PHI instructions that we attempt to compute constant evolutions for.
+ /// This allows us to avoid potentially expensive recomputation of these
+ /// properties. An instruction maps to null if we are unable to compute its
+ /// exit value.
+ std::map<PHINode*, Constant*> ConstantEvolutionLoopExitValue;
+
+ /// ValuesAtScopes - This map contains entries for all the instructions
+ /// that we attempt to compute getSCEVAtScope information for without
+ /// using SCEV techniques, which can be expensive.
+ std::map<Instruction *, std::map<const Loop *, Constant *> > ValuesAtScopes;
+
+ /// createSCEV - We know that there is no SCEV for the specified value.
+ /// Analyze the expression.
+ SCEVHandle createSCEV(Value *V);
+
+ /// createNodeForPHI - Provide the special handling we need to analyze PHI
+ /// SCEVs.
+ SCEVHandle createNodeForPHI(PHINode *PN);
+
+ /// createNodeForGEP - Provide the special handling we need to analyze GEP
+ /// SCEVs.
+ SCEVHandle createNodeForGEP(User *GEP);
+
+ /// ReplaceSymbolicValueWithConcrete - This looks up the computed SCEV value
+ /// for the specified instruction and replaces any references to the
+ /// symbolic value SymName with the specified value. This is used during
+ /// PHI resolution.
+ void ReplaceSymbolicValueWithConcrete(Instruction *I,
+ const SCEVHandle &SymName,
+ const SCEVHandle &NewVal);
+
+ /// getBackedgeTakenInfo - Return the BackedgeTakenInfo for the given
+ /// loop, lazily computing new values if the loop hasn't been analyzed
+ /// yet.
+ const BackedgeTakenInfo &getBackedgeTakenInfo(const Loop *L);
+
+ /// ComputeBackedgeTakenCount - Compute the number of times the specified
+ /// loop will iterate.
+ BackedgeTakenInfo ComputeBackedgeTakenCount(const Loop *L);
+
+ /// ComputeLoadConstantCompareBackedgeTakenCount - Given an exit condition
+ /// of 'icmp op load X, cst', try to see if we can compute the trip count.
+ SCEVHandle
+ ComputeLoadConstantCompareBackedgeTakenCount(LoadInst *LI,
+ Constant *RHS,
+ const Loop *L,
+ ICmpInst::Predicate p);
+
+ /// ComputeBackedgeTakenCountExhaustively - If the trip is known to execute
+ /// a constant number of times (the condition evolves only from constants),
+ /// try to evaluate a few iterations of the loop until we get the exit
+ /// condition gets a value of ExitWhen (true or false). If we cannot
+ /// evaluate the trip count of the loop, return UnknownValue.
+ SCEVHandle ComputeBackedgeTakenCountExhaustively(const Loop *L, Value *Cond,
+ bool ExitWhen);
+
+ /// HowFarToZero - Return the number of times a backedge comparing the
+ /// specified value to zero will execute. If not computable, return
+ /// UnknownValue.
+ SCEVHandle HowFarToZero(const SCEV *V, const Loop *L);
+
+ /// HowFarToNonZero - Return the number of times a backedge checking the
+ /// specified value for nonzero will execute. If not computable, return
+ /// UnknownValue.
+ SCEVHandle HowFarToNonZero(const SCEV *V, const Loop *L);
+
+ /// HowManyLessThans - Return the number of times a backedge containing the
+ /// specified less-than comparison will execute. If not computable, return
+ /// UnknownValue. isSigned specifies whether the less-than is signed.
+ BackedgeTakenInfo HowManyLessThans(const SCEV *LHS, const SCEV *RHS,
+ const Loop *L, bool isSigned);
+
+ /// getLoopPredecessor - If the given loop's header has exactly one unique
+ /// predecessor outside the loop, return it. Otherwise return null.
+ BasicBlock *getLoopPredecessor(const Loop *L);
+
+ /// getPredecessorWithUniqueSuccessorForBB - Return a predecessor of BB
+ /// (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);
+
+ /// getConstantEvolutionLoopExitValue - If we know that the specified Phi is
+ /// in the header of its containing loop, we know the loop executes a
+ /// constant number of times, and the PHI node is just a recurrence
+ /// involving constants, fold it.
+ Constant *getConstantEvolutionLoopExitValue(PHINode *PN, const APInt& BEs,
+ const Loop *L);
+
+ /// forgetLoopPHIs - Delete the memoized SCEVs associated with the
+ /// PHI nodes in the given loop. This is used when the trip count of
+ /// the loop may have changed.
+ void forgetLoopPHIs(const Loop *L);
+
+ public:
+ static char ID; // Pass identification, replacement for typeid
+ ScalarEvolution();
+
+ /// isSCEVable - Test if values of the given type are analyzable within
+ /// the SCEV framework. This primarily includes integer types, and it
+ /// can optionally include pointer types if the ScalarEvolution class
+ /// has access to target-specific information.
+ bool isSCEVable(const Type *Ty) const;
+
+ /// getTypeSizeInBits - Return the size in bits of the specified type,
+ /// for which isSCEVable must return true.
+ uint64_t getTypeSizeInBits(const Type *Ty) const;
+
+ /// getEffectiveSCEVType - Return a type with the same bitwidth as
+ /// the given type and which represents how SCEV will treat the given
+ /// type, for which isSCEVable must return true. For pointer types,
+ /// this is the pointer-sized integer type.
+ const Type *getEffectiveSCEVType(const Type *Ty) const;
+
+ /// getSCEV - Return a SCEV expression handle for the full generality of the
+ /// specified expression.
+ SCEVHandle getSCEV(Value *V);
+
+ SCEVHandle getConstant(ConstantInt *V);
+ SCEVHandle getConstant(const APInt& Val);
+ SCEVHandle getTruncateExpr(const SCEVHandle &Op, const Type *Ty);
+ SCEVHandle getZeroExtendExpr(const SCEVHandle &Op, const Type *Ty);
+ SCEVHandle getSignExtendExpr(const SCEVHandle &Op, const Type *Ty);
+ SCEVHandle getAddExpr(std::vector<SCEVHandle> &Ops);
+ SCEVHandle getAddExpr(const SCEVHandle &LHS, const SCEVHandle &RHS) {
+ std::vector<SCEVHandle> Ops;
+ Ops.push_back(LHS);
+ Ops.push_back(RHS);
+ return getAddExpr(Ops);
+ }
+ SCEVHandle getAddExpr(const SCEVHandle &Op0, const SCEVHandle &Op1,
+ const SCEVHandle &Op2) {
+ std::vector<SCEVHandle> Ops;
+ Ops.push_back(Op0);
+ Ops.push_back(Op1);
+ Ops.push_back(Op2);
+ return getAddExpr(Ops);
+ }
+ SCEVHandle getMulExpr(std::vector<SCEVHandle> &Ops);
+ SCEVHandle getMulExpr(const SCEVHandle &LHS, const SCEVHandle &RHS) {
+ std::vector<SCEVHandle> Ops;
+ Ops.push_back(LHS);
+ Ops.push_back(RHS);
+ return getMulExpr(Ops);
+ }
+ SCEVHandle getUDivExpr(const SCEVHandle &LHS, const SCEVHandle &RHS);
+ SCEVHandle getAddRecExpr(const SCEVHandle &Start, const SCEVHandle &Step,
+ const Loop *L);
+ SCEVHandle getAddRecExpr(std::vector<SCEVHandle> &Operands,
+ const Loop *L);
+ SCEVHandle getAddRecExpr(const std::vector<SCEVHandle> &Operands,
+ const Loop *L) {
+ std::vector<SCEVHandle> NewOp(Operands);
+ return getAddRecExpr(NewOp, L);
+ }
+ SCEVHandle getSMaxExpr(const SCEVHandle &LHS, const SCEVHandle &RHS);
+ SCEVHandle getSMaxExpr(std::vector<SCEVHandle> Operands);
+ SCEVHandle getUMaxExpr(const SCEVHandle &LHS, const SCEVHandle &RHS);
+ SCEVHandle getUMaxExpr(std::vector<SCEVHandle> Operands);
+ SCEVHandle getUnknown(Value *V);
+ SCEVHandle getCouldNotCompute();
+
+ /// getNegativeSCEV - Return the SCEV object corresponding to -V.
+ ///
+ SCEVHandle getNegativeSCEV(const SCEVHandle &V);
+
+ /// getNotSCEV - Return the SCEV object corresponding to ~V.
+ ///
+ SCEVHandle getNotSCEV(const SCEVHandle &V);
+
+ /// getMinusSCEV - Return LHS-RHS.
+ ///
+ SCEVHandle getMinusSCEV(const SCEVHandle &LHS,
+ const SCEVHandle &RHS);
+
+ /// getTruncateOrZeroExtend - Return a SCEV corresponding to a conversion
+ /// of the input value to the specified type. If the type must be
+ /// extended, it is zero extended.
+ SCEVHandle getTruncateOrZeroExtend(const SCEVHandle &V, const Type *Ty);
+
+ /// getTruncateOrSignExtend - Return a SCEV corresponding to a conversion
+ /// of the input value to the specified type. If the type must be
+ /// extended, it is sign extended.
+ SCEVHandle getTruncateOrSignExtend(const SCEVHandle &V, const Type *Ty);
+
+ /// getNoopOrZeroExtend - Return a SCEV corresponding to a conversion of
+ /// the input value to the specified type. If the type must be extended,
+ /// it is zero extended. The conversion must not be narrowing.
+ SCEVHandle getNoopOrZeroExtend(const SCEVHandle &V, const Type *Ty);
+
+ /// getNoopOrSignExtend - Return a SCEV corresponding to a conversion of
+ /// the input value to the specified type. If the type must be extended,
+ /// it is sign extended. The conversion must not be narrowing.
+ SCEVHandle getNoopOrSignExtend(const SCEVHandle &V, const Type *Ty);
+
+ /// getTruncateOrNoop - Return a SCEV corresponding to a conversion of the
+ /// input value to the specified type. The conversion must not be
+ /// widening.
+ SCEVHandle getTruncateOrNoop(const SCEVHandle &V, const Type *Ty);
+
+ /// getIntegerSCEV - Given an integer or FP type, create a constant for the
+ /// specified signed integer value and return a SCEV for the constant.
+ SCEVHandle getIntegerSCEV(int Val, const Type *Ty);
+
+ /// hasSCEV - Return true if the SCEV for this value has already been
+ /// computed.
+ bool hasSCEV(Value *V) const;
+
+ /// setSCEV - Insert the specified SCEV into the map of current SCEVs for
+ /// the specified value.
+ void setSCEV(Value *V, const SCEVHandle &H);
+
+ /// getSCEVAtScope - Return a SCEV expression handle for the specified value
+ /// at the specified scope in the program. The L value specifies a loop
+ /// nest to evaluate the expression at, where null is the top-level or a
+ /// specified loop is immediately inside of the loop.
+ ///
+ /// This method can be used to compute the exit value for a variable defined
+ /// in a loop by querying what the value will hold in the parent loop.
+ ///
+ /// In the case that a relevant loop exit value cannot be computed, the
+ /// original value V is returned.
+ SCEVHandle getSCEVAtScope(const SCEV *S, const Loop *L);
+
+ /// getSCEVAtScope - This is a convenience function which does
+ /// getSCEVAtScope(getSCEV(V), L).
+ SCEVHandle 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
+ /// expressions in loop trip counts.
+ bool isLoopGuardedByCond(const Loop *L, ICmpInst::Predicate Pred,
+ const SCEV *LHS, const SCEV *RHS);
+
+ /// getBackedgeTakenCount - If the specified loop has a predictable
+ /// backedge-taken count, return it, otherwise return a SCEVCouldNotCompute
+ /// object. The backedge-taken count is the number of times the loop header
+ /// will be branched to from within the loop. This is one less than the
+ /// trip count of the loop, since it doesn't count the first iteration,
+ /// when the header is branched to from outside the loop.
+ ///
+ /// Note that it is not valid to call this method on a loop without a
+ /// loop-invariant backedge-taken count (see
+ /// hasLoopInvariantBackedgeTakenCount).
+ ///
+ SCEVHandle getBackedgeTakenCount(const Loop *L);
+
+ /// getMaxBackedgeTakenCount - Similar to getBackedgeTakenCount, except
+ /// return the least SCEV value that is known never to be less than the
+ /// actual backedge taken count.
+ SCEVHandle getMaxBackedgeTakenCount(const Loop *L);
+
+ /// hasLoopInvariantBackedgeTakenCount - Return true if the specified loop
+ /// has an analyzable loop-invariant backedge-taken count.
+ bool hasLoopInvariantBackedgeTakenCount(const Loop *L);
+
+ /// forgetLoopBackedgeTakenCount - This method should be called by the
+ /// client when it has changed a loop in a way that may effect
+ /// ScalarEvolution's ability to compute a trip count, or if the loop
+ /// is deleted.
+ void forgetLoopBackedgeTakenCount(const Loop *L);
+
+ virtual bool runOnFunction(Function &F);
+ virtual void releaseMemory();
+ virtual void getAnalysisUsage(AnalysisUsage &AU) const;
+ void print(raw_ostream &OS, const Module* = 0) const;
+ virtual void print(std::ostream &OS, const Module* = 0) const;
+ void print(std::ostream *OS, const Module* M = 0) const {
+ if (OS) print(*OS, M);
+ }
+ };
+}
+
+#endif
diff --git a/include/llvm/Analysis/ScalarEvolutionExpander.h b/include/llvm/Analysis/ScalarEvolutionExpander.h
new file mode 100644
index 000000000000..7e0de47dc4f3
--- /dev/null
+++ b/include/llvm/Analysis/ScalarEvolutionExpander.h
@@ -0,0 +1,147 @@
+//===---- llvm/Analysis/ScalarEvolutionExpander.h - SCEV Exprs --*- 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 the classes used to generate code from scalar expressions.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ANALYSIS_SCALAREVOLUTION_EXPANDER_H
+#define LLVM_ANALYSIS_SCALAREVOLUTION_EXPANDER_H
+
+#include "llvm/Instructions.h"
+#include "llvm/Type.h"
+#include "llvm/Analysis/ScalarEvolution.h"
+#include "llvm/Analysis/ScalarEvolutionExpressions.h"
+
+namespace llvm {
+ /// SCEVExpander - This class uses information about analyze scalars to
+ /// rewrite expressions in canonical form.
+ ///
+ /// Clients should create an instance of this class when rewriting is needed,
+ /// and destroy it when finished to allow the release of the associated
+ /// memory.
+ struct SCEVExpander : public SCEVVisitor<SCEVExpander, Value*> {
+ ScalarEvolution &SE;
+ std::map<SCEVHandle, AssertingVH<Value> > InsertedExpressions;
+ std::set<Value*> InsertedValues;
+
+ BasicBlock::iterator InsertPt;
+
+ friend struct SCEVVisitor<SCEVExpander, Value*>;
+ public:
+ explicit SCEVExpander(ScalarEvolution &se)
+ : SE(se) {}
+
+ /// clear - Erase the contents of the InsertedExpressions map so that users
+ /// trying to expand the same expression into multiple BasicBlocks or
+ /// different places within the same BasicBlock can do so.
+ void clear() { InsertedExpressions.clear(); }
+
+ /// isInsertedInstruction - Return true if the specified instruction was
+ /// inserted by the code rewriter. If so, the client should not modify the
+ /// instruction.
+ bool isInsertedInstruction(Instruction *I) const {
+ return InsertedValues.count(I);
+ }
+
+ /// isInsertedExpression - Return true if the the code rewriter has a
+ /// Value* recorded for the given expression.
+ bool isInsertedExpression(const SCEV *S) const {
+ return InsertedExpressions.count(S);
+ }
+
+ /// getOrInsertCanonicalInductionVariable - This method returns the
+ /// canonical induction variable of the specified type for the specified
+ /// loop (inserting one if there is none). A canonical induction variable
+ /// starts at zero and steps by one on each iteration.
+ Value *getOrInsertCanonicalInductionVariable(const Loop *L, const Type *Ty){
+ assert(Ty->isInteger() && "Can only insert integer induction variables!");
+ SCEVHandle H = SE.getAddRecExpr(SE.getIntegerSCEV(0, Ty),
+ SE.getIntegerSCEV(1, Ty), L);
+ return expand(H);
+ }
+
+ /// addInsertedValue - Remember the specified instruction as being the
+ /// canonical form for the specified SCEV.
+ void addInsertedValue(Value *V, const SCEV *S) {
+ InsertedExpressions[S] = V;
+ InsertedValues.insert(V);
+ }
+
+ void setInsertionPoint(BasicBlock::iterator NewIP) { InsertPt = NewIP; }
+
+ BasicBlock::iterator getInsertionPoint() const { return InsertPt; }
+
+ /// expandCodeFor - Insert code to directly compute the specified SCEV
+ /// expression into the program. The inserted code is inserted into the
+ /// SCEVExpander's current insertion point. If a type is specified, the
+ /// result will be expanded to have that type, with a cast if necessary.
+ Value *expandCodeFor(SCEVHandle SH, const Type *Ty = 0);
+
+ /// expandCodeFor - Insert code to directly compute the specified SCEV
+ /// expression into the program. The inserted code is inserted into the
+ /// specified block.
+ Value *expandCodeFor(SCEVHandle SH, const Type *Ty,
+ BasicBlock::iterator IP) {
+ setInsertionPoint(IP);
+ return expandCodeFor(SH, Ty);
+ }
+
+ /// InsertCastOfTo - Insert a cast of V to the specified type, doing what
+ /// we can to share the casts.
+ Value *InsertCastOfTo(Instruction::CastOps opcode, Value *V,
+ const Type *Ty);
+
+ /// InsertNoopCastOfTo - Insert a cast of V to the specified type,
+ /// which must be possible with a noop cast.
+ Value *InsertNoopCastOfTo(Value *V, const Type *Ty);
+
+ /// InsertBinop - Insert the specified binary operator, doing a small amount
+ /// of work to avoid inserting an obviously redundant operation.
+ Value *InsertBinop(Instruction::BinaryOps Opcode, Value *LHS,
+ Value *RHS, BasicBlock::iterator InsertPt);
+
+ private:
+ /// expandAddToGEP - Expand a SCEVAddExpr with a pointer type into a GEP
+ /// instead of using ptrtoint+arithmetic+inttoptr.
+ Value *expandAddToGEP(const SCEVHandle *op_begin, const SCEVHandle *op_end,
+ const PointerType *PTy, const Type *Ty, Value *V);
+
+ Value *expand(const SCEV *S);
+
+ Value *visitConstant(const SCEVConstant *S) {
+ return S->getValue();
+ }
+
+ Value *visitTruncateExpr(const SCEVTruncateExpr *S);
+
+ Value *visitZeroExtendExpr(const SCEVZeroExtendExpr *S);
+
+ Value *visitSignExtendExpr(const SCEVSignExtendExpr *S);
+
+ Value *visitAddExpr(const SCEVAddExpr *S);
+
+ Value *visitMulExpr(const SCEVMulExpr *S);
+
+ Value *visitUDivExpr(const SCEVUDivExpr *S);
+
+ Value *visitAddRecExpr(const SCEVAddRecExpr *S);
+
+ Value *visitSMaxExpr(const SCEVSMaxExpr *S);
+
+ Value *visitUMaxExpr(const SCEVUMaxExpr *S);
+
+ Value *visitUnknown(const SCEVUnknown *S) {
+ return S->getValue();
+ }
+ };
+}
+
+#endif
+
diff --git a/include/llvm/Analysis/ScalarEvolutionExpressions.h b/include/llvm/Analysis/ScalarEvolutionExpressions.h
new file mode 100644
index 000000000000..264447ef86a2
--- /dev/null
+++ b/include/llvm/Analysis/ScalarEvolutionExpressions.h
@@ -0,0 +1,588 @@
+//===- llvm/Analysis/ScalarEvolutionExpressions.h - SCEV Exprs --*- 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 the classes used to represent and build scalar expressions.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ANALYSIS_SCALAREVOLUTION_EXPRESSIONS_H
+#define LLVM_ANALYSIS_SCALAREVOLUTION_EXPRESSIONS_H
+
+#include "llvm/Analysis/ScalarEvolution.h"
+
+namespace llvm {
+ class ConstantInt;
+ class ConstantRange;
+ class APInt;
+ class DominatorTree;
+
+ enum SCEVTypes {
+ // These should be ordered in terms of increasing complexity to make the
+ // folders simpler.
+ scConstant, scTruncate, scZeroExtend, scSignExtend, scAddExpr, scMulExpr,
+ scUDivExpr, scAddRecExpr, scUMaxExpr, scSMaxExpr, scUnknown,
+ scCouldNotCompute
+ };
+
+ //===--------------------------------------------------------------------===//
+ /// SCEVConstant - This class represents a constant integer value.
+ ///
+ class SCEVConstant : public SCEV {
+ friend class ScalarEvolution;
+
+ ConstantInt *V;
+ explicit SCEVConstant(ConstantInt *v) : SCEV(scConstant), V(v) {}
+
+ virtual ~SCEVConstant();
+ public:
+ ConstantInt *getValue() const { return V; }
+
+ virtual bool isLoopInvariant(const Loop *L) const {
+ return true;
+ }
+
+ virtual bool hasComputableLoopEvolution(const Loop *L) const {
+ return false; // Not loop variant
+ }
+
+ virtual const Type *getType() const;
+
+ SCEVHandle replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym,
+ const SCEVHandle &Conc,
+ ScalarEvolution &SE) const {
+ return this;
+ }
+
+ bool dominates(BasicBlock *BB, DominatorTree *DT) const {
+ return true;
+ }
+
+ virtual void print(raw_ostream &OS) const;
+
+ /// Methods for support type inquiry through isa, cast, and dyn_cast:
+ static inline bool classof(const SCEVConstant *S) { return true; }
+ static inline bool classof(const SCEV *S) {
+ return S->getSCEVType() == scConstant;
+ }
+ };
+
+ //===--------------------------------------------------------------------===//
+ /// SCEVCastExpr - This is the base class for unary cast operator classes.
+ ///
+ class SCEVCastExpr : public SCEV {
+ protected:
+ SCEVHandle Op;
+ const Type *Ty;
+
+ SCEVCastExpr(unsigned SCEVTy, const SCEVHandle &op, const Type *ty);
+ virtual ~SCEVCastExpr();
+
+ public:
+ const SCEVHandle &getOperand() const { return Op; }
+ virtual const Type *getType() const { return Ty; }
+
+ virtual bool isLoopInvariant(const Loop *L) const {
+ return Op->isLoopInvariant(L);
+ }
+
+ virtual bool hasComputableLoopEvolution(const Loop *L) const {
+ return Op->hasComputableLoopEvolution(L);
+ }
+
+ virtual bool dominates(BasicBlock *BB, DominatorTree *DT) const;
+
+ /// Methods for support type inquiry through isa, cast, and dyn_cast:
+ static inline bool classof(const SCEVCastExpr *S) { return true; }
+ static inline bool classof(const SCEV *S) {
+ return S->getSCEVType() == scTruncate ||
+ S->getSCEVType() == scZeroExtend ||
+ S->getSCEVType() == scSignExtend;
+ }
+ };
+
+ //===--------------------------------------------------------------------===//
+ /// SCEVTruncateExpr - This class represents a truncation of an integer value
+ /// to a smaller integer value.
+ ///
+ class SCEVTruncateExpr : public SCEVCastExpr {
+ friend class ScalarEvolution;
+
+ SCEVTruncateExpr(const SCEVHandle &op, const Type *ty);
+ virtual ~SCEVTruncateExpr();
+
+ public:
+ SCEVHandle replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym,
+ const SCEVHandle &Conc,
+ ScalarEvolution &SE) const {
+ SCEVHandle H = Op->replaceSymbolicValuesWithConcrete(Sym, Conc, SE);
+ if (H == Op)
+ return this;
+ return SE.getTruncateExpr(H, Ty);
+ }
+
+ virtual void print(raw_ostream &OS) const;
+
+ /// Methods for support type inquiry through isa, cast, and dyn_cast:
+ static inline bool classof(const SCEVTruncateExpr *S) { return true; }
+ static inline bool classof(const SCEV *S) {
+ return S->getSCEVType() == scTruncate;
+ }
+ };
+
+ //===--------------------------------------------------------------------===//
+ /// SCEVZeroExtendExpr - This class represents a zero extension of a small
+ /// integer value to a larger integer value.
+ ///
+ class SCEVZeroExtendExpr : public SCEVCastExpr {
+ friend class ScalarEvolution;
+
+ SCEVZeroExtendExpr(const SCEVHandle &op, const Type *ty);
+ virtual ~SCEVZeroExtendExpr();
+
+ public:
+ SCEVHandle replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym,
+ const SCEVHandle &Conc,
+ ScalarEvolution &SE) const {
+ SCEVHandle H = Op->replaceSymbolicValuesWithConcrete(Sym, Conc, SE);
+ if (H == Op)
+ return this;
+ return SE.getZeroExtendExpr(H, Ty);
+ }
+
+ virtual void print(raw_ostream &OS) const;
+
+ /// Methods for support type inquiry through isa, cast, and dyn_cast:
+ static inline bool classof(const SCEVZeroExtendExpr *S) { return true; }
+ static inline bool classof(const SCEV *S) {
+ return S->getSCEVType() == scZeroExtend;
+ }
+ };
+
+ //===--------------------------------------------------------------------===//
+ /// SCEVSignExtendExpr - This class represents a sign extension of a small
+ /// integer value to a larger integer value.
+ ///
+ class SCEVSignExtendExpr : public SCEVCastExpr {
+ friend class ScalarEvolution;
+
+ SCEVSignExtendExpr(const SCEVHandle &op, const Type *ty);
+ virtual ~SCEVSignExtendExpr();
+
+ public:
+ SCEVHandle replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym,
+ const SCEVHandle &Conc,
+ ScalarEvolution &SE) const {
+ SCEVHandle H = Op->replaceSymbolicValuesWithConcrete(Sym, Conc, SE);
+ if (H == Op)
+ return this;
+ return SE.getSignExtendExpr(H, Ty);
+ }
+
+ virtual void print(raw_ostream &OS) const;
+
+ /// Methods for support type inquiry through isa, cast, and dyn_cast:
+ static inline bool classof(const SCEVSignExtendExpr *S) { return true; }
+ static inline bool classof(const SCEV *S) {
+ return S->getSCEVType() == scSignExtend;
+ }
+ };
+
+
+ //===--------------------------------------------------------------------===//
+ /// SCEVNAryExpr - This node is a base class providing common
+ /// functionality for n'ary operators.
+ ///
+ class SCEVNAryExpr : public SCEV {
+ protected:
+ std::vector<SCEVHandle> Operands;
+
+ SCEVNAryExpr(enum SCEVTypes T, const std::vector<SCEVHandle> &ops)
+ : SCEV(T), Operands(ops) {}
+ virtual ~SCEVNAryExpr() {}
+
+ public:
+ unsigned getNumOperands() const { return (unsigned)Operands.size(); }
+ const SCEVHandle &getOperand(unsigned i) const {
+ assert(i < Operands.size() && "Operand index out of range!");
+ return Operands[i];
+ }
+
+ const std::vector<SCEVHandle> &getOperands() const { return Operands; }
+ typedef std::vector<SCEVHandle>::const_iterator op_iterator;
+ op_iterator op_begin() const { return Operands.begin(); }
+ op_iterator op_end() const { return Operands.end(); }
+
+ virtual bool isLoopInvariant(const Loop *L) const {
+ for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
+ if (!getOperand(i)->isLoopInvariant(L)) return false;
+ return true;
+ }
+
+ // hasComputableLoopEvolution - N-ary expressions have computable loop
+ // evolutions iff they have at least one operand that varies with the loop,
+ // but that all varying operands are computable.
+ virtual bool hasComputableLoopEvolution(const Loop *L) const {
+ bool HasVarying = false;
+ for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
+ if (!getOperand(i)->isLoopInvariant(L)) {
+ if (getOperand(i)->hasComputableLoopEvolution(L))
+ HasVarying = true;
+ else
+ return false;
+ }
+ return HasVarying;
+ }
+
+ bool dominates(BasicBlock *BB, DominatorTree *DT) const;
+
+ virtual const Type *getType() const { return getOperand(0)->getType(); }
+
+ /// Methods for support type inquiry through isa, cast, and dyn_cast:
+ static inline bool classof(const SCEVNAryExpr *S) { return true; }
+ static inline bool classof(const SCEV *S) {
+ return S->getSCEVType() == scAddExpr ||
+ S->getSCEVType() == scMulExpr ||
+ S->getSCEVType() == scSMaxExpr ||
+ S->getSCEVType() == scUMaxExpr ||
+ S->getSCEVType() == scAddRecExpr;
+ }
+ };
+
+ //===--------------------------------------------------------------------===//
+ /// SCEVCommutativeExpr - This node is the base class for n'ary commutative
+ /// operators.
+ ///
+ class SCEVCommutativeExpr : public SCEVNAryExpr {
+ protected:
+ SCEVCommutativeExpr(enum SCEVTypes T, const std::vector<SCEVHandle> &ops)
+ : SCEVNAryExpr(T, ops) {}
+ ~SCEVCommutativeExpr();
+
+ public:
+ SCEVHandle replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym,
+ const SCEVHandle &Conc,
+ ScalarEvolution &SE) const;
+
+ virtual const char *getOperationStr() const = 0;
+
+ virtual void print(raw_ostream &OS) const;
+
+ /// Methods for support type inquiry through isa, cast, and dyn_cast:
+ static inline bool classof(const SCEVCommutativeExpr *S) { return true; }
+ static inline bool classof(const SCEV *S) {
+ return S->getSCEVType() == scAddExpr ||
+ S->getSCEVType() == scMulExpr ||
+ S->getSCEVType() == scSMaxExpr ||
+ S->getSCEVType() == scUMaxExpr;
+ }
+ };
+
+
+ //===--------------------------------------------------------------------===//
+ /// SCEVAddExpr - This node represents an addition of some number of SCEVs.
+ ///
+ class SCEVAddExpr : public SCEVCommutativeExpr {
+ friend class ScalarEvolution;
+
+ explicit SCEVAddExpr(const std::vector<SCEVHandle> &ops)
+ : SCEVCommutativeExpr(scAddExpr, ops) {
+ }
+
+ public:
+ virtual const char *getOperationStr() const { return " + "; }
+
+ /// Methods for support type inquiry through isa, cast, and dyn_cast:
+ static inline bool classof(const SCEVAddExpr *S) { return true; }
+ static inline bool classof(const SCEV *S) {
+ return S->getSCEVType() == scAddExpr;
+ }
+ };
+
+ //===--------------------------------------------------------------------===//
+ /// SCEVMulExpr - This node represents multiplication of some number of SCEVs.
+ ///
+ class SCEVMulExpr : public SCEVCommutativeExpr {
+ friend class ScalarEvolution;
+
+ explicit SCEVMulExpr(const std::vector<SCEVHandle> &ops)
+ : SCEVCommutativeExpr(scMulExpr, ops) {
+ }
+
+ public:
+ virtual const char *getOperationStr() const { return " * "; }
+
+ /// Methods for support type inquiry through isa, cast, and dyn_cast:
+ static inline bool classof(const SCEVMulExpr *S) { return true; }
+ static inline bool classof(const SCEV *S) {
+ return S->getSCEVType() == scMulExpr;
+ }
+ };
+
+
+ //===--------------------------------------------------------------------===//
+ /// SCEVUDivExpr - This class represents a binary unsigned division operation.
+ ///
+ class SCEVUDivExpr : public SCEV {
+ friend class ScalarEvolution;
+
+ SCEVHandle LHS, RHS;
+ SCEVUDivExpr(const SCEVHandle &lhs, const SCEVHandle &rhs)
+ : SCEV(scUDivExpr), LHS(lhs), RHS(rhs) {}
+
+ virtual ~SCEVUDivExpr();
+ public:
+ const SCEVHandle &getLHS() const { return LHS; }
+ const SCEVHandle &getRHS() const { return RHS; }
+
+ virtual bool isLoopInvariant(const Loop *L) const {
+ return LHS->isLoopInvariant(L) && RHS->isLoopInvariant(L);
+ }
+
+ virtual bool hasComputableLoopEvolution(const Loop *L) const {
+ return LHS->hasComputableLoopEvolution(L) &&
+ RHS->hasComputableLoopEvolution(L);
+ }
+
+ SCEVHandle replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym,
+ const SCEVHandle &Conc,
+ ScalarEvolution &SE) const {
+ SCEVHandle L = LHS->replaceSymbolicValuesWithConcrete(Sym, Conc, SE);
+ SCEVHandle R = RHS->replaceSymbolicValuesWithConcrete(Sym, Conc, SE);
+ if (L == LHS && R == RHS)
+ return this;
+ else
+ return SE.getUDivExpr(L, R);
+ }
+
+ bool dominates(BasicBlock *BB, DominatorTree *DT) const;
+
+ virtual const Type *getType() const;
+
+ void print(raw_ostream &OS) const;
+
+ /// Methods for support type inquiry through isa, cast, and dyn_cast:
+ static inline bool classof(const SCEVUDivExpr *S) { return true; }
+ static inline bool classof(const SCEV *S) {
+ return S->getSCEVType() == scUDivExpr;
+ }
+ };
+
+
+ //===--------------------------------------------------------------------===//
+ /// SCEVAddRecExpr - This node represents a polynomial recurrence on the trip
+ /// count of the specified loop. This is the primary focus of the
+ /// ScalarEvolution framework; all the other SCEV subclasses are mostly just
+ /// supporting infrastructure to allow SCEVAddRecExpr expressions to be
+ /// created and analyzed.
+ ///
+ /// All operands of an AddRec are required to be loop invariant.
+ ///
+ class SCEVAddRecExpr : public SCEVNAryExpr {
+ friend class ScalarEvolution;
+
+ const Loop *L;
+
+ SCEVAddRecExpr(const std::vector<SCEVHandle> &ops, const Loop *l)
+ : SCEVNAryExpr(scAddRecExpr, ops), L(l) {
+ for (size_t i = 0, e = Operands.size(); i != e; ++i)
+ assert(Operands[i]->isLoopInvariant(l) &&
+ "Operands of AddRec must be loop-invariant!");
+ }
+ ~SCEVAddRecExpr();
+
+ public:
+ const SCEVHandle &getStart() const { return Operands[0]; }
+ const Loop *getLoop() const { return L; }
+
+ /// getStepRecurrence - This method constructs and returns the recurrence
+ /// indicating how much this expression steps by. If this is a polynomial
+ /// of degree N, it returns a chrec of degree N-1.
+ SCEVHandle getStepRecurrence(ScalarEvolution &SE) const {
+ if (isAffine()) return getOperand(1);
+ return SE.getAddRecExpr(std::vector<SCEVHandle>(op_begin()+1,op_end()),
+ getLoop());
+ }
+
+ virtual bool hasComputableLoopEvolution(const Loop *QL) const {
+ if (L == QL) return true;
+ return false;
+ }
+
+ virtual bool isLoopInvariant(const Loop *QueryLoop) const;
+
+ /// isAffine - Return true if this is an affine AddRec (i.e., it represents
+ /// an expressions A+B*x where A and B are loop invariant values.
+ bool isAffine() const {
+ // We know that the start value is invariant. This expression is thus
+ // affine iff the step is also invariant.
+ return getNumOperands() == 2;
+ }
+
+ /// isQuadratic - Return true if this is an quadratic AddRec (i.e., it
+ /// represents an expressions A+B*x+C*x^2 where A, B and C are loop
+ /// invariant values. This corresponds to an addrec of the form {L,+,M,+,N}
+ bool isQuadratic() const {
+ return getNumOperands() == 3;
+ }
+
+ /// evaluateAtIteration - Return the value of this chain of recurrences at
+ /// the specified iteration number.
+ SCEVHandle evaluateAtIteration(SCEVHandle It, ScalarEvolution &SE) const;
+
+ /// getNumIterationsInRange - Return the number of iterations of this loop
+ /// that produce values in the specified constant range. Another way of
+ /// looking at this is that it returns the first iteration number where the
+ /// value is not in the condition, thus computing the exit count. If the
+ /// iteration count can't be computed, an instance of SCEVCouldNotCompute is
+ /// returned.
+ SCEVHandle getNumIterationsInRange(ConstantRange Range,
+ ScalarEvolution &SE) const;
+
+ SCEVHandle replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym,
+ const SCEVHandle &Conc,
+ ScalarEvolution &SE) const;
+
+ virtual void print(raw_ostream &OS) const;
+
+ /// Methods for support type inquiry through isa, cast, and dyn_cast:
+ static inline bool classof(const SCEVAddRecExpr *S) { return true; }
+ static inline bool classof(const SCEV *S) {
+ return S->getSCEVType() == scAddRecExpr;
+ }
+ };
+
+
+ //===--------------------------------------------------------------------===//
+ /// SCEVSMaxExpr - This class represents a signed maximum selection.
+ ///
+ class SCEVSMaxExpr : public SCEVCommutativeExpr {
+ friend class ScalarEvolution;
+
+ explicit SCEVSMaxExpr(const std::vector<SCEVHandle> &ops)
+ : SCEVCommutativeExpr(scSMaxExpr, ops) {
+ }
+
+ public:
+ virtual const char *getOperationStr() const { return " smax "; }
+
+ /// Methods for support type inquiry through isa, cast, and dyn_cast:
+ static inline bool classof(const SCEVSMaxExpr *S) { return true; }
+ static inline bool classof(const SCEV *S) {
+ return S->getSCEVType() == scSMaxExpr;
+ }
+ };
+
+
+ //===--------------------------------------------------------------------===//
+ /// SCEVUMaxExpr - This class represents an unsigned maximum selection.
+ ///
+ class SCEVUMaxExpr : public SCEVCommutativeExpr {
+ friend class ScalarEvolution;
+
+ explicit SCEVUMaxExpr(const std::vector<SCEVHandle> &ops)
+ : SCEVCommutativeExpr(scUMaxExpr, ops) {
+ }
+
+ public:
+ virtual const char *getOperationStr() const { return " umax "; }
+
+ /// Methods for support type inquiry through isa, cast, and dyn_cast:
+ static inline bool classof(const SCEVUMaxExpr *S) { return true; }
+ static inline bool classof(const SCEV *S) {
+ return S->getSCEVType() == scUMaxExpr;
+ }
+ };
+
+
+ //===--------------------------------------------------------------------===//
+ /// SCEVUnknown - This means that we are dealing with an entirely unknown SCEV
+ /// value, and only represent it as it's LLVM Value. This is the "bottom"
+ /// value for the analysis.
+ ///
+ class SCEVUnknown : public SCEV {
+ friend class ScalarEvolution;
+
+ Value *V;
+ explicit SCEVUnknown(Value *v) : SCEV(scUnknown), V(v) {}
+
+ protected:
+ ~SCEVUnknown();
+ public:
+ Value *getValue() const { return V; }
+
+ virtual bool isLoopInvariant(const Loop *L) const;
+ virtual bool hasComputableLoopEvolution(const Loop *QL) const {
+ return false; // not computable
+ }
+
+ SCEVHandle replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym,
+ const SCEVHandle &Conc,
+ ScalarEvolution &SE) const {
+ if (&*Sym == this) return Conc;
+ return this;
+ }
+
+ bool dominates(BasicBlock *BB, DominatorTree *DT) const;
+
+ virtual const Type *getType() const;
+
+ virtual void print(raw_ostream &OS) const;
+
+ /// Methods for support type inquiry through isa, cast, and dyn_cast:
+ static inline bool classof(const SCEVUnknown *S) { return true; }
+ static inline bool classof(const SCEV *S) {
+ return S->getSCEVType() == scUnknown;
+ }
+ };
+
+ /// SCEVVisitor - This class defines a simple visitor class that may be used
+ /// for various SCEV analysis purposes.
+ template<typename SC, typename RetVal=void>
+ struct SCEVVisitor {
+ RetVal visit(const SCEV *S) {
+ switch (S->getSCEVType()) {
+ case scConstant:
+ return ((SC*)this)->visitConstant((const SCEVConstant*)S);
+ case scTruncate:
+ return ((SC*)this)->visitTruncateExpr((const SCEVTruncateExpr*)S);
+ case scZeroExtend:
+ return ((SC*)this)->visitZeroExtendExpr((const SCEVZeroExtendExpr*)S);
+ case scSignExtend:
+ return ((SC*)this)->visitSignExtendExpr((const SCEVSignExtendExpr*)S);
+ case scAddExpr:
+ return ((SC*)this)->visitAddExpr((const SCEVAddExpr*)S);
+ case scMulExpr:
+ return ((SC*)this)->visitMulExpr((const SCEVMulExpr*)S);
+ case scUDivExpr:
+ return ((SC*)this)->visitUDivExpr((const SCEVUDivExpr*)S);
+ case scAddRecExpr:
+ return ((SC*)this)->visitAddRecExpr((const SCEVAddRecExpr*)S);
+ case scSMaxExpr:
+ return ((SC*)this)->visitSMaxExpr((const SCEVSMaxExpr*)S);
+ case scUMaxExpr:
+ return ((SC*)this)->visitUMaxExpr((const SCEVUMaxExpr*)S);
+ case scUnknown:
+ return ((SC*)this)->visitUnknown((const SCEVUnknown*)S);
+ case scCouldNotCompute:
+ return ((SC*)this)->visitCouldNotCompute((const SCEVCouldNotCompute*)S);
+ default:
+ assert(0 && "Unknown SCEV type!");
+ abort();
+ }
+ }
+
+ RetVal visitCouldNotCompute(const SCEVCouldNotCompute *S) {
+ assert(0 && "Invalid use of SCEVCouldNotCompute!");
+ abort();
+ return RetVal();
+ }
+ };
+}
+
+#endif
diff --git a/include/llvm/Analysis/SparsePropagation.h b/include/llvm/Analysis/SparsePropagation.h
new file mode 100644
index 000000000000..c75531a7e6e0
--- /dev/null
+++ b/include/llvm/Analysis/SparsePropagation.h
@@ -0,0 +1,200 @@
+//===- SparsePropagation.h - Sparse Conditional Property Propagation ------===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file implements an abstract sparse conditional propagation algorithm,
+// modeled after SCCP, but with a customizable lattice function.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ANALYSIS_SPARSE_PROPAGATION_H
+#define LLVM_ANALYSIS_SPARSE_PROPAGATION_H
+
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/SmallPtrSet.h"
+#include <iosfwd>
+#include <vector>
+#include <set>
+
+namespace llvm {
+ class Value;
+ class Constant;
+ class Argument;
+ class Instruction;
+ class PHINode;
+ class TerminatorInst;
+ class BasicBlock;
+ class Function;
+ class SparseSolver;
+
+ template<typename T> class SmallVectorImpl;
+
+/// AbstractLatticeFunction - This class is implemented by the dataflow instance
+/// to specify what the lattice values are and how they handle merges etc.
+/// This gives the client the power to compute lattice values from instructions,
+/// constants, etc. The requirement is that lattice values must all fit into
+/// a void*. If a void* is not sufficient, the implementation should use this
+/// pointer to be a pointer into a uniquing set or something.
+///
+class AbstractLatticeFunction {
+public:
+ typedef void *LatticeVal;
+private:
+ LatticeVal UndefVal, OverdefinedVal, UntrackedVal;
+public:
+ AbstractLatticeFunction(LatticeVal undefVal, LatticeVal overdefinedVal,
+ LatticeVal untrackedVal) {
+ UndefVal = undefVal;
+ OverdefinedVal = overdefinedVal;
+ UntrackedVal = untrackedVal;
+ }
+ virtual ~AbstractLatticeFunction();
+
+ LatticeVal getUndefVal() const { return UndefVal; }
+ LatticeVal getOverdefinedVal() const { return OverdefinedVal; }
+ LatticeVal getUntrackedVal() const { return UntrackedVal; }
+
+ /// IsUntrackedValue - If the specified Value is something that is obviously
+ /// uninteresting to the analysis (and would always return UntrackedVal),
+ /// this function can return true to avoid pointless work.
+ virtual bool IsUntrackedValue(Value *V) {
+ return false;
+ }
+
+ /// ComputeConstant - Given a constant value, compute and return a lattice
+ /// value corresponding to the specified constant.
+ virtual LatticeVal ComputeConstant(Constant *C) {
+ return getOverdefinedVal(); // always safe
+ }
+
+ /// GetConstant - If the specified lattice value is representable as an LLVM
+ /// constant value, return it. Otherwise return null. The returned value
+ /// must be in the same LLVM type as Val.
+ virtual Constant *GetConstant(LatticeVal LV, Value *Val, SparseSolver &SS) {
+ return 0;
+ }
+
+ /// ComputeArgument - Given a formal argument value, compute and return a
+ /// lattice value corresponding to the specified argument.
+ virtual LatticeVal ComputeArgument(Argument *I) {
+ return getOverdefinedVal(); // always safe
+ }
+
+ /// MergeValues - Compute and return the merge of the two specified lattice
+ /// values. Merging should only move one direction down the lattice to
+ /// guarantee convergence (toward overdefined).
+ virtual LatticeVal MergeValues(LatticeVal X, LatticeVal Y) {
+ return getOverdefinedVal(); // always safe, never useful.
+ }
+
+ /// ComputeInstructionState - Given an instruction and a vector of its operand
+ /// values, compute the result value of the instruction.
+ virtual LatticeVal ComputeInstructionState(Instruction &I, SparseSolver &SS) {
+ return getOverdefinedVal(); // always safe, never useful.
+ }
+
+ /// PrintValue - Render the specified lattice value to the specified stream.
+ virtual void PrintValue(LatticeVal V, std::ostream &OS);
+};
+
+
+/// SparseSolver - This class is a general purpose solver for Sparse Conditional
+/// Propagation with a programmable lattice function.
+///
+class SparseSolver {
+ typedef AbstractLatticeFunction::LatticeVal LatticeVal;
+
+ /// LatticeFunc - This is the object that knows the lattice and how to do
+ /// compute transfer functions.
+ AbstractLatticeFunction *LatticeFunc;
+
+ DenseMap<Value*, LatticeVal> ValueState; // The state each value is in.
+ SmallPtrSet<BasicBlock*, 16> BBExecutable; // The bbs that are executable.
+
+ std::vector<Instruction*> InstWorkList; // Worklist of insts to process.
+
+ std::vector<BasicBlock*> BBWorkList; // The BasicBlock work list
+
+ /// KnownFeasibleEdges - Entries in this set are edges which have already had
+ /// PHI nodes retriggered.
+ typedef std::pair<BasicBlock*,BasicBlock*> Edge;
+ std::set<Edge> KnownFeasibleEdges;
+
+ SparseSolver(const SparseSolver&); // DO NOT IMPLEMENT
+ void operator=(const SparseSolver&); // DO NOT IMPLEMENT
+public:
+ explicit SparseSolver(AbstractLatticeFunction *Lattice)
+ : LatticeFunc(Lattice) {}
+ ~SparseSolver() {
+ delete LatticeFunc;
+ }
+
+ /// Solve - Solve for constants and executable blocks.
+ ///
+ void Solve(Function &F);
+
+ void Print(Function &F, std::ostream &OS) const;
+
+ /// getLatticeState - Return the LatticeVal object that corresponds to the
+ /// value. If an value is not in the map, it is returned as untracked,
+ /// unlike the getOrInitValueState method.
+ LatticeVal getLatticeState(Value *V) const {
+ DenseMap<Value*, LatticeVal>::iterator I = ValueState.find(V);
+ return I != ValueState.end() ? I->second : LatticeFunc->getUntrackedVal();
+ }
+
+ /// getOrInitValueState - Return the LatticeVal object that corresponds to the
+ /// value, initializing the value's state if it hasn't been entered into the
+ /// map yet. This function is necessary because not all values should start
+ /// out in the underdefined state... Arguments should be overdefined, and
+ /// constants should be marked as constants.
+ ///
+ LatticeVal getOrInitValueState(Value *V);
+
+ /// isEdgeFeasible - Return true if the control flow edge from the 'From'
+ /// basic block to the 'To' basic block is currently feasible. If
+ /// AggressiveUndef is true, then this treats values with unknown lattice
+ /// values as undefined. This is generally only useful when solving the
+ /// lattice, not when querying it.
+ bool isEdgeFeasible(BasicBlock *From, BasicBlock *To,
+ bool AggressiveUndef = false);
+
+ /// isBlockExecutable - Return true if there are any known feasible
+ /// edges into the basic block. This is generally only useful when
+ /// querying the lattice.
+ bool isBlockExecutable(BasicBlock *BB) const {
+ return BBExecutable.count(BB);
+ }
+
+private:
+ /// UpdateState - When the state for some instruction is potentially updated,
+ /// this function notices and adds I to the worklist if needed.
+ void UpdateState(Instruction &Inst, LatticeVal V);
+
+ /// MarkBlockExecutable - This method can be used by clients to mark all of
+ /// the blocks that are known to be intrinsically live in the processed unit.
+ void MarkBlockExecutable(BasicBlock *BB);
+
+ /// markEdgeExecutable - Mark a basic block as executable, adding it to the BB
+ /// work list if it is not already executable.
+ void markEdgeExecutable(BasicBlock *Source, BasicBlock *Dest);
+
+ /// getFeasibleSuccessors - Return a vector of booleans to indicate which
+ /// successors are reachable from a given terminator instruction.
+ void getFeasibleSuccessors(TerminatorInst &TI, SmallVectorImpl<bool> &Succs,
+ bool AggressiveUndef);
+
+ void visitInst(Instruction &I);
+ void visitPHINode(PHINode &I);
+ void visitTerminatorInst(TerminatorInst &TI);
+
+};
+
+} // end namespace llvm
+
+#endif // LLVM_ANALYSIS_SPARSE_PROPAGATION_H
diff --git a/include/llvm/Analysis/Trace.h b/include/llvm/Analysis/Trace.h
new file mode 100644
index 000000000000..fd615fcdae08
--- /dev/null
+++ b/include/llvm/Analysis/Trace.h
@@ -0,0 +1,120 @@
+//===- llvm/Analysis/Trace.h - Represent one trace of LLVM code -*- C++ -*-===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This class represents a single trace of LLVM basic blocks. A trace is a
+// single entry, multiple exit, region of code that is often hot. Trace-based
+// optimizations treat traces almost like they are a large, strange, basic
+// block: because the trace path is assumed to be hot, optimizations for the
+// fall-through path are made at the expense of the non-fall-through paths.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ANALYSIS_TRACE_H
+#define LLVM_ANALYSIS_TRACE_H
+
+#include "llvm/Support/Streams.h"
+#include <vector>
+#include <cassert>
+
+namespace llvm {
+ class BasicBlock;
+ class Function;
+ class Module;
+
+class Trace {
+ typedef std::vector<BasicBlock *> BasicBlockListType;
+ BasicBlockListType BasicBlocks;
+
+public:
+ /// Trace ctor - Make a new trace from a vector of basic blocks,
+ /// residing in the function which is the parent of the first
+ /// basic block in the vector.
+ ///
+ Trace(const std::vector<BasicBlock *> &vBB) : BasicBlocks (vBB) {}
+
+ /// getEntryBasicBlock - Return the entry basic block (first block)
+ /// of the trace.
+ ///
+ BasicBlock *getEntryBasicBlock () const { return BasicBlocks[0]; }
+
+ /// operator[]/getBlock - Return basic block N in the trace.
+ ///
+ BasicBlock *operator[](unsigned i) const { return BasicBlocks[i]; }
+ BasicBlock *getBlock(unsigned i) const { return BasicBlocks[i]; }
+
+ /// getFunction - Return this trace's parent function.
+ ///
+ Function *getFunction () const;
+
+ /// getModule - Return this Module that contains this trace's parent
+ /// function.
+ ///
+ Module *getModule () const;
+
+ /// getBlockIndex - Return the index of the specified basic block in the
+ /// trace, or -1 if it is not in the trace.
+ int getBlockIndex(const BasicBlock *X) const {
+ for (unsigned i = 0, e = BasicBlocks.size(); i != e; ++i)
+ if (BasicBlocks[i] == X)
+ return i;
+ return -1;
+ }
+
+ /// contains - Returns true if this trace contains the given basic
+ /// block.
+ ///
+ bool contains(const BasicBlock *X) const {
+ return getBlockIndex(X) != -1;
+ }
+
+ /// Returns true if B1 occurs before B2 in the trace, or if it is the same
+ /// block as B2.. Both blocks must be in the trace.
+ ///
+ bool dominates(const BasicBlock *B1, const BasicBlock *B2) const {
+ int B1Idx = getBlockIndex(B1), B2Idx = getBlockIndex(B2);
+ assert(B1Idx != -1 && B2Idx != -1 && "Block is not in the trace!");
+ return B1Idx <= B2Idx;
+ }
+
+ // BasicBlock iterators...
+ typedef BasicBlockListType::iterator iterator;
+ typedef BasicBlockListType::const_iterator const_iterator;
+ typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
+ typedef std::reverse_iterator<iterator> reverse_iterator;
+
+ iterator begin() { return BasicBlocks.begin(); }
+ const_iterator begin() const { return BasicBlocks.begin(); }
+ iterator end () { return BasicBlocks.end(); }
+ const_iterator end () const { return BasicBlocks.end(); }
+
+ reverse_iterator rbegin() { return BasicBlocks.rbegin(); }
+ const_reverse_iterator rbegin() const { return BasicBlocks.rbegin(); }
+ reverse_iterator rend () { return BasicBlocks.rend(); }
+ const_reverse_iterator rend () const { return BasicBlocks.rend(); }
+
+ unsigned size() const { return BasicBlocks.size(); }
+ bool empty() const { return BasicBlocks.empty(); }
+
+ iterator erase(iterator q) { return BasicBlocks.erase (q); }
+ iterator erase(iterator q1, iterator q2) { return BasicBlocks.erase (q1, q2); }
+
+ /// print - Write trace to output stream.
+ ///
+ void print (std::ostream &O) const;
+ void print (std::ostream *O) const { if (O) print(*O); }
+
+ /// dump - Debugger convenience method; writes trace to standard error
+ /// output stream.
+ ///
+ void dump () const;
+};
+
+} // end namespace llvm
+
+#endif // TRACE_H
diff --git a/include/llvm/Analysis/ValueTracking.h b/include/llvm/Analysis/ValueTracking.h
new file mode 100644
index 000000000000..5f5f77a5c9fe
--- /dev/null
+++ b/include/llvm/Analysis/ValueTracking.h
@@ -0,0 +1,87 @@
+//===- llvm/Analysis/ValueTracking.h - Walk computations --------*- C++ -*-===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file contains routines that help analyze properties that chains of
+// computations have.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ANALYSIS_VALUETRACKING_H
+#define LLVM_ANALYSIS_VALUETRACKING_H
+
+#include "llvm/Support/DataTypes.h"
+#include <string>
+
+namespace llvm {
+ class Value;
+ class Instruction;
+ class APInt;
+ class TargetData;
+
+ /// ComputeMaskedBits - Determine which of the bits specified in Mask are
+ /// known to be either zero or one and return them in the KnownZero/KnownOne
+ /// bit sets. This code only analyzes bits in Mask, in order to short-circuit
+ /// processing.
+ void ComputeMaskedBits(Value *V, const APInt &Mask, APInt &KnownZero,
+ APInt &KnownOne, TargetData *TD = 0,
+ unsigned Depth = 0);
+
+ /// MaskedValueIsZero - Return true if 'V & Mask' is known to be zero. We use
+ /// this predicate to simplify operations downstream. Mask is known to be
+ /// zero for bits that V cannot have.
+ bool MaskedValueIsZero(Value *V, const APInt &Mask,
+ TargetData *TD = 0, unsigned Depth = 0);
+
+
+ /// ComputeNumSignBits - Return the number of times the sign bit of the
+ /// register is replicated into the other bits. We know that at least 1 bit
+ /// is always equal to the sign bit (itself), but other cases can give us
+ /// information. For example, immediately after an "ashr X, 2", we know that
+ /// the top 3 bits are all equal to each other, so we return 3.
+ ///
+ /// 'Op' must have a scalar integer type.
+ ///
+ unsigned ComputeNumSignBits(Value *Op, TargetData *TD = 0,
+ unsigned Depth = 0);
+
+ /// CannotBeNegativeZero - Return true if we can prove that the specified FP
+ /// value is never equal to -0.0.
+ ///
+ bool CannotBeNegativeZero(const Value *V, unsigned Depth = 0);
+
+ /// FindScalarValue - Given an aggregrate and an sequence of indices, see if
+ /// the scalar value indexed is already around as a register, for example if
+ /// it were inserted directly into the aggregrate.
+ ///
+ /// If InsertBefore is not null, this function will duplicate (modified)
+ /// insertvalues when a part of a nested struct is extracted.
+ Value *FindInsertedValue(Value *V,
+ const unsigned *idx_begin,
+ const unsigned *idx_end,
+ Instruction *InsertBefore = 0);
+
+ /// This is a convenience wrapper for finding values indexed by a single index
+ /// only.
+ inline Value *FindInsertedValue(Value *V, const unsigned Idx,
+ Instruction *InsertBefore = 0) {
+ const unsigned Idxs[1] = { Idx };
+ return FindInsertedValue(V, &Idxs[0], &Idxs[1], InsertBefore);
+ }
+
+ /// GetConstantStringInfo - This function computes the length of a
+ /// null-terminated C string pointed to by V. If successful, it returns true
+ /// and returns the string in Str. If unsuccessful, it returns false. If
+ /// 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 StopAtNul = true);
+} // end namespace llvm
+
+#endif
diff --git a/include/llvm/Analysis/Verifier.h b/include/llvm/Analysis/Verifier.h
new file mode 100644
index 000000000000..a6b2a6df21af
--- /dev/null
+++ b/include/llvm/Analysis/Verifier.h
@@ -0,0 +1,75 @@
+//===-- llvm/Analysis/Verifier.h - Module Verifier --------------*- 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 the function verifier interface, that can be used for some
+// sanity checking of input to the system, and for checking that transformations
+// haven't done something bad.
+//
+// Note that this does not provide full 'java style' security and verifications,
+// instead it just tries to ensure that code is well formed.
+//
+// To see what specifically is checked, look at the top of Verifier.cpp
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ANALYSIS_VERIFIER_H
+#define LLVM_ANALYSIS_VERIFIER_H
+
+#include <string>
+
+namespace llvm {
+
+class FunctionPass;
+class Module;
+class Function;
+
+/// @brief An enumeration to specify the action to be taken if errors found.
+///
+/// This enumeration is used in the functions below to indicate what should
+/// happen if the verifier finds errors. Each of the functions that uses
+/// this enumeration as an argument provides a default value for it. The
+/// actions are listed below.
+enum VerifierFailureAction {
+ AbortProcessAction, ///< verifyModule will print to stderr and abort()
+ PrintMessageAction, ///< verifyModule will print to stderr and return true
+ ReturnStatusAction ///< verifyModule will just return true
+};
+
+/// @brief Create a verifier pass.
+///
+/// Check a module or function for validity. When the pass is used, the
+/// action indicated by the \p action argument will be used if errors are
+/// found.
+FunctionPass *createVerifierPass(
+ VerifierFailureAction action = AbortProcessAction ///< Action to take
+);
+
+/// @brief Check a module for errors.
+///
+/// If there are no errors, the function returns false. If an error is found,
+/// the action taken depends on the \p action parameter.
+/// This should only be used for debugging, because it plays games with
+/// PassManagers and stuff.
+
+bool verifyModule(
+ const Module &M, ///< The module to be verified
+ VerifierFailureAction action = AbortProcessAction, ///< Action to take
+ std::string *ErrorInfo = 0 ///< Information about failures.
+);
+
+// verifyFunction - Check a function for errors, useful for use when debugging a
+// pass.
+bool verifyFunction(
+ const Function &F, ///< The function to be verified
+ VerifierFailureAction action = AbortProcessAction ///< Action to take
+);
+
+} // End llvm namespace
+
+#endif