LLVM  8.0.0svn
Namespaces | Macros | Functions | Variables
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
 Compute iterated dominance frontiers using a linear time algorithm.
 
 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.