NewGVN.cpp | Explore in Territory

//===- NewGVN.cpp - Global Value Numbering Pass ---------------------------===//
//
// 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 the new LLVM's Global Value Numbering pass.
/// GVN partitions values computed by a function into congruence classes.
/// Values ending up in the same congruence class are guaranteed to be the same
/// for every execution of the program. In that respect, congruency is a
/// compile-time approximation of equivalence of values at runtime.
/// The algorithm implemented here uses a sparse formulation and it's based
/// on the ideas described in the paper:
/// "A Sparse Algorithm for Predicated Global Value Numbering" from
/// Karthik Gargi.
///
/// A brief overview of the algorithm: The algorithm is essentially the same as
/// the standard RPO value numbering algorithm (a good reference is the paper
/// "SCC based value numbering" by L. Taylor Simpson) with one major difference:
/// The RPO algorithm proceeds, on every iteration, to process every reachable
/// block and every instruction in that block.  This is because the standard RPO
/// algorithm does not track what things have the same value number, it only
/// tracks what the value number of a given operation is (the mapping is
/// operation -> value number).  Thus, when a value number of an operation
/// changes, it must reprocess everything to ensure all uses of a value number
/// get updated properly.  In constrast, the sparse algorithm we use *also*
/// tracks what operations have a given value number (IE it also tracks the
/// reverse mapping from value number -> operations with that value number), so
/// that it only needs to reprocess the instructions that are affected when
/// something's value number changes.  The vast majority of complexity and code
/// in this file is devoted to tracking what value numbers could change for what
/// instructions when various things happen.  The rest of the algorithm is
/// devoted to performing symbolic evaluation, forward propagation, and
/// simplification of operations based on the value numbers deduced so far
///
/// In order to make the GVN mostly-complete, we use a technique derived from
/// "Detection of Redundant Expressions: A Complete and Polynomial-time
/// Algorithm in SSA" by R.R. Pai.  The source of incompleteness in most SSA
/// based GVN algorithms is related to their inability to detect equivalence
/// between phi of ops (IE phi(a+b, c+d)) and op of phis (phi(a,c) + phi(b, d)).
/// We resolve this issue by generating the equivalent "phi of ops" form for
/// each op of phis we see, in a way that only takes polynomial time to resolve.
///
/// We also do not perform elimination by using any published algorithm.  All
/// published algorithms are O(Instructions). Instead, we use a technique that
/// is O(number of operations with the same value number), enabling us to skip
/// trying to eliminate things that have unique value numbers.
//
//===----------------------------------------------------------------------===//

#include "llvm/Transforms/Scalar/NewGVN.h"
#include "llvm/ADT/ArrayRef.h"
#include "llvm/ADT/BitVector.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/DenseMapInfo.h"
#include "llvm/ADT/DenseSet.h"
#include "llvm/ADT/DepthFirstIterator.h"
#include "llvm/ADT/GraphTraits.h"
#include "llvm/ADT/Hashing.h"
#include "llvm/ADT/PointerIntPair.h"
#include "llvm/ADT/PostOrderIterator.h"
#include "llvm/ADT/SetOperations.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/SparseBitVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/iterator_range.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/AssumptionCache.h"
#include "llvm/Analysis/CFGPrinter.h"
#include "llvm/Analysis/ConstantFolding.h"
#include "llvm/Analysis/GlobalsModRef.h"
#include "llvm/Analysis/InstructionSimplify.h"
#include "llvm/Analysis/MemoryBuiltins.h"
#include "llvm/Analysis/MemorySSA.h"
#include "llvm/Analysis/TargetLibraryInfo.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/IR/Argument.h"
#include "llvm/IR/BasicBlock.h"
#include "llvm/IR/Constant.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/InstrTypes.h"
#include "llvm/IR/Instruction.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/IR/PatternMatch.h"
#include "llvm/IR/Type.h"
#include "llvm/IR/Use.h"
#include "llvm/IR/User.h"
#include "llvm/IR/Value.h"
#include "llvm/Support/Allocator.h"
#include "llvm/Support/ArrayRecycler.h"
#include "llvm/Support/Casting.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/DebugCounter.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/PointerLikeTypeTraits.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Transforms/Scalar/GVNExpression.h"
#include "llvm/Transforms/Utils/AssumeBundleBuilder.h"
#include "llvm/Transforms/Utils/Local.h"
#include "llvm/Transforms/Utils/PredicateInfo.h"
#include "llvm/Transforms/Utils/VNCoercion.h"
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <iterator>
#include <map>
#include <memory>
#include <set>
#include <string>
#include <tuple>
#include <utility>
#include <vector>

