MemoryDependenceAnalysis.h

//===- 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/Support/ValueHandle.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;
  class DominatorTree;
  class PHITransAddr;
  
  class MemDepResult {
    enum DepType {
      Invalid = 0,
      
      Clobber,

      Def,
      
      NonLocal
    };
    typedef PointerIntPair<Instruction*, 2, DepType> PairTy;
    PairTy Value;
    explicit MemDepResult(PairTy V) : Value(V) {}
  public:
    MemDepResult() : Value(0, Invalid) {}
    
    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));
    }

    bool isClobber() const { return Value.getInt() == Clobber; }

    bool isDef() const { return Value.getInt() == Def; }
    
    bool isNonLocal() const { return Value.getInt() == NonLocal; }
    
    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;
         
    bool isDirty() const { return Value.getInt() == Invalid; }
    
    static MemDepResult getDirty(Instruction *Inst) {
      return MemDepResult(PairTy(Inst, Invalid));
    }
  };

  class NonLocalDepResult {
    BasicBlock *BB;
    MemDepResult Result;
    Value *Address;
  public:
    NonLocalDepResult(BasicBlock *bb, MemDepResult result, Value *address)
      : BB(bb), Result(result), Address(address) {}
    
    // BB is the sort key, it can't be changed.
    BasicBlock *getBB() const { return BB; }
    
    void setResult(const MemDepResult &R, Value *Addr) {
      Result = R;
      Address = Addr;
    }
    
    const MemDepResult &getResult() const { return Result; }
    
    Value *getAddress() const { return Address; }
  };
  
  class NonLocalDepEntry {
    BasicBlock *BB;
    MemDepResult Result;
  public:
    NonLocalDepEntry(BasicBlock *bb, MemDepResult result)
      : BB(bb), Result(result) {}

    // This is used for searches.
    NonLocalDepEntry(BasicBlock *bb) : BB(bb) {}

    // BB is the sort key, it can't be changed.
    BasicBlock *getBB() const { return BB; }
    
    void setResult(const MemDepResult &R) { Result = R; }

    const MemDepResult &getResult() const { return Result; }
    
    bool operator<(const NonLocalDepEntry &RHS) const {
      return BB < RHS.BB;
    }
  };
  
  class MemoryDependenceAnalysis : public FunctionPass {
    // A map from instructions to their dependency.
    typedef DenseMap<Instruction*, MemDepResult> LocalDepMapType;
    LocalDepMapType LocalDeps;

  public:
    typedef std::vector<NonLocalDepEntry> NonLocalDepInfo;
  private:
    typedef PointerIntPair<Value*, 1, bool> ValueIsLoadPair;

    typedef PointerIntPair<BasicBlock*, 1, bool> BBSkipFirstBlockPair;

    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;

    
    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 from dependencies to the non-local dependees.
    ReverseDepMapType ReverseNonLocalDeps;
    
    AliasAnalysis *AA;
    TargetData *TD;
    OwningPtr<PredIteratorCache> PredCache;
  public:
    MemoryDependenceAnalysis();
    ~MemoryDependenceAnalysis();
    static char ID;

    bool runOnFunction(Function &);
    
    void releaseMemory();
    
    virtual void getAnalysisUsage(AnalysisUsage &AU) const;
    
    MemDepResult getDependency(Instruction *QueryInst);

    const NonLocalDepInfo &getNonLocalCallDependency(CallSite QueryCS);
    
    
    void getNonLocalPointerDependency(Value *Pointer, bool isLoad,
                                      BasicBlock *BB,
                                    SmallVectorImpl<NonLocalDepResult> &Result);
    
    void removeInstruction(Instruction *InstToRemove);
    
    void invalidateCachedPointerInfo(Value *Ptr);

    void invalidateCachedPredecessors();
    
  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(const PHITransAddr &Pointer, uint64_t Size,
                                     bool isLoad, BasicBlock *BB,
                                     SmallVectorImpl<NonLocalDepResult> &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);
    
    void verifyRemoved(Instruction *Inst) const;
    
  };

} // End llvm namespace

#endif

---