LLVM API Documentation

Utils/SimplifyCFG.cpp File Reference

#include "llvm/Transforms/Utils/Local.h"
#include "llvm/Constants.h"
#include "llvm/Instructions.h"
#include "llvm/Type.h"
#include "llvm/Support/CFG.h"
#include "llvm/Support/Debug.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
#include <algorithm>
#include <functional>
#include <set>
#include <map>
#include <iostream>

Include dependency graph for Utils/SimplifyCFG.cpp:

Go to the source code of this file.

Defines

#define DEBUG_TYPE   "simplifycfg"

Functions

static bool SafeToMergeTerminators (TerminatorInst *SI1, TerminatorInst *SI2)
static void AddPredecessorToBlock (BasicBlock *Succ, BasicBlock *NewPred, BasicBlock *ExistPred)
static bool CanPropagatePredecessorsForPHIs (BasicBlock *BB, BasicBlock *Succ)
static bool TryToSimplifyUncondBranchFromEmptyBlock (BasicBlock *BB, BasicBlock *Succ)
static ValueGetIfCondition (BasicBlock *BB, BasicBlock *&IfTrue, BasicBlock *&IfFalse)
static bool DominatesMergePoint (Value *V, BasicBlock *BB, std::set< Instruction * > *AggressiveInsts)
static ValueGatherConstantSetEQs (Value *V, std::vector< ConstantInt * > &Values)
static ValueGatherConstantSetNEs (Value *V, std::vector< ConstantInt * > &Values)
static bool GatherValueComparisons (Instruction *Cond, Value *&CompVal, std::vector< ConstantInt * > &Values)
static void ErasePossiblyDeadInstructionTree (Instruction *I)
static ValueisValueEqualityComparison (TerminatorInst *TI)
static BasicBlockGetValueEqualityComparisonCases (TerminatorInst *TI, std::vector< std::pair< ConstantInt *, BasicBlock * > > &Cases)
static void EliminateBlockCases (BasicBlock *BB, std::vector< std::pair< ConstantInt *, BasicBlock * > > &Cases)
static bool ValuesOverlap (std::vector< std::pair< ConstantInt *, BasicBlock * > > &C1, std::vector< std::pair< ConstantInt *, BasicBlock * > > &C2)
static bool SimplifyEqualityComparisonWithOnlyPredecessor (TerminatorInst *TI, BasicBlock *Pred)
static bool FoldValueComparisonIntoPredecessors (TerminatorInst *TI)
static bool HoistThenElseCodeToIf (BranchInst *BI)
static bool BlockIsSimpleEnoughToThreadThrough (BasicBlock *BB)
static bool FoldCondBranchOnPHI (BranchInst *BI)
static bool FoldTwoEntryPHINode (PHINode *PN)
bool llvm::SimplifyCFG (BasicBlock *BB)


Define Documentation

#define DEBUG_TYPE   "simplifycfg"

Definition at line 14 of file Utils/SimplifyCFG.cpp.


Function Documentation

static void AddPredecessorToBlock ( BasicBlock Succ,
BasicBlock NewPred,
BasicBlock ExistPred 
) [static]

AddPredecessorToBlock - Update PHI nodes in Succ to indicate that there will now be entries in it from the 'NewPred' block. The values that will be flowing into the PHI nodes will be the same as those coming in from ExistPred, an existing predecessor of Succ.

Definition at line 59 of file Utils/SimplifyCFG.cpp.

References llvm::BasicBlock::begin(), llvm::succ_begin(), llvm::succ_end(), and V.

Referenced by FoldValueComparisonIntoPredecessors(), HoistThenElseCodeToIf(), and llvm::SimplifyCFG().

static bool BlockIsSimpleEnoughToThreadThrough ( BasicBlock BB  )  [static]

BlockIsSimpleEnoughToThreadThrough - Return true if we can thread a branch across this block.

Definition at line 902 of file Utils/SimplifyCFG.cpp.

References BB, llvm::BasicBlock::begin(), E, llvm::BasicBlock::getTerminator(), and U.

