Subversion Repositories QNX 8.QNX8 LLVM/Clang compiler suite

//===- GVN.h - Eliminate redundant values and loads -------------*- C++ -*-===//

//

// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.

// See https://llvm.org/LICENSE.txt for license information.

// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception

//

//===----------------------------------------------------------------------===//

/// \file

/// This file provides the interface for LLVM's Global Value Numbering pass

/// which eliminates fully redundant instructions. It also does somewhat Ad-Hoc

/// PRE and dead load elimination.

///

//===----------------------------------------------------------------------===//

#ifndef LLVM_TRANSFORMS_SCALAR_GVN_H

#define LLVM_TRANSFORMS_SCALAR_GVN_H

#include "llvm/ADT/DenseMap.h"

#include "llvm/ADT/MapVector.h"

#include "llvm/ADT/SetVector.h"

#include "llvm/ADT/SmallVector.h"

#include "llvm/IR/Dominators.h"

#include "llvm/IR/InstrTypes.h"

#include "llvm/IR/PassManager.h"

#include "llvm/IR/ValueHandle.h"

#include "llvm/Support/Allocator.h"

#include "llvm/Support/Compiler.h"

#include <cstdint>

#include <optional>

#include <utility>

#include <vector>

namespace llvm {

class AAResults;

class AssumeInst;

class AssumptionCache;

class BasicBlock;

class BranchInst;

class CallInst;

class ExtractValueInst;

class Function;

class FunctionPass;

class GetElementPtrInst;

class ImplicitControlFlowTracking;

class LoadInst;

class LoopInfo;

class MemDepResult;

class MemoryDependenceResults;

class MemorySSA;

class MemorySSAUpdater;

class NonLocalDepResult;

class OptimizationRemarkEmitter;

class PHINode;

class TargetLibraryInfo;

class Value;

/// A private "module" namespace for types and utilities used by GVN. These

/// are implementation details and should not be used by clients.

namespace gvn LLVM_LIBRARY_VISIBILITY {

struct AvailableValue;

struct AvailableValueInBlock;

class GVNLegacyPass;

} // end namespace gvn

/// A set of parameters to control various transforms performed by GVN pass.

//  Each of the optional boolean parameters can be set to:

///      true - enabling the transformation.

///      false - disabling the transformation.

///      None - relying on a global default.

/// Intended use is to create a default object, modify parameters with

/// additional setters and then pass it to GVN.

struct GVNOptions {

  std::optional<bool> AllowPRE;

  std::optional<bool> AllowLoadPRE;

  std::optional<bool> AllowLoadInLoopPRE;

  std::optional<bool> AllowLoadPRESplitBackedge;

  std::optional<bool> AllowMemDep;

  GVNOptions() = default;

  /// Enables or disables PRE in GVN.

  GVNOptions &setPRE(bool PRE) {

    AllowPRE = PRE;

    return *this;

  }

  /// Enables or disables PRE of loads in GVN.

  GVNOptions &setLoadPRE(bool LoadPRE) {

    AllowLoadPRE = LoadPRE;

    return *this;

  }

  GVNOptions &setLoadInLoopPRE(bool LoadInLoopPRE) {

    AllowLoadInLoopPRE = LoadInLoopPRE;

    return *this;

  }

  /// Enables or disables PRE of loads in GVN.

  GVNOptions &setLoadPRESplitBackedge(bool LoadPRESplitBackedge) {

    AllowLoadPRESplitBackedge = LoadPRESplitBackedge;

    return *this;

  }

  /// Enables or disables use of MemDepAnalysis.

  GVNOptions &setMemDep(bool MemDep) {

    AllowMemDep = MemDep;

    return *this;

  }

};

/// The core GVN pass object.

///

/// FIXME: We should have a good summary of the GVN algorithm implemented by

/// this particular pass here.

class GVNPass : public PassInfoMixin<GVNPass> {

  GVNOptions Options;

public:

