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/DenseSet.h"
#include "llvm/ADT/Hashing.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/Analysis/GlobalsModRef.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/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/GVN.h"
#include "llvm/Transforms/Scalar/GVNExpression.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
#include "llvm/Transforms/Utils/Local.h"
#include "llvm/Transforms/Utils/LockstepReverseIterator.h"
#include <cassert>
#include <cstddef>
#include <cstdint>
#include <iterator>
#include <utility>

Go to the source code of this file.

Classes
struct	llvm::DenseMapInfo< ModelledPHI >

Macros
#define	DEBUG_TYPE   "gvn-sink"

Typedefs
using	ModelledPHISet = DenseSet<ModelledPHI>

Functions
	STATISTIC (NumRemoved, "Number of instructions removed")
static bool	isMemoryInst (const Instruction *I)
static raw_ostream &	operator<< (raw_ostream &OS, const SinkingInstructionCandidate &C)

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 78 of file GVNSink.cpp.

Typedef Documentation

ModelledPHISet

using ModelledPHISet = DenseSet<ModelledPHI>

Definition at line 275 of file GVNSink.cpp.

Function Documentation

isMemoryInst()

bool isMemoryInst ( const Instruction * I )

static

Definition at line 87 of file GVNSink.cpp.

References llvm::cast(), I, and llvm::isa().

operator<<()

raw_ostream & operator<< ( raw_ostream & OS, const SinkingInstructionCandidate & C )

static

Definition at line 249 of file GVNSink.cpp.

References llvm::CallingConv::C.

STATISTIC()

STATISTIC	(	NumRemoved	,
		"Number of instructions removed"	)