61–70 of 193 posts
unsigned add(unsigned x, unsigned y) {
std::vector vx {x};
std::vector vy {y};
auto res = vx[0]+vy[0];
return res;
}Also optimizers have a limit, they can't reason as abstractly as humans, for example:
bool is_divisible_by_6(int x) {
return x % 2 == 0 && x % 3 == 0;
}
bool is_divisible_by_6_optimal(int x) {
return x % 6 == 0;
}
The morale is that you still have to optimize algorithms (O notation) and math operations / expressions.
Obvious caveat: pushing this a bit further it can quickly fallback to the default case. The optimizer is a superpower but you still need to try to write efficient code. unsigned add_v5(unsigned x, unsigned y) { if (x == y) return 2 * x; return x + y; } Results in: add_v5(unsigned int, unsigned int): lsl w8, w0, #1 add w9, w1, w0 cmp w0, w1 csel w0, w8, w9, eq ret (armv8-a clang 21.1.0 with O3) If compiler folks can c…
I’m not a compiler expert, an assembly expert or an ARM expert, so this may be wildly wrong, but this looks optimized to me. The trick is that it’s doing both the add and the left shift in parallel then selecting which to use based on a compare of the two values with csel. (To see this, rather than reading the code sequentially, think of every instruction as being issued at the same time until you hit an instruction…
I wonder if compilers do multiple passes on the intermediate code in order to optimize / simplify it. For example, during each pass the optimizer searches some known harcoded patterns and replaces them with something else and repeats until no possible improvement is found. Also optimizers have a limit, they can't reason as abstractly as humans, for example: bool is_divisible_by_6(int x) { return x % 2 == 0 && x % 3 =…
On higher optimization levels, many passes occur multiple times. However, as far as I know, compilers don't repeatedly run passes until they've reached an optimum. Instead, they run a fixed series of passes. I don't know why, maybe someone can chime in.
I liked the idea behind this post, but really the author fairly widely missed the mark in my opinion. The extent to which you can "fool the optimizer" is highly dependent on the language and the code you're talking about. Python is a great example of a language that is devilishly hard to optimize for precisely because of the language semantics. C and C++ are entirely different examples with entirely different optimiz…
unsigned mult(unsigned x, unsigned y) {
unsigned y0 = y;
while (x--) y = add_v1(y, y0);
return y;
}
mult(unsigned int, unsigned int):
madd w0, w1, w0, w1
ret
Earlier quoted context omitted.
> It probably shouldn't do that if you create a dynamic library that needs a symbol table but for an ELF binary it could, no? It can't do that because the program might load a dynamic library that depends on the function (it's perfectly OK for a `.so` to depend on a function from the main executable, for example). That's one of the reasons why a very cheap optimization is to always use `static` for functions when you…
Sadly most C++ projects are organized in a way that hampers static functions. To achieve incremental builds, stuff is split into separate source files that are compiled and optimized separately, and only at the final step linked, which requires symbols of course. I get it though, because carefully structuring your #includes to get a single translation unit is messy, and compile times get too long.
Obvious caveat: pushing this a bit further it can quickly fallback to the default case. The optimizer is a superpower but you still need to try to write efficient code. unsigned add_v5(unsigned x, unsigned y) { if (x == y) return 2 * x; return x + y; } Results in: add_v5(unsigned int, unsigned int): lsl w8, w0, #1 add w9, w1, w0 cmp w0, w1 csel w0, w8, w9, eq ret (armv8-a clang 21.1.0 with O3) If compiler folks can c…
Compilers are essentially massive towers of heuristics for which patterns to apply for optimization. We don't throw a general SMT solver at your code because that takes way too long to compile; instead, we look at examples of actual code and make reasonable efforts to improve code.
In the case of the incrementing in a loop, there is a general analysis called Scalar Evolution that recasts expressions as an affine expression of canonical loop iteration variables (i.e., f(x), where x is 0 on the first loop iteration, 1 on the second, etc.). In the loop `while (x--) y++;`, the x variable [at the end of each loop iteration] can be rewritten as x = x₀ + -1*i, while the y variable is y = y₀ + 1*i. The loop trip count can be solved to an exact count, so we can replace the use of y outside the loop with y = y₀ + 1*trip count = y₀ + x, and then the loop itself is dead and can be deleted. These are all optimizations that happen to be quite useful in other contexts, so it's able to easily recognize this form of loop.
In the example you give, the compiler has to recognize the equivalence of two values conditional on control flow. The problem is that this problem really starts to run into the "the time needed to optimize this isn't worth the gain you get in the end." Note that there are a lot of cases where you have conditional joins (these are "phis" in SSA optimizer parlance), most of which aren't meaningfully simplifiable, so you're cutting off the analysis for all but the simplest cases. At a guess, the simplification is looking for all of the input values to be of the same form, but 2 * x (which will actually be canonicalized to x << 1) is not the same form as x + y, so it's not going to see if the condition being used to choose between the same values would be sufficient to make some operation return the same value. There are representations that make this problem much easier (egraphs), but these are not the dominant form for optimizers at present.
Obvious caveat: pushing this a bit further it can quickly fallback to the default case. The optimizer is a superpower but you still need to try to write efficient code. unsigned add_v5(unsigned x, unsigned y) { if (x == y) return 2 * x; return x + y; } Results in: add_v5(unsigned int, unsigned int): lsl w8, w0, #1 add w9, w1, w0 cmp w0, w1 csel w0, w8, w9, eq ret (armv8-a clang 21.1.0 with O3) If compiler folks can c…
I’m not a compiler expert, an assembly expert or an ARM expert, so this may be wildly wrong, but this looks optimized to me. The trick is that it’s doing both the add and the left shift in parallel then selecting which to use based on a compare of the two values with csel. (To see this, rather than reading the code sequentially, think of every instruction as being issued at the same time until you hit an instruction…
It's not. Why would lsl+csel or add+csel or cmp+csel ever be faster than a simple add? Or have higher throughput? Or require less energy? An integer addition is just about the lowest-latency operation you can do on mainstream CPUs, apart from register-renaming operations that never leave the front-end.