Page MenuHomePhabricator

LLVM IR constant expressions never trap.
Needs ReviewPublic

Authored by efriedma on Jun 7 2019, 5:30 PM.

Details

Summary

Currently, constants have a property "Constant::canTrap", which is whether they contain a division that might have undefined behavior. If an instruction has a canTrap constant expression as an operand, and that constant expression contains a division with undefined behavior, the instruction has undefined behavior. For PHI nodes, the behavior is only undefined along the corresponding edges. This isn't documented anywhere in LangRef, but we use it to avoid certain transforms in a few optimization passes. For example, isSafeToSpeculativelyExecute checks whether instructions have a canTrap operand.

In practice, canTrap is almost never true: the only way create such an expression is to do something strange with the address of a global, so the denominator of a division is a complex constant expression. This means we have a lot of complexity with very little test coverage. So it would be nice if we could simplify the rules here.

This patch proposes to give up on the whole "canTrap" thing, and redefine the meaning of division in constant expressions. With this patch, if a constant expression divides by zero, or contains an overflowing divide, the result is poison. This simplifies a bunch of code. It also fixes an infinite loop bug involving a canTrap constant, a PHI, and an unsplittable critical edge. The downside is a slight performance hit: if we do end up with a divide constant expression with a complex denominator, we generate extra code to avoid the trap.

There are a few ways to reduce the performance hit that I haven't tried to implement. On architectures where division never traps, we could avoid generating extra code. We could also try to avoid constant-folding divide instructions that would result in a complex constant expression.

Diff Detail

Repository
rL LLVM

Event Timeline

efriedma created this revision.Jun 7 2019, 5:30 PM
Herald added a project: Restricted Project. · View Herald TranscriptJun 7 2019, 5:30 PM

Overall, I think that this makes sense. Thanks for proposing this.

lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp
3224

Please add a comment here explaining that you're guarding against both x/0 and INT_MIN/-1.

test/CodeGen/X86/divide-constant.ll
301 ↗(On Diff #203646)

Can you check known bits? I feel like we should somehow know that ptrtoint(@g) isn't zero.

For a test case, we can always do ptrtoint(@g1)/(ptrtoint(@g2)-123456) or similar.

jdoerfert added inline comments.Jun 8 2019, 9:29 AM
docs/LangRef.rst
3441

I'm not really happy with this formulation.
It basically says that we somewhere define things to be UB and here we say that it is not UB if it is a constant.

lib/Analysis/ValueTracking.cpp
489

V == I implies isa<Instruction>(V) and you can use isSafeToSpeculativelyExecute(I)

Looks much better, the GISel changes are fine.

efriedma marked 2 inline comments as done.Jun 10 2019, 2:06 PM
efriedma added inline comments.
lib/Analysis/ValueTracking.cpp
489

I think you're reading this backwards; isSafeToSpeculativelyExecute only executes if V != I

test/CodeGen/X86/divide-constant.ll
301 ↗(On Diff #203646)

I don't think there's any way to prove the value is non-zero here; it's extern_weak.

hfinkel added inline comments.Jun 10 2019, 2:30 PM
test/CodeGen/X86/divide-constant.ll
301 ↗(On Diff #203646)

Indeed. I missed that. I did mean the comment more generally - it seems like we should know that non-weak globals aren't zero. That having been said, looking at the implementation of SelectionDAG::isKnownNeverZero and SelectionDAG::computeKnownBits, etc. they don't seem to know anything about globals, so I suppose that enhancement there would also be needed in order to have an impact on this lowering.

nikic added a subscriber: nikic.Jun 10 2019, 2:33 PM
jdoerfert added inline comments.Jun 10 2019, 3:10 PM
lib/Analysis/ValueTracking.cpp
489

I was, :(

efriedma updated this revision to Diff 203924.Jun 10 2019, 4:03 PM
efriedma edited the summary of this revision. (Show Details)

Address review comments, minor code cleanup, fix ConstantExpr::getAsInstruction, fix regression tests.

Is this still an RFC or by now an accumulation of changes we actually want to make? I added to comments assuming the latter.

lib/IR/Constants.cpp
2966

This can be reasonably separated or you could probably work with the ValueOperands or Ops array. At least I don't (immediately) see that we need to keep this connected to the RFC patch.

test/Transforms/LoopVectorize/X86/masked_load_store.ll
1505–1506

I'm unsure about the sentence that talks about history. I think I'd prefer a statement about the semantic we have, thus, "constant expressions never trap, check ...". But I don't feel strongly about this.

efriedma updated this revision to Diff 204362.Jun 12 2019, 2:59 PM
efriedma retitled this revision from [RFC] LLVM IR constant expressions never trap. to LLVM IR constant expressions never trap..

Addressed review comments. Added release note. I think this patch contains all the changes necessary to reflect the change to IR semantics.

I'll send a brief email to llvmdev now, so everyone's aware this is changing.

I commented on the llvmdev thread, but instead of moving this complexity around, I'd really rather see it go away. We should never have supported div/rem constant expressions in the first place...

-Chris