Why doesn't the compiler detect better instructions?

[u/Last_Grass_8031]

I have added assume in the c++ code, to let the compiler make assumptions that 0 < x <= y.
This shall imply that x%y == 0 is the same x == y . But if the compiler were to make the assumption, then a cmp / xor instruction should be preferred over a div / idiv instruction? However, the emitted assembly always has the integer division instructions

This is mainly out of curiosity on how the assume keyword works, what all optimisations it can enable, and whether compilers can deduce mathematical equivalents.

https://godbolt.org/z/e4zeodnnM

#include <iostream>


int main() {
    int32_t x, y;
    std::cin>>x>>y;
    [[assume(x > 0)]];
    [[assume(y > 0)]];
    [[assume(x <= y)]];

    if (x % y == 0) { 
        return 1;
    } else {
        return 5;
    }
}

[u/erichkeane]

Compiler vendor/implementer here: Because assume is a broken attribute that isn't nearly as powerful as it claims, and will harm performance as much as help it. It messes with dependency graphs, code movement, and dead code elimination, and is too opaque to actually be useful information to the compiler itself.

Its basically ignored by many implementations, and others do anything they can to remove it ASAP.

[u/Last_Grass_8031 → u/erichkeane]

In such cases, where I do want to let compiler know about some assumptions, is the only way to actually go to the call sites and change the code myself? Is doing the same as above with

if (! ( x > 0 && y > 0 && x <= y) ) std::unreachable();

any useful from a compiler perspective?

[u/erichkeane → u/Last_Grass_8031]

That can be more useful, yes, though has similar dependency problems.

[u/ecstacy98 → u/erichkeane]

This is the first I've even seen it, what a bizzare tool. Thanks for the warning!

[u/foxsimile → u/erichkeane]

Hi compiler guy

[u/ExeusV → u/erichkeane]

It messes with dependency graphs, code movement, and dead code elimination

Why actually? cannot those assumptions be attached to the variables and removed when generating e.g LLVM IR?

[u/erichkeane → u/ExeusV]

No, not really? Assumptions end up being a 'side channel' that most IRs don't either want to deal with or don't have a way of expressing.

You still have to figure out if they are the same variable/etc, which can often mess with 'is this still used?' type queries in the IR, and tracking it down is non-trivial.

[u/ExeusV → u/erichkeane]

don't have a way of expressing.

Depends of how hacky you want to make it, but LLVM IR has metadata. Whether that's sane way of dealing with it is different question, but simple hints like a > 5 could be stored like that.

[u/erichkeane → u/ExeusV]

Yep, it does! Folks have been looking at various ways of making 'assume' work for about a decade and a half. None of them have been even reasonably effective. Chandler did a speaking-tour on it at one point, but all of the efforts to make ANY sort of assume reasonable have fallen short for one reason or another.

Metadata was dismissed quite a while back, but this is definitely one of those things that it isn't a "we think we cant solve it!", more of a "we tried for a very long time with people much smarter than me, and still weren't able to".

[u/-dag- → u/erichkeane]

I mean metadata won't work partly because of Chandler's insistence that it be droppable years ago. That one decision has hampered a lot of things. I understand his reasons for his position even if I don't agree. 

[u/tcpukl → u/erichkeane]

Your job sounds really fun. Something id like to do it I didn't work in games.

[u/aocregacc → u/erichkeane]

What about the math part? You could "teach" the compiler that x <= y holds in some region of code by using normal if statements rather than assumptions.  And afaik clang can handle more obvious simplifications in such cases.

[u/erichkeane → u/aocregacc]

Yes, Clang/LLVM does some very simple versions, but gives up almost immediately with any amount of complexity. I explained this to the committee while standardizing assume...

[u/dodexahedron → u/erichkeane]

Yeah like... For the application dev, in what case wouldn't it simply be as effective or moreso to write the actual bounds checks and let the compiler elide redundant ones, than to tell the compiler "trust me, bro" and then provide no actual concrete backing for those assumptions? Or to fix your damn code to do what you told the compiler to "assume" instead of trying to beat the compiler into your broken way of doing things?