Referenced by FoldCondBranchOnPHI(), and llvm::SimplifyCFG().

static bool CanPropagatePredecessorsForPHIs ( BasicBlock BB,
BasicBlock Succ 
) [static]

Definition at line 77 of file Utils/SimplifyCFG.cpp.

References BB, llvm::BasicBlock::begin(), E, llvm::BasicBlock::front(), llvm::BasicBlock::getSinglePredecessor(), PI, llvm::pred_begin(), llvm::pred_end(), and llvm::succ_begin().

Referenced by TryToSimplifyUncondBranchFromEmptyBlock().

static bool DominatesMergePoint ( Value V,
BasicBlock BB,
std::set< Instruction * > *  AggressiveInsts 
) [static]

Definition at line 323 of file Utils/SimplifyCFG.cpp.

References BB, llvm::BasicBlock::begin(), llvm::User::getNumOperands(), llvm::Instruction::getOpcode(), llvm::User::getOperand(), llvm::Instruction::getParent(), llvm::BasicBlock::getTerminator(), llvm::SPII::Load, and V.

Referenced by FoldTwoEntryPHINode().

static void EliminateBlockCases ( BasicBlock BB,
std::vector< std::pair< ConstantInt *, BasicBlock * > > &  Cases 
) [static]

Definition at line 517 of file Utils/SimplifyCFG.cpp.

References BB, and second.

Referenced by SimplifyEqualityComparisonWithOnlyPredecessor().

static void ErasePossiblyDeadInstructionTree ( Instruction I  )  [static]

ErasePossiblyDeadInstructionTree - If the specified instruction is dead and has no side effects, nuke it. If it uses any instructions that become dead because the instruction is now gone, nuke them too.

Definition at line 461 of file Utils/SimplifyCFG.cpp.

References llvm::BasicBlock::getInstList(), llvm::Instruction::getParent(), llvm::isInstructionTriviallyDead(), llvm::User::op_begin(), and llvm::User::op_end().

Referenced by FoldValueComparisonIntoPredecessors(), llvm::SimplifyCFG(), and SimplifyEqualityComparisonWithOnlyPredecessor().

static bool FoldCondBranchOnPHI ( BranchInst BI  )  [static]

FoldCondBranchOnPHI - If we have a conditional branch on a PHI node value that is defined in the same block as the branch and if any PHI entries are constants, thread edges corresponding to that entry to be branches to their ultimate destination.

Definition at line 929 of file Utils/SimplifyCFG.cpp.

References llvm::PHINode::addIncoming(), llvm::ISD::BasicBlock, BB, llvm::BasicBlock::begin(), BlockIsSimpleEnoughToThreadThrough(), C, llvm::ConstantFoldInstruction(), llvm::Instruction::eraseFromParent(), llvm::BranchInst::getCondition(), llvm::PHINode::getIncomingBlock(), llvm::PHINode::getIncomingValue(), llvm::PHINode::getIncomingValueForBlock(), llvm::BasicBlock::getInstList(), llvm::Value::getName(), llvm::PHINode::getNumIncomingValues(), llvm::User::getNumOperands(), llvm::TerminatorInst::getNumSuccessors(), llvm::User::getOperand(), llvm::BasicBlock::getParent(), llvm::Instruction::getParent(), llvm::TerminatorInst::getSuccessor(), llvm::BranchInst::getSuccessor(), llvm::BasicBlock::getTerminator(), llvm::Value::getType(), llvm::Value::hasOneUse(), PI, llvm::BasicBlock::removePredecessor(), llvm::Value::replaceAllUsesWith(), llvm::Value::setName(), llvm::User::setOperand(), llvm::TerminatorInst::setSuccessor(), and V.

Referenced by llvm::SimplifyCFG().

static bool FoldTwoEntryPHINode ( PHINode PN  )  [static]

FoldTwoEntryPHINode - Given a BB that starts with the specified two-entry PHI node, see if we can eliminate it.

Definition at line 1027 of file Utils/SimplifyCFG.cpp.

