LoopUnswitch.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/Analysis/ConstantFolding.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/LoopPass.h"
#include "llvm/Analysis/Dominators.h"
#include "llvm/Transforms/Utils/Cloning.h"
#include "llvm/Transforms/Utils/Local.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Compiler.h"
#include "llvm/Support/Debug.h"
#include <algorithm>
#include <set>

Include dependency graph for LoopUnswitch.cpp:

Go to the source code of this file.

Defines
#define	DEBUG_TYPE   "loop-unswitch"
Functions
	STATISTIC (NumBranches,"Number of branches unswitched")
	STATISTIC (NumSwitches,"Number of switches unswitched")
	STATISTIC (NumSelects,"Number of selects unswitched")
	STATISTIC (NumTrivial,"Number of unswitches that are trivial")
	STATISTIC (NumSimplify,"Number of simplifications of unswitched code")
Pass *	llvm::createLoopUnswitchPass (bool OptimizeForSize=false)
static Value *	FindLIVLoopCondition (Value *Cond, Loop *L, bool &Changed)
static bool	isTrivialLoopExitBlockHelper (Loop *L, BasicBlock *BB, BasicBlock *&ExitBB, std::set< BasicBlock * > &Visited)
static BasicBlock *	isTrivialLoopExitBlock (Loop *L, BasicBlock *BB)
static void	RemapInstruction (Instruction *I, DenseMap< const Value *, Value * > &ValueMap)
static Loop *	CloneLoop (Loop *L, Loop *PL, DenseMap< const Value *, Value * > &VM, LoopInfo *LI, LPPassManager *LPM)
static void	RemoveFromWorklist (Instruction *I, std::vector< Instruction * > &Worklist)
static void	ReplaceUsesOfWith (Instruction *I, Value *V, std::vector< Instruction * > &Worklist, Loop *L, LPPassManager *LPM)
Variables
static cl::opt< unsigned >	Threshold ("loop-unswitch-threshold", cl::desc("Max loop size to unswitch"), cl::init(10), cl::Hidden)
static RegisterPass< LoopUnswitch >	X ("loop-unswitch","Unswitch loops")

---

Define Documentation

#define DEBUG_TYPE   "loop-unswitch"

Definition at line 29 of file LoopUnswitch.cpp.

---

Function Documentation

static Loop* CloneLoop	(	Loop *	L,
		Loop *	PL,
		DenseMap< const Value *, Value * > &	VM,
		LoopInfo *	LI,
		LPPassManager *	LPM
	)			[static]

CloneLoop - Recursively clone the specified loop and all of its children, mapping the blocks with the specified map.

Definition at line 480 of file LoopUnswitch.cpp.

References llvm::LoopBase< BlockT >::addBasicBlockToLoop(), llvm::LoopBase< BlockT >::begin(), llvm::LoopBase< BlockT >::block_begin(), llvm::LoopBase< BlockT >::block_end(), E, llvm::LoopBase< BlockT >::end(), llvm::LoopInfo::getBase(), llvm::LoopInfo::getLoopFor(), llvm::LPPassManager::insertLoop(), and llvm::GC::Loop.

static Value* FindLIVLoopCondition	(	Value *	Cond,
		Loop *	L,
		bool &	Changed
	)			[static]

FindLIVLoopCondition - Cond is a condition that occurs in L. If it is invariant in the loop, or has an invariant piece, return the invariant. Otherwise, return null.

Definition at line 165 of file LoopUnswitch.cpp.

References And(), llvm::LoopBase< BlockT >::isLoopInvariant(), LHS, llvm::APIntOps::Or(), and RHS.

static BasicBlock* isTrivialLoopExitBlock	(	Loop *	L,
		BasicBlock *	BB
	)			[static]

isTrivialLoopExitBlock - Return true if the specified block unconditionally leads to an exit from the specified loop, and has no side-effects in the process. If so, return the block that is exited to, otherwise return null.

Definition at line 312 of file LoopUnswitch.cpp.

References llvm::LoopBase< BlockT >::getHeader(), isTrivialLoopExitBlockHelper(), and Visited.

