Bug Summary

File:include/llvm/Support/Error.h
Warning:line 200, column 5
Potential leak of memory pointed to by 'Payload._M_t._M_head_impl'

Annotated Source Code

Press '?' to see keyboard shortcuts

clang -cc1 -triple x86_64-pc-linux-gnu -analyze -disable-free -disable-llvm-verifier -discard-value-names -main-file-name PassBuilder.cpp -analyzer-store=region -analyzer-opt-analyze-nested-blocks -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=cplusplus -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -analyzer-config-compatibility-mode=true -mrelocation-model pic -pic-level 2 -mthread-model posix -fmath-errno -masm-verbose -mconstructor-aliases -munwind-tables -fuse-init-array -target-cpu x86-64 -dwarf-column-info -debugger-tuning=gdb -momit-leaf-frame-pointer -ffunction-sections -fdata-sections -resource-dir /usr/lib/llvm-9/lib/clang/9.0.0 -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I /build/llvm-toolchain-snapshot-9~svn362543/build-llvm/lib/Passes -I /build/llvm-toolchain-snapshot-9~svn362543/lib/Passes -I /build/llvm-toolchain-snapshot-9~svn362543/build-llvm/include -I /build/llvm-toolchain-snapshot-9~svn362543/include -U NDEBUG -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/x86_64-linux-gnu/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/x86_64-linux-gnu/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/c++/6.3.0/backward -internal-isystem /usr/include/clang/9.0.0/include/ -internal-isystem /usr/local/include -internal-isystem /usr/lib/llvm-9/lib/clang/9.0.0/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -O2 -Wno-unused-parameter -Wwrite-strings -Wno-missing-field-initializers -Wno-long-long -Wno-maybe-uninitialized -Wno-comment -std=c++11 -fdeprecated-macro -fdebug-compilation-dir /build/llvm-toolchain-snapshot-9~svn362543/build-llvm/lib/Passes -fdebug-prefix-map=/build/llvm-toolchain-snapshot-9~svn362543=. -ferror-limit 19 -fmessage-length 0 -fvisibility-inlines-hidden -stack-protector 2 -fobjc-runtime=gcc -fdiagnostics-show-option -vectorize-loops -vectorize-slp -analyzer-output=html -analyzer-config stable-report-filename=true -o /tmp/scan-build-2019-06-05-060531-1271-1 -x c++ /build/llvm-toolchain-snapshot-9~svn362543/lib/Passes/PassBuilder.cpp -faddrsig

/build/llvm-toolchain-snapshot-9~svn362543/lib/Passes/PassBuilder.cpp

