SimplifyCFGPass.cpp Source File (original) (raw)

44#include

45using namespace llvm;

47#define DEBUG_TYPE "simplifycfg"

51 cl::desc("Control the number of bonus instructions (default = 1)"));

55 cl::desc("Preserve canonical loop structure (default = true)"));

60 "Convert switches into an integer range comparison (default = false)"));

64 cl::desc("Convert switches to lookup tables (default = false)"));

68 cl::desc("Forward switch condition to phi ops (default = false)"));

72 cl::desc("hoist common instructions (default = false)"));

76 cl::desc("Hoist loads/stores if the target supports conditional faulting "

77 "(default = false)"));

81 cl::desc("Sink common instructions (default = false)"));

85 cl::desc("Speculate unpredictable branches (default = false)"));

87 STATISTIC(NumSimpl, "Number of blocks simplified");

89static bool

91 std::vectorDominatorTree::UpdateType *Updates) {

96 if (BBs.size() < 2)

97 return false;

99 if (Updates)

100 Updates->reserve(Updates->size() + BBs.size());

101

104 {

105 auto *Term = BBs[0]->getTerminator();

106

107

108

110 F.getContext(), Twine("common.") + Term->getOpcodeName(), &F, BBs[0]);

111

112 NewOps.resize(Term->getNumOperands());

113 for (auto I : zip(Term->operands(), NewOps)) {

115 BBs.size(),

116 CanonicalBB->getName() + ".op");

117 std::get<1>(I)->insertInto(CanonicalBB, CanonicalBB->end());

118 }

119

120

121 CanonicalTerm = Term->clone();

122 CanonicalTerm->insertInto(CanonicalBB, CanonicalBB->end());

123

124 for (auto I : zip(NewOps, CanonicalTerm->operands()))

125 std::get<1>(I) = std::get<0>(I);

126 }

127

128

129

132 auto *Term = BB->getTerminator();

133 assert(Term->getOpcode() == CanonicalTerm->getOpcode() &&

134 "All blocks to be tail-merged must be the same "

135 "(function-terminating) terminator type.");

136

137

138

139 for (auto I : zip(Term->operands(), NewOps))

140 std::get<1>(I)->addIncoming(std::get<0>(I), BB);

141

142

143 if (!CommonDebugLoc)

144 CommonDebugLoc = Term->getDebugLoc();

145 else

146 CommonDebugLoc =

148

149

150

153 Term->eraseFromParent();

154

155 if (Updates)

157 }

158

159 CanonicalTerm->setDebugLoc(CommonDebugLoc);

160

161 return true;

162}

163

167 Structure;

168

169

172 continue;

173

174

176 continue;

177

178 auto *Term = BB.getTerminator();

179

180

181

182 switch (Term->getOpcode()) {

183 case Instruction::Ret:

184 case Instruction::Resume:

185 break;

186 default:

187 continue;

188 }

189

190

191 if (BB.getTerminatingMustTailCall())

192 continue;

193

194

195

196

198 if (Function *F = CI->getCalledFunction())

200 if (ID == Intrinsic::experimental_deoptimize)

201 continue;

202 }

203

204

205

206 if (any_of(Term->operands(),

207 [](Value *Op) { return Op->getType()->isTokenTy(); }))

208 continue;

209

210

211 Structure[Term->getOpcode()].emplace_back(&BB);

212 }

213

215

216 std::vectorDominatorTree::UpdateType Updates;

217

220

221 if (DTU)

223

225}

226

227

228

233 bool LocalChange = true;

234

238 for (const auto &Edge : Edges)

239 UniqueLoopHeaders.insert(const_cast<BasicBlock *>(Edge.second));

240

242 UniqueLoopHeaders.end());

243

244 unsigned IterCnt = 0;

245 (void)IterCnt;

246 while (LocalChange) {

247 assert(IterCnt++ < 1000 && "Iterative simplification didn't converge!");

248 LocalChange = false;

249

250

253 if (DTU) {

256 "Should not end up trying to simplify blocks marked for removal.");

257

258

260 ++BBIt;

261 }

263 LocalChange = true;

