Skip to content

Implemented inlining history and use it inside inlining reports#365

Merged
poechsel merged 7 commits intooxcaml:mainfrom
poechsel:inlining-reports
Feb 21, 2022
Merged

Implemented inlining history and use it inside inlining reports#365
poechsel merged 7 commits intooxcaml:mainfrom
poechsel:inlining-reports

Conversation

@poechsel
Copy link
Copy Markdown
Contributor

@poechsel poechsel commented Nov 2, 2021

An Inlining_history is the history of all operations the compiler did before a term (in our case either a function definition or a function call) was produced.

For example take the following piece of code:

 (* A.ml *)
let foo arg =
    let[@inline never] bar arg = .... in
    bar x
let baz_1 x = foo x
let baz_2 x = (foo [@@inlined never]) x

After simplify if the call to foo inside baz_1 was inlined then a new closure (bar) and a new call (bar) will appear. In that case the inlining history of this new call to bar will be "Call to the function (bar that has been introduced after inlining baz_1.foo), which itself has been introduced after inlining baz_1.foo)".

Once we got a list of inlining history it is possible to reconstruct the inlining tree, which is the tree of all decisions made by the inliner.
For the previous piece of code the inlining tree will be:

   Module A
   ├─► Declaration of Function [foo]
   │   │ Deemed inlinable
   │   ├─► Declaration of function [bar]
   │   │   │ Deemed as non inlinable
   │   └─► Call to [bar]
   │       │ Non inlined because the callee was deemed to be non inlinable
   └─► Definition of [baz_1]
       │ Deemed inlinable
       ├─► Call to [foo]
       │   │ Inlined
       │   ├─► Declaration of function [bar]
       │   │   │ Deemed as non inlinable
       │   └─► Call to [bar] that was first defined at [foo.bar]
       │       │ Non inlined because the callee was deemed to be non inlinable
       └─► Call to [foo]
           │ Not inlined because of an annotation

This inlining tree can then be displayed using the inlining reports.

More technically, the Inlining history are represented using the type

 type path = private
    | Empty
    | Unknown of { prev : path }
    | Function of
        { dbg : Debuginfo.t;
          name : string;
          prev : path
        }
    | Module of
        { name : string;
          prev : path
        }
    | Class of
        { name : string;
          prev : path
        }
    | Call of
        { dbg : Debuginfo.t;
          callee : t;
          prev : path
        }
    | Inline of { prev : path }

The inlining history is computed using two elements:

  • The absolute history, stored in the env, and that tracks the absolute history between the toplevel and the last term where a decision was made
  • The relative history, stored on function declarations and apply nodes which track the history relative to the previous function declaration.
    When a call gets inlined its relative history is transmitted to the function declarations and apply nodes that are created as a result.

The inlining reports were rewritten to use the inlining histories of the recorded decisions. They are not perfect and will be improved (Most notably, I want to add a system of link to move easily between apply node and the corresponding decision) but are nevertheless usable.

Here is an example of the new inlining reports (made for the file middle_end/compilation_unit.ml):
compilation_unit.0.inlining.org.txt

