[aclements]

Go already performs cross-package inlining, so it can already inline library calls. (This is relatively easy to do in Go compared to other languages because packages must form a DAG. Compiling package A writes out enough information in the object file for A that compiling package B that depends on A can inline calls to functions in A.)

[pcwalton]

> This is relatively easy to do in Go compared to other languages because packages must form a DAG.

That doesn't make sense to me. The complicated part is storing the IR in packages in a form that can be read back into the compiler later. That's needed to do inlining at all. Once you have that done, doing LTO is trivial: you just slurp your IR for all modules linked together into the compiler and emit a single binary. (You can be fancier, like ThinLTO does, but again, the effort needed to do ThinLTO is independent of whether you have cyclic dependencies or not.)

[DannyBee]

"Compiling package A writes out enough information in the object file for A that compiling package B that depends on A can inline calls to functions in A"

So it records the calling convention, architecture flags, alignment, and other ABI pieces etc? As well as an estimate of instruction-level inlining cost, summary info about arguments, etc, so you effectively decide whether inlining it will help or hurt, without having the IR around to try?

FWIW: Writing out the info is usually not the hard part, actually, and is unrelated to the DAG-ness of the packages.

GCC is just the perennial example here, but they refused to write it out for years for political reasons, not technical ones :)

[aclements]

"So it records the calling convention, architecture flags, alignment, and other ABI pieces etc?"

No. At the moment it records the AST in the object file, because the inliner works at the Go AST level. In the future it may instead record the SSA representation (which would obviously give better cost estimates; the current heuristics are really extremely simple).

"FWIW: Writing out the info is usually not the hard part, actually, and is unrelated to the DAG-ness of the packages."

The DAG-ness means it's always available when compiling the call site, even if it's a cross-package call. It means you don't have to do it at link time.

[DannyBee]

"In the future it may instead record the SSA representation (which would obviously give better cost estimates; the current heuristics are really extremely simple)."

This would be identical to what others do then :)

"The DAG-ness means it's always available when compiling the call site, even if it's a cross-package call. It means you don't have to do it at link time. "

This is unrelated to DAG-ness. Unless you mean something else by DAG-ness. DAG-ness means it's a directed-acyclic graph. That is, all other things being equal, it has no cycles.

This is unrelated to the problem.

For example, in other languages/etc, it could be weakly defined, or other some form of overridable, regardless of whether it has cycles, is actually multiply defined etc. That requires link-time resolution, becuase you can't optimize it making an assumption about its callees/callers, or even inline it, and then just hand that version to others because you may have screwed it up in a way one of those other callers depend on.

That is, the overridability is an attribute of the function, not a problem of how it is used.

Ditto on the ABI, alignment, etc.

None of the interesting problems they have to solve are related to packaging. They occur with DAGs or non-DAGs, are just related to these languages supporting a richer set of things you can do to functions :)

[pcwalton]

> The DAG-ness means it's always available when compiling the call site, even if it's a cross-package call. It means you don't have to do it at link time.

Why is it any harder to do at link time?

(I've implemented this in a production compiler, and choosing whether to do it at compile time or link time was a trivial decision.)

[DannyBee]

traditionally, this required a linker that understands there is ir in the files. in practice, i don't believe this has been a problem for many years now (and again, was only a problem in the open source world, so saying it's related to the language is kind of strange.).

Every good production C++ compiler has had some form of link time optimization for many years.

IBM's, for example, has been happily cross-optimizing between C++, java, fortran, PL/IX, etc without any issues, going on at least 15, maybe 25+ years now (I know it's 15 for sure, i suspect it's closer to 25).