1//===- Parsing, selection, and construction of pass pipelines -------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8/// \file
9///
10/// This file provides the implementation of the PassBuilder based on our
11/// static pass registry as well as related functionality. It also provides
12/// helpers to aid in analyzing, debugging, and testing passes and pass
13/// pipelines.
14///
15//===----------------------------------------------------------------------===//
16
17#include "llvm/Passes/PassBuilder.h"
18#include "llvm/ADT/StringSwitch.h"
19#include "llvm/Analysis/AliasAnalysis.h"
20#include "llvm/Analysis/AliasAnalysisEvaluator.h"
21#include "llvm/Analysis/AssumptionCache.h"
22#include "llvm/Analysis/BasicAliasAnalysis.h"
23#include "llvm/Analysis/BlockFrequencyInfo.h"
24#include "llvm/Analysis/BranchProbabilityInfo.h"
25#include "llvm/Analysis/CFGPrinter.h"
26#include "llvm/Analysis/CFLAndersAliasAnalysis.h"
27#include "llvm/Analysis/CFLSteensAliasAnalysis.h"
28#include "llvm/Analysis/CGSCCPassManager.h"
29#include "llvm/Analysis/CallGraph.h"
30#include "llvm/Analysis/DemandedBits.h"
31#include "llvm/Analysis/DependenceAnalysis.h"
32#include "llvm/Analysis/DominanceFrontier.h"
33#include "llvm/Analysis/GlobalsModRef.h"
34#include "llvm/Analysis/IVUsers.h"
35#include "llvm/Analysis/LazyCallGraph.h"
36#include "llvm/Analysis/LazyValueInfo.h"
37#include "llvm/Analysis/LoopAccessAnalysis.h"
38#include "llvm/Analysis/LoopInfo.h"
39#include "llvm/Analysis/MemoryDependenceAnalysis.h"
40#include "llvm/Analysis/MemorySSA.h"
41#include "llvm/Analysis/ModuleSummaryAnalysis.h"
42#include "llvm/Analysis/OptimizationRemarkEmitter.h"
43#include "llvm/Analysis/PhiValues.h"
44#include "llvm/Analysis/PostDominators.h"
45#include "llvm/Analysis/ProfileSummaryInfo.h"
46#include "llvm/Analysis/RegionInfo.h"
47#include "llvm/Analysis/ScalarEvolution.h"
48#include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h"
49#include "llvm/Analysis/ScopedNoAliasAA.h"
50#include "llvm/Analysis/StackSafetyAnalysis.h"
51#include "llvm/Analysis/TargetLibraryInfo.h"
52#include "llvm/Analysis/TargetTransformInfo.h"
53#include "llvm/Analysis/TypeBasedAliasAnalysis.h"
54#include "llvm/CodeGen/PreISelIntrinsicLowering.h"
55#include "llvm/CodeGen/UnreachableBlockElim.h"
56#include "llvm/IR/Dominators.h"
57#include "llvm/IR/IRPrintingPasses.h"
58#include "llvm/IR/PassManager.h"
59#include "llvm/IR/SafepointIRVerifier.h"
60#include "llvm/IR/Verifier.h"
61#include "llvm/Support/Debug.h"
62#include "llvm/Support/FormatVariadic.h"
63#include "llvm/Support/Regex.h"
64#include "llvm/Target/TargetMachine.h"
65#include "llvm/Transforms/AggressiveInstCombine/AggressiveInstCombine.h"
66#include "llvm/Transforms/IPO/AlwaysInliner.h"
67#include "llvm/Transforms/IPO/ArgumentPromotion.h"
68#include "llvm/Transforms/IPO/CalledValuePropagation.h"
69#include "llvm/Transforms/IPO/ConstantMerge.h"
70#include "llvm/Transforms/IPO/CrossDSOCFI.h"
71#include "llvm/Transforms/IPO/DeadArgumentElimination.h"
72#include "llvm/Transforms/IPO/ElimAvailExtern.h"
73#include "llvm/Transforms/IPO/ForceFunctionAttrs.h"
74#include "llvm/Transforms/IPO/FunctionAttrs.h"
75#include "llvm/Transforms/IPO/FunctionImport.h"
76#include "llvm/Transforms/IPO/GlobalDCE.h"
77#include "llvm/Transforms/IPO/GlobalOpt.h"
78#include "llvm/Transforms/IPO/GlobalSplit.h"
79#include "llvm/Transforms/IPO/HotColdSplitting.h"
80#include "llvm/Transforms/IPO/InferFunctionAttrs.h"
81#include "llvm/Transforms/IPO/Inliner.h"
82#include "llvm/Transforms/IPO/Internalize.h"
83#include "llvm/Transforms/IPO/LowerTypeTests.h"
84#include "llvm/Transforms/IPO/PartialInlining.h"
85#include "llvm/Transforms/IPO/SCCP.h"
86#include "llvm/Transforms/IPO/SampleProfile.h"
87#include "llvm/Transforms/IPO/StripDeadPrototypes.h"
88#include "llvm/Transforms/IPO/SyntheticCountsPropagation.h"
89#include "llvm/Transforms/IPO/WholeProgramDevirt.h"
90#include "llvm/Transforms/InstCombine/InstCombine.h"
91#include "llvm/Transforms/Instrumentation.h"
92#include "llvm/Transforms/Instrumentation/AddressSanitizer.h"
93#include "llvm/Transforms/Instrumentation/BoundsChecking.h"
94#include "llvm/Transforms/Instrumentation/CGProfile.h"
95#include "llvm/Transforms/Instrumentation/ControlHeightReduction.h"
96#include "llvm/Transforms/Instrumentation/GCOVProfiler.h"
97#include "llvm/Transforms/Instrumentation/HWAddressSanitizer.h"
98#include "llvm/Transforms/Instrumentation/InstrOrderFile.h"
99#include "llvm/Transforms/Instrumentation/InstrProfiling.h"
100#include "llvm/Transforms/Instrumentation/MemorySanitizer.h"
101#include "llvm/Transforms/Instrumentation/PGOInstrumentation.h"
102#include "llvm/Transforms/Instrumentation/ThreadSanitizer.h"
103#include "llvm/Transforms/Scalar/ADCE.h"
104#include "llvm/Transforms/Scalar/AlignmentFromAssumptions.h"
105#include "llvm/Transforms/Scalar/BDCE.h"
106#include "llvm/Transforms/Scalar/CallSiteSplitting.h"
107#include "llvm/Transforms/Scalar/ConstantHoisting.h"
108#include "llvm/Transforms/Scalar/CorrelatedValuePropagation.h"
109#include "llvm/Transforms/Scalar/DCE.h"
110#include "llvm/Transforms/Scalar/DeadStoreElimination.h"
111#include "llvm/Transforms/Scalar/DivRemPairs.h"
112#include "llvm/Transforms/Scalar/EarlyCSE.h"
113#include "llvm/Transforms/Scalar/Float2Int.h"
114#include "llvm/Transforms/Scalar/GVN.h"
115#include "llvm/Transforms/Scalar/GuardWidening.h"
116#include "llvm/Transforms/Scalar/IVUsersPrinter.h"
117#include "llvm/Transforms/Scalar/IndVarSimplify.h"
118#include "llvm/Transforms/Scalar/InductiveRangeCheckElimination.h"
119#include "llvm/Transforms/Scalar/InstSimplifyPass.h"
120#include "llvm/Transforms/Scalar/JumpThreading.h"
121#include "llvm/Transforms/Scalar/LICM.h"
122#include "llvm/Transforms/Scalar/LoopAccessAnalysisPrinter.h"
123#include "llvm/Transforms/Scalar/LoopDataPrefetch.h"
124#include "llvm/Transforms/Scalar/LoopDeletion.h"
125#include "llvm/Transforms/Scalar/LoopDistribute.h"
126#include "llvm/Transforms/Scalar/LoopFuse.h"
127#include "llvm/Transforms/Scalar/LoopIdiomRecognize.h"
128#include "llvm/Transforms/Scalar/LoopInstSimplify.h"
129#include "llvm/Transforms/Scalar/LoopLoadElimination.h"
130#include "llvm/Transforms/Scalar/LoopPassManager.h"
131#include "llvm/Transforms/Scalar/LoopPredication.h"
132#include "llvm/Transforms/Scalar/LoopRotation.h"
133#include "llvm/Transforms/Scalar/LoopSimplifyCFG.h"
134#include "llvm/Transforms/Scalar/LoopSink.h"
135#include "llvm/Transforms/Scalar/LoopStrengthReduce.h"
136#include "llvm/Transforms/Scalar/LoopUnrollAndJamPass.h"
137#include "llvm/Transforms/Scalar/LoopUnrollPass.h"
138#include "llvm/Transforms/Scalar/LowerAtomic.h"
139#include "llvm/Transforms/Scalar/LowerExpectIntrinsic.h"
140#include "llvm/Transforms/Scalar/LowerGuardIntrinsic.h"
141#include "llvm/Transforms/Scalar/LowerWidenableCondition.h"
142#include "llvm/Transforms/Scalar/MakeGuardsExplicit.h"
143#include "llvm/Transforms/Scalar/MemCpyOptimizer.h"
144#include "llvm/Transforms/Scalar/MergedLoadStoreMotion.h"
145#include "llvm/Transforms/Scalar/MergeICmps.h"
146#include "llvm/Transforms/Scalar/NaryReassociate.h"
147#include "llvm/Transforms/Scalar/NewGVN.h"
148#include "llvm/Transforms/Scalar/PartiallyInlineLibCalls.h"
149#include "llvm/Transforms/Scalar/Reassociate.h"
150#include "llvm/Transforms/Scalar/RewriteStatepointsForGC.h"
151#include "llvm/Transforms/Scalar/SCCP.h"
152#include "llvm/Transforms/Scalar/SROA.h"
153#include "llvm/Transforms/Scalar/Scalarizer.h"
154#include "llvm/Transforms/Scalar/SimpleLoopUnswitch.h"
155#include "llvm/Transforms/Scalar/SimplifyCFG.h"
156#include "llvm/Transforms/Scalar/Sink.h"
157#include "llvm/Transforms/Scalar/SpeculateAroundPHIs.h"
158#include "llvm/Transforms/Scalar/SpeculativeExecution.h"
159#include "llvm/Transforms/Scalar/TailRecursionElimination.h"
160#include "llvm/Transforms/Scalar/WarnMissedTransforms.h"
161#include "llvm/Transforms/Utils/AddDiscriminators.h"
162#include "llvm/Transforms/Utils/BreakCriticalEdges.h"
163#include "llvm/Transforms/Utils/CanonicalizeAliases.h"
164#include "llvm/Transforms/Utils/EntryExitInstrumenter.h"
165#include "llvm/Transforms/Utils/LCSSA.h"
166#include "llvm/Transforms/Utils/LibCallsShrinkWrap.h"
167#include "llvm/Transforms/Utils/LoopSimplify.h"
168#include "llvm/Transforms/Utils/LowerInvoke.h"
169#include "llvm/Transforms/Utils/Mem2Reg.h"
170#include "llvm/Transforms/Utils/NameAnonGlobals.h"
171#include "llvm/Transforms/Utils/SymbolRewriter.h"
172#include "llvm/Transforms/Vectorize/LoadStoreVectorizer.h"
173#include "llvm/Transforms/Vectorize/LoopVectorize.h"
174#include "llvm/Transforms/Vectorize/SLPVectorizer.h"
175
176using namespace llvm;
177
178static cl::opt<unsigned> MaxDevirtIterations("pm-max-devirt-iterations",
179 cl::ReallyHidden, cl::init(4));
180static cl::opt<bool>
181 RunPartialInlining("enable-npm-partial-inlining", cl::init(false),
182 cl::Hidden, cl::ZeroOrMore,
183 cl::desc("Run Partial inlinining pass"));
184
185static cl::opt<bool>
186 RunNewGVN("enable-npm-newgvn", cl::init(false),
187 cl::Hidden, cl::ZeroOrMore,
188 cl::desc("Run NewGVN instead of GVN"));
189
190static cl::opt<bool> EnableGVNHoist(
191 "enable-npm-gvn-hoist", cl::init(false), cl::Hidden,
192 cl::desc("Enable the GVN hoisting pass for the new PM (default = off)"));
193
194static cl::opt<bool> EnableGVNSink(
195 "enable-npm-gvn-sink", cl::init(false), cl::Hidden,
196 cl::desc("Enable the GVN hoisting pass for the new PM (default = off)"));
197
198static cl::opt<bool> EnableUnrollAndJam(
199 "enable-npm-unroll-and-jam", cl::init(false), cl::Hidden,
200 cl::desc("Enable the Unroll and Jam pass for the new PM (default = off)"));
201
202static cl::opt<bool> EnableSyntheticCounts(
203 "enable-npm-synthetic-counts", cl::init(false), cl::Hidden, cl::ZeroOrMore,
204 cl::desc("Run synthetic function entry count generation "
205 "pass"));
206
207static Regex DefaultAliasRegex(
208 "^(default|thinlto-pre-link|thinlto|lto-pre-link|lto)<(O[0123sz])>$");
209
210// This option is used in simplifying testing SampleFDO optimizations for
211// profile loading.
212static cl::opt<bool>
213 EnableCHR("enable-chr-npm", cl::init(true), cl::Hidden,
214 cl::desc("Enable control height reduction optimization (CHR)"));
215
216PipelineTuningOptions::PipelineTuningOptions() {
217 LoopInterleaving = EnableLoopInterleaving;
218 LoopVectorization = EnableLoopVectorization;
219 SLPVectorization = RunSLPVectorization;
220 LoopUnrolling = true;
221 ForgetAllSCEVInLoopUnroll = ForgetSCEVInLoopUnroll;
222 LicmMssaOptCap = SetLicmMssaOptCap;
223 LicmMssaNoAccForPromotionCap = SetLicmMssaNoAccForPromotionCap;
224}
225
226extern cl::opt<bool> EnableHotColdSplit;
227extern cl::opt<bool> EnableOrderFileInstrumentation;
228
229extern cl::opt<bool> FlattenedProfileUsed;
230
231static bool isOptimizingForSize(PassBuilder::OptimizationLevel Level) {
232 switch (Level) {
233 case PassBuilder::O0:
234 case PassBuilder::O1:
235 case PassBuilder::O2:
236 case PassBuilder::O3:
237 return false;
238
239 case PassBuilder::Os:
240 case PassBuilder::Oz:
241 return true;
242 }
243 llvm_unreachable("Invalid optimization level!")::llvm::llvm_unreachable_internal("Invalid optimization level!"
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/Passes/PassBuilder.cpp"
, 243)
;
244}
245
246namespace {
247
248/// No-op module pass which does nothing.
249struct NoOpModulePass {
250 PreservedAnalyses run(Module &M, ModuleAnalysisManager &) {
251 return PreservedAnalyses::all();
252 }
253 static StringRef name() { return "NoOpModulePass"; }
254};
255
256/// No-op module analysis.
257class NoOpModuleAnalysis : public AnalysisInfoMixin<NoOpModuleAnalysis> {
258 friend AnalysisInfoMixin<NoOpModuleAnalysis>;
259 static AnalysisKey Key;
260
261public:
262 struct Result {};
263 Result run(Module &, ModuleAnalysisManager &) { return Result(); }
264 static StringRef name() { return "NoOpModuleAnalysis"; }
265};
266
267/// No-op CGSCC pass which does nothing.
268struct NoOpCGSCCPass {
269 PreservedAnalyses run(LazyCallGraph::SCC &C, CGSCCAnalysisManager &,
270 LazyCallGraph &, CGSCCUpdateResult &UR) {
271 return PreservedAnalyses::all();
272 }
273 static StringRef name() { return "NoOpCGSCCPass"; }
274};
275
276/// No-op CGSCC analysis.
277class NoOpCGSCCAnalysis : public AnalysisInfoMixin<NoOpCGSCCAnalysis> {
278 friend AnalysisInfoMixin<NoOpCGSCCAnalysis>;
279 static AnalysisKey Key;
280
281public:
282 struct Result {};
283 Result run(LazyCallGraph::SCC &, CGSCCAnalysisManager &, LazyCallGraph &G) {
284 return Result();
285 }
286 static StringRef name() { return "NoOpCGSCCAnalysis"; }
287};
288
289/// No-op function pass which does nothing.
290struct NoOpFunctionPass {
291 PreservedAnalyses run(Function &F, FunctionAnalysisManager &) {
292 return PreservedAnalyses::all();
293 }
294 static StringRef name() { return "NoOpFunctionPass"; }
295};
296
297/// No-op function analysis.
298class NoOpFunctionAnalysis : public AnalysisInfoMixin<NoOpFunctionAnalysis> {
299 friend AnalysisInfoMixin<NoOpFunctionAnalysis>;
300 static AnalysisKey Key;
301
302public:
303 struct Result {};
304 Result run(Function &, FunctionAnalysisManager &) { return Result(); }
305 static StringRef name() { return "NoOpFunctionAnalysis"; }
306};
307
308/// No-op loop pass which does nothing.
309struct NoOpLoopPass {
310 PreservedAnalyses run(Loop &L, LoopAnalysisManager &,
311 LoopStandardAnalysisResults &, LPMUpdater &) {
312 return PreservedAnalyses::all();
313 }
314 static StringRef name() { return "NoOpLoopPass"; }
315};
316
317/// No-op loop analysis.
318class NoOpLoopAnalysis : public AnalysisInfoMixin<NoOpLoopAnalysis> {
319 friend AnalysisInfoMixin<NoOpLoopAnalysis>;
320 static AnalysisKey Key;
321
322public:
323 struct Result {};
324 Result run(Loop &, LoopAnalysisManager &, LoopStandardAnalysisResults &) {
325 return Result();
326 }
327 static StringRef name() { return "NoOpLoopAnalysis"; }
328};
329
330AnalysisKey NoOpModuleAnalysis::Key;
331AnalysisKey NoOpCGSCCAnalysis::Key;
332AnalysisKey NoOpFunctionAnalysis::Key;
333AnalysisKey NoOpLoopAnalysis::Key;
334
335} // End anonymous namespace.
336
337void PassBuilder::invokePeepholeEPCallbacks(
338 FunctionPassManager &FPM, PassBuilder::OptimizationLevel Level) {
339 for (auto &C : PeepholeEPCallbacks)
340 C(FPM, Level);
341}
342
343void PassBuilder::registerModuleAnalyses(ModuleAnalysisManager &MAM) {
344#define MODULE_ANALYSIS(NAME, CREATE_PASS) \
345 MAM.registerPass([&] { return CREATE_PASS; });
346#include "PassRegistry.def"
347
348 for (auto &C : ModuleAnalysisRegistrationCallbacks)
349 C(MAM);
350}
351
352void PassBuilder::registerCGSCCAnalyses(CGSCCAnalysisManager &CGAM) {
353#define CGSCC_ANALYSIS(NAME, CREATE_PASS) \
354 CGAM.registerPass([&] { return CREATE_PASS; });
355#include "PassRegistry.def"
356
357 for (auto &C : CGSCCAnalysisRegistrationCallbacks)
358 C(CGAM);
359}
360
361void PassBuilder::registerFunctionAnalyses(FunctionAnalysisManager &FAM) {
362#define FUNCTION_ANALYSIS(NAME, CREATE_PASS) \
363 FAM.registerPass([&] { return CREATE_PASS; });
364#include "PassRegistry.def"
365
366 for (auto &C : FunctionAnalysisRegistrationCallbacks)
367 C(FAM);
368}
369
370void PassBuilder::registerLoopAnalyses(LoopAnalysisManager &LAM) {
371#define LOOP_ANALYSIS(NAME, CREATE_PASS) \
372 LAM.registerPass([&] { return CREATE_PASS; });
373#include "PassRegistry.def"
374
375 for (auto &C : LoopAnalysisRegistrationCallbacks)
376 C(LAM);
377}
378
379FunctionPassManager
380PassBuilder::buildFunctionSimplificationPipeline(OptimizationLevel Level,
381 ThinLTOPhase Phase,
382 bool DebugLogging) {
383 assert(Level != O0 && "Must request optimizations!")((Level != O0 && "Must request optimizations!") ? static_cast
<void> (0) : __assert_fail ("Level != O0 && \"Must request optimizations!\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/Passes/PassBuilder.cpp"
, 383, __PRETTY_FUNCTION__))
;
384 FunctionPassManager FPM(DebugLogging);
385
386 // Form SSA out of local memory accesses after breaking apart aggregates into
387 // scalars.
388 FPM.addPass(SROA());
389
390 // Catch trivial redundancies
391 FPM.addPass(EarlyCSEPass(true /* Enable mem-ssa. */));
392
393 // Hoisting of scalars and load expressions.
394 if (EnableGVNHoist)
395 FPM.addPass(GVNHoistPass());
396
397 // Global value numbering based sinking.
398 if (EnableGVNSink) {
399 FPM.addPass(GVNSinkPass());
400 FPM.addPass(SimplifyCFGPass());
401 }
402
403 // Speculative execution if the target has divergent branches; otherwise nop.
404 FPM.addPass(SpeculativeExecutionPass());
405
406 // Optimize based on known information about branches, and cleanup afterward.
407 FPM.addPass(JumpThreadingPass());
408 FPM.addPass(CorrelatedValuePropagationPass());
409 FPM.addPass(SimplifyCFGPass());
410 if (Level == O3)
411 FPM.addPass(AggressiveInstCombinePass());
412 FPM.addPass(InstCombinePass());
413
414 if (!isOptimizingForSize(Level))
415 FPM.addPass(LibCallsShrinkWrapPass());
416
417 invokePeepholeEPCallbacks(FPM, Level);
418
419 // For PGO use pipeline, try to optimize memory intrinsics such as memcpy
420 // using the size value profile. Don't perform this when optimizing for size.
421 if (PGOOpt && PGOOpt->Action == PGOOptions::IRUse &&
422 !isOptimizingForSize(Level))
423 FPM.addPass(PGOMemOPSizeOpt());
424
425 FPM.addPass(TailCallElimPass());
426 FPM.addPass(SimplifyCFGPass());
427
428 // Form canonically associated expression trees, and simplify the trees using
429 // basic mathematical properties. For example, this will form (nearly)
430 // minimal multiplication trees.
431 FPM.addPass(ReassociatePass());
432
433 // Add the primary loop simplification pipeline.
434 // FIXME: Currently this is split into two loop pass pipelines because we run
435 // some function passes in between them. These can and should be removed
436 // and/or replaced by scheduling the loop pass equivalents in the correct
437 // positions. But those equivalent passes aren't powerful enough yet.
438 // Specifically, `SimplifyCFGPass` and `InstCombinePass` are currently still
439 // used. We have `LoopSimplifyCFGPass` which isn't yet powerful enough yet to
440 // fully replace `SimplifyCFGPass`, and the closest to the other we have is
441 // `LoopInstSimplify`.
442 LoopPassManager LPM1(DebugLogging), LPM2(DebugLogging);
443
444 // Simplify the loop body. We do this initially to clean up after other loop
445 // passes run, either when iterating on a loop or on inner loops with
446 // implications on the outer loop.
447 LPM1.addPass(LoopInstSimplifyPass());
448 LPM1.addPass(LoopSimplifyCFGPass());
449
450 // Rotate Loop - disable header duplication at -Oz
451 LPM1.addPass(LoopRotatePass(Level != Oz));
452 LPM1.addPass(LICMPass(PTO.LicmMssaOptCap, PTO.LicmMssaNoAccForPromotionCap));
453 LPM1.addPass(SimpleLoopUnswitchPass());
454 LPM2.addPass(IndVarSimplifyPass());
455 LPM2.addPass(LoopIdiomRecognizePass());
456
457 for (auto &C : LateLoopOptimizationsEPCallbacks)
458 C(LPM2, Level);
459
460 LPM2.addPass(LoopDeletionPass());
461 // Do not enable unrolling in PreLinkThinLTO phase during sample PGO
462 // because it changes IR to makes profile annotation in back compile
463 // inaccurate.
464 if ((Phase != ThinLTOPhase::PreLink || !PGOOpt ||
465 PGOOpt->Action != PGOOptions::SampleUse) &&
466 PTO.LoopUnrolling)
467 LPM2.addPass(
468 LoopFullUnrollPass(Level, false, PTO.ForgetAllSCEVInLoopUnroll));
469
470 for (auto &C : LoopOptimizerEndEPCallbacks)
471 C(LPM2, Level);
472
473 // We provide the opt remark emitter pass for LICM to use. We only need to do
474 // this once as it is immutable.
475 FPM.addPass(RequireAnalysisPass<OptimizationRemarkEmitterAnalysis, Function>());
476 FPM.addPass(createFunctionToLoopPassAdaptor(std::move(LPM1), DebugLogging));
477 FPM.addPass(SimplifyCFGPass());
478 FPM.addPass(InstCombinePass());
479 FPM.addPass(createFunctionToLoopPassAdaptor(std::move(LPM2), DebugLogging));
480
481 // Eliminate redundancies.
482 if (Level != O1) {
483 // These passes add substantial compile time so skip them at O1.
484 FPM.addPass(MergedLoadStoreMotionPass());
485 if (RunNewGVN)
486 FPM.addPass(NewGVNPass());
487 else
488 FPM.addPass(GVN());
489 }
490
491 // Specially optimize memory movement as it doesn't look like dataflow in SSA.
492 FPM.addPass(MemCpyOptPass());
493
494 // Sparse conditional constant propagation.
495 // FIXME: It isn't clear why we do this *after* loop passes rather than
496 // before...
497 FPM.addPass(SCCPPass());
498
499 // Delete dead bit computations (instcombine runs after to fold away the dead
500 // computations, and then ADCE will run later to exploit any new DCE
501 // opportunities that creates).
502 FPM.addPass(BDCEPass());
503
504 // Run instcombine after redundancy and dead bit elimination to exploit
505 // opportunities opened up by them.
506 FPM.addPass(InstCombinePass());
507 invokePeepholeEPCallbacks(FPM, Level);
508
509 // Re-consider control flow based optimizations after redundancy elimination,
510 // redo DCE, etc.
511 FPM.addPass(JumpThreadingPass());
512 FPM.addPass(CorrelatedValuePropagationPass());
513 FPM.addPass(DSEPass());
514 FPM.addPass(createFunctionToLoopPassAdaptor(
515 LICMPass(PTO.LicmMssaOptCap, PTO.LicmMssaNoAccForPromotionCap),
516 DebugLogging));
517
518 for (auto &C : ScalarOptimizerLateEPCallbacks)
519 C(FPM, Level);
520
521 // Finally, do an expensive DCE pass to catch all the dead code exposed by
522 // the simplifications and basic cleanup after all the simplifications.
523 FPM.addPass(ADCEPass());
524 FPM.addPass(SimplifyCFGPass());
525 FPM.addPass(InstCombinePass());
526 invokePeepholeEPCallbacks(FPM, Level);
527
528 if (EnableCHR && Level == O3 && PGOOpt &&
529 (PGOOpt->Action == PGOOptions::IRUse ||
530 PGOOpt->Action == PGOOptions::SampleUse))
531 FPM.addPass(ControlHeightReductionPass());
532
533 return FPM;
534}
535
536void PassBuilder::addPGOInstrPasses(ModulePassManager &MPM, bool DebugLogging,
537 PassBuilder::OptimizationLevel Level,
538 bool RunProfileGen, bool IsCS,
539 std::string ProfileFile,
540 std::string ProfileRemappingFile) {
541 // Generally running simplification passes and the inliner with an high
542 // threshold results in smaller executables, but there may be cases where
543 // the size grows, so let's be conservative here and skip this simplification
544 // at -Os/Oz. We will not do this inline for context sensistive PGO (when
545 // IsCS is true).
546 if (!isOptimizingForSize(Level) && !IsCS) {
547 InlineParams IP;
548
549 // In the old pass manager, this is a cl::opt. Should still this be one?
550 IP.DefaultThreshold = 75;
551
552 // FIXME: The hint threshold has the same value used by the regular inliner.
553 // This should probably be lowered after performance testing.
554 // FIXME: this comment is cargo culted from the old pass manager, revisit).
555 IP.HintThreshold = 325;
556
557 CGSCCPassManager CGPipeline(DebugLogging);
558
559 CGPipeline.addPass(InlinerPass(IP));
560
561 FunctionPassManager FPM;
562 FPM.addPass(SROA());
563 FPM.addPass(EarlyCSEPass()); // Catch trivial redundancies.
564 FPM.addPass(SimplifyCFGPass()); // Merge & remove basic blocks.
565 FPM.addPass(InstCombinePass()); // Combine silly sequences.
566 invokePeepholeEPCallbacks(FPM, Level);
567
568 CGPipeline.addPass(createCGSCCToFunctionPassAdaptor(std::move(FPM)));
569
570 MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPipeline)));
571 }
572
573 // Delete anything that is now dead to make sure that we don't instrument
574 // dead code. Instrumentation can end up keeping dead code around and
575 // dramatically increase code size.
576 MPM.addPass(GlobalDCEPass());
577
578 if (RunProfileGen) {
579 MPM.addPass(PGOInstrumentationGen(IsCS));
580
581 FunctionPassManager FPM;
582 FPM.addPass(
583 createFunctionToLoopPassAdaptor(LoopRotatePass(), DebugLogging));
584 MPM.addPass(createModuleToFunctionPassAdaptor(std::move(FPM)));
585
586 // Add the profile lowering pass.
587 InstrProfOptions Options;
588 if (!ProfileFile.empty())
589 Options.InstrProfileOutput = ProfileFile;
590 Options.DoCounterPromotion = true;
591 Options.UseBFIInPromotion = IsCS;
592 MPM.addPass(InstrProfiling(Options, IsCS));
593 } else if (!ProfileFile.empty()) {
594 MPM.addPass(PGOInstrumentationUse(ProfileFile, ProfileRemappingFile, IsCS));
595 // Cache ProfileSummaryAnalysis once to avoid the potential need to insert
596 // RequireAnalysisPass for PSI before subsequent non-module passes.
597 MPM.addPass(RequireAnalysisPass<ProfileSummaryAnalysis, Module>());
598 }
599}
600
601static InlineParams
602getInlineParamsFromOptLevel(PassBuilder::OptimizationLevel Level) {
603 auto O3 = PassBuilder::O3;
604 unsigned OptLevel = Level > O3 ? 2 : Level;
605 unsigned SizeLevel = Level > O3 ? Level - O3 : 0;
606 return getInlineParams(OptLevel, SizeLevel);
607}
608
609ModulePassManager
610PassBuilder::buildModuleSimplificationPipeline(OptimizationLevel Level,
611 ThinLTOPhase Phase,
612 bool DebugLogging) {
613 ModulePassManager MPM(DebugLogging);
614
615 bool HasSampleProfile = PGOOpt && (PGOOpt->Action == PGOOptions::SampleUse);
616
617 // In ThinLTO mode, when flattened profile is used, all the available
618 // profile information will be annotated in PreLink phase so there is
619 // no need to load the profile again in PostLink.
620 bool LoadSampleProfile =
621 HasSampleProfile &&
622 !(FlattenedProfileUsed && Phase == ThinLTOPhase::PostLink);
623
624 // During the ThinLTO backend phase we perform early indirect call promotion
625 // here, before globalopt. Otherwise imported available_externally functions
626 // look unreferenced and are removed. If we are going to load the sample
627 // profile then defer until later.
628 // TODO: See if we can move later and consolidate with the location where
629 // we perform ICP when we are loading a sample profile.
630 // TODO: We pass HasSampleProfile (whether there was a sample profile file
631 // passed to the compile) to the SamplePGO flag of ICP. This is used to
632 // determine whether the new direct calls are annotated with prof metadata.
633 // Ideally this should be determined from whether the IR is annotated with
634 // sample profile, and not whether the a sample profile was provided on the
635 // command line. E.g. for flattened profiles where we will not be reloading
636 // the sample profile in the ThinLTO backend, we ideally shouldn't have to
637 // provide the sample profile file.
638 if (Phase == ThinLTOPhase::PostLink && !LoadSampleProfile)
639 MPM.addPass(PGOIndirectCallPromotion(true /* InLTO */, HasSampleProfile));
640
641 // Do basic inference of function attributes from known properties of system
642 // libraries and other oracles.
643 MPM.addPass(InferFunctionAttrsPass());
644
645 // Create an early function pass manager to cleanup the output of the
646 // frontend.
647 FunctionPassManager EarlyFPM(DebugLogging);
648 EarlyFPM.addPass(SimplifyCFGPass());
649 EarlyFPM.addPass(SROA());
650 EarlyFPM.addPass(EarlyCSEPass());
651 EarlyFPM.addPass(LowerExpectIntrinsicPass());
652 if (Level == O3)
653 EarlyFPM.addPass(CallSiteSplittingPass());
654
655 // In SamplePGO ThinLTO backend, we need instcombine before profile annotation
656 // to convert bitcast to direct calls so that they can be inlined during the
657 // profile annotation prepration step.
658 // More details about SamplePGO design can be found in:
659 // https://research.google.com/pubs/pub45290.html
660 // FIXME: revisit how SampleProfileLoad/Inliner/ICP is structured.
661 if (LoadSampleProfile)
662 EarlyFPM.addPass(InstCombinePass());
663 MPM.addPass(createModuleToFunctionPassAdaptor(std::move(EarlyFPM)));
664
665 if (LoadSampleProfile) {
666 // Annotate sample profile right after early FPM to ensure freshness of
667 // the debug info.
668 MPM.addPass(SampleProfileLoaderPass(PGOOpt->ProfileFile,
669 PGOOpt->ProfileRemappingFile,
670 Phase == ThinLTOPhase::PreLink));
671 // Cache ProfileSummaryAnalysis once to avoid the potential need to insert
672 // RequireAnalysisPass for PSI before subsequent non-module passes.
673 MPM.addPass(RequireAnalysisPass<ProfileSummaryAnalysis, Module>());
674 // Do not invoke ICP in the ThinLTOPrelink phase as it makes it hard
675 // for the profile annotation to be accurate in the ThinLTO backend.
676 if (Phase != ThinLTOPhase::PreLink)
677 // We perform early indirect call promotion here, before globalopt.
678 // This is important for the ThinLTO backend phase because otherwise
679 // imported available_externally functions look unreferenced and are
680 // removed.
681 MPM.addPass(PGOIndirectCallPromotion(Phase == ThinLTOPhase::PostLink,
682 true /* SamplePGO */));
683 }
684
685 // Interprocedural constant propagation now that basic cleanup has occurred
686 // and prior to optimizing globals.
687 // FIXME: This position in the pipeline hasn't been carefully considered in
688 // years, it should be re-analyzed.
689 MPM.addPass(IPSCCPPass());
690
691 // Attach metadata to indirect call sites indicating the set of functions
692 // they may target at run-time. This should follow IPSCCP.
693 MPM.addPass(CalledValuePropagationPass());
694
695 // Optimize globals to try and fold them into constants.
696 MPM.addPass(GlobalOptPass());
697
698 // Promote any localized globals to SSA registers.
699 // FIXME: Should this instead by a run of SROA?
700 // FIXME: We should probably run instcombine and simplify-cfg afterward to
701 // delete control flows that are dead once globals have been folded to
702 // constants.
703 MPM.addPass(createModuleToFunctionPassAdaptor(PromotePass()));
704
705 // Remove any dead arguments exposed by cleanups and constand folding
706 // globals.
707 MPM.addPass(DeadArgumentEliminationPass());
708
709 // Create a small function pass pipeline to cleanup after all the global
710 // optimizations.
711 FunctionPassManager GlobalCleanupPM(DebugLogging);
712 GlobalCleanupPM.addPass(InstCombinePass());
713 invokePeepholeEPCallbacks(GlobalCleanupPM, Level);
714
715 GlobalCleanupPM.addPass(SimplifyCFGPass());
716 MPM.addPass(createModuleToFunctionPassAdaptor(std::move(GlobalCleanupPM)));
717
718 // Add all the requested passes for instrumentation PGO, if requested.
719 if (PGOOpt && Phase != ThinLTOPhase::PostLink &&
720 (PGOOpt->Action == PGOOptions::IRInstr ||
721 PGOOpt->Action == PGOOptions::IRUse)) {
722 addPGOInstrPasses(MPM, DebugLogging, Level,
723 /* RunProfileGen */ PGOOpt->Action == PGOOptions::IRInstr,
724 /* IsCS */ false, PGOOpt->ProfileFile,
725 PGOOpt->ProfileRemappingFile);
726 MPM.addPass(PGOIndirectCallPromotion(false, false));
727 }
728 if (PGOOpt && Phase != ThinLTOPhase::PostLink &&
729 PGOOpt->CSAction == PGOOptions::CSIRInstr)
730 MPM.addPass(PGOInstrumentationGenCreateVar(PGOOpt->CSProfileGenFile));
731
732 // Synthesize function entry counts for non-PGO compilation.
733 if (EnableSyntheticCounts && !PGOOpt)
734 MPM.addPass(SyntheticCountsPropagation());
735
736 // Require the GlobalsAA analysis for the module so we can query it within
737 // the CGSCC pipeline.
738 MPM.addPass(RequireAnalysisPass<GlobalsAA, Module>());
739
740 // Require the ProfileSummaryAnalysis for the module so we can query it within
741 // the inliner pass.
742 MPM.addPass(RequireAnalysisPass<ProfileSummaryAnalysis, Module>());
743
744 // Now begin the main postorder CGSCC pipeline.
745 // FIXME: The current CGSCC pipeline has its origins in the legacy pass
746 // manager and trying to emulate its precise behavior. Much of this doesn't
747 // make a lot of sense and we should revisit the core CGSCC structure.
748 CGSCCPassManager MainCGPipeline(DebugLogging);
749
750 // Note: historically, the PruneEH pass was run first to deduce nounwind and
751 // generally clean up exception handling overhead. It isn't clear this is
752 // valuable as the inliner doesn't currently care whether it is inlining an
753 // invoke or a call.
754
755 // Run the inliner first. The theory is that we are walking bottom-up and so
756 // the callees have already been fully optimized, and we want to inline them
757 // into the callers so that our optimizations can reflect that.
758 // For PreLinkThinLTO pass, we disable hot-caller heuristic for sample PGO
759 // because it makes profile annotation in the backend inaccurate.
760 InlineParams IP = getInlineParamsFromOptLevel(Level);
761 if (Phase == ThinLTOPhase::PreLink && PGOOpt &&
762 PGOOpt->Action == PGOOptions::SampleUse)
763 IP.HotCallSiteThreshold = 0;
764 MainCGPipeline.addPass(InlinerPass(IP));
765
766 // Now deduce any function attributes based in the current code.
767 MainCGPipeline.addPass(PostOrderFunctionAttrsPass());
768
769 // When at O3 add argument promotion to the pass pipeline.
770 // FIXME: It isn't at all clear why this should be limited to O3.
771 if (Level == O3)
772 MainCGPipeline.addPass(ArgumentPromotionPass());
773
774 // Lastly, add the core function simplification pipeline nested inside the
775 // CGSCC walk.
776 MainCGPipeline.addPass(createCGSCCToFunctionPassAdaptor(
777 buildFunctionSimplificationPipeline(Level, Phase, DebugLogging)));
778
779 for (auto &C : CGSCCOptimizerLateEPCallbacks)
780 C(MainCGPipeline, Level);
781
782 // We wrap the CGSCC pipeline in a devirtualization repeater. This will try
783 // to detect when we devirtualize indirect calls and iterate the SCC passes
784 // in that case to try and catch knock-on inlining or function attrs
785 // opportunities. Then we add it to the module pipeline by walking the SCCs
786 // in postorder (or bottom-up).
787 MPM.addPass(
788 createModuleToPostOrderCGSCCPassAdaptor(createDevirtSCCRepeatedPass(
789 std::move(MainCGPipeline), MaxDevirtIterations)));
790
791 return MPM;
792}
793
794ModulePassManager PassBuilder::buildModuleOptimizationPipeline(
795 OptimizationLevel Level, bool DebugLogging, bool LTOPreLink) {
796 ModulePassManager MPM(DebugLogging);
797
798 // Optimize globals now that the module is fully simplified.
799 MPM.addPass(GlobalOptPass());
800 MPM.addPass(GlobalDCEPass());
801
802 // Run partial inlining pass to partially inline functions that have
803 // large bodies.
804 if (RunPartialInlining)
805 MPM.addPass(PartialInlinerPass());
806
807 // Remove avail extern fns and globals definitions since we aren't compiling
808 // an object file for later LTO. For LTO we want to preserve these so they
809 // are eligible for inlining at link-time. Note if they are unreferenced they
810 // will be removed by GlobalDCE later, so this only impacts referenced
811 // available externally globals. Eventually they will be suppressed during
812 // codegen, but eliminating here enables more opportunity for GlobalDCE as it
813 // may make globals referenced by available external functions dead and saves
814 // running remaining passes on the eliminated functions.
815 MPM.addPass(EliminateAvailableExternallyPass());
816
817 if (EnableOrderFileInstrumentation)
818 MPM.addPass(InstrOrderFilePass());
819
820 // Do RPO function attribute inference across the module to forward-propagate
821 // attributes where applicable.
822 // FIXME: Is this really an optimization rather than a canonicalization?
823 MPM.addPass(ReversePostOrderFunctionAttrsPass());
824
825 // Do a post inline PGO instrumentation and use pass. This is a context
826 // sensitive PGO pass. We don't want to do this in LTOPreLink phrase as
827 // cross-module inline has not been done yet. The context sensitive
828 // instrumentation is after all the inlines are done.
829 if (!LTOPreLink && PGOOpt) {
830 if (PGOOpt->CSAction == PGOOptions::CSIRInstr)
831 addPGOInstrPasses(MPM, DebugLogging, Level, /* RunProfileGen */ true,
832 /* IsCS */ true, PGOOpt->CSProfileGenFile,
833 PGOOpt->ProfileRemappingFile);
834 else if (PGOOpt->CSAction == PGOOptions::CSIRUse)
835 addPGOInstrPasses(MPM, DebugLogging, Level, /* RunProfileGen */ false,
836 /* IsCS */ true, PGOOpt->ProfileFile,
837 PGOOpt->ProfileRemappingFile);
838 }
839
840 // Re-require GloblasAA here prior to function passes. This is particularly
841 // useful as the above will have inlined, DCE'ed, and function-attr
842 // propagated everything. We should at this point have a reasonably minimal
843 // and richly annotated call graph. By computing aliasing and mod/ref
844 // information for all local globals here, the late loop passes and notably
845 // the vectorizer will be able to use them to help recognize vectorizable
846 // memory operations.
847 MPM.addPass(RequireAnalysisPass<GlobalsAA, Module>());
848
849 FunctionPassManager OptimizePM(DebugLogging);
850 OptimizePM.addPass(Float2IntPass());
851 // FIXME: We need to run some loop optimizations to re-rotate loops after
852 // simplify-cfg and others undo their rotation.
853
854 // Optimize the loop execution. These passes operate on entire loop nests
855 // rather than on each loop in an inside-out manner, and so they are actually
856 // function passes.
857
858 for (auto &C : VectorizerStartEPCallbacks)
859 C(OptimizePM, Level);
860
861 // First rotate loops that may have been un-rotated by prior passes.
862 OptimizePM.addPass(
863 createFunctionToLoopPassAdaptor(LoopRotatePass(), DebugLogging));
864
865 // Distribute loops to allow partial vectorization. I.e. isolate dependences
866 // into separate loop that would otherwise inhibit vectorization. This is
867 // currently only performed for loops marked with the metadata
868 // llvm.loop.distribute=true or when -enable-loop-distribute is specified.
869 OptimizePM.addPass(LoopDistributePass());
870
871 // Now run the core loop vectorizer.
872 OptimizePM.addPass(LoopVectorizePass(
873 LoopVectorizeOptions(!PTO.LoopInterleaving, !PTO.LoopVectorization)));
874
875 // Eliminate loads by forwarding stores from the previous iteration to loads
876 // of the current iteration.
877 OptimizePM.addPass(LoopLoadEliminationPass());
878
879 // Cleanup after the loop optimization passes.
880 OptimizePM.addPass(InstCombinePass());
881
882 // Now that we've formed fast to execute loop structures, we do further
883 // optimizations. These are run afterward as they might block doing complex
884 // analyses and transforms such as what are needed for loop vectorization.
885
886 // Cleanup after loop vectorization, etc. Simplification passes like CVP and
887 // GVN, loop transforms, and others have already run, so it's now better to
888 // convert to more optimized IR using more aggressive simplify CFG options.
889 // The extra sinking transform can create larger basic blocks, so do this
890 // before SLP vectorization.
891 OptimizePM.addPass(SimplifyCFGPass(SimplifyCFGOptions().
892 forwardSwitchCondToPhi(true).
893 convertSwitchToLookupTable(true).
894 needCanonicalLoops(false).
895 sinkCommonInsts(true)));
896
897 // Optimize parallel scalar instruction chains into SIMD instructions.
898 if (PTO.SLPVectorization)
899 OptimizePM.addPass(SLPVectorizerPass());
900
901 OptimizePM.addPass(InstCombinePass());
902
903 // Unroll small loops to hide loop backedge latency and saturate any parallel
904 // execution resources of an out-of-order processor. We also then need to
905 // clean up redundancies and loop invariant code.
906 // FIXME: It would be really good to use a loop-integrated instruction
907 // combiner for cleanup here so that the unrolling and LICM can be pipelined
908 // across the loop nests.
909 // We do UnrollAndJam in a separate LPM to ensure it happens before unroll
910 if (EnableUnrollAndJam) {
911 OptimizePM.addPass(
912 createFunctionToLoopPassAdaptor(LoopUnrollAndJamPass(Level)));
913 }
914 if (PTO.LoopUnrolling)
915 OptimizePM.addPass(LoopUnrollPass(
916 LoopUnrollOptions(Level, false, PTO.ForgetAllSCEVInLoopUnroll)));
917 OptimizePM.addPass(WarnMissedTransformationsPass());
918 OptimizePM.addPass(InstCombinePass());
919 OptimizePM.addPass(RequireAnalysisPass<OptimizationRemarkEmitterAnalysis, Function>());
920 OptimizePM.addPass(createFunctionToLoopPassAdaptor(
921 LICMPass(PTO.LicmMssaOptCap, PTO.LicmMssaNoAccForPromotionCap),
922 DebugLogging));
923
924 // Now that we've vectorized and unrolled loops, we may have more refined
925 // alignment information, try to re-derive it here.
926 OptimizePM.addPass(AlignmentFromAssumptionsPass());
927
928 // Split out cold code. Splitting is done late to avoid hiding context from
929 // other optimizations and inadvertently regressing performance. The tradeoff
930 // is that this has a higher code size cost than splitting early.
931 if (EnableHotColdSplit && !LTOPreLink)
932 MPM.addPass(HotColdSplittingPass());
933
934 // LoopSink pass sinks instructions hoisted by LICM, which serves as a
935 // canonicalization pass that enables other optimizations. As a result,
936 // LoopSink pass needs to be a very late IR pass to avoid undoing LICM
937 // result too early.
938 OptimizePM.addPass(LoopSinkPass());
939
940 // And finally clean up LCSSA form before generating code.
941 OptimizePM.addPass(InstSimplifyPass());
942
943 // This hoists/decomposes div/rem ops. It should run after other sink/hoist
944 // passes to avoid re-sinking, but before SimplifyCFG because it can allow
945 // flattening of blocks.
946 OptimizePM.addPass(DivRemPairsPass());
947
948 // LoopSink (and other loop passes since the last simplifyCFG) might have
949 // resulted in single-entry-single-exit or empty blocks. Clean up the CFG.
950 OptimizePM.addPass(SimplifyCFGPass());
951
952 // Optimize PHIs by speculating around them when profitable. Note that this
953 // pass needs to be run after any PRE or similar pass as it is essentially
954 // inserting redundancies into the program. This even includes SimplifyCFG.
955 OptimizePM.addPass(SpeculateAroundPHIsPass());
956
957 for (auto &C : OptimizerLastEPCallbacks)
958 C(OptimizePM, Level);
959
960 // Add the core optimizing pipeline.
961 MPM.addPass(createModuleToFunctionPassAdaptor(std::move(OptimizePM)));
962
963 MPM.addPass(CGProfilePass());
964
965 // Now we need to do some global optimization transforms.
966 // FIXME: It would seem like these should come first in the optimization
967 // pipeline and maybe be the bottom of the canonicalization pipeline? Weird
968 // ordering here.
969 MPM.addPass(GlobalDCEPass());
970 MPM.addPass(ConstantMergePass());
971
972 return MPM;
973}
974
975ModulePassManager
976PassBuilder::buildPerModuleDefaultPipeline(OptimizationLevel Level,
977 bool DebugLogging, bool LTOPreLink) {
978 assert(Level != O0 && "Must request optimizations for the default pipeline!")((Level != O0 && "Must request optimizations for the default pipeline!"
) ? static_cast<void> (0) : __assert_fail ("Level != O0 && \"Must request optimizations for the default pipeline!\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/Passes/PassBuilder.cpp"
, 978, __PRETTY_FUNCTION__))
;
979
980 ModulePassManager MPM(DebugLogging);
981
982 // Force any function attributes we want the rest of the pipeline to observe.
983 MPM.addPass(ForceFunctionAttrsPass());
984
985 // Apply module pipeline start EP callback.
986 for (auto &C : PipelineStartEPCallbacks)
987 C(MPM);
988
989 if (PGOOpt && PGOOpt->SamplePGOSupport)
990 MPM.addPass(createModuleToFunctionPassAdaptor(AddDiscriminatorsPass()));
991
992 // Add the core simplification pipeline.
993 MPM.addPass(buildModuleSimplificationPipeline(Level, ThinLTOPhase::None,
994 DebugLogging));
995
996 // Now add the optimization pipeline.
997 MPM.addPass(buildModuleOptimizationPipeline(Level, DebugLogging, LTOPreLink));
998
999 return MPM;
1000}
1001
1002ModulePassManager
1003PassBuilder::buildThinLTOPreLinkDefaultPipeline(OptimizationLevel Level,
1004 bool DebugLogging) {
1005 assert(Level != O0 && "Must request optimizations for the default pipeline!")((Level != O0 && "Must request optimizations for the default pipeline!"
) ? static_cast<void> (0) : __assert_fail ("Level != O0 && \"Must request optimizations for the default pipeline!\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/Passes/PassBuilder.cpp"
, 1005, __PRETTY_FUNCTION__))
;
1006
1007 ModulePassManager MPM(DebugLogging);
1008
1009 // Force any function attributes we want the rest of the pipeline to observe.
1010 MPM.addPass(ForceFunctionAttrsPass());
1011
1012 if (PGOOpt && PGOOpt->SamplePGOSupport)
1013 MPM.addPass(createModuleToFunctionPassAdaptor(AddDiscriminatorsPass()));
1014
1015 // Apply module pipeline start EP callback.
1016 for (auto &C : PipelineStartEPCallbacks)
1017 C(MPM);
1018
1019 // If we are planning to perform ThinLTO later, we don't bloat the code with
1020 // unrolling/vectorization/... now. Just simplify the module as much as we
1021 // can.
1022 MPM.addPass(buildModuleSimplificationPipeline(Level, ThinLTOPhase::PreLink,
1023 DebugLogging));
1024
1025 // Run partial inlining pass to partially inline functions that have
1026 // large bodies.
1027 // FIXME: It isn't clear whether this is really the right place to run this
1028 // in ThinLTO. Because there is another canonicalization and simplification
1029 // phase that will run after the thin link, running this here ends up with
1030 // less information than will be available later and it may grow functions in
1031 // ways that aren't beneficial.
1032 if (RunPartialInlining)
1033 MPM.addPass(PartialInlinerPass());
1034
1035 // Reduce the size of the IR as much as possible.
1036 MPM.addPass(GlobalOptPass());
1037
1038 return MPM;
1039}
1040
1041ModulePassManager PassBuilder::buildThinLTODefaultPipeline(
1042 OptimizationLevel Level, bool DebugLogging,
1043 const ModuleSummaryIndex *ImportSummary) {
1044 ModulePassManager MPM(DebugLogging);
1045
1046 if (ImportSummary) {
1047 // These passes import type identifier resolutions for whole-program
1048 // devirtualization and CFI. They must run early because other passes may
1049 // disturb the specific instruction patterns that these passes look for,
1050 // creating dependencies on resolutions that may not appear in the summary.
1051 //
1052 // For example, GVN may transform the pattern assume(type.test) appearing in
1053 // two basic blocks into assume(phi(type.test, type.test)), which would
1054 // transform a dependency on a WPD resolution into a dependency on a type
1055 // identifier resolution for CFI.
1056 //
1057 // Also, WPD has access to more precise information than ICP and can
1058 // devirtualize more effectively, so it should operate on the IR first.
1059 //
1060 // The WPD and LowerTypeTest passes need to run at -O0 to lower type
1061 // metadata and intrinsics.
1062 MPM.addPass(WholeProgramDevirtPass(nullptr, ImportSummary));
1063 MPM.addPass(LowerTypeTestsPass(nullptr, ImportSummary));
1064 }
1065
1066 if (Level == O0)
1067 return MPM;
1068
1069 // Force any function attributes we want the rest of the pipeline to observe.
1070 MPM.addPass(ForceFunctionAttrsPass());
1071
1072 // Add the core simplification pipeline.
1073 MPM.addPass(buildModuleSimplificationPipeline(Level, ThinLTOPhase::PostLink,
1074 DebugLogging));
1075
1076 // Now add the optimization pipeline.
1077 MPM.addPass(buildModuleOptimizationPipeline(Level, DebugLogging));
1078
1079 return MPM;
1080}
1081
1082ModulePassManager
1083PassBuilder::buildLTOPreLinkDefaultPipeline(OptimizationLevel Level,
1084 bool DebugLogging) {
1085 assert(Level != O0 && "Must request optimizations for the default pipeline!")((Level != O0 && "Must request optimizations for the default pipeline!"
) ? static_cast<void> (0) : __assert_fail ("Level != O0 && \"Must request optimizations for the default pipeline!\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/Passes/PassBuilder.cpp"
, 1085, __PRETTY_FUNCTION__))
;
1086 // FIXME: We should use a customized pre-link pipeline!
1087 return buildPerModuleDefaultPipeline(Level, DebugLogging,
1088 /* LTOPreLink */true);
1089}
1090
1091ModulePassManager
1092PassBuilder::buildLTODefaultPipeline(OptimizationLevel Level, bool DebugLogging,
1093 ModuleSummaryIndex *ExportSummary) {
1094 ModulePassManager MPM(DebugLogging);
1095
1096 if (Level == O0) {
1097 // The WPD and LowerTypeTest passes need to run at -O0 to lower type
1098 // metadata and intrinsics.
1099 MPM.addPass(WholeProgramDevirtPass(ExportSummary, nullptr));
1100 MPM.addPass(LowerTypeTestsPass(ExportSummary, nullptr));
1101 return MPM;
1102 }
1103
1104 if (PGOOpt && PGOOpt->Action == PGOOptions::SampleUse) {
1105 // Load sample profile before running the LTO optimization pipeline.
1106 MPM.addPass(SampleProfileLoaderPass(PGOOpt->ProfileFile,
1107 PGOOpt->ProfileRemappingFile,
1108 false /* ThinLTOPhase::PreLink */));
1109 // Cache ProfileSummaryAnalysis once to avoid the potential need to insert
1110 // RequireAnalysisPass for PSI before subsequent non-module passes.
1111 MPM.addPass(RequireAnalysisPass<ProfileSummaryAnalysis, Module>());
1112 }
1113
1114 // Remove unused virtual tables to improve the quality of code generated by
1115 // whole-program devirtualization and bitset lowering.
1116 MPM.addPass(GlobalDCEPass());
1117
1118 // Force any function attributes we want the rest of the pipeline to observe.
1119 MPM.addPass(ForceFunctionAttrsPass());
1120
1121 // Do basic inference of function attributes from known properties of system
1122 // libraries and other oracles.
1123 MPM.addPass(InferFunctionAttrsPass());
1124
1125 if (Level > 1) {
1126 FunctionPassManager EarlyFPM(DebugLogging);
1127 EarlyFPM.addPass(CallSiteSplittingPass());
1128 MPM.addPass(createModuleToFunctionPassAdaptor(std::move(EarlyFPM)));
1129
1130 // Indirect call promotion. This should promote all the targets that are
1131 // left by the earlier promotion pass that promotes intra-module targets.
1132 // This two-step promotion is to save the compile time. For LTO, it should
1133 // produce the same result as if we only do promotion here.
1134 MPM.addPass(PGOIndirectCallPromotion(
1135 true /* InLTO */, PGOOpt && PGOOpt->Action == PGOOptions::SampleUse));
1136 // Propagate constants at call sites into the functions they call. This
1137 // opens opportunities for globalopt (and inlining) by substituting function
1138 // pointers passed as arguments to direct uses of functions.
1139 MPM.addPass(IPSCCPPass());
1140
1141 // Attach metadata to indirect call sites indicating the set of functions
1142 // they may target at run-time. This should follow IPSCCP.
1143 MPM.addPass(CalledValuePropagationPass());
1144 }
1145
1146 // Now deduce any function attributes based in the current code.
1147 MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(
1148 PostOrderFunctionAttrsPass()));
1149
1150 // Do RPO function attribute inference across the module to forward-propagate
1151 // attributes where applicable.
1152 // FIXME: Is this really an optimization rather than a canonicalization?
1153 MPM.addPass(ReversePostOrderFunctionAttrsPass());
1154
1155 // Use in-range annotations on GEP indices to split globals where beneficial.
1156 MPM.addPass(GlobalSplitPass());
1157
1158 // Run whole program optimization of virtual call when the list of callees
1159 // is fixed.
1160 MPM.addPass(WholeProgramDevirtPass(ExportSummary, nullptr));
1161
1162 // Stop here at -O1.
1163 if (Level == 1) {
1164 // The LowerTypeTestsPass needs to run to lower type metadata and the
1165 // type.test intrinsics. The pass does nothing if CFI is disabled.
1166 MPM.addPass(LowerTypeTestsPass(ExportSummary, nullptr));
1167 return MPM;
1168 }
1169
1170 // Optimize globals to try and fold them into constants.
1171 MPM.addPass(GlobalOptPass());
1172
1173 // Promote any localized globals to SSA registers.
1174 MPM.addPass(createModuleToFunctionPassAdaptor(PromotePass()));
1175
1176 // Linking modules together can lead to duplicate global constant, only
1177 // keep one copy of each constant.
1178 MPM.addPass(ConstantMergePass());
1179
1180 // Remove unused arguments from functions.
1181 MPM.addPass(DeadArgumentEliminationPass());
1182
1183 // Reduce the code after globalopt and ipsccp. Both can open up significant
1184 // simplification opportunities, and both can propagate functions through
1185 // function pointers. When this happens, we often have to resolve varargs
1186 // calls, etc, so let instcombine do this.
1187 FunctionPassManager PeepholeFPM(DebugLogging);
1188 if (Level == O3)
1189 PeepholeFPM.addPass(AggressiveInstCombinePass());
1190 PeepholeFPM.addPass(InstCombinePass());
1191 invokePeepholeEPCallbacks(PeepholeFPM, Level);
1192
1193 MPM.addPass(createModuleToFunctionPassAdaptor(std::move(PeepholeFPM)));
1194
1195 // Note: historically, the PruneEH pass was run first to deduce nounwind and
1196 // generally clean up exception handling overhead. It isn't clear this is
1197 // valuable as the inliner doesn't currently care whether it is inlining an
1198 // invoke or a call.
1199 // Run the inliner now.
1200 MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(
1201 InlinerPass(getInlineParamsFromOptLevel(Level))));
1202
1203 // Optimize globals again after we ran the inliner.
1204 MPM.addPass(GlobalOptPass());
1205
1206 // Garbage collect dead functions.
1207 // FIXME: Add ArgumentPromotion pass after once it's ported.
1208 MPM.addPass(GlobalDCEPass());
1209
1210 FunctionPassManager FPM(DebugLogging);
1211 // The IPO Passes may leave cruft around. Clean up after them.
1212 FPM.addPass(InstCombinePass());
1213 invokePeepholeEPCallbacks(FPM, Level);
1214
1215 FPM.addPass(JumpThreadingPass());
1216
1217 // Do a post inline PGO instrumentation and use pass. This is a context
1218 // sensitive PGO pass.
1219 if (PGOOpt) {
1220 if (PGOOpt->CSAction == PGOOptions::CSIRInstr)
1221 addPGOInstrPasses(MPM, DebugLogging, Level, /* RunProfileGen */ true,
1222 /* IsCS */ true, PGOOpt->CSProfileGenFile,
1223 PGOOpt->ProfileRemappingFile);
1224 else if (PGOOpt->CSAction == PGOOptions::CSIRUse)
1225 addPGOInstrPasses(MPM, DebugLogging, Level, /* RunProfileGen */ false,
1226 /* IsCS */ true, PGOOpt->ProfileFile,
1227 PGOOpt->ProfileRemappingFile);
1228 }
1229
1230 // Break up allocas
1231 FPM.addPass(SROA());
1232
1233 // LTO provides additional opportunities for tailcall elimination due to
1234 // link-time inlining, and visibility of nocapture attribute.
1235 FPM.addPass(TailCallElimPass());
1236
1237 // Run a few AA driver optimizations here and now to cleanup the code.
1238 MPM.addPass(createModuleToFunctionPassAdaptor(std::move(FPM)));
1239
1240 MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(
1241 PostOrderFunctionAttrsPass()));
1242 // FIXME: here we run IP alias analysis in the legacy PM.
1243
1244 FunctionPassManager MainFPM;
1245
1246 // FIXME: once we fix LoopPass Manager, add LICM here.
1247 // FIXME: once we provide support for enabling MLSM, add it here.
1248 if (RunNewGVN)
1249 MainFPM.addPass(NewGVNPass());
1250 else
1251 MainFPM.addPass(GVN());
1252
1253 // Remove dead memcpy()'s.
1254 MainFPM.addPass(MemCpyOptPass());
1255
1256 // Nuke dead stores.
1257 MainFPM.addPass(DSEPass());
1258
1259 // FIXME: at this point, we run a bunch of loop passes:
1260 // indVarSimplify, loopDeletion, loopInterchange, loopUnroll,
1261 // loopVectorize. Enable them once the remaining issue with LPM
1262 // are sorted out.
1263
1264 MainFPM.addPass(InstCombinePass());
1265 MainFPM.addPass(SimplifyCFGPass());
1266 MainFPM.addPass(SCCPPass());
1267 MainFPM.addPass(InstCombinePass());
1268 MainFPM.addPass(BDCEPass());
1269
1270 // FIXME: We may want to run SLPVectorizer here.
1271 // After vectorization, assume intrinsics may tell us more
1272 // about pointer alignments.
1273#if 0
1274 MainFPM.add(AlignmentFromAssumptionsPass());
1275#endif
1276
1277 // FIXME: Conditionally run LoadCombine here, after it's ported
1278 // (in case we still have this pass, given its questionable usefulness).
1279
1280 MainFPM.addPass(InstCombinePass());
1281 invokePeepholeEPCallbacks(MainFPM, Level);
1282 MainFPM.addPass(JumpThreadingPass());
1283 MPM.addPass(createModuleToFunctionPassAdaptor(std::move(MainFPM)));
1284
1285 // Create a function that performs CFI checks for cross-DSO calls with
1286 // targets in the current module.
1287 MPM.addPass(CrossDSOCFIPass());
1288
1289 // Lower type metadata and the type.test intrinsic. This pass supports
1290 // clang's control flow integrity mechanisms (-fsanitize=cfi*) and needs
1291 // to be run at link time if CFI is enabled. This pass does nothing if
1292 // CFI is disabled.
1293 MPM.addPass(LowerTypeTestsPass(ExportSummary, nullptr));
1294
1295 // Enable splitting late in the FullLTO post-link pipeline. This is done in
1296 // the same stage in the old pass manager (\ref addLateLTOOptimizationPasses).
1297 if (EnableHotColdSplit)
1298 MPM.addPass(HotColdSplittingPass());
1299
1300 // Add late LTO optimization passes.
1301 // Delete basic blocks, which optimization passes may have killed.
1302 MPM.addPass(createModuleToFunctionPassAdaptor(SimplifyCFGPass()));
1303
1304 // Drop bodies of available eternally objects to improve GlobalDCE.
1305 MPM.addPass(EliminateAvailableExternallyPass());
1306
1307 // Now that we have optimized the program, discard unreachable functions.
1308 MPM.addPass(GlobalDCEPass());
1309
1310 // FIXME: Maybe enable MergeFuncs conditionally after it's ported.
1311 return MPM;
1312}
1313
1314AAManager PassBuilder::buildDefaultAAPipeline() {
1315 AAManager AA;
1316
1317 // The order in which these are registered determines their priority when
1318 // being queried.
1319
1320 // First we register the basic alias analysis that provides the majority of
1321 // per-function local AA logic. This is a stateless, on-demand local set of
1322 // AA techniques.
1323 AA.registerFunctionAnalysis<BasicAA>();
1324
1325 // Next we query fast, specialized alias analyses that wrap IR-embedded
1326 // information about aliasing.
1327 AA.registerFunctionAnalysis<ScopedNoAliasAA>();
1328 AA.registerFunctionAnalysis<TypeBasedAA>();
1329
1330 // Add support for querying global aliasing information when available.
1331 // Because the `AAManager` is a function analysis and `GlobalsAA` is a module
1332 // analysis, all that the `AAManager` can do is query for any *cached*
1333 // results from `GlobalsAA` through a readonly proxy.
1334 AA.registerModuleAnalysis<GlobalsAA>();
1335
1336 return AA;
1337}
1338
1339static Optional<int> parseRepeatPassName(StringRef Name) {
1340 if (!Name.consume_front("repeat<") || !Name.consume_back(">"))
1341 return None;
1342 int Count;
1343 if (Name.getAsInteger(0, Count) || Count <= 0)
1344 return None;
1345 return Count;
1346}
1347
1348static Optional<int> parseDevirtPassName(StringRef Name) {
1349 if (!Name.consume_front("devirt<") || !Name.consume_back(">"))
1350 return None;
1351 int Count;
1352 if (Name.getAsInteger(0, Count) || Count <= 0)
1353 return None;
1354 return Count;
1355}
1356
1357static bool checkParametrizedPassName(StringRef Name, StringRef PassName) {
1358 if (!Name.consume_front(PassName))
1359 return false;
1360 // normal pass name w/o parameters == default parameters
1361 if (Name.empty())
1362 return true;
1363 return Name.startswith("<") && Name.endswith(">");
1364}
1365
1366namespace {
1367
1368/// This performs customized parsing of pass name with parameters.
1369///
1370/// We do not need parametrization of passes in textual pipeline very often,
1371/// yet on a rare occasion ability to specify parameters right there can be
1372/// useful.
1373///
1374/// \p Name - parameterized specification of a pass from a textual pipeline
1375/// is a string in a form of :
1376/// PassName '<' parameter-list '>'
1377///
1378/// Parameter list is being parsed by the parser callable argument, \p Parser,
1379/// It takes a string-ref of parameters and returns either StringError or a
1380/// parameter list in a form of a custom parameters type, all wrapped into
1381/// Expected<> template class.
1382///
1383template <typename ParametersParseCallableT>
1384auto parsePassParameters(ParametersParseCallableT &&Parser, StringRef Name,
1385 StringRef PassName) -> decltype(Parser(StringRef{})) {
1386 using ParametersT = typename decltype(Parser(StringRef{}))::value_type;
1387
1388 StringRef Params = Name;
1389 if (!Params.consume_front(PassName)) {
1390 assert(false &&((false && "unable to strip pass name from parametrized pass specification"
) ? static_cast<void> (0) : __assert_fail ("false && \"unable to strip pass name from parametrized pass specification\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/Passes/PassBuilder.cpp"
, 1391, __PRETTY_FUNCTION__))
1391 "unable to strip pass name from parametrized pass specification")((false && "unable to strip pass name from parametrized pass specification"
) ? static_cast<void> (0) : __assert_fail ("false && \"unable to strip pass name from parametrized pass specification\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/Passes/PassBuilder.cpp"
, 1391, __PRETTY_FUNCTION__))
;
1392 }
1393 if (Params.empty())
1394 return ParametersT{};
1395 if (!Params.consume_front("<") || !Params.consume_back(">")) {
1396 assert(false && "invalid format for parametrized pass name")((false && "invalid format for parametrized pass name"
) ? static_cast<void> (0) : __assert_fail ("false && \"invalid format for parametrized pass name\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/Passes/PassBuilder.cpp"
, 1396, __PRETTY_FUNCTION__))
;
1397 }
1398
1399 Expected<ParametersT> Result = Parser(Params);
1400 assert((Result || Result.template errorIsA<StringError>()) &&(((Result || Result.template errorIsA<StringError>()) &&
"Pass parameter parser can only return StringErrors.") ? static_cast
<void> (0) : __assert_fail ("(Result || Result.template errorIsA<StringError>()) && \"Pass parameter parser can only return StringErrors.\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/Passes/PassBuilder.cpp"
, 1401, __PRETTY_FUNCTION__))
1401 "Pass parameter parser can only return StringErrors.")(((Result || Result.template errorIsA<StringError>()) &&
"Pass parameter parser can only return StringErrors.") ? static_cast
<void> (0) : __assert_fail ("(Result || Result.template errorIsA<StringError>()) && \"Pass parameter parser can only return StringErrors.\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/Passes/PassBuilder.cpp"
, 1401, __PRETTY_FUNCTION__))
;
1402 return std::move(Result);
1403}
1404
1405/// Parser of parameters for LoopUnroll pass.
1406Expected<LoopUnrollOptions> parseLoopUnrollOptions(StringRef Params) {
1407 LoopUnrollOptions UnrollOpts;
1408 while (!Params.empty()) {
1409 StringRef ParamName;
1410 std::tie(ParamName, Params) = Params.split(';');
1411 int OptLevel = StringSwitch<int>(ParamName)
1412 .Case("O0", 0)
1413 .Case("O1", 1)
1414 .Case("O2", 2)
1415 .Case("O3", 3)
1416 .Default(-1);
1417 if (OptLevel >= 0) {
1418 UnrollOpts.setOptLevel(OptLevel);
1419 continue;
1420 }
1421
1422 bool Enable = !ParamName.consume_front("no-");
1423 if (ParamName == "partial") {
1424 UnrollOpts.setPartial(Enable);
1425 } else if (ParamName == "peeling") {
1426 UnrollOpts.setPeeling(Enable);
1427 } else if (ParamName == "runtime") {
1428 UnrollOpts.setRuntime(Enable);
1429 } else if (ParamName == "upperbound") {
1430 UnrollOpts.setUpperBound(Enable);
1431 } else {
1432 return make_error<StringError>(
1433 formatv("invalid LoopUnrollPass parameter '{0}' ", ParamName).str(),
1434 inconvertibleErrorCode());
1435 }
1436 }
1437 return UnrollOpts;
1438}
1439
1440Expected<MemorySanitizerOptions> parseMSanPassOptions(StringRef Params) {
1441 MemorySanitizerOptions Result;
1442 while (!Params.empty()) {
1443 StringRef ParamName;
1444 std::tie(ParamName, Params) = Params.split(';');
1445
1446 if (ParamName == "recover") {
1447 Result.Recover = true;
1448 } else if (ParamName == "kernel") {
1449 Result.Kernel = true;
1450 } else if (ParamName.consume_front("track-origins=")) {
1451 if (ParamName.getAsInteger(0, Result.TrackOrigins))
1452 return make_error<StringError>(
1453 formatv("invalid argument to MemorySanitizer pass track-origins "
1454 "parameter: '{0}' ",
1455 ParamName)
1456 .str(),
1457 inconvertibleErrorCode());
1458 } else {
1459 return make_error<StringError>(
1460 formatv("invalid MemorySanitizer pass parameter '{0}' ", ParamName)
1461 .str(),
1462 inconvertibleErrorCode());
1463 }
1464 }
1465 return Result;
1466}
1467
1468/// Parser of parameters for SimplifyCFG pass.
1469Expected<SimplifyCFGOptions> parseSimplifyCFGOptions(StringRef Params) {
1470 SimplifyCFGOptions Result;
1471 while (!Params.empty()) {
1472 StringRef ParamName;
1473 std::tie(ParamName, Params) = Params.split(';');
1474
1475 bool Enable = !ParamName.consume_front("no-");
1476 if (ParamName == "forward-switch-cond") {
1477 Result.forwardSwitchCondToPhi(Enable);
1478 } else if (ParamName == "switch-to-lookup") {
1479 Result.convertSwitchToLookupTable(Enable);
1480 } else if (ParamName == "keep-loops") {
1481 Result.needCanonicalLoops(Enable);
1482 } else if (ParamName == "sink-common-insts") {
1483 Result.sinkCommonInsts(Enable);
1484 } else if (Enable && ParamName.consume_front("bonus-inst-threshold=")) {
1485 APInt BonusInstThreshold;
1486 if (ParamName.getAsInteger(0, BonusInstThreshold))
1487 return make_error<StringError>(
1488 formatv("invalid argument to SimplifyCFG pass bonus-threshold "
1489 "parameter: '{0}' ",
1490 ParamName).str(),
1491 inconvertibleErrorCode());
1492 Result.bonusInstThreshold(BonusInstThreshold.getSExtValue());
1493 } else {
1494 return make_error<StringError>(
1495 formatv("invalid SimplifyCFG pass parameter '{0}' ", ParamName).str(),
1496 inconvertibleErrorCode());
1497 }
1498 }
1499 return Result;
1500}
1501
1502/// Parser of parameters for LoopVectorize pass.
1503Expected<LoopVectorizeOptions> parseLoopVectorizeOptions(StringRef Params) {
1504 LoopVectorizeOptions Opts;
1505 while (!Params.empty()) {
1506 StringRef ParamName;
1507 std::tie(ParamName, Params) = Params.split(';');
1508
1509 bool Enable = !ParamName.consume_front("no-");
1510 if (ParamName == "interleave-forced-only") {
1511 Opts.setInterleaveOnlyWhenForced(Enable);
1512 } else if (ParamName == "vectorize-forced-only") {
1513 Opts.setVectorizeOnlyWhenForced(Enable);
1514 } else {
1515 return make_error<StringError>(
1516 formatv("invalid LoopVectorize parameter '{0}' ", ParamName).str(),
1517 inconvertibleErrorCode());
1518 }
1519 }
1520 return Opts;
1521}
1522
1523Expected<bool> parseLoopUnswitchOptions(StringRef Params) {
1524 bool Result = false;
1525 while (!Params.empty()) {
1526 StringRef ParamName;
1527 std::tie(ParamName, Params) = Params.split(';');
1528
1529 bool Enable = !ParamName.consume_front("no-");
1530 if (ParamName == "nontrivial") {
1531 Result = Enable;
1532 } else {
1533 return make_error<StringError>(
1534 formatv("invalid LoopUnswitch pass parameter '{0}' ", ParamName)
1535 .str(),
1536 inconvertibleErrorCode());
1537 }
1538 }
1539 return Result;
1540}
1541} // namespace
1542
1543/// Tests whether a pass name starts with a valid prefix for a default pipeline
1544/// alias.
1545static bool startsWithDefaultPipelineAliasPrefix(StringRef Name) {
1546 return Name.startswith("default") || Name.startswith("thinlto") ||
1547 Name.startswith("lto");
1548}
1549
1550/// Tests whether registered callbacks will accept a given pass name.
1551///
1552/// When parsing a pipeline text, the type of the outermost pipeline may be
1553/// omitted, in which case the type is automatically determined from the first
1554/// pass name in the text. This may be a name that is handled through one of the
1555/// callbacks. We check this through the oridinary parsing callbacks by setting
1556/// up a dummy PassManager in order to not force the client to also handle this
1557/// type of query.
1558template <typename PassManagerT, typename CallbacksT>
1559static bool callbacksAcceptPassName(StringRef Name, CallbacksT &Callbacks) {
1560 if (!Callbacks.empty()) {
1561 PassManagerT DummyPM;
1562 for (auto &CB : Callbacks)
1563 if (CB(Name, DummyPM, {}))
1564 return true;
1565 }
1566 return false;
1567}
1568
1569template <typename CallbacksT>
1570static bool isModulePassName(StringRef Name, CallbacksT &Callbacks) {
1571 // Manually handle aliases for pre-configured pipeline fragments.
1572 if (startsWithDefaultPipelineAliasPrefix(Name))
1573 return DefaultAliasRegex.match(Name);
1574
1575 // Explicitly handle pass manager names.
1576 if (Name == "module")
1577 return true;
1578 if (Name == "cgscc")
1579 return true;
1580 if (Name == "function")
1581 return true;
1582
1583 // Explicitly handle custom-parsed pass names.
1584 if (parseRepeatPassName(Name))
1585 return true;
1586
1587#define MODULE_PASS(NAME, CREATE_PASS) \
1588 if (Name == NAME) \
1589 return true;
1590#define MODULE_ANALYSIS(NAME, CREATE_PASS) \
1591 if (Name == "require<" NAME ">" || Name == "invalidate<" NAME ">") \
1592 return true;
1593#include "PassRegistry.def"
1594
1595 return callbacksAcceptPassName<ModulePassManager>(Name, Callbacks);
1596}
1597
1598template <typename CallbacksT>
1599static bool isCGSCCPassName(StringRef Name, CallbacksT &Callbacks) {
1600 // Explicitly handle pass manager names.
1601 if (Name == "cgscc")
1602 return true;
1603 if (Name == "function")
1604 return true;
1605
1606 // Explicitly handle custom-parsed pass names.
1607 if (parseRepeatPassName(Name))
1608 return true;
1609 if (parseDevirtPassName(Name))
1610 return true;
1611
1612#define CGSCC_PASS(NAME, CREATE_PASS) \
1613 if (Name == NAME) \
1614 return true;
1615#define CGSCC_ANALYSIS(NAME, CREATE_PASS) \
1616 if (Name == "require<" NAME ">" || Name == "invalidate<" NAME ">") \
1617 return true;
1618#include "PassRegistry.def"
1619
1620 return callbacksAcceptPassName<CGSCCPassManager>(Name, Callbacks);
1621}
1622
1623template <typename CallbacksT>
1624static bool isFunctionPassName(StringRef Name, CallbacksT &Callbacks) {
1625 // Explicitly handle pass manager names.
1626 if (Name == "function")
1627 return true;
1628 if (Name == "loop")
1629 return true;
1630
1631 // Explicitly handle custom-parsed pass names.
1632 if (parseRepeatPassName(Name))
1633 return true;
1634
1635#define FUNCTION_PASS(NAME, CREATE_PASS) \
1636 if (Name == NAME) \
1637 return true;
1638#define FUNCTION_PASS_WITH_PARAMS(NAME, CREATE_PASS, PARSER) \
1639 if (checkParametrizedPassName(Name, NAME)) \
1640 return true;
1641#define FUNCTION_ANALYSIS(NAME, CREATE_PASS) \
1642 if (Name == "require<" NAME ">" || Name == "invalidate<" NAME ">") \
1643 return true;
1644#include "PassRegistry.def"
1645
1646 return callbacksAcceptPassName<FunctionPassManager>(Name, Callbacks);
1647}
1648
1649template <typename CallbacksT>
1650static bool isLoopPassName(StringRef Name, CallbacksT &Callbacks) {
1651 // Explicitly handle pass manager names.
1652 if (Name == "loop")
1653 return true;
1654
1655 // Explicitly handle custom-parsed pass names.
1656 if (parseRepeatPassName(Name))
1657 return true;
1658
1659#define LOOP_PASS(NAME, CREATE_PASS) \
1660 if (Name == NAME) \
1661 return true;
1662#define LOOP_PASS_WITH_PARAMS(NAME, CREATE_PASS, PARSER) \
1663 if (checkParametrizedPassName(Name, NAME)) \
1664 return true;
1665#define LOOP_ANALYSIS(NAME, CREATE_PASS) \
1666 if (Name == "require<" NAME ">" || Name == "invalidate<" NAME ">") \
1667 return true;
1668#include "PassRegistry.def"
1669
1670 return callbacksAcceptPassName<LoopPassManager>(Name, Callbacks);
1671}
1672
1673Optional<std::vector<PassBuilder::PipelineElement>>
1674PassBuilder::parsePipelineText(StringRef Text) {
1675 std::vector<PipelineElement> ResultPipeline;
1676
1677 SmallVector<std::vector<PipelineElement> *, 4> PipelineStack = {
1678 &ResultPipeline};
1679 for (;;) {
1680 std::vector<PipelineElement> &Pipeline = *PipelineStack.back();
1681 size_t Pos = Text.find_first_of(",()");
1682 Pipeline.push_back({Text.substr(0, Pos), {}});
1683
1684 // If we have a single terminating name, we're done.
1685 if (Pos == Text.npos)
1686 break;
1687
1688 char Sep = Text[Pos];
1689 Text = Text.substr(Pos + 1);
1690 if (Sep == ',')
1691 // Just a name ending in a comma, continue.
1692 continue;
1693
1694 if (Sep == '(') {
1695 // Push the inner pipeline onto the stack to continue processing.
1696 PipelineStack.push_back(&Pipeline.back().InnerPipeline);
1697 continue;
1698 }
1699
1700 assert(Sep == ')' && "Bogus separator!")((Sep == ')' && "Bogus separator!") ? static_cast<
void> (0) : __assert_fail ("Sep == ')' && \"Bogus separator!\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/Passes/PassBuilder.cpp"
, 1700, __PRETTY_FUNCTION__))
;
1701 // When handling the close parenthesis, we greedily consume them to avoid
1702 // empty strings in the pipeline.
1703 do {
1704 // If we try to pop the outer pipeline we have unbalanced parentheses.
1705 if (PipelineStack.size() == 1)
1706 return None;
1707
1708 PipelineStack.pop_back();
1709 } while (Text.consume_front(")"));
1710
1711 // Check if we've finished parsing.
1712 if (Text.empty())
1713 break;
1714
1715 // Otherwise, the end of an inner pipeline always has to be followed by
1716 // a comma, and then we can continue.
1717 if (!Text.consume_front(","))
1718 return None;
1719 }
1720
1721 if (PipelineStack.size() > 1)
1722 // Unbalanced paretheses.
1723 return None;
1724
1725 assert(PipelineStack.back() == &ResultPipeline &&((PipelineStack.back() == &ResultPipeline && "Wrong pipeline at the bottom of the stack!"
) ? static_cast<void> (0) : __assert_fail ("PipelineStack.back() == &ResultPipeline && \"Wrong pipeline at the bottom of the stack!\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/Passes/PassBuilder.cpp"
, 1726, __PRETTY_FUNCTION__))
1726 "Wrong pipeline at the bottom of the stack!")((PipelineStack.back() == &ResultPipeline && "Wrong pipeline at the bottom of the stack!"
) ? static_cast<void> (0) : __assert_fail ("PipelineStack.back() == &ResultPipeline && \"Wrong pipeline at the bottom of the stack!\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/Passes/PassBuilder.cpp"
, 1726, __PRETTY_FUNCTION__))
;
1727 return {std::move(ResultPipeline)};
1728}
1729
1730Error PassBuilder::parseModulePass(ModulePassManager &MPM,
1731 const PipelineElement &E,
1732 bool VerifyEachPass, bool DebugLogging) {
1733 auto &Name = E.Name;
1734 auto &InnerPipeline = E.InnerPipeline;
1735
1736 // First handle complex passes like the pass managers which carry pipelines.
1737 if (!InnerPipeline.empty()) {
1738 if (Name == "module") {
1739 ModulePassManager NestedMPM(DebugLogging);
1740 if (auto Err = parseModulePassPipeline(NestedMPM, InnerPipeline,
1741 VerifyEachPass, DebugLogging))
1742 return Err;
1743 MPM.addPass(std::move(NestedMPM));
1744 return Error::success();
1745 }
1746 if (Name == "cgscc") {
1747 CGSCCPassManager CGPM(DebugLogging);
1748 if (auto Err = parseCGSCCPassPipeline(CGPM, InnerPipeline, VerifyEachPass,
1749 DebugLogging))
1750 return Err;
1751 MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM)));
1752 return Error::success();
1753 }
1754 if (Name == "function") {
1755 FunctionPassManager FPM(DebugLogging);
1756 if (auto Err = parseFunctionPassPipeline(FPM, InnerPipeline,
1757 VerifyEachPass, DebugLogging))
1758 return Err;
1759 MPM.addPass(createModuleToFunctionPassAdaptor(std::move(FPM)));
1760 return Error::success();
1761 }
1762 if (auto Count = parseRepeatPassName(Name)) {
1763 ModulePassManager NestedMPM(DebugLogging);
1764 if (auto Err = parseModulePassPipeline(NestedMPM, InnerPipeline,
1765 VerifyEachPass, DebugLogging))
1766 return Err;
1767 MPM.addPass(createRepeatedPass(*Count, std::move(NestedMPM)));
1768 return Error::success();
1769 }
1770
1771 for (auto &C : ModulePipelineParsingCallbacks)
1772 if (C(Name, MPM, InnerPipeline))
1773 return Error::success();
1774
1775 // Normal passes can't have pipelines.
1776 return make_error<StringError>(
1777 formatv("invalid use of '{0}' pass as module pipeline", Name).str(),
1778 inconvertibleErrorCode());
1779 ;
1780 }
1781
1782 // Manually handle aliases for pre-configured pipeline fragments.
1783 if (startsWithDefaultPipelineAliasPrefix(Name)) {
1784 SmallVector<StringRef, 3> Matches;
1785 if (!DefaultAliasRegex.match(Name, &Matches))
1786 return make_error<StringError>(
1787 formatv("unknown default pipeline alias '{0}'", Name).str(),
1788 inconvertibleErrorCode());
1789
1790 assert(Matches.size() == 3 && "Must capture two matched strings!")((Matches.size() == 3 && "Must capture two matched strings!"
) ? static_cast<void> (0) : __assert_fail ("Matches.size() == 3 && \"Must capture two matched strings!\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/Passes/PassBuilder.cpp"
, 1790, __PRETTY_FUNCTION__))
;
1791
1792 OptimizationLevel L = StringSwitch<OptimizationLevel>(Matches[2])
1793 .Case("O0", O0)
1794 .Case("O1", O1)
1795 .Case("O2", O2)
1796 .Case("O3", O3)
1797 .Case("Os", Os)
1798 .Case("Oz", Oz);
1799 if (L == O0)
1800 // At O0 we do nothing at all!
1801 return Error::success();
1802
1803 if (Matches[1] == "default") {
1804 MPM.addPass(buildPerModuleDefaultPipeline(L, DebugLogging));
1805 } else if (Matches[1] == "thinlto-pre-link") {
1806 MPM.addPass(buildThinLTOPreLinkDefaultPipeline(L, DebugLogging));
1807 } else if (Matches[1] == "thinlto") {
1808 MPM.addPass(buildThinLTODefaultPipeline(L, DebugLogging, nullptr));
1809 } else if (Matches[1] == "lto-pre-link") {
1810 MPM.addPass(buildLTOPreLinkDefaultPipeline(L, DebugLogging));
1811 } else {
1812 assert(Matches[1] == "lto" && "Not one of the matched options!")((Matches[1] == "lto" && "Not one of the matched options!"
) ? static_cast<void> (0) : __assert_fail ("Matches[1] == \"lto\" && \"Not one of the matched options!\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/Passes/PassBuilder.cpp"
, 1812, __PRETTY_FUNCTION__))
;
1813 MPM.addPass(buildLTODefaultPipeline(L, DebugLogging, nullptr));
1814 }
1815 return Error::success();
1816 }
1817
1818 // Finally expand the basic registered passes from the .inc file.
1819#define MODULE_PASS(NAME, CREATE_PASS) \
1820 if (Name == NAME) { \
1821 MPM.addPass(CREATE_PASS); \
1822 return Error::success(); \
1823 }
1824#define MODULE_ANALYSIS(NAME, CREATE_PASS) \
1825 if (Name == "require<" NAME ">") { \
1826 MPM.addPass( \
1827 RequireAnalysisPass< \
1828 std::remove_reference<decltype(CREATE_PASS)>::type, Module>()); \
1829 return Error::success(); \
1830 } \
1831 if (Name == "invalidate<" NAME ">") { \
1832 MPM.addPass(InvalidateAnalysisPass< \
1833 std::remove_reference<decltype(CREATE_PASS)>::type>()); \
1834 return Error::success(); \
1835 }
1836#include "PassRegistry.def"
1837
1838 for (auto &C : ModulePipelineParsingCallbacks)
1839 if (C(Name, MPM, InnerPipeline))
1840 return Error::success();
1841 return make_error<StringError>(
1842 formatv("unknown module pass '{0}'", Name).str(),
1843 inconvertibleErrorCode());
1844}
1845
1846Error PassBuilder::parseCGSCCPass(CGSCCPassManager &CGPM,
1847 const PipelineElement &E, bool VerifyEachPass,
1848 bool DebugLogging) {
1849 auto &Name = E.Name;
1850 auto &InnerPipeline = E.InnerPipeline;
1851
1852 // First handle complex passes like the pass managers which carry pipelines.
1853 if (!InnerPipeline.empty()) {
1854 if (Name == "cgscc") {
1855 CGSCCPassManager NestedCGPM(DebugLogging);
1856 if (auto Err = parseCGSCCPassPipeline(NestedCGPM, InnerPipeline,
1857 VerifyEachPass, DebugLogging))
1858 return Err;
1859 // Add the nested pass manager with the appropriate adaptor.
1860 CGPM.addPass(std::move(NestedCGPM));
1861 return Error::success();
1862 }
1863 if (Name == "function") {
1864 FunctionPassManager FPM(DebugLogging);
1865 if (auto Err = parseFunctionPassPipeline(FPM, InnerPipeline,
1866 VerifyEachPass, DebugLogging))
1867 return Err;
1868 // Add the nested pass manager with the appropriate adaptor.
1869 CGPM.addPass(createCGSCCToFunctionPassAdaptor(std::move(FPM)));
1870 return Error::success();
1871 }
1872 if (auto Count = parseRepeatPassName(Name)) {
1873 CGSCCPassManager NestedCGPM(DebugLogging);
1874 if (auto Err = parseCGSCCPassPipeline(NestedCGPM, InnerPipeline,
1875 VerifyEachPass, DebugLogging))
1876 return Err;
1877 CGPM.addPass(createRepeatedPass(*Count, std::move(NestedCGPM)));
1878 return Error::success();
1879 }
1880 if (auto MaxRepetitions = parseDevirtPassName(Name)) {
1881 CGSCCPassManager NestedCGPM(DebugLogging);
1882 if (auto Err = parseCGSCCPassPipeline(NestedCGPM, InnerPipeline,
1883 VerifyEachPass, DebugLogging))
1884 return Err;
1885 CGPM.addPass(
1886 createDevirtSCCRepeatedPass(std::move(NestedCGPM), *MaxRepetitions));
1887 return Error::success();
1888 }
1889
1890 for (auto &C : CGSCCPipelineParsingCallbacks)
1891 if (C(Name, CGPM, InnerPipeline))
1892 return Error::success();
1893
1894 // Normal passes can't have pipelines.
1895 return make_error<StringError>(
1896 formatv("invalid use of '{0}' pass as cgscc pipeline", Name).str(),
1897 inconvertibleErrorCode());
1898 }
1899
1900// Now expand the basic registered passes from the .inc file.
1901#define CGSCC_PASS(NAME, CREATE_PASS) \
1902 if (Name == NAME) { \
1903 CGPM.addPass(CREATE_PASS); \
1904 return Error::success(); \
1905 }
1906#define CGSCC_ANALYSIS(NAME, CREATE_PASS) \
1907 if (Name == "require<" NAME ">") { \
1908 CGPM.addPass(RequireAnalysisPass< \
1909 std::remove_reference<decltype(CREATE_PASS)>::type, \
1910 LazyCallGraph::SCC, CGSCCAnalysisManager, LazyCallGraph &, \
1911 CGSCCUpdateResult &>()); \
1912 return Error::success(); \
1913 } \
1914 if (Name == "invalidate<" NAME ">") { \
1915 CGPM.addPass(InvalidateAnalysisPass< \
1916 std::remove_reference<decltype(CREATE_PASS)>::type>()); \
1917 return Error::success(); \
1918 }
1919#include "PassRegistry.def"
1920
1921 for (auto &C : CGSCCPipelineParsingCallbacks)
1922 if (C(Name, CGPM, InnerPipeline))
1923 return Error::success();
1924 return make_error<StringError>(
1925 formatv("unknown cgscc pass '{0}'", Name).str(),
1926 inconvertibleErrorCode());
1927}
1928
1929Error PassBuilder::parseFunctionPass(FunctionPassManager &FPM,
1930 const PipelineElement &E,
1931 bool VerifyEachPass, bool DebugLogging) {
1932 auto &Name = E.Name;
1933 auto &InnerPipeline = E.InnerPipeline;
1934
1935 // First handle complex passes like the pass managers which carry pipelines.
1936 if (!InnerPipeline.empty()) {
1937 if (Name == "function") {
1938 FunctionPassManager NestedFPM(DebugLogging);
1939 if (auto Err = parseFunctionPassPipeline(NestedFPM, InnerPipeline,
1940 VerifyEachPass, DebugLogging))
1941 return Err;
1942 // Add the nested pass manager with the appropriate adaptor.
1943 FPM.addPass(std::move(NestedFPM));
1944 return Error::success();
1945 }
1946 if (Name == "loop") {
1947 LoopPassManager LPM(DebugLogging);
1948 if (auto Err = parseLoopPassPipeline(LPM, InnerPipeline, VerifyEachPass,
1949 DebugLogging))
1950 return Err;
1951 // Add the nested pass manager with the appropriate adaptor.
1952 FPM.addPass(
1953 createFunctionToLoopPassAdaptor(std::move(LPM), DebugLogging));
1954 return Error::success();
1955 }
1956 if (auto Count = parseRepeatPassName(Name)) {
1957 FunctionPassManager NestedFPM(DebugLogging);
1958 if (auto Err = parseFunctionPassPipeline(NestedFPM, InnerPipeline,
1959 VerifyEachPass, DebugLogging))
1960 return Err;
1961 FPM.addPass(createRepeatedPass(*Count, std::move(NestedFPM)));
1962 return Error::success();
1963 }
1964
1965 for (auto &C : FunctionPipelineParsingCallbacks)
1966 if (C(Name, FPM, InnerPipeline))
1967 return Error::success();
1968
1969 // Normal passes can't have pipelines.
1970 return make_error<StringError>(
1971 formatv("invalid use of '{0}' pass as function pipeline", Name).str(),
1972 inconvertibleErrorCode());
1973 }
1974
1975// Now expand the basic registered passes from the .inc file.
1976#define FUNCTION_PASS(NAME, CREATE_PASS) \
1977 if (Name == NAME) { \
1978 FPM.addPass(CREATE_PASS); \
1979 return Error::success(); \
1980 }
1981#define FUNCTION_PASS_WITH_PARAMS(NAME, CREATE_PASS, PARSER) \
1982 if (checkParametrizedPassName(Name, NAME)) { \
1983 auto Params = parsePassParameters(PARSER, Name, NAME); \
1984 if (!Params) \
1985 return Params.takeError(); \
1986 FPM.addPass(CREATE_PASS(Params.get())); \
1987 return Error::success(); \
1988 }
1989#define FUNCTION_ANALYSIS(NAME, CREATE_PASS) \
1990 if (Name == "require<" NAME ">") { \
1991 FPM.addPass( \
1992 RequireAnalysisPass< \
1993 std::remove_reference<decltype(CREATE_PASS)>::type, Function>()); \
1994 return Error::success(); \
1995 } \
1996 if (Name == "invalidate<" NAME ">") { \
1997 FPM.addPass(InvalidateAnalysisPass< \
1998 std::remove_reference<decltype(CREATE_PASS)>::type>()); \
1999 return Error::success(); \
2000 }
2001#include "PassRegistry.def"
2002
2003 for (auto &C : FunctionPipelineParsingCallbacks)
2004 if (C(Name, FPM, InnerPipeline))
2005 return Error::success();
2006 return make_error<StringError>(
2007 formatv("unknown function pass '{0}'", Name).str(),
2008 inconvertibleErrorCode());
2009}
2010
2011Error PassBuilder::parseLoopPass(LoopPassManager &LPM, const PipelineElement &E,
2012 bool VerifyEachPass, bool DebugLogging) {
2013 StringRef Name = E.Name;
2014 auto &InnerPipeline = E.InnerPipeline;
2015
2016 // First handle complex passes like the pass managers which carry pipelines.
2017 if (!InnerPipeline.empty()) {
2018 if (Name == "loop") {
2019 LoopPassManager NestedLPM(DebugLogging);
2020 if (auto Err = parseLoopPassPipeline(NestedLPM, InnerPipeline,
2021 VerifyEachPass, DebugLogging))
2022 return Err;
2023 // Add the nested pass manager with the appropriate adaptor.
2024 LPM.addPass(std::move(NestedLPM));
2025 return Error::success();
2026 }
2027 if (auto Count = parseRepeatPassName(Name)) {
2028 LoopPassManager NestedLPM(DebugLogging);
2029 if (auto Err = parseLoopPassPipeline(NestedLPM, InnerPipeline,
2030 VerifyEachPass, DebugLogging))
2031 return Err;
2032 LPM.addPass(createRepeatedPass(*Count, std::move(NestedLPM)));
2033 return Error::success();
2034 }
2035
2036 for (auto &C : LoopPipelineParsingCallbacks)
2037 if (C(Name, LPM, InnerPipeline))
2038 return Error::success();
2039
2040 // Normal passes can't have pipelines.
2041 return make_error<StringError>(
2042 formatv("invalid use of '{0}' pass as loop pipeline", Name).str(),
2043 inconvertibleErrorCode());
2044 }
2045
2046// Now expand the basic registered passes from the .inc file.
2047#define LOOP_PASS(NAME, CREATE_PASS) \
2048 if (Name == NAME) { \
2049 LPM.addPass(CREATE_PASS); \
2050 return Error::success(); \
2051 }
2052#define LOOP_PASS_WITH_PARAMS(NAME, CREATE_PASS, PARSER) \
2053 if (checkParametrizedPassName(Name, NAME)) { \
2054 auto Params = parsePassParameters(PARSER, Name, NAME); \
2055 if (!Params) \
2056 return Params.takeError(); \
2057 LPM.addPass(CREATE_PASS(Params.get())); \
2058 return Error::success(); \
2059 }
2060#define LOOP_ANALYSIS(NAME, CREATE_PASS) \
2061 if (Name == "require<" NAME ">") { \
2062 LPM.addPass(RequireAnalysisPass< \
2063 std::remove_reference<decltype(CREATE_PASS)>::type, Loop, \
2064 LoopAnalysisManager, LoopStandardAnalysisResults &, \
2065 LPMUpdater &>()); \
2066 return Error::success(); \
2067 } \
2068 if (Name == "invalidate<" NAME ">") { \
2069 LPM.addPass(InvalidateAnalysisPass< \
2070 std::remove_reference<decltype(CREATE_PASS)>::type>()); \
2071 return Error::success(); \
2072 }
2073#include "PassRegistry.def"
2074
2075 for (auto &C : LoopPipelineParsingCallbacks)
2076 if (C(Name, LPM, InnerPipeline))
2077 return Error::success();
2078 return make_error<StringError>(formatv("unknown loop pass '{0}'", Name).str(),
2079 inconvertibleErrorCode());
2080}
2081
2082bool PassBuilder::parseAAPassName(AAManager &AA, StringRef Name) {
2083#define MODULE_ALIAS_ANALYSIS(NAME, CREATE_PASS) \
2084 if (Name == NAME) { \
2085 AA.registerModuleAnalysis< \
2086 std::remove_reference<decltype(CREATE_PASS)>::type>(); \
2087 return true; \
2088 }
2089#define FUNCTION_ALIAS_ANALYSIS(NAME, CREATE_PASS) \
2090 if (Name == NAME) { \
2091 AA.registerFunctionAnalysis< \
2092 std::remove_reference<decltype(CREATE_PASS)>::type>(); \
2093 return true; \
2094 }
2095#include "PassRegistry.def"
2096
2097 for (auto &C : AAParsingCallbacks)
2098 if (C(Name, AA))
2099 return true;
2100 return false;
2101}
2102
2103Error PassBuilder::parseLoopPassPipeline(LoopPassManager &LPM,
2104 ArrayRef<PipelineElement> Pipeline,
2105 bool VerifyEachPass,
2106 bool DebugLogging) {
2107 for (const auto &Element : Pipeline) {
2108 if (auto Err = parseLoopPass(LPM, Element, VerifyEachPass, DebugLogging))
2109 return Err;
2110 // FIXME: No verifier support for Loop passes!
2111 }
2112 return Error::success();
2113}
2114
2115Error PassBuilder::parseFunctionPassPipeline(FunctionPassManager &FPM,
2116 ArrayRef<PipelineElement> Pipeline,
2117 bool VerifyEachPass,
2118 bool DebugLogging) {
2119 for (const auto &Element : Pipeline) {
2120 if (auto Err =
2121 parseFunctionPass(FPM, Element, VerifyEachPass, DebugLogging))
2122 return Err;
2123 if (VerifyEachPass)
2124 FPM.addPass(VerifierPass());
2125 }
2126 return Error::success();
2127}
2128
2129Error PassBuilder::parseCGSCCPassPipeline(CGSCCPassManager &CGPM,
2130 ArrayRef<PipelineElement> Pipeline,
2131 bool VerifyEachPass,
2132 bool DebugLogging) {
2133 for (const auto &Element : Pipeline) {
2134 if (auto Err = parseCGSCCPass(CGPM, Element, VerifyEachPass, DebugLogging))
2135 return Err;
2136 // FIXME: No verifier support for CGSCC passes!
2137 }
2138 return Error::success();
2139}
2140
2141void PassBuilder::crossRegisterProxies(LoopAnalysisManager &LAM,
2142 FunctionAnalysisManager &FAM,
2143 CGSCCAnalysisManager &CGAM,
2144 ModuleAnalysisManager &MAM) {
2145 MAM.registerPass([&] { return FunctionAnalysisManagerModuleProxy(FAM); });
2146 MAM.registerPass([&] { return CGSCCAnalysisManagerModuleProxy(CGAM); });
2147 CGAM.registerPass([&] { return ModuleAnalysisManagerCGSCCProxy(MAM); });
2148 FAM.registerPass([&] { return CGSCCAnalysisManagerFunctionProxy(CGAM); });
2149 FAM.registerPass([&] { return ModuleAnalysisManagerFunctionProxy(MAM); });
2150 FAM.registerPass([&] { return LoopAnalysisManagerFunctionProxy(LAM); });
2151 LAM.registerPass([&] { return FunctionAnalysisManagerLoopProxy(FAM); });
2152}
2153
2154Error PassBuilder::parseModulePassPipeline(ModulePassManager &MPM,
2155 ArrayRef<PipelineElement> Pipeline,
2156 bool VerifyEachPass,
2157 bool DebugLogging) {
2158 for (const auto &Element : Pipeline) {
2159 if (auto Err = parseModulePass(MPM, Element, VerifyEachPass, DebugLogging))
2160 return Err;
2161 if (VerifyEachPass)
2162 MPM.addPass(VerifierPass());
2163 }
2164 return Error::success();
2165}
2166
2167// Primary pass pipeline description parsing routine for a \c ModulePassManager
2168// FIXME: Should this routine accept a TargetMachine or require the caller to
2169// pre-populate the analysis managers with target-specific stuff?
2170Error PassBuilder::parsePassPipeline(ModulePassManager &MPM,
2171 StringRef PipelineText,
2172 bool VerifyEachPass, bool DebugLogging) {
2173 auto Pipeline = parsePipelineText(PipelineText);
2174 if (!Pipeline || Pipeline->empty())
2175 return make_error<StringError>(
2176 formatv("invalid pipeline '{0}'", PipelineText).str(),
2177 inconvertibleErrorCode());
2178
2179 // If the first name isn't at the module layer, wrap the pipeline up
2180 // automatically.
2181 StringRef FirstName = Pipeline->front().Name;
2182
2183 if (!isModulePassName(FirstName, ModulePipelineParsingCallbacks)) {
2184 if (isCGSCCPassName(FirstName, CGSCCPipelineParsingCallbacks)) {
2185 Pipeline = {{"cgscc", std::move(*Pipeline)}};
2186 } else if (isFunctionPassName(FirstName,
2187 FunctionPipelineParsingCallbacks)) {
2188 Pipeline = {{"function", std::move(*Pipeline)}};
2189 } else if (isLoopPassName(FirstName, LoopPipelineParsingCallbacks)) {
2190 Pipeline = {{"function", {{"loop", std::move(*Pipeline)}}}};
2191 } else {
2192 for (auto &C : TopLevelPipelineParsingCallbacks)
2193 if (C(MPM, *Pipeline, VerifyEachPass, DebugLogging))
2194 return Error::success();
2195
2196 // Unknown pass or pipeline name!
2197 auto &InnerPipeline = Pipeline->front().InnerPipeline;
2198 return make_error<StringError>(
2199 formatv("unknown {0} name '{1}'",
2200 (InnerPipeline.empty() ? "pass" : "pipeline"), FirstName)
2201 .str(),
2202 inconvertibleErrorCode());
2203 }
2204 }
2205
2206 if (auto Err =
2207 parseModulePassPipeline(MPM, *Pipeline, VerifyEachPass, DebugLogging))
2208 return Err;
2209 return Error::success();
2210}
2211
2212// Primary pass pipeline description parsing routine for a \c CGSCCPassManager
2213Error PassBuilder::parsePassPipeline(CGSCCPassManager &CGPM,
2214 StringRef PipelineText,
2215 bool VerifyEachPass, bool DebugLogging) {
2216 auto Pipeline = parsePipelineText(PipelineText);
2217 if (!Pipeline || Pipeline->empty())
2218 return make_error<StringError>(
2219 formatv("invalid pipeline '{0}'", PipelineText).str(),
2220 inconvertibleErrorCode());
2221
2222 StringRef FirstName = Pipeline->front().Name;
2223 if (!isCGSCCPassName(FirstName, CGSCCPipelineParsingCallbacks))
2224 return make_error<StringError>(
2225 formatv("unknown cgscc pass '{0}' in pipeline '{1}'", FirstName,
2226 PipelineText)
2227 .str(),
2228 inconvertibleErrorCode());
2229
2230 if (auto Err =
2231 parseCGSCCPassPipeline(CGPM, *Pipeline, VerifyEachPass, DebugLogging))
2232 return Err;
2233 return Error::success();
2234}
2235
2236// Primary pass pipeline description parsing routine for a \c
2237// FunctionPassManager
2238Error PassBuilder::parsePassPipeline(FunctionPassManager &FPM,
2239 StringRef PipelineText,
2240 bool VerifyEachPass, bool DebugLogging) {
2241 auto Pipeline = parsePipelineText(PipelineText);
2242 if (!Pipeline || Pipeline->empty())
2243 return make_error<StringError>(
2244 formatv("invalid pipeline '{0}'", PipelineText).str(),
2245 inconvertibleErrorCode());
2246
2247 StringRef FirstName = Pipeline->front().Name;
2248 if (!isFunctionPassName(FirstName, FunctionPipelineParsingCallbacks))
2249 return make_error<StringError>(
2250 formatv("unknown function pass '{0}' in pipeline '{1}'", FirstName,
2251 PipelineText)
2252 .str(),
2253 inconvertibleErrorCode());
2254
2255 if (auto Err = parseFunctionPassPipeline(FPM, *Pipeline, VerifyEachPass,
2256 DebugLogging))
2257 return Err;
2258 return Error::success();
2259}
2260
2261// Primary pass pipeline description parsing routine for a \c LoopPassManager
2262Error PassBuilder::parsePassPipeline(LoopPassManager &CGPM,
2263 StringRef PipelineText,
2264 bool VerifyEachPass, bool DebugLogging) {
2265 auto Pipeline = parsePipelineText(PipelineText);
2266 if (!Pipeline || Pipeline->empty())
1
Assuming the condition is true
2267 return make_error<StringError>(
2
Calling 'make_error<llvm::StringError, std::__cxx11::basic_string<char>, std::error_code>'
2268 formatv("invalid pipeline '{0}'", PipelineText).str(),
2269 inconvertibleErrorCode());
2270
2271 if (auto Err =
2272 parseLoopPassPipeline(CGPM, *Pipeline, VerifyEachPass, DebugLogging))
2273 return Err;
2274
2275 return Error::success();
2276}
2277
2278Error PassBuilder::parseAAPipeline(AAManager &AA, StringRef PipelineText) {
2279 // If the pipeline just consists of the word 'default' just replace the AA
2280 // manager with our default one.
2281 if (PipelineText == "default") {
2282 AA = buildDefaultAAPipeline();
2283 return Error::success();
2284 }
2285
2286 while (!PipelineText.empty()) {
2287 StringRef Name;
2288 std::tie(Name, PipelineText) = PipelineText.split(',');
2289 if (!parseAAPassName(AA, Name))
2290 return make_error<StringError>(
2291 formatv("unknown alias analysis name '{0}'", Name).str(),
2292 inconvertibleErrorCode());
2293 }
2294
2295 return Error::success();
2296}