lukemaurer
lukemaurer requested changes Nov 3, 2021
View reviewed changes
@mshinwell mshinwell added the flambda2 Prerequisite for, or part of, flambda2 label Nov 5, 2021
@poechsel poechsel force-pushed the inlining-reports branch 3 times, most recently from 0a4c01e to cd9c86e Compare November 30, 2021 15:50
lukemaurer
lukemaurer reviewed Feb 16, 2022
View reviewed changes
lukemaurer
lukemaurer reviewed Feb 17, 2022
View reviewed changes
lukemaurer
lukemaurer reviewed Feb 18, 2022
View reviewed changes
mshinwell
mshinwell requested changes Feb 21, 2022
View reviewed changes
@poechsel poechsel merged commit 18e474d into oxcaml:main Feb 21, 2022
mshinwell pushed a commit that referenced this pull request Mar 3, 2022
@poechsel @mshinwell
Implemented inlining history and use it inside inlining reports (#365)
c2d3dc9 
* Implemented inlining history

* Add links between apply node and there respective function declaration

* Fix formatting for inlining arguments

* Inlining reports are now showing all decisions taken for any paths, making them work both with simplify and closure conversion
stedolan added a commit to stedolan/flambda-backend that referenced this pull request Mar 7, 2022
@stedolan
Squashed 'ocaml/' changes from 173842c..64235a3
c6bb9c5 
64235a3 flambda-backend: Change Float.nan from sNaN to qNaN (oxcaml#466)
14a8e27 flambda-backend: Track GC work for all managed bigarray allocations (upstream 11022) (oxcaml#569)
c3cda96 flambda-backend: Add two new methods to targetint for dwarf (oxcaml#560)
e6f1fed flambda-backend: Handle arithmetic overflow in select_addr (oxcaml#570)
dab7209 flambda-backend: Add Target_system to ocaml/utils (oxcaml#542)
82d5044 flambda-backend: Enhance numbers.ml with more primitive types (oxcaml#544)
216be99 flambda-backend: Fix flambda_o3 and flambda_oclassic attributes (oxcaml#536)
4b56e07 flambda-backend: Test naked pointer root handling (oxcaml#550)
40d69ce flambda-backend: Stop local function optimisation from moving code into function bodies; opaque_identity fixes for class compilation (oxcaml#537)
f08ae58 flambda-backend: Implemented inlining history and use it inside inlining reports (oxcaml#365)
ac496bf flambda-backend: Disable the local keyword in typing (oxcaml#540)
7d46712 flambda-backend: Bugfix for Typedtree generation of arrow types (oxcaml#539)
61a7b47 flambda-backend: Insert missing page table check in roots_nat.c (oxcaml#541)
323bd36 flambda-backend: Compiler error when -disable-all-extensions and -extension are used (oxcaml#534)
d8956b0 flambda-backend: Persistent environment and reproducibility (oxcaml#533)
4a0c89f flambda-backend: Revert "Revert bswap PRs (480 and 482)" (oxcaml#506)
7803705 flambda-backend: Cause a C warning when CAMLreturn is missing in C stubs. (oxcaml#376)
6199db5 flambda-backend: Improve unboxing during cmm for Flambda (oxcaml#295)
96b9e1b flambda-backend: Print diagnostics at runtime for Invalid (oxcaml#530)
42ab88e flambda-backend: Disable bytecode compilers in ocamltest (oxcaml#504)
58c72d5 flambda-backend: Backport ocaml/ocaml#10595 from upstream/trunk (oxcaml#471)
1010539 flambda-backend: Use C++ name mangling convention (oxcaml#483)
81881bb flambda-backend: Local allocation test no longer relies on lifting (oxcaml#525)
f5c4719 flambda-backend: Fix an assertion in Closure that breaks probes (oxcaml#505)
c2cf2b2 flambda-backend: Add some missing command line arguments to ocamlnat (oxcaml#499)

git-subtree-dir: ocaml
git-subtree-split: 64235a3
stedolan added a commit that referenced this pull request Mar 7, 2022
@stedolan
Squashed 'ocaml/' changes from 173842c..64235a3
b54d3a3 
64235a3 flambda-backend: Change Float.nan from sNaN to qNaN (#466)
14a8e27 flambda-backend: Track GC work for all managed bigarray allocations (upstream 11022) (#569)
c3cda96 flambda-backend: Add two new methods to targetint for dwarf (#560)
e6f1fed flambda-backend: Handle arithmetic overflow in select_addr (#570)
dab7209 flambda-backend: Add Target_system to ocaml/utils (#542)
82d5044 flambda-backend: Enhance numbers.ml with more primitive types (#544)
216be99 flambda-backend: Fix flambda_o3 and flambda_oclassic attributes (#536)
4b56e07 flambda-backend: Test naked pointer root handling (#550)
40d69ce flambda-backend: Stop local function optimisation from moving code into function bodies; opaque_identity fixes for class compilation (#537)
f08ae58 flambda-backend: Implemented inlining history and use it inside inlining reports (#365)
ac496bf flambda-backend: Disable the local keyword in typing (#540)
7d46712 flambda-backend: Bugfix for Typedtree generation of arrow types (#539)
61a7b47 flambda-backend: Insert missing page table check in roots_nat.c (#541)
323bd36 flambda-backend: Compiler error when -disable-all-extensions and -extension are used (#534)
d8956b0 flambda-backend: Persistent environment and reproducibility (#533)
4a0c89f flambda-backend: Revert "Revert bswap PRs (480 and 482)" (#506)
7803705 flambda-backend: Cause a C warning when CAMLreturn is missing in C stubs. (#376)
6199db5 flambda-backend: Improve unboxing during cmm for Flambda (#295)
96b9e1b flambda-backend: Print diagnostics at runtime for Invalid (#530)
42ab88e flambda-backend: Disable bytecode compilers in ocamltest (#504)
58c72d5 flambda-backend: Backport ocaml/ocaml#10595 from upstream/trunk (#471)
1010539 flambda-backend: Use C++ name mangling convention (#483)
81881bb flambda-backend: Local allocation test no longer relies on lifting (#525)
f5c4719 flambda-backend: Fix an assertion in Closure that breaks probes (#505)
c2cf2b2 flambda-backend: Add some missing command line arguments to ocamlnat (#499)

git-subtree-dir: ocaml
git-subtree-split: 64235a3
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

@lukemaurer lukemaurer lukemaurer approved these changes

@mshinwell mshinwell mshinwell approved these changes

@Gbury Gbury Awaiting requested review from Gbury

@lthls lthls Awaiting requested review from lthls

Assignees

No one assigned

Labels

flambda2 Prerequisite for, or part of, flambda2

Projects

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

3 participants

@poechsel @lukemaurer @mshinwell