usingnamespacellvm;
usingnamespacellvm::GVNExpression;
usingnamespacellvm::VNCoercion;
usingnamespacellvm::PatternMatch;

#define DEBUG_TYPE …

STATISTIC(NumGVNInstrDeleted, "Number of instructions deleted");
STATISTIC(NumGVNBlocksDeleted, "Number of blocks deleted");
STATISTIC(NumGVNOpsSimplified, "Number of Expressions simplified");
STATISTIC(NumGVNPhisAllSame, "Number of PHIs whos arguments are all the same");
STATISTIC(NumGVNMaxIterations,
          "Maximum Number of iterations it took to converge GVN");
STATISTIC(NumGVNLeaderChanges, "Number of leader changes");
STATISTIC(NumGVNSortedLeaderChanges, "Number of sorted leader changes");
STATISTIC(NumGVNAvoidedSortedLeaderChanges,
          "Number of avoided sorted leader changes");
STATISTIC(NumGVNDeadStores, "Number of redundant/dead stores eliminated");
STATISTIC(NumGVNPHIOfOpsCreated, "Number of PHI of ops created");
STATISTIC(NumGVNPHIOfOpsEliminations,
          "Number of things eliminated using PHI of ops");
DEBUG_COUNTER(VNCounter, "newgvn-vn",
              "Controls which instructions are value numbered");
DEBUG_COUNTER(PHIOfOpsCounter, "newgvn-phi",
              "Controls which instructions we create phi of ops for");
// Currently store defining access refinement is too slow due to basicaa being
// egregiously slow.  This flag lets us keep it working while we work on this
// issue.
static cl::opt<bool> EnableStoreRefinement("enable-store-refinement",
                                           cl::init(false), cl::Hidden);

/// Currently, the generation "phi of ops" can result in correctness issues.
static cl::opt<bool> EnablePhiOfOps("enable-phi-of-ops", cl::init(true),
                                    cl::Hidden);

//===----------------------------------------------------------------------===//
//                                GVN Pass
//===----------------------------------------------------------------------===//

// Anchor methods.
namespace llvm {
namespace GVNExpression {

Expression::~Expression() = default;
BasicExpression::~BasicExpression() = default;
CallExpression::~CallExpression() = default;
LoadExpression::~LoadExpression() = default;
StoreExpression::~StoreExpression() = default;
AggregateValueExpression::~AggregateValueExpression() = default;
PHIExpression::~PHIExpression() = default;

} // end namespace GVNExpression
} // end namespace llvm

namespace {

// Tarjan's SCC finding algorithm with Nuutila's improvements
// SCCIterator is actually fairly complex for the simple thing we want.
// It also wants to hand us SCC's that are unrelated to the phi node we ask
// about, and have us process them there or risk redoing work.
// Graph traits over a filter iterator also doesn't work that well here.
// This SCC finder is specialized to walk use-def chains, and only follows
// instructions,
// not generic values (arguments, etc).
struct TarjanSCC { … };

// Congruence classes represent the set of expressions/instructions
// that are all the same *during some scope in the function*.
// That is, because of the way we perform equality propagation, and
// because of memory value numbering, it is not correct to assume
// you can willy-nilly replace any member with any other at any
// point in the function.
//
// For any Value in the Member set, it is valid to replace any dominated member
// with that Value.
//
// Every congruence class has a leader, and the leader is used to symbolize
// instructions in a canonical way (IE every operand of an instruction that is a
// member of the same congruence class will always be replaced with leader
// during symbolization).  To simplify symbolization, we keep the leader as a
// constant if class can be proved to be a constant value.  Otherwise, the
// leader is the member of the value set with the smallest DFS number.  Each
// congruence class also has a defining expression, though the expression may be
// null.  If it exists, it can be used for forward propagation and reassociation
// of values.

// For memory, we also track a representative MemoryAccess, and a set of memory
// members for MemoryPhis (which have no real instructions). Note that for
// memory, it seems tempting to try to split the memory members into a
// MemoryCongruenceClass or something.  Unfortunately, this does not work
// easily.  The value numbering of a given memory expression depends on the
// leader of the memory congruence class, and the leader of memory congruence
// class depends on the value numbering of a given memory expression.  This
// leads to wasted propagation, and in some cases, missed optimization.  For
// example: If we had value numbered two stores together before, but now do not,
// we move them to a new value congruence class.  This in turn will move at one
// of the memorydefs to a new memory congruence class.  Which in turn, affects
// the value numbering of the stores we just value numbered (because the memory
// congruence class is part of the value number).  So while theoretically
// possible to split them up, it turns out to be *incredibly* complicated to get
// it to work right, because of the interdependency.  While structurally
// slightly messier, it is algorithmically much simpler and faster to do what we
// do here, and track them both at once in the same class.
// Note: The default iterators for this class iterate over values
class CongruenceClass { … };

} // end anonymous namespace