References BB, llvm::BasicBlock::begin(), DEBUG, DominatesMergePoint(), GetIfCondition(), llvm::PHINode::getIncomingBlock(), llvm::PHINode::getIncomingValue(), llvm::BasicBlock::getInstList(), llvm::Value::getName(), llvm::Instruction::getParent(), llvm::BasicBlock::getTerminator(), llvm::Value::getType(), Name, llvm::pred_begin(), llvm::Value::replaceAllUsesWith(), and llvm::Value::setName().

Referenced by llvm::SimplifyCFG().

static bool FoldValueComparisonIntoPredecessors ( TerminatorInst TI  )  [static]

Definition at line 688 of file Utils/SimplifyCFG.cpp.

References llvm::SwitchInst::addCase(), AddPredecessorToBlock(), llvm::ISD::BasicBlock, BB, Changed, E, ErasePossiblyDeadInstructionTree(), first, llvm::SwitchInst::getNumSuccessors(), llvm::BasicBlock::getParent(), llvm::Instruction::getParent(), llvm::SwitchInst::getSuccessor(), GetValueEqualityComparisonCases(), isValueEqualityComparison(), llvm::pred_begin(), llvm::pred_end(), llvm::BasicBlock::removePredecessor(), SafeToMergeTerminators(), second, llvm::SwitchInst::setSuccessor(), and llvm::BasicBlock::size().

Referenced by llvm::SimplifyCFG().

static Value* GatherConstantSetEQs ( Value V,
std::vector< ConstantInt * > &  Values 
) [static]

Definition at line 389 of file Utils/SimplifyCFG.cpp.

References C, llvm::Instruction::getOpcode(), llvm::User::getOperand(), Inst, and V.

Referenced by GatherValueComparisons().

static Value* GatherConstantSetNEs ( Value V,
std::vector< ConstantInt * > &  Values 
) [static]

Definition at line 411 of file Utils/SimplifyCFG.cpp.

References C, llvm::Instruction::getOpcode(), llvm::User::getOperand(), llvm::Value::getType(), Inst, and V.

Referenced by GatherValueComparisons().

static bool GatherValueComparisons ( Instruction Cond,
Value *&  CompVal,
std::vector< ConstantInt * > &  Values 
) [static]

GatherValueComparisons - If the specified Cond is an 'and' or 'or' of a bunch of comparisons of one value against constants, return the value and the constants being compared.

Definition at line 440 of file Utils/SimplifyCFG.cpp.

References GatherConstantSetEQs(), GatherConstantSetNEs(), and llvm::Instruction::getOpcode().

Referenced by llvm::SimplifyCFG().

static Value* GetIfCondition ( BasicBlock BB,
BasicBlock *&  IfTrue,
BasicBlock *&  IfFalse 
) [static]

GetIfCondition - Given a basic block (BB) with two predecessors (and presumably PHI nodes in it), check to see if the merge at this block is due to an "if condition". If so, return the boolean condition that determines which entry into BB will be taken. Also, return by references the block that will be entered from if the condition is true, and the block that will be entered if the condition is false.

Definition at line 232 of file Utils/SimplifyCFG.cpp.

References BB, llvm::BranchInst::getCondition(), llvm::BranchInst::getSuccessor(), llvm::BasicBlock::getTerminator(), llvm::BranchInst::isConditional(), llvm::pred_begin(), and llvm::pred_end().

Referenced by FoldTwoEntryPHINode().

static BasicBlock* GetValueEqualityComparisonCases ( TerminatorInst TI,
std::vector< std::pair< ConstantInt *, BasicBlock * > > &  Cases 
) [static]

Definition at line 496 of file Utils/SimplifyCFG.cpp.

References llvm::BranchInst::getCondition(), and llvm::BranchInst::getSuccessor().

Referenced by FoldValueComparisonIntoPredecessors(), and SimplifyEqualityComparisonWithOnlyPredecessor().

static bool HoistThenElseCodeToIf ( BranchInst BI  )  [static]

