[PM/AA] Hoist the interface to TBAA into a dedicated header along with
[oota-llvm.git] / lib / CodeGen / Passes.cpp
1 //===-- Passes.cpp - Target independent code generation passes ------------===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This file defines interfaces to access the target independent code
11 // generation passes provided by the LLVM backend.
12 //
13 //===---------------------------------------------------------------------===//
14
15 #include "llvm/CodeGen/Passes.h"
16 #include "llvm/Analysis/BasicAliasAnalysis.h"
17 #include "llvm/Analysis/CFLAliasAnalysis.h"
18 #include "llvm/Analysis/Passes.h"
19 #include "llvm/Analysis/ScopedNoAliasAA.h"
20 #include "llvm/Analysis/TypeBasedAliasAnalysis.h"
21 #include "llvm/CodeGen/MachineFunctionPass.h"
22 #include "llvm/CodeGen/RegAllocRegistry.h"
23 #include "llvm/IR/IRPrintingPasses.h"
24 #include "llvm/IR/LegacyPassManager.h"
25 #include "llvm/IR/Verifier.h"
26 #include "llvm/MC/MCAsmInfo.h"
27 #include "llvm/Support/CommandLine.h"
28 #include "llvm/Support/Debug.h"
29 #include "llvm/Support/ErrorHandling.h"
30 #include "llvm/Support/raw_ostream.h"
31 #include "llvm/Transforms/Instrumentation.h"
32 #include "llvm/Transforms/Scalar.h"
33 #include "llvm/Transforms/Utils/SymbolRewriter.h"
34
35 using namespace llvm;
36
37 static cl::opt<bool> DisablePostRA("disable-post-ra", cl::Hidden,
38     cl::desc("Disable Post Regalloc"));
39 static cl::opt<bool> DisableBranchFold("disable-branch-fold", cl::Hidden,
40     cl::desc("Disable branch folding"));
41 static cl::opt<bool> DisableTailDuplicate("disable-tail-duplicate", cl::Hidden,
42     cl::desc("Disable tail duplication"));
43 static cl::opt<bool> DisableEarlyTailDup("disable-early-taildup", cl::Hidden,
44     cl::desc("Disable pre-register allocation tail duplication"));
45 static cl::opt<bool> DisableBlockPlacement("disable-block-placement",
46     cl::Hidden, cl::desc("Disable probability-driven block placement"));
47 static cl::opt<bool> EnableBlockPlacementStats("enable-block-placement-stats",
48     cl::Hidden, cl::desc("Collect probability-driven block placement stats"));
49 static cl::opt<bool> DisableSSC("disable-ssc", cl::Hidden,
50     cl::desc("Disable Stack Slot Coloring"));
51 static cl::opt<bool> DisableMachineDCE("disable-machine-dce", cl::Hidden,
52     cl::desc("Disable Machine Dead Code Elimination"));
53 static cl::opt<bool> DisableEarlyIfConversion("disable-early-ifcvt", cl::Hidden,
54     cl::desc("Disable Early If-conversion"));
55 static cl::opt<bool> DisableMachineLICM("disable-machine-licm", cl::Hidden,
56     cl::desc("Disable Machine LICM"));
57 static cl::opt<bool> DisableMachineCSE("disable-machine-cse", cl::Hidden,
58     cl::desc("Disable Machine Common Subexpression Elimination"));
59 static cl::opt<cl::boolOrDefault> OptimizeRegAlloc(
60     "optimize-regalloc", cl::Hidden,
61     cl::desc("Enable optimized register allocation compilation path."));
62 static cl::opt<bool> DisablePostRAMachineLICM("disable-postra-machine-licm",
63     cl::Hidden,
64     cl::desc("Disable Machine LICM"));
65 static cl::opt<bool> DisableMachineSink("disable-machine-sink", cl::Hidden,
66     cl::desc("Disable Machine Sinking"));
67 static cl::opt<bool> DisableLSR("disable-lsr", cl::Hidden,
68     cl::desc("Disable Loop Strength Reduction Pass"));
69 static cl::opt<bool> DisableConstantHoisting("disable-constant-hoisting",
70     cl::Hidden, cl::desc("Disable ConstantHoisting"));
71 static cl::opt<bool> DisableCGP("disable-cgp", cl::Hidden,
72     cl::desc("Disable Codegen Prepare"));
73 static cl::opt<bool> DisableCopyProp("disable-copyprop", cl::Hidden,
74     cl::desc("Disable Copy Propagation pass"));
75 static cl::opt<bool> DisablePartialLibcallInlining("disable-partial-libcall-inlining",
76     cl::Hidden, cl::desc("Disable Partial Libcall Inlining"));
77 static cl::opt<bool> EnableImplicitNullChecks(
78     "enable-implicit-null-checks",
79     cl::desc("Fold null checks into faulting memory operations"),
80     cl::init(false));
81 static cl::opt<bool> PrintLSR("print-lsr-output", cl::Hidden,
82     cl::desc("Print LLVM IR produced by the loop-reduce pass"));
83 static cl::opt<bool> PrintISelInput("print-isel-input", cl::Hidden,
84     cl::desc("Print LLVM IR input to isel pass"));
85 static cl::opt<bool> PrintGCInfo("print-gc", cl::Hidden,
86     cl::desc("Dump garbage collector data"));
87 static cl::opt<bool> VerifyMachineCode("verify-machineinstrs", cl::Hidden,
88     cl::desc("Verify generated machine code"),
89     cl::init(false),
90     cl::ZeroOrMore);
91
92 static cl::opt<std::string>
93 PrintMachineInstrs("print-machineinstrs", cl::ValueOptional,
94                    cl::desc("Print machine instrs"),
95                    cl::value_desc("pass-name"), cl::init("option-unspecified"));
96
97 // Temporary option to allow experimenting with MachineScheduler as a post-RA
98 // scheduler. Targets can "properly" enable this with
99 // substitutePass(&PostRASchedulerID, &PostMachineSchedulerID); Ideally it
100 // wouldn't be part of the standard pass pipeline, and the target would just add
101 // a PostRA scheduling pass wherever it wants.
102 static cl::opt<bool> MISchedPostRA("misched-postra", cl::Hidden,
103   cl::desc("Run MachineScheduler post regalloc (independent of preRA sched)"));
104
105 // Experimental option to run live interval analysis early.
106 static cl::opt<bool> EarlyLiveIntervals("early-live-intervals", cl::Hidden,
107     cl::desc("Run live interval analysis earlier in the pipeline"));
108
109 static cl::opt<bool> UseCFLAA("use-cfl-aa-in-codegen",
110   cl::init(false), cl::Hidden,
111   cl::desc("Enable the new, experimental CFL alias analysis in CodeGen"));
112
113 /// Allow standard passes to be disabled by command line options. This supports
114 /// simple binary flags that either suppress the pass or do nothing.
115 /// i.e. -disable-mypass=false has no effect.
116 /// These should be converted to boolOrDefault in order to use applyOverride.
117 static IdentifyingPassPtr applyDisable(IdentifyingPassPtr PassID,
118                                        bool Override) {
119   if (Override)
120     return IdentifyingPassPtr();
121   return PassID;
122 }
123
124 /// Allow standard passes to be disabled by the command line, regardless of who
125 /// is adding the pass.
126 ///
127 /// StandardID is the pass identified in the standard pass pipeline and provided
128 /// to addPass(). It may be a target-specific ID in the case that the target
129 /// directly adds its own pass, but in that case we harmlessly fall through.
130 ///
131 /// TargetID is the pass that the target has configured to override StandardID.
132 ///
133 /// StandardID may be a pseudo ID. In that case TargetID is the name of the real
134 /// pass to run. This allows multiple options to control a single pass depending
135 /// on where in the pipeline that pass is added.
136 static IdentifyingPassPtr overridePass(AnalysisID StandardID,
137                                        IdentifyingPassPtr TargetID) {
138   if (StandardID == &PostRASchedulerID)
139     return applyDisable(TargetID, DisablePostRA);
140
141   if (StandardID == &BranchFolderPassID)
142     return applyDisable(TargetID, DisableBranchFold);
143
144   if (StandardID == &TailDuplicateID)
145     return applyDisable(TargetID, DisableTailDuplicate);
146
147   if (StandardID == &TargetPassConfig::EarlyTailDuplicateID)
148     return applyDisable(TargetID, DisableEarlyTailDup);
149
150   if (StandardID == &MachineBlockPlacementID)
151     return applyDisable(TargetID, DisableBlockPlacement);
152
153   if (StandardID == &StackSlotColoringID)
154     return applyDisable(TargetID, DisableSSC);
155
156   if (StandardID == &DeadMachineInstructionElimID)
157     return applyDisable(TargetID, DisableMachineDCE);
158
159   if (StandardID == &EarlyIfConverterID)
160     return applyDisable(TargetID, DisableEarlyIfConversion);
161
162   if (StandardID == &MachineLICMID)
163     return applyDisable(TargetID, DisableMachineLICM);
164
165   if (StandardID == &MachineCSEID)
166     return applyDisable(TargetID, DisableMachineCSE);
167
168   if (StandardID == &TargetPassConfig::PostRAMachineLICMID)
169     return applyDisable(TargetID, DisablePostRAMachineLICM);
170
171   if (StandardID == &MachineSinkingID)
172     return applyDisable(TargetID, DisableMachineSink);
173
174   if (StandardID == &MachineCopyPropagationID)
175     return applyDisable(TargetID, DisableCopyProp);
176
177   return TargetID;
178 }
179
180 //===---------------------------------------------------------------------===//
181 /// TargetPassConfig
182 //===---------------------------------------------------------------------===//
183
184 INITIALIZE_PASS(TargetPassConfig, "targetpassconfig",
185                 "Target Pass Configuration", false, false)
186 char TargetPassConfig::ID = 0;
187
188 // Pseudo Pass IDs.
189 char TargetPassConfig::EarlyTailDuplicateID = 0;
190 char TargetPassConfig::PostRAMachineLICMID = 0;
191
192 namespace llvm {
193 class PassConfigImpl {
194 public:
195   // List of passes explicitly substituted by this target. Normally this is
196   // empty, but it is a convenient way to suppress or replace specific passes
197   // that are part of a standard pass pipeline without overridding the entire
198   // pipeline. This mechanism allows target options to inherit a standard pass's
199   // user interface. For example, a target may disable a standard pass by
200   // default by substituting a pass ID of zero, and the user may still enable
201   // that standard pass with an explicit command line option.
202   DenseMap<AnalysisID,IdentifyingPassPtr> TargetPasses;
203
204   /// Store the pairs of <AnalysisID, AnalysisID> of which the second pass
205   /// is inserted after each instance of the first one.
206   SmallVector<std::pair<AnalysisID, IdentifyingPassPtr>, 4> InsertedPasses;
207 };
208 } // namespace llvm
209
210 // Out of line virtual method.
211 TargetPassConfig::~TargetPassConfig() {
212   delete Impl;
213 }
214
215 // Out of line constructor provides default values for pass options and
216 // registers all common codegen passes.
217 TargetPassConfig::TargetPassConfig(TargetMachine *tm, PassManagerBase &pm)
218     : ImmutablePass(ID), PM(&pm), StartBefore(nullptr), StartAfter(nullptr),
219       StopAfter(nullptr), Started(true), Stopped(false),
220       AddingMachinePasses(false), TM(tm), Impl(nullptr), Initialized(false),
221       DisableVerify(false), EnableTailMerge(true) {
222
223   Impl = new PassConfigImpl();
224
225   // Register all target independent codegen passes to activate their PassIDs,
226   // including this pass itself.
227   initializeCodeGen(*PassRegistry::getPassRegistry());
228
229   // Substitute Pseudo Pass IDs for real ones.
230   substitutePass(&EarlyTailDuplicateID, &TailDuplicateID);
231   substitutePass(&PostRAMachineLICMID, &MachineLICMID);
232 }
233
234 /// Insert InsertedPassID pass after TargetPassID.
235 void TargetPassConfig::insertPass(AnalysisID TargetPassID,
236                                   IdentifyingPassPtr InsertedPassID) {
237   assert(((!InsertedPassID.isInstance() &&
238            TargetPassID != InsertedPassID.getID()) ||
239           (InsertedPassID.isInstance() &&
240            TargetPassID != InsertedPassID.getInstance()->getPassID())) &&
241          "Insert a pass after itself!");
242   std::pair<AnalysisID, IdentifyingPassPtr> P(TargetPassID, InsertedPassID);
243   Impl->InsertedPasses.push_back(P);
244 }
245
246 /// createPassConfig - Create a pass configuration object to be used by
247 /// addPassToEmitX methods for generating a pipeline of CodeGen passes.
248 ///
249 /// Targets may override this to extend TargetPassConfig.
250 TargetPassConfig *LLVMTargetMachine::createPassConfig(PassManagerBase &PM) {
251   return new TargetPassConfig(this, PM);
252 }
253
254 TargetPassConfig::TargetPassConfig()
255   : ImmutablePass(ID), PM(nullptr) {
256   llvm_unreachable("TargetPassConfig should not be constructed on-the-fly");
257 }
258
259 // Helper to verify the analysis is really immutable.
260 void TargetPassConfig::setOpt(bool &Opt, bool Val) {
261   assert(!Initialized && "PassConfig is immutable");
262   Opt = Val;
263 }
264
265 void TargetPassConfig::substitutePass(AnalysisID StandardID,
266                                       IdentifyingPassPtr TargetID) {
267   Impl->TargetPasses[StandardID] = TargetID;
268 }
269
270 IdentifyingPassPtr TargetPassConfig::getPassSubstitution(AnalysisID ID) const {
271   DenseMap<AnalysisID, IdentifyingPassPtr>::const_iterator
272     I = Impl->TargetPasses.find(ID);
273   if (I == Impl->TargetPasses.end())
274     return ID;
275   return I->second;
276 }
277
278 /// Add a pass to the PassManager if that pass is supposed to be run.  If the
279 /// Started/Stopped flags indicate either that the compilation should start at
280 /// a later pass or that it should stop after an earlier pass, then do not add
281 /// the pass.  Finally, compare the current pass against the StartAfter
282 /// and StopAfter options and change the Started/Stopped flags accordingly.
283 void TargetPassConfig::addPass(Pass *P, bool verifyAfter, bool printAfter) {
284   assert(!Initialized && "PassConfig is immutable");
285
286   // Cache the Pass ID here in case the pass manager finds this pass is
287   // redundant with ones already scheduled / available, and deletes it.
288   // Fundamentally, once we add the pass to the manager, we no longer own it
289   // and shouldn't reference it.
290   AnalysisID PassID = P->getPassID();
291
292   if (StartBefore == PassID)
293     Started = true;
294   if (Started && !Stopped) {
295     std::string Banner;
296     // Construct banner message before PM->add() as that may delete the pass.
297     if (AddingMachinePasses && (printAfter || verifyAfter))
298       Banner = std::string("After ") + std::string(P->getPassName());
299     PM->add(P);
300     if (AddingMachinePasses) {
301       if (printAfter)
302         addPrintPass(Banner);
303       if (verifyAfter)
304         addVerifyPass(Banner);
305     }
306
307     // Add the passes after the pass P if there is any.
308     for (SmallVectorImpl<std::pair<AnalysisID, IdentifyingPassPtr> >::iterator
309              I = Impl->InsertedPasses.begin(),
310              E = Impl->InsertedPasses.end();
311          I != E; ++I) {
312       if ((*I).first == PassID) {
313         assert((*I).second.isValid() && "Illegal Pass ID!");
314         Pass *NP;
315         if ((*I).second.isInstance())
316           NP = (*I).second.getInstance();
317         else {
318           NP = Pass::createPass((*I).second.getID());
319           assert(NP && "Pass ID not registered");
320         }
321         addPass(NP, false, false);
322       }
323     }
324   } else {
325     delete P;
326   }
327   if (StopAfter == PassID)
328     Stopped = true;
329   if (StartAfter == PassID)
330     Started = true;
331   if (Stopped && !Started)
332     report_fatal_error("Cannot stop compilation after pass that is not run");
333 }
334
335 /// Add a CodeGen pass at this point in the pipeline after checking for target
336 /// and command line overrides.
337 ///
338 /// addPass cannot return a pointer to the pass instance because is internal the
339 /// PassManager and the instance we create here may already be freed.
340 AnalysisID TargetPassConfig::addPass(AnalysisID PassID, bool verifyAfter,
341                                      bool printAfter) {
342   IdentifyingPassPtr TargetID = getPassSubstitution(PassID);
343   IdentifyingPassPtr FinalPtr = overridePass(PassID, TargetID);
344   if (!FinalPtr.isValid())
345     return nullptr;
346
347   Pass *P;
348   if (FinalPtr.isInstance())
349     P = FinalPtr.getInstance();
350   else {
351     P = Pass::createPass(FinalPtr.getID());
352     if (!P)
353       llvm_unreachable("Pass ID not registered");
354   }
355   AnalysisID FinalID = P->getPassID();
356   addPass(P, verifyAfter, printAfter); // Ends the lifetime of P.
357
358   return FinalID;
359 }
360
361 void TargetPassConfig::printAndVerify(const std::string &Banner) {
362   addPrintPass(Banner);
363   addVerifyPass(Banner);
364 }
365
366 void TargetPassConfig::addPrintPass(const std::string &Banner) {
367   if (TM->shouldPrintMachineCode())
368     PM->add(createMachineFunctionPrinterPass(dbgs(), Banner));
369 }
370
371 void TargetPassConfig::addVerifyPass(const std::string &Banner) {
372   if (VerifyMachineCode)
373     PM->add(createMachineVerifierPass(Banner));
374 }
375
376 /// Add common target configurable passes that perform LLVM IR to IR transforms
377 /// following machine independent optimization.
378 void TargetPassConfig::addIRPasses() {
379   // Basic AliasAnalysis support.
380   // Add TypeBasedAliasAnalysis before BasicAliasAnalysis so that
381   // BasicAliasAnalysis wins if they disagree. This is intended to help
382   // support "obvious" type-punning idioms.
383   if (UseCFLAA)
384     addPass(createCFLAliasAnalysisPass());
385   addPass(createTypeBasedAliasAnalysisPass());
386   addPass(createScopedNoAliasAAPass());
387   addPass(createBasicAliasAnalysisPass());
388
389   // Before running any passes, run the verifier to determine if the input
390   // coming from the front-end and/or optimizer is valid.
391   if (!DisableVerify)
392     addPass(createVerifierPass());
393
394   // Run loop strength reduction before anything else.
395   if (getOptLevel() != CodeGenOpt::None && !DisableLSR) {
396     addPass(createLoopStrengthReducePass());
397     if (PrintLSR)
398       addPass(createPrintFunctionPass(dbgs(), "\n\n*** Code after LSR ***\n"));
399   }
400
401   // Run GC lowering passes for builtin collectors
402   // TODO: add a pass insertion point here
403   addPass(createGCLoweringPass());
404   addPass(createShadowStackGCLoweringPass());
405
406   // Make sure that no unreachable blocks are instruction selected.
407   addPass(createUnreachableBlockEliminationPass());
408
409   // Prepare expensive constants for SelectionDAG.
410   if (getOptLevel() != CodeGenOpt::None && !DisableConstantHoisting)
411     addPass(createConstantHoistingPass());
412
413   if (getOptLevel() != CodeGenOpt::None && !DisablePartialLibcallInlining)
414     addPass(createPartiallyInlineLibCallsPass());
415 }
416
417 /// Turn exception handling constructs into something the code generators can
418 /// handle.
419 void TargetPassConfig::addPassesToHandleExceptions() {
420   switch (TM->getMCAsmInfo()->getExceptionHandlingType()) {
421   case ExceptionHandling::SjLj:
422     // SjLj piggy-backs on dwarf for this bit. The cleanups done apply to both
423     // Dwarf EH prepare needs to be run after SjLj prepare. Otherwise,
424     // catch info can get misplaced when a selector ends up more than one block
425     // removed from the parent invoke(s). This could happen when a landing
426     // pad is shared by multiple invokes and is also a target of a normal
427     // edge from elsewhere.
428     addPass(createSjLjEHPreparePass());
429     // FALLTHROUGH
430   case ExceptionHandling::DwarfCFI:
431   case ExceptionHandling::ARM:
432     addPass(createDwarfEHPass(TM));
433     break;
434   case ExceptionHandling::WinEH:
435     // We support using both GCC-style and MSVC-style exceptions on Windows, so
436     // add both preparation passes. Each pass will only actually run if it
437     // recognizes the personality function.
438     addPass(createWinEHPass(TM));
439     addPass(createDwarfEHPass(TM));
440     break;
441   case ExceptionHandling::None:
442     addPass(createLowerInvokePass());
443
444     // The lower invoke pass may create unreachable code. Remove it.
445     addPass(createUnreachableBlockEliminationPass());
446     break;
447   }
448 }
449
450 /// Add pass to prepare the LLVM IR for code generation. This should be done
451 /// before exception handling preparation passes.
452 void TargetPassConfig::addCodeGenPrepare() {
453   if (getOptLevel() != CodeGenOpt::None && !DisableCGP)
454     addPass(createCodeGenPreparePass(TM));
455   addPass(createRewriteSymbolsPass());
456 }
457
458 /// Add common passes that perform LLVM IR to IR transforms in preparation for
459 /// instruction selection.
460 void TargetPassConfig::addISelPrepare() {
461   addPreISel();
462
463   // Add both the safe stack and the stack protection passes: each of them will
464   // only protect functions that have corresponding attributes.
465   addPass(createSafeStackPass());
466   addPass(createStackProtectorPass(TM));
467
468   if (PrintISelInput)
469     addPass(createPrintFunctionPass(
470         dbgs(), "\n\n*** Final LLVM Code input to ISel ***\n"));
471
472   // All passes which modify the LLVM IR are now complete; run the verifier
473   // to ensure that the IR is valid.
474   if (!DisableVerify)
475     addPass(createVerifierPass());
476 }
477
478 /// Add the complete set of target-independent postISel code generator passes.
479 ///
480 /// This can be read as the standard order of major LLVM CodeGen stages. Stages
481 /// with nontrivial configuration or multiple passes are broken out below in
482 /// add%Stage routines.
483 ///
484 /// Any TargetPassConfig::addXX routine may be overriden by the Target. The
485 /// addPre/Post methods with empty header implementations allow injecting
486 /// target-specific fixups just before or after major stages. Additionally,
487 /// targets have the flexibility to change pass order within a stage by
488 /// overriding default implementation of add%Stage routines below. Each
489 /// technique has maintainability tradeoffs because alternate pass orders are
490 /// not well supported. addPre/Post works better if the target pass is easily
491 /// tied to a common pass. But if it has subtle dependencies on multiple passes,
492 /// the target should override the stage instead.
493 ///
494 /// TODO: We could use a single addPre/Post(ID) hook to allow pass injection
495 /// before/after any target-independent pass. But it's currently overkill.
496 void TargetPassConfig::addMachinePasses() {
497   AddingMachinePasses = true;
498
499   // Insert a machine instr printer pass after the specified pass.
500   // If -print-machineinstrs specified, print machineinstrs after all passes.
501   if (StringRef(PrintMachineInstrs.getValue()).equals(""))
502     TM->Options.PrintMachineCode = true;
503   else if (!StringRef(PrintMachineInstrs.getValue())
504            .equals("option-unspecified")) {
505     const PassRegistry *PR = PassRegistry::getPassRegistry();
506     const PassInfo *TPI = PR->getPassInfo(PrintMachineInstrs.getValue());
507     const PassInfo *IPI = PR->getPassInfo(StringRef("machineinstr-printer"));
508     assert (TPI && IPI && "Pass ID not registered!");
509     const char *TID = (const char *)(TPI->getTypeInfo());
510     const char *IID = (const char *)(IPI->getTypeInfo());
511     insertPass(TID, IID);
512   }
513
514   // Print the instruction selected machine code...
515   printAndVerify("After Instruction Selection");
516
517   // Expand pseudo-instructions emitted by ISel.
518   addPass(&ExpandISelPseudosID);
519
520   // Add passes that optimize machine instructions in SSA form.
521   if (getOptLevel() != CodeGenOpt::None) {
522     addMachineSSAOptimization();
523   } else {
524     // If the target requests it, assign local variables to stack slots relative
525     // to one another and simplify frame index references where possible.
526     addPass(&LocalStackSlotAllocationID, false);
527   }
528
529   // Run pre-ra passes.
530   addPreRegAlloc();
531
532   // Run register allocation and passes that are tightly coupled with it,
533   // including phi elimination and scheduling.
534   if (getOptimizeRegAlloc())
535     addOptimizedRegAlloc(createRegAllocPass(true));
536   else
537     addFastRegAlloc(createRegAllocPass(false));
538
539   // Run post-ra passes.
540   addPostRegAlloc();
541
542   // Insert prolog/epilog code.  Eliminate abstract frame index references...
543   if (getOptLevel() != CodeGenOpt::None)
544     addPass(createShrinkWrapPass());
545   addPass(&PrologEpilogCodeInserterID);
546
547   /// Add passes that optimize machine instructions after register allocation.
548   if (getOptLevel() != CodeGenOpt::None)
549     addMachineLateOptimization();
550
551   // Expand pseudo instructions before second scheduling pass.
552   addPass(&ExpandPostRAPseudosID);
553
554   // Run pre-sched2 passes.
555   addPreSched2();
556
557   if (EnableImplicitNullChecks)
558     addPass(&ImplicitNullChecksID);
559
560   // Second pass scheduler.
561   if (getOptLevel() != CodeGenOpt::None) {
562     if (MISchedPostRA)
563       addPass(&PostMachineSchedulerID);
564     else
565       addPass(&PostRASchedulerID);
566   }
567
568   // GC
569   if (addGCPasses()) {
570     if (PrintGCInfo)
571       addPass(createGCInfoPrinter(dbgs()), false, false);
572   }
573
574   // Basic block placement.
575   if (getOptLevel() != CodeGenOpt::None)
576     addBlockPlacement();
577
578   addPreEmitPass();
579
580   addPass(&StackMapLivenessID, false);
581
582   AddingMachinePasses = false;
583 }
584
585 /// Add passes that optimize machine instructions in SSA form.
586 void TargetPassConfig::addMachineSSAOptimization() {
587   // Pre-ra tail duplication.
588   addPass(&EarlyTailDuplicateID);
589
590   // Optimize PHIs before DCE: removing dead PHI cycles may make more
591   // instructions dead.
592   addPass(&OptimizePHIsID, false);
593
594   // This pass merges large allocas. StackSlotColoring is a different pass
595   // which merges spill slots.
596   addPass(&StackColoringID, false);
597
598   // If the target requests it, assign local variables to stack slots relative
599   // to one another and simplify frame index references where possible.
600   addPass(&LocalStackSlotAllocationID, false);
601
602   // With optimization, dead code should already be eliminated. However
603   // there is one known exception: lowered code for arguments that are only
604   // used by tail calls, where the tail calls reuse the incoming stack
605   // arguments directly (see t11 in test/CodeGen/X86/sibcall.ll).
606   addPass(&DeadMachineInstructionElimID);
607
608   // Allow targets to insert passes that improve instruction level parallelism,
609   // like if-conversion. Such passes will typically need dominator trees and
610   // loop info, just like LICM and CSE below.
611   addILPOpts();
612
613   addPass(&MachineLICMID, false);
614   addPass(&MachineCSEID, false);
615   addPass(&MachineSinkingID);
616
617   addPass(&PeepholeOptimizerID, false);
618   // Clean-up the dead code that may have been generated by peephole
619   // rewriting.
620   addPass(&DeadMachineInstructionElimID);
621 }
622
623 //===---------------------------------------------------------------------===//
624 /// Register Allocation Pass Configuration
625 //===---------------------------------------------------------------------===//
626
627 bool TargetPassConfig::getOptimizeRegAlloc() const {
628   switch (OptimizeRegAlloc) {
629   case cl::BOU_UNSET: return getOptLevel() != CodeGenOpt::None;
630   case cl::BOU_TRUE:  return true;
631   case cl::BOU_FALSE: return false;
632   }
633   llvm_unreachable("Invalid optimize-regalloc state");
634 }
635
636 /// RegisterRegAlloc's global Registry tracks allocator registration.
637 MachinePassRegistry RegisterRegAlloc::Registry;
638
639 /// A dummy default pass factory indicates whether the register allocator is
640 /// overridden on the command line.
641 static FunctionPass *useDefaultRegisterAllocator() { return nullptr; }
642 static RegisterRegAlloc
643 defaultRegAlloc("default",
644                 "pick register allocator based on -O option",
645                 useDefaultRegisterAllocator);
646
647 /// -regalloc=... command line option.
648 static cl::opt<RegisterRegAlloc::FunctionPassCtor, false,
649                RegisterPassParser<RegisterRegAlloc> >
650 RegAlloc("regalloc",
651          cl::init(&useDefaultRegisterAllocator),
652          cl::desc("Register allocator to use"));
653
654
655 /// Instantiate the default register allocator pass for this target for either
656 /// the optimized or unoptimized allocation path. This will be added to the pass
657 /// manager by addFastRegAlloc in the unoptimized case or addOptimizedRegAlloc
658 /// in the optimized case.
659 ///
660 /// A target that uses the standard regalloc pass order for fast or optimized
661 /// allocation may still override this for per-target regalloc
662 /// selection. But -regalloc=... always takes precedence.
663 FunctionPass *TargetPassConfig::createTargetRegisterAllocator(bool Optimized) {
664   if (Optimized)
665     return createGreedyRegisterAllocator();
666   else
667     return createFastRegisterAllocator();
668 }
669
670 /// Find and instantiate the register allocation pass requested by this target
671 /// at the current optimization level.  Different register allocators are
672 /// defined as separate passes because they may require different analysis.
673 ///
674 /// This helper ensures that the regalloc= option is always available,
675 /// even for targets that override the default allocator.
676 ///
677 /// FIXME: When MachinePassRegistry register pass IDs instead of function ptrs,
678 /// this can be folded into addPass.
679 FunctionPass *TargetPassConfig::createRegAllocPass(bool Optimized) {
680   RegisterRegAlloc::FunctionPassCtor Ctor = RegisterRegAlloc::getDefault();
681
682   // Initialize the global default.
683   if (!Ctor) {
684     Ctor = RegAlloc;
685     RegisterRegAlloc::setDefault(RegAlloc);
686   }
687   if (Ctor != useDefaultRegisterAllocator)
688     return Ctor();
689
690   // With no -regalloc= override, ask the target for a regalloc pass.
691   return createTargetRegisterAllocator(Optimized);
692 }
693
694 /// Return true if the default global register allocator is in use and
695 /// has not be overriden on the command line with '-regalloc=...'
696 bool TargetPassConfig::usingDefaultRegAlloc() const {
697   return RegAlloc.getNumOccurrences() == 0;
698 }
699
700 /// Add the minimum set of target-independent passes that are required for
701 /// register allocation. No coalescing or scheduling.
702 void TargetPassConfig::addFastRegAlloc(FunctionPass *RegAllocPass) {
703   addPass(&PHIEliminationID, false);
704   addPass(&TwoAddressInstructionPassID, false);
705
706   addPass(RegAllocPass);
707 }
708
709 /// Add standard target-independent passes that are tightly coupled with
710 /// optimized register allocation, including coalescing, machine instruction
711 /// scheduling, and register allocation itself.
712 void TargetPassConfig::addOptimizedRegAlloc(FunctionPass *RegAllocPass) {
713   addPass(&ProcessImplicitDefsID, false);
714
715   // LiveVariables currently requires pure SSA form.
716   //
717   // FIXME: Once TwoAddressInstruction pass no longer uses kill flags,
718   // LiveVariables can be removed completely, and LiveIntervals can be directly
719   // computed. (We still either need to regenerate kill flags after regalloc, or
720   // preferably fix the scavenger to not depend on them).
721   addPass(&LiveVariablesID, false);
722
723   // Edge splitting is smarter with machine loop info.
724   addPass(&MachineLoopInfoID, false);
725   addPass(&PHIEliminationID, false);
726
727   // Eventually, we want to run LiveIntervals before PHI elimination.
728   if (EarlyLiveIntervals)
729     addPass(&LiveIntervalsID, false);
730
731   addPass(&TwoAddressInstructionPassID, false);
732   addPass(&RegisterCoalescerID);
733
734   // PreRA instruction scheduling.
735   addPass(&MachineSchedulerID);
736
737   // Add the selected register allocation pass.
738   addPass(RegAllocPass);
739
740   // Allow targets to change the register assignments before rewriting.
741   addPreRewrite();
742
743   // Finally rewrite virtual registers.
744   addPass(&VirtRegRewriterID);
745
746   // Perform stack slot coloring and post-ra machine LICM.
747   //
748   // FIXME: Re-enable coloring with register when it's capable of adding
749   // kill markers.
750   addPass(&StackSlotColoringID);
751
752   // Run post-ra machine LICM to hoist reloads / remats.
753   //
754   // FIXME: can this move into MachineLateOptimization?
755   addPass(&PostRAMachineLICMID);
756 }
757
758 //===---------------------------------------------------------------------===//
759 /// Post RegAlloc Pass Configuration
760 //===---------------------------------------------------------------------===//
761
762 /// Add passes that optimize machine instructions after register allocation.
763 void TargetPassConfig::addMachineLateOptimization() {
764   // Branch folding must be run after regalloc and prolog/epilog insertion.
765   addPass(&BranchFolderPassID);
766
767   // Tail duplication.
768   // Note that duplicating tail just increases code size and degrades
769   // performance for targets that require Structured Control Flow.
770   // In addition it can also make CFG irreducible. Thus we disable it.
771   if (!TM->requiresStructuredCFG())
772     addPass(&TailDuplicateID);
773
774   // Copy propagation.
775   addPass(&MachineCopyPropagationID);
776 }
777
778 /// Add standard GC passes.
779 bool TargetPassConfig::addGCPasses() {
780   addPass(&GCMachineCodeAnalysisID, false);
781   return true;
782 }
783
784 /// Add standard basic block placement passes.
785 void TargetPassConfig::addBlockPlacement() {
786   if (addPass(&MachineBlockPlacementID, false)) {
787     // Run a separate pass to collect block placement statistics.
788     if (EnableBlockPlacementStats)
789       addPass(&MachineBlockPlacementStatsID);
790   }
791 }