264 ++NumSimpl;

265 }

266 }

268 }

270}

271

275 DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Eager);

276

278 EverChanged |=

281

282

283 if (!EverChanged) return false;

284

285

286

287

288

289

291 return true;

292

293 do {

296 } while (EverChanged);

297

298 return true;

299}

300

305 (DT && DT->verify(DominatorTree::VerificationLevel::Full))) &&

306 "Original domtree is invalid?");

307

309

311 (DT && DT->verify(DominatorTree::VerificationLevel::Full))) &&

312 "Failed to maintain validity of domtree!");

313

315}

316

317

332 Options.HoistLoadsStoresWithCondFaulting =

338}

339

343

345 : Options(Opts) {

347}

348

352 OS, MapClassName2PassName);

353 OS << '<';

354 OS << "bonus-inst-threshold=" << Options.BonusInstThreshold << ';';

355 OS << (Options.ForwardSwitchCondToPhi ? "" : "no-") << "forward-switch-cond;";

356 OS << (Options.ConvertSwitchRangeToICmp ? "" : "no-")

357 << "switch-range-to-icmp;";

358 OS << (Options.ConvertSwitchToArithmetic ? "" : "no-")

359 << "switch-to-arithmetic;";

360 OS << (Options.ConvertSwitchToLookupTable ? "" : "no-")

361 << "switch-to-lookup;";

362 OS << (Options.NeedCanonicalLoop ? "" : "no-") << "keep-loops;";

363 OS << (Options.HoistCommonInsts ? "" : "no-") << "hoist-common-insts;";

364 OS << (Options.HoistLoadsStoresWithCondFaulting ? "" : "no-")

365 << "hoist-loads-stores-with-cond-faulting;";

366 OS << (Options.SinkCommonInsts ? "" : "no-") << "sink-common-insts;";

367 OS << (Options.SpeculateBlocks ? "" : "no-") << "speculate-blocks;";

368 OS << (Options.SimplifyCondBranch ? "" : "no-") << "simplify-cond-branch;";

369 OS << (Options.SpeculateUnpredictables ? "" : "no-")

370 << "speculate-unpredictables";

371 OS << '>';

372}

373

388

389namespace {

390struct CFGSimplifyPass : public FunctionPass {

391 static char ID;

393 std::function<bool(const Function &)> PredicateFtor;

394

396 std::function<bool(const Function &)> Ftor = nullptr)

398

400

401

403 }

404

406 if (skipFunction(F) || (PredicateFtor && !PredicateFtor(F)))

407 return false;

408

409 Options.AC = &getAnalysis().getAssumptionCache(F);

412 DT = &getAnalysis().getDomTree();

413

414 auto &TTI = getAnalysis().getTTI(F);

416 }

417 void getAnalysisUsage(AnalysisUsage &AU) const override {

418 AU.addRequired();

420 AU.addRequired();

421 AU.addRequired();

425 }

426};

427}

428

429char CFGSimplifyPass::ID = 0;

431 false)

437

438

442 return new CFGSimplifyPass(Options, std::move(Ftor));

443}

assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")

This file contains the simple types necessary to represent the attributes associated with functions a...

static bool runOnFunction(Function &F, bool PostInlining)

This is the interface for a simple mod/ref and alias analysis over globals.

This file provides various utilities for inspecting and working with the control flow graph in LLVM I...

This file implements a map that provides insertion order iteration.

#define INITIALIZE_PASS_DEPENDENCY(depName)

#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)

#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)

dot regions Print regions of function to dot true view regions View regions of function(with no function bodies)"

static cl::opt< bool > UserSwitchRangeToICmp("switch-range-to-icmp", cl::Hidden, cl::init(false), cl::desc("Convert switches into an integer range comparison (default = false)"))

static cl::opt< bool > UserSinkCommonInsts("sink-common-insts", cl::Hidden, cl::init(false), cl::desc("Sink common instructions (default = false)"))

static bool iterativelySimplifyCFG(Function &F, const TargetTransformInfo &TTI, DomTreeUpdater *DTU, const SimplifyCFGOptions &Options)

