SCCPSolver.h

Go to the documentation of this file.

//===- SCCPSolver.h - SCCP Utility ----------------------------- *- 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 implements Sparse Conditional Constant Propagation (SCCP) utility.
//
//===----------------------------------------------------------------------===//
 
#ifndef LLVM_TRANSFORMS_UTILS_SCCPSOLVER_H
#define LLVM_TRANSFORMS_UTILS_SCCPSOLVER_H
 
#include "llvm/ADT/MapVector.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/DomTreeUpdater.h"
#include "llvm/Transforms/Utils/PredicateInfo.h"
#include <vector>
 
namespace llvm {
class Argument;
class BasicBlock;
class CallInst;
class Constant;
class DataLayout;
class DominatorTree;
class Function;
class GlobalVariable;
class Instruction;
class LLVMContext;
class LoopInfo;
class PostDominatorTree;
class StructType;
class TargetLibraryInfo;
class Value;
class ValueLatticeElement;
 
/// Helper struct for bundling up the analysis results per function for IPSCCP.
struct AnalysisResultsForFn {
  std::unique_ptr<PredicateInfo> PredInfo;
  DominatorTree *DT;
  PostDominatorTree *PDT;
  LoopInfo *LI;
};
 
/// Helper struct shared between Function Specialization and SCCP Solver.
struct ArgInfo {
  Argument *Formal; // The Formal argument being analysed.
  Constant *Actual; // A corresponding actual constant argument.
 
  ArgInfo(Argument *F, Constant *A) : Formal(F), Actual(A) {}
 
  bool operator==(const ArgInfo &Other) const {
    return Formal == Other.Formal && Actual == Other.Actual;
  }
 
  bool operator!=(const ArgInfo &Other) const { return !(*this == Other); }
 
  friend hash_code hash_value(const ArgInfo &A) {
    return hash_combine(hash_value(A.Formal), hash_value(A.Actual));
  }
};
 
class SCCPInstVisitor;
 
//===----------------------------------------------------------------------===//
//
/// SCCPSolver - This interface class is a general purpose solver for Sparse
/// Conditional Constant Propagation (SCCP).
///
class SCCPSolver {
  std::unique_ptr<SCCPInstVisitor> Visitor;
 
public:
  SCCPSolver(const DataLayout &DL,
             std::function<const TargetLibraryInfo &(Function &)> GetTLI,
             LLVMContext &Ctx);
 
  ~SCCPSolver();
 
  void addAnalysis(Function &F, AnalysisResultsForFn A);
 
  /// 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.
  /// This returns true if the block was not considered live before.
  bool markBlockExecutable(BasicBlock *BB);
 
  const PredicateBase *getPredicateInfoFor(Instruction *I);
 
  const LoopInfo &getLoopInfo(Function &F);
 
  DomTreeUpdater getDTU(Function &F);
 
  /// trackValueOfGlobalVariable - Clients can use this method to
  /// inform the SCCPSolver that it should track loads and stores to the
  /// specified global variable if it can.  This is only legal to call if
  /// performing Interprocedural SCCP.
  void trackValueOfGlobalVariable(GlobalVariable *GV);
 
  /// addTrackedFunction - If the SCCP solver is supposed to track calls into
  /// and out of the specified function (which cannot have its address taken),
  /// this method must be called.
  void addTrackedFunction(Function *F);
 
  /// Add function to the list of functions whose return cannot be modified.
  void addToMustPreserveReturnsInFunctions(Function *F);
 
  /// Returns true if the return of the given function cannot be modified.
  bool mustPreserveReturn(Function *F);
 
  void addArgumentTrackedFunction(Function *F);
 
  /// Returns true if the given function is in the solver's set of
  /// argument-tracked functions.
  bool isArgumentTrackedFunction(Function *F);
 
  /// Solve - Solve for constants and executable blocks.
  void solve();
 