  struct Expression;

  GVNPass(GVNOptions Options = {}) : Options(Options) {}

  /// Run the pass over the function.

  PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);

  void printPipeline(raw_ostream &OS,

                     function_ref<StringRef(StringRef)> MapClassName2PassName);

  /// This removes the specified instruction from

  /// our various maps and marks it for deletion.

  void markInstructionForDeletion(Instruction *I) {

    VN.erase(I);

    InstrsToErase.push_back(I);

  }

  DominatorTree &getDominatorTree() const { return *DT; }

  AAResults *getAliasAnalysis() const { return VN.getAliasAnalysis(); }

  MemoryDependenceResults &getMemDep() const { return *MD; }

  bool isPREEnabled() const;

  bool isLoadPREEnabled() const;

  bool isLoadInLoopPREEnabled() const;

  bool isLoadPRESplitBackedgeEnabled() const;

  bool isMemDepEnabled() const;

  /// This class holds the mapping between values and value numbers.  It is used

  /// as an efficient mechanism to determine the expression-wise equivalence of

  /// two values.

  class ValueTable {

    DenseMap<Value *, uint32_t> valueNumbering;

    DenseMap<Expression, uint32_t> expressionNumbering;

    // Expressions is the vector of Expression. ExprIdx is the mapping from

    // value number to the index of Expression in Expressions. We use it

    // instead of a DenseMap because filling such mapping is faster than

    // filling a DenseMap and the compile time is a little better.

    uint32_t nextExprNumber = 0;

    std::vector<Expression> Expressions;

    std::vector<uint32_t> ExprIdx;

    // Value number to PHINode mapping. Used for phi-translate in scalarpre.

    DenseMap<uint32_t, PHINode *> NumberingPhi;

    // Cache for phi-translate in scalarpre.

    using PhiTranslateMap =

        DenseMap<std::pair<uint32_t, const BasicBlock *>, uint32_t>;

    PhiTranslateMap PhiTranslateTable;

    AAResults *AA = nullptr;

    MemoryDependenceResults *MD = nullptr;

    DominatorTree *DT = nullptr;

    uint32_t nextValueNumber = 1;

    Expression createExpr(Instruction *I);

    Expression createCmpExpr(unsigned Opcode, CmpInst::Predicate Predicate,

                             Value *LHS, Value *RHS);

    Expression createExtractvalueExpr(ExtractValueInst *EI);

    Expression createGEPExpr(GetElementPtrInst *GEP);

    uint32_t lookupOrAddCall(CallInst *C);

    uint32_t phiTranslateImpl(const BasicBlock *BB, const BasicBlock *PhiBlock,

                              uint32_t Num, GVNPass &Gvn);

    bool areCallValsEqual(uint32_t Num, uint32_t NewNum, const BasicBlock *Pred,

                          const BasicBlock *PhiBlock, GVNPass &Gvn);

    std::pair<uint32_t, bool> assignExpNewValueNum(Expression &exp);

    bool areAllValsInBB(uint32_t num, const BasicBlock *BB, GVNPass &Gvn);

  public:

    ValueTable();

    ValueTable(const ValueTable &Arg);

    ValueTable(ValueTable &&Arg);

    ~ValueTable();

    ValueTable &operator=(const ValueTable &Arg);

    uint32_t lookupOrAdd(Value *V);

    uint32_t lookup(Value *V, bool Verify = true) const;

    uint32_t lookupOrAddCmp(unsigned Opcode, CmpInst::Predicate Pred,

                            Value *LHS, Value *RHS);

    uint32_t phiTranslate(const BasicBlock *BB, const BasicBlock *PhiBlock,

                          uint32_t Num, GVNPass &Gvn);

    void eraseTranslateCacheEntry(uint32_t Num, const BasicBlock &CurrBlock);

    bool exists(Value *V) const;

    void add(Value *V, uint32_t num);

    void clear();

    void erase(Value *v);

