Page MenuHomePhabricator

[CodeMoverUtils] Improve IsControlFlowEquivalent.
ClosedPublic

Authored by Whitney on Dec 16 2019, 3:48 PM.

Details

Summary

Currently IsControlFlowEquivalent determine if two blocks are control
flow equivalent by checking if A dominates B and B post dominates A.
There exists blocks that are control flow equivalent even if they don't
satisfy the A dominates B and B post dominates A condition.
For example,

if (cond)
  A
if (cond)
  B

In the PR, we determine if two blocks are control flow equivalent by
also checking if the two sets of conditions A and B depends on are
equivalent.

Diff Detail

Event Timeline

There are a very large number of changes, so older changes are hidden. Show Older Changes
jdoerfert added inline comments.Dec 19 2019, 7:34 PM
llvm/lib/Transforms/Utils/CodeMoverUtils.cpp
73

Last modification here, make it Values, not Instructions.

75

Typo: logic

llvm/unittests/Transforms/Utils/CodeMoverUtilsTest.cpp
479

Maybe add my example from the last review just to make sure.

Whitney updated this revision to Diff 234825.Dec 19 2019, 8:51 PM
Whitney marked 4 inline comments as done.

Addressed Johannes's comments.

fhahn added inline comments.Dec 20 2019, 12:25 AM
llvm/include/llvm/Transforms/Utils/CodeMoverUtils.h
28

Is there a strong need to expose all those implementation details in the header here?

It seems this is just an implementation detail used for isControlFlowEquivalent & co that can be entirely contained in CodeMoverUtils.cpp. Unless there's a convincing use case that requires those details to be exposed, I think we should keep them in the .cpp.

llvm/lib/Transforms/Utils/CodeMoverUtils.cpp
40

I guess we could just use SCEV here to check for equivalence. I don't think re-using GVN logic will be feasible, unless you want to value number the whole function

286

This should use DenseMap, unless there is a good justification to not use it. Also ControlCondition could just be a tagged pointer (http://llvm.org/doxygen/classllvm_1_1PointerIntPair.html)

fhahn added inline comments.Dec 20 2019, 12:35 AM
llvm/include/llvm/Transforms/Utils/CodeMoverUtils.h
28

Ah I see this was added after another review comment. I don't have a very strong opinion on this, but I don't really see a benefit of exposing this, as long as there are no other users. Exposing it once there's a need is trivial and keeping it private makes it slightly easier to change/adapt.

If you want to expose this interface, I think that's best done in a separate review, to keep the reviews focused (e.g. the title/description of this patch do not mention the new interface and the motivation at all).

jdoerfert added inline comments.Dec 20 2019, 2:09 AM
llvm/include/llvm/Transforms/Utils/CodeMoverUtils.h
28

Ah I see this was added after another review comment.

Correct, I explicitly asked to do that.

I don't have a very strong opinion on this, but I don't really see a benefit of exposing this, as long as there are no other users. Exposing it once there's a need is trivial and keeping it private makes it slightly easier to change/adapt.

We can obviously move it back to the .cpp file now and back to the header once the outside user comes in. To be honest, I would rather not put it in CodeMoveUtils to begin with but in sth like ControlConditons.h, that would make the discussion if it should be open obsolete as well. Anyway, since it can be moved later and you seem to dislike this solution, I will not argue to expose it any more.

If you want to expose this interface, I think that's best done in a separate review, to keep the reviews focused (e.g. the title/description of this patch do not mention the new interface and the motivation at all).

Changing the title/description of the commit would seem easy enough though

llvm/lib/Transforms/Utils/CodeMoverUtils.cpp
40

I guess we could just use SCEV here to check for equivalence.

"Just use SCEV" is maybe the wrong wording, at least for what I had in mind. My thinking was:
We have probably quite a few "equivalence" checker in the code base. Which one to reuse depends at the end of the day on the properties you need.
It becomes interesting as soon as you actually have condition sets that do not match 1-1 but are still equivalent. As I mentioned earlier, other relations, e.g., subset, will also be interesting. This is all "future work" where though.

I don't think re-using GVN logic will be feasible, unless you want to value number the whole function

If that turns out to help normalizing complex control conditions, why not. I will hopefully have a GSoC student to revive the PolyhedralValueAnalysis, that is even more expensive ;)

