LLVM API Documentation

LoopUnswitch.cpp File Reference

#include "llvm/Transforms/Scalar.h"
#include "llvm/Constants.h"
#include "llvm/Function.h"
#include "llvm/Instructions.h"
#include "llvm/Analysis/LoopInfo.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/PostOrderIterator.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/CommandLine.h"
#include <algorithm>
#include <iostream>
#include <set>

Include dependency graph for LoopUnswitch.cpp:

Go to the source code of this file.

Defines

#define DEBUG_TYPE   "loop-unswitch"

Functions

FunctionPassllvm::createLoopUnswitchPass ()
static ValueFindLIVLoopCondition (Value *Cond, Loop *L, bool &Changed)
static bool isTrivialLoopExitBlockHelper (Loop *L, BasicBlock *BB, BasicBlock *&ExitBB, std::set< BasicBlock * > &Visited)
static BasicBlockisTrivialLoopExitBlock (Loop *L, BasicBlock *BB)
static bool IsTrivialUnswitchCondition (Loop *L, Value *Cond, Constant **Val=0, BasicBlock **LoopExit=0)
static void RemapInstruction (Instruction *I, std::map< const Value *, Value * > &ValueMap)
static LoopCloneLoop (Loop *L, Loop *PL, std::map< const Value *, Value * > &VM, LoopInfo *LI)
static void EmitPreheaderBranchOnCondition (Value *LIC, Constant *Val, BasicBlock *TrueDest, BasicBlock *FalseDest, Instruction *InsertPt)
static void RemoveFromWorklist (Instruction *I, std::vector< Instruction * > &Worklist)
static void ReplaceUsesOfWith (Instruction *I, Value *V, std::vector< Instruction * > &Worklist)

Variables

Statistic NumBranches ("loop-unswitch","Number of branches unswitched")
Statistic NumSwitches ("loop-unswitch","Number of switches unswitched")
Statistic NumSelects ("loop-unswitch","Number of selects unswitched")
Statistic NumTrivial ("loop-unswitch","Number of unswitches that are trivial")
Statistic NumSimplify ("loop-unswitch","Number of simplifications of unswitched code")
cl::opt< unsigned > Threshold ("loop-unswitch-threshold", cl::desc("Max loop size to unswitch"), cl::init(10), cl::Hidden)
RegisterOpt< 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,
std::map< const Value *, Value * > &  VM,
LoopInfo LI 
) [static]

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

Definition at line 457 of file LoopUnswitch.cpp.

References llvm::Loop::addChildLoop(), llvm::LoopInfo::addTopLevelLoop(), llvm::Loop::begin(), llvm::Loop::block_begin(), llvm::Loop::block_end(), E, llvm::Loop::end(), llvm::LoopInfo::getLoopFor(), and LI.

static void EmitPreheaderBranchOnCondition ( Value LIC,
Constant Val,
BasicBlock TrueDest,
BasicBlock FalseDest,
Instruction InsertPt 
) [static]

EmitPreheaderBranchOnCondition - Emit a conditional branch on two values if LIC == Val, branch to TrueDst, otherwise branch to FalseDest. Insert the code immediately before InsertPt.

Definition at line 482 of file LoopUnswitch.cpp.

References True, and Val.

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 135 of file LoopUnswitch.cpp.

References llvm::Loop::isLoopInvariant().

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 251 of file LoopUnswitch.cpp.

References BB, llvm::Loop::getHeader(), isTrivialLoopExitBlockHelper(), and Visited.

Referenced by IsTrivialUnswitchCondition().

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 218 of file LoopUnswitch.cpp.

References BB, llvm::BasicBlock::begin(), llvm::Loop::contains(), E, llvm::BasicBlock::end(), llvm::succ_begin(), and llvm::succ_end().

Referenced by isTrivialLoopExitBlock().

static bool IsTrivialUnswitchCondition ( Loop L,
Value Cond,
Constant **  Val = 0,
BasicBlock **  LoopExit = 0 
) [static]

IsTrivialUnswitchCondition - Check to see if this unswitch condition is trivial: that is, that the condition controls whether or not the loop does anything at all. If this is a trivial condition, unswitching produces no code duplications (equivalently, it produces a simpler loop and a new empty loop, which gets deleted).

If this is a trivial condition, return true, otherwise return false. When returning true, this sets Cond and Val to the condition that controls the trivial condition: when Cond dynamically equals Val, the loop is known to exit. Finally, this sets LoopExit to the BB that the loop exits to when Cond == Val.

Definition at line 272 of file LoopUnswitch.cpp.

References llvm::BasicBlock::begin(), E, llvm::BasicBlock::end(), False, llvm::Loop::getHeader(), llvm::BasicBlock::getTerminator(), isTrivialLoopExitBlock(), True, and Val.

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

Definition at line 445 of file LoopUnswitch.cpp.

References E, 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 715 of file LoopUnswitch.cpp.

References Offset.

Referenced by ReplaceUsesOfWith().

static void ReplaceUsesOfWith ( Instruction I,
Value V,
std::vector< Instruction * > &  Worklist 
) [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 728 of file LoopUnswitch.cpp.

References DEBUG, E, llvm::Instruction::eraseFromParent(), llvm::User::getNumOperands(), llvm::User::getOperand(), NumSimplify, RemoveFromWorklist(), llvm::Value::replaceAllUsesWith(), llvm::Value::use_begin(), llvm::Value::use_end(), and V.


Variable Documentation

LoopInfo* LI

Definition at line 60 of file LoopUnswitch.cpp.

std::vector<Loop*> LoopProcessWorklist

Definition at line 63 of file LoopUnswitch.cpp.

Statistic NumBranches("loop-unswitch","Number of branches unswitched") [static]

Statistic NumSelects("loop-unswitch","Number of selects unswitched") [static]

Statistic NumSimplify("loop-unswitch","Number of simplifications of unswitched code") [static]

Referenced by ReplaceUsesOfWith().

Statistic NumSwitches("loop-unswitch","Number of switches unswitched") [static]

Statistic NumTrivial("loop-unswitch","Number of unswitches that are trivial") [static]

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

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