static bool isTrivialLoopExitBlockHelper	(	Loop *	L,
		BasicBlock *	BB,
		BasicBlock *&	ExitBB,
		std::set< BasicBlock * > &	Visited
	)			[static]

isTrivialLoopExitBlock - Check to see if all paths from BB either: 1. Exit the loop with no side effects. 2. Branch to the latch block with no side-effects.

If these conditions are true, we return true and set ExitBB to the block we exit through.

Definition at line 279 of file LoopUnswitch.cpp.

References llvm::BasicBlock::begin(), llvm::LoopBase< BlockT >::contains(), E, llvm::BasicBlock::end(), llvm::succ_begin(), and llvm::succ_end().

Referenced by isTrivialLoopExitBlock().

static void RemapInstruction	(	Instruction *	I,
		DenseMap< const Value *, Value * > &	ValueMap
	)			[inline, static]

Definition at line 468 of file LoopUnswitch.cpp.

References E, llvm::DenseMap< KeyT, ValueT, KeyInfoT, ValueInfoT >::end(), llvm::DenseMap< KeyT, ValueT, KeyInfoT, ValueInfoT >::find(), llvm::User::getNumOperands(), llvm::User::getOperand(), Op, and llvm::User::setOperand().

static void RemoveFromWorklist	(	Instruction *	I,
		std::vector< Instruction * > &	Worklist
	)			[static]

RemoveFromWorklist - Remove all instances of I from the worklist vector specified.

Definition at line 732 of file LoopUnswitch.cpp.

References Offset.

Referenced by ReplaceUsesOfWith().

static void ReplaceUsesOfWith	(	Instruction *	I,
		Value *	V,
		std::vector< Instruction * > &	Worklist,
		Loop *	L,
		LPPassManager *	LPM
	)			[static]

ReplaceUsesOfWith - When we find that I really equals V, remove I from the program, replacing all uses with V and update the worklist.

Definition at line 745 of file LoopUnswitch.cpp.

References llvm::LPPassManager::deleteSimpleAnalysisValue(), DOUT, E, and RemoveFromWorklist().

STATISTIC	(	NumSimplify	,
		"Number of simplifications of unswitched code"
	)

STATISTIC	(	NumTrivial	,
		"Number of unswitches that are trivial"
	)

STATISTIC	(	NumSelects	,
		"Number of selects unswitched"
	)

STATISTIC	(	NumSwitches	,
		"Number of switches unswitched"
	)

STATISTIC	(	NumBranches	,
		"Number of branches unswitched"
	)

---

Variable Documentation

Loop* currentLoop

Definition at line 75 of file LoopUnswitch.cpp.

DominanceFrontier* DF

Definition at line 76 of file LoopUnswitch.cpp.

DominatorTree* DT

Definition at line 77 of file LoopUnswitch.cpp.

char ID [static]

Definition at line 89 of file LoopUnswitch.cpp.

LoopInfo* LI

Definition at line 64 of file LoopUnswitch.cpp.

std::vector<BasicBlock*> LoopBlocks

Definition at line 84 of file LoopUnswitch.cpp.

Referenced by llvm::UnrollLoop().

BasicBlock* loopHeader

Definition at line 78 of file LoopUnswitch.cpp.

BasicBlock* loopPreheader

Definition at line 79 of file LoopUnswitch.cpp.

std::vector<Loop*> LoopProcessWorklist

Definition at line 69 of file LoopUnswitch.cpp.

LPPassManager* LPM

Definition at line 65 of file LoopUnswitch.cpp.

std::vector<BasicBlock*> NewBlocks

Definition at line 86 of file LoopUnswitch.cpp.

Referenced by llvm::CloneLoop(), and llvm::UnrollLoop().

bool OptimizeForSize

Definition at line 72 of file LoopUnswitch.cpp.

bool redoLoop

Definition at line 73 of file LoopUnswitch.cpp.

cl::opt<unsigned> Threshold("loop-unswitch-threshold", cl::desc("Max loop size to unswitch"), cl::init(10), cl::Hidden) [static]

SmallPtrSet<Value *,8> UnswitchedVals

Definition at line 70 of file LoopUnswitch.cpp.

RegisterPass<LoopUnswitch> X("loop-unswitch","Unswitch loops") [static]