fhahn added inline comments.Dec 20 2019, 2:44 AM
llvm/lib/Transforms/Utils/CodeMoverUtils.cpp
40

"Just use SCEV" is maybe the wrong wording, at least for what I had in mind.

I should have been more specific. I meant by using SCEV we would be able to handle more general conditions, benefit from normalization and probably do all that with less code and benefit from the existing caching.

My thinking was:
We have probably quite a few "equivalence" checker in the code base. Which one to reuse depends at the end of the day on the properties you need.
It becomes interesting as soon as you actually have condition sets that do not match 1-1 but are still equivalent. As I mentioned earlier, other relations, e.g., subset, will also be interesting. This is all "future work" where though.

That makes a lot of sense to me.

I don't think re-using GVN logic will be feasible, unless you want to value number the whole function

If that turns out to help normalizing complex control conditions, why not. I will hopefully have a GSoC student to revive the PolyhedralValueAnalysis, that is even more expensive ;)

Sure, those are things we can decide on driven by data.

Whitney updated this revision to Diff 235038.Dec 21 2019, 10:40 PM
Whitney marked 6 inline comments as done.

Addressed review comments.

Whitney marked an inline comment as done.Dec 21 2019, 10:46 PM
Whitney added inline comments.
llvm/lib/Transforms/Utils/CodeMoverUtils.cpp
286

Do you feel strongly about changing to DenseMap? I tried to change it, but I could not make it work successfully. Somehow equivalent values are inserted to the same set. I can post my code change as a comment and see if you could spot the problem, if you really want to change to a dense map.

Whitney marked an inline comment as done.Dec 21 2019, 11:02 PM
Whitney added inline comments.
llvm/lib/Transforms/Utils/CodeMoverUtils.cpp
286

The problem should be LookupBucketFor() find bucket of a value using its hash, so two Values isEquivalent() considered as equivalent could be in two different buckets, and both would be added to the set/map.

fhahn added inline comments.Dec 23 2019, 5:37 AM
llvm/lib/Transforms/Utils/CodeMoverUtils.cpp
286

Are you sure there isn’t a problem with the hash function?

After a quick look it seems like the hasher uses only the pointer of the value (and the int) for the hash value . So for example, two different icmp instructions will have different hashes.

But the comperator can consider those two different icmp instructions equal, if their condition matches and their operands are equivalent.

