SimplifyCFGPass.cpp Source File (original) (raw)

45#include

46using namespace llvm;

48#define DEBUG_TYPE "simplifycfg"

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

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

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

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

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

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

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

78 "(default = false)"));

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

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

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

90static bool

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

97 if (BBs.size() < 2)

98 return false;

100 if (Updates)

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

102

105 {

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

107

108

109

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

112

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

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

116 BBs.size(),

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

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

119 }

120

121

122 CanonicalTerm = Term->clone();

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

124

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

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

127 }

128

129

130

131 DILocation *CommonDebugLoc = nullptr;

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

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

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

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

137

138

139

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

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

142

143

144 if (!CommonDebugLoc)

145 CommonDebugLoc = Term->getDebugLoc();

146 else

147 CommonDebugLoc =

149

150

151

154 Term->eraseFromParent();

155

156 if (Updates)

157 Updates->push_back({DominatorTree::Insert, BB, CanonicalBB});

158 }

159

160 CanonicalTerm->setDebugLoc(CommonDebugLoc);

161

162 return true;

163}

164

168 Structure;

169

170

173 continue;

174

175

177 continue;

178

179 auto *Term = BB.getTerminator();

180

181

182

183 switch (Term->getOpcode()) {

184 case Instruction::Ret:

185 case Instruction::Resume:

186 break;

187 default:

188 continue;

189 }

190

191

192 if (BB.getTerminatingMustTailCall())

193 continue;

194

195

196

197

198 if (auto *CI =

199 dyn_cast_or_null(Term->getPrevNonDebugInstruction())) {

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

202 if (ID == Intrinsic::experimental_deoptimize)

203 continue;

204 }

205

206

207

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

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

210 continue;

211

212

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

214 }

215

216 bool Changed = false;

217

218 std::vectorDominatorTree::UpdateType Updates;

219

222

223 if (DTU)

225

226 return Changed;

227}

228

229

230

234 bool Changed = false;

235 bool LocalChange = true;

236

240 for (const auto &Edge : Edges)

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

242

244 UniqueLoopHeaders.end());

245

246 unsigned IterCnt = 0;

247 (void)IterCnt;

248 while (LocalChange) {

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

250 LocalChange = false;

251

252

255 if (DTU) {

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

259

260

262 ++BBIt;

263 }

265 LocalChange = true;

266 ++NumSimpl;

267 }

268 }

269 Changed |= LocalChange;

270 }

271 return Changed;

272}

273

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

278

280 EverChanged |=

283

284

285 if (!EverChanged) return false;

286

287

288

289

290

291

293 return true;

294

295 do {

298 } while (EverChanged);

299

300 return true;

301}

302

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

308 "Original domtree is invalid?");

309

311

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

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

315

316 return Changed;

317}

318

319

334 Options.HoistLoadsStoresWithCondFaulting =

340}

341

344}

345

349}

350

354 OS, MapClassName2PassName);

355 OS << '<';

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

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

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

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

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

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

370 << "speculate-unpredictables";

371 OS << '>';

372}

373

386 return PA;

387}

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 {

425 }

426};

427}

428

429char CFGSimplifyPass::ID = 0;

431 false)

437

438

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

443}

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

Performs the initial survey of the specified function

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)

assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())

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.

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)

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

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)

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

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)

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.

A container for analyses that lazily runs them and caches their results.

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

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

Represent the analysis usage information of a pass.

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 DILocation * getMergedLocation(DILocation *LocA, DILocation *LocB)

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

This class represents an Operation in the Expression.

Analysis pass which computes a DominatorTree.

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

verify - checks if the tree is correct.

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.

Legacy wrapper pass to provide the GlobalsAAResult object.

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.

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 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.

void preserve()

Mark an analysis as preserved.

PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)

Run the pass over the function.

SimplifyCFGPass()

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

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

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.

void reserve(size_type N)

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.

StringRef getName() const

Return a constant reference to the value's name.

int getNumOccurrences() const

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.

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

bool succ_empty(const Instruction *I)

bool any_of(R &&range, UnaryPredicate P)

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

void initializeCFGSimplifyPassPass(PassRegistry &)

cl::opt< bool > RequireAndPreserveDomTree

This function is used to do simplification of a CFG.

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.

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

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.

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

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

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.

bool ForwardSwitchCondToPhi

bool ConvertSwitchRangeToICmp

bool ConvertSwitchToLookupTable

bool SpeculateUnpredictables

bool HoistLoadsStoresWithCondFaulting

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