This is an archive of the discontinued LLVM Phabricator instance.

Constant propagation after hiting assume(icmp)
ClosedPublic

Authored by Prazek on Aug 10 2015, 1:07 PM.

Diff Detail

Event Timeline

Prazek updated this revision to Diff 31712.Aug 10 2015, 1:07 PM
Prazek retitled this revision from to Constant propagation after hiting assume(icmp).
Prazek updated this object.
Prazek added reviewers: majnemer, nlewycky, rsmith.
Prazek added a subscriber: llvm-commits.
majnemer added inline comments.Aug 10 2015, 1:27 PM
lib/Transforms/Scalar/GVN.cpp
2101–2108

Avoid making changes not relevant to this change. This seems like a fine change to do separately.

2258–2263

The type is obvious so you could just use auto *. Also, consider splitting this into another function to reduce indentation.

2266–2269

Initialisms are typically capitalized.

2272

This could be written more concisely as: !LHSConst != !RHSConst. The xor is a little out of place considering you aren't doing anything with bits.

nlewycky added inline comments.Aug 10 2015, 1:32 PM
lib/Transforms/Scalar/GVN.cpp
611–612

The description is not wrong, but I would've described it differently:

// Block-local map of equivalent values to their leader, does not propagate to any successors. Entries added mid-block are applied to the remaining instructions in the block.
SmallMapVector<llvm::Value*, llvm::Constant*, 4> LocalLeaderMap;

Notably there's nothing *const-y* about it. We often replace X with Y when both are Instructions, or when Y is an Argument, or in this case when Y is a Constant. What's special about this is that it's block-local.

727

s/instr/I/

2073

Extra blank.

2075

Extra spaces before semicolons

2260

Extr ablank.

2264

Extra blank.

2266–2267

LHS and RHS. If you're worried about shadowing the existing LHS and RHS, I'd suggest ICmpLHS and ICmpRHS or ICmpOp0 and ICmpOp1.

2271–2272

The common idiom is to check which is Constant and then use std::swap.

However, we canonicalize constants to the RHS when possible (ie., not "sub" instructions). Any reason it would be de-canonicalized at this point?

2276

Capitalize.

2277

Period.

2278–2280

Surely this fits on fewer lines?

2291

Extra blank.

2441

I suspect this should have a quick exit for the common case where ReplaceWithConstMap is empty. Putting the test here might make sense, so that we don't even call it at -O0.

We surely don't want to iterate over the operands calling find on an empty map.

test/Transforms/GVN/assume-ptr-equal-same-bb.ll
1 ↗(On Diff #31712)

Please merge the two tests, using FileCheck for both of them. I think you can replace the grep with a CHECK: here.

dberlin edited edge metadata.Aug 10 2015, 1:53 PM

So, this is essentially trying to start to get GVN to recognize that operations are made of operations on value numbers.

Except you are only handling the really special case where those value numbers are constant over the entire program (instead of also handling cases where the operations simplify, or have arithmetic niceties, etc. SimplifyInstruction will do some of this, but it won't notice some classes of things)

I'm generally biased against trying to bolt more into our current GVN, but hey, when you do stuff like this, it just makes New GVN a lot faster by comparison :)

So SGTM

lib/Transforms/Scalar/GVN.cpp
2263

Why only ICMP_EQ?

2277

This isn't quite right :)
There are cases that propagate equality checks, and cases we don't call it because it would do the wrong thing.

For example, i know your code doesn't quite work right with assume followed by certain types of switch statements (where there are multiple edges to the same successor).

See the code handling switch statements, that verifies there are not multiple edges to the same successor, and if there are not, *does not call propagateEquality* (old line 2259)

You are going to either need to unify or duplicate a lot of this kind of logic, depending on the terminator of the basic block the assume statement is in.

Prazek marked 9 inline comments as done.Aug 10 2015, 3:17 PM
Prazek added inline comments.
lib/Transforms/Scalar/GVN.cpp
2272

!LHSConst != !RHSConst looks bad to me. I can change it to LHSConst != RHSConst

Prazek marked 3 inline comments as done.Aug 10 2015, 3:19 PM
Prazek marked an inline comment as done.Aug 10 2015, 3:43 PM
Prazek added inline comments.
lib/Transforms/Scalar/GVN.cpp
2263

You mean to add fcmp also?

Not just that.
llvm.assume asserts whatever the condition is, is true.
PropagateEquality will propagate equalities like (A < B) == true as
well, by replacing all dominated instances of A>= B == false.

So you should be able to "propagate" basically all the ICMP variants.

Prazek marked 8 inline comments as done.Aug 10 2015, 5:51 PM
Prazek marked an inline comment as done.Aug 10 2015, 5:52 PM
Prazek updated this revision to Diff 31758.Aug 10 2015, 7:05 PM
Prazek edited edge metadata.

LGTM someone?

hfinkel added inline comments.
lib/Transforms/Scalar/GVN.cpp
1778

It looks like all of the arguments could fit on one line (or at most two), please do that.

1782

I'd prefer a blank line between the } and the if.

1784

We can include FCMP_UEQ here if the fcmp has the nnans fast-math flag, please do so.

Prazek marked 3 inline comments as done.Aug 16 2015, 1:22 PM
Prazek updated this revision to Diff 32252.Aug 16 2015, 1:23 PM
nlewycky added inline comments.Aug 17 2015, 5:09 PM
lib/Transforms/Scalar/GVN.cpp
1769

Please add a string to this: assert(expression && "Failure message"); See http://llvm.org/docs/CodingStandards.html#assert-liberally

1771

Wrong context. Use the same context from any Type or Value you have.

Let me explain what llvm contexts are for. They're intended to keep different threads separate, and keep them from accessing each others data, since llvm does not have internal locking. So the context owns the types and constant, and if two threads try to create "i1 true" at the same time then they'll race on updating the map. (Also, it's a verifier failure to have two Type*'s form two contexts involved in the same Module. By default everyone just uses the global context, but there may be a library user that does not.)

1773
1776–1777

Reflow this comment.

2070–2071

Reflow this comment.

test/Transforms/GVN/assume-ptr-equal.ll
7–23

Please interleave the check statements with the function being tested. This helps show which calls should I expect to become direct calls to foo and bar.

16

Typo, CHECK-LABLE

Prazek marked 7 inline comments as done.Aug 17 2015, 7:28 PM
Prazek updated this revision to Diff 32373.Aug 17 2015, 7:32 PM
nlewycky added inline comments.Aug 17 2015, 8:37 PM
lib/Transforms/Scalar/GVN.cpp
1777–1778

I think this comment could be made more clear. Why can't equality propagation be done for every successor? What does propagateEquality check? Something like:

"This property is only true in dominated successors, propagateEquality will check dominance for us."

perhaps?

2075

Operand

test/Transforms/GVN/assume-ptr-equal.ll
29

Is this a call to _ZN1A3fooEv or _Z1A3barEv? Put the CHECK line next to this line (usually right after).

Prazek marked 3 inline comments as done.Aug 17 2015, 8:48 PM
Prazek updated this revision to Diff 32375.Aug 17 2015, 8:49 PM
nlewycky accepted this revision.Aug 17 2015, 8:51 PM
nlewycky edited edge metadata.

LGTM

This revision is now accepted and ready to land.Aug 17 2015, 8:51 PM
Prazek closed this revision.Aug 17 2015, 8:57 PM