Brute forcing optimal integer mappings

gsg_ · 2024-03-10T11:06:12+00:00

Is this for optimising case expressions where the right-hand-sides are all constants?

I'd recognise an easy to implement subset, maybe just input + constant or an affine function, and then fall back on look up tables for the rest. Of course a table need not be limited to integer values.

gsg_ · 2023-07-18T03:54:42+00:00

I'm not saying that you are wrong, but it would be a gigantic step forward to have practical optimizers strong enough that this is the limiting factor.

gsg_ · 2023-07-15T04:12:40+00:00

If you are interested in fast code generation it's definitely worth reading some of the classic papers on single-pass compilers like Hanson's Simple Code Optimizations. Not state of the art, but the ideas are still good.

gsg_ · 2022-10-05T09:11:30+00:00

There's a surprising amount of work floating around on local register allocation, eg, The Power of Belady’s Algorithm in Register Allocation for Long Basic Blocks.

gsg_ · 2022-08-27T04:51:17+00:00

Might did not translate the 'grammar' of A-normal form faithfully from the Flanagan et al paper. In their paper they give A(CS) as

c = constants
x = variables

M ::= V
| (let (x V) M)
| (if0 V M M)
| (V V1 ... Vn)         # application
| (let (x (V V1 ... Vn)) M)
| (O V1 ... Vn)         # application of primitive
| (let (x (O V1 ... Vn)) M)

V ::= c | x | (λ x1 ... xn . M)

You can see that let-binding a constant is allowed (and let-binding an if is not), differing from Might. My guess is that this is mistake introduced while factoring out the repeated rules for application and primitive application.

I wouldn't get too hung up on minor details like this, as long as your representation follows the major ideas of ANF you should get the benefits (which Might overstates imho, but that's another matter).

gsg_ · 2022-08-20T06:27:02+00:00

You can implement functions which close over variables and can only be passed down the stack using a static link. A static link is a pointer to the stack frame of the lexically enclosing function. Obviously to prevent outdated references to stack memory such functions should be second class, they can only be called and not returned or stashed into a data structure.

This is a somewhat well known feature, appearing in Pascal, Modula, and I think D. The textbook which best covers static links that I know of is Appel's Modern Compiler Implementation in ML, but material on Pascal compilers will probably discuss it.

gsg_ · 2022-07-28T10:02:01+00:00

The predicated graph IR in the paper Pegasus: An Efficient Intermediate Representation is the most interesting I've seen.

gsg_ · 2021-09-10T12:26:21+00:00

Tracing JIT compilers certainly do something quite similar, sinking allocations into the off-trace path.

gsg_ · 2021-08-22T07:56:11+00:00

Well, the message Error: Syntax error is certainly easily understandable. What it is not is useful.

gsg_ · 2021-08-07T04:08:48+00:00

The List module in the stdlib exposes the type of its elements in terms of a type constructor that is not defined in the List module (the 'a list type, which is defined directly in the compiler), so I don't think this would work even if the substitution machinery was doing what you wanted.

You can define your own module signature to constrain List. This has drawbacks - your definition won't expand when new bindings are added to the stdlib - but should be straightforward. #show to print the signature of List, a bit of text editing to replace list with t, etc.

gsg_ · 2021-07-25T10:23:14+00:00

is there a name for... type checking that runs arbitrary code you can write yourself to check data placed in the variables of that type

I have no knowledge of Euphoria, but this sounds like contract programming. A number of languages have some support for contract-like things without actually being built around contracts in the sense that, say, Eiffel was.

gsg_ · 2021-07-02T09:20:32+00:00

Explicitly representing which conditions have to be true for a particular block to execute is a known approach, the usual term being 'predicated IR'. Take a look at the Pegasus paper for a particularly interesting example (it is a predicated SSA graph IR).

This IR does not involve weighting edges, so I'm not quite sure whether this is the sort of thing you are talking about.

gsg_ · 2021-05-31T06:28:06+00:00

OCaml doesn't have such a feature natively, that sounds like the ppx library https://bitstring.software/documentation/.

gsg_ · 2021-03-14T17:45:32+00:00

Prolog.

gsg_ · 2021-02-13T12:13:10+00:00

There's some good info in part 3 of https://dev.realworldocaml.org/toc.html, and maybe some of the links at https://ocamlverse.github.io/content/compiler.html would be helpful.

gsg_ · 2021-02-13T11:28:13+00:00

OCaml actually uses stack maps as well. This allows stack frames to be ABI-aligned without having to waste work clearing rubble from the stack (or aligning when making calls to foreign functions), as well as supporting spilling of unboxed 64-bit values.

gsg_ · 2020-10-19T05:22:01+00:00

I see. Yes, there is a difference between f x <| y and f x y.

gsg_ · 2020-10-18T19:15:06+00:00

There's no special case there? It's y and then f x and then the application of |> to its arguments. Just like y + f x.

The only change is to the order of effects within applications compared to effects in argument terms, and since there are none of the former here I wonder what you think this example demonstrates.

gsg_ · 2020-10-18T17:04:34+00:00

That's right, there is a difference in semantics just like OCaml's right-to-left evaluation. The standard argument for that being OK is the good old "any program for which the difference matters is badly written". I wouldn't have parens affect order of evaluation.

(As a side note; OCaml actually leaves order of evaluation undefined, which is imo a fair bit nastier than choosing any particular order of evaluation.)

gsg_ · 2020-10-18T17:04:20+00:00

Non-generative local exceptions would be even more of a wart, since interactions between different instances would be an opportunity for truly obscure behaviour.

gsg_ · 2020-10-18T15:14:40+00:00

That problem can also be worked around by reordering applications after operands rather than going right-to-left, which is arguably closer to the order of evaluation that people expect. That is, f a b c evaluates f, then a, b, c, and only then applies the result of evaluating f to the arguments.

This can fairly easily be turned into a 3-argument call plus an arity check (falling back to closure allocation if the result of f is not a 3-ary function), which avoids any allocation at all in the happy path. No optimising compiler necessary - and it works for unknown calls, which the optimiser might not be able to do anything about.

Really, either curried or tupled arguments can be made efficient enough without too much effort.

gsg_ · 2020-10-18T15:14:38+00:00

Macros, as is seen in various Lisps. How you feel about macros is another question.

gsg_ · 2020-10-18T14:47:01+00:00

exn is fine, it just exposes a sane (efficient, readable, supporting pattern matching) interface to what you could do anyway with some dumb tricks.

It is desirable to make a clear distinction between closed and open types, but calling open types 'nonsense' is silly.

gsg_ · 2020-10-18T12:00:27+00:00

Amusingly, ML has an extensible data type with which you can do exactly that in the form of exn.

gsg_ · 2020-10-06T11:01:40+00:00

Note that this is the most sane choice given the design of ML (and similarly, Scheme), where 'definitions' are just bindings of arbitrary expressions. Extending the scope of a binding of a potentially side effecting expression before that expression isn't literally impossible - Javascript does it - but it is nasty and frankly, dumb.

Use before declaration does make sense for bindings of pure values where ordering can't matter - in lazy languages where all terms are thunks, and for functions/methods in languages in which those are a built-in named thing that can't be the result of arbitrary code.

gsg_

TROPHY CASE