/build/llvm-toolchain-snapshot-9~svn362543/include/llvm/Support/Error.h

1//===- llvm/Support/Error.h - Recoverable error handling --------*- C++ -*-===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This file defines an API used to report recoverable errors.
10//
11//===----------------------------------------------------------------------===//
12
13#ifndef LLVM_SUPPORT_ERROR_H
14#define LLVM_SUPPORT_ERROR_H
15
16#include "llvm-c/Error.h"
17#include "llvm/ADT/STLExtras.h"
18#include "llvm/ADT/SmallVector.h"
19#include "llvm/ADT/StringExtras.h"
20#include "llvm/ADT/Twine.h"
21#include "llvm/Config/abi-breaking.h"
22#include "llvm/Support/AlignOf.h"
23#include "llvm/Support/Compiler.h"
24#include "llvm/Support/Debug.h"
25#include "llvm/Support/ErrorHandling.h"
26#include "llvm/Support/ErrorOr.h"
27#include "llvm/Support/Format.h"
28#include "llvm/Support/raw_ostream.h"
29#include <algorithm>
30#include <cassert>
31#include <cstdint>
32#include <cstdlib>
33#include <functional>
34#include <memory>
35#include <new>
36#include <string>
37#include <system_error>
38#include <type_traits>
39#include <utility>
40#include <vector>
41
42namespace llvm {
43
44class ErrorSuccess;
45
46/// Base class for error info classes. Do not extend this directly: Extend
47/// the ErrorInfo template subclass instead.
48class ErrorInfoBase {
49public:
50 virtual ~ErrorInfoBase() = default;
51
52 /// Print an error message to an output stream.
53 virtual void log(raw_ostream &OS) const = 0;
54
55 /// Return the error message as a string.
56 virtual std::string message() const {
57 std::string Msg;
58 raw_string_ostream OS(Msg);
59 log(OS);
60 return OS.str();
61 }
62
63 /// Convert this error to a std::error_code.
64 ///
65 /// This is a temporary crutch to enable interaction with code still
66 /// using std::error_code. It will be removed in the future.
67 virtual std::error_code convertToErrorCode() const = 0;
68
69 // Returns the class ID for this type.
70 static const void *classID() { return &ID; }
71
72 // Returns the class ID for the dynamic type of this ErrorInfoBase instance.
73 virtual const void *dynamicClassID() const = 0;
74
75 // Check whether this instance is a subclass of the class identified by
76 // ClassID.
77 virtual bool isA(const void *const ClassID) const {
78 return ClassID == classID();
79 }
80
81 // Check whether this instance is a subclass of ErrorInfoT.
82 template <typename ErrorInfoT> bool isA() const {
83 return isA(ErrorInfoT::classID());
84 }
85
86private:
87 virtual void anchor();
88
89 static char ID;
90};
91
92/// Lightweight error class with error context and mandatory checking.
93///
94/// Instances of this class wrap a ErrorInfoBase pointer. Failure states
95/// are represented by setting the pointer to a ErrorInfoBase subclass
96/// instance containing information describing the failure. Success is
97/// represented by a null pointer value.
98///
99/// Instances of Error also contains a 'Checked' flag, which must be set
100/// before the destructor is called, otherwise the destructor will trigger a
101/// runtime error. This enforces at runtime the requirement that all Error
102/// instances be checked or returned to the caller.
103///
104/// There are two ways to set the checked flag, depending on what state the
105/// Error instance is in. For Error instances indicating success, it
106/// is sufficient to invoke the boolean conversion operator. E.g.:
107///
108/// @code{.cpp}
109/// Error foo(<...>);
110///
111/// if (auto E = foo(<...>))
112/// return E; // <- Return E if it is in the error state.
113/// // We have verified that E was in the success state. It can now be safely
114/// // destroyed.
115/// @endcode
116///
117/// A success value *can not* be dropped. For example, just calling 'foo(<...>)'
118/// without testing the return value will raise a runtime error, even if foo
119/// returns success.
120///
121/// For Error instances representing failure, you must use either the
122/// handleErrors or handleAllErrors function with a typed handler. E.g.:
123///
124/// @code{.cpp}
125/// class MyErrorInfo : public ErrorInfo<MyErrorInfo> {
126/// // Custom error info.
127/// };
128///
129/// Error foo(<...>) { return make_error<MyErrorInfo>(...); }
130///
131/// auto E = foo(<...>); // <- foo returns failure with MyErrorInfo.
132/// auto NewE =
133/// handleErrors(E,
134/// [](const MyErrorInfo &M) {
135/// // Deal with the error.
136/// },
137/// [](std::unique_ptr<OtherError> M) -> Error {
138/// if (canHandle(*M)) {
139/// // handle error.
140/// return Error::success();
141/// }
142/// // Couldn't handle this error instance. Pass it up the stack.
143/// return Error(std::move(M));
144/// );
145/// // Note - we must check or return NewE in case any of the handlers
146/// // returned a new error.
147/// @endcode
148///
149/// The handleAllErrors function is identical to handleErrors, except
150/// that it has a void return type, and requires all errors to be handled and
151/// no new errors be returned. It prevents errors (assuming they can all be
152/// handled) from having to be bubbled all the way to the top-level.
153///
154/// *All* Error instances must be checked before destruction, even if
155/// they're moved-assigned or constructed from Success values that have already
156/// been checked. This enforces checking through all levels of the call stack.
157class LLVM_NODISCARD[[clang::warn_unused_result]] Error {
158 // Both ErrorList and FileError need to be able to yank ErrorInfoBase
159 // pointers out of this class to add to the error list.
160 friend class ErrorList;
161 friend class FileError;
162
163 // handleErrors needs to be able to set the Checked flag.
164 template <typename... HandlerTs>
165 friend Error handleErrors(Error E, HandlerTs &&... Handlers);
166
167 // Expected<T> needs to be able to steal the payload when constructed from an
168 // error.
169 template <typename T> friend class Expected;
170
171 // wrap needs to be able to steal the payload.
172 friend LLVMErrorRef wrap(Error);
173
174protected:
175 /// Create a success value. Prefer using 'Error::success()' for readability
176 Error() {
177 setPtr(nullptr);
178 setChecked(false);
179 }
180
181public:
182 /// Create a success value.
183 static ErrorSuccess success();
184
185 // Errors are not copy-constructable.
186 Error(const Error &Other) = delete;
187
188 /// Move-construct an error value. The newly constructed error is considered
189 /// unchecked, even if the source error had been checked. The original error
190 /// becomes a checked Success value, regardless of its original state.
191 Error(Error &&Other) {
192 setChecked(true);
193 *this = std::move(Other);
194 }
195
196 /// Create an error value. Prefer using the 'make_error' function, but
197 /// this constructor can be useful when "re-throwing" errors from handlers.
198 Error(std::unique_ptr<ErrorInfoBase> Payload) {
199 setPtr(Payload.release());
200 setChecked(false);
7
Potential leak of memory pointed to by 'Payload._M_t._M_head_impl'
201 }
202
203 // Errors are not copy-assignable.
204 Error &operator=(const Error &Other) = delete;
205
206 /// Move-assign an error value. The current error must represent success, you
207 /// you cannot overwrite an unhandled error. The current error is then
208 /// considered unchecked. The source error becomes a checked success value,
209 /// regardless of its original state.
210 Error &operator=(Error &&Other) {
211 // Don't allow overwriting of unchecked values.
212 assertIsChecked();
213 setPtr(Other.getPtr());
214
215 // This Error is unchecked, even if the source error was checked.
216 setChecked(false);
217
218 // Null out Other's payload and set its checked bit.
219 Other.setPtr(nullptr);
220 Other.setChecked(true);
221
222 return *this;
223 }
224
225 /// Destroy a Error. Fails with a call to abort() if the error is
226 /// unchecked.
227 ~Error() {
228 assertIsChecked();
229 delete getPtr();
230 }
231
232 /// Bool conversion. Returns true if this Error is in a failure state,
233 /// and false if it is in an accept state. If the error is in a Success state
234 /// it will be considered checked.
235 explicit operator bool() {
236 setChecked(getPtr() == nullptr);
237 return getPtr() != nullptr;
238 }
239
240 /// Check whether one error is a subclass of another.
241 template <typename ErrT> bool isA() const {
242 return getPtr() && getPtr()->isA(ErrT::classID());
243 }
244
245 /// Returns the dynamic class id of this error, or null if this is a success
246 /// value.
247 const void* dynamicClassID() const {
248 if (!getPtr())
249 return nullptr;
250 return getPtr()->dynamicClassID();
251 }
252
253private:
254#if LLVM_ENABLE_ABI_BREAKING_CHECKS1
255 // assertIsChecked() happens very frequently, but under normal circumstances
256 // is supposed to be a no-op. So we want it to be inlined, but having a bunch
257 // of debug prints can cause the function to be too large for inlining. So
258 // it's important that we define this function out of line so that it can't be
259 // inlined.
260 LLVM_ATTRIBUTE_NORETURN__attribute__((noreturn))
261 void fatalUncheckedError() const;
262#endif
263
264 void assertIsChecked() {
265#if LLVM_ENABLE_ABI_BREAKING_CHECKS1
266 if (LLVM_UNLIKELY(!getChecked() || getPtr())__builtin_expect((bool)(!getChecked() || getPtr()), false))
267 fatalUncheckedError();
268#endif
269 }
270
271 ErrorInfoBase *getPtr() const {
272 return reinterpret_cast<ErrorInfoBase*>(
273 reinterpret_cast<uintptr_t>(Payload) &
274 ~static_cast<uintptr_t>(0x1));
275 }
276
277 void setPtr(ErrorInfoBase *EI) {
278#if LLVM_ENABLE_ABI_BREAKING_CHECKS1
279 Payload = reinterpret_cast<ErrorInfoBase*>(
280 (reinterpret_cast<uintptr_t>(EI) &
281 ~static_cast<uintptr_t>(0x1)) |
282 (reinterpret_cast<uintptr_t>(Payload) & 0x1));
283#else
284 Payload = EI;
285#endif
286 }
287
288 bool getChecked() const {
289#if LLVM_ENABLE_ABI_BREAKING_CHECKS1
290 return (reinterpret_cast<uintptr_t>(Payload) & 0x1) == 0;
291#else
292 return true;
293#endif
294 }
295
296 void setChecked(bool V) {
297 Payload = reinterpret_cast<ErrorInfoBase*>(
298 (reinterpret_cast<uintptr_t>(Payload) &
299 ~static_cast<uintptr_t>(0x1)) |
300 (V ? 0 : 1));
301 }
302
303 std::unique_ptr<ErrorInfoBase> takePayload() {
304 std::unique_ptr<ErrorInfoBase> Tmp(getPtr());
305 setPtr(nullptr);
306 setChecked(true);
307 return Tmp;
308 }
309
310 friend raw_ostream &operator<<(raw_ostream &OS, const Error &E) {
311 if (auto P = E.getPtr())
312 P->log(OS);
313 else
314 OS << "success";
315 return OS;
316 }
317
318 ErrorInfoBase *Payload = nullptr;
319};
320
321/// Subclass of Error for the sole purpose of identifying the success path in
322/// the type system. This allows to catch invalid conversion to Expected<T> at
323/// compile time.
324class ErrorSuccess final : public Error {};
325
326inline ErrorSuccess Error::success() { return ErrorSuccess(); }
327
328/// Make a Error instance representing failure using the given error info
329/// type.
330template <typename ErrT, typename... ArgTs> Error make_error(ArgTs &&... Args) {
331 return Error(llvm::make_unique<ErrT>(std::forward<ArgTs>(Args)...));
3
Calling 'make_unique<llvm::StringError, std::__cxx11::basic_string<char>, std::error_code>'
5
Returned allocated memory
6
Calling constructor for 'Error'
332}
333
334/// Base class for user error types. Users should declare their error types
335/// like:
336///
337/// class MyError : public ErrorInfo<MyError> {
338/// ....
339/// };
340///
341/// This class provides an implementation of the ErrorInfoBase::kind
342/// method, which is used by the Error RTTI system.
343template <typename ThisErrT, typename ParentErrT = ErrorInfoBase>
344class ErrorInfo : public ParentErrT {
345public:
346 using ParentErrT::ParentErrT; // inherit constructors
347
348 static const void *classID() { return &ThisErrT::ID; }
349
350 const void *dynamicClassID() const override { return &ThisErrT::ID; }
351
352 bool isA(const void *const ClassID) const override {
353 return ClassID == classID() || ParentErrT::isA(ClassID);
354 }
355};
356
357/// Special ErrorInfo subclass representing a list of ErrorInfos.
358/// Instances of this class are constructed by joinError.
359class ErrorList final : public ErrorInfo<ErrorList> {
360 // handleErrors needs to be able to iterate the payload list of an
361 // ErrorList.
362 template <typename... HandlerTs>
363 friend Error handleErrors(Error E, HandlerTs &&... Handlers);
364
365 // joinErrors is implemented in terms of join.
366 friend Error joinErrors(Error, Error);
367
368public:
369 void log(raw_ostream &OS) const override {
370 OS << "Multiple errors:\n";
371 for (auto &ErrPayload : Payloads) {
372 ErrPayload->log(OS);
373 OS << "\n";
374 }
375 }
376
377 std::error_code convertToErrorCode() const override;
378
379 // Used by ErrorInfo::classID.
380 static char ID;
381
382private:
383 ErrorList(std::unique_ptr<ErrorInfoBase> Payload1,
384 std::unique_ptr<ErrorInfoBase> Payload2) {
385 assert(!Payload1->isA<ErrorList>() && !Payload2->isA<ErrorList>() &&((!Payload1->isA<ErrorList>() && !Payload2->
isA<ErrorList>() && "ErrorList constructor payloads should be singleton errors"
) ? static_cast<void> (0) : __assert_fail ("!Payload1->isA<ErrorList>() && !Payload2->isA<ErrorList>() && \"ErrorList constructor payloads should be singleton errors\""
, "/build/llvm-toolchain-snapshot-9~svn362543/include/llvm/Support/Error.h"
, 386, __PRETTY_FUNCTION__))
386 "ErrorList constructor payloads should be singleton errors")((!Payload1->isA<ErrorList>() && !Payload2->
isA<ErrorList>() && "ErrorList constructor payloads should be singleton errors"
) ? static_cast<void> (0) : __assert_fail ("!Payload1->isA<ErrorList>() && !Payload2->isA<ErrorList>() && \"ErrorList constructor payloads should be singleton errors\""
, "/build/llvm-toolchain-snapshot-9~svn362543/include/llvm/Support/Error.h"
, 386, __PRETTY_FUNCTION__))
;
387 Payloads.push_back(std::move(Payload1));
388 Payloads.push_back(std::move(Payload2));
389 }
390
391 static Error join(Error E1, Error E2) {
392 if (!E1)
393 return E2;
394 if (!E2)
395 return E1;
396 if (E1.isA<ErrorList>()) {
397 auto &E1List = static_cast<ErrorList &>(*E1.getPtr());
398 if (E2.isA<ErrorList>()) {
399 auto E2Payload = E2.takePayload();
400 auto &E2List = static_cast<ErrorList &>(*E2Payload);
401 for (auto &Payload : E2List.Payloads)
402 E1List.Payloads.push_back(std::move(Payload));
403 } else
404 E1List.Payloads.push_back(E2.takePayload());
405
406 return E1;
407 }
408 if (E2.isA<ErrorList>()) {
409 auto &E2List = static_cast<ErrorList &>(*E2.getPtr());
410 E2List.Payloads.insert(E2List.Payloads.begin(), E1.takePayload());
411 return E2;
412 }
413 return Error(std::unique_ptr<ErrorList>(
414 new ErrorList(E1.takePayload(), E2.takePayload())));
415 }
416
417 std::vector<std::unique_ptr<ErrorInfoBase>> Payloads;
418};
419
420/// Concatenate errors. The resulting Error is unchecked, and contains the
421/// ErrorInfo(s), if any, contained in E1, followed by the
422/// ErrorInfo(s), if any, contained in E2.
423inline Error joinErrors(Error E1, Error E2) {
424 return ErrorList::join(std::move(E1), std::move(E2));
425}
426
427/// Tagged union holding either a T or a Error.
428///
429/// This class parallels ErrorOr, but replaces error_code with Error. Since
430/// Error cannot be copied, this class replaces getError() with
431/// takeError(). It also adds an bool errorIsA<ErrT>() method for testing the
432/// error class type.
433template <class T> class LLVM_NODISCARD[[clang::warn_unused_result]] Expected {
434 template <class T1> friend class ExpectedAsOutParameter;
435 template <class OtherT> friend class Expected;
436
437 static const bool isRef = std::is_reference<T>::value;
438
439 using wrap = std::reference_wrapper<typename std::remove_reference<T>::type>;
440
441 using error_type = std::unique_ptr<ErrorInfoBase>;
442
443public:
444 using storage_type = typename std::conditional<isRef, wrap, T>::type;
445 using value_type = T;
446
447private:
448 using reference = typename std::remove_reference<T>::type &;
449 using const_reference = const typename std::remove_reference<T>::type &;
450 using pointer = typename std::remove_reference<T>::type *;
451 using const_pointer = const typename std::remove_reference<T>::type *;
452
453public:
454 /// Create an Expected<T> error value from the given Error.
455 Expected(Error Err)
456 : HasError(true)
457#if LLVM_ENABLE_ABI_BREAKING_CHECKS1
458 // Expected is unchecked upon construction in Debug builds.
459 , Unchecked(true)
460#endif
461 {
462 assert(Err && "Cannot create Expected<T> from Error success value.")((Err && "Cannot create Expected<T> from Error success value."
) ? static_cast<void> (0) : __assert_fail ("Err && \"Cannot create Expected<T> from Error success value.\""
, "/build/llvm-toolchain-snapshot-9~svn362543/include/llvm/Support/Error.h"
, 462, __PRETTY_FUNCTION__))
;
463 new (getErrorStorage()) error_type(Err.takePayload());
464 }
465
466 /// Forbid to convert from Error::success() implicitly, this avoids having
467 /// Expected<T> foo() { return Error::success(); } which compiles otherwise
468 /// but triggers the assertion above.
469 Expected(ErrorSuccess) = delete;
470
471 /// Create an Expected<T> success value from the given OtherT value, which
472 /// must be convertible to T.
473 template <typename OtherT>
474 Expected(OtherT &&Val,
475 typename std::enable_if<std::is_convertible<OtherT, T>::value>::type
476 * = nullptr)
477 : HasError(false)
478#if LLVM_ENABLE_ABI_BREAKING_CHECKS1
479 // Expected is unchecked upon construction in Debug builds.
480 , Unchecked(true)
481#endif
482 {
483 new (getStorage()) storage_type(std::forward<OtherT>(Val));
484 }
485
486 /// Move construct an Expected<T> value.
487 Expected(Expected &&Other) { moveConstruct(std::move(Other)); }
488
489 /// Move construct an Expected<T> value from an Expected<OtherT>, where OtherT
490 /// must be convertible to T.
491 template <class OtherT>
492 Expected(Expected<OtherT> &&Other,
493 typename std::enable_if<std::is_convertible<OtherT, T>::value>::type
494 * = nullptr) {
495 moveConstruct(std::move(Other));
496 }
497
498 /// Move construct an Expected<T> value from an Expected<OtherT>, where OtherT
499 /// isn't convertible to T.
500 template <class OtherT>
501 explicit Expected(
502 Expected<OtherT> &&Other,
503 typename std::enable_if<!std::is_convertible<OtherT, T>::value>::type * =
504 nullptr) {
505 moveConstruct(std::move(Other));
506 }
507
508 /// Move-assign from another Expected<T>.
509 Expected &operator=(Expected &&Other) {
510 moveAssign(std::move(Other));
511 return *this;
512 }
513
514 /// Destroy an Expected<T>.
515 ~Expected() {
516 assertIsChecked();
517 if (!HasError)
518 getStorage()->~storage_type();
519 else
520 getErrorStorage()->~error_type();
521 }
522
523 /// Return false if there is an error.
524 explicit operator bool() {
525#if LLVM_ENABLE_ABI_BREAKING_CHECKS1
526 Unchecked = HasError;
527#endif
528 return !HasError;
529 }
530
531 /// Returns a reference to the stored T value.
532 reference get() {
533 assertIsChecked();
534 return *getStorage();
535 }
536
537 /// Returns a const reference to the stored T value.
538 const_reference get() const {
539 assertIsChecked();
540 return const_cast<Expected<T> *>(this)->get();
541 }
542
543 /// Check that this Expected<T> is an error of type ErrT.
544 template <typename ErrT> bool errorIsA() const {
545 return HasError && (*getErrorStorage())->template isA<ErrT>();
546 }
547
548 /// Take ownership of the stored error.
549 /// After calling this the Expected<T> is in an indeterminate state that can
550 /// only be safely destructed. No further calls (beside the destructor) should
551 /// be made on the Expected<T> vaule.
552 Error takeError() {
553#if LLVM_ENABLE_ABI_BREAKING_CHECKS1
554 Unchecked = false;
555#endif
556 return HasError ? Error(std::move(*getErrorStorage())) : Error::success();
557 }
558
559 /// Returns a pointer to the stored T value.
560 pointer operator->() {
561 assertIsChecked();
562 return toPointer(getStorage());
563 }
564
565 /// Returns a const pointer to the stored T value.
566 const_pointer operator->() const {
567 assertIsChecked();
568 return toPointer(getStorage());
569 }
570
571 /// Returns a reference to the stored T value.
572 reference operator*() {
573 assertIsChecked();
574 return *getStorage();
575 }
576
577 /// Returns a const reference to the stored T value.
578 const_reference operator*() const {
579 assertIsChecked();
580 return *getStorage();
581 }
582
583private:
584 template <class T1>
585 static bool compareThisIfSameType(const T1 &a, const T1 &b) {
586 return &a == &b;
587 }
588
589 template <class T1, class T2>
590 static bool compareThisIfSameType(const T1 &a, const T2 &b) {
591 return false;
592 }
593
594 template <class OtherT> void moveConstruct(Expected<OtherT> &&Other) {
595 HasError = Other.HasError;
596#if LLVM_ENABLE_ABI_BREAKING_CHECKS1
597 Unchecked = true;
598 Other.Unchecked = false;
599#endif
600
601 if (!HasError)
602 new (getStorage()) storage_type(std::move(*Other.getStorage()));
603 else
604 new (getErrorStorage()) error_type(std::move(*Other.getErrorStorage()));
605 }
606
607 template <class OtherT> void moveAssign(Expected<OtherT> &&Other) {
608 assertIsChecked();
609
610 if (compareThisIfSameType(*this, Other))
611 return;
612
613 this->~Expected();
614 new (this) Expected(std::move(Other));
615 }
616
617 pointer toPointer(pointer Val) { return Val; }
618
619 const_pointer toPointer(const_pointer Val) const { return Val; }
620
621 pointer toPointer(wrap *Val) { return &Val->get(); }
622
623 const_pointer toPointer(const wrap *Val) const { return &Val->get(); }
624
625 storage_type *getStorage() {
626 assert(!HasError && "Cannot get value when an error exists!")((!HasError && "Cannot get value when an error exists!"
) ? static_cast<void> (0) : __assert_fail ("!HasError && \"Cannot get value when an error exists!\""
, "/build/llvm-toolchain-snapshot-9~svn362543/include/llvm/Support/Error.h"
, 626, __PRETTY_FUNCTION__))
;
627 return reinterpret_cast<storage_type *>(TStorage.buffer);
628 }
629
630 const storage_type *getStorage() const {
631 assert(!HasError && "Cannot get value when an error exists!")((!HasError && "Cannot get value when an error exists!"
) ? static_cast<void> (0) : __assert_fail ("!HasError && \"Cannot get value when an error exists!\""
, "/build/llvm-toolchain-snapshot-9~svn362543/include/llvm/Support/Error.h"
, 631, __PRETTY_FUNCTION__))
;
632 return reinterpret_cast<const storage_type *>(TStorage.buffer);
633 }
634
635 error_type *getErrorStorage() {
636 assert(HasError && "Cannot get error when a value exists!")((HasError && "Cannot get error when a value exists!"
) ? static_cast<void> (0) : __assert_fail ("HasError && \"Cannot get error when a value exists!\""
, "/build/llvm-toolchain-snapshot-9~svn362543/include/llvm/Support/Error.h"
, 636, __PRETTY_FUNCTION__))
;
637 return reinterpret_cast<error_type *>(ErrorStorage.buffer);
638 }
639
640 const error_type *getErrorStorage() const {
641 assert(HasError && "Cannot get error when a value exists!")((HasError && "Cannot get error when a value exists!"
) ? static_cast<void> (0) : __assert_fail ("HasError && \"Cannot get error when a value exists!\""
, "/build/llvm-toolchain-snapshot-9~svn362543/include/llvm/Support/Error.h"
, 641, __PRETTY_FUNCTION__))
;
642 return reinterpret_cast<const error_type *>(ErrorStorage.buffer);
643 }
644
645 // Used by ExpectedAsOutParameter to reset the checked flag.
646 void setUnchecked() {
647#if LLVM_ENABLE_ABI_BREAKING_CHECKS1
648 Unchecked = true;
649#endif
650 }
651
652#if LLVM_ENABLE_ABI_BREAKING_CHECKS1
653 LLVM_ATTRIBUTE_NORETURN__attribute__((noreturn))
654 LLVM_ATTRIBUTE_NOINLINE__attribute__((noinline))
655 void fatalUncheckedExpected() const {
656 dbgs() << "Expected<T> must be checked before access or destruction.\n";
657 if (HasError) {
658 dbgs() << "Unchecked Expected<T> contained error:\n";
659 (*getErrorStorage())->log(dbgs());
660 } else
661 dbgs() << "Expected<T> value was in success state. (Note: Expected<T> "
662 "values in success mode must still be checked prior to being "
663 "destroyed).\n";
664 abort();
665 }
666#endif
667
668 void assertIsChecked() {
669#if LLVM_ENABLE_ABI_BREAKING_CHECKS1
670 if (LLVM_UNLIKELY(Unchecked)__builtin_expect((bool)(Unchecked), false))
671 fatalUncheckedExpected();
672#endif
673 }
674
675 union {
676 AlignedCharArrayUnion<storage_type> TStorage;
677 AlignedCharArrayUnion<error_type> ErrorStorage;
678 };
679 bool HasError : 1;
680#if LLVM_ENABLE_ABI_BREAKING_CHECKS1
681 bool Unchecked : 1;
682#endif
683};
684
685/// Report a serious error, calling any installed error handler. See
686/// ErrorHandling.h.
687LLVM_ATTRIBUTE_NORETURN__attribute__((noreturn)) void report_fatal_error(Error Err,
688 bool gen_crash_diag = true);
689
690/// Report a fatal error if Err is a failure value.
691///
692/// This function can be used to wrap calls to fallible functions ONLY when it
693/// is known that the Error will always be a success value. E.g.
694///
695/// @code{.cpp}
696/// // foo only attempts the fallible operation if DoFallibleOperation is
697/// // true. If DoFallibleOperation is false then foo always returns
698/// // Error::success().
699/// Error foo(bool DoFallibleOperation);
700///
701/// cantFail(foo(false));
702/// @endcode
703inline void cantFail(Error Err, const char *Msg = nullptr) {
704 if (Err) {
705 if (!Msg)
706 Msg = "Failure value returned from cantFail wrapped call";
707 llvm_unreachable(Msg)::llvm::llvm_unreachable_internal(Msg, "/build/llvm-toolchain-snapshot-9~svn362543/include/llvm/Support/Error.h"
, 707)
;
708 }
709}
710
711/// Report a fatal error if ValOrErr is a failure value, otherwise unwraps and
712/// returns the contained value.
713///
714/// This function can be used to wrap calls to fallible functions ONLY when it
715/// is known that the Error will always be a success value. E.g.
716///
717/// @code{.cpp}
718/// // foo only attempts the fallible operation if DoFallibleOperation is
719/// // true. If DoFallibleOperation is false then foo always returns an int.
720/// Expected<int> foo(bool DoFallibleOperation);
721///
722/// int X = cantFail(foo(false));
723/// @endcode
724template <typename T>
725T cantFail(Expected<T> ValOrErr, const char *Msg = nullptr) {
726 if (ValOrErr)
727 return std::move(*ValOrErr);
728 else {
729 if (!Msg)
730 Msg = "Failure value returned from cantFail wrapped call";
731 llvm_unreachable(Msg)::llvm::llvm_unreachable_internal(Msg, "/build/llvm-toolchain-snapshot-9~svn362543/include/llvm/Support/Error.h"
, 731)
;
732 }
733}
734
735/// Report a fatal error if ValOrErr is a failure value, otherwise unwraps and
736/// returns the contained reference.
737///
738/// This function can be used to wrap calls to fallible functions ONLY when it
739/// is known that the Error will always be a success value. E.g.
740///
741/// @code{.cpp}
742/// // foo only attempts the fallible operation if DoFallibleOperation is
743/// // true. If DoFallibleOperation is false then foo always returns a Bar&.
744/// Expected<Bar&> foo(bool DoFallibleOperation);
745///
746/// Bar &X = cantFail(foo(false));
747/// @endcode
748template <typename T>
749T& cantFail(Expected<T&> ValOrErr, const char *Msg = nullptr) {
750 if (ValOrErr)
751 return *ValOrErr;
752 else {
753 if (!Msg)
754 Msg = "Failure value returned from cantFail wrapped call";
755 llvm_unreachable(Msg)::llvm::llvm_unreachable_internal(Msg, "/build/llvm-toolchain-snapshot-9~svn362543/include/llvm/Support/Error.h"
, 755)
;
756 }
757}
758
759/// Helper for testing applicability of, and applying, handlers for
760/// ErrorInfo types.
761template <typename HandlerT>
762class ErrorHandlerTraits
763 : public ErrorHandlerTraits<decltype(
764 &std::remove_reference<HandlerT>::type::operator())> {};
765
766// Specialization functions of the form 'Error (const ErrT&)'.
767template <typename ErrT> class ErrorHandlerTraits<Error (&)(ErrT &)> {
768public:
769 static bool appliesTo(const ErrorInfoBase &E) {
770 return E.template isA<ErrT>();
771 }
772
773 template <typename HandlerT>
774 static Error apply(HandlerT &&H, std::unique_ptr<ErrorInfoBase> E) {
775 assert(appliesTo(*E) && "Applying incorrect handler")((appliesTo(*E) && "Applying incorrect handler") ? static_cast
<void> (0) : __assert_fail ("appliesTo(*E) && \"Applying incorrect handler\""
, "/build/llvm-toolchain-snapshot-9~svn362543/include/llvm/Support/Error.h"
, 775, __PRETTY_FUNCTION__))
;
776 return H(static_cast<ErrT &>(*E));
777 }
778};
779
780// Specialization functions of the form 'void (const ErrT&)'.
781template <typename ErrT> class ErrorHandlerTraits<void (&)(ErrT &)> {
782public:
783 static bool appliesTo(const ErrorInfoBase &E) {
784 return E.template isA<ErrT>();
785 }
786
787 template <typename HandlerT>
788 static Error apply(HandlerT &&H, std::unique_ptr<ErrorInfoBase> E) {
789 assert(appliesTo(*E) && "Applying incorrect handler")((appliesTo(*E) && "Applying incorrect handler") ? static_cast
<void> (0) : __assert_fail ("appliesTo(*E) && \"Applying incorrect handler\""
, "/build/llvm-toolchain-snapshot-9~svn362543/include/llvm/Support/Error.h"
, 789, __PRETTY_FUNCTION__))
;
790 H(static_cast<ErrT &>(*E));
791 return Error::success();
792 }
793};
794
795/// Specialization for functions of the form 'Error (std::unique_ptr<ErrT>)'.
796template <typename ErrT>
797class ErrorHandlerTraits<Error (&)(std::unique_ptr<ErrT>)> {
798public:
799 static bool appliesTo(const ErrorInfoBase &E) {
800 return E.template isA<ErrT>();
801 }
802
803 template <typename HandlerT>
804 static Error apply(HandlerT &&H, std::unique_ptr<ErrorInfoBase> E) {
805 assert(appliesTo(*E) && "Applying incorrect handler")((appliesTo(*E) && "Applying incorrect handler") ? static_cast
<void> (0) : __assert_fail ("appliesTo(*E) && \"Applying incorrect handler\""
, "/build/llvm-toolchain-snapshot-9~svn362543/include/llvm/Support/Error.h"
, 805, __PRETTY_FUNCTION__))
;
806 std::unique_ptr<ErrT> SubE(static_cast<ErrT *>(E.release()));
807 return H(std::move(SubE));
808 }
809};
810
811/// Specialization for functions of the form 'void (std::unique_ptr<ErrT>)'.
812template <typename ErrT>
813class ErrorHandlerTraits<void (&)(std::unique_ptr<ErrT>)> {
814public:
815 static bool appliesTo(const ErrorInfoBase &E) {
816 return E.template isA<ErrT>();
817 }
818
819 template <typename HandlerT>
820 static Error apply(HandlerT &&H, std::unique_ptr<ErrorInfoBase> E) {
821 assert(appliesTo(*E) && "Applying incorrect handler")((appliesTo(*E) && "Applying incorrect handler") ? static_cast
<void> (0) : __assert_fail ("appliesTo(*E) && \"Applying incorrect handler\""
, "/build/llvm-toolchain-snapshot-9~svn362543/include/llvm/Support/Error.h"
, 821, __PRETTY_FUNCTION__))
;
822 std::unique_ptr<ErrT> SubE(static_cast<ErrT *>(E.release()));
823 H(std::move(SubE));
824 return Error::success();
825 }
826};
827
828// Specialization for member functions of the form 'RetT (const ErrT&)'.
829template <typename C, typename RetT, typename ErrT>
830class ErrorHandlerTraits<RetT (C::*)(ErrT &)>
831 : public ErrorHandlerTraits<RetT (&)(ErrT &)> {};
832
833// Specialization for member functions of the form 'RetT (const ErrT&) const'.
834template <typename C, typename RetT, typename ErrT>
835class ErrorHandlerTraits<RetT (C::*)(ErrT &) const>
836 : public ErrorHandlerTraits<RetT (&)(ErrT &)> {};
837
838// Specialization for member functions of the form 'RetT (const ErrT&)'.
839template <typename C, typename RetT, typename ErrT>
840class ErrorHandlerTraits<RetT (C::*)(const ErrT &)>
841 : public ErrorHandlerTraits<RetT (&)(ErrT &)> {};
842
843// Specialization for member functions of the form 'RetT (const ErrT&) const'.
844template <typename C, typename RetT, typename ErrT>
845class ErrorHandlerTraits<RetT (C::*)(const ErrT &) const>
846 : public ErrorHandlerTraits<RetT (&)(ErrT &)> {};
847
848/// Specialization for member functions of the form
849/// 'RetT (std::unique_ptr<ErrT>)'.
850template <typename C, typename RetT, typename ErrT>
851class ErrorHandlerTraits<RetT (C::*)(std::unique_ptr<ErrT>)>
852 : public ErrorHandlerTraits<RetT (&)(std::unique_ptr<ErrT>)> {};
853
854/// Specialization for member functions of the form
855/// 'RetT (std::unique_ptr<ErrT>) const'.
856template <typename C, typename RetT, typename ErrT>
857class ErrorHandlerTraits<RetT (C::*)(std::unique_ptr<ErrT>) const>
858 : public ErrorHandlerTraits<RetT (&)(std::unique_ptr<ErrT>)> {};
859
860inline Error handleErrorImpl(std::unique_ptr<ErrorInfoBase> Payload) {
861 return Error(std::move(Payload));
862}
863
864template <typename HandlerT, typename... HandlerTs>
865Error handleErrorImpl(std::unique_ptr<ErrorInfoBase> Payload,
866 HandlerT &&Handler, HandlerTs &&... Handlers) {
867 if (ErrorHandlerTraits<HandlerT>::appliesTo(*Payload))
868 return ErrorHandlerTraits<HandlerT>::apply(std::forward<HandlerT>(Handler),
869 std::move(Payload));
870 return handleErrorImpl(std::move(Payload),
871 std::forward<HandlerTs>(Handlers)...);
872}
873
874/// Pass the ErrorInfo(s) contained in E to their respective handlers. Any
875/// unhandled errors (or Errors returned by handlers) are re-concatenated and
876/// returned.
877/// Because this function returns an error, its result must also be checked
878/// or returned. If you intend to handle all errors use handleAllErrors
879/// (which returns void, and will abort() on unhandled errors) instead.
880template <typename... HandlerTs>
881Error handleErrors(Error E, HandlerTs &&... Hs) {
882 if (!E)
883 return Error::success();
884
885 std::unique_ptr<ErrorInfoBase> Payload = E.takePayload();
886
887 if (Payload->isA<ErrorList>()) {
888 ErrorList &List = static_cast<ErrorList &>(*Payload);
889 Error R;
890 for (auto &P : List.Payloads)
891 R = ErrorList::join(
892 std::move(R),
893 handleErrorImpl(std::move(P), std::forward<HandlerTs>(Hs)...));
894 return R;
895 }
896
897 return handleErrorImpl(std::move(Payload), std::forward<HandlerTs>(Hs)...);
898}
899
900/// Behaves the same as handleErrors, except that by contract all errors
901/// *must* be handled by the given handlers (i.e. there must be no remaining
902/// errors after running the handlers, or llvm_unreachable is called).
903template <typename... HandlerTs>
904void handleAllErrors(Error E, HandlerTs &&... Handlers) {
905 cantFail(handleErrors(std::move(E), std::forward<HandlerTs>(Handlers)...));
906}
907
908/// Check that E is a non-error, then drop it.
909/// If E is an error, llvm_unreachable will be called.
910inline void handleAllErrors(Error E) {
911 cantFail(std::move(E));
912}
913
914/// Handle any errors (if present) in an Expected<T>, then try a recovery path.
915///
916/// If the incoming value is a success value it is returned unmodified. If it
917/// is a failure value then it the contained error is passed to handleErrors.
918/// If handleErrors is able to handle the error then the RecoveryPath functor
919/// is called to supply the final result. If handleErrors is not able to
920/// handle all errors then the unhandled errors are returned.
921///
922/// This utility enables the follow pattern:
923///
924/// @code{.cpp}
925/// enum FooStrategy { Aggressive, Conservative };
926/// Expected<Foo> foo(FooStrategy S);
927///
928/// auto ResultOrErr =
929/// handleExpected(
930/// foo(Aggressive),
931/// []() { return foo(Conservative); },
932/// [](AggressiveStrategyError&) {
933/// // Implicitly conusme this - we'll recover by using a conservative
934/// // strategy.
935/// });
936///
937/// @endcode
938template <typename T, typename RecoveryFtor, typename... HandlerTs>
939Expected<T> handleExpected(Expected<T> ValOrErr, RecoveryFtor &&RecoveryPath,
940 HandlerTs &&... Handlers) {
941 if (ValOrErr)
942 return ValOrErr;
943
944 if (auto Err = handleErrors(ValOrErr.takeError(),
945 std::forward<HandlerTs>(Handlers)...))
946 return std::move(Err);
947
948 return RecoveryPath();
949}
950
951/// Log all errors (if any) in E to OS. If there are any errors, ErrorBanner
952/// will be printed before the first one is logged. A newline will be printed
953/// after each error.
954///
955/// This function is compatible with the helpers from Support/WithColor.h. You
956/// can pass any of them as the OS. Please consider using them instead of
957/// including 'error: ' in the ErrorBanner.
958///
959/// This is useful in the base level of your program to allow clean termination
960/// (allowing clean deallocation of resources, etc.), while reporting error
961/// information to the user.
962void logAllUnhandledErrors(Error E, raw_ostream &OS, Twine ErrorBanner = {});
963
964/// Write all error messages (if any) in E to a string. The newline character
965/// is used to separate error messages.
966inline std::string toString(Error E) {
967 SmallVector<std::string, 2> Errors;
968 handleAllErrors(std::move(E), [&Errors](const ErrorInfoBase &EI) {
969 Errors.push_back(EI.message());
970 });
971 return join(Errors.begin(), Errors.end(), "\n");
972}
973
974/// Consume a Error without doing anything. This method should be used
975/// only where an error can be considered a reasonable and expected return
976/// value.
977///
978/// Uses of this method are potentially indicative of design problems: If it's
979/// legitimate to do nothing while processing an "error", the error-producer
980/// might be more clearly refactored to return an Optional<T>.
981inline void consumeError(Error Err) {
982 handleAllErrors(std::move(Err), [](const ErrorInfoBase &) {});
983}
984
985/// Helper for converting an Error to a bool.
986///
987/// This method returns true if Err is in an error state, or false if it is
988/// in a success state. Puts Err in a checked state in both cases (unlike
989/// Error::operator bool(), which only does this for success states).
990inline bool errorToBool(Error Err) {
991 bool IsError = static_cast<bool>(Err);
992 if (IsError)
993 consumeError(std::move(Err));
994 return IsError;
995}
996
997/// Helper for Errors used as out-parameters.
998///
999/// This helper is for use with the Error-as-out-parameter idiom, where an error
1000/// is passed to a function or method by reference, rather than being returned.
1001/// In such cases it is helpful to set the checked bit on entry to the function
1002/// so that the error can be written to (unchecked Errors abort on assignment)
1003/// and clear the checked bit on exit so that clients cannot accidentally forget
1004/// to check the result. This helper performs these actions automatically using
1005/// RAII:
1006///
1007/// @code{.cpp}
1008/// Result foo(Error &Err) {
1009/// ErrorAsOutParameter ErrAsOutParam(&Err); // 'Checked' flag set
1010/// // <body of foo>
1011/// // <- 'Checked' flag auto-cleared when ErrAsOutParam is destructed.
1012/// }
1013/// @endcode
1014///
1015/// ErrorAsOutParameter takes an Error* rather than Error& so that it can be
1016/// used with optional Errors (Error pointers that are allowed to be null). If
1017/// ErrorAsOutParameter took an Error reference, an instance would have to be
1018/// created inside every condition that verified that Error was non-null. By
1019/// taking an Error pointer we can just create one instance at the top of the
1020/// function.
1021class ErrorAsOutParameter {
1022public:
1023 ErrorAsOutParameter(Error *Err) : Err(Err) {
1024 // Raise the checked bit if Err is success.
1025 if (Err)
1026 (void)!!*Err;
1027 }
1028
1029 ~ErrorAsOutParameter() {
1030 // Clear the checked bit.
1031 if (Err && !*Err)
1032 *Err = Error::success();
1033 }
1034
1035private:
1036 Error *Err;
1037};
1038
1039/// Helper for Expected<T>s used as out-parameters.
1040///
1041/// See ErrorAsOutParameter.
1042template <typename T>
1043class ExpectedAsOutParameter {
1044public:
1045 ExpectedAsOutParameter(Expected<T> *ValOrErr)
1046 : ValOrErr(ValOrErr) {
1047 if (ValOrErr)
1048 (void)!!*ValOrErr;
1049 }
1050
1051 ~ExpectedAsOutParameter() {
1052 if (ValOrErr)
1053 ValOrErr->setUnchecked();
1054 }
1055
1056private:
1057 Expected<T> *ValOrErr;
1058};
1059
1060/// This class wraps a std::error_code in a Error.
1061///
1062/// This is useful if you're writing an interface that returns a Error
1063/// (or Expected) and you want to call code that still returns
1064/// std::error_codes.
1065class ECError : public ErrorInfo<ECError> {
1066 friend Error errorCodeToError(std::error_code);
1067
1068 virtual void anchor() override;
1069
1070public:
1071 void setErrorCode(std::error_code EC) { this->EC = EC; }
1072 std::error_code convertToErrorCode() const override { return EC; }
1073 void log(raw_ostream &OS) const override { OS << EC.message(); }
1074
1075 // Used by ErrorInfo::classID.
1076 static char ID;
1077
1078protected:
1079 ECError() = default;
1080 ECError(std::error_code EC) : EC(EC) {}
1081
1082 std::error_code EC;
1083};
1084
1085/// The value returned by this function can be returned from convertToErrorCode
1086/// for Error values where no sensible translation to std::error_code exists.
1087/// It should only be used in this situation, and should never be used where a
1088/// sensible conversion to std::error_code is available, as attempts to convert
1089/// to/from this error will result in a fatal error. (i.e. it is a programmatic
1090///error to try to convert such a value).
1091std::error_code inconvertibleErrorCode();
1092
1093/// Helper for converting an std::error_code to a Error.
1094Error errorCodeToError(std::error_code EC);
1095
1096/// Helper for converting an ECError to a std::error_code.
1097///
1098/// This method requires that Err be Error() or an ECError, otherwise it
1099/// will trigger a call to abort().
1100std::error_code errorToErrorCode(Error Err);
1101
1102/// Convert an ErrorOr<T> to an Expected<T>.
1103template <typename T> Expected<T> errorOrToExpected(ErrorOr<T> &&EO) {
1104 if (auto EC = EO.getError())
1105 return errorCodeToError(EC);
1106 return std::move(*EO);
1107}
1108
1109/// Convert an Expected<T> to an ErrorOr<T>.
1110template <typename T> ErrorOr<T> expectedToErrorOr(Expected<T> &&E) {
1111 if (auto Err = E.takeError())
1112 return errorToErrorCode(std::move(Err));
1113 return std::move(*E);
1114}
1115
1116/// This class wraps a string in an Error.
1117///
1118/// StringError is useful in cases where the client is not expected to be able
1119/// to consume the specific error message programmatically (for example, if the
1120/// error message is to be presented to the user).
1121///
1122/// StringError can also be used when additional information is to be printed
1123/// along with a error_code message. Depending on the constructor called, this
1124/// class can either display:
1125/// 1. the error_code message (ECError behavior)
1126/// 2. a string
1127/// 3. the error_code message and a string
1128///
1129/// These behaviors are useful when subtyping is required; for example, when a
1130/// specific library needs an explicit error type. In the example below,
1131/// PDBError is derived from StringError:
1132///
1133/// @code{.cpp}
1134/// Expected<int> foo() {
1135/// return llvm::make_error<PDBError>(pdb_error_code::dia_failed_loading,
1136/// "Additional information");
1137/// }
1138/// @endcode
1139///
1140class StringError : public ErrorInfo<StringError> {
1141public:
1142 static char ID;
1143
1144 // Prints EC + S and converts to EC
1145 StringError(std::error_code EC, const Twine &S = Twine());
1146
1147 // Prints S and converts to EC
1148 StringError(const Twine &S, std::error_code EC);
1149
1150 void log(raw_ostream &OS) const override;
1151 std::error_code convertToErrorCode() const override;
1152
1153 const std::string &getMessage() const { return Msg; }
1154
1155private:
1156 std::string Msg;
1157 std::error_code EC;
1158 const bool PrintMsgOnly = false;
1159};
1160
1161/// Create formatted StringError object.
1162template <typename... Ts>
1163Error createStringError(std::error_code EC, char const *Fmt,
1164 const Ts &... Vals) {
1165 std::string Buffer;
1166 raw_string_ostream Stream(Buffer);
1167 Stream << format(Fmt, Vals...);
1168 return make_error<StringError>(Stream.str(), EC);
1169}
1170
1171Error createStringError(std::error_code EC, char const *Msg);
1172
1173/// This class wraps a filename and another Error.
1174///
1175/// In some cases, an error needs to live along a 'source' name, in order to
1176/// show more detailed information to the user.
1177class FileError final : public ErrorInfo<FileError> {
1178
1179 friend Error createFileError(const Twine &, Error);
1180 friend Error createFileError(const Twine &, size_t, Error);
1181
1182public:
1183 void log(raw_ostream &OS) const override {
1184 assert(Err && !FileName.empty() && "Trying to log after takeError().")((Err && !FileName.empty() && "Trying to log after takeError()."
) ? static_cast<void> (0) : __assert_fail ("Err && !FileName.empty() && \"Trying to log after takeError().\""
, "/build/llvm-toolchain-snapshot-9~svn362543/include/llvm/Support/Error.h"
, 1184, __PRETTY_FUNCTION__))
;
1185 OS << "'" << FileName << "': ";
1186 if (Line.hasValue())
1187 OS << "line " << Line.getValue() << ": ";
1188 Err->log(OS);
1189 }
1190
1191 Error takeError() { return Error(std::move(Err)); }
1192
1193 std::error_code convertToErrorCode() const override;
1194
1195 // Used by ErrorInfo::classID.
1196 static char ID;
1197
1198private:
1199 FileError(const Twine &F, Optional<size_t> LineNum,
1200 std::unique_ptr<ErrorInfoBase> E) {
1201 assert(E && "Cannot create FileError from Error success value.")((E && "Cannot create FileError from Error success value."
) ? static_cast<void> (0) : __assert_fail ("E && \"Cannot create FileError from Error success value.\""
, "/build/llvm-toolchain-snapshot-9~svn362543/include/llvm/Support/Error.h"
, 1201, __PRETTY_FUNCTION__))
;
1202 assert(!F.isTriviallyEmpty() &&((!F.isTriviallyEmpty() && "The file name provided to FileError must not be empty."
) ? static_cast<void> (0) : __assert_fail ("!F.isTriviallyEmpty() && \"The file name provided to FileError must not be empty.\""
, "/build/llvm-toolchain-snapshot-9~svn362543/include/llvm/Support/Error.h"
, 1203, __PRETTY_FUNCTION__))
1203 "The file name provided to FileError must not be empty.")((!F.isTriviallyEmpty() && "The file name provided to FileError must not be empty."
) ? static_cast<void> (0) : __assert_fail ("!F.isTriviallyEmpty() && \"The file name provided to FileError must not be empty.\""
, "/build/llvm-toolchain-snapshot-9~svn362543/include/llvm/Support/Error.h"
, 1203, __PRETTY_FUNCTION__))
;
1204 FileName = F.str();
1205 Err = std::move(E);
1206 Line = std::move(LineNum);
1207 }
1208
1209 static Error build(const Twine &F, Optional<size_t> Line, Error E) {
1210 return Error(
1211 std::unique_ptr<FileError>(new FileError(F, Line, E.takePayload())));
1212 }
1213
1214 std::string FileName;
1215 Optional<size_t> Line;
1216 std::unique_ptr<ErrorInfoBase> Err;
1217};
1218
1219/// Concatenate a source file path and/or name with an Error. The resulting
1220/// Error is unchecked.
1221inline Error createFileError(const Twine &F, Error E) {
1222 return FileError::build(F, Optional<size_t>(), std::move(E));
1223}
1224
1225/// Concatenate a source file path and/or name with line number and an Error.
1226/// The resulting Error is unchecked.
1227inline Error createFileError(const Twine &F, size_t Line, Error E) {
1228 return FileError::build(F, Optional<size_t>(Line), std::move(E));
1229}
1230
1231/// Concatenate a source file path and/or name with a std::error_code
1232/// to form an Error object.
1233inline Error createFileError(const Twine &F, std::error_code EC) {
1234 return createFileError(F, errorCodeToError(EC));
1235}
1236
1237/// Concatenate a source file path and/or name with line number and
1238/// std::error_code to form an Error object.
1239inline Error createFileError(const Twine &F, size_t Line, std::error_code EC) {
1240 return createFileError(F, Line, errorCodeToError(EC));
1241}
1242
1243Error createFileError(const Twine &F, ErrorSuccess) = delete;
1244
1245/// Helper for check-and-exit error handling.
1246///
1247/// For tool use only. NOT FOR USE IN LIBRARY CODE.
1248///
1249class ExitOnError {
1250public:
1251 /// Create an error on exit helper.
1252 ExitOnError(std::string Banner = "", int DefaultErrorExitCode = 1)
1253 : Banner(std::move(Banner)),
1254 GetExitCode([=](const Error &) { return DefaultErrorExitCode; }) {}
1255
1256 /// Set the banner string for any errors caught by operator().
1257 void setBanner(std::string Banner) { this->Banner = std::move(Banner); }
1258
1259 /// Set the exit-code mapper function.
1260 void setExitCodeMapper(std::function<int(const Error &)> GetExitCode) {
1261 this->GetExitCode = std::move(GetExitCode);
1262 }
1263
1264 /// Check Err. If it's in a failure state log the error(s) and exit.
1265 void operator()(Error Err) const { checkError(std::move(Err)); }
1266
1267 /// Check E. If it's in a success state then return the contained value. If
1268 /// it's in a failure state log the error(s) and exit.
1269 template <typename T> T operator()(Expected<T> &&E) const {
1270 checkError(E.takeError());
1271 return std::move(*E);
1272 }
1273
1274 /// Check E. If it's in a success state then return the contained reference. If
1275 /// it's in a failure state log the error(s) and exit.
1276 template <typename T> T& operator()(Expected<T&> &&E) const {
1277 checkError(E.takeError());
1278 return *E;
1279 }
1280
1281private:
1282 void checkError(Error Err) const {
1283 if (Err) {
1284 int ExitCode = GetExitCode(Err);
1285 logAllUnhandledErrors(std::move(Err), errs(), Banner);
1286 exit(ExitCode);
1287 }
1288 }
1289
1290 std::string Banner;
1291 std::function<int(const Error &)> GetExitCode;
1292};
1293
1294/// Conversion from Error to LLVMErrorRef for C error bindings.
1295inline LLVMErrorRef wrap(Error Err) {
1296 return reinterpret_cast<LLVMErrorRef>(Err.takePayload().release());
1297}
1298
1299/// Conversion from LLVMErrorRef to Error for C error bindings.
1300inline Error unwrap(LLVMErrorRef ErrRef) {
1301 return Error(std::unique_ptr<ErrorInfoBase>(
1302 reinterpret_cast<ErrorInfoBase *>(ErrRef)));
1303}
1304
1305} // end namespace llvm
1306
1307#endif // LLVM_SUPPORT_ERROR_H