namespace llvm {

struct ExactEqualsExpression { … };

template <> struct DenseMapInfo<const Expression *> { … };

} // end namespace llvm

namespace {

class NewGVN { … };

} // end anonymous namespace

template <typename T>
static bool equalsLoadStoreHelper(const T &LHS, const Expression &RHS) { … }

bool LoadExpression::equals(const Expression &Other) const { … }

bool StoreExpression::equals(const Expression &Other) const { … }

// Determine if the edge From->To is a backedge
bool NewGVN::isBackedge(BasicBlock *From, BasicBlock *To) const { … }

#ifndef NDEBUG
static std::string getBlockName(const BasicBlock *B) {
  return DOTGraphTraits<DOTFuncInfo *>::getSimpleNodeLabel(B, nullptr);
}
#endif

// Get a MemoryAccess for an instruction, fake or real.
MemoryUseOrDef *NewGVN::getMemoryAccess(const Instruction *I) const { … }

// Get a MemoryPhi for a basic block. These are all real.
MemoryPhi *NewGVN::getMemoryAccess(const BasicBlock *BB) const { … }

// Get the basic block from an instruction/memory value.
BasicBlock *NewGVN::getBlockForValue(Value *V) const { … }

// Delete a definitely dead expression, so it can be reused by the expression
// allocator.  Some of these are not in creation functions, so we have to accept
// const versions.
void NewGVN::deleteExpression(const Expression *E) const { … }

// If V is a predicateinfo copy, get the thing it is a copy of.
static Value *getCopyOf(const Value *V) { … }

// Return true if V is really PN, even accounting for predicateinfo copies.
static bool isCopyOfPHI(const Value *V, const PHINode *PN) { … }

static bool isCopyOfAPHI(const Value *V) { … }

// Sort PHI Operands into a canonical order.  What we use here is an RPO
// order. The BlockInstRange numbers are generated in an RPO walk of the basic
// blocks.
void NewGVN::sortPHIOps(MutableArrayRef<ValPair> Ops) const { … }

// Return true if V is a value that will always be available (IE can
// be placed anywhere) in the function.  We don't do globals here
// because they are often worse to put in place.
static bool alwaysAvailable(Value *V) { … }

// Create a PHIExpression from an array of {incoming edge, value} pairs.  I is
// the original instruction we are creating a PHIExpression for (but may not be
// a phi node). We require, as an invariant, that all the PHIOperands in the
// same block are sorted the same way. sortPHIOps will sort them into a
// canonical order.
PHIExpression *NewGVN::createPHIExpression(ArrayRef<ValPair> PHIOperands,
                                           const Instruction *I,
                                           BasicBlock *PHIBlock,
                                           bool &HasBackedge,
                                           bool &OriginalOpsConstant) const { … }

// Set basic expression info (Arguments, type, opcode) for Expression
// E from Instruction I in block B.
bool NewGVN::setBasicExpressionInfo(Instruction *I, BasicExpression *E) const { … }

const Expression *NewGVN::createBinaryExpression(unsigned Opcode, Type *T,
                                                 Value *Arg1, Value *Arg2,
                                                 Instruction *I) const { … }

// Take a Value returned by simplification of Expression E/Instruction
// I, and see if it resulted in a simpler expression. If so, return
// that expression.
NewGVN::ExprResult NewGVN::checkExprResults(Expression *E, Instruction *I,
                                            Value *V) const { … }

// Create a value expression from the instruction I, replacing operands with
// their leaders.

NewGVN::ExprResult NewGVN::createExpression(Instruction *I) const { … }

const AggregateValueExpression *
NewGVN::createAggregateValueExpression(Instruction *I) const { … }

const DeadExpression *NewGVN::createDeadExpression() const { … }

const VariableExpression *NewGVN::createVariableExpression(Value *V) const { … }

const Expression *NewGVN::createVariableOrConstant(Value *V) const { … }

const ConstantExpression *NewGVN::createConstantExpression(Constant *C) const { … }

