Passes¶
Fundamentally, compiler passes are bits of code that transform or analyze the current IR in some way. For example, a scheduler pass will change the cycle numbers of instructions and possibly reorder them accordingly.
Conceptually, OpenQL’s passes can get a bit more complicated than that, at least internally. Instead of a linear pass list, OpenQL’s pass manager supports a tree of passes (useful for instance to set options for a whole group of passes at once, for establishing logging or performance monitoring regions if that’s ever implemented, or otherwise manipulate a group of passes as if it’s a single pass), and even has basic support for conditional passes, or repeating a group of passes until a condition is true. To support all of this without making simple cases needlessly complex for users, the lifecycle of a pass is nontrivial.
First, the pass is created via an
append_pass()
API call (or equivalent).Options may then be set on the pass via
set_option()
API calls (or equivalent).At some point, the pass is “constructed”. This doesn’t imply C++ construction of the pass class (this happens at the start of this list); rather, this is about the
construct()
method. The user can either call this directly, or the pass manager will do it automatically when needed. During construction, a pass can choose to become a group of passes, rather than staying a single pass. This can be a normal group, a conditional group, a “while” group, or a “repeat until” group. It can make this decision based on its options; therefore, to avoid potential confusion, it’s illegal to change the options of a pass after it has been constructed. Instead, if the pass turned itself into a group, the user is subsequently allowed to modify its list of sub-passes, including setting options directly on the sub-passes, or adding new sub-passes. These sub-passes will eventually be constructed again, repeating this process recursively.If the pass did not turn into a group, it will eventually be “run” for the given IR tree. A single pass may be run multiple times if it’s a sub-pass of a looping block, or it may never be run. If the pass did decide to turn into a group upon construction, the overridable
run()
method is never called; instead, the base class for the pass will ensure that its sub-passes are run appropriately.
As an example of when this might become useful, imagine that eventually the mapper pass is split up into its logical sub-passes, namely optional initial placement, routing, and primitive decomposition. At this point, legacy user code may still assume that the old combined mapper pass exists, and behaves as a single pass within the context of pass management. To support this, the old mapper pass can be defined to construct into a group of its sub-passes, with the initial placement pass added only if initial placement is actually enabled. Now, until the user explicitly constructs the mapper pass (which the old code would have no reason to ever do), the mapper pass behaves exactly as it would have before, i.e. a single pass that can have options applied on it or be deleted, yet the compiler necessarily behaves exactly as if the user had created the initial placement, routing, and primitive decomposition passes manually.
Note
Most of the APIs related to pass groups and management thereof are
currently disabled via the QL_HIERARCHICAL_PASS_MANAGEMENT
preprocessor
directive, explicitly #undef
’d in src/ql/config.h.template
.
Internally, however, everything should already be there.
Implementation¶
Pass classes¶
Pass instances and/or groups of passes are represented by a class that
(ultimately) derives from ql::pmgr::pass_types::Base
. There is no
associated object for a pass type; rather, the C++ type itself is used for the
pass type, so in principle you only have to implement one class to define a
pass.
Passes don’t normally implement ql::pmgr::pass_types::Base
directly.
Instead, they may use:
ql::pmgr::pass_types::Transformation
for regular transformation passes operating on the new IR;
ql::pmgr::pass_types::Analysis
for new-IR passes that don’t change the IR, aside from possibly adding metadata to it via annotations;
ql::pmgr::pass_types::ProgramTransformation
for old-IR passes that transform the complete program in one go;
ql::pmgr::pass_types::KernelTransformation
for old-IR passes that transform one kernel at a time; or
ql::pmgr::pass_types::ProgramAnalysis
for old-IR passes that analyze the complete program in one go.
Note that there is currently no difference between the *Transformation
and
*Analysis
passes, because there is currently no good way to guarantee
constness with the IR tree. They’re really just hints right now.
Most passes override the following methods to define their functionality:
dump_docs(...)
: a dump function that writes the documentation for the pass type. This must not depend on any pass options; it is only called on “virgin” objects (unfortunately, there is no such thing as overriding static methods in C++).
get_friendly_name()
: used by the documentation generation logic to get a user-friendly name for the pass, to use as section header.The constructor: used to define pass-specific options.
run(...)
: actually runs the pass.
The pass class itself is not the correct place to store variables/fields for
the actual algorithm that run()
implements. Instead, if the implementation
of a pass is complex, it’s better to make a detail
namespace for the
pass-specific types and functions, and leave the pass class as a thin wrapper
around it. Ideally, these wrappers (and pass registration) can then ultimately
be generated, preventing a lot of boilerplate code. Even without the generator,
it’s good to have the boilerplate and documentation generation stuff separate
from the actual implementation; the implementation will probably be complex
enough as it is.
The pass factory¶
For a pass type to be usable within a compilation strategy, its class must be
registered with the pass factory (ql::pmgr::Factory
) used to build the
strategy with. While the code is written such that it’s possible for a user
program to eventually make its own pass factory (which would probably be
necessary to let them define their own passes), currently everything just uses
a default-constructed Factory
object initially.
Passes self-register statically to the pass factory using the static register_pass function. This allows the pass factory to not have to depend on and include pass headers. To do that, the pass class needs to declare a static boolean member called (for example) is_pass_registered and defined in a similar way as: .. code-block:: c++
bool ReadCQasmPass::is_pass_registered = pmgr::Factory::register_pass<ReadCQasmPass>(“io.cqasm.Read”);
The template argument (typedefs to) the pass class, while the string argument defines its externally-usable type name.
Note
The C++ namespace path and externally-usable type name path should be kept in sync! Please avoid using differing naming conventions for the two. If needed for backward compatibility, different aliases can be made for the same pass type, but the complement of the C++ name should also be usable as a pass type externally.
Note
The capitalization of the pass types is chosen such to be as familiar as
possible to Python users: the last entry represents a class, while the
remaining period-separated entries represent module names. In C++ it works
the same, except that passes have their own namespace in addition, so you
end up with ...::name::Pass
rather than ...::Name
.
After default-construction, the Factory
object will be “configured” by the
pass manager. During configuration, aliases are added for the
architecture-specific passes of the selected architecture, preventing the user
from having to explicitly prefix these passes using arch.<arch-name>.
. This
mechanism also allows an architecture to override the implementation of a
generic pass if it needs to, without breaking backward compatibility, as
architecture-specific passes take precedence over generic passes when these
aliases are created. Aliases may also be generated for “dnu” (do-not-use)
passes that are explicitly requested by the user.
The pass manager¶
Pass instances are glued together into a pass strategy by the pass manager
(ql::pmgr::Manager
), also known as just the Compiler
in API
terminology. For the most part, this class is just boilerplate around a factory
and a single group pass that represents the first level of the pass group
hierarchy. However, it also contains a bunch of backward compatibility logic
from the olden days when there was no pass management at all by way of the
from_defaults()
and convert_global_to_pass_options()
methods, and the
compiler configuration JSON file loading logic by way of the from_json()
method.
convert_global_to_pass_options()
especially requires a bit of attention,
because its implementation is currently very stupid: whenever a global option
is defined, it effectively calls set_option()
on any default pass that
has an option going by the (converted) global option name. This may not be
good enough when more passes are added eventually; for example, if multiple
passes have a heuristic
option, the global option conversion logic has no
way of only setting the option for a particular pass type (incidentally, this
is why the scheduler heuristic pass option is redundantly named
scheduler_heuristic
instead).
Adding a new pass¶
Having read the above, adding a new pass should be a fairly straightforward process. Nevertheless, here’s a checklist that should handle the common cases.
Figure out what you want to call the pass, keeping in mind the naming conventions and organizing groups (i.e.
ana
,io
,map
,opt
, andsch
, see namespaces).Create a source file for the pass corresponding to the pass type you settled on in
src/ql/pass
, and an accompanying header file ininclude/ql/pass
. The contents can mostly be copypasted from existing passes; much of it is boilerplate.Derive from the right base class for your pass (probably
Transformation
orAnalysis
). If needed, change the prototype of therun()
function accordingly.Implement the documentation generation functions. If you can’t be bothered to put anything useful there until you’re done with the implementation yet then that’s on you, but at least put a one-liner placeholder there. Don’t just copypaste the documentation of another pass!
Update the constructor to define the pass options you want for your pass.
Put an appropriate placeholder in
run()
, such asQL_ICE("not yet implemented")
.Register your pass with the pass factory by calling the factory’s static method register_pass and storing its result.
At this point, you should have everything needed for the user to be able to create the pass, and for the documentation generation system to detect and add it.
If you want the pass to become part of the default pass list, add it to
ql::pmgr::Manager::from_defaults()
. Note that it should probably be guarded by a global option that defaults to not inserting the pass for backward compatibility; these are defined inql::com::options::make_ql_options()
.If you want the pass to become part of an architecture-specific default pass list, add it to the
populate_backend_passes()
method of itsInfo
class.Actually implement and document the pass. If the implementation is complex, it should be put in a
detail
namespace within the pass namespace, with all (private!) header files and source files in thesrc
directory. Any header file that must be public or is used elsewhere within OpenQL, for example one containing annotation types that other passes may want to do something with as well, should not be indetail
;detail
is your private implementation, anything outside of it is public.