/build/llvm-toolchain-snapshot-9~svn362543/include/llvm/ADT/STLExtras.h

1//===- llvm/ADT/STLExtras.h - Useful STL related functions ------*- C++ -*-===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This file contains some templates that are useful if you are working with the
10// STL at all.
11//
12// No library is required when using these functions.
13//
14//===----------------------------------------------------------------------===//
15
16#ifndef LLVM_ADT_STLEXTRAS_H
17#define LLVM_ADT_STLEXTRAS_H
18
19#include "llvm/ADT/Optional.h"
20#include "llvm/ADT/SmallVector.h"
21#include "llvm/ADT/iterator.h"
22#include "llvm/ADT/iterator_range.h"
23#include "llvm/Config/abi-breaking.h"
24#include "llvm/Support/ErrorHandling.h"
25#include <algorithm>
26#include <cassert>
27#include <cstddef>
28#include <cstdint>
29#include <cstdlib>
30#include <functional>
31#include <initializer_list>
32#include <iterator>
33#include <limits>
34#include <memory>
35#include <tuple>
36#include <type_traits>
37#include <utility>
38
39#ifdef EXPENSIVE_CHECKS
40#include <random> // for std::mt19937
41#endif
42
43namespace llvm {
44
45// Only used by compiler if both template types are the same. Useful when
46// using SFINAE to test for the existence of member functions.
47template <typename T, T> struct SameType;
48
49namespace detail {
50
51template <typename RangeT>
52using IterOfRange = decltype(std::begin(std::declval<RangeT &>()));
53
54template <typename RangeT>
55using ValueOfRange = typename std::remove_reference<decltype(
56 *std::begin(std::declval<RangeT &>()))>::type;
57
58} // end namespace detail
59
60//===----------------------------------------------------------------------===//
61// Extra additions to <type_traits>
62//===----------------------------------------------------------------------===//
63
64template <typename T>
65struct negation : std::integral_constant<bool, !bool(T::value)> {};
66
67template <typename...> struct conjunction : std::true_type {};
68template <typename B1> struct conjunction<B1> : B1 {};
69template <typename B1, typename... Bn>
70struct conjunction<B1, Bn...>
71 : std::conditional<bool(B1::value), conjunction<Bn...>, B1>::type {};
72
73template <typename T> struct make_const_ptr {
74 using type =
75 typename std::add_pointer<typename std::add_const<T>::type>::type;
76};
77
78template <typename T> struct make_const_ref {
79 using type = typename std::add_lvalue_reference<
80 typename std::add_const<T>::type>::type;
81};
82
83//===----------------------------------------------------------------------===//
84// Extra additions to <functional>
85//===----------------------------------------------------------------------===//
86
87template <class Ty> struct identity {
88 using argument_type = Ty;
89
90 Ty &operator()(Ty &self) const {
91 return self;
92 }
93 const Ty &operator()(const Ty &self) const {
94 return self;
95 }
96};
97
98template <class Ty> struct less_ptr {
99 bool operator()(const Ty* left, const Ty* right) const {
100 return *left < *right;
101 }
102};
103
104template <class Ty> struct greater_ptr {
105 bool operator()(const Ty* left, const Ty* right) const {
106 return *right < *left;
107 }
108};
109
110/// An efficient, type-erasing, non-owning reference to a callable. This is
111/// intended for use as the type of a function parameter that is not used
112/// after the function in question returns.
113///
114/// This class does not own the callable, so it is not in general safe to store
115/// a function_ref.
116template<typename Fn> class function_ref;
117
118template<typename Ret, typename ...Params>
119class function_ref<Ret(Params...)> {
120 Ret (*callback)(intptr_t callable, Params ...params) = nullptr;
121 intptr_t callable;
122
123 template<typename Callable>
124 static Ret callback_fn(intptr_t callable, Params ...params) {
125 return (*reinterpret_cast<Callable*>(callable))(
126 std::forward<Params>(params)...);
127 }
128
129public:
130 function_ref() = default;
131 function_ref(std::nullptr_t) {}
132
133 template <typename Callable>
134 function_ref(Callable &&callable,
135 typename std::enable_if<
136 !std::is_same<typename std::remove_reference<Callable>::type,
137 function_ref>::value>::type * = nullptr)
138 : callback(callback_fn<typename std::remove_reference<Callable>::type>),
139 callable(reinterpret_cast<intptr_t>(&callable)) {}
140
141 Ret operator()(Params ...params) const {
142 return callback(callable, std::forward<Params>(params)...);
143 }
144
145 operator bool() const { return callback; }
146};
147
148// deleter - Very very very simple method that is used to invoke operator
149// delete on something. It is used like this:
150//
151// for_each(V.begin(), B.end(), deleter<Interval>);
152template <class T>
153inline void deleter(T *Ptr) {
154 delete Ptr;
155}
156
157//===----------------------------------------------------------------------===//
158// Extra additions to <iterator>
159//===----------------------------------------------------------------------===//
160
161namespace adl_detail {
162
163using std::begin;
164
165template <typename ContainerTy>
166auto adl_begin(ContainerTy &&container)
167 -> decltype(begin(std::forward<ContainerTy>(container))) {
168 return begin(std::forward<ContainerTy>(container));
169}
170
171using std::end;
172
173template <typename ContainerTy>
174auto adl_end(ContainerTy &&container)
175 -> decltype(end(std::forward<ContainerTy>(container))) {
176 return end(std::forward<ContainerTy>(container));
177}
178
179using std::swap;
180
181template <typename T>
182void adl_swap(T &&lhs, T &&rhs) noexcept(noexcept(swap(std::declval<T>(),
183 std::declval<T>()))) {
184 swap(std::forward<T>(lhs), std::forward<T>(rhs));
185}
186
187} // end namespace adl_detail
188
189template <typename ContainerTy>
190auto adl_begin(ContainerTy &&container)
191 -> decltype(adl_detail::adl_begin(std::forward<ContainerTy>(container))) {
192 return adl_detail::adl_begin(std::forward<ContainerTy>(container));
193}
194
195template <typename ContainerTy>
196auto adl_end(ContainerTy &&container)
197 -> decltype(adl_detail::adl_end(std::forward<ContainerTy>(container))) {
198 return adl_detail::adl_end(std::forward<ContainerTy>(container));
199}
200
201template <typename T>
202void adl_swap(T &&lhs, T &&rhs) noexcept(
203 noexcept(adl_detail::adl_swap(std::declval<T>(), std::declval<T>()))) {
204 adl_detail::adl_swap(std::forward<T>(lhs), std::forward<T>(rhs));
205}
206
207/// Test whether \p RangeOrContainer is empty. Similar to C++17 std::empty.
208template <typename T>
209constexpr bool empty(const T &RangeOrContainer) {
210 return adl_begin(RangeOrContainer) == adl_end(RangeOrContainer);
211}
212
213// mapped_iterator - This is a simple iterator adapter that causes a function to
214// be applied whenever operator* is invoked on the iterator.
215
216template <typename ItTy, typename FuncTy,
217 typename FuncReturnTy =
218 decltype(std::declval<FuncTy>()(*std::declval<ItTy>()))>
219class mapped_iterator
220 : public iterator_adaptor_base<
221 mapped_iterator<ItTy, FuncTy>, ItTy,
222 typename std::iterator_traits<ItTy>::iterator_category,
223 typename std::remove_reference<FuncReturnTy>::type> {
224public:
225 mapped_iterator(ItTy U, FuncTy F)
226 : mapped_iterator::iterator_adaptor_base(std::move(U)), F(std::move(F)) {}
227
228 ItTy getCurrent() { return this->I; }
229
230 FuncReturnTy operator*() { return F(*this->I); }
231
232private:
233 FuncTy F;
234};
235
236// map_iterator - Provide a convenient way to create mapped_iterators, just like
237// make_pair is useful for creating pairs...
238template <class ItTy, class FuncTy>
239inline mapped_iterator<ItTy, FuncTy> map_iterator(ItTy I, FuncTy F) {
240 return mapped_iterator<ItTy, FuncTy>(std::move(I), std::move(F));
241}
242
243/// Helper to determine if type T has a member called rbegin().
244template <typename Ty> class has_rbegin_impl {
245 using yes = char[1];
246 using no = char[2];
247
248 template <typename Inner>
249 static yes& test(Inner *I, decltype(I->rbegin()) * = nullptr);
250
251 template <typename>
252 static no& test(...);
253
254public:
255 static const bool value = sizeof(test<Ty>(nullptr)) == sizeof(yes);
256};
257
258/// Metafunction to determine if T& or T has a member called rbegin().
259template <typename Ty>
260struct has_rbegin : has_rbegin_impl<typename std::remove_reference<Ty>::type> {
261};
262
263// Returns an iterator_range over the given container which iterates in reverse.
264// Note that the container must have rbegin()/rend() methods for this to work.
265template <typename ContainerTy>
266auto reverse(ContainerTy &&C,
267 typename std::enable_if<has_rbegin<ContainerTy>::value>::type * =
268 nullptr) -> decltype(make_range(C.rbegin(), C.rend())) {
269 return make_range(C.rbegin(), C.rend());
270}
271
272// Returns a std::reverse_iterator wrapped around the given iterator.
273template <typename IteratorTy>
274std::reverse_iterator<IteratorTy> make_reverse_iterator(IteratorTy It) {
275 return std::reverse_iterator<IteratorTy>(It);
276}
277
278// Returns an iterator_range over the given container which iterates in reverse.
279// Note that the container must have begin()/end() methods which return
280// bidirectional iterators for this to work.
281template <typename ContainerTy>
282auto reverse(
283 ContainerTy &&C,
284 typename std::enable_if<!has_rbegin<ContainerTy>::value>::type * = nullptr)
285 -> decltype(make_range(llvm::make_reverse_iterator(std::end(C)),
286 llvm::make_reverse_iterator(std::begin(C)))) {
287 return make_range(llvm::make_reverse_iterator(std::end(C)),
288 llvm::make_reverse_iterator(std::begin(C)));
289}
290
291/// An iterator adaptor that filters the elements of given inner iterators.
292///
293/// The predicate parameter should be a callable object that accepts the wrapped
294/// iterator's reference type and returns a bool. When incrementing or
295/// decrementing the iterator, it will call the predicate on each element and
296/// skip any where it returns false.
297///
298/// \code
299/// int A[] = { 1, 2, 3, 4 };
300/// auto R = make_filter_range(A, [](int N) { return N % 2 == 1; });
301/// // R contains { 1, 3 }.
302/// \endcode
303///
304/// Note: filter_iterator_base implements support for forward iteration.
305/// filter_iterator_impl exists to provide support for bidirectional iteration,
306/// conditional on whether the wrapped iterator supports it.
307template <typename WrappedIteratorT, typename PredicateT, typename IterTag>
308class filter_iterator_base
309 : public iterator_adaptor_base<
310 filter_iterator_base<WrappedIteratorT, PredicateT, IterTag>,
311 WrappedIteratorT,
312 typename std::common_type<
313 IterTag, typename std::iterator_traits<
314 WrappedIteratorT>::iterator_category>::type> {
315 using BaseT = iterator_adaptor_base<
316 filter_iterator_base<WrappedIteratorT, PredicateT, IterTag>,
317 WrappedIteratorT,
318 typename std::common_type<
319 IterTag, typename std::iterator_traits<
320 WrappedIteratorT>::iterator_category>::type>;
321
322protected:
323 WrappedIteratorT End;
324 PredicateT Pred;
325
326 void findNextValid() {
327 while (this->I != End && !Pred(*this->I))
328 BaseT::operator++();
329 }
330
331 // Construct the iterator. The begin iterator needs to know where the end
332 // is, so that it can properly stop when it gets there. The end iterator only
333 // needs the predicate to support bidirectional iteration.
334 filter_iterator_base(WrappedIteratorT Begin, WrappedIteratorT End,
335 PredicateT Pred)
336 : BaseT(Begin), End(End), Pred(Pred) {
337 findNextValid();
338 }
339
340public:
341 using BaseT::operator++;
342
343 filter_iterator_base &operator++() {
344 BaseT::operator++();
345 findNextValid();
346 return *this;
347 }
348};
349
350/// Specialization of filter_iterator_base for forward iteration only.
351template <typename WrappedIteratorT, typename PredicateT,
352 typename IterTag = std::forward_iterator_tag>
353class filter_iterator_impl
354 : public filter_iterator_base<WrappedIteratorT, PredicateT, IterTag> {
355 using BaseT = filter_iterator_base<WrappedIteratorT, PredicateT, IterTag>;
356
357public:
358 filter_iterator_impl(WrappedIteratorT Begin, WrappedIteratorT End,
359 PredicateT Pred)
360 : BaseT(Begin, End, Pred) {}
361};
362
363/// Specialization of filter_iterator_base for bidirectional iteration.
364template <typename WrappedIteratorT, typename PredicateT>
365class filter_iterator_impl<WrappedIteratorT, PredicateT,
366 std::bidirectional_iterator_tag>
367 : public filter_iterator_base<WrappedIteratorT, PredicateT,
368 std::bidirectional_iterator_tag> {
369 using BaseT = filter_iterator_base<WrappedIteratorT, PredicateT,
370 std::bidirectional_iterator_tag>;
371 void findPrevValid() {
372 while (!this->Pred(*this->I))
373 BaseT::operator--();
374 }
375
376public:
377 using BaseT::operator--;
378
379 filter_iterator_impl(WrappedIteratorT Begin, WrappedIteratorT End,
380 PredicateT Pred)
381 : BaseT(Begin, End, Pred) {}
382
383 filter_iterator_impl &operator--() {
384 BaseT::operator--();
385 findPrevValid();
386 return *this;
387 }
388};
389
390namespace detail {
391
392template <bool is_bidirectional> struct fwd_or_bidi_tag_impl {
393 using type = std::forward_iterator_tag;
394};
395
396template <> struct fwd_or_bidi_tag_impl<true> {
397 using type = std::bidirectional_iterator_tag;
398};
399
400/// Helper which sets its type member to forward_iterator_tag if the category
401/// of \p IterT does not derive from bidirectional_iterator_tag, and to
402/// bidirectional_iterator_tag otherwise.
403template <typename IterT> struct fwd_or_bidi_tag {
404 using type = typename fwd_or_bidi_tag_impl<std::is_base_of<
405 std::bidirectional_iterator_tag,
406 typename std::iterator_traits<IterT>::iterator_category>::value>::type;
407};
408
409} // namespace detail
410
411/// Defines filter_iterator to a suitable specialization of
412/// filter_iterator_impl, based on the underlying iterator's category.
413template <typename WrappedIteratorT, typename PredicateT>
414using filter_iterator = filter_iterator_impl<
415 WrappedIteratorT, PredicateT,
416 typename detail::fwd_or_bidi_tag<WrappedIteratorT>::type>;
417
418/// Convenience function that takes a range of elements and a predicate,
419/// and return a new filter_iterator range.
420///
421/// FIXME: Currently if RangeT && is a rvalue reference to a temporary, the
422/// lifetime of that temporary is not kept by the returned range object, and the
423/// temporary is going to be dropped on the floor after the make_iterator_range
424/// full expression that contains this function call.
425template <typename RangeT, typename PredicateT>
426iterator_range<filter_iterator<detail::IterOfRange<RangeT>, PredicateT>>
427make_filter_range(RangeT &&Range, PredicateT Pred) {
428 using FilterIteratorT =
429 filter_iterator<detail::IterOfRange<RangeT>, PredicateT>;
430 return make_range(
431 FilterIteratorT(std::begin(std::forward<RangeT>(Range)),
432 std::end(std::forward<RangeT>(Range)), Pred),
433 FilterIteratorT(std::end(std::forward<RangeT>(Range)),
434 std::end(std::forward<RangeT>(Range)), Pred));
435}
436
437/// A pseudo-iterator adaptor that is designed to implement "early increment"
438/// style loops.
439///
440/// This is *not a normal iterator* and should almost never be used directly. It
441/// is intended primarily to be used with range based for loops and some range
442/// algorithms.
443///
444/// The iterator isn't quite an `OutputIterator` or an `InputIterator` but
445/// somewhere between them. The constraints of these iterators are:
446///
447/// - On construction or after being incremented, it is comparable and
448/// dereferencable. It is *not* incrementable.
449/// - After being dereferenced, it is neither comparable nor dereferencable, it
450/// is only incrementable.
451///
452/// This means you can only dereference the iterator once, and you can only
453/// increment it once between dereferences.
454template <typename WrappedIteratorT>
455class early_inc_iterator_impl
456 : public iterator_adaptor_base<early_inc_iterator_impl<WrappedIteratorT>,
457 WrappedIteratorT, std::input_iterator_tag> {
458 using BaseT =
459 iterator_adaptor_base<early_inc_iterator_impl<WrappedIteratorT>,
460 WrappedIteratorT, std::input_iterator_tag>;
461
462 using PointerT = typename std::iterator_traits<WrappedIteratorT>::pointer;
463
464protected:
465#if LLVM_ENABLE_ABI_BREAKING_CHECKS1
466 bool IsEarlyIncremented = false;
467#endif
468
469public:
470 early_inc_iterator_impl(WrappedIteratorT I) : BaseT(I) {}
471
472 using BaseT::operator*;
473 typename BaseT::reference operator*() {
474#if LLVM_ENABLE_ABI_BREAKING_CHECKS1
475 assert(!IsEarlyIncremented && "Cannot dereference twice!")((!IsEarlyIncremented && "Cannot dereference twice!")
? static_cast<void> (0) : __assert_fail ("!IsEarlyIncremented && \"Cannot dereference twice!\""
, "/build/llvm-toolchain-snapshot-9~svn362543/include/llvm/ADT/STLExtras.h"
, 475, __PRETTY_FUNCTION__))
;
476 IsEarlyIncremented = true;
477#endif
478 return *(this->I)++;
479 }
480
481 using BaseT::operator++;
482 early_inc_iterator_impl &operator++() {
483#if LLVM_ENABLE_ABI_BREAKING_CHECKS1
484 assert(IsEarlyIncremented && "Cannot increment before dereferencing!")((IsEarlyIncremented && "Cannot increment before dereferencing!"
) ? static_cast<void> (0) : __assert_fail ("IsEarlyIncremented && \"Cannot increment before dereferencing!\""
, "/build/llvm-toolchain-snapshot-9~svn362543/include/llvm/ADT/STLExtras.h"
, 484, __PRETTY_FUNCTION__))
;
485 IsEarlyIncremented = false;
486#endif
487 return *this;
488 }
489
490 using BaseT::operator==;
491 bool operator==(const early_inc_iterator_impl &RHS) const {
492#if LLVM_ENABLE_ABI_BREAKING_CHECKS1
493 assert(!IsEarlyIncremented && "Cannot compare after dereferencing!")((!IsEarlyIncremented && "Cannot compare after dereferencing!"
) ? static_cast<void> (0) : __assert_fail ("!IsEarlyIncremented && \"Cannot compare after dereferencing!\""
, "/build/llvm-toolchain-snapshot-9~svn362543/include/llvm/ADT/STLExtras.h"
, 493, __PRETTY_FUNCTION__))
;
494#endif
495 return BaseT::operator==(RHS);
496 }
497};
498
499/// Make a range that does early increment to allow mutation of the underlying
500/// range without disrupting iteration.
501///
502/// The underlying iterator will be incremented immediately after it is
503/// dereferenced, allowing deletion of the current node or insertion of nodes to
504/// not disrupt iteration provided they do not invalidate the *next* iterator --
505/// the current iterator can be invalidated.
506///
507/// This requires a very exact pattern of use that is only really suitable to
508/// range based for loops and other range algorithms that explicitly guarantee
509/// to dereference exactly once each element, and to increment exactly once each
510/// element.
511template <typename RangeT>
512iterator_range<early_inc_iterator_impl<detail::IterOfRange<RangeT>>>
513make_early_inc_range(RangeT &&Range) {
514 using EarlyIncIteratorT =
515 early_inc_iterator_impl<detail::IterOfRange<RangeT>>;
516 return make_range(EarlyIncIteratorT(std::begin(std::forward<RangeT>(Range))),
517 EarlyIncIteratorT(std::end(std::forward<RangeT>(Range))));
518}
519
520// forward declarations required by zip_shortest/zip_first/zip_longest
521template <typename R, typename UnaryPredicate>
522bool all_of(R &&range, UnaryPredicate P);
523template <typename R, typename UnaryPredicate>
524bool any_of(R &&range, UnaryPredicate P);
525
526template <size_t... I> struct index_sequence;
527
528template <class... Ts> struct index_sequence_for;
529
530namespace detail {
531
532using std::declval;
533
534// We have to alias this since inlining the actual type at the usage site
535// in the parameter list of iterator_facade_base<> below ICEs MSVC 2017.
536template<typename... Iters> struct ZipTupleType {
537 using type = std::tuple<decltype(*declval<Iters>())...>;
538};
539
540template <typename ZipType, typename... Iters>
541using zip_traits = iterator_facade_base<
542 ZipType, typename std::common_type<std::bidirectional_iterator_tag,
543 typename std::iterator_traits<
544 Iters>::iterator_category...>::type,
545 // ^ TODO: Implement random access methods.
546 typename ZipTupleType<Iters...>::type,
547 typename std::iterator_traits<typename std::tuple_element<
548 0, std::tuple<Iters...>>::type>::difference_type,
549 // ^ FIXME: This follows boost::make_zip_iterator's assumption that all
550 // inner iterators have the same difference_type. It would fail if, for
551 // instance, the second field's difference_type were non-numeric while the
552 // first is.
553 typename ZipTupleType<Iters...>::type *,
554 typename ZipTupleType<Iters...>::type>;
555
556template <typename ZipType, typename... Iters>
557struct zip_common : public zip_traits<ZipType, Iters...> {
558 using Base = zip_traits<ZipType, Iters...>;
559 using value_type = typename Base::value_type;
560
561 std::tuple<Iters...> iterators;
562
563protected:
564 template <size_t... Ns> value_type deref(index_sequence<Ns...>) const {
565 return value_type(*std::get<Ns>(iterators)...);
566 }
567
568 template <size_t... Ns>
569 decltype(iterators) tup_inc(index_sequence<Ns...>) const {
570 return std::tuple<Iters...>(std::next(std::get<Ns>(iterators))...);
571 }
572
573 template <size_t... Ns>
574 decltype(iterators) tup_dec(index_sequence<Ns...>) const {
575 return std::tuple<Iters...>(std::prev(std::get<Ns>(iterators))...);
576 }
577
578public:
579 zip_common(Iters &&... ts) : iterators(std::forward<Iters>(ts)...) {}
580
581 value_type operator*() { return deref(index_sequence_for<Iters...>{}); }
582
583 const value_type operator*() const {
584 return deref(index_sequence_for<Iters...>{});
585 }
586
587 ZipType &operator++() {
588 iterators = tup_inc(index_sequence_for<Iters...>{});
589 return *reinterpret_cast<ZipType *>(this);
590 }
591
592 ZipType &operator--() {
593 static_assert(Base::IsBidirectional,
594 "All inner iterators must be at least bidirectional.");
595 iterators = tup_dec(index_sequence_for<Iters...>{});
596 return *reinterpret_cast<ZipType *>(this);
597 }
598};
599
600template <typename... Iters>
601struct zip_first : public zip_common<zip_first<Iters...>, Iters...> {
602 using Base = zip_common<zip_first<Iters...>, Iters...>;
603
604 bool operator==(const zip_first<Iters...> &other) const {
605 return std::get<0>(this->iterators) == std::get<0>(other.iterators);
606 }
607
608 zip_first(Iters &&... ts) : Base(std::forward<Iters>(ts)...) {}
609};
610
611template <typename... Iters>
612class zip_shortest : public zip_common<zip_shortest<Iters...>, Iters...> {
613 template <size_t... Ns>
614 bool test(const zip_shortest<Iters...> &other, index_sequence<Ns...>) const {
615 return all_of(std::initializer_list<bool>{std::get<Ns>(this->iterators) !=
616 std::get<Ns>(other.iterators)...},
617 identity<bool>{});
618 }
619
620public:
621 using Base = zip_common<zip_shortest<Iters...>, Iters...>;
622
623 zip_shortest(Iters &&... ts) : Base(std::forward<Iters>(ts)...) {}
624
625 bool operator==(const zip_shortest<Iters...> &other) const {
626 return !test(other, index_sequence_for<Iters...>{});
627 }
628};
629
630template <template <typename...> class ItType, typename... Args> class zippy {
631public:
632 using iterator = ItType<decltype(std::begin(std::declval<Args>()))...>;
633 using iterator_category = typename iterator::iterator_category;
634 using value_type = typename iterator::value_type;
635 using difference_type = typename iterator::difference_type;
636 using pointer = typename iterator::pointer;
637 using reference = typename iterator::reference;
638
639private:
640 std::tuple<Args...> ts;
641
642 template <size_t... Ns> iterator begin_impl(index_sequence<Ns...>) const {
643 return iterator(std::begin(std::get<Ns>(ts))...);
644 }
645 template <size_t... Ns> iterator end_impl(index_sequence<Ns...>) const {
646 return iterator(std::end(std::get<Ns>(ts))...);
647 }
648
649public:
650 zippy(Args &&... ts_) : ts(std::forward<Args>(ts_)...) {}
651
652 iterator begin() const { return begin_impl(index_sequence_for<Args...>{}); }
653 iterator end() const { return end_impl(index_sequence_for<Args...>{}); }
654};
655
656} // end namespace detail
657
658/// zip iterator for two or more iteratable types.
659template <typename T, typename U, typename... Args>
660detail::zippy<detail::zip_shortest, T, U, Args...> zip(T &&t, U &&u,
661 Args &&... args) {
662 return detail::zippy<detail::zip_shortest, T, U, Args...>(
663 std::forward<T>(t), std::forward<U>(u), std::forward<Args>(args)...);
664}
665
666/// zip iterator that, for the sake of efficiency, assumes the first iteratee to
667/// be the shortest.
668template <typename T, typename U, typename... Args>
669detail::zippy<detail::zip_first, T, U, Args...> zip_first(T &&t, U &&u,
670 Args &&... args) {
671 return detail::zippy<detail::zip_first, T, U, Args...>(
672 std::forward<T>(t), std::forward<U>(u), std::forward<Args>(args)...);
673}
674
675namespace detail {
676template <typename Iter>
677static Iter next_or_end(const Iter &I, const Iter &End) {
678 if (I == End)
679 return End;
680 return std::next(I);
681}
682
683template <typename Iter>
684static auto deref_or_none(const Iter &I, const Iter &End)
685 -> llvm::Optional<typename std::remove_const<
686 typename std::remove_reference<decltype(*I)>::type>::type> {
687 if (I == End)
688 return None;
689 return *I;
690}
691
692template <typename Iter> struct ZipLongestItemType {
693 using type =
694 llvm::Optional<typename std::remove_const<typename std::remove_reference<
695 decltype(*std::declval<Iter>())>::type>::type>;
696};
697
698template <typename... Iters> struct ZipLongestTupleType {
699 using type = std::tuple<typename ZipLongestItemType<Iters>::type...>;
700};
701
702template <typename... Iters>
703class zip_longest_iterator
704 : public iterator_facade_base<
705 zip_longest_iterator<Iters...>,
706 typename std::common_type<
707 std::forward_iterator_tag,
708 typename std::iterator_traits<Iters>::iterator_category...>::type,
709 typename ZipLongestTupleType<Iters...>::type,
710 typename std::iterator_traits<typename std::tuple_element<
711 0, std::tuple<Iters...>>::type>::difference_type,
712 typename ZipLongestTupleType<Iters...>::type *,
713 typename ZipLongestTupleType<Iters...>::type> {
714public:
715 using value_type = typename ZipLongestTupleType<Iters...>::type;
716
717private:
718 std::tuple<Iters...> iterators;
719 std::tuple<Iters...> end_iterators;
720
721 template <size_t... Ns>
722 bool test(const zip_longest_iterator<Iters...> &other,
723 index_sequence<Ns...>) const {
724 return llvm::any_of(
725 std::initializer_list<bool>{std::get<Ns>(this->iterators) !=
726 std::get<Ns>(other.iterators)...},
727 identity<bool>{});
728 }
729
730 template <size_t... Ns> value_type deref(index_sequence<Ns...>) const {
731 return value_type(
732 deref_or_none(std::get<Ns>(iterators), std::get<Ns>(end_iterators))...);
733 }
734
735 template <size_t... Ns>
736 decltype(iterators) tup_inc(index_sequence<Ns...>) const {
737 return std::tuple<Iters...>(
738 next_or_end(std::get<Ns>(iterators), std::get<Ns>(end_iterators))...);
739 }
740
741public:
742 zip_longest_iterator(std::pair<Iters &&, Iters &&>... ts)
743 : iterators(std::forward<Iters>(ts.first)...),
744 end_iterators(std::forward<Iters>(ts.second)...) {}
745
746 value_type operator*() { return deref(index_sequence_for<Iters...>{}); }
747
748 value_type operator*() const { return deref(index_sequence_for<Iters...>{}); }
749
750 zip_longest_iterator<Iters...> &operator++() {
751 iterators = tup_inc(index_sequence_for<Iters...>{});
752 return *this;
753 }
754
755 bool operator==(const zip_longest_iterator<Iters...> &other) const {
756 return !test(other, index_sequence_for<Iters...>{});
757 }
758};
759
760template <typename... Args> class zip_longest_range {
761public:
762 using iterator =
763 zip_longest_iterator<decltype(adl_begin(std::declval<Args>()))...>;
764 using iterator_category = typename iterator::iterator_category;
765 using value_type = typename iterator::value_type;
766 using difference_type = typename iterator::difference_type;
767 using pointer = typename iterator::pointer;
768 using reference = typename iterator::reference;
769
770private:
771 std::tuple<Args...> ts;
772
773 template <size_t... Ns> iterator begin_impl(index_sequence<Ns...>) const {
774 return iterator(std::make_pair(adl_begin(std::get<Ns>(ts)),
775 adl_end(std::get<Ns>(ts)))...);
776 }
777
778 template <size_t... Ns> iterator end_impl(index_sequence<Ns...>) const {
779 return iterator(std::make_pair(adl_end(std::get<Ns>(ts)),
780 adl_end(std::get<Ns>(ts)))...);
781 }
782
783public:
784 zip_longest_range(Args &&... ts_) : ts(std::forward<Args>(ts_)...) {}
785
786 iterator begin() const { return begin_impl(index_sequence_for<Args...>{}); }
787 iterator end() const { return end_impl(index_sequence_for<Args...>{}); }
788};
789} // namespace detail
790
791/// Iterate over two or more iterators at the same time. Iteration continues
792/// until all iterators reach the end. The llvm::Optional only contains a value
793/// if the iterator has not reached the end.
794template <typename T, typename U, typename... Args>
795detail::zip_longest_range<T, U, Args...> zip_longest(T &&t, U &&u,
796 Args &&... args) {
797 return detail::zip_longest_range<T, U, Args...>(
798 std::forward<T>(t), std::forward<U>(u), std::forward<Args>(args)...);
799}
800
801/// Iterator wrapper that concatenates sequences together.
802///
803/// This can concatenate different iterators, even with different types, into
804/// a single iterator provided the value types of all the concatenated
805/// iterators expose `reference` and `pointer` types that can be converted to
806/// `ValueT &` and `ValueT *` respectively. It doesn't support more
807/// interesting/customized pointer or reference types.
808///
809/// Currently this only supports forward or higher iterator categories as
810/// inputs and always exposes a forward iterator interface.
811template <typename ValueT, typename... IterTs>
812class concat_iterator
813 : public iterator_facade_base<concat_iterator<ValueT, IterTs...>,
814 std::forward_iterator_tag, ValueT> {
815 using BaseT = typename concat_iterator::iterator_facade_base;
816
817 /// We store both the current and end iterators for each concatenated
818 /// sequence in a tuple of pairs.
819 ///
820 /// Note that something like iterator_range seems nice at first here, but the
821 /// range properties are of little benefit and end up getting in the way
822 /// because we need to do mutation on the current iterators.
823 std::tuple<IterTs...> Begins;
824 std::tuple<IterTs...> Ends;
825
826 /// Attempts to increment a specific iterator.
827 ///
828 /// Returns true if it was able to increment the iterator. Returns false if
829 /// the iterator is already at the end iterator.
830 template <size_t Index> bool incrementHelper() {
831 auto &Begin = std::get<Index>(Begins);
832 auto &End = std::get<Index>(Ends);
833 if (Begin == End)
834 return false;
835
836 ++Begin;
837 return true;
838 }
839
840 /// Increments the first non-end iterator.
841 ///
842 /// It is an error to call this with all iterators at the end.
843 template <size_t... Ns> void increment(index_sequence<Ns...>) {
844 // Build a sequence of functions to increment each iterator if possible.
845 bool (concat_iterator::*IncrementHelperFns[])() = {
846 &concat_iterator::incrementHelper<Ns>...};
847
848 // Loop over them, and stop as soon as we succeed at incrementing one.
849 for (auto &IncrementHelperFn : IncrementHelperFns)
850 if ((this->*IncrementHelperFn)())
851 return;
852
853 llvm_unreachable("Attempted to increment an end concat iterator!")::llvm::llvm_unreachable_internal("Attempted to increment an end concat iterator!"
, "/build/llvm-toolchain-snapshot-9~svn362543/include/llvm/ADT/STLExtras.h"
, 853)
;
854 }
855
856 /// Returns null if the specified iterator is at the end. Otherwise,
857 /// dereferences the iterator and returns the address of the resulting
858 /// reference.
859 template <size_t Index> ValueT *getHelper() const {
860 auto &Begin = std::get<Index>(Begins);
861 auto &End = std::get<Index>(Ends);
862 if (Begin == End)
863 return nullptr;
864
865 return &*Begin;
866 }
867
868 /// Finds the first non-end iterator, dereferences, and returns the resulting
869 /// reference.
870 ///
871 /// It is an error to call this with all iterators at the end.
872 template <size_t... Ns> ValueT &get(index_sequence<Ns...>) const {
873 // Build a sequence of functions to get from iterator if possible.
874 ValueT *(concat_iterator::*GetHelperFns[])() const = {
875 &concat_iterator::getHelper<Ns>...};
876
877 // Loop over them, and return the first result we find.
878 for (auto &GetHelperFn : GetHelperFns)
879 if (ValueT *P = (this->*GetHelperFn)())
880 return *P;
881
882 llvm_unreachable("Attempted to get a pointer from an end concat iterator!")::llvm::llvm_unreachable_internal("Attempted to get a pointer from an end concat iterator!"
, "/build/llvm-toolchain-snapshot-9~svn362543/include/llvm/ADT/STLExtras.h"
, 882)
;
883 }
884
885public:
886 /// Constructs an iterator from a squence of ranges.
887 ///
888 /// We need the full range to know how to switch between each of the
889 /// iterators.
890 template <typename... RangeTs>
891 explicit concat_iterator(RangeTs &&... Ranges)
892 : Begins(std::begin(Ranges)...), Ends(std::end(Ranges)...) {}
893
894 using BaseT::operator++;
895
896 concat_iterator &operator++() {
897 increment(index_sequence_for<IterTs...>());
898 return *this;
899 }
900
901 ValueT &operator*() const { return get(index_sequence_for<IterTs...>()); }
902
903 bool operator==(const concat_iterator &RHS) const {
904 return Begins == RHS.Begins && Ends == RHS.Ends;
905 }
906};
907
908namespace detail {
909
910/// Helper to store a sequence of ranges being concatenated and access them.
911///
912/// This is designed to facilitate providing actual storage when temporaries
913/// are passed into the constructor such that we can use it as part of range
914/// based for loops.
915template <typename ValueT, typename... RangeTs> class concat_range {
916public:
917 using iterator =
918 concat_iterator<ValueT,
919 decltype(std::begin(std::declval<RangeTs &>()))...>;
920
921private:
922 std::tuple<RangeTs...> Ranges;
923
924 template <size_t... Ns> iterator begin_impl(index_sequence<Ns...>) {
925 return iterator(std::get<Ns>(Ranges)...);
926 }
927 template <size_t... Ns> iterator end_impl(index_sequence<Ns...>) {
928 return iterator(make_range(std::end(std::get<Ns>(Ranges)),
929 std::end(std::get<Ns>(Ranges)))...);
930 }
931
932public:
933 concat_range(RangeTs &&... Ranges)
934 : Ranges(std::forward<RangeTs>(Ranges)...) {}
935
936 iterator begin() { return begin_impl(index_sequence_for<RangeTs...>{}); }
937 iterator end() { return end_impl(index_sequence_for<RangeTs...>{}); }
938};
939
940} // end namespace detail
941
942/// Concatenated range across two or more ranges.
943///
944/// The desired value type must be explicitly specified.
945template <typename ValueT, typename... RangeTs>
946detail::concat_range<ValueT, RangeTs...> concat(RangeTs &&... Ranges) {
947 static_assert(sizeof...(RangeTs) > 1,
948 "Need more than one range to concatenate!");
949 return detail::concat_range<ValueT, RangeTs...>(
950 std::forward<RangeTs>(Ranges)...);
951}
952
953//===----------------------------------------------------------------------===//
954// Extra additions to <utility>
955//===----------------------------------------------------------------------===//
956
957/// Function object to check whether the first component of a std::pair
958/// compares less than the first component of another std::pair.
959struct less_first {
960 template <typename T> bool operator()(const T &lhs, const T &rhs) const {
961 return lhs.first < rhs.first;
962 }
963};
964
965/// Function object to check whether the second component of a std::pair
966/// compares less than the second component of another std::pair.
967struct less_second {
968 template <typename T> bool operator()(const T &lhs, const T &rhs) const {
969 return lhs.second < rhs.second;
970 }
971};
972
973/// \brief Function object to apply a binary function to the first component of
974/// a std::pair.
975template<typename FuncTy>
976struct on_first {
977 FuncTy func;
978
979 template <typename T>
980 auto operator()(const T &lhs, const T &rhs) const
981 -> decltype(func(lhs.first, rhs.first)) {
982 return func(lhs.first, rhs.first);
983 }
984};
985
986// A subset of N3658. More stuff can be added as-needed.
987
988/// Represents a compile-time sequence of integers.
989template <class T, T... I> struct integer_sequence {
990 using value_type = T;
991
992 static constexpr size_t size() { return sizeof...(I); }
993};
994
995/// Alias for the common case of a sequence of size_ts.
996template <size_t... I>
997struct index_sequence : integer_sequence<std::size_t, I...> {};
998
999template <std::size_t N, std::size_t... I>
1000struct build_index_impl : build_index_impl<N - 1, N - 1, I...> {};
1001template <std::size_t... I>
1002struct build_index_impl<0, I...> : index_sequence<I...> {};
1003
1004/// Creates a compile-time integer sequence for a parameter pack.
1005template <class... Ts>
1006struct index_sequence_for : build_index_impl<sizeof...(Ts)> {};
1007
1008/// Utility type to build an inheritance chain that makes it easy to rank
1009/// overload candidates.
1010template <int N> struct rank : rank<N - 1> {};
1011template <> struct rank<0> {};
1012
1013/// traits class for checking whether type T is one of any of the given
1014/// types in the variadic list.
1015template <typename T, typename... Ts> struct is_one_of {
1016 static const bool value = false;
1017};
1018
1019template <typename T, typename U, typename... Ts>
1020struct is_one_of<T, U, Ts...> {
1021 static const bool value =
1022 std::is_same<T, U>::value || is_one_of<T, Ts...>::value;
1023};
1024
1025/// traits class for checking whether type T is a base class for all
1026/// the given types in the variadic list.
1027template <typename T, typename... Ts> struct are_base_of {
1028 static const bool value = true;
1029};
1030
1031template <typename T, typename U, typename... Ts>
1032struct are_base_of<T, U, Ts...> {
1033 static const bool value =
1034 std::is_base_of<T, U>::value && are_base_of<T, Ts...>::value;
1035};
1036
1037//===----------------------------------------------------------------------===//
1038// Extra additions for arrays
1039//===----------------------------------------------------------------------===//
1040
1041/// Find the length of an array.
1042template <class T, std::size_t N>
1043constexpr inline size_t array_lengthof(T (&)[N]) {
1044 return N;
1045}
1046
1047/// Adapt std::less<T> for array_pod_sort.
1048template<typename T>
1049inline int array_pod_sort_comparator(const void *P1, const void *P2) {
1050 if (std::less<T>()(*reinterpret_cast<const T*>(P1),
1051 *reinterpret_cast<const T*>(P2)))
1052 return -1;
1053 if (std::less<T>()(*reinterpret_cast<const T*>(P2),
1054 *reinterpret_cast<const T*>(P1)))
1055 return 1;
1056 return 0;
1057}
1058
1059/// get_array_pod_sort_comparator - This is an internal helper function used to
1060/// get type deduction of T right.
1061template<typename T>
1062inline int (*get_array_pod_sort_comparator(const T &))
1063 (const void*, const void*) {
1064 return array_pod_sort_comparator<T>;
1065}
1066
1067/// array_pod_sort - This sorts an array with the specified start and end
1068/// extent. This is just like std::sort, except that it calls qsort instead of
1069/// using an inlined template. qsort is slightly slower than std::sort, but
1070/// most sorts are not performance critical in LLVM and std::sort has to be
1071/// template instantiated for each type, leading to significant measured code
1072/// bloat. This function should generally be used instead of std::sort where
1073/// possible.
1074///
1075/// This function assumes that you have simple POD-like types that can be
1076/// compared with std::less and can be moved with memcpy. If this isn't true,
1077/// you should use std::sort.
1078///
1079/// NOTE: If qsort_r were portable, we could allow a custom comparator and
1080/// default to std::less.
1081template<class IteratorTy>
1082inline void array_pod_sort(IteratorTy Start, IteratorTy End) {
1083 // Don't inefficiently call qsort with one element or trigger undefined
1084 // behavior with an empty sequence.
1085 auto NElts = End - Start;
1086 if (NElts <= 1) return;
1087#ifdef EXPENSIVE_CHECKS
1088 std::mt19937 Generator(std::random_device{}());
1089 std::shuffle(Start, End, Generator);
1090#endif
1091 qsort(&*Start, NElts, sizeof(*Start), get_array_pod_sort_comparator(*Start));
1092}
1093
1094template <class IteratorTy>
1095inline void array_pod_sort(
1096 IteratorTy Start, IteratorTy End,
1097 int (*Compare)(
1098 const typename std::iterator_traits<IteratorTy>::value_type *,
1099 const typename std::iterator_traits<IteratorTy>::value_type *)) {
1100 // Don't inefficiently call qsort with one element or trigger undefined
1101 // behavior with an empty sequence.
1102 auto NElts = End - Start;
1103 if (NElts <= 1) return;
1104#ifdef EXPENSIVE_CHECKS
1105 std::mt19937 Generator(std::random_device{}());
1106 std::shuffle(Start, End, Generator);
1107#endif
1108 qsort(&*Start, NElts, sizeof(*Start),
1109 reinterpret_cast<int (*)(const void *, const void *)>(Compare));
1110}
1111
1112// Provide wrappers to std::sort which shuffle the elements before sorting
1113// to help uncover non-deterministic behavior (PR35135).
1114template <typename IteratorTy>
1115inline void sort(IteratorTy Start, IteratorTy End) {
1116#ifdef EXPENSIVE_CHECKS
1117 std::mt19937 Generator(std::random_device{}());
1118 std::shuffle(Start, End, Generator);
1119#endif
1120 std::sort(Start, End);
1121}
1122
1123template <typename Container> inline void sort(Container &&C) {
1124 llvm::sort(adl_begin(C), adl_end(C));
1125}
1126
1127template <typename IteratorTy, typename Compare>
1128inline void sort(IteratorTy Start, IteratorTy End, Compare Comp) {
1129#ifdef EXPENSIVE_CHECKS
1130 std::mt19937 Generator(std::random_device{}());
1131 std::shuffle(Start, End, Generator);
1132#endif
1133 std::sort(Start, End, Comp);
1134}
1135
1136template <typename Container, typename Compare>
1137inline void sort(Container &&C, Compare Comp) {
1138 llvm::sort(adl_begin(C), adl_end(C), Comp);
1139}
1140
1141//===----------------------------------------------------------------------===//
1142// Extra additions to <algorithm>
1143//===----------------------------------------------------------------------===//
1144
1145/// For a container of pointers, deletes the pointers and then clears the
1146/// container.
1147template<typename Container>
1148void DeleteContainerPointers(Container &C) {
1149 for (auto V : C)
1150 delete V;
1151 C.clear();
1152}
1153
1154/// In a container of pairs (usually a map) whose second element is a pointer,
1155/// deletes the second elements and then clears the container.
1156template<typename Container>
1157void DeleteContainerSeconds(Container &C) {
1158 for (auto &V : C)
1159 delete V.second;
1160 C.clear();
1161}
1162
1163/// Get the size of a range. This is a wrapper function around std::distance
1164/// which is only enabled when the operation is O(1).
1165template <typename R>
1166auto size(R &&Range, typename std::enable_if<
1167 std::is_same<typename std::iterator_traits<decltype(
1168 Range.begin())>::iterator_category,
1169 std::random_access_iterator_tag>::value,
1170 void>::type * = nullptr)
1171 -> decltype(std::distance(Range.begin(), Range.end())) {
1172 return std::distance(Range.begin(), Range.end());
1173}
1174
1175/// Provide wrappers to std::for_each which take ranges instead of having to
1176/// pass begin/end explicitly.
1177template <typename R, typename UnaryPredicate>
1178UnaryPredicate for_each(R &&Range, UnaryPredicate P) {
1179 return std::for_each(adl_begin(Range), adl_end(Range), P);
1180}
1181
1182/// Provide wrappers to std::all_of which take ranges instead of having to pass
1183/// begin/end explicitly.
1184template <typename R, typename UnaryPredicate>
1185bool all_of(R &&Range, UnaryPredicate P) {
1186 return std::all_of(adl_begin(Range), adl_end(Range), P);
1187}
1188
1189/// Provide wrappers to std::any_of which take ranges instead of having to pass
1190/// begin/end explicitly.
1191template <typename R, typename UnaryPredicate>
1192bool any_of(R &&Range, UnaryPredicate P) {
1193 return std::any_of(adl_begin(Range), adl_end(Range), P);
1194}
1195
1196/// Provide wrappers to std::none_of which take ranges instead of having to pass
1197/// begin/end explicitly.
1198template <typename R, typename UnaryPredicate>
1199bool none_of(R &&Range, UnaryPredicate P) {
1200 return std::none_of(adl_begin(Range), adl_end(Range), P);
1201}
1202
1203/// Provide wrappers to std::find which take ranges instead of having to pass
1204/// begin/end explicitly.
1205template <typename R, typename T>
1206auto find(R &&Range, const T &Val) -> decltype(adl_begin(Range)) {
1207 return std::find(adl_begin(Range), adl_end(Range), Val);
1208}
1209
1210/// Provide wrappers to std::find_if which take ranges instead of having to pass
1211/// begin/end explicitly.
1212template <typename R, typename UnaryPredicate>
1213auto find_if(R &&Range, UnaryPredicate P) -> decltype(adl_begin(Range)) {
1214 return std::find_if(adl_begin(Range), adl_end(Range), P);
1215}
1216
1217template <typename R, typename UnaryPredicate>
1218auto find_if_not(R &&Range, UnaryPredicate P) -> decltype(adl_begin(Range)) {
1219 return std::find_if_not(adl_begin(Range), adl_end(Range), P);
1220}
1221
1222/// Provide wrappers to std::remove_if which take ranges instead of having to
1223/// pass begin/end explicitly.
1224template <typename R, typename UnaryPredicate>
1225auto remove_if(R &&Range, UnaryPredicate P) -> decltype(adl_begin(Range)) {
1226 return std::remove_if(adl_begin(Range), adl_end(Range), P);
1227}
1228
1229/// Provide wrappers to std::copy_if which take ranges instead of having to
1230/// pass begin/end explicitly.
1231template <typename R, typename OutputIt, typename UnaryPredicate>
1232OutputIt copy_if(R &&Range, OutputIt Out, UnaryPredicate P) {
1233 return std::copy_if(adl_begin(Range), adl_end(Range), Out, P);
1234}
1235
1236template <typename R, typename OutputIt>
1237OutputIt copy(R &&Range, OutputIt Out) {
1238 return std::copy(adl_begin(Range), adl_end(Range), Out);
1239}
1240
1241/// Wrapper function around std::find to detect if an element exists
1242/// in a container.
1243template <typename R, typename E>
1244bool is_contained(R &&Range, const E &Element) {
1245 return std::find(adl_begin(Range), adl_end(Range), Element) != adl_end(Range);
1246}
1247
1248/// Wrapper function around std::count to count the number of times an element
1249/// \p Element occurs in the given range \p Range.
1250template <typename R, typename E>
1251auto count(R &&Range, const E &Element) ->
1252 typename std::iterator_traits<decltype(adl_begin(Range))>::difference_type {
1253 return std::count(adl_begin(Range), adl_end(Range), Element);
1254}
1255
1256/// Wrapper function around std::count_if to count the number of times an
1257/// element satisfying a given predicate occurs in a range.
1258template <typename R, typename UnaryPredicate>
1259auto count_if(R &&Range, UnaryPredicate P) ->
1260 typename std::iterator_traits<decltype(adl_begin(Range))>::difference_type {
1261 return std::count_if(adl_begin(Range), adl_end(Range), P);
1262}
1263
1264/// Wrapper function around std::transform to apply a function to a range and
1265/// store the result elsewhere.
1266template <typename R, typename OutputIt, typename UnaryPredicate>
1267OutputIt transform(R &&Range, OutputIt d_first, UnaryPredicate P) {
1268 return std::transform(adl_begin(Range), adl_end(Range), d_first, P);
1269}
1270
1271/// Provide wrappers to std::partition which take ranges instead of having to
1272/// pass begin/end explicitly.
1273template <typename R, typename UnaryPredicate>
1274auto partition(R &&Range, UnaryPredicate P) -> decltype(adl_begin(Range)) {
1275 return std::partition(adl_begin(Range), adl_end(Range), P);
1276}
1277
1278/// Provide wrappers to std::lower_bound which take ranges instead of having to
1279/// pass begin/end explicitly.
1280template <typename R, typename T>
1281auto lower_bound(R &&Range, T &&Value) -> decltype(adl_begin(Range)) {
1282 return std::lower_bound(adl_begin(Range), adl_end(Range),
1283 std::forward<T>(Value));
1284}
1285
1286template <typename R, typename T, typename Compare>
1287auto lower_bound(R &&Range, T &&Value, Compare C)
1288 -> decltype(adl_begin(Range)) {
1289 return std::lower_bound(adl_begin(Range), adl_end(Range),
1290 std::forward<T>(Value), C);
1291}
1292
1293/// Provide wrappers to std::upper_bound which take ranges instead of having to
1294/// pass begin/end explicitly.
1295template <typename R, typename T>
1296auto upper_bound(R &&Range, T &&Value) -> decltype(adl_begin(Range)) {
1297 return std::upper_bound(adl_begin(Range), adl_end(Range),
1298 std::forward<T>(Value));
1299}
1300
1301template <typename R, typename T, typename Compare>
1302auto upper_bound(R &&Range, T &&Value, Compare C)
1303 -> decltype(adl_begin(Range)) {
1304 return std::upper_bound(adl_begin(Range), adl_end(Range),
1305 std::forward<T>(Value), C);
1306}
1307
1308template <typename R>
1309void stable_sort(R &&Range) {
1310 std::stable_sort(adl_begin(Range), adl_end(Range));
1311}
1312
1313template <typename R, typename Compare>
1314void stable_sort(R &&Range, Compare C) {
1315 std::stable_sort(adl_begin(Range), adl_end(Range), C);
1316}
1317
1318/// Binary search for the first index where a predicate is true.
1319/// Returns the first I in [Lo, Hi) where C(I) is true, or Hi if it never is.
1320/// Requires that C is always false below some limit, and always true above it.
1321///
1322/// Example:
1323/// size_t DawnModernEra = bsearch(1776, 2050, [](size_t Year){
1324/// return Presidents.for(Year).twitterHandle() != None;
1325/// });
1326///
1327/// Note the return value differs from std::binary_search!
1328template <typename Predicate>
1329size_t bsearch(size_t Lo, size_t Hi, Predicate P) {
1330 while (Lo != Hi) {
1331 assert(Hi > Lo)((Hi > Lo) ? static_cast<void> (0) : __assert_fail (
"Hi > Lo", "/build/llvm-toolchain-snapshot-9~svn362543/include/llvm/ADT/STLExtras.h"
, 1331, __PRETTY_FUNCTION__))
;
1332 size_t Mid = Lo + (Hi - Lo) / 2;
1333 if (P(Mid))
1334 Hi = Mid;
1335 else
1336 Lo = Mid + 1;
1337 }
1338 return Hi;
1339}
1340
1341/// Binary search for the first iterator where a predicate is true.
1342/// Returns the first I in [Lo, Hi) where C(*I) is true, or Hi if it never is.
1343/// Requires that C is always false below some limit, and always true above it.
1344template <typename It, typename Predicate,
1345 typename Val = decltype(*std::declval<It>())>
1346It bsearch(It Lo, It Hi, Predicate P) {
1347 return std::lower_bound(Lo, Hi, 0u,
1348 [&](const Val &V, unsigned) { return !P(V); });
1349}
1350
1351/// Binary search for the first iterator in a range where a predicate is true.
1352/// Requires that C is always false below some limit, and always true above it.
1353template <typename R, typename Predicate>
1354auto bsearch(R &&Range, Predicate P) -> decltype(adl_begin(Range)) {
1355 return bsearch(adl_begin(Range), adl_end(Range), P);
1356}
1357
1358/// Wrapper function around std::equal to detect if all elements
1359/// in a container are same.
1360template <typename R>
1361bool is_splat(R &&Range) {
1362 size_t range_size = size(Range);
1363 return range_size != 0 && (range_size == 1 ||
1364 std::equal(adl_begin(Range) + 1, adl_end(Range), adl_begin(Range)));
1365}
1366
1367/// Given a range of type R, iterate the entire range and return a
1368/// SmallVector with elements of the vector. This is useful, for example,
1369/// when you want to iterate a range and then sort the results.
1370template <unsigned Size, typename R>
1371SmallVector<typename std::remove_const<detail::ValueOfRange<R>>::type, Size>
1372to_vector(R &&Range) {
1373 return {adl_begin(Range), adl_end(Range)};
1374}
1375
1376/// Provide a container algorithm similar to C++ Library Fundamentals v2's
1377/// `erase_if` which is equivalent to:
1378///
1379/// C.erase(remove_if(C, pred), C.end());
1380///
1381/// This version works for any container with an erase method call accepting
1382/// two iterators.
1383template <typename Container, typename UnaryPredicate>
1384void erase_if(Container &C, UnaryPredicate P) {
1385 C.erase(remove_if(C, P), C.end());
1386}
1387
1388//===----------------------------------------------------------------------===//
1389// Extra additions to <memory>
1390//===----------------------------------------------------------------------===//
1391
1392// Implement make_unique according to N3656.
1393
1394/// Constructs a `new T()` with the given args and returns a
1395/// `unique_ptr<T>` which owns the object.
1396///
1397/// Example:
1398///
1399/// auto p = make_unique<int>();
1400/// auto p = make_unique<std::tuple<int, int>>(0, 1);
1401template <class T, class... Args>
1402typename std::enable_if<!std::is_array<T>::value, std::unique_ptr<T>>::type
1403make_unique(Args &&... args) {
1404 return std::unique_ptr<T>(new T(std::forward<Args>(args)...));
4
Memory is allocated
1405}
1406
1407/// Constructs a `new T[n]` with the given args and returns a
1408/// `unique_ptr<T[]>` which owns the object.
1409///
1410/// \param n size of the new array.
1411///
1412/// Example:
1413///
1414/// auto p = make_unique<int[]>(2); // value-initializes the array with 0's.
1415template <class T>
1416typename std::enable_if<std::is_array<T>::value && std::extent<T>::value == 0,
1417 std::unique_ptr<T>>::type
1418make_unique(size_t n) {
1419 return std::unique_ptr<T>(new typename std::remove_extent<T>::type[n]());
1420}
1421
1422/// This function isn't used and is only here to provide better compile errors.
1423template <class T, class... Args>
1424typename std::enable_if<std::extent<T>::value != 0>::type
1425make_unique(Args &&...) = delete;
1426
1427struct FreeDeleter {
1428 void operator()(void* v) {
1429 ::free(v);
1430 }
1431};
1432
1433template<typename First, typename Second>
1434struct pair_hash {
1435 size_t operator()(const std::pair<First, Second> &P) const {
1436 return std::hash<First>()(P.first) * 31 + std::hash<Second>()(P.second);
1437 }
1438};
1439
1440/// A functor like C++14's std::less<void> in its absence.
1441struct less {
1442 template <typename A, typename B> bool operator()(A &&a, B &&b) const {
1443 return std::forward<A>(a) < std::forward<B>(b);
1444 }
1445};
1446
1447/// A functor like C++14's std::equal<void> in its absence.
1448struct equal {
1449 template <typename A, typename B> bool operator()(A &&a, B &&b) const {
1450 return std::forward<A>(a) == std::forward<B>(b);
1451 }
1452};
1453
1454/// Binary functor that adapts to any other binary functor after dereferencing
1455/// operands.
1456template <typename T> struct deref {
1457 T func;
1458
1459 // Could be further improved to cope with non-derivable functors and
1460 // non-binary functors (should be a variadic template member function
1461 // operator()).
1462 template <typename A, typename B>
1463 auto operator()(A &lhs, B &rhs) const -> decltype(func(*lhs, *rhs)) {
1464 assert(lhs)((lhs) ? static_cast<void> (0) : __assert_fail ("lhs", "/build/llvm-toolchain-snapshot-9~svn362543/include/llvm/ADT/STLExtras.h"
, 1464, __PRETTY_FUNCTION__))
;
1465 assert(rhs)((rhs) ? static_cast<void> (0) : __assert_fail ("rhs", "/build/llvm-toolchain-snapshot-9~svn362543/include/llvm/ADT/STLExtras.h"
, 1465, __PRETTY_FUNCTION__))
;
1466 return func(*lhs, *rhs);
1467 }
1468};
1469
1470namespace detail {
1471
1472template <typename R> class enumerator_iter;
1473
1474template <typename R> struct result_pair {
1475 friend class enumerator_iter<R>;
1476
1477 result_pair() = default;
1478 result_pair(std::size_t Index, IterOfRange<R> Iter)
1479 : Index(Index), Iter(Iter) {}
1480
1481 result_pair<R> &operator=(const result_pair<R> &Other) {
1482 Index = Other.Index;
1483 Iter = Other.Iter;
1484 return *this;
1485 }
1486
1487 std::size_t index() const { return Index; }
1488 const ValueOfRange<R> &value() const { return *Iter; }
1489 ValueOfRange<R> &value() { return *Iter; }
1490
1491private:
1492 std::size_t Index = std::numeric_limits<std::size_t>::max();
1493 IterOfRange<R> Iter;
1494};
1495
1496template <typename R>
1497class enumerator_iter
1498 : public iterator_facade_base<
1499 enumerator_iter<R>, std::forward_iterator_tag, result_pair<R>,
1500 typename std::iterator_traits<IterOfRange<R>>::difference_type,
1501 typename std::iterator_traits<IterOfRange<R>>::pointer,
1502 typename std::iterator_traits<IterOfRange<R>>::reference> {
1503 using result_type = result_pair<R>;
1504
1505public:
1506 explicit enumerator_iter(IterOfRange<R> EndIter)
1507 : Result(std::numeric_limits<size_t>::max(), EndIter) {}
1508
1509 enumerator_iter(std::size_t Index, IterOfRange<R> Iter)
1510 : Result(Index, Iter) {}
1511
1512 result_type &operator*() { return Result; }
1513 const result_type &operator*() const { return Result; }
1514
1515 enumerator_iter<R> &operator++() {
1516 assert(Result.Index != std::numeric_limits<size_t>::max())((Result.Index != std::numeric_limits<size_t>::max()) ?
static_cast<void> (0) : __assert_fail ("Result.Index != std::numeric_limits<size_t>::max()"
, "/build/llvm-toolchain-snapshot-9~svn362543/include/llvm/ADT/STLExtras.h"
, 1516, __PRETTY_FUNCTION__))
;
1517 ++Result.Iter;
1518 ++Result.Index;
1519 return *this;
1520 }
1521
1522 bool operator==(const enumerator_iter<R> &RHS) const {
1523 // Don't compare indices here, only iterators. It's possible for an end
1524 // iterator to have different indices depending on whether it was created
1525 // by calling std::end() versus incrementing a valid iterator.
1526 return Result.Iter == RHS.Result.Iter;
1527 }
1528
1529 enumerator_iter<R> &operator=(const enumerator_iter<R> &Other) {
1530 Result = Other.Result;
1531 return *this;
1532 }
1533
1534private:
1535 result_type Result;
1536};
1537
1538template <typename R> class enumerator {
1539public:
1540 explicit enumerator(R &&Range) : TheRange(std::forward<R>(Range)) {}
1541
1542 enumerator_iter<R> begin() {
1543 return enumerator_iter<R>(0, std::begin(TheRange));
1544 }
1545
1546 enumerator_iter<R> end() {
1547 return enumerator_iter<R>(std::end(TheRange));
1548 }
1549
1550private:
1551 R TheRange;
1552};
1553
1554} // end namespace detail
1555
1556/// Given an input range, returns a new range whose values are are pair (A,B)
1557/// such that A is the 0-based index of the item in the sequence, and B is
1558/// the value from the original sequence. Example:
1559///
1560/// std::vector<char> Items = {'A', 'B', 'C', 'D'};
1561/// for (auto X : enumerate(Items)) {
1562/// printf("Item %d - %c\n", X.index(), X.value());
1563/// }
1564///
1565/// Output:
1566/// Item 0 - A
1567/// Item 1 - B
1568/// Item 2 - C
1569/// Item 3 - D
1570///
1571template <typename R> detail::enumerator<R> enumerate(R &&TheRange) {
1572 return detail::enumerator<R>(std::forward<R>(TheRange));
1573}
1574
1575namespace detail {
1576
1577template <typename F, typename Tuple, std::size_t... I>
1578auto apply_tuple_impl(F &&f, Tuple &&t, index_sequence<I...>)
1579 -> decltype(std::forward<F>(f)(std::get<I>(std::forward<Tuple>(t))...)) {
1580 return std::forward<F>(f)(std::get<I>(std::forward<Tuple>(t))...);
1581}
1582
1583} // end namespace detail
1584
1585/// Given an input tuple (a1, a2, ..., an), pass the arguments of the
1586/// tuple variadically to f as if by calling f(a1, a2, ..., an) and
1587/// return the result.
1588template <typename F, typename Tuple>
1589auto apply_tuple(F &&f, Tuple &&t) -> decltype(detail::apply_tuple_impl(
1590 std::forward<F>(f), std::forward<Tuple>(t),
1591 build_index_impl<
1592 std::tuple_size<typename std::decay<Tuple>::type>::value>{})) {
1593 using Indices = build_index_impl<
1594 std::tuple_size<typename std::decay<Tuple>::type>::value>;
1595
1596 return detail::apply_tuple_impl(std::forward<F>(f), std::forward<Tuple>(t),
1597 Indices{});
1598}
1599
1600/// Return true if the sequence [Begin, End) has exactly N items. Runs in O(N)
1601/// time. Not meant for use with random-access iterators.
1602template <typename IterTy>
1603bool hasNItems(
1604 IterTy &&Begin, IterTy &&End, unsigned N,
1605 typename std::enable_if<
1606 !std::is_same<
1607 typename std::iterator_traits<typename std::remove_reference<
1608 decltype(Begin)>::type>::iterator_category,
1609 std::random_access_iterator_tag>::value,
1610 void>::type * = nullptr) {
1611 for (; N; --N, ++Begin)
1612 if (Begin == End)
1613 return false; // Too few.
1614 return Begin == End;
1615}
1616
1617/// Return true if the sequence [Begin, End) has N or more items. Runs in O(N)
1618/// time. Not meant for use with random-access iterators.
1619template <typename IterTy>
1620bool hasNItemsOrMore(
1621 IterTy &&Begin, IterTy &&End, unsigned N,
1622 typename std::enable_if<
1623 !std::is_same<
1624 typename std::iterator_traits<typename std::remove_reference<
1625 decltype(Begin)>::type>::iterator_category,
1626 std::random_access_iterator_tag>::value,
1627 void>::type * = nullptr) {
1628 for (; N; --N, ++Begin)
1629 if (Begin == End)
1630 return false; // Too few.
1631 return true;
1632}
1633
1634/// Returns a raw pointer that represents the same address as the argument.
1635///
1636/// The late bound return should be removed once we move to C++14 to better
1637/// align with the C++20 declaration. Also, this implementation can be removed
1638/// once we move to C++20 where it's defined as std::to_addres()
1639///
1640/// The std::pointer_traits<>::to_address(p) variations of these overloads has
1641/// not been implemented.
1642template <class Ptr> auto to_address(const Ptr &P) -> decltype(P.operator->()) {
1643 return P.operator->();
1644}
1645template <class T> constexpr T *to_address(T *P) { return P; }
1646
1647} // end namespace llvm
1648
1649#endif // LLVM_ADT_STLEXTRAS_H