const UnknownExpression *NewGVN::createUnknownExpression(Instruction *I) const { … }

const CallExpression *
NewGVN::createCallExpression(CallInst *CI, const MemoryAccess *MA) const { … }

// Return true if some equivalent of instruction Inst dominates instruction U.
bool NewGVN::someEquivalentDominates(const Instruction *Inst,
                                     const Instruction *U) const { … }

// See if we have a congruence class and leader for this operand, and if so,
// return it. Otherwise, return the operand itself.
Value *NewGVN::lookupOperandLeader(Value *V) const { … }

const MemoryAccess *NewGVN::lookupMemoryLeader(const MemoryAccess *MA) const { … }

// Return true if the MemoryAccess is really equivalent to everything. This is
// equivalent to the lattice value "TOP" in most lattices.  This is the initial
// state of all MemoryAccesses.
bool NewGVN::isMemoryAccessTOP(const MemoryAccess *MA) const { … }

LoadExpression *NewGVN::createLoadExpression(Type *LoadType, Value *PointerOp,
                                             LoadInst *LI,
                                             const MemoryAccess *MA) const { … }

const StoreExpression *
NewGVN::createStoreExpression(StoreInst *SI, const MemoryAccess *MA) const { … }

const Expression *NewGVN::performSymbolicStoreEvaluation(Instruction *I) const { … }

// See if we can extract the value of a loaded pointer from a load, a store, or
// a memory instruction.
const Expression *
NewGVN::performSymbolicLoadCoercion(Type *LoadType, Value *LoadPtr,
                                    LoadInst *LI, Instruction *DepInst,
                                    MemoryAccess *DefiningAccess) const { … }

const Expression *NewGVN::performSymbolicLoadEvaluation(Instruction *I) const { … }

NewGVN::ExprResult
NewGVN::performSymbolicPredicateInfoEvaluation(IntrinsicInst *I) const { … }

// Evaluate read only and pure calls, and create an expression result.
NewGVN::ExprResult NewGVN::performSymbolicCallEvaluation(Instruction *I) const { … }

// Retrieve the memory class for a given MemoryAccess.
CongruenceClass *NewGVN::getMemoryClass(const MemoryAccess *MA) const { … }

// Update the MemoryAccess equivalence table to say that From is equal to To,
// and return true if this is different from what already existed in the table.
bool NewGVN::setMemoryClass(const MemoryAccess *From,
                            CongruenceClass *NewClass) { … }

// Determine if a instruction is cycle-free.  That means the values in the
// instruction don't depend on any expressions that can change value as a result
// of the instruction.  For example, a non-cycle free instruction would be v =
// phi(0, v+1).
bool NewGVN::isCycleFree(const Instruction *I) const { … }

// Evaluate PHI nodes symbolically and create an expression result.
const Expression *
NewGVN::performSymbolicPHIEvaluation(ArrayRef<ValPair> PHIOps,
                                     Instruction *I,
                                     BasicBlock *PHIBlock) const { … }

const Expression *
NewGVN::performSymbolicAggrValueEvaluation(Instruction *I) const { … }

NewGVN::ExprResult NewGVN::performSymbolicCmpEvaluation(Instruction *I) const { … }

// Substitute and symbolize the instruction before value numbering.
NewGVN::ExprResult
NewGVN::performSymbolicEvaluation(Instruction *I,
                                  SmallPtrSetImpl<Value *> &Visited) const { … }

// Look up a container of values/instructions in a map, and touch all the
// instructions in the container.  Then erase value from the map.
template <typename Map, typename KeyType>
void NewGVN::touchAndErase(Map &M, const KeyType &Key) { … }

void NewGVN::addAdditionalUsers(Value *To, Value *User) const { … }

void NewGVN::addAdditionalUsers(ExprResult &Res, Instruction *User) const { … }

void NewGVN::markUsersTouched(Value *V) { … }

void NewGVN::addMemoryUsers(const MemoryAccess *To, MemoryAccess *U) const { … }

void NewGVN::markMemoryDefTouched(const MemoryAccess *MA) { … }

void NewGVN::markMemoryUsersTouched(const MemoryAccess *MA) { … }

// Touch all the predicates that depend on this instruction.
void NewGVN::markPredicateUsersTouched(Instruction *I) { … }

// Mark users affected by a memory leader change.
void NewGVN::markMemoryLeaderChangeTouched(CongruenceClass *CC) { … }

// Touch the instructions that need to be updated after a congruence class has a
// leader change, and mark changed values.
void NewGVN::markValueLeaderChangeTouched(CongruenceClass *CC) { … }

