[RFC] Modular native-code backends by nojb · Pull Request #634 · ocaml/ocaml

nojb · 2016-06-24T22:59:10Z

TL;DR: a refactoring of the native code generator to allow switching the native-code backends at run-time. Submitting PR in order to gather feedback on the proposed approach.

Motivation

Cross-compilation support Support for multiple native code builds of the stdlib, compilerlibs and otherlibs #620
Plug-in native-code backends MPR #6696
Compile all backends for testing (this is already possible using a special Makefile target)
... ?

Current approach

The native-code generator is organised in two parts: a more-or-less architecture-independent part in asmcomp/ and architecture-dependent files in each one of the subdirectories asmcomp/<arch> (where arch is amd64, arm, etc.).

When ./configure is run it symlinks the files of the host architecture asmcomp/<arch> to asmcomp/ itself. These modules are: Arch, Proc, Selection, Reload, CSE, Emit, Scheduling. The compiler never needs to know that there is more than one native-code backend available. This is simple and convenient because the architecture-independent and dependant parts are tightly wound together.

Instead of doing this "linking trick" we want to be able to consider all backends at the same time and to choose them at run-time.

Proposed approach

We propose to use functors. However it is not completely trivial to do this because there are circular dependencies between the architecture-independent parts and architecture dependent ones as a whole.

Furthermore, one of the main types used throughout the compiler back-end, Mach.{instruction, operation, ...} uses in its definition the types Arch.addressing_mode and Arch.specific_operation which are architecture-dependent. If we make Mach into a functor then every single module out there that uses Mach will need to become a functor of Mach or re-instantiate Mach in order to do its work. This quickly leads to a lot of complexity.

To break this chain of dependencies, we make the type Mach.operation polymorphic:

type ('addressing_mode, 'specific_operation) operation =
  | Ispecific of 'specific_operation
  | ...

Adapt Printmach and Printlinear to deal with this extra polymorphism (extra arguments for 'addressing_mode and 'specific_operation printers, etc.).
New modules Arch_intf and Proc_intf containing signatures for Arch and Proc modules.
The modules Selectgen, Schedgen, Reloadgen, CSEgen which are used to build the architecture-dependent Selection Scheduling Reload, CSE now are functors of Arch and/or Proc.
A new signature for native-code backends in Native_backend_intf:

module type S = sig
  module Arch : Arch_intf.S
  module Proc : Proc_intf.S with type addressing_mode = Arch.addressing_mode
                             and type specific_operation = Arch.specific_operation

  type fundecl = (Arch.addressing_mode, Arch.specific_operation) Mach.fundecl
  type linearize_fundecl = (Arch.addressing_mode, Arch.specific_operation) Linearize.fundecl

  module Reload : sig
    val fundecl: fundecl -> fundecl * bool
  end
  module Scheduling : sig
    val fundecl: linearize_fundecl -> linearize_fundecl
  end
  module Selection : sig
    val fundecl: Cmm.fundecl -> fundecl
  end
  module CSE : sig
    val fundecl: fundecl -> fundecl
  end
  module Emit : sig
    module Emitaux : Emitaux.S
    val fundecl: linearize_fundecl -> unit
    val data: Cmm.data_item list -> unit
    val begin_assembly: unit -> unit
    val end_assembly: unit -> unit
  end
end

The module Asmgen is a functor of Native_backend_intf.S. Its body instantiates:

module Cmmgen = Cmmgen.Make (Arch) (Proc)
module Closure = Closure.Make (Arch)
module Interf = Interf.Make (Proc)
module Spill = Spill.Make (Proc)
module Comballoc = Comballoc.Make (Arch)
module Coloring = Coloring.Make (Proc)
module Deadcode = Deadcode.Make (Proc)
module Liveness = Liveness.Make (Proc)

Amspackager and Asmlink become functors parametrised by Asmgen.

Current state

A first proof of concept is working (hardcoded for amd64, see driver/optmain.ml).
Sometimes the dependency on Arch or Proc is very small (just a few constants). We could turn some of these functors into functions taking first class modules, which seems lighter.
For simplicity and to reduce the diff I simply wrapped many modules completely in a functor. Often this is overkill in that only a small part of the module needs to be functorized. This needs a second pass to clean up.
... Suggestions, ideas, comments, etc ?

Thanks!

/cc @alainfrisch

gasche · 2016-06-26T19:01:41Z