I don’t think that is allowed, equivalent values should always have the same hash (while it's fine for unequal elements to have the same hash). It probably works with unordered_map on the test cases by coincidence due to different default bucket sizes or something like that.

fhahn added inline comments.Dec 23 2019, 5:57 AM
llvm/lib/Transforms/Utils/CodeMoverUtils.cpp
286

equivalent values

it should probably say equal values according to the comparator.

Whitney updated this revision to Diff 235195.Dec 23 2019, 6:23 PM

Changed to use SmallVector instead of unordered_set.

Whitney marked 4 inline comments as done.Dec 23 2019, 6:25 PM
Whitney added inline comments.
llvm/lib/Transforms/Utils/CodeMoverUtils.cpp
286

Thanks for the info, didn't know If k1 and k2 are equivalent, the hash function shall return the same value for both.. Changed to a SmallVector.

Whitney updated this revision to Diff 235239.Dec 24 2019, 5:06 PM
Whitney marked an inline comment as done.

Need a new way to check if isMoveForward(), after the isControlFlowEquivalent improvement.

@fhahn @jdoerfert What do you think of this now?

fhahn added a comment.Jan 7 2020, 11:12 AM

Looking at the examples, it looks like GVN + GVNHoist would at least some of the equivalences trivial. GVNHoist is currently disabled by default, but I think it would be a more general way to materialize equivalences similar to the ones in the tests, rather than teaching various places to do their own equivalence checks.

llvm/lib/Transforms/Utils/CodeMoverUtils.cpp
55

Comment Needs update

74

Not sure if that is really needed?

77

Not used?

87

I think this potentially can be quite expensive. IMO it would be good to have a note about that here.

172

Similar to my suggestion for isEquivalent(const Value &V1, const Value &V2), I think it would be good to have a limit for the number of conditions to collect to avoid compile-time explosion on IR triggered the worst case here.

193

I think it would be good to have a limit here on the number of recursions, like we have in many places where we walk back the def-use-chains, to avoid compile-time explosions on IR triggering the worst case.

203

nit: different points in time?

226

This seems to be comparing every operand from I1 with every operand from I2. Wouldn’t it be enough to compare the first op of both, the second operands and so on? Would also be good to have a test case.

299

This comment should say what it means that I0 comes before I1. Also, the name isMoveForward seems unconnected to the description.

305

Using DT to compare instruction ordering a is quite inefficient. OrderedInstructions is better for multiple queries. I'm not sure if it works with PDT though

Meinersbur added inline comments.Jan 7 2020, 11:57 AM
llvm/lib/Transforms/Utils/CodeMoverUtils.cpp
37

[typo] terminaotr

40

@Whitney Comparing equivalences using == on SCEVPredicate only works on SCEVable types and expressions (eg. ). Would that be feasible or too limiting?

40

I guess we could just use SCEV here to check for equivalence. I don't think re-using GVN logic will be feasible, unless you want to value number the whole function

What I was thinking was to run GVN/GVNHoist beforehand or add LoopFuse close after GVN in the pass pipeline s.t. we could assume that equivalent conditions are represented by the same llvm::Value.

Whitney updated this revision to Diff 236858.Jan 8 2020, 10:31 AM
Whitney marked 16 inline comments as done.

Addressed review comments.

llvm/lib/Transforms/Utils/CodeMoverUtils.cpp
40

Changed to simplify comparing the address of the two llvm::Values. As mentioned, if we first run GVN/GVNHoist, then this is sufficient. We can come back to this when a use case came up to require a more complex equivalence check, or if we encounter issues with running GVN/GVNHoist before certain pass.

77

Right, it is not used. This is added after a reviewer suggestion. We can add it back later when this become a public interface.

87

not expensive anymore

fhahn added inline comments.Jan 15 2020, 9:46 AM
llvm/lib/Transforms/Utils/CodeMoverUtils.cpp
59

nit: 'it limits the '?

61

'... or we hit the limit' ?

173

nit: no llvm:: needed?

191

I think it would be good to mention that we rely on other passes to ensure equivalent conditions have the same value.

194

nit: no braces needed

320–322

OrderedInstruction numbers basic block on demand and caches them. In order for that to be effective, it needs to be passed in by the caller. E.g. moveInstsBottomUp would have to create it and pass it in. It should also be used for the dominates checks further down the function.

But looking at the latest version of the patch, it seems to be completely orthogonal to the main changes. If that's the case, probably best to be split off.

Whitney updated this revision to Diff 238319.Jan 15 2020, 10:46 AM
Whitney marked 7 inline comments as done.

Addressed Florian's latest comments.

llvm/lib/Transforms/Utils/CodeMoverUtils.cpp
320–322

The two dominates checks further down the function actually want to use DT.dominates, e.g. it is not safe to move instruction forward to a InsertPoint where OI.dominates(InsertPoint, U) but not DT.dominates(InsertPoint, U).

The change is needed, since isSafeToMoveBefore uses isControlFlowEquivalent as one of the checks, and the patch changes the behaviour of isControlFlowEquivalent.

fhahn added inline comments.Jan 15 2020, 11:13 AM
llvm/lib/Transforms/Utils/CodeMoverUtils.cpp
320–322

The two dominates checks further down the function actually want to use DT.dominates, e.g. it is not safe to move instruction forward to a InsertPoint where OI.dominates(InsertPoint, U) but not DT.dominates(InsertPoint, U).

I think I am missing something. Shouldn't OI.dominates(InsertPoint, U) and DT.dominates(InsertPoint, U) be equivalent?

The change is needed, since isSafeToMoveBefore uses isControlFlowEquivalent as one of the checks, and the patch changes the behaviour of isControlFlowEquivalent.

Again I think I am missing something. Isn't the change in the function just switching DT.dominates to OI.dominates? similar, the change in moveInstructionsToTheBeginning just adds OI?

394

Any modifications to a BB potentially messes up OI. OrderedBasicBlock (used by OrderedInstructions) provides a mechanism to remove instructions, but I think currently there's no way to update the cache to insert instructions at the beginning, so we'd have to remove the cached BB. It seems like this is more work than I initially thought, so maybe it's better to do that as a follow up. Or just keep create the OrderedInstruction object in isSafeToMoveBefore, *if* it can be used by all instruction level dominates queries.

Whitney marked 3 inline comments as done.Jan 15 2020, 11:27 AM
Whitney added inline comments.
llvm/lib/Transforms/Utils/CodeMoverUtils.cpp
320–322
if ()
  I1
else 
  I2

Here OI.dominates(I1, I2) returns true, but DT.dominates(I1, I2) returns false.

Notice that isControlFlowEquivalent() is used in isSafeToMoveBefore(). And this patch changes the behaviour of isControlFlowEquivalent(). DT.dominates cannot be used to determine if moving forward anymore.

394

If you agree, I will change back to construct OrderedInstruction in isSafeToMoveBefore for this review.

Whitney marked 2 inline comments as done.Jan 15 2020, 11:30 AM
Whitney added inline comments.
llvm/lib/Transforms/Utils/CodeMoverUtils.cpp
320–322

The example should be

if (cond)
  I1
if (cond)
  I2

Here OI.dominates(I1, I2) returns true, but DT.dominates(I1, I2) returns false.

Notice that isControlFlowEquivalent() is used in isSafeToMoveBefore(). And this patch changes the behaviour of isControlFlowEquivalent(). DT.dominates cannot be used to determine if moving forward anymore.

fhahn added inline comments.Jan 15 2020, 12:07 PM
llvm/lib/Transforms/Utils/CodeMoverUtils.cpp
320–322

Here OI.dominates(I1, I2) returns true, but DT.dominates(I1, I2) returns false.

Right I now see what's going on: OrderedInstructions does not support passing in uses and DT has special handling for use in PHI nodes. Support for that should be easy to add to OrderedInstructions, which I would strongly encourage to be used here for all instruction level dominance queries. Otherwise each dominates call iterates over the whole basic block in the worst case. Until then, you should be able to use it for DT.dominates(OpInst, &InsertPoint)

It would be good to add such a case to CodeMoverUtilsTest.cpp tests. which passes in 2 instructions.

Notice that isControlFlowEquivalent() is used in isSafeToMoveBefore(). And this patch changes the behaviour of isControlFlowEquivalent(). DT.dominates cannot be used to determine if moving forward anymore.

Sure. but in the patch you are still using const bool MoveForward = OI.dominates(&I, &InsertPoint); (which is equivalent to the original DT.dominates).

394

Sounds good.

Whitney updated this revision to Diff 238386.Jan 15 2020, 4:07 PM
Whitney marked 3 inline comments as done.

Addressed Florian's latest comments.
Added two new test cases.

fhahn accepted this revision.Jan 21 2020, 3:49 PM

LGTM, thanks! There a few remaining small comments from my side. It would probably best to wait a bit with committing, in case someone else has additional thoughts.

In terms of algorithm, it might be slightly faster to interleave condition discovery and checks, i.e. collect the conditions for the first BB, then while collecting conditions for the second BB bail out once we encounter a condition that's not also in the list of the first BB. But that's a minor thing and could be done as a follow up.

llvm/lib/Transforms/Utils/CodeMoverUtils.cpp
52

nit: I am not sure if SelfTy here is as descriptive as it could be. I would expect SelfTy to match the type of the enclosing class or similar. Maybe something like ConditionVectorTy would be slightly better (although I am not too concerned about the name).

208

nit: should we cover the swapped case in isEquivalent?

322

nit: I think it would be clearer to use OI.dominates, like t line 333. I think with OI.dominates, the DFS numbers should be updated on demand, automatically.

llvm/unittests/Transforms/Utils/CodeMoverUtilsTest.cpp
13

Is this required here?

60

I think you should be able to avoid creating the string line by line with \n using R"", as in https://github.com/llvm/llvm-project/blob/master/llvm/unittests/Transforms/Utils/LocalTest.cpp#L183

63

is there a reason for the frombool/tobool clutter here and in the other tests? Could we not just pass i1 %cond1 and use that directly? Also I think the dereferenceable(4) metadata can be dropped.

89

Given how often this is used to get a pointer to a basic block by name I think it would be worth adding a getBasicBlockByName helper, similar to https://github.com/llvm/llvm-project/blob/master/llvm/unittests/Analysis/ScalarEvolutionTest.cpp#L210

This revision is now accepted and ready to land.Jan 21 2020, 3:49 PM
Whitney updated this revision to Diff 239487.Jan 21 2020, 8:43 PM
Whitney marked 9 inline comments as done.

Addressed Florian's latest comments.

llvm/lib/Transforms/Utils/CodeMoverUtils.cpp
208

Let's keep isEquivalent simple, and see if other passes (e.g. GVN) can handle those cases properly first.

322

I intensionally use OI.dfsBefore instead of OI.dominates, as they are not equivalent. Unit test IsSafeToMoveTest2 illustrate the need.

This revision was automatically updated to reflect the committed changes.
nikic added a subscriber: nikic.Apr 20 2020, 1:12 PM
nikic added inline comments.
llvm/lib/Transforms/Utils/CodeMoverUtils.cpp
322

Just stumbled across this while trying to eliminate the OrderedInstructions use: The use of dfsBefore here doesn't really make sense. The dfsBefore check can luck out and give you a correct result if both I and InsertPoint *happen* to be on the same DFS path, but there's no guarantee that this is the case. You can easily see this by swapping the block order in the IsSafeToMoveTest2 test case:

diff --git llvm/unittests/Transforms/Utils/CodeMoverUtilsTest.cpp llvm/unittests/Transforms/Utils/CodeMoverUtilsTest.cpp
index cf764bf76f06..dc70c6c52717 100644
--- llvm/unittests/Transforms/Utils/CodeMoverUtilsTest.cpp
+++ llvm/unittests/Transforms/Utils/CodeMoverUtilsTest.cpp
@@ -555,13 +555,13 @@ TEST(CodeMoverUtils, IsSafeToMoveTest2) {
   std::unique_ptr<Module> M =
       parseIR(C, R"(define void @foo(i1 %cond, i32 %op0, i32 %op1) {
                  entry:
-                   br i1 %cond, label %if.then.first, label %if.end.first
+                   br i1 %cond, label %if.end.first, label %if.then.first
                  if.then.first:
                    %add = add i32 %op0, %op1
                    %user = add i32 %add, 1
                    br label %if.end.first
                  if.end.first:
-                   br i1 %cond, label %if.then.second, label %if.end.second
+                   br i1 %cond, label %if.end.second, label %if.then.second
                  if.then.second:
                    %sub_op0 = add i32 %op0, 1
                    %sub = sub i32 %sub_op0, %op1

This will make both queries return true instead of false, which is obviously not right.

I don't know how to make this code correct though, or how a notion of "forward" or "backward" on a graph would be rigorously defined.

You can of course make the code conservatively correct by requiring that I dominates InsertPoint or InsertPoint dominates I, but from what I understood you're specifically interested in cases where this is not the case.

Whitney marked an inline comment as done.Apr 20 2020, 3:48 PM
Whitney added inline comments.
llvm/lib/Transforms/Utils/CodeMoverUtils.cpp
322

You are right, it is incorrect to use dfsBefore here. I am thinking to create a bfsBefore, which should gives correct result no matter for the original IsSafeToMoveTest2 or the modified IsSafeToMoveTest2.

Why do you want to eliminate the use of OrderedInstructions, should I add bfsBefore there?

nikic added inline comments.Apr 21 2020, 9:50 AM
llvm/lib/Transforms/Utils/CodeMoverUtils.cpp
322

I don't think that bfsBefore() will help either. As a simple case, if you have an if/else, and query moving an instruction between the if and the else block, then one of them is going to have a lower BFS number, but you still can't determine "move forward" or "move backward" based on that. (In this case, the outcome should be either "no move possible" or the move has to consist of both move forward and move backward, or move backward and move forward.)

For the purpose of the dominance checks below, it would be sufficient to just check dominance for both uses and operands, independent of "MoveForward", as the use/op dominance always needs to hold. The main problem is the "collectInstructionsInBetween" below, which needs to know the scan direction.

Why do you want to eliminate the use of OrderedInstructions, should I add bfsBefore there?

OrderedInstructions is now a thin wrapper around DominatorTree and Instruction::comesBefore(). It used to be caching analysis for local dominance.

Whitney marked an inline comment as done.Apr 21 2020, 10:31 AM
Whitney added inline comments.
llvm/lib/Transforms/Utils/CodeMoverUtils.cpp
322

As currently we first check isControlFlowEquivalent, the bfs depths of the two instructions should not be the same. We can assert that this is true. And if I has a smaller bfs depth than InsertPoint, then moving forward, else moving backward.