// Give a range of things that have instruction DFS numbers, this will return
// the member of the range with the smallest dfs number.
template <class T, class Range>
T *NewGVN::getMinDFSOfRange(const Range &R) const { … }

// This function returns the MemoryAccess that should be the next leader of
// congruence class CC, under the assumption that the current leader is going to
// disappear.
const MemoryAccess *NewGVN::getNextMemoryLeader(CongruenceClass *CC) const { … }

// This function returns the next value leader of a congruence class, under the
// assumption that the current leader is going away.  This should end up being
// the next most dominating member.
Value *NewGVN::getNextValueLeader(CongruenceClass *CC) const { … }

// Move a MemoryAccess, currently in OldClass, to NewClass, including updates to
// the memory members, etc for the move.
//
// The invariants of this function are:
//
// - I must be moving to NewClass from OldClass
// - The StoreCount of OldClass and NewClass is expected to have been updated
//   for I already if it is a store.
// - The OldClass memory leader has not been updated yet if I was the leader.
void NewGVN::moveMemoryToNewCongruenceClass(Instruction *I,
                                            MemoryAccess *InstMA,
                                            CongruenceClass *OldClass,
                                            CongruenceClass *NewClass) { … }

// Move a value, currently in OldClass, to be part of NewClass
// Update OldClass and NewClass for the move (including changing leaders, etc).
void NewGVN::moveValueToNewCongruenceClass(Instruction *I, const Expression *E,
                                           CongruenceClass *OldClass,
                                           CongruenceClass *NewClass) { … }

// For a given expression, mark the phi of ops instructions that could have
// changed as a result.
void NewGVN::markPhiOfOpsChanged(const Expression *E) { … }

// Perform congruence finding on a given value numbering expression.
void NewGVN::performCongruenceFinding(Instruction *I, const Expression *E) { … }

// Process the fact that Edge (from, to) is reachable, including marking
// any newly reachable blocks and instructions for processing.
void NewGVN::updateReachableEdge(BasicBlock *From, BasicBlock *To) { … }

// Given a predicate condition (from a switch, cmp, or whatever) and a block,
// see if we know some constant value for it already.
Value *NewGVN::findConditionEquivalence(Value *Cond) const { … }

// Process the outgoing edges of a block for reachability.
void NewGVN::processOutgoingEdges(Instruction *TI, BasicBlock *B) { … }

// Remove the PHI of Ops PHI for I
void NewGVN::removePhiOfOps(Instruction *I, PHINode *PHITemp) { … }

// Add PHI Op in BB as a PHI of operations version of ExistingValue.
void NewGVN::addPhiOfOps(PHINode *Op, BasicBlock *BB,
                         Instruction *ExistingValue) { … }

static bool okayForPHIOfOps(const Instruction *I) { … }

// Return true if this operand will be safe to use for phi of ops.
//
// The reason some operands are unsafe is that we are not trying to recursively
// translate everything back through phi nodes.  We actually expect some lookups
// of expressions to fail.  In particular, a lookup where the expression cannot
// exist in the predecessor.  This is true even if the expression, as shown, can
// be determined to be constant.
bool NewGVN::OpIsSafeForPHIOfOps(Value *V, const BasicBlock *PHIBlock,
                                 SmallPtrSetImpl<const Value *> &Visited) { … }

// Try to find a leader for instruction TransInst, which is a phi translated
// version of something in our original program.  Visited is used to ensure we
// don't infinite loop during translations of cycles.  OrigInst is the
// instruction in the original program, and PredBB is the predecessor we
// translated it through.
Value *NewGVN::findLeaderForInst(Instruction *TransInst,
                                 SmallPtrSetImpl<Value *> &Visited,
                                 MemoryAccess *MemAccess, Instruction *OrigInst,
                                 BasicBlock *PredBB) { … }

// When we see an instruction that is an op of phis, generate the equivalent phi
// of ops form.
const Expression *
NewGVN::makePossiblePHIOfOps(Instruction *I,
                             SmallPtrSetImpl<Value *> &Visited) { … }

// The algorithm initially places the values of the routine in the TOP
// congruence class. The leader of TOP is the undetermined value `poison`.
// When the algorithm has finished, values still in TOP are unreachable.
void NewGVN::initializeCongruenceClasses(Function &F) { … }

void NewGVN::cleanupTables() { … }

// Assign local DFS number mapping to instructions, and leave space for Value
// PHI's.
std::pair<unsigned, unsigned> NewGVN::assignDFSNumbers(BasicBlock *B,
                                                       unsigned Start) { … }