Call SimplifyCFG on all the blocks in the function, iterating until no more changes are made.

Definition SimplifyCFGPass.cpp:229

static cl::opt< unsigned > UserBonusInstThreshold("bonus-inst-threshold", cl::Hidden, cl::init(1), cl::desc("Control the number of bonus instructions (default = 1)"))

static bool simplifyFunctionCFGImpl(Function &F, const TargetTransformInfo &TTI, DominatorTree *DT, const SimplifyCFGOptions &Options)

Definition SimplifyCFGPass.cpp:272

static bool simplifyFunctionCFG(Function &F, const TargetTransformInfo &TTI, DominatorTree *DT, const SimplifyCFGOptions &Options)

Definition SimplifyCFGPass.cpp:301

static cl::opt< bool > UserSwitchToLookup("switch-to-lookup", cl::Hidden, cl::init(false), cl::desc("Convert switches to lookup tables (default = false)"))

static cl::opt< bool > UserHoistLoadsStoresWithCondFaulting("hoist-loads-stores-with-cond-faulting", cl::Hidden, cl::init(false), cl::desc("Hoist loads/stores if the target supports conditional faulting " "(default = false)"))

static cl::opt< bool > UserKeepLoops("keep-loops", cl::Hidden, cl::init(true), cl::desc("Preserve canonical loop structure (default = true)"))

static cl::opt< bool > UserHoistCommonInsts("hoist-common-insts", cl::Hidden, cl::init(false), cl::desc("hoist common instructions (default = false)"))

static cl::opt< bool > UserSpeculateUnpredictables("speculate-unpredictables", cl::Hidden, cl::init(false), cl::desc("Speculate unpredictable branches (default = false)"))

static void applyCommandLineOverridesToOptions(SimplifyCFGOptions &Options)

Definition SimplifyCFGPass.cpp:318

static bool tailMergeBlocksWithSimilarFunctionTerminators(Function &F, DomTreeUpdater *DTU)

Definition SimplifyCFGPass.cpp:164

static cl::opt< bool > UserForwardSwitchCond("forward-switch-cond", cl::Hidden, cl::init(false), cl::desc("Forward switch condition to phi ops (default = false)"))

static bool performBlockTailMerging(Function &F, ArrayRef< BasicBlock * > BBs, std::vector< DominatorTree::UpdateType > *Updates)

Definition SimplifyCFGPass.cpp:90

This file provides the interface for the pass responsible for both simplifying and canonicalizing the...

This file defines the SmallPtrSet class.

This file defines the SmallVector class.

This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...

#define STATISTIC(VARNAME, DESC)

static SymbolRef::Type getType(const Symbol *Sym)

This pass exposes codegen information to IR-level passes.

PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)

Get the result of an analysis pass for a given IR unit.

AnalysisUsage & addRequired()

AnalysisUsage & addPreserved()

Add the specified Pass class to the set of analyses preserved by this pass.

ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...

size_t size() const

size - Get the array size.

A function analysis which provides an AssumptionCache.

An immutable pass that tracks lazily created AssumptionCache objects.

LLVM Basic Block Representation.

static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)

Creates a new BasicBlock.

static BranchInst * Create(BasicBlock *IfTrue, InsertPosition InsertBefore=nullptr)

static LLVM_ABI DebugLoc getMergedLocation(DebugLoc LocA, DebugLoc LocB)

When two instructions are combined into a single instruction we also need to combine the original loc...

Analysis pass which computes a DominatorTree.

bool verify(VerificationLevel VL=VerificationLevel::Full) const

verify - checks if the tree is correct.

static constexpr UpdateKind Insert

Legacy analysis pass which computes a DominatorTree.

Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.

FunctionPass class - This class is used to implement most global optimizations.

BasicBlockListType::iterator iterator

void applyUpdates(ArrayRef< UpdateT > Updates)

Submit updates to all available trees.

bool isBBPendingDeletion(BasicBlockT *DelBB) const

Returns true if DelBB is awaiting deletion.

unsigned getOpcode() const

Returns a member of one of the enums like Instruction::Add.