HoistThenElseCodeToIf - Given a conditional branch that goes to BB1 and BB2, hoist any common code in the two blocks up into the branch block. The caller of this function guarantees that BI's block dominates BB1 and BB2.

Definition at line 819 of file Utils/SimplifyCFG.cpp.

References AddPredecessorToBlock(), llvm::BasicBlock::begin(), llvm::Instruction::clone(), E, llvm::Instruction::eraseFromParent(), llvm::BranchInst::getCondition(), llvm::BasicBlock::getInstList(), llvm::Value::getName(), llvm::Instruction::getOpcode(), llvm::Instruction::getParent(), llvm::BranchInst::getSuccessor(), llvm::Value::getType(), llvm::Instruction::isIdenticalTo(), llvm::Value::replaceAllUsesWith(), llvm::Value::setName(), llvm::succ_begin(), and llvm::succ_end().

Referenced by llvm::SimplifyCFG().

static Value* isValueEqualityComparison ( TerminatorInst TI  )  [static]

Definition at line 473 of file Utils/SimplifyCFG.cpp.

References llvm::pred_begin(), and llvm::pred_end().

Referenced by FoldValueComparisonIntoPredecessors(), llvm::SimplifyCFG(), and SimplifyEqualityComparisonWithOnlyPredecessor().

static bool SafeToMergeTerminators ( TerminatorInst SI1,
TerminatorInst SI2 
) [static]

SafeToMergeTerminators - Return true if it is safe to merge these two terminator instructions together.

Definition at line 32 of file Utils/SimplifyCFG.cpp.

References E, llvm::Instruction::getParent(), llvm::succ_begin(), and llvm::succ_end().

Referenced by FoldValueComparisonIntoPredecessors(), and llvm::SimplifyCFG().

static bool SimplifyEqualityComparisonWithOnlyPredecessor ( TerminatorInst TI,
BasicBlock Pred 
) [static]

Definition at line 567 of file Utils/SimplifyCFG.cpp.

References DEBUG, EliminateBlockCases(), ErasePossiblyDeadInstructionTree(), first, llvm::SwitchInst::getCaseValue(), llvm::SwitchInst::getNumCases(), llvm::Instruction::getParent(), llvm::SwitchInst::getSuccessor(), llvm::BasicBlock::getTerminator(), GetValueEqualityComparisonCases(), isValueEqualityComparison(), NI, llvm::SwitchInst::removeCase(), llvm::BasicBlock::removePredecessor(), second, llvm::succ_begin(), llvm::succ_end(), and ValuesOverlap().

Referenced by llvm::SimplifyCFG().

static bool TryToSimplifyUncondBranchFromEmptyBlock ( BasicBlock BB,
BasicBlock Succ 
) [static]

TryToSimplifyUncondBranchFromEmptyBlock - BB contains an unconditional branch to Succ, and contains no instructions other than PHI nodes and the branch. If possible, eliminate BB.

Definition at line 143 of file Utils/SimplifyCFG.cpp.

References BB, llvm::BasicBlock::begin(), CanPropagatePredecessorsForPHIs(), DEBUG, llvm::BasicBlock::eraseFromParent(), llvm::BasicBlock::front(), llvm::PHINode::getIncomingBlock(), llvm::PHINode::getIncomingValue(), llvm::BasicBlock::getInstList(), llvm::Value::getName(), llvm::PHINode::getNumIncomingValues(), llvm::Value::hasName(), llvm::pred_begin(), llvm::pred_end(), llvm::Value::replaceAllUsesWith(), and llvm::Value::setName().

Referenced by llvm::SimplifyCFG().

static bool ValuesOverlap ( std::vector< std::pair< ConstantInt *, BasicBlock * > > &  C1,
std::vector< std::pair< ConstantInt *, BasicBlock * > > &  C2 
) [static]

Definition at line 529 of file Utils/SimplifyCFG.cpp.

References first, and llvm::MVT::i1.

Referenced by SimplifyEqualityComparisonWithOnlyPredecessor().