void NewGVN::updateProcessedCount(const Value *V) { … }

// Evaluate MemoryPhi nodes symbolically, just like PHI nodes
void NewGVN::valueNumberMemoryPhi(MemoryPhi *MP) { … }

// Value number a single instruction, symbolically evaluating, performing
// congruence finding, and updating mappings.
void NewGVN::valueNumberInstruction(Instruction *I) { … }

// Check if there is a path, using single or equal argument phi nodes, from
// First to Second.
bool NewGVN::singleReachablePHIPath(
    SmallPtrSet<const MemoryAccess *, 8> &Visited, const MemoryAccess *First,
    const MemoryAccess *Second) const { … }

// Verify the that the memory equivalence table makes sense relative to the
// congruence classes.  Note that this checking is not perfect, and is currently
// subject to very rare false negatives. It is only useful for
// testing/debugging.
void NewGVN::verifyMemoryCongruency() const { … }

// Verify that the sparse propagation we did actually found the maximal fixpoint
// We do this by storing the value to class mapping, touching all instructions,
// and redoing the iteration to see if anything changed.
void NewGVN::verifyIterationSettled(Function &F) { … }

// Verify that for each store expression in the expression to class mapping,
// only the latest appears, and multiple ones do not appear.
// Because loads do not use the stored value when doing equality with stores,
// if we don't erase the old store expressions from the table, a load can find
// a no-longer valid StoreExpression.
void NewGVN::verifyStoreExpressions() const { … }

// This is the main value numbering loop, it iterates over the initial touched
// instruction set, propagating value numbers, marking things touched, etc,
// until the set of touched instructions is completely empty.
void NewGVN::iterateTouchedInstructions() { … }

// This is the main transformation entry point.
bool NewGVN::runGVN() { … }

struct NewGVN::ValueDFS { … };

// This function converts the set of members for a congruence class from values,
// to sets of defs and uses with associated DFS info.  The total number of
// reachable uses for each value is stored in UseCount, and instructions that
// seem
// dead (have no non-dead uses) are stored in ProbablyDead.
void NewGVN::convertClassToDFSOrdered(
    const CongruenceClass &Dense, SmallVectorImpl<ValueDFS> &DFSOrderedSet,
    DenseMap<const Value *, unsigned int> &UseCounts,
    SmallPtrSetImpl<Instruction *> &ProbablyDead) const { … }

// This function converts the set of members for a congruence class from values,
// to the set of defs for loads and stores, with associated DFS info.
void NewGVN::convertClassToLoadsAndStores(
    const CongruenceClass &Dense,
    SmallVectorImpl<ValueDFS> &LoadsAndStores) const { … }

static void patchAndReplaceAllUsesWith(Instruction *I, Value *Repl) { … }

void NewGVN::deleteInstructionsInBlock(BasicBlock *BB) { … }

void NewGVN::markInstructionForDeletion(Instruction *I) { … }

void NewGVN::replaceInstruction(Instruction *I, Value *V) { … }

namespace {

// This is a stack that contains both the value and dfs info of where
// that value is valid.
class ValueDFSStack { … };

} // end anonymous namespace

// Given an expression, get the congruence class for it.
CongruenceClass *NewGVN::getClassForExpression(const Expression *E) const { … }

// Given a value and a basic block we are trying to see if it is available in,
// see if the value has a leader available in that block.
Value *NewGVN::findPHIOfOpsLeader(const Expression *E,
                                  const Instruction *OrigInst,
                                  const BasicBlock *BB) const { … }

bool NewGVN::eliminateInstructions(Function &F) { … }

// This function provides global ranking of operations so that we can place them
// in a canonical order.  Note that rank alone is not necessarily enough for a
// complete ordering, as constants all have the same rank.  However, generally,
// we will simplify an operation with all constants so that it doesn't matter
// what order they appear in.
unsigned int NewGVN::getRank(const Value *V) const { … }

// This is a function that says whether two commutative operations should
// have their order swapped when canonicalizing.
bool NewGVN::shouldSwapOperands(const Value *A, const Value *B) const { … }

bool NewGVN::shouldSwapOperandsForIntrinsic(const Value *A, const Value *B,
                                            const IntrinsicInst *I) const { … }

PreservedAnalyses NewGVNPass::run(Function &F, AnalysisManager<Function> &AM) { … }
llvm/llvm/lib/Transforms/Scalar/NewGVN.cpp