void setDebugLoc(DebugLoc Loc)

Set the debug location information for this instruction.

LLVM_ABI InstListType::iterator insertInto(BasicBlock *ParentBB, InstListType::iterator It)

Inserts an unlinked instruction into ParentBB at position It and returns the iterator of the inserted...

static PHINode * Create(Type *Ty, unsigned NumReservedValues, const Twine &NameStr="", InsertPosition InsertBefore=nullptr)

Constructors - NumReservedValues is a hint for the number of incoming edges that this phi node will h...

static LLVM_ABI PassRegistry * getPassRegistry()

getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...

A set of analyses that are preserved following a run of a transformation pass.

static PreservedAnalyses all()

Construct a special preserved set that preserves all passes.

PreservedAnalyses & preserve()

Mark an analysis as preserved.

LLVM_ABI PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)

Run the pass over the function.

Definition SimplifyCFGPass.cpp:374

LLVM_ABI SimplifyCFGPass()

The default constructor sets the pass options to create canonical IR, rather than optimal IR.

Definition SimplifyCFGPass.cpp:340

LLVM_ABI void printPipeline(raw_ostream &OS, function_ref< StringRef(StringRef)> MapClassName2PassName)

Definition SimplifyCFGPass.cpp:349

std::pair< iterator, bool > insert(PtrType Ptr)

Inserts Ptr if and only if there is no element in the container equal to Ptr.

SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.

This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.

StringRef - Represent a constant reference to a string, i.e.

Analysis pass providing the TargetTransformInfo.

Wrapper pass for TargetTransformInfo.

This pass provides access to the codegen interfaces that are needed for IR-level transformations.

Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...

LLVM Value Representation.

LLVM_ABI StringRef getName() const

Return a constant reference to the value's name.

An efficient, type-erasing, non-owning reference to a callable.

This class implements an extremely fast bulk output stream that can only output to a stream.

unsigned ID

LLVM IR allows to use arbitrary numbers as calling convention identifiers.

initializer< Ty > init(const Ty &Val)

This is an optimization pass for GlobalISel generic memory operations.

detail::zippy< detail::zip_shortest, T, U, Args... > zip(T &&t, U &&u, Args &&...args)

zip iterator for two or more iteratable types.

LLVM_ABI FunctionPass * createCFGSimplificationPass(SimplifyCFGOptions Options=SimplifyCFGOptions(), std::function< bool(const Function &)> Ftor=nullptr)

Definition SimplifyCFGPass.cpp:440

bool succ_empty(const Instruction *I)

auto dyn_cast_or_null(const Y &Val)

bool any_of(R &&range, UnaryPredicate P)

Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.

LLVM_ABI cl::opt< bool > RequireAndPreserveDomTree

This function is used to do simplification of a CFG.

DWARFExpression::Operation Op

auto make_second_range(ContainerTy &&c)

Given a container of pairs, return a range over the second elements.

OutputIt move(R &&Range, OutputIt Out)

Provide wrappers to std::move which take ranges instead of having to pass begin/end explicitly.

LLVM_ABI bool simplifyCFG(BasicBlock *BB, const TargetTransformInfo &TTI, DomTreeUpdater *DTU=nullptr, const SimplifyCFGOptions &Options={}, ArrayRef< WeakVH > LoopHeaders={})

AnalysisManager< Function > FunctionAnalysisManager

Convenience typedef for the Function analysis manager.

LLVM_ABI void FindFunctionBackedges(const Function &F, SmallVectorImpl< std::pair< const BasicBlock *, const BasicBlock * > > &Result)

Analyze the specified function to find all of the loop backedges in the function and return them.

LLVM_ABI bool removeUnreachableBlocks(Function &F, DomTreeUpdater *DTU=nullptr, MemorySSAUpdater *MSSAU=nullptr)

Remove all blocks that can not be reached from the function's entry.

LLVM_ABI void initializeCFGSimplifyPassPass(PassRegistry &)

Implement std::hash so that hash_code can be used in STL containers.

A CRTP mix-in to automatically provide informational APIs needed for passes.

A MapVector that performs no allocations if smaller than a certain size.