1/*
2 * Copyright 2015 WebAssembly Community Group participants
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17#ifndef wasm_pass_h
18#define wasm_pass_h
19
20#include <functional>
21
22#include "mixed_arena.h"
23#include "support/utilities.h"
24#include "wasm-traversal.h"
25#include "wasm.h"
26
27namespace wasm {
28
29class Pass;
30
31//
32// Global registry of all passes in /passes/
33//
34struct PassRegistry {
35 PassRegistry();
36
37 static PassRegistry* get();
38
39 using Creator = std::function<Pass*()>;
40
41 void registerPass(const char* name, const char* description, Creator create);
42 // Register a pass that's used for internal testing. These passes do not show
43 // up in --help.
44 void
45 registerTestPass(const char* name, const char* description, Creator create);
46 std::unique_ptr<Pass> createPass(std::string name);
47 std::vector<std::string> getRegisteredNames();
48 std::string getPassDescription(std::string name);
49 bool isPassHidden(std::string name);
50
51private:
52 void registerPasses();
53
54 struct PassInfo {
55 std::string description;
56 Creator create;
57 bool hidden;
58 PassInfo() = default;
59 PassInfo(std::string description, Creator create, bool hidden = false)
60 : description(description), create(create), hidden(hidden) {}
61 };
62 std::map<std::string, PassInfo> passInfos;
63};
64
65struct InliningOptions {
66 // Function size at which we always inline.
67 // Typically a size so small that after optimizations, the inlined code will
68 // be smaller than the call instruction itself. 2 is a safe number because
69 // there is no risk of things like
70 // (func $reverse (param $x i32) (param $y i32)
71 // (call $something (local.get $y) (local.get $x))
72 // )
73 // in which case the reversing of the params means we'll possibly need
74 // a block and a temp local. But that takes at least 3 nodes, and 2 < 3.
75 // More generally, with 2 items we may have a local.get, but no way to
76 // require it to be saved instead of directly consumed.
77 Index alwaysInlineMaxSize = 2;
78 // Function size which we inline when there is only one caller. By default we
79 // inline all such functions (as after inlining we can remove the original
80 // function).
81 Index oneCallerInlineMaxSize = -1;
82 // Function size above which we never inline, ignoring the various flexible
83 // factors (like whether we are optimizing for size or speed) that could
84 // influence us.
85 // This is checked after alwaysInlineMaxSize and oneCallerInlineMaxSize, but
86 // the order normally won't matter.
87 Index flexibleInlineMaxSize = 20;
88 // Loops usually mean the function does heavy work, so the call overhead
89 // is not significant and we do not inline such functions by default.
90 bool allowFunctionsWithLoops = false;
91 // The number of ifs to allow partial inlining of their conditions. A value of
92 // zero disables partial inlining.
93 // TODO: Investigate enabling this. Locally 4 appears useful on real-world
94 // code, but reports of regressions have arrived.
95 Index partialInliningIfs = 0;
96};
97
98// Forward declaration for FuncEffectsMap.
99class EffectAnalyzer;
100
101using FuncEffectsMap = std::unordered_map<Name, EffectAnalyzer>;
102
103struct PassOptions {
104 // Run passes in debug mode, doing extra validation and timing checks.
105 bool debug = false;
106 // Whether to run the validator to check for errors.
107 bool validate = true;
108 // When validating validate globally and not just locally
109 bool validateGlobally = true;
110 // 0, 1, 2 correspond to -O0, -O1, -O2, etc.
111 int optimizeLevel = 0;
112 // 0, 1, 2 correspond to -O0, -Os, -Oz
113 int shrinkLevel = 0;
114 // Tweak thresholds for the Inlining pass.
115 InliningOptions inlining;
116 // Optimize assuming things like div by 0, bad load/store, will not trap.
117 // This is deprecated in favor of trapsNeverHappen.
118 bool ignoreImplicitTraps = false;
119 // Optimize assuming a trap will never happen at runtime. This is similar to
120 // ignoreImplicitTraps, but different:
121 //
122 // * ignoreImplicitTraps simply ignores the side effect of trapping when it
123 // computes side effects, and then passes work with that data.
124 // * trapsNeverHappen assumes that if an instruction with a possible trap is
125 // reached, then it does not trap, and an (unreachable) - that always
126 // traps - is never reached.
127 //
128 // The main difference is that in trapsNeverHappen mode we will not move
129 // around code that might trap, like this:
130 //
131 // (if (condition) (code))
132 //
133 // If (code) might trap, ignoreImplicitTraps ignores that trap, and it might
134 // end up moving (code) to happen before the (condition), that is,
135 // unconditionally. trapsNeverHappen, on the other hand, does not ignore the
136 // side effect of the trap; instead, it will potentially remove the trapping
137 // instruction, if it can - it is always safe to remove a trap in this mode,
138 // as the traps are assumed to not happen. Where it cannot remove the side
139 // effect, it will at least not move code around.
140 //
141 // A consequence of this difference is that code that puts a possible trap
142 // behind a condition is unsafe in ignoreImplicitTraps, but safe in
143 // trapsNeverHappen. In general, trapsNeverHappen is safe on production code
144 // where traps are either fatal errors or assertions, and it is assumed
145 // neither of those can happen (and it is undefined behavior if they do).
146 //
147 // TODO: deprecate and remove ignoreImplicitTraps.
148 //
149 // Since trapsNeverHappen assumes a trap is never reached, it can in principle
150 // remove code like this:
151 //
152 // (i32.store ..)
153 // (unreachable)
154 //
155 // The trap isn't reached, by assumption, and if we reach the store then we'd
156 // reach the trap, so we can assume that isn't reached either, and TNH can
157 // remove both. We do have a specific limitation here, however, which is that
158 // trapsNeverHappen cannot remove calls to *imports*. We assume that an import
159 // might do things we cannot understand, so we never eliminate it. For
160 // example, in LLVM output we might see this:
161 //
162 // (call $abort) ;; a noreturn import - the process is halted with an error
163 // (unreachable)
164 //
165 // That trap is never actually reached since the abort halts execution. In TNH
166 // we can remove the trap but not the call right before it.
167 bool trapsNeverHappen = false;
168 // Optimize assuming that the low 1K of memory is not valid memory for the
169 // application to use. In that case, we can optimize load/store offsets in
170 // many cases.
171 bool lowMemoryUnused = false;
172 enum { LowMemoryBound = 1024 };
173 // Whether to allow "loose" math semantics, ignoring corner cases with NaNs
174 // and assuming math follows the algebraic rules for associativity and so
175 // forth (which IEEE floats do not, strictly speaking). This is inspired by
176 // gcc/clang's -ffast-math flag.
177 bool fastMath = false;
178 // Whether to assume that an imported memory is zero-initialized. Without
179 // this, we can do fewer optimizations on memory segments, because if memory
180 // *was* modified then the wasm's segments may trample those previous
181 // modifications. If memory was zero-initialized then we can remove zeros from
182 // the wasm's segments.
183 // (This is not a problem if the memory is *not* imported, since then wasm
184 // creates it and we know it is all zeros right before the active segments are
185 // applied.)
186 bool zeroFilledMemory = false;
187 // Assume code outside of the module does not inspect or interact with GC and
188 // function references, with the goal of being able to aggressively optimize
189 // all user-defined types. The outside may hold on to references and pass them
190 // back in, but may not inspect their contents, call them, or reflect on their
191 // types in any way.
192 //
193 // By default we do not make this assumption, and assume anything that escapes
194 // to the outside may be inspected in detail, which prevents us from e.g.
195 // changing the type of any value that may escape except by refining it (so we
196 // can't remove or refine fields on an escaping struct type, for example,
197 // unless the new type declares the original type as a supertype).
198 //
199 // Note that the module can still have imports and exports - otherwise it
200 // could do nothing at all! - so the meaning of "closed world" is a little
201 // subtle here. We do still want to keep imports and exports unchanged, as
202 // they form a contract with the outside world. For example, if an import has
203 // two parameters, we can't remove one of them. A nuance regarding that is how
204 // type equality works between wasm modules using the isorecursive type
205 // system: not only do we need to not remove a parameter as just mentioned,
206 // but we also want to keep types of things on the boundary unchanged. For
207 // example, we should not change an exported function's signature, as the
208 // outside may need that type to properly call the export.
209 //
210 // * Since the goal of closedWorld is to optimize types aggressively but
211 // types on the module boundary cannot be changed, we assume the producer
212 // has made a mistake and we consider it a validation error if any user
213 // defined types besides the types of imported or exported functions
214 // themselves appear on the module boundary. For example, no user defined
215 // struct type may be a parameter or result of an exported function. This
216 // error may be relaxed or made more configurable in the future.
217 bool closedWorld = false;
218 // Whether to try to preserve debug info through, which are special calls.
219 bool debugInfo = false;
220 // Whether we are targeting JS. In that case we want to avoid emitting things
221 // in the optimizer that do not translate well to JS, or that could cause us
222 // to need extra lowering work or even a loop (where we optimize to something
223 // that needs lowering, then we lower it, then we can optimize it again to the
224 // original form).
225 bool targetJS = false;
226 // Arbitrary string arguments from the commandline, which we forward to
227 // passes.
228 std::unordered_map<std::string, std::string> arguments;
229 // Passes to skip and not run.
230 std::unordered_set<std::string> passesToSkip;
231
232 // Effect info computed for functions. One pass can generate this and then
233 // other passes later can benefit from it. It is up to the sequence of passes
234 // to update or discard this when necessary - in particular, when new effects
235 // are added to a function this must be changed or we may optimize
236 // incorrectly (however, it is extremely rare for a pass to *add* effects;
237 // passes normally only remove effects).
238 std::shared_ptr<FuncEffectsMap> funcEffectsMap;
239
240 // -Os is our default
241 static constexpr const int DEFAULT_OPTIMIZE_LEVEL = 2;
242 static constexpr const int DEFAULT_SHRINK_LEVEL = 1;
243
244 void setDefaultOptimizationOptions() {
245 optimizeLevel = DEFAULT_OPTIMIZE_LEVEL;
246 shrinkLevel = DEFAULT_SHRINK_LEVEL;
247 }
248
249 static PassOptions getWithDefaultOptimizationOptions() {
250 PassOptions ret;
251 ret.setDefaultOptimizationOptions();
252 return ret;
253 }
254
255 static PassOptions getWithoutOptimization() {
256 return PassOptions(); // defaults are to not optimize
257 }
258
259 bool hasArgument(std::string key) { return arguments.count(key) > 0; }
260
261 std::string getArgument(std::string key, std::string errorTextIfMissing) {
262 if (!hasArgument(key)) {
263 Fatal() << errorTextIfMissing;
264 }
265 return arguments[key];
266 }
267
268 std::string getArgumentOrDefault(std::string key, std::string default_) {
269 if (!hasArgument(key)) {
270 return default_;
271 }
272 return arguments[key];
273 }
274};
275
276//
277// Runs a set of passes, in order
278//
279struct PassRunner {
280 Module* wasm;
281 MixedArena* allocator;
282 std::vector<std::unique_ptr<Pass>> passes;
283 PassOptions options;
284
285 PassRunner(Module* wasm) : wasm(wasm), allocator(&wasm->allocator) {}
286 PassRunner(Module* wasm, PassOptions options)
287 : wasm(wasm), allocator(&wasm->allocator), options(options) {}
288
289 // no copying, we control |passes|
290 PassRunner(const PassRunner&) = delete;
291 PassRunner& operator=(const PassRunner&) = delete;
292
293 virtual ~PassRunner() = default;
294
295 // But we can make it easy to create a nested runner
296 // TODO: Go through and use this in more places
297 explicit PassRunner(const PassRunner* runner)
298 : wasm(runner->wasm), allocator(runner->allocator),
299 options(runner->options), isNested(true) {}
300
301 void setDebug(bool debug) {
302 options.debug = debug;
303 // validate everything by default if debugging
304 options.validateGlobally = debug;
305 }
306 void setDebugInfo(bool debugInfo) { options.debugInfo = debugInfo; }
307 void setValidateGlobally(bool validate) {
308 options.validateGlobally = validate;
309 }
310
311 // Add a pass using its name.
312 void add(std::string passName) {
313 doAdd(PassRegistry::get()->createPass(passName));
314 }
315
316 // Add a pass given an instance.
317 void add(std::unique_ptr<Pass> pass) { doAdd(std::move(pass)); }
318
319 // Adds the pass if there are no DWARF-related issues. There is an issue if
320 // there is DWARF and if the pass does not support DWARF (as defined by the
321 // pass returning true from invalidatesDWARF); otherwise, if there is no
322 // DWARF, or the pass supports it, the pass is added.
323 // In contrast to add(), add() will always add the pass, and it will print a
324 // warning if there is an issue with DWARF. This method is useful for a pass
325 // that is optional, to avoid adding it and therefore avoid getting the
326 // warning.
327 void addIfNoDWARFIssues(std::string passName);
328
329 // Adds the default set of optimization passes; this is
330 // what -O does.
331 void addDefaultOptimizationPasses();
332
333 // Adds the default optimization passes that work on
334 // individual functions.
335 void addDefaultFunctionOptimizationPasses();
336
337 // Adds the default optimization passes that work on
338 // entire modules as a whole, and make sense to
339 // run before function passes.
340 void addDefaultGlobalOptimizationPrePasses();
341
342 // Adds the default optimization passes that work on
343 // entire modules as a whole, and make sense to
344 // run after function passes.
345 // This is run at the very end of the optimization
346 // process - you can assume no other opts will be run
347 // afterwards.
348 void addDefaultGlobalOptimizationPostPasses();
349
350 // Run the passes on the module
351 void run();
352
353 // Run the passes on a specific function
354 void runOnFunction(Function* func);
355
356 // When running a pass runner within another pass runner, this
357 // flag should be set. This influences how pass debugging works,
358 // and may influence other things in the future too.
359 void setIsNested(bool nested) { isNested = nested; }
360
361 // BINARYEN_PASS_DEBUG is a convenient commandline way to log out the toplevel
362 // passes, their times, and validate between each pass.
363 // (we don't recurse pass debug into sub-passes, as it
364 // doesn't help anyhow and also is bad for e.g. printing
365 // which is a pass)
366 // this method returns whether we are in passDebug mode, and which value:
367 // 1: log out each pass that we run, and validate in between (can pass
368 // --no-validation to skip validation).
369 // 2: like 1, and also save the last pass's output, so if breakage happens we
370 // can print a useful error. also logs out names of nested passes.
371 // 3: like 1, and also dumps out byn-* files for each pass as it is run.
372 static int getPassDebug();
373
374 // Returns whether a pass by that name will remove debug info.
375 static bool passRemovesDebugInfo(const std::string& name);
376
377protected:
378 virtual void doAdd(std::unique_ptr<Pass> pass);
379
380private:
381 // Whether this is a nested pass runner.
382 bool isNested = false;
383
384 // Whether the passes we have added so far to be run (but not necessarily run
385 // yet) have removed DWARF.
386 bool addedPassesRemovedDWARF = false;
387
388 // Whether this pass runner has run. A pass runner should only be run once.
389 bool ran = false;
390
391 void runPass(Pass* pass);
392 void runPassOnFunction(Pass* pass, Function* func);
393
394 // After running a pass, handle any changes due to
395 // how the pass is defined, such as clearing away any
396 // temporary data structures that the pass declares it
397 // invalidates.
398 // If a function is passed, we operate just on that function;
399 // otherwise, the whole module.
400 void handleAfterEffects(Pass* pass, Function* func = nullptr);
401
402 bool shouldPreserveDWARF();
403};
404
405//
406// Core pass class
407//
408class Pass {
409 PassRunner* runner = nullptr;
410 friend PassRunner;
411
412public:
413 virtual ~Pass() = default;
414
415 // Implement this with code to run the pass on the whole module
416 virtual void run(Module* module) { WASM_UNREACHABLE("unimplemented"); }
417
418 // Implement this with code to run the pass on a single function, for
419 // a function-parallel pass
420 virtual void runOnFunction(Module* module, Function* function) {
421 WASM_UNREACHABLE("unimplemented");
422 }
423
424 // Function parallelism. By default, passes are not run in parallel, but you
425 // can override this method to say that functions are parallelizable. This
426 // should always be safe *unless* you do something in the pass that makes it
427 // not thread-safe; in other words, the Module and Function objects and
428 // so forth are set up so that Functions can be processed in parallel, so
429 // if you do not add global state that could be raced on, your pass could be
430 // function-parallel.
431 //
432 // Function-parallel passes create an instance of the Walker class per
433 // function. That means that you can't rely on Walker object properties to
434 // persist across your functions, and you can't expect a new object to be
435 // created for each function either (which could be very inefficient).
436 //
437 // It is valid for function-parallel passes to read (but not modify) global
438 // module state, like globals or imports. However, reading other functions'
439 // contents is invalid, as function-parallel tests can be run while still
440 // adding functions to the module.
441 virtual bool isFunctionParallel() { return false; }
442
443 // This method is used to create instances per function for a
444 // function-parallel pass. You may need to override this if you subclass a
445 // Walker, as otherwise this will create the parent class.
446 virtual std::unique_ptr<Pass> create() { WASM_UNREACHABLE("unimplenented"); }
447
448 // Whether this pass modifies the Binaryen IR in the module. This is true for
449 // most passes, except for passes that have no side effects, or passes that
450 // only modify other things than Binaryen IR (for example, the Stack IR
451 // passes only modify that IR).
452 // This property is important as if Binaryen IR is modified, we need to throw
453 // out any Stack IR - it would need to be regenerated and optimized.
454 virtual bool modifiesBinaryenIR() { return true; }
455
456 // Some passes modify the wasm in a way that we cannot update DWARF properly
457 // for. This is used to issue a proper warning about that.
458 virtual bool invalidatesDWARF() { return false; }
459
460 // Whether this pass modifies Binaryen IR in ways that may require fixups for
461 // non-nullable locals to validate according to the wasm spec. If the pass
462 // adds locals not in that form, or moves code around in ways that might break
463 // that validation, this must return true. In that case the pass runner will
464 // automatically run the necessary fixups afterwards.
465 //
466 // For more details see the LocalStructuralDominance class.
467 virtual bool requiresNonNullableLocalFixups() { return true; }
468
469 std::string name;
470
471 PassRunner* getPassRunner() { return runner; }
472 void setPassRunner(PassRunner* runner_) {
473 assert((!runner || runner == runner_) && "Pass already had a runner");
474 runner = runner_;
475 }
476
477 PassOptions& getPassOptions() { return runner->options; }
478
479protected:
480 Pass() = default;
481 Pass(Pass&) = default;
482 Pass& operator=(const Pass&) = delete;
483};
484
485//
486// Core pass class that uses AST walking. This class can be parameterized by
487// different types of AST walkers.
488//
489template<typename WalkerType>
490class WalkerPass : public Pass, public WalkerType {
491
492protected:
493 using super = WalkerPass<WalkerType>;
494
495public:
496 void run(Module* module) override {
497 assert(getPassRunner());
498 // Parallel pass running is implemented in the PassRunner.
499 if (isFunctionParallel()) {
500 // Reduce opt/shrink levels to a maximum of one in nested runners like
501 // these, to balance runtime. We definitely want the full levels in the
502 // main passes we run, but nested pass runners are of secondary
503 // importance.
504 // TODO Investigate the impact of allowing the levels to just pass
505 // through. That seems to cause at least some regression in compile
506 // times in -O3, however, but with careful measurement we may find
507 // the benefits are worth it. For now -O1 is a reasonable compromise
508 // as it has basically linear runtime, unlike -O2 and -O3.
509 auto options = getPassOptions();
510 options.optimizeLevel = std::min(options.optimizeLevel, 1);
511 options.shrinkLevel = std::min(options.shrinkLevel, 1);
512 PassRunner runner(module, options);
513 runner.setIsNested(true);
514 runner.add(create());
515 runner.run();
516 return;
517 }
518 // Single-thread running just calls the walkModule traversal.
519 WalkerType::walkModule(module);
520 }
521
522 // Utility for ad-hoc running.
523 void run(PassRunner* runner, Module* module) {
524 setPassRunner(runner);
525 run(module);
526 }
527
528 void runOnFunction(Module* module, Function* func) override {
529 assert(getPassRunner());
530 WalkerType::walkFunctionInModule(func, module);
531 }
532
533 // Utility for ad-hoc running.
534 void runOnFunction(PassRunner* runner, Module* module, Function* func) {
535 setPassRunner(runner);
536 runOnFunction(module, func);
537 }
538
539 void runOnModuleCode(PassRunner* runner, Module* module) {
540 setPassRunner(runner);
541 WalkerType::walkModuleCode(module);
542 }
543};
544
545} // namespace wasm
546
547#endif // wasm_pass_h
548

source code of dart_sdk/third_party/binaryen/src/src/pass.h