Skip to main content
34 votes
Accepted

How to ensure that an optimising compiler will terminate?

The roots of the problem: cost models, and monotonicity You're really getting at the heart of the problem when you say: each rewrite rule should make the program "more efficient" After all,...
Moonchild's user avatar
  • 879
26 votes

Pros and cons of "anything-can-happen" UB versus allowing particular deviations from sequential program execution

As far as I know, there are only two advantages: performance and ease of writing compiler optimizations. Performance When compilers can make assumptions, they always make assumptions to improve ...
Gavin D. Howard's user avatar
21 votes

What are the pitfalls of using an existing IR/compiler infrastructure like LLVM?

Very large and very complicated The LLVM project has over 2 million lines, or 1.3 GB, of code. It's one of the largest projects on Github. It's so large that (at least at one point) you couldn't even ...
tarzh's user avatar
  • 3,924
21 votes

How to ensure that an optimising compiler will terminate?

The existing answer is good and representative of the techniques currently used in most optimizing compilers. I’d like to add to that by mentioning equality saturation, a newer technique that seems ...
Alexis King's user avatar
  • 8,731
17 votes

Pros and cons of "anything-can-happen" UB versus allowing particular deviations from sequential program execution

“Anything-can-happen UB” is a fundamental consequence of lacking memory safety In order to even be able to restrict the set of behaviors that a buggy program may create, the compiler must be able to ...
Alexis King's user avatar
  • 8,731
13 votes
Accepted

Tail-recursive detection and conversion

It is technically always possible to turn a recursive function into a tail recursive one by maintaining a separate, heap-allocated stack. For example, you could write your ...
Alexis King's user avatar
  • 8,731
10 votes

What are the disadvantages of automatically inlining all functions?

First, you can't inline all functions: it's quite obviously impossible for recursive functions, first-class functions (closures and those that get passed by a pointer to the function) and "...
Alex Chichigin's user avatar
9 votes

Why was C implemented with a register preservation convention that seems to be far less efficient than its predecessor's?

How registers behave across function calls is part of the calling conventions defined by a particular language implementation. To facilitate cross-implementation and cross-language calls, most ...
Gilles 'SO- stop being evil''s user avatar
8 votes
Accepted

Empirically, what are the implementation-complexity and performance implications of "unboxed" primitives?

The main decision you have to make is whether your language will be sufficiently statically typed that you don't need type tags for unboxed primitives at runtime. Java (or rather, JVM bytecode) is an ...
kaya3's user avatar
  • 19.7k
8 votes
Accepted

What are the tradeoffs between using sea of nodes, CFG of basic blocks, and egraphs for compiler optimizations?

Let's contrast sea-of-nodes and basic blocks with e-graphs. All three are graph representations of programs. The main feature of a graph representation is that intermediate values can be dependencies ...
Corbin's user avatar
  • 851
8 votes
Accepted

Are there languages or compilers having optimizations to deallocate variables early?

Yes. The Koka programming language does this. What you are looking for is referred to by the authors as "garbage-free" memory management, and "reuse" (in various forms). "...
apropos's user avatar
  • 1,028
7 votes

Which calling convention should my compiler use?

I would split the 14 (I'm not including cc <n> here) calling conventions listed in three categories: generic (those that would make sense for any function to ...
RubenVerg's user avatar
  • 1,632
7 votes

Which calling convention should my compiler use?

Any externally-accessible function (such as for libraries) should 100% use the standardized calling convention for the operating environment (what LLVM calls "ccc" I suppose). I believe on ...
kouta-kun's user avatar
  • 1,359
7 votes
Accepted

How can a programming language support vectorization portably?

The way GLSL does SIMD is by having vectorized primitives (float3, float4, etc) that you can do operations on, or access individual elements. I figure a templatized version of it that can expand to ...
kouta-kun's user avatar
  • 1,359
7 votes

What are the pitfalls of using an existing IR/compiler infrastructure like LLVM?

There's not always a whole lot you can do if the backend has bugs. Consider this recent issue for Zig, which discusses using their own backend instead of LLVM. One of the advantages listed is, and I ...
Bbrk24's user avatar
  • 9,067
7 votes

What are the disadvantages of automatically inlining all functions?

Function inlining isn't always a win. It increases code size, which increases compilation times and may decreased performance due to more pressure in the intruction cache. For some functions the ...
hugomg's user avatar
  • 1,345
7 votes

How to ensure that an optimising compiler will terminate?

All that I've seen work with rule application limits, i.e. you give up after a certain number of steps. If you know how these limits work, you sometimes can create examples for programs that have an ...
feldentm's user avatar
  • 1,831
7 votes

How to ensure that an optimising compiler will terminate?

As requested, I'm going to do my best to summarize the Termination-Checking for LLVM Peephole Optimizations paper, by Menendez and Nagarakatte. The reality of compiler optimization staging is that it ...
cody's user avatar
  • 221
6 votes

What are the downsides, if any, of using implicit function purity in an impure language?

Even if purity is only used for optimisations, users may still rely on those optimisations such that it's an unacceptable performance regression if the same code ceases to be optimisable. There is ...
kaya3's user avatar
  • 19.7k
6 votes
Accepted

What are some common ways to optimise an interpreter?

The first option is changing the way you execute the code. Reduce the cache thrashing of the tree walk interpretation by moving the AST nodes being interpreted into a contiguous memory buffer. After ...
ratchet freak's user avatar
6 votes

How can a programming language support vectorization portably?

One important consideration is how your language handles aliasing. This is a major killer of auto-vectorization opportunities for C and C++. For example, in the following function: ...
Nate Eldredge's user avatar
6 votes

How can a programming language support vectorization portably?

Array Programming One possible way is to have arrays similar to C++ std::valarray or Fortran arrays. Including semantics to perform operations on an entire array ...
CPlus's user avatar
  • 8,321
6 votes

How can a programming language support vectorization portably?

Probably the most portable way to do this is to leverage the very sophisticated optimisations, including automatic vectorisation, provided by established compiler backends such as LLVM. For the vast ...
kaya3's user avatar
  • 19.7k
6 votes

Are there any disadvangates to requiring sincos() type functions?

Multiple return values Since you listed C as an example of a language that doesn’t have this, it’s worth pointing out that the language itself doesn’t facilitate returning multiple values from one ...
Bbrk24's user avatar
  • 9,067
6 votes

How to implement dynamic scoping?

Dynamic scoping seems strangely awkward to implement despite having in some ways nicer semantics. Dynamic scope is arguably easier to implement than lexical scope ─ it means instead of building a ...
kaya3's user avatar
  • 19.7k
6 votes

How to optimize non-tail recursion?

Last call modulo constructor One common situation in declarative languages is where there is almost a tail call, in the sense that there are no computations or calls (or ABI infrastructure, such as ...
Pseudonym's user avatar
  • 4,726
6 votes
Accepted

How does link-time function inlining work?

LLVM link time optimizations are implemented by having the intermediate .o files keep the bitcode for each function around instead of fully emitting unrelocated ...
chc4's user avatar
  • 196
5 votes

Why was C implemented with a register preservation convention that seems to be far less efficient than its predecessor's?

The C language does not require that it be implemented on a register transfer machine, let alone define which registers are callee-save and which registers are caller-save. This is the job of the ABI ...
Pseudonym's user avatar
  • 4,726

Only top scored, non community-wiki answers of a minimum length are eligible