I find your presentation of the change informative and interesting, but it is difficult to review the code itself because the whole diff starts with lines and lines of .depend operation (maybe remove that from a first patch?) making it painful to scroll, and individual commits are a bit of a mess. Maybe a rebase would help assess the design?

(I don't know where to look to easily read the changes to driver/optmain.ml for example, or where to find examples of functions that could be turned into functions, etc.)

I guess the person whose feedback would matter most in this case is @xavierleroy , that I suppose decided the original organisation of this part of the codebase.

It's a minor detail, but I think the signature Native_backend_intf.S would be more readable if it had its own abstract type components addressing_mode and specific_operation to which both Proc and Arch were equated.

nojb · 2016-06-26T19:05:06Z

Hi @gasche, thanks for the comments. I will clean up the pull request to make it easier to read.

We add two type arguments: type ('addr, 'op) operation where 'addr corresponds to Arch.addressing_mode and 'op to Arch.specific_operation (for any architecture-dependent Arch module).

Printing functions for Mach.{operation, instruction, ...} (idem for Linearize) now take extra printer parameters to print the 'addr, 'op type arguments. Additionally they take an argument of type int -> string which is used to print register names (this corresponds to Proc.register_name). This is done to avoid a dependency on architecture-dependent Proc modules.

These interfaces define the interface between the architecture-independent part of the native-code generator and the architecture-dependent parts.

The following modules are made functors of Arch and/or Proc: CSEgen Schedgen Selectgen (Reloadgen does not need to be functorized) Interf Spill Comballoc Coloring Deadcode Liveness The first group of modules are used by each native-code backend to implement their own functionality. The rest of the modules are used "internally" by the Asmgen module.

This is the signature to be implemented by native-code backends. It corresponds to the files normally found in asmcomp/amd64, asmcomp/arm, etc. This signature will be used as the argument type for the Asmgen functor.

Asmgen becomes a functor of Native_backend_intf. Asmlink and Asmpackager become functors of Asmgen. Instead of functorizing these modules we could use first class modules passed as function arguments.

We rename every module in asmcomp/amd64 with a prefix since they are to coexist with other backends. Also update Makefile not to symlink these modules into asmcomp and to generate the *_emit.ml files at asmcomp/<arch>/<arch>_emit.ml.

These modules all depend on Arch or Proc. Since the dependence is only on values (not on types), it may be better to pass the necessary modules as a function argument as needed. For simplicity we use functors for now.

This is better than making Closure a functor of Arch.

nojb · 2016-06-26T22:41:56Z

Removed .depend from the patch
Cleaned up the commits to make them easier to read.
Switched Closure to use first-class modules instead of a functor as an example of my comment above. The same could be done with Cmmgen for example.

nojb · 2016-06-26T22:43:31Z

Also found the following slides by @xavierleroy which are relevant for this PR: http://gallium.inria.fr/~xleroy/talks/icfp99.ps.gz.

gasche · 2016-06-26T23:01:45Z

I find the use of first-class module in ca1327a a regression rather than an improvement.

It uses first-class modules rather than functors, so it is more complex -- all things being equal, the simpler features used the better.
The change is in fact much more invasive as the arch parameter needs to be threaded down the whole call chain to the function using it, and using the information in another leaf function in the future would again require an invasive internal change.
It breaks the homogeneity in handling with respect to other parts of the backend. Having the exact same structure in each module has advantages, for example it suggest that if a feature such as functor-pack became available we could easily use it here.

I think it's very good that you made this experiment but, to my personal taste, the results are less convincing than the pure-functor approach.

chambart · 2016-06-30T12:43:41Z

asmcomp/proc_intf.ml

+  val contains_calls: bool ref
+  val assemble_file: string -> string -> int
+  val init : unit -> unit
+end


This file should contain the documentation that was previously in Proc.
Note that it is often a good idea to have both an .ml and .mli file in the compiler sources to avoid parallel build problems.

Indeed! I will put it back and add the .mli as well. Thanks!

chambart · 2016-06-30T13:02:18Z

This feature is a clear improvement without serious problems. It will also simplify the maintenance of the various less used backends. I am strongly in favor.

For the code itself I didn't seriously review this patch yet, but from a quick scan, this looks like a safe change: this is moving things around, the scary parts of the backend is unchanged, and there is no risk of mix between backends as the specific instruction type prevents it.

There may be some concerns with integers size, and the value of some backend specific values (like compile time constants). But this can be addressed in a later patch.

xavierleroy · 2016-12-04T16:43:58Z

Functorizing the native-code generator over Arch and Proc is one of the first things I tried back in 1994 while writing what was to become ocamlopt. At that time, I found that it made the code harder to write, to read, and to maintain than the "redneck functor" approach (playing with -I and multiple source files) that we still use today. This hasn't improved since then, and I still prefer not to functorize this code.

nojb · 2016-12-04T17:29:03Z

Thanks for the comment. That was the impression I got as well. Closing!

nojb added 4 commits June 26, 2016 21:15

Make Mach.operation polymorphic

86d43d1

We add two type arguments: type ('addr, 'op) operation where 'addr corresponds to Arch.addressing_mode and 'op to Arch.specific_operation (for any architecture-dependent Arch module).

Add Arch_intf, Proc_intf

b48359c

These interfaces define the interface between the architecture-independent part of the native-code generator and the architecture-dependent parts.

nojb force-pushed the modular-native-backends branch 3 times, most recently from 6ece5ad to 62f0538 Compare June 26, 2016 22:26

nojb added 6 commits June 27, 2016 00:36

Add Native_backend_intf

5aa00af

This is the signature to be implemented by native-code backends. It corresponds to the files normally found in asmcomp/amd64, asmcomp/arm, etc. This signature will be used as the argument type for the Asmgen functor.

Functorize Asmgen, Asmlink, Asmpackager

1720ddf

Asmgen becomes a functor of Native_backend_intf. Asmlink and Asmpackager become functors of Asmgen. Instead of functorizing these modules we could use first class modules passed as function arguments.

Rename asmcomp/amd64/*, update Makefile

d45d3ec

We rename every module in asmcomp/amd64 with a prefix since they are to coexist with other backends. Also update Makefile not to symlink these modules into asmcomp and to generate the *_emit.ml files at asmcomp/<arch>/<arch>_emit.ml.

Functorize Closure, Cmmgen, Strmatch, ...

1dfcbdd

These modules all depend on Arch or Proc. Since the dependence is only on values (not on types), it may be better to pass the necessary modules as a function argument as needed. For simplicity we use functors for now.

Do not re-export Emit, Emitaux inside Asmgen

1b23b66

Pass Arch as a function argument to Closure.intro.

ca1327a

This is better than making Closure a functor of Arch.

nojb force-pushed the modular-native-backends branch from 62f0538 to ca1327a Compare June 26, 2016 22:38

chambart reviewed Jun 30, 2016
View reviewed changes

Restore Proc comments

463bb50

nojb force-pushed the modular-native-backends branch from aa8f137 to 463bb50 Compare June 30, 2016 19:47

Re-export only used funs of Cmmgen in Asmgen

1687691

gasche mentioned this pull request Jul 1, 2016

Labels after calls, call GC points and checkbound points #644

Merged

mshinwell mentioned this pull request Jul 6, 2016

Add cplugins and add a configure option -fPIC #668

Merged

nojb closed this Dec 4, 2016

nojb deleted the modular-native-backends branch February 24, 2017 09:11

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

[RFC] Modular native-code backends#634

[RFC] Modular native-code backends#634
nojb wants to merge 12 commits intoocaml:trunkfrom
nojb:modular-native-backends

nojb commented Jun 24, 2016 •

edited

Loading

Uh oh!

gasche commented Jun 26, 2016

Uh oh!

nojb commented Jun 26, 2016

Uh oh!

nojb commented Jun 26, 2016

Uh oh!

nojb commented Jun 26, 2016

Uh oh!

gasche commented Jun 26, 2016

Uh oh!

chambart Jun 30, 2016

Uh oh!

nojb Jun 30, 2016

Uh oh!

chambart commented Jun 30, 2016

Uh oh!

xavierleroy commented Dec 4, 2016

Uh oh!

nojb commented Dec 4, 2016

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

4 participants

Conversation

nojb commented Jun 24, 2016 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Motivation

Current approach

Proposed approach

Current state

Uh oh!

gasche commented Jun 26, 2016

Uh oh!

nojb commented Jun 26, 2016

Uh oh!

nojb commented Jun 26, 2016

Uh oh!

nojb commented Jun 26, 2016

Uh oh!

gasche commented Jun 26, 2016

Uh oh!

chambart Jun 30, 2016

Choose a reason for hiding this comment

Uh oh!

nojb Jun 30, 2016

Choose a reason for hiding this comment

Uh oh!

chambart commented Jun 30, 2016

Uh oh!

xavierleroy commented Dec 4, 2016

Uh oh!

nojb commented Dec 4, 2016

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

4 participants

nojb commented Jun 24, 2016 •

edited

Loading