This file implements the new LLVM's Global Value Numbering pass. More...

#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/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/Transforms/Utils/Local.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/Intrinsics.h"
#include "llvm/IR/LLVMContext.h"
#include "llvm/IR/Type.h"
#include "llvm/IR/Use.h"
#include "llvm/IR/User.h"
#include "llvm/IR/Value.h"
#include "llvm/Pass.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.h"
#include "llvm/Transforms/Scalar/GVNExpression.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>

Classes
struct	llvm::ExactEqualsExpression

struct	llvm::DenseMapInfo< const Expression * >

struct	NewGVN::ValueDFS

Namespaces
	llvm
	This class represents lattice values for constants.

	llvm::GVNExpression

Macros
#define	DEBUG_TYPE "newgvn"

Functions
	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")

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

static std::string	getBlockName (const BasicBlock *B)

static Value *	getCopyOf (const Value *V)

static bool	isCopyOfPHI (const Value V, const PHINode PN)

static bool	isCopyOfAPHI (const Value *V)

static bool	alwaysAvailable (Value *V)

static bool	okayForPHIOfOps (const Instruction *I)

static void	patchAndReplaceAllUsesWith (Instruction I, Value Repl)

	INITIALIZE_PASS_BEGIN (NewGVNLegacyPass, "newgvn", "Global Value Numbering", false, false) INITIALIZE_PASS_END(NewGVNLegacyPass

Variables
static cl::opt< bool >	EnableStoreRefinement ("enable-store-refinement", cl::init(false), cl::Hidden)

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

	newgvn

Global Value	Numbering

Global Value	false

Detailed Description

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.

Definition in file NewGVN.cpp.

Macro Definition Documentation

◆ DEBUG_TYPE

#define DEBUG_TYPE "newgvn"

Definition at line 127 of file NewGVN.cpp.

Function Documentation

◆ alwaysAvailable()

static bool alwaysAvailable ( Value * V )

static

Definition at line 971 of file NewGVN.cpp.

References llvm::MCID::Add, llvm::all_of(), llvm::GVNExpression::BasicExpression::allocateOperands(), llvm::VNCoercion::analyzeLoadFromClobberingLoad(), llvm::VNCoercion::analyzeLoadFromClobberingMemInst(), llvm::VNCoercion::analyzeLoadFromClobberingStore(), llvm::any_of(), Arg, assert(), B, llvm::ArrayRef< T >::begin(), llvm::ISD::BR, C, llvm::MCID::Call, llvm::ConstantFoldInstOperands(), llvm::copy(), llvm::dbgs(), llvm::dyn_cast(), E, llvm::SmallVectorImpl< T >::emplace_back(), llvm::empty(), EnableStoreRefinement, F(), llvm::CmpInst::FCMP_OEQ, llvm::CmpInst::FCMP_UNE, From, GEP, llvm::UndefValue::get(), llvm::LoadInst::getAlignment(), getBlockName(), llvm::BranchInst::getCondition(), llvm::VNCoercion::getConstantLoadValueForLoad(), llvm::VNCoercion::getConstantMemInstValueForLoad(), llvm::VNCoercion::getConstantStoreValueForLoad(), llvm::ConstantInt::getFalse(), llvm::CmpInst::getInversePredicate(), llvm::Constant::getNullValue(), llvm::User::getNumOperands(), llvm::Instruction::getNumSuccessors(), llvm::GVNExpression::Expression::getOpcode(), llvm::Instruction::getOpcode(), llvm::GVNExpression::BasicExpression::getOperand(), llvm::User::getOperand(), llvm::Instruction::getParent(), llvm::LoadInst::getPointerOperand(), llvm::StoreInst::getPointerOperand(), llvm::CmpInst::getPredicate(), llvm::Instruction::getSuccessor(), llvm::BranchInst::getSuccessor(), llvm::CmpInst::getSwappedPredicate(), llvm::ConstantInt::getTrue(), llvm::Value::getType(), llvm::Value::getValueID(), llvm::StoreInst::getValueOperand(), I, llvm::CmpInst::ICMP_EQ, llvm::CmpInst::ICMP_NE, if(), llvm::Instruction::isAtomic(), llvm::Instruction::isBinaryOp(), llvm::isCallocLikeFn(), llvm::Instruction::isCommutative(), llvm::BranchInst::isConditional(), isCopyOfAPHI(), isCopyOfPHI(), llvm::CmpInst::isImpliedFalseByMatchingCmp(), llvm::CmpInst::isImpliedTrueByMatchingCmp(), llvm::isMallocLikeFn(), llvm::ConstantInt::isOne(), llvm::LoadInst::isSimple(), llvm::StoreInst::isSimple(), llvm::ConstantInt::isZero(), llvm::AArch64CC::LE, llvm::Intrinsic::lifetime_start, LLVM_DEBUG, llvm_unreachable, llvm::SPII::Load, llvm::make_filter_range(), llvm::RISCVFenceField::O, llvm::User::op_begin(), llvm::User::op_end(), llvm::GVNExpression::BasicExpression::op_push_back(), llvm::User::operands(), P, llvm::SmallVectorTemplateBase< T >::push_back(), llvm::RISCVFenceField::R, llvm::Intrinsic::sadd_with_overflow, llvm::MCID::Select, llvm::GVNExpression::Expression::setOpcode(), llvm::GVNExpression::BasicExpression::setType(), SI, llvm::SimplifyBinOp(), llvm::SimplifyCastInst(), llvm::SimplifyCmpInst(), llvm::SimplifyGEPInst(), llvm::SimplifySelectInst(), llvm::ArrayRef< T >::size(), llvm::Intrinsic::smul_with_overflow, llvm::Intrinsic::ssa_copy, llvm::Intrinsic::ssub_with_overflow, llvm::SPII::Store, std::swap(), llvm::transform(), llvm::Intrinsic::uadd_with_overflow, llvm::Intrinsic::umul_with_overflow, llvm::Value::users(), llvm::Intrinsic::usub_with_overflow, and X.

Referenced by NewGVN::ValueDFS::operator<(), and patchAndReplaceAllUsesWith().

◆ DEBUG_COUNTER() [1/2]

DEBUG_COUNTER	(	VNCounter	,
		"newgvn-vn"	,
		"Controls which instructions are value numbered"
	)

◆ DEBUG_COUNTER() [2/2]

DEBUG_COUNTER	(	PHIOfOpsCounter	,
		"newgvn-phi"	,
		"Controls which instructions we create phi of ops for"
	)

◆ equalsLoadStoreHelper()

template<typename T >

static bool equalsLoadStoreHelper	(	const T &	LHS,
		const Expression &	RHS
	)

static

Definition at line 870 of file NewGVN.cpp.

Referenced by llvm::GVNExpression::LoadExpression::equals(), and llvm::GVNExpression::StoreExpression::equals().

◆ getBlockName()

static std::string getBlockName ( const BasicBlock * B )

static

Definition at line 898 of file NewGVN.cpp.

References assert(), llvm::dyn_cast(), E, and llvm::Instruction::getParent().

Referenced by alwaysAvailable(), okayForPHIOfOps(), and patchAndReplaceAllUsesWith().

◆ getCopyOf()

static Value* getCopyOf ( const Value * V )

static

Definition at line 941 of file NewGVN.cpp.

References llvm::Intrinsic::ssa_copy.

Referenced by isCopyOfAPHI(), and isCopyOfPHI().

◆ INITIALIZE_PASS_BEGIN()

INITIALIZE_PASS_BEGIN	(	NewGVNLegacyPass	,
		"newgvn"	,
		"Global Value Numbering"	,
		false	,
		false
	)

Referenced by patchAndReplaceAllUsesWith().

◆ isCopyOfAPHI()

static bool isCopyOfAPHI ( const Value * V )

static

Definition at line 953 of file NewGVN.cpp.

References getCopyOf(), and llvm::sort().

Referenced by alwaysAvailable().

◆ isCopyOfPHI()

static bool isCopyOfPHI	(	const Value *	V,
		const PHINode *	PN
	)

static

Definition at line 949 of file NewGVN.cpp.

References getCopyOf().

Referenced by alwaysAvailable().

◆ okayForPHIOfOps()

static bool okayForPHIOfOps ( const Instruction * I )

static

Definition at line 2601 of file NewGVN.cpp.

References llvm::Function::args(), llvm::SmallPtrSetImpl< PtrType >::begin(), llvm::SmallPtrSetImplBase::clear(), llvm::SmallVectorImpl< T >::clear(), llvm::Instruction::clone(), llvm::PHINode::Create(), llvm::dbgs(), llvm::tgtok::Def, llvm::Value::deleteValue(), llvm::Value::DoPHITranslation(), llvm::User::dropAllReferences(), llvm::dyn_cast(), E, llvm::SmallVectorBase::empty(), EnablePhiOfOps, llvm::SmallPtrSetImpl< PtrType >::end(), llvm::UndefValue::get(), llvm::MemoryAccess::getBlock(), getBlockName(), getID(), llvm::PHINode::getIncomingBlock(), llvm::PHINode::getIncomingValueForBlock(), llvm::User::getNumOperands(), llvm::Instruction::getParent(), llvm::Value::getType(), llvm::StoreInst::getValueOperand(), I, if(), llvm::SmallPtrSetImpl< PtrType >::insert(), llvm::Instruction::isTerminator(), llvm::Type::isVoidTy(), LLVM_DEBUG, llvm::nodes(), llvm::User::operand_values(), llvm::User::operands(), llvm::SmallVectorImpl< T >::pop_back_val(), llvm::SmallVectorTemplateBase< T >::push_back(), llvm::DebugCounter::shouldExecute(), llvm::size(), and llvm::Value::users().

◆ patchAndReplaceAllUsesWith()

static void patchAndReplaceAllUsesWith	(	Instruction *	I,
		Value *	Repl
	)

static

Definition at line 3700 of file NewGVN.cpp.

References llvm::AnalysisUsage::addPreserved(), llvm::AnalysisUsage::addRequired(), alwaysAvailable(), assert(), llvm::dbgs(), llvm::tgtok::Def, llvm::dyn_cast(), llvm::empty(), llvm::SmallPtrSetImpl< PtrType >::erase(), llvm::Instruction::eraseFromParent(), llvm::UndefValue::get(), getBlockName(), llvm::BasicBlock::getContext(), llvm::Module::getDataLayout(), llvm::PHINode::getIncomingBlock(), llvm::Type::getInt8Ty(), llvm::IntrinsicInst::getIntrinsicID(), llvm::Constant::getNullValue(), llvm::Instruction::getParent(), llvm::GlobalValue::getParent(), llvm::PassRegistry::getPassRegistry(), llvm::Type::getPointerTo(), llvm::BasicBlock::getTerminator(), llvm::Value::getType(), I, llvm::PHINode::incoming_values(), INITIALIZE_PASS_BEGIN(), INITIALIZE_PASS_DEPENDENCY, llvm::initializeNewGVNLegacyPassPass(), llvm::SmallPtrSetImpl< PtrType >::insert(), llvm::Type::isVoidTy(), LLVM_DEBUG, llvm::DenseMapBase< DenseMap< KeyT, ValueT, KeyInfoT, BucketT >, KeyT, ValueT, KeyInfoT, BucketT >::lookup(), llvm::patchReplacementInstruction(), llvm::BasicBlock::rbegin(), llvm::BasicBlock::rend(), llvm::Value::replaceAllUsesWith(), llvm::reverse(), runOnFunction(), llvm::sort(), llvm::Intrinsic::ssa_copy, llvm::Value::use_empty(), and llvm::wouldInstructionBeTriviallyDead().

◆ STATISTIC() [1/11]

STATISTIC	(	NumGVNInstrDeleted	,
		"Number of instructions deleted"
	)

◆ STATISTIC() [2/11]

STATISTIC	(	NumGVNBlocksDeleted	,
		"Number of blocks deleted"
	)

◆ STATISTIC() [3/11]

STATISTIC	(	NumGVNOpsSimplified	,
		"Number of Expressions simplified"
	)

◆ STATISTIC() [4/11]

STATISTIC	(	NumGVNPhisAllSame	,
		"Number of PHIs whos arguments are all the same"
	)

◆ STATISTIC() [5/11]

STATISTIC	(	NumGVNMaxIterations	,
		"Maximum Number of iterations it took to converge GVN"
	)

◆ STATISTIC() [6/11]

STATISTIC	(	NumGVNLeaderChanges	,
		"Number of leader changes"
	)

◆ STATISTIC() [7/11]

STATISTIC	(	NumGVNSortedLeaderChanges	,
		"Number of sorted leader changes"
	)

◆ STATISTIC() [8/11]

STATISTIC	(	NumGVNAvoidedSortedLeaderChanges	,
		"Number of avoided sorted leader changes"
	)

◆ STATISTIC() [9/11]

STATISTIC	(	NumGVNDeadStores	,
		"Number of redundant/dead stores eliminated"
	)

◆ STATISTIC() [10/11]

STATISTIC	(	NumGVNPHIOfOpsCreated	,
		"Number of PHI of ops created"
	)

◆ STATISTIC() [11/11]

STATISTIC	(	NumGVNPHIOfOpsEliminations	,
		"Number of things eliminated using PHI of ops"
	)

Variable Documentation

◆ EnablePhiOfOps

cl::opt<bool> EnablePhiOfOps("enable-phi-of-ops", cl::init(true), cl::Hidden)

static

Currently, the generation "phi of ops" can result in correctness issues.

Referenced by okayForPHIOfOps().

◆ EnableStoreRefinement

cl::opt<bool> EnableStoreRefinement("enable-store-refinement", cl::init(false), cl::Hidden)

static

Referenced by alwaysAvailable().

◆ false

Global Value false

Definition at line 4245 of file NewGVN.cpp.

◆ newgvn

newgvn

Definition at line 4245 of file NewGVN.cpp.

◆ Numbering

Global Value Numbering

Definition at line 4245 of file NewGVN.cpp.

Referenced by llvm::DIEHash::update().

Classes

Namespaces

Macros

Functions

Variables

Detailed Description

Macro Definition Documentation

◆ DEBUG_TYPE

Function Documentation

◆ alwaysAvailable()

◆ DEBUG_COUNTER() [1/2]

◆ DEBUG_COUNTER() [2/2]

◆ equalsLoadStoreHelper()

◆ getBlockName()

◆ getCopyOf()

◆ INITIALIZE_PASS_BEGIN()

◆ isCopyOfAPHI()

◆ isCopyOfPHI()

◆ okayForPHIOfOps()

◆ patchAndReplaceAllUsesWith()

◆ STATISTIC() [1/11]

◆ STATISTIC() [2/11]

◆ STATISTIC() [3/11]

◆ STATISTIC() [4/11]

◆ STATISTIC() [5/11]

◆ STATISTIC() [6/11]

◆ STATISTIC() [7/11]

◆ STATISTIC() [8/11]

◆ STATISTIC() [9/11]

◆ STATISTIC() [10/11]

◆ STATISTIC() [11/11]

Variable Documentation

◆ EnablePhiOfOps

◆ EnableStoreRefinement

◆ false

◆ newgvn

◆ Numbering