    void setAliasAnalysis(AAResults *A) { AA = A; }

    AAResults *getAliasAnalysis() const { return AA; }

    void setMemDep(MemoryDependenceResults *M) { MD = M; }

    void setDomTree(DominatorTree *D) { DT = D; }

    uint32_t getNextUnusedValueNumber() { return nextValueNumber; }

    void verifyRemoved(const Value *) const;

  };

private:

  friend class gvn::GVNLegacyPass;

  friend struct DenseMapInfo<Expression>;

  MemoryDependenceResults *MD = nullptr;

  DominatorTree *DT = nullptr;

  const TargetLibraryInfo *TLI = nullptr;

  AssumptionCache *AC = nullptr;

  SetVector<BasicBlock *> DeadBlocks;

  OptimizationRemarkEmitter *ORE = nullptr;

  ImplicitControlFlowTracking *ICF = nullptr;

  LoopInfo *LI = nullptr;

  MemorySSAUpdater *MSSAU = nullptr;

  ValueTable VN;

  /// A mapping from value numbers to lists of Value*'s that

  /// have that value number.  Use findLeader to query it.

  struct LeaderTableEntry {

    Value *Val;

    const BasicBlock *BB;

    LeaderTableEntry *Next;

  };

  DenseMap<uint32_t, LeaderTableEntry> LeaderTable;

  BumpPtrAllocator TableAllocator;

  // Block-local map of equivalent values to their leader, does not

  // propagate to any successors. Entries added mid-block are applied

  // to the remaining instructions in the block.

  SmallMapVector<Value *, Value *, 4> ReplaceOperandsWithMap;

  SmallVector<Instruction *, 8> InstrsToErase;

  // Map the block to reversed postorder traversal number. It is used to

  // find back edge easily.

  DenseMap<AssertingVH<BasicBlock>, uint32_t> BlockRPONumber;

  // This is set 'true' initially and also when new blocks have been added to

  // the function being analyzed. This boolean is used to control the updating

  // of BlockRPONumber prior to accessing the contents of BlockRPONumber.

  bool InvalidBlockRPONumbers = true;

  using LoadDepVect = SmallVector<NonLocalDepResult, 64>;

  using AvailValInBlkVect = SmallVector<gvn::AvailableValueInBlock, 64>;

  using UnavailBlkVect = SmallVector<BasicBlock *, 64>;

  bool runImpl(Function &F, AssumptionCache &RunAC, DominatorTree &RunDT,

               const TargetLibraryInfo &RunTLI, AAResults &RunAA,

               MemoryDependenceResults *RunMD, LoopInfo *LI,

               OptimizationRemarkEmitter *ORE, MemorySSA *MSSA = nullptr);

  /// Push a new Value to the LeaderTable onto the list for its value number.

  void addToLeaderTable(uint32_t N, Value *V, const BasicBlock *BB) {

    LeaderTableEntry &Curr = LeaderTable[N];

    if (!Curr.Val) {

      Curr.Val = V;

      Curr.BB = BB;

      return;

    }

    LeaderTableEntry *Node = TableAllocator.Allocate<LeaderTableEntry>();

    Node->Val = V;

    Node->BB = BB;

    Node->Next = Curr.Next;

    Curr.Next = Node;

  }

  /// Scan the list of values corresponding to a given

  /// value number, and remove the given instruction if encountered.

  void removeFromLeaderTable(uint32_t N, Instruction *I, BasicBlock *BB) {

    LeaderTableEntry *Prev = nullptr;

    LeaderTableEntry *Curr = &LeaderTable[N];

    while (Curr && (Curr->Val != I || Curr->BB != BB)) {

      Prev = Curr;

      Curr = Curr->Next;

    }

    if (!Curr)

      return;

    if (Prev) {

      Prev->Next = Curr->Next;

    } else {

      if (!Curr->Next) {

        Curr->Val = nullptr;

        Curr->BB = nullptr;

      } else {

        LeaderTableEntry *Next = Curr->Next;

        Curr->Val = Next->Val;

        Curr->BB = Next->BB;

        Curr->Next = Next->Next;

      }

    }

  }

