This is an archive of the discontinued LLVM Phabricator instance.

[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

Whitney created this revision.Dec 16 2019, 3:48 PM

Thanks for working on this. I was hoping we go in this direction eventually.

I haven't looked at everything in details but I have some high-level comments we should probably address/discuss first.

We should make collectDependingConditions visible from the outside.
Can we rename Conditions into ControlConditions (also use that term instead of "depending conditions")?
I would store the information about the range (from which block to which) in the ControlCondition object so it becomes self contained.

Further comments inlined.

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

The class, members and methods need documentation.

284

What if you would only track positive conditions (negate the others) and you put them into a set. The is equivalent check will then be imple equality check on the sets. You can then also check "implication" through subset relation, and missing condition, through set difference.

Whitney updated this revision to Diff 234469.Dec 18 2019, 12:35 AM

Addressed a subset of Johannes's comments.

etiotto added inline comments.Dec 18 2019, 2:12 PM
llvm/include/llvm/Transforms/Utils/CodeMoverUtils.h
38

[suggestion]: Put const to make the member variable immutable.

74

[suggestion]: This is a factory method to construct ControlConditions right? Can you add it as a static member function in the class?

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

[suggestion]: you could use llvm:all_of to check whether the sets have the same conditions.

This is a quite deep introspection that I'd assume would be in the domain of some analysis, such as value numbering. It could ensure that equivalent conditional branches will take the same llvm::Value.

However, if your use case is loop fusion, then it might not even be necessary. Loop fusion can be made strictly more powerful by sinking the loop condition into the loop. Another pass might then be able to optimize the fused interior if the conditions are equivalent. That is,

if (c1)
  for (int i = 0; i < n; ++i)
    body1(i);
if (c2)
  for (int i = 0; i < n; ++i)
    body2(i);

can be fused to

for (int i = 0; i < n; ++i) {
  if (c1)
    body1(i);
  if (c2)
    body2(i);
}

If c1 is equivalent to c2, JumpThreading may change it to

for (int i = 0; i < n; ++i) {
  if (c1) {
    body1(i);
    body2(i);
  }
}

Hoisting c1 out of the loop again, even if c1 and c2 stay separate would be a job for LoopUnswitching.

I realize (well, I did not in the call this morning) that fusing that loop fusion will probably not improve performance unless c1 and c2 usually evaluate to true, but at least for correctness (#pragma clang loop fuse), it is valid. Profitability can be checked separately.

Whitney added a comment.EditedDec 18 2019, 4:23 PM

This is a quite deep introspection that I'd assume would be in the domain of some analysis, such as value numbering. It could ensure that equivalent conditional branches will take the same llvm::Value.

I agree that to make the ControlConditions class more powerful, we will need value numbering to check for equivalence between llvm::Values. I am considering that as future improvement. And the code is written in a way that there should be only one function need to be modified once value numbering is available to be queried.

However, if your use case is loop fusion, then it might not even be necessary. Loop fusion can be made strictly more powerful by sinking the loop condition into the loop. Another pass might then be able to optimize the fused interior if the conditions are equivalent. That is,

if (c1)
  for (int i = 0; i < n; ++i)
    body1(i);
if (c2)
  for (int i = 0; i < n; ++i)
    body2(i);

can be fused to

for (int i = 0; i < n; ++i) {
  if (c1)
    body1(i);
  if (c2)
    body2(i);
}

If c1 is equivalent to c2, JumpThreading may change it to

for (int i = 0; i < n; ++i) {
  if (c1) {
    body1(i);
    body2(i);
  }
}

Hoisting c1 out of the loop again, even if c1 and c2 stay separate would be a job for LoopUnswitching.

I realize (well, I did not in the call this morning) that fusing that loop fusion will probably not improve performance unless c1 and c2 usually evaluate to true, but at least for correctness (#pragma clang loop fuse), it is valid. Profitability can be checked separately.

To check for profitability, LoopFusion end up need to do something similar, e.g check if the two sets of control conditions it decided to sink in are equivalent, if not, then likely it is not profitable.
In addition, I imagine that it is not always possible to sink the conditions in the loop, e.g.

if (c1)
  for (int i = 0; i < n; ++i)
    body1(i);
if (c2)
  for (int i = A[x]; i < n; ++i)
    body2(i);

i in the second loop initialize with a LoadInst which is originally guarded by c2. if(c2) cannot be proven safe to move inside the loop, because of the LoadInst. Assuming A is not modified in the first loop, LoopFusion should still be able to fuse them, by moving the LoadInst to the preheader of the first loop, which by this patch can be proven control flow equivalent with the preheader of the second loop.

For LoopFusion, one use case of ControlConditions class is to check if it is safe to move intervening code around, while intervening code may not be safe to be moved out of a branch.

Whitney updated this revision to Diff 234654.Dec 18 2019, 8:07 PM
Whitney marked 6 inline comments as done.

Addressed all review comments.

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

I changed to use unordered_set. I created a ControlCondition struct instead as the type for the unordered_set. Do you think that's sufficient?

First, I really think we should have a control condition collection/handling interface. So whatever loop fusion does, if this is tested we should merge it.

I went through all but the test code now. I have some comments that we need to discuss and then I'll go over the tests so we can wrap this up.

llvm/include/llvm/Transforms/Utils/CodeMoverUtils.h
79

Nit: The comment is out of date.

82

empty is fine but it's the "container view" on this.
We should have an alternative or additional function to provide the "control condition view. I mean, if this means that ToBB has the same control conditions as FromBB we should spell it out that way.

94

The True name and the comment is confusing me. Is True different from IsTrueCondition elsewhere? If not, keep the same name. Maybe even accept a ControlCondition here to avoid duplicating the internals, e.g., what makes up a ControlCondition.

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

Nit: Add a TODO above to look at invariant loads and readnone calls.

56

You can recurse here for the operands.

Also add a TODO that mentions other extensions (e.g., boolean binary operations) and asks someone to look into reusing GVN/CSE logic here.

132

The dom tree queries (DT.dominates(BI->getSuccessor(1), CurBlock)) confuse me. The block that contains BI is the immediate dominator of CurBlock, right?
I might be mistaken here but doesn't this mean these queries are only true if the successor and cur block are the same?

If I'm right, code like the one below and a query %from -> %to should fail with the assertion above.:

from:
  br label %idom
idom:
  br i1 %c0, label %lvl0a, label %lvl0b
lvl0a:
  br i1 %c1, label %lvl1a, label %lvl1b
lvl0b:
  br i1 %c1, label %lvl1b, label %lvl1c
lvl1a:
  br label %to
lvl1b:
  ret void
lvl1c:
  br label %to
to:
  ret void

For now you can give up if the idom is not post dominated by the current block and not the predecessor block of the current one.

Whitney updated this revision to Diff 234822.Dec 19 2019, 6:00 PM
Whitney marked 7 inline comments as done.

Addressed Johannes's comments.

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

Good catch, DT.dominates(BI->getSuccessor(1), CurBlock) only true when BI->getSuccessor(1) is CurBlock.
Cannot give up if the Idom is not post dominated by the CurBlock, as when CurBlock post dominates Idom, then CurBlock is executed unconditionally from Idom, i.e. no control condition is required.
I am changing to PDT.dominates(CurBlock, BI->getSuccessor(1)).

I'm generally fine with this. Some comments below.

I'll accept it tomorrow or so if no one else posts another comment.

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

CallInst -> CallBase

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
480

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
29

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

284

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
29

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
29

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
284

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
284

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
284

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
284

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
284

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.

297

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

303

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

319

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
319

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
319

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?

392

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
319
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.

392

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
319

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
319

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).

392

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?

321

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?

61

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

64

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.

90

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.

321

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
321

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
321

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
321

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
321

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.