blob: 9693780bdaa07f278cdb53b9f183630b38726971 [file] [log] [blame]
Chris Lattneraa4c91f2003-12-28 07:59:53 +00001//===-- Passes.cpp - Target independent code generation passes ------------===//
Misha Brukmanedf128a2005-04-21 22:36:52 +00002//
John Criswellb576c942003-10-20 19:43:21 +00003// The LLVM Compiler Infrastructure
4//
Chris Lattner4ee451d2007-12-29 20:36:04 +00005// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
Misha Brukmanedf128a2005-04-21 22:36:52 +00007//
John Criswellb576c942003-10-20 19:43:21 +00008//===----------------------------------------------------------------------===//
Alkis Evlogimenos7237ece2003-10-02 16:57:49 +00009//
10// This file defines interfaces to access the target independent code
11// generation passes provided by the LLVM backend.
12//
13//===---------------------------------------------------------------------===//
14
Andrew Trickd5422652012-02-04 02:56:48 +000015#include "llvm/Analysis/Passes.h"
16#include "llvm/Analysis/Verifier.h"
17#include "llvm/Transforms/Scalar.h"
18#include "llvm/PassManager.h"
19#include "llvm/CodeGen/GCStrategy.h"
Andrew Trickd5422652012-02-04 02:56:48 +000020#include "llvm/CodeGen/MachineFunctionPass.h"
Alkis Evlogimenos7237ece2003-10-02 16:57:49 +000021#include "llvm/CodeGen/Passes.h"
Andrew Trickd5422652012-02-04 02:56:48 +000022#include "llvm/CodeGen/RegAllocRegistry.h"
23#include "llvm/Target/TargetLowering.h"
Andrew Trickd5422652012-02-04 02:56:48 +000024#include "llvm/Target/TargetOptions.h"
Bob Wilson564fbf62012-07-02 19:48:31 +000025#include "llvm/MC/MCAsmInfo.h"
Andrew Trickd5422652012-02-04 02:56:48 +000026#include "llvm/Assembly/PrintModulePass.h"
27#include "llvm/Support/CommandLine.h"
28#include "llvm/Support/Debug.h"
Andrew Trick74613342012-02-04 02:56:45 +000029#include "llvm/Support/ErrorHandling.h"
Jim Laskey13ec7022006-08-01 14:21:23 +000030
Chris Lattneraa4c91f2003-12-28 07:59:53 +000031using namespace llvm;
Brian Gaeked0fde302003-11-11 22:41:34 +000032
Andrew Trickd5422652012-02-04 02:56:48 +000033static cl::opt<bool> DisablePostRA("disable-post-ra", cl::Hidden,
34 cl::desc("Disable Post Regalloc"));
35static cl::opt<bool> DisableBranchFold("disable-branch-fold", cl::Hidden,
36 cl::desc("Disable branch folding"));
37static cl::opt<bool> DisableTailDuplicate("disable-tail-duplicate", cl::Hidden,
38 cl::desc("Disable tail duplication"));
39static cl::opt<bool> DisableEarlyTailDup("disable-early-taildup", cl::Hidden,
40 cl::desc("Disable pre-register allocation tail duplication"));
Chandler Carruth9e67db42012-04-16 13:49:17 +000041static cl::opt<bool> DisableBlockPlacement("disable-block-placement",
42 cl::Hidden, cl::desc("Disable the probability-driven block placement, and "
43 "re-enable the old code placement pass"));
Andrew Trickd5422652012-02-04 02:56:48 +000044static cl::opt<bool> EnableBlockPlacementStats("enable-block-placement-stats",
45 cl::Hidden, cl::desc("Collect probability-driven block placement stats"));
46static cl::opt<bool> DisableCodePlace("disable-code-place", cl::Hidden,
47 cl::desc("Disable code placement"));
48static cl::opt<bool> DisableSSC("disable-ssc", cl::Hidden,
49 cl::desc("Disable Stack Slot Coloring"));
50static cl::opt<bool> DisableMachineDCE("disable-machine-dce", cl::Hidden,
51 cl::desc("Disable Machine Dead Code Elimination"));
52static cl::opt<bool> DisableMachineLICM("disable-machine-licm", cl::Hidden,
53 cl::desc("Disable Machine LICM"));
54static cl::opt<bool> DisableMachineCSE("disable-machine-cse", cl::Hidden,
55 cl::desc("Disable Machine Common Subexpression Elimination"));
Andrew Trick8dd26252012-02-10 04:10:36 +000056static cl::opt<cl::boolOrDefault>
57OptimizeRegAlloc("optimize-regalloc", cl::Hidden,
58 cl::desc("Enable optimized register allocation compilation path."));
Andrew Trick746f24b2012-02-11 07:11:32 +000059static cl::opt<cl::boolOrDefault>
60EnableMachineSched("enable-misched", cl::Hidden,
Andrew Trick8dd26252012-02-10 04:10:36 +000061 cl::desc("Enable the machine instruction scheduling pass."));
62static cl::opt<bool> EnableStrongPHIElim("strong-phi-elim", cl::Hidden,
63 cl::desc("Use strong PHI elimination."));
Andrew Trickd5422652012-02-04 02:56:48 +000064static cl::opt<bool> DisablePostRAMachineLICM("disable-postra-machine-licm",
65 cl::Hidden,
66 cl::desc("Disable Machine LICM"));
67static cl::opt<bool> DisableMachineSink("disable-machine-sink", cl::Hidden,
68 cl::desc("Disable Machine Sinking"));
69static cl::opt<bool> DisableLSR("disable-lsr", cl::Hidden,
70 cl::desc("Disable Loop Strength Reduction Pass"));
71static cl::opt<bool> DisableCGP("disable-cgp", cl::Hidden,
72 cl::desc("Disable Codegen Prepare"));
73static cl::opt<bool> DisableCopyProp("disable-copyprop", cl::Hidden,
Evan Cheng01b623c2012-02-20 23:28:17 +000074 cl::desc("Disable Copy Propagation pass"));
Andrew Trickd5422652012-02-04 02:56:48 +000075static cl::opt<bool> PrintLSR("print-lsr-output", cl::Hidden,
76 cl::desc("Print LLVM IR produced by the loop-reduce pass"));
77static cl::opt<bool> PrintISelInput("print-isel-input", cl::Hidden,
78 cl::desc("Print LLVM IR input to isel pass"));
79static cl::opt<bool> PrintGCInfo("print-gc", cl::Hidden,
80 cl::desc("Dump garbage collector data"));
81static cl::opt<bool> VerifyMachineCode("verify-machineinstrs", cl::Hidden,
82 cl::desc("Verify generated machine code"),
83 cl::init(getenv("LLVM_VERIFY_MACHINEINSTRS")!=NULL));
Bob Wilson6e1b8122012-05-30 00:17:12 +000084static cl::opt<std::string>
85PrintMachineInstrs("print-machineinstrs", cl::ValueOptional,
86 cl::desc("Print machine instrs"),
87 cl::value_desc("pass-name"), cl::init("option-unspecified"));
Andrew Trickd5422652012-02-04 02:56:48 +000088
Andrew Trick79bf2882012-02-15 03:21:51 +000089/// Allow standard passes to be disabled by command line options. This supports
90/// simple binary flags that either suppress the pass or do nothing.
91/// i.e. -disable-mypass=false has no effect.
92/// These should be converted to boolOrDefault in order to use applyOverride.
Bob Wilson3fb99a72012-07-02 19:48:37 +000093static AnalysisID applyDisable(AnalysisID PassID, bool Override) {
Andrew Trick79bf2882012-02-15 03:21:51 +000094 if (Override)
Bob Wilson3fb99a72012-07-02 19:48:37 +000095 return 0;
96 return PassID;
Andrew Trick79bf2882012-02-15 03:21:51 +000097}
98
99/// Allow Pass selection to be overriden by command line options. This supports
100/// flags with ternary conditions. TargetID is passed through by default. The
101/// pass is suppressed when the option is false. When the option is true, the
102/// StandardID is selected if the target provides no default.
103static AnalysisID applyOverride(AnalysisID TargetID, cl::boolOrDefault Override,
104 AnalysisID StandardID) {
Andrew Trick746f24b2012-02-11 07:11:32 +0000105 switch (Override) {
106 case cl::BOU_UNSET:
Andrew Trick79bf2882012-02-15 03:21:51 +0000107 return TargetID;
Andrew Trick746f24b2012-02-11 07:11:32 +0000108 case cl::BOU_TRUE:
Bob Wilson3fb99a72012-07-02 19:48:37 +0000109 if (TargetID)
Andrew Trick79bf2882012-02-15 03:21:51 +0000110 return TargetID;
Bob Wilson3fb99a72012-07-02 19:48:37 +0000111 if (StandardID == 0)
Andrew Trick746f24b2012-02-11 07:11:32 +0000112 report_fatal_error("Target cannot enable pass");
Andrew Trick79bf2882012-02-15 03:21:51 +0000113 return StandardID;
Andrew Trick746f24b2012-02-11 07:11:32 +0000114 case cl::BOU_FALSE:
Bob Wilson3fb99a72012-07-02 19:48:37 +0000115 return 0;
Andrew Trick746f24b2012-02-11 07:11:32 +0000116 }
117 llvm_unreachable("Invalid command line option state");
118}
119
Andrew Trick79bf2882012-02-15 03:21:51 +0000120/// Allow standard passes to be disabled by the command line, regardless of who
121/// is adding the pass.
122///
123/// StandardID is the pass identified in the standard pass pipeline and provided
124/// to addPass(). It may be a target-specific ID in the case that the target
125/// directly adds its own pass, but in that case we harmlessly fall through.
126///
127/// TargetID is the pass that the target has configured to override StandardID.
128///
129/// StandardID may be a pseudo ID. In that case TargetID is the name of the real
130/// pass to run. This allows multiple options to control a single pass depending
131/// on where in the pipeline that pass is added.
132static AnalysisID overridePass(AnalysisID StandardID, AnalysisID TargetID) {
133 if (StandardID == &PostRASchedulerID)
134 return applyDisable(TargetID, DisablePostRA);
135
136 if (StandardID == &BranchFolderPassID)
137 return applyDisable(TargetID, DisableBranchFold);
138
139 if (StandardID == &TailDuplicateID)
140 return applyDisable(TargetID, DisableTailDuplicate);
141
142 if (StandardID == &TargetPassConfig::EarlyTailDuplicateID)
143 return applyDisable(TargetID, DisableEarlyTailDup);
144
145 if (StandardID == &MachineBlockPlacementID)
146 return applyDisable(TargetID, DisableCodePlace);
147
148 if (StandardID == &CodePlacementOptID)
149 return applyDisable(TargetID, DisableCodePlace);
150
151 if (StandardID == &StackSlotColoringID)
152 return applyDisable(TargetID, DisableSSC);
153
154 if (StandardID == &DeadMachineInstructionElimID)
155 return applyDisable(TargetID, DisableMachineDCE);
156
157 if (StandardID == &MachineLICMID)
158 return applyDisable(TargetID, DisableMachineLICM);
159
160 if (StandardID == &MachineCSEID)
161 return applyDisable(TargetID, DisableMachineCSE);
162
163 if (StandardID == &MachineSchedulerID)
164 return applyOverride(TargetID, EnableMachineSched, StandardID);
165
166 if (StandardID == &TargetPassConfig::PostRAMachineLICMID)
167 return applyDisable(TargetID, DisablePostRAMachineLICM);
168
169 if (StandardID == &MachineSinkingID)
170 return applyDisable(TargetID, DisableMachineSink);
171
172 if (StandardID == &MachineCopyPropagationID)
173 return applyDisable(TargetID, DisableCopyProp);
174
175 return TargetID;
176}
177
Jim Laskeyeb577ba2006-08-02 12:30:23 +0000178//===---------------------------------------------------------------------===//
Andrew Trick74613342012-02-04 02:56:45 +0000179/// TargetPassConfig
180//===---------------------------------------------------------------------===//
181
182INITIALIZE_PASS(TargetPassConfig, "targetpassconfig",
183 "Target Pass Configuration", false, false)
184char TargetPassConfig::ID = 0;
185
Andrew Trick79bf2882012-02-15 03:21:51 +0000186// Pseudo Pass IDs.
187char TargetPassConfig::EarlyTailDuplicateID = 0;
188char TargetPassConfig::PostRAMachineLICMID = 0;
189
Andrew Trick5e108ee2012-02-15 03:21:47 +0000190namespace llvm {
191class PassConfigImpl {
192public:
193 // List of passes explicitly substituted by this target. Normally this is
194 // empty, but it is a convenient way to suppress or replace specific passes
195 // that are part of a standard pass pipeline without overridding the entire
196 // pipeline. This mechanism allows target options to inherit a standard pass's
197 // user interface. For example, a target may disable a standard pass by
Bob Wilson3fb99a72012-07-02 19:48:37 +0000198 // default by substituting a pass ID of zero, and the user may still enable
199 // that standard pass with an explicit command line option.
Andrew Trick5e108ee2012-02-15 03:21:47 +0000200 DenseMap<AnalysisID,AnalysisID> TargetPasses;
Bob Wilson6e1b8122012-05-30 00:17:12 +0000201
202 /// Store the pairs of <AnalysisID, AnalysisID> of which the second pass
203 /// is inserted after each instance of the first one.
204 SmallVector<std::pair<AnalysisID, AnalysisID>, 4> InsertedPasses;
Andrew Trick5e108ee2012-02-15 03:21:47 +0000205};
206} // namespace llvm
207
Andrew Trick74613342012-02-04 02:56:45 +0000208// Out of line virtual method.
Andrew Trick5e108ee2012-02-15 03:21:47 +0000209TargetPassConfig::~TargetPassConfig() {
210 delete Impl;
211}
Andrew Trick74613342012-02-04 02:56:45 +0000212
Andrew Trick61f1e3d2012-02-08 21:22:48 +0000213// Out of line constructor provides default values for pass options and
214// registers all common codegen passes.
Andrew Trick061efcf2012-02-04 02:56:59 +0000215TargetPassConfig::TargetPassConfig(TargetMachine *tm, PassManagerBase &pm)
Bob Wilson30a507a2012-07-02 19:48:45 +0000216 : ImmutablePass(ID), PM(&pm), StartAfter(0), StopAfter(0),
217 Started(true), Stopped(false), TM(tm), Impl(0), Initialized(false),
Andrew Trickffea03f2012-02-08 21:22:39 +0000218 DisableVerify(false),
219 EnableTailMerge(true) {
220
Andrew Trick5e108ee2012-02-15 03:21:47 +0000221 Impl = new PassConfigImpl();
222
Andrew Trick74613342012-02-04 02:56:45 +0000223 // Register all target independent codegen passes to activate their PassIDs,
224 // including this pass itself.
225 initializeCodeGen(*PassRegistry::getPassRegistry());
Andrew Trick79bf2882012-02-15 03:21:51 +0000226
227 // Substitute Pseudo Pass IDs for real ones.
Bob Wilson3fb99a72012-07-02 19:48:37 +0000228 substitutePass(&EarlyTailDuplicateID, &TailDuplicateID);
229 substitutePass(&PostRAMachineLICMID, &MachineLICMID);
Andrew Trick79bf2882012-02-15 03:21:51 +0000230
231 // Temporarily disable experimental passes.
Bob Wilson3fb99a72012-07-02 19:48:37 +0000232 substitutePass(&MachineSchedulerID, 0);
Andrew Trick74613342012-02-04 02:56:45 +0000233}
234
Bob Wilson6e1b8122012-05-30 00:17:12 +0000235/// Insert InsertedPassID pass after TargetPassID.
Bob Wilson3fb99a72012-07-02 19:48:37 +0000236void TargetPassConfig::insertPass(AnalysisID TargetPassID,
237 AnalysisID InsertedPassID) {
238 assert(TargetPassID != InsertedPassID && "Insert a pass after itself!");
239 std::pair<AnalysisID, AnalysisID> P(TargetPassID, InsertedPassID);
Bob Wilson6e1b8122012-05-30 00:17:12 +0000240 Impl->InsertedPasses.push_back(P);
241}
242
Andrew Trick74613342012-02-04 02:56:45 +0000243/// createPassConfig - Create a pass configuration object to be used by
244/// addPassToEmitX methods for generating a pipeline of CodeGen passes.
245///
246/// Targets may override this to extend TargetPassConfig.
Andrew Trick061efcf2012-02-04 02:56:59 +0000247TargetPassConfig *LLVMTargetMachine::createPassConfig(PassManagerBase &PM) {
248 return new TargetPassConfig(this, PM);
Andrew Trick74613342012-02-04 02:56:45 +0000249}
250
251TargetPassConfig::TargetPassConfig()
Bill Wendling7c4ce302012-05-01 08:27:43 +0000252 : ImmutablePass(ID), PM(0) {
Andrew Trick74613342012-02-04 02:56:45 +0000253 llvm_unreachable("TargetPassConfig should not be constructed on-the-fly");
254}
255
Andrew Trickffea03f2012-02-08 21:22:39 +0000256// Helper to verify the analysis is really immutable.
257void TargetPassConfig::setOpt(bool &Opt, bool Val) {
258 assert(!Initialized && "PassConfig is immutable");
259 Opt = Val;
260}
261
Bob Wilson3fb99a72012-07-02 19:48:37 +0000262void TargetPassConfig::substitutePass(AnalysisID StandardID,
263 AnalysisID TargetID) {
264 Impl->TargetPasses[StandardID] = TargetID;
Andrew Trick5e108ee2012-02-15 03:21:47 +0000265}
Andrew Trick746f24b2012-02-11 07:11:32 +0000266
Andrew Trick5e108ee2012-02-15 03:21:47 +0000267AnalysisID TargetPassConfig::getPassSubstitution(AnalysisID ID) const {
268 DenseMap<AnalysisID, AnalysisID>::const_iterator
269 I = Impl->TargetPasses.find(ID);
270 if (I == Impl->TargetPasses.end())
271 return ID;
272 return I->second;
273}
274
Bob Wilson30a507a2012-07-02 19:48:45 +0000275/// Add a pass to the PassManager if that pass is supposed to be run. If the
276/// Started/Stopped flags indicate either that the compilation should start at
277/// a later pass or that it should stop after an earlier pass, then do not add
278/// the pass. Finally, compare the current pass against the StartAfter
279/// and StopAfter options and change the Started/Stopped flags accordingly.
Bob Wilson564fbf62012-07-02 19:48:31 +0000280void TargetPassConfig::addPass(Pass *P) {
Bob Wilson6b2bb152012-07-02 19:48:39 +0000281 assert(!Initialized && "PassConfig is immutable");
282
Chandler Carruth6068c482012-07-02 22:56:41 +0000283 // Cache the Pass ID here in case the pass manager finds this pass is
284 // redundant with ones already scheduled / available, and deletes it.
285 // Fundamentally, once we add the pass to the manager, we no longer own it
286 // and shouldn't reference it.
287 AnalysisID PassID = P->getPassID();
288
Bob Wilson30a507a2012-07-02 19:48:45 +0000289 if (Started && !Stopped)
290 PM->add(P);
Chandler Carruth6068c482012-07-02 22:56:41 +0000291 if (StopAfter == PassID)
Bob Wilson30a507a2012-07-02 19:48:45 +0000292 Stopped = true;
Chandler Carruth6068c482012-07-02 22:56:41 +0000293 if (StartAfter == PassID)
Bob Wilson30a507a2012-07-02 19:48:45 +0000294 Started = true;
295 if (Stopped && !Started)
296 report_fatal_error("Cannot stop compilation after pass that is not run");
Bob Wilson564fbf62012-07-02 19:48:31 +0000297}
298
Andrew Trick5e108ee2012-02-15 03:21:47 +0000299/// Add a CodeGen pass at this point in the pipeline after checking for target
300/// and command line overrides.
Bob Wilson3fb99a72012-07-02 19:48:37 +0000301AnalysisID TargetPassConfig::addPass(AnalysisID PassID) {
Bob Wilson3fb99a72012-07-02 19:48:37 +0000302 AnalysisID TargetID = getPassSubstitution(PassID);
303 AnalysisID FinalID = overridePass(PassID, TargetID);
304 if (FinalID == 0)
Andrew Trick5e108ee2012-02-15 03:21:47 +0000305 return FinalID;
306
307 Pass *P = Pass::createPass(FinalID);
Andrew Trickebe18ef2012-02-08 21:22:34 +0000308 if (!P)
309 llvm_unreachable("Pass ID not registered");
Bob Wilson564fbf62012-07-02 19:48:31 +0000310 addPass(P);
Bob Wilson6e1b8122012-05-30 00:17:12 +0000311 // Add the passes after the pass P if there is any.
312 for (SmallVector<std::pair<AnalysisID, AnalysisID>, 4>::iterator
313 I = Impl->InsertedPasses.begin(), E = Impl->InsertedPasses.end();
314 I != E; ++I) {
Bob Wilson3fb99a72012-07-02 19:48:37 +0000315 if ((*I).first == PassID) {
Bob Wilson6e1b8122012-05-30 00:17:12 +0000316 assert((*I).second && "Illegal Pass ID!");
317 Pass *NP = Pass::createPass((*I).second);
318 assert(NP && "Pass ID not registered");
Bob Wilson564fbf62012-07-02 19:48:31 +0000319 addPass(NP);
Bob Wilson6e1b8122012-05-30 00:17:12 +0000320 }
321 }
Andrew Trick5e108ee2012-02-15 03:21:47 +0000322 return FinalID;
Andrew Trick061efcf2012-02-04 02:56:59 +0000323}
Andrew Trickd5422652012-02-04 02:56:48 +0000324
Bob Wilson564fbf62012-07-02 19:48:31 +0000325void TargetPassConfig::printAndVerify(const char *Banner) {
Andrew Trickd5422652012-02-04 02:56:48 +0000326 if (TM->shouldPrintMachineCode())
Bob Wilson564fbf62012-07-02 19:48:31 +0000327 addPass(createMachineFunctionPrinterPass(dbgs(), Banner));
Andrew Trickd5422652012-02-04 02:56:48 +0000328
329 if (VerifyMachineCode)
Bob Wilson564fbf62012-07-02 19:48:31 +0000330 addPass(createMachineVerifierPass(Banner));
Andrew Trickd5422652012-02-04 02:56:48 +0000331}
332
Andrew Trick061efcf2012-02-04 02:56:59 +0000333/// Add common target configurable passes that perform LLVM IR to IR transforms
334/// following machine independent optimization.
335void TargetPassConfig::addIRPasses() {
Andrew Trickd5422652012-02-04 02:56:48 +0000336 // Basic AliasAnalysis support.
337 // Add TypeBasedAliasAnalysis before BasicAliasAnalysis so that
338 // BasicAliasAnalysis wins if they disagree. This is intended to help
339 // support "obvious" type-punning idioms.
Bob Wilson564fbf62012-07-02 19:48:31 +0000340 addPass(createTypeBasedAliasAnalysisPass());
341 addPass(createBasicAliasAnalysisPass());
Andrew Trickd5422652012-02-04 02:56:48 +0000342
343 // Before running any passes, run the verifier to determine if the input
344 // coming from the front-end and/or optimizer is valid.
345 if (!DisableVerify)
Bob Wilson564fbf62012-07-02 19:48:31 +0000346 addPass(createVerifierPass());
Andrew Trickd5422652012-02-04 02:56:48 +0000347
348 // Run loop strength reduction before anything else.
349 if (getOptLevel() != CodeGenOpt::None && !DisableLSR) {
Bob Wilson564fbf62012-07-02 19:48:31 +0000350 addPass(createLoopStrengthReducePass(getTargetLowering()));
Andrew Trickd5422652012-02-04 02:56:48 +0000351 if (PrintLSR)
Bob Wilson564fbf62012-07-02 19:48:31 +0000352 addPass(createPrintFunctionPass("\n\n*** Code after LSR ***\n", &dbgs()));
Andrew Trickd5422652012-02-04 02:56:48 +0000353 }
354
Bob Wilson564fbf62012-07-02 19:48:31 +0000355 addPass(createGCLoweringPass());
Andrew Trickd5422652012-02-04 02:56:48 +0000356
357 // Make sure that no unreachable blocks are instruction selected.
Bob Wilson564fbf62012-07-02 19:48:31 +0000358 addPass(createUnreachableBlockEliminationPass());
359}
360
361/// Turn exception handling constructs into something the code generators can
362/// handle.
363void TargetPassConfig::addPassesToHandleExceptions() {
364 switch (TM->getMCAsmInfo()->getExceptionHandlingType()) {
365 case ExceptionHandling::SjLj:
366 // SjLj piggy-backs on dwarf for this bit. The cleanups done apply to both
367 // Dwarf EH prepare needs to be run after SjLj prepare. Otherwise,
368 // catch info can get misplaced when a selector ends up more than one block
369 // removed from the parent invoke(s). This could happen when a landing
370 // pad is shared by multiple invokes and is also a target of a normal
371 // edge from elsewhere.
372 addPass(createSjLjEHPreparePass(TM->getTargetLowering()));
373 // FALLTHROUGH
374 case ExceptionHandling::DwarfCFI:
375 case ExceptionHandling::ARM:
376 case ExceptionHandling::Win64:
377 addPass(createDwarfEHPass(TM));
378 break;
379 case ExceptionHandling::None:
380 addPass(createLowerInvokePass(TM->getTargetLowering()));
381
382 // The lower invoke pass may create unreachable code. Remove it.
383 addPass(createUnreachableBlockEliminationPass());
384 break;
385 }
Andrew Trick061efcf2012-02-04 02:56:59 +0000386}
Andrew Trickd5422652012-02-04 02:56:48 +0000387
Andrew Trick061efcf2012-02-04 02:56:59 +0000388/// Add common passes that perform LLVM IR to IR transforms in preparation for
389/// instruction selection.
390void TargetPassConfig::addISelPrepare() {
Andrew Trickd5422652012-02-04 02:56:48 +0000391 if (getOptLevel() != CodeGenOpt::None && !DisableCGP)
Bob Wilson564fbf62012-07-02 19:48:31 +0000392 addPass(createCodeGenPreparePass(getTargetLowering()));
Andrew Trickd5422652012-02-04 02:56:48 +0000393
Bob Wilson564fbf62012-07-02 19:48:31 +0000394 addPass(createStackProtectorPass(getTargetLowering()));
Andrew Trickd5422652012-02-04 02:56:48 +0000395
396 addPreISel();
397
398 if (PrintISelInput)
Bob Wilson564fbf62012-07-02 19:48:31 +0000399 addPass(createPrintFunctionPass("\n\n"
Bill Wendling7c4ce302012-05-01 08:27:43 +0000400 "*** Final LLVM Code input to ISel ***\n",
401 &dbgs()));
Andrew Trickd5422652012-02-04 02:56:48 +0000402
403 // All passes which modify the LLVM IR are now complete; run the verifier
404 // to ensure that the IR is valid.
405 if (!DisableVerify)
Bob Wilson564fbf62012-07-02 19:48:31 +0000406 addPass(createVerifierPass());
Andrew Trick061efcf2012-02-04 02:56:59 +0000407}
Andrew Trickd5422652012-02-04 02:56:48 +0000408
Andrew Trickf7b96312012-02-09 00:40:55 +0000409/// Add the complete set of target-independent postISel code generator passes.
410///
411/// This can be read as the standard order of major LLVM CodeGen stages. Stages
412/// with nontrivial configuration or multiple passes are broken out below in
413/// add%Stage routines.
414///
415/// Any TargetPassConfig::addXX routine may be overriden by the Target. The
416/// addPre/Post methods with empty header implementations allow injecting
417/// target-specific fixups just before or after major stages. Additionally,
418/// targets have the flexibility to change pass order within a stage by
419/// overriding default implementation of add%Stage routines below. Each
420/// technique has maintainability tradeoffs because alternate pass orders are
421/// not well supported. addPre/Post works better if the target pass is easily
422/// tied to a common pass. But if it has subtle dependencies on multiple passes,
Andrew Trick06efdd22012-02-10 07:08:25 +0000423/// the target should override the stage instead.
Andrew Trickf7b96312012-02-09 00:40:55 +0000424///
425/// TODO: We could use a single addPre/Post(ID) hook to allow pass injection
426/// before/after any target-independent pass. But it's currently overkill.
Andrew Trick061efcf2012-02-04 02:56:59 +0000427void TargetPassConfig::addMachinePasses() {
Andrew Trickd5422652012-02-04 02:56:48 +0000428 // Print the instruction selected machine code...
429 printAndVerify("After Instruction Selection");
430
Bob Wilson6e1b8122012-05-30 00:17:12 +0000431 // Insert a machine instr printer pass after the specified pass.
432 // If -print-machineinstrs specified, print machineinstrs after all passes.
433 if (StringRef(PrintMachineInstrs.getValue()).equals(""))
434 TM->Options.PrintMachineCode = true;
435 else if (!StringRef(PrintMachineInstrs.getValue())
436 .equals("option-unspecified")) {
437 const PassRegistry *PR = PassRegistry::getPassRegistry();
438 const PassInfo *TPI = PR->getPassInfo(PrintMachineInstrs.getValue());
439 const PassInfo *IPI = PR->getPassInfo(StringRef("print-machineinstrs"));
440 assert (TPI && IPI && "Pass ID not registered!");
441 const char *TID = (char *)(TPI->getTypeInfo());
442 const char *IID = (char *)(IPI->getTypeInfo());
Bob Wilson3fb99a72012-07-02 19:48:37 +0000443 insertPass(TID, IID);
Bob Wilson6e1b8122012-05-30 00:17:12 +0000444 }
445
Andrew Trickd5422652012-02-04 02:56:48 +0000446 // Expand pseudo-instructions emitted by ISel.
Bob Wilson3fb99a72012-07-02 19:48:37 +0000447 addPass(&ExpandISelPseudosID);
Andrew Trickd5422652012-02-04 02:56:48 +0000448
Andrew Trickf7b96312012-02-09 00:40:55 +0000449 // Add passes that optimize machine instructions in SSA form.
Andrew Trickd5422652012-02-04 02:56:48 +0000450 if (getOptLevel() != CodeGenOpt::None) {
Andrew Trickf7b96312012-02-09 00:40:55 +0000451 addMachineSSAOptimization();
452 }
453 else {
454 // If the target requests it, assign local variables to stack slots relative
455 // to one another and simplify frame index references where possible.
Bob Wilson3fb99a72012-07-02 19:48:37 +0000456 addPass(&LocalStackSlotAllocationID);
Andrew Trickd5422652012-02-04 02:56:48 +0000457 }
458
459 // Run pre-ra passes.
460 if (addPreRegAlloc())
461 printAndVerify("After PreRegAlloc passes");
462
Andrew Trickf7b96312012-02-09 00:40:55 +0000463 // Run register allocation and passes that are tightly coupled with it,
464 // including phi elimination and scheduling.
Andrew Trick8dd26252012-02-10 04:10:36 +0000465 if (getOptimizeRegAlloc())
466 addOptimizedRegAlloc(createRegAllocPass(true));
467 else
468 addFastRegAlloc(createRegAllocPass(false));
Andrew Trickd5422652012-02-04 02:56:48 +0000469
470 // Run post-ra passes.
471 if (addPostRegAlloc())
472 printAndVerify("After PostRegAlloc passes");
473
474 // Insert prolog/epilog code. Eliminate abstract frame index references...
Bob Wilson3fb99a72012-07-02 19:48:37 +0000475 addPass(&PrologEpilogCodeInserterID);
Andrew Trickd5422652012-02-04 02:56:48 +0000476 printAndVerify("After PrologEpilogCodeInserter");
477
Andrew Trickf7b96312012-02-09 00:40:55 +0000478 /// Add passes that optimize machine instructions after register allocation.
479 if (getOptLevel() != CodeGenOpt::None)
480 addMachineLateOptimization();
Andrew Trickd5422652012-02-04 02:56:48 +0000481
482 // Expand pseudo instructions before second scheduling pass.
Bob Wilson3fb99a72012-07-02 19:48:37 +0000483 addPass(&ExpandPostRAPseudosID);
Jakob Stoklund Olesen2ef5bf62012-03-28 20:49:30 +0000484 printAndVerify("After ExpandPostRAPseudos");
Andrew Trickd5422652012-02-04 02:56:48 +0000485
486 // Run pre-sched2 passes.
487 if (addPreSched2())
Jakob Stoklund Olesen78811662012-03-28 23:31:15 +0000488 printAndVerify("After PreSched2 passes");
Andrew Trickd5422652012-02-04 02:56:48 +0000489
490 // Second pass scheduler.
Andrew Trick79bf2882012-02-15 03:21:51 +0000491 if (getOptLevel() != CodeGenOpt::None) {
Bob Wilson3fb99a72012-07-02 19:48:37 +0000492 addPass(&PostRASchedulerID);
Jakob Stoklund Olesen8b4c5022012-03-28 23:54:28 +0000493 printAndVerify("After PostRAScheduler");
Andrew Trickd5422652012-02-04 02:56:48 +0000494 }
495
Andrew Trickf7b96312012-02-09 00:40:55 +0000496 // GC
Bob Wilson3fb99a72012-07-02 19:48:37 +0000497 addPass(&GCMachineCodeAnalysisID);
Andrew Trickd5422652012-02-04 02:56:48 +0000498 if (PrintGCInfo)
Bob Wilson564fbf62012-07-02 19:48:31 +0000499 addPass(createGCInfoPrinter(dbgs()));
Andrew Trickd5422652012-02-04 02:56:48 +0000500
Andrew Trickf7b96312012-02-09 00:40:55 +0000501 // Basic block placement.
Andrew Trick79bf2882012-02-15 03:21:51 +0000502 if (getOptLevel() != CodeGenOpt::None)
Andrew Trickf7b96312012-02-09 00:40:55 +0000503 addBlockPlacement();
Andrew Trickd5422652012-02-04 02:56:48 +0000504
505 if (addPreEmitPass())
Jakob Stoklund Olesen8b4c5022012-03-28 23:54:28 +0000506 printAndVerify("After PreEmit passes");
Andrew Trickd5422652012-02-04 02:56:48 +0000507}
508
Andrew Trickf7b96312012-02-09 00:40:55 +0000509/// Add passes that optimize machine instructions in SSA form.
510void TargetPassConfig::addMachineSSAOptimization() {
511 // Pre-ra tail duplication.
Bob Wilson3fb99a72012-07-02 19:48:37 +0000512 if (addPass(&EarlyTailDuplicateID))
Andrew Trickf7b96312012-02-09 00:40:55 +0000513 printAndVerify("After Pre-RegAlloc TailDuplicate");
Andrew Trickf7b96312012-02-09 00:40:55 +0000514
515 // Optimize PHIs before DCE: removing dead PHI cycles may make more
516 // instructions dead.
Bob Wilson3fb99a72012-07-02 19:48:37 +0000517 addPass(&OptimizePHIsID);
Andrew Trickf7b96312012-02-09 00:40:55 +0000518
519 // If the target requests it, assign local variables to stack slots relative
520 // to one another and simplify frame index references where possible.
Bob Wilson3fb99a72012-07-02 19:48:37 +0000521 addPass(&LocalStackSlotAllocationID);
Andrew Trickf7b96312012-02-09 00:40:55 +0000522
523 // With optimization, dead code should already be eliminated. However
524 // there is one known exception: lowered code for arguments that are only
525 // used by tail calls, where the tail calls reuse the incoming stack
526 // arguments directly (see t11 in test/CodeGen/X86/sibcall.ll).
Bob Wilson3fb99a72012-07-02 19:48:37 +0000527 addPass(&DeadMachineInstructionElimID);
Andrew Trickf7b96312012-02-09 00:40:55 +0000528 printAndVerify("After codegen DCE pass");
529
Bob Wilson3fb99a72012-07-02 19:48:37 +0000530 addPass(&MachineLICMID);
531 addPass(&MachineCSEID);
532 addPass(&MachineSinkingID);
Andrew Trickf7b96312012-02-09 00:40:55 +0000533 printAndVerify("After Machine LICM, CSE and Sinking passes");
534
Bob Wilson3fb99a72012-07-02 19:48:37 +0000535 addPass(&PeepholeOptimizerID);
Andrew Trickf7b96312012-02-09 00:40:55 +0000536 printAndVerify("After codegen peephole optimization pass");
537}
538
Andrew Trick74613342012-02-04 02:56:45 +0000539//===---------------------------------------------------------------------===//
Andrew Trickf7b96312012-02-09 00:40:55 +0000540/// Register Allocation Pass Configuration
Jim Laskeyeb577ba2006-08-02 12:30:23 +0000541//===---------------------------------------------------------------------===//
Andrew Trickf7b96312012-02-09 00:40:55 +0000542
Andrew Trick8dd26252012-02-10 04:10:36 +0000543bool TargetPassConfig::getOptimizeRegAlloc() const {
544 switch (OptimizeRegAlloc) {
545 case cl::BOU_UNSET: return getOptLevel() != CodeGenOpt::None;
546 case cl::BOU_TRUE: return true;
547 case cl::BOU_FALSE: return false;
548 }
549 llvm_unreachable("Invalid optimize-regalloc state");
550}
551
Andrew Trickf7b96312012-02-09 00:40:55 +0000552/// RegisterRegAlloc's global Registry tracks allocator registration.
Jim Laskeyeb577ba2006-08-02 12:30:23 +0000553MachinePassRegistry RegisterRegAlloc::Registry;
554
Andrew Trickf7b96312012-02-09 00:40:55 +0000555/// A dummy default pass factory indicates whether the register allocator is
556/// overridden on the command line.
Andrew Trick8dd26252012-02-10 04:10:36 +0000557static FunctionPass *useDefaultRegisterAllocator() { return 0; }
Jakob Stoklund Olesen700bfad2010-05-27 23:57:25 +0000558static RegisterRegAlloc
559defaultRegAlloc("default",
560 "pick register allocator based on -O option",
Andrew Trick8dd26252012-02-10 04:10:36 +0000561 useDefaultRegisterAllocator);
Jim Laskeyeb577ba2006-08-02 12:30:23 +0000562
Andrew Trickf7b96312012-02-09 00:40:55 +0000563/// -regalloc=... command line option.
Dan Gohman844731a2008-05-13 00:00:25 +0000564static cl::opt<RegisterRegAlloc::FunctionPassCtor, false,
565 RegisterPassParser<RegisterRegAlloc> >
566RegAlloc("regalloc",
Andrew Trick8dd26252012-02-10 04:10:36 +0000567 cl::init(&useDefaultRegisterAllocator),
Jakob Stoklund Olesen700bfad2010-05-27 23:57:25 +0000568 cl::desc("Register allocator to use"));
Alkis Evlogimenos7237ece2003-10-02 16:57:49 +0000569
Jim Laskeyeb577ba2006-08-02 12:30:23 +0000570
Andrew Trick8dd26252012-02-10 04:10:36 +0000571/// Instantiate the default register allocator pass for this target for either
572/// the optimized or unoptimized allocation path. This will be added to the pass
573/// manager by addFastRegAlloc in the unoptimized case or addOptimizedRegAlloc
574/// in the optimized case.
575///
576/// A target that uses the standard regalloc pass order for fast or optimized
577/// allocation may still override this for per-target regalloc
578/// selection. But -regalloc=... always takes precedence.
579FunctionPass *TargetPassConfig::createTargetRegisterAllocator(bool Optimized) {
580 if (Optimized)
581 return createGreedyRegisterAllocator();
582 else
583 return createFastRegisterAllocator();
584}
585
586/// Find and instantiate the register allocation pass requested by this target
587/// at the current optimization level. Different register allocators are
588/// defined as separate passes because they may require different analysis.
589///
590/// This helper ensures that the regalloc= option is always available,
591/// even for targets that override the default allocator.
592///
593/// FIXME: When MachinePassRegistry register pass IDs instead of function ptrs,
594/// this can be folded into addPass.
595FunctionPass *TargetPassConfig::createRegAllocPass(bool Optimized) {
Jim Laskey9ff542f2006-08-01 18:29:48 +0000596 RegisterRegAlloc::FunctionPassCtor Ctor = RegisterRegAlloc::getDefault();
Jakob Stoklund Olesen700bfad2010-05-27 23:57:25 +0000597
Andrew Trick8dd26252012-02-10 04:10:36 +0000598 // Initialize the global default.
Jim Laskey13ec7022006-08-01 14:21:23 +0000599 if (!Ctor) {
Jim Laskeyeb577ba2006-08-02 12:30:23 +0000600 Ctor = RegAlloc;
601 RegisterRegAlloc::setDefault(RegAlloc);
Jim Laskey13ec7022006-08-01 14:21:23 +0000602 }
Andrew Trick8dd26252012-02-10 04:10:36 +0000603 if (Ctor != useDefaultRegisterAllocator)
Jakob Stoklund Olesen700bfad2010-05-27 23:57:25 +0000604 return Ctor();
605
Andrew Trick8dd26252012-02-10 04:10:36 +0000606 // With no -regalloc= override, ask the target for a regalloc pass.
607 return createTargetRegisterAllocator(Optimized);
608}
609
610/// Add the minimum set of target-independent passes that are required for
611/// register allocation. No coalescing or scheduling.
612void TargetPassConfig::addFastRegAlloc(FunctionPass *RegAllocPass) {
Bob Wilson3fb99a72012-07-02 19:48:37 +0000613 addPass(&PHIEliminationID);
614 addPass(&TwoAddressInstructionPassID);
Andrew Trick8dd26252012-02-10 04:10:36 +0000615
Bob Wilson564fbf62012-07-02 19:48:31 +0000616 addPass(RegAllocPass);
Andrew Trick8dd26252012-02-10 04:10:36 +0000617 printAndVerify("After Register Allocation");
Jim Laskey33a0a6d2006-07-27 20:05:00 +0000618}
Andrew Trickf7b96312012-02-09 00:40:55 +0000619
620/// Add standard target-independent passes that are tightly coupled with
Andrew Trick8dd26252012-02-10 04:10:36 +0000621/// optimized register allocation, including coalescing, machine instruction
622/// scheduling, and register allocation itself.
623void TargetPassConfig::addOptimizedRegAlloc(FunctionPass *RegAllocPass) {
Bob Wilson3fb99a72012-07-02 19:48:37 +0000624 addPass(&ProcessImplicitDefsID);
Jakob Stoklund Olesen5984d2b2012-06-25 18:12:18 +0000625
Andrew Trick8dd26252012-02-10 04:10:36 +0000626 // LiveVariables currently requires pure SSA form.
627 //
628 // FIXME: Once TwoAddressInstruction pass no longer uses kill flags,
629 // LiveVariables can be removed completely, and LiveIntervals can be directly
630 // computed. (We still either need to regenerate kill flags after regalloc, or
631 // preferably fix the scavenger to not depend on them).
Bob Wilson3fb99a72012-07-02 19:48:37 +0000632 addPass(&LiveVariablesID);
Andrew Trick8dd26252012-02-10 04:10:36 +0000633
634 // Add passes that move from transformed SSA into conventional SSA. This is a
635 // "copy coalescing" problem.
636 //
637 if (!EnableStrongPHIElim) {
638 // Edge splitting is smarter with machine loop info.
Bob Wilson3fb99a72012-07-02 19:48:37 +0000639 addPass(&MachineLoopInfoID);
640 addPass(&PHIEliminationID);
Andrew Trick8dd26252012-02-10 04:10:36 +0000641 }
Bob Wilson3fb99a72012-07-02 19:48:37 +0000642 addPass(&TwoAddressInstructionPassID);
Andrew Trick8dd26252012-02-10 04:10:36 +0000643
Andrew Trick8dd26252012-02-10 04:10:36 +0000644 if (EnableStrongPHIElim)
Bob Wilson3fb99a72012-07-02 19:48:37 +0000645 addPass(&StrongPHIEliminationID);
Andrew Trick8dd26252012-02-10 04:10:36 +0000646
Bob Wilson3fb99a72012-07-02 19:48:37 +0000647 addPass(&RegisterCoalescerID);
Andrew Trick8dd26252012-02-10 04:10:36 +0000648
649 // PreRA instruction scheduling.
Bob Wilson3fb99a72012-07-02 19:48:37 +0000650 if (addPass(&MachineSchedulerID))
Andrew Trick17d35e52012-03-14 04:00:41 +0000651 printAndVerify("After Machine Scheduling");
Andrew Trick8dd26252012-02-10 04:10:36 +0000652
653 // Add the selected register allocation pass.
Bob Wilson564fbf62012-07-02 19:48:31 +0000654 addPass(RegAllocPass);
Jakob Stoklund Olesen34f5a2b2012-06-26 17:09:29 +0000655 printAndVerify("After Register Allocation, before rewriter");
656
657 // Allow targets to change the register assignments before rewriting.
658 if (addPreRewrite())
659 printAndVerify("After pre-rewrite passes");
Andrew Trickf7b96312012-02-09 00:40:55 +0000660
Jakob Stoklund Olesen05ec7122012-06-08 23:44:45 +0000661 // Finally rewrite virtual registers.
Bob Wilson3fb99a72012-07-02 19:48:37 +0000662 addPass(&VirtRegRewriterID);
Jakob Stoklund Olesen05ec7122012-06-08 23:44:45 +0000663 printAndVerify("After Virtual Register Rewriter");
664
Andrew Trick746f24b2012-02-11 07:11:32 +0000665 // FinalizeRegAlloc is convenient until MachineInstrBundles is more mature,
666 // but eventually, all users of it should probably be moved to addPostRA and
667 // it can go away. Currently, it's the intended place for targets to run
668 // FinalizeMachineBundles, because passes other than MachineScheduling an
669 // RegAlloc itself may not be aware of bundles.
670 if (addFinalizeRegAlloc())
671 printAndVerify("After RegAlloc finalization");
672
Andrew Trickf7b96312012-02-09 00:40:55 +0000673 // Perform stack slot coloring and post-ra machine LICM.
Andrew Trick8dd26252012-02-10 04:10:36 +0000674 //
675 // FIXME: Re-enable coloring with register when it's capable of adding
676 // kill markers.
Bob Wilson3fb99a72012-07-02 19:48:37 +0000677 addPass(&StackSlotColoringID);
Andrew Trick900d7b72012-02-15 07:57:03 +0000678
679 // Run post-ra machine LICM to hoist reloads / remats.
680 //
681 // FIXME: can this move into MachineLateOptimization?
Bob Wilson3fb99a72012-07-02 19:48:37 +0000682 addPass(&PostRAMachineLICMID);
Andrew Trick900d7b72012-02-15 07:57:03 +0000683
684 printAndVerify("After StackSlotColoring and postra Machine LICM");
Andrew Trickf7b96312012-02-09 00:40:55 +0000685}
686
687//===---------------------------------------------------------------------===//
688/// Post RegAlloc Pass Configuration
689//===---------------------------------------------------------------------===//
690
691/// Add passes that optimize machine instructions after register allocation.
692void TargetPassConfig::addMachineLateOptimization() {
693 // Branch folding must be run after regalloc and prolog/epilog insertion.
Bob Wilson3fb99a72012-07-02 19:48:37 +0000694 if (addPass(&BranchFolderPassID))
Jakob Stoklund Olesen663ee202012-03-28 20:47:37 +0000695 printAndVerify("After BranchFolding");
Andrew Trickf7b96312012-02-09 00:40:55 +0000696
697 // Tail duplication.
Bob Wilson3fb99a72012-07-02 19:48:37 +0000698 if (addPass(&TailDuplicateID))
Jakob Stoklund Olesen663ee202012-03-28 20:47:37 +0000699 printAndVerify("After TailDuplicate");
Andrew Trickf7b96312012-02-09 00:40:55 +0000700
701 // Copy propagation.
Bob Wilson3fb99a72012-07-02 19:48:37 +0000702 if (addPass(&MachineCopyPropagationID))
Jakob Stoklund Olesen663ee202012-03-28 20:47:37 +0000703 printAndVerify("After copy propagation pass");
Andrew Trickf7b96312012-02-09 00:40:55 +0000704}
705
706/// Add standard basic block placement passes.
707void TargetPassConfig::addBlockPlacement() {
Bob Wilson3fb99a72012-07-02 19:48:37 +0000708 AnalysisID PassID = 0;
Chandler Carruth9e67db42012-04-16 13:49:17 +0000709 if (!DisableBlockPlacement) {
710 // MachineBlockPlacement is a new pass which subsumes the functionality of
711 // CodPlacementOpt. The old code placement pass can be restored by
712 // disabling block placement, but eventually it will be removed.
Bob Wilson3fb99a72012-07-02 19:48:37 +0000713 PassID = addPass(&MachineBlockPlacementID);
Andrew Trickf7b96312012-02-09 00:40:55 +0000714 } else {
Bob Wilson3fb99a72012-07-02 19:48:37 +0000715 PassID = addPass(&CodePlacementOptID);
Andrew Trickf7b96312012-02-09 00:40:55 +0000716 }
Bob Wilson3fb99a72012-07-02 19:48:37 +0000717 if (PassID) {
Andrew Trick79bf2882012-02-15 03:21:51 +0000718 // Run a separate pass to collect block placement statistics.
719 if (EnableBlockPlacementStats)
Bob Wilson3fb99a72012-07-02 19:48:37 +0000720 addPass(&MachineBlockPlacementStatsID);
Andrew Trickf7b96312012-02-09 00:40:55 +0000721
Jakob Stoklund Olesen8b4c5022012-03-28 23:54:28 +0000722 printAndVerify("After machine block placement.");
Andrew Trickf7b96312012-02-09 00:40:55 +0000723 }
724}