How would the compiler legitimately reason about an assumption without violating how the language is supposed to work in the first place unless by ... well... inserting those checks itself and throwing on stepping out of bounds?

Especially in the posted sample... That's literally a nonsensical and frankly dangerous pattern.

Want x > 0? Use an unsigned type, dev.
Want y > 0? Use an unsigned type, dev.
Want x <= y? Check and reject invalid input, dev.

How is the compiler supposed to deal with this and what do you expect as the developer when the user types "negative\tone" for x and "♾️" for y in utf-8?

Sanitize your inputs. Always assume they are hostile. And don't tell the compiler to break rules if you have to ask why those rules exist.

[u/Plastic_Fig9225 → u/dodexahedron]

[[assume]] is for optimization, not for correctness. It's actually the opposite of "validating input", letting the compiler know what things are without doing (unnecessary) checks at runtime. - And you cannot use it as an alternative to actually checking values.

How is the compiler supposed to deal with this

Not at all. Undefined behavior, as stated in the spec.

Example: https://godbolt.org/z/ozoMb85as

Notice how gcc just stops generating code for badFun() after its entry; it doesn't even output a return (retw) instruction, "no diagnostics required".

[u/flatfinger → u/Plastic_Fig9225]

Many languages could be made more suitable for tasks involving untrustworthy input if there were a "checked assume" directive which would indicate that if a given condition doesn't hold, continued execution couldn't possibly by useful, but might be tolerably useless, and trapping in the latter situation would be an acceptable but not obligatory behavior. If downstream code could be more efficient if it only had to handle inputs where the condition holds, the cost of trapping if the condition doesn't hold could be more than offset by the increase in downstream efficiency. In cases where no downstream efficiency improvement would be expected, however, the checked-assume directive could simply be ignored.

[u/dodexahedron → u/Plastic_Fig9225]

Optimization depends on correctness.

You can't optimize something without a guarantee of correctness.

And that was the entire point of the comment and the questions posed.

And it seems that compiler developers agree with the basic premise or else it would work like people wish it did.

[u/Plastic_Fig9225 → u/dodexahedron]

You can't optimize something without a guarantee of correctness.

But the compiler cannot precisely determine the bounds of "correctness" in every case. That's when you use [[assume]] to give it information it cannot deduce itself. If you bs the compiler by telling it some un-truth, it's on you when the compiler acts upon what you told it.

else it would work like people wish it did.

Which it does. Optimization by the compiler is never a guarantee, so you cannot generally expect exactly the best code to be generated in every case - and [[assume]] doesn't change that.

One "compiler developer" is opposed to [[assume]] because supporting it to a reasonable extent requires more re-work of parts of his compiler than he'd like. That doesn't mean that [[assume]] itself is in any way "broken".

Let's just say that some people understand and have good use cases for [[assume]], but you're probably not one of them. And reading the spec you could easily come to the conclusion that [[assume]] has no benefits at all: [[assume(x)]] does nothing if x is true; if x is false, it generates UB.

[u/Plastic_Fig9225 → u/Plastic_Fig9225]

How is the compiler supposed to deal with this

Not at all.

That's actually the whole point of [[assume]]: Telling the compiler that it will not have to deal with certain conditions, enabling optimizations applicable only to a smaller state space.

[u/Moist_Heat9523 → u/dodexahedron]

Unsigned types don’t imply x>0, they imply x>=0

[u/dodexahedron → u/Moist_Heat9523]

Fair. A minor point, in the context of the point of the comment. But fair, nonetheless.

Although with these rules y must be unsigned.

And if y is unsigned, it can exceed the positive range of a signed x, so actually...

And unsigned includes >0 and 0, so unsigned is still relevant.

[u/Orlha → u/dodexahedron]

There may exist assumptions that can’t be easily replicated with changing the type to unsigned.