  /// resolvedUndefsIn - While solving the dataflow for a function, we assume
  /// that branches on undef values cannot reach any of their successors.
  /// However, this is not a safe assumption.  After we solve dataflow, this
  /// method should be use to handle this.  If this returns true, the solver
  /// should be rerun.
  bool resolvedUndefsIn(Function &F);
 
  void solveWhileResolvedUndefsIn(Module &M);
 
  void solveWhileResolvedUndefsIn(SmallVectorImpl<Function *> &WorkList);
 
  bool isBlockExecutable(BasicBlock *BB) const;
 
  // isEdgeFeasible - Return true if the control flow edge from the 'From' basic
  // block to the 'To' basic block is currently feasible.
  bool isEdgeFeasible(BasicBlock *From, BasicBlock *To) const;
 
  std::vector<ValueLatticeElement> getStructLatticeValueFor(Value *V) const;
 
  void removeLatticeValueFor(Value *V);
 
  const ValueLatticeElement &getLatticeValueFor(Value *V) const;
 
  /// getTrackedRetVals - Get the inferred return value map.
  const MapVector<Function *, ValueLatticeElement> &getTrackedRetVals();
 
  /// getTrackedGlobals - Get and return the set of inferred initializers for
  /// global variables.
  const DenseMap<GlobalVariable *, ValueLatticeElement> &getTrackedGlobals();
 
  /// getMRVFunctionsTracked - Get the set of functions which return multiple
  /// values tracked by the pass.
  const SmallPtrSet<Function *, 16> getMRVFunctionsTracked();
 
  /// markOverdefined - Mark the specified value overdefined.  This
  /// works with both scalars and structs.
  void markOverdefined(Value *V);
 
  // isStructLatticeConstant - Return true if all the lattice values
  // corresponding to elements of the structure are constants,
  // false otherwise.
  bool isStructLatticeConstant(Function *F, StructType *STy);
 
  /// Helper to return a Constant if \p LV is either a constant or a constant
  /// range with a single element.
  Constant *getConstant(const ValueLatticeElement &LV) const;
 
  /// Return a reference to the set of argument tracked functions.
  SmallPtrSetImpl<Function *> &getArgumentTrackedFunctions();
 
  /// Mark the constant arguments of a new function specialization. \p F points
  /// to the cloned function and \p Args contains a list of constant arguments
  /// represented as pairs of {formal,actual} values (the formal argument is
  /// associated with the original function definition). All other arguments of
  /// the specialization inherit the lattice state of their corresponding values
  /// in the original function.
  void markArgInFuncSpecialization(Function *F,
                                   const SmallVectorImpl<ArgInfo> &Args);
 
  /// Mark all of the blocks in function \p F non-executable. Clients can used
  /// this method to erase a function from the module (e.g., if it has been
  /// completely specialized and is no longer needed).
  void markFunctionUnreachable(Function *F);
 
  void visit(Instruction *I);
  void visitCall(CallInst &I);
 
  bool simplifyInstsInBlock(BasicBlock &BB,
                            SmallPtrSetImpl<Value *> &InsertedValues,
                            Statistic &InstRemovedStat,
                            Statistic &InstReplacedStat);
 
  bool removeNonFeasibleEdges(BasicBlock *BB, DomTreeUpdater &DTU,
                              BasicBlock *&NewUnreachableBB) const;
 
  bool tryToReplaceWithConstant(Value *V);
 
  // Helper to check if \p LV is either a constant or a constant
  // range with a single element. This should cover exactly the same cases as
  // the old ValueLatticeElement::isConstant() and is intended to be used in the
  // transition to ValueLatticeElement.
  static bool isConstant(const ValueLatticeElement &LV);
 
  // Helper to check if \p LV is either overdefined or a constant range with
  // more than a single element. This should cover exactly the same cases as the
  // old ValueLatticeElement::isOverdefined() and is intended to be used in the
  // transition to ValueLatticeElement.
  static bool isOverdefined(const ValueLatticeElement &LV);
};
} // namespace llvm
 
#endif // LLVM_TRANSFORMS_UTILS_SCCPSOLVER_H