  // List of critical edges to be split between iterations.

  SmallVector<std::pair<Instruction *, unsigned>, 4> toSplit;

  // Helper functions of redundant load elimination

  bool processLoad(LoadInst *L);

  bool processNonLocalLoad(LoadInst *L);

  bool processAssumeIntrinsic(AssumeInst *II);

  /// Given a local dependency (Def or Clobber) determine if a value is

  /// available for the load.

  std::optional<gvn::AvailableValue>

  AnalyzeLoadAvailability(LoadInst *Load, MemDepResult DepInfo, Value *Address);

  /// Given a list of non-local dependencies, determine if a value is

  /// available for the load in each specified block.  If it is, add it to

  /// ValuesPerBlock.  If not, add it to UnavailableBlocks.

  void AnalyzeLoadAvailability(LoadInst *Load, LoadDepVect &Deps,

                               AvailValInBlkVect &ValuesPerBlock,

                               UnavailBlkVect &UnavailableBlocks);

  bool PerformLoadPRE(LoadInst *Load, AvailValInBlkVect &ValuesPerBlock,

                      UnavailBlkVect &UnavailableBlocks);

  /// Try to replace a load which executes on each loop iteraiton with Phi

  /// translation of load in preheader and load(s) in conditionally executed

  /// paths.

  bool performLoopLoadPRE(LoadInst *Load, AvailValInBlkVect &ValuesPerBlock,

                          UnavailBlkVect &UnavailableBlocks);

  /// Eliminates partially redundant \p Load, replacing it with \p

  /// AvailableLoads (connected by Phis if needed).

  void eliminatePartiallyRedundantLoad(

      LoadInst *Load, AvailValInBlkVect &ValuesPerBlock,

      MapVector<BasicBlock *, Value *> &AvailableLoads);

  // Other helper routines

  bool processInstruction(Instruction *I);

  bool processBlock(BasicBlock *BB);

  void dump(DenseMap<uint32_t, Value *> &d) const;

  bool iterateOnFunction(Function &F);

  bool performPRE(Function &F);

  bool performScalarPRE(Instruction *I);

  bool performScalarPREInsertion(Instruction *Instr, BasicBlock *Pred,

                                 BasicBlock *Curr, unsigned int ValNo);

  Value *findLeader(const BasicBlock *BB, uint32_t num);

  void cleanupGlobalSets();

  void verifyRemoved(const Instruction *I) const;

  bool splitCriticalEdges();

  BasicBlock *splitCriticalEdges(BasicBlock *Pred, BasicBlock *Succ);

  bool replaceOperandsForInBlockEquality(Instruction *I) const;

  bool propagateEquality(Value *LHS, Value *RHS, const BasicBlockEdge &Root,

                         bool DominatesByEdge);

  bool processFoldableCondBr(BranchInst *BI);

  void addDeadBlock(BasicBlock *BB);

  void assignValNumForDeadCode();

  void assignBlockRPONumber(Function &F);

};

/// Create a legacy GVN pass. This also allows parameterizing whether or not

/// MemDep is enabled.

FunctionPass *createGVNPass(bool NoMemDepAnalysis = false);

/// A simple and fast domtree-based GVN pass to hoist common expressions

/// from sibling branches.

struct GVNHoistPass : PassInfoMixin<GVNHoistPass> {

  /// Run the pass over the function.

  PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);

};

/// Uses an "inverted" value numbering to decide the similarity of

/// expressions and sinks similar expressions into successors.

struct GVNSinkPass : PassInfoMixin<GVNSinkPass> {

  /// Run the pass over the function.

  PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);

};

} // end namespace llvm

#endif // LLVM_TRANSFORMS_SCALAR_GVN_H