GVNSink.cpp File Reference

This pass attempts to sink instructions into successors, reducing static instruction count and enabling if-conversion. More...

#include "llvm/ADT/ArrayRef.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/DenseMapInfo.h"
#include "llvm/ADT/DenseSet.h"
#include "llvm/ADT/Hashing.h"
#include "llvm/ADT/None.h"
#include "llvm/ADT/Optional.h"
#include "llvm/ADT/PostOrderIterator.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/StringExtras.h"
#include "llvm/Analysis/GlobalsModRef.h"
#include "llvm/Transforms/Utils/Local.h"
#include "llvm/IR/BasicBlock.h"
#include "llvm/IR/CFG.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/InstrTypes.h"
#include "llvm/IR/Instruction.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/PassManager.h"
#include "llvm/IR/Type.h"
#include "llvm/IR/Use.h"
#include "llvm/IR/Value.h"
#include "llvm/Pass.h"
#include "llvm/Support/Allocator.h"
#include "llvm/Support/ArrayRecycler.h"
#include "llvm/Support/AtomicOrdering.h"
#include "llvm/Support/Casting.h"
#include "llvm/Support/Compiler.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Transforms/Scalar.h"
#include "llvm/Transforms/Scalar/GVN.h"
#include "llvm/Transforms/Scalar/GVNExpression.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
#include <algorithm>
#include <cassert>
#include <cstddef>
#include <cstdint>
#include <iterator>
#include <utility>

Include dependency graph for GVNSink.cpp:

Go to the source code of this file.

Namespaces
	llvm
	This class represents lattice values for constants.
	llvm::GVNExpression

Macros
#define	DEBUG_TYPE   "gvn-sink"

Functions
	STATISTIC (NumRemoved, "Number of instructions removed")
	INITIALIZE_PASS_BEGIN (GVNSinkLegacyPass, "gvn-sink", "Early GVN sinking of Expressions", false, false) INITIALIZE_PASS_END(GVNSinkLegacyPass

Variables
gvn	sink
	When an instruction is found to only be used outside of the loop, this function moves it to the exit blocks and patches up SSA form as needed. More...
gvn Early GVN sinking of	Expressions
gvn Early GVN sinking of	false

Detailed Description

This pass attempts to sink instructions into successors, reducing static instruction count and enabling if-conversion.

We use a variant of global value numbering to decide what can be sunk. Consider:

[ a1 = add i32 b, 1 ] [ c1 = add i32 d, 1 ] [ a2 = xor i32 a1, 1 ] [ c2 = xor i32 c1, 1 ] \ / [ e = phi i32 a2, c2 ] [ add i32 e, 4 ]

GVN would number a1 and c1 differently because they compute different results - the VN of an instruction is a function of its opcode and the transitive closure of its operands. This is the key property for hoisting and CSE.

What we want when sinking however is for a numbering that is a function of the uses of an instruction, which allows us to answer the question "if I replace a1 with c1, will it contribute in an equivalent way to all successive instructions?". The PostValueTable class in GVN provides this mapping.

Definition in file GVNSink.cpp.

Macro Definition Documentation

DEBUG_TYPE

#define DEBUG_TYPE   "gvn-sink"

Definition at line 84 of file GVNSink.cpp.

Function Documentation

INITIALIZE_PASS_BEGIN()

INITIALIZE_PASS_BEGIN	(	GVNSinkLegacyPass	,
		"gvn-sink"	,
		"Early GVN sinking of Expressions"	,
		false	,
		false
	)

Referenced by llvm::GVNSinkPass::run().

STATISTIC()

STATISTIC	(	NumRemoved	,
		"Number of instructions removed"
	)

Variable Documentation

Expressions

gvn Early GVN sinking of Expressions

Definition at line 920 of file GVNSink.cpp.

false

gvn Early GVN sinking of false

Definition at line 920 of file GVNSink.cpp.

sink

static bool sink

When an instruction is found to only be used outside of the loop, this function moves it to the exit blocks and patches up SSA form as needed.

This method is guaranteed to remove the original instruction from its position, and may either delete it or move it to outside of the loop.

Definition at line 920 of file GVNSink.cpp.