Reassociate.cpp File Reference

#include "llvm/Transforms/Scalar.h"
#include "llvm/Constants.h"
#include "llvm/DerivedTypes.h"
#include "llvm/Function.h"
#include "llvm/Instructions.h"
#include "llvm/Pass.h"
#include "llvm/Assembly/Writer.h"
#include "llvm/Support/CFG.h"
#include "llvm/Support/Compiler.h"
#include "llvm/Support/Debug.h"
#include "llvm/ADT/PostOrderIterator.h"
#include "llvm/ADT/Statistic.h"
#include <algorithm>
#include <map>

Include dependency graph for Reassociate.cpp:

Go to the source code of this file.

Defines
#define	DEBUG_TYPE   "reassociate"
Functions
	STATISTIC (NumLinear,"Number of insts linearized")
	STATISTIC (NumChanged,"Number of insts reassociated")
	STATISTIC (NumAnnihil,"Number of expr tree annihilated")
	STATISTIC (NumFactor,"Number of multiplies factored")
bool	operator< (const ValueEntry &LHS, const ValueEntry &RHS)
static void	PrintOps (Instruction *I, const std::vector< ValueEntry > &Ops)
FunctionPass *	llvm::createReassociatePass ()
static bool	isUnmovableInstruction (Instruction *I)
static BinaryOperator *	isReassociableOp (Value *V, unsigned Opcode)
static Instruction *	LowerNegateToMultiply (Instruction *Neg)
static Value *	NegateValue (Value *V, Instruction *BI)
static bool	ShouldBreakUpSubtract (Instruction *Sub)
static Instruction *	BreakUpSubtract (Instruction *Sub)
static Instruction *	ConvertShiftToMul (Instruction *Shl)
static unsigned	FindInOperandList (std::vector< ValueEntry > &Ops, unsigned i, Value *X)
static Value *	EmitAddTreeOfValues (Instruction *I, std::vector< Value * > &Ops)
static void	FindSingleUseMultiplyFactors (Value *V, std::vector< Value * > &Factors)
Variables
static RegisterPass< Reassociate >	X ("reassociate","Reassociate expressions")

---

Define Documentation

#define DEBUG_TYPE   "reassociate"

Definition at line 23 of file Reassociate.cpp.

---

Function Documentation

static Instruction* BreakUpSubtract

(

Instruction *

Sub

)

[static]

BreakUpSubtract - If we have (X-Y), and if either X is an add, or if this is only used by an add, transform this into (X+(0-Y)) to promote better reassociation.

Definition at line 425 of file Reassociate.cpp.

References DOUT, llvm::Instruction::eraseFromParent(), llvm::User::getOperand(), NegateValue(), llvm::Value::replaceAllUsesWith(), and llvm::Value::takeName().

static Instruction* ConvertShiftToMul

(

Instruction *

Shl

)

[static]

ConvertShiftToMul - If this is a shift of a reassociable multiply or is used by one, change this into a multiply by a constant to assist with further reassociation.

Definition at line 448 of file Reassociate.cpp.

References Add(), llvm::Instruction::eraseFromParent(), llvm::User::getOperand(), llvm::Value::getType(), llvm::Value::hasOneUse(), isReassociableOp(), llvm::Value::replaceAllUsesWith(), llvm::Value::takeName(), and llvm::Instruction::use_back().

static Value* EmitAddTreeOfValues	(	Instruction *	I,
		std::vector< Value * > &	Ops
	)			[static]

EmitAddTreeOfValues - Emit a tree of add instructions, summing Ops together and returning the result. Insert the tree before I.

Definition at line 486 of file Reassociate.cpp.

References V1.

static unsigned FindInOperandList	(	std::vector< ValueEntry > &	Ops,
		unsigned	i,
		Value *	X
	)			[static]

Definition at line 470 of file Reassociate.cpp.

static void FindSingleUseMultiplyFactors	(	Value *	V,
		std::vector< Value * > &	Factors
	)			[static]

FindSingleUseMultiplyFactors - If V is a single-use multiply, recursively add its operands as factors, otherwise add V to the list of factors.

Definition at line 526 of file Reassociate.cpp.

References llvm::BinaryOperator::getOpcode(), llvm::User::getOperand(), llvm::Value::hasOneUse(), and llvm::Value::use_empty().

static BinaryOperator* isReassociableOp	(	Value *	V,
		unsigned	Opcode
	)			[static]

isReassociableOp - Return true if V is an instruction of the specified opcode and if it only has one use.

Definition at line 188 of file Reassociate.cpp.

References getOpcode(), llvm::Value::hasOneUse(), and llvm::Value::use_empty().

Referenced by ConvertShiftToMul(), and ShouldBreakUpSubtract().

static bool isUnmovableInstruction

(

Instruction *

I

)

[static]

Definition at line 117 of file Reassociate.cpp.

References Call, llvm::Instruction::getOpcode(), Load, Malloc, and PHI.

static Instruction* LowerNegateToMultiply

(

Instruction *

Neg

)

[static]

LowerNegateToMultiply - Replace 0-X with X*-1.

Definition at line 197 of file Reassociate.cpp.

References llvm::Instruction::eraseFromParent(), llvm::User::getOperand(), llvm::Value::getType(), llvm::Value::replaceAllUsesWith(), and llvm::Value::takeName().

static Value* NegateValue	(	Value *	V,
		Instruction *	BI
	)			[static]

Definition at line 367 of file Reassociate.cpp.

References Add(), llvm::Value::getName(), llvm::Value::hasOneUse(), and llvm::Value::setName().

Referenced by BreakUpSubtract().

bool @817::operator<	(	const ValueEntry &	LHS,
		const ValueEntry &	RHS
	)			[inline, static]

Definition at line 51 of file Reassociate.cpp.

static void PrintOps	(	Instruction *	I,
		const std::vector< ValueEntry > &	Ops
	)			[static]

PrintOps - Print out the expression identified in the Ops list.

Definition at line 59 of file Reassociate.cpp.

References llvm::cerr(), and llvm::WriteAsOperand().

static bool ShouldBreakUpSubtract

(

Instruction *

Sub

)

[static]

ShouldBreakUpSubtract - Return true if we should break up this subtract of X-Y into (X + -Y).

Definition at line 401 of file Reassociate.cpp.

References Add(), llvm::User::getOperand(), llvm::Value::hasOneUse(), isReassociableOp(), and llvm::Instruction::use_back().

STATISTIC	(	NumFactor	,
		"Number of multiplies factored"
	)

STATISTIC	(	NumAnnihil	,
		"Number of expr tree annihilated"
	)

STATISTIC	(	NumChanged	,
		"Number of insts reassociated"
	)

STATISTIC	(	NumLinear	,
		"Number of insts linearized"
	)

---

Variable Documentation

char ID [static]

Definition at line 76 of file Reassociate.cpp.

bool MadeChange

Definition at line 74 of file Reassociate.cpp.

Value* Op

Definition at line 48 of file Reassociate.cpp.

unsigned Rank

Definition at line 47 of file Reassociate.cpp.

std::map<BasicBlock*, unsigned> RankMap

Definition at line 72 of file Reassociate.cpp.

std::map<Value*, unsigned> ValueRankMap

Definition at line 73 of file Reassociate.cpp.

RegisterPass<Reassociate> X("reassociate","Reassociate expressions") [static]