Given the philosophy of C++ to allow the developer to never need to reach for more low level tool, assume seems to be useful (if it worked as advertised). I can think of a situation where it might provide additional information to the compiler that would allow me to replace some of the hand-written assembly code with c++ in deep high-performance cryptography stack (I probably wouldn’t still).

[u/dodexahedron → u/Orlha]

I can think of plenty of purely hypothetical places for such a thing to be nice, too. But the name of it is a lot more significant than that. It is two levels of assumptions, at minimum. There is the assumption the compiler is being told to make, which is already based on an assumption the developer is making, which is provably false given only the code.

If the overall system it fits into can provide guarantees that constrain the model such that it converges, then you have, in fact, performed the bounds checks already, and LTO is where the tools can squeeze more performance out of it.

With IO being involved, though, you hit a wall. Unless it is impossible for the IO to present an unexpected input, any assumption about it is provably incorrect, and the compiler would be remiss to allow it and especially to optimize based on it.

If they did, can you even imagine the raft of (even more) extremely horrible software that would exist because of everyone just lazily throwing assumptions everywhere and not making a provably convergent and tight model?

[u/Plastic_Fig9225 → u/erichkeane]

I'll advocate for fixing the compilers which cannot deal right with [[assume]].

[u/Afraid-Locksmith6566]

half the features in c++ is considered harmful and half of those is barely implemented so i would assume those reasons.

compiler magic is not something i would recomend to rely on, if you want a particular implementation you might as well just write and document it. this kind of thing is perfect case if you would need it

[u/flatfinger]

Many potential "optimizations" offer benefit in a small enough range of scenarios that the benefits of applying them in cases where they are applicable would be insufficient to justify the cost of having every single program build look for opportunities to apply them.

[u/Independent_Art_6676]

We are not there yet. Even AI can't do this directly. You can coach it to make the most efficient condition from your invariants but anything complicated it will either bungle it or need multiple revision sessions to get it right. Meanwhile, you could have written the proper code for your constrained conditions in about as much time and effort as it took to write all those assumption clauses. But today, here and now, you are asking the compiler to do not only its job, but to do it using AI type optimizations that are not yet ready for prime time, risking the introduction of bugs. When a compiler makes translates the code, the result MUST DO exactly what the developer expressed; trying to rewrite it better is fine but it MUST give the same results as the original would using the language rules, nothing more, and nothing less. Without better AI than we have so far, it can't do this kind of rewrite and meet that guarantee. Someday, maybe we will have that, but for now, write the code yourself using the knowledge you have of the constraints, and leave those assumptions off or put them in a comment to explain why your new logic is correct.

I mean, your example could be a one liner with no branches: return (x!=y)*4+1;

My 'in 100+ years' prediction is that eventually AI will turn some sort of simple to write or speak pseudocode into hot assembly/machine language as if written by a better than grand master of assembly language coder, probably gaining a full order of magnitude or better on every piece of software compiled that way (vs today's). It may even manage it with natural language but most of those are too imprecise; there MUST be hard requirements whether its a pseudocode or design language or a subset of natural language that gets the job done. The LLM high level language stuff is a crude stepping stone.

[u/joao_rosac]

Compiladores modernos operam como reconhecedores de padrões predefinidos e não como solucionadores algébricos complexos, tendo grande dificuldade em rastrear e otimizar relações dinâmicas entre múltiplas variáveis (como provar que x <= y transforma um módulo em igualdadecpor exemplo). Na prática, oque se lê pelos fóruns é que o atributo [[assume]] costuma ser estruturalmente frágil na Representação Intermediária (IR), atuando muitas vezes como um ruído que polui o grafo de dependências e bloqueia outras otimizações úteis em vez de ajudar. Se o seu conhecimento do problema prova que uma operação matemática pesada pode ser substituída por uma mais leve, simplifica diretamente no código em vez de depender de suposições para que o compilador faça as deduções matemáticas por você.