[CodeMoverUtils] Improve IsControlFlowEquivalent.

[Whitney]

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.

[jdoerfert]

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

222

The class, members and methods need documentation.

282

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]

Addressed a subset of Johannes's comments.

[etiotto]

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

37

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

73

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

[Meinersbur]

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]

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]

Addressed all review comments.

llvm/lib/Transforms/Utils/CodeMoverUtils.cpp

282

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?

[jdoerfert]

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

78

Nit: The comment is out of date.

81

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.

93

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]

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

[jdoerfert]

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]

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]

Addressed Johannes's comments.

[fhahn]

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

282

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]

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]

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]

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]

Addressed review comments.

[Whitney]

llvm/lib/Transforms/Utils/CodeMoverUtils.cpp

282

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]

llvm/lib/Transforms/Utils/CodeMoverUtils.cpp

282

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]

llvm/lib/Transforms/Utils/CodeMoverUtils.cpp

282

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]

llvm/lib/Transforms/Utils/CodeMoverUtils.cpp

282

equivalent values

it should probably say equal values according to the comparator.

[Whitney]

Changed to use SmallVector instead of unordered_set.

[Whitney]

llvm/lib/Transforms/Utils/CodeMoverUtils.cpp

282

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]

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

[Whitney]

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

[Whitney]

ping

[fhahn]

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.

295

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

301

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]

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]

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

[Whitney]

ping

[fhahn]

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

316

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]

Addressed Florian's latest comments.

llvm/lib/Transforms/Utils/CodeMoverUtils.cpp

316

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]

llvm/lib/Transforms/Utils/CodeMoverUtils.cpp

316

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?

387

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]

llvm/lib/Transforms/Utils/CodeMoverUtils.cpp

316

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.

387

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

[Whitney]

llvm/lib/Transforms/Utils/CodeMoverUtils.cpp

316

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]

llvm/lib/Transforms/Utils/CodeMoverUtils.cpp

316

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

387

Sounds good.

[Whitney]

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

[Whitney]

ping

[fhahn]

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?

318

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

[Whitney]

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.

318

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

[nikic]

llvm/lib/Transforms/Utils/CodeMoverUtils.cpp

318

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]

llvm/lib/Transforms/Utils/CodeMoverUtils.cpp

318

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]

llvm/lib/Transforms/Utils/CodeMoverUtils.cpp

318

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]

llvm/lib/Transforms/Utils/CodeMoverUtils.cpp

318

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.

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

 
 class BasicBlock;
 class DependenceInfo;
 class DominatorTree;
 class Instruction;
 class PostDominatorTree;
 
 /// Return true if \p I0 and \p I1 are control flow equivalent.
-/// Two instructions are control flow equivalent if when one executes,
-/// the other is guaranteed to execute. This is determined using dominators
-/// and post-dominators: if A dominates B and B post-dominates A then A and B
-/// are control-flow equivalent.
+/// Two instructions are control flow equivalent if their basic blocks are
+/// control flow equivalent.
 bool isControlFlowEquivalent(const Instruction &I0, const Instruction &I1,
                              const DominatorTree &DT,
                              const PostDominatorTree &PDT);
 
 /// Return true if \p BB0 and \p BB1 are control flow equivalent.
 /// Two basic blocks are control flow equivalent if when one executes, the other
-/// is guaranteed to execute. This is determined using dominators and
-/// post-dominators: if A dominates B and B post-dominates A then A and B are
-/// control-flow equivalent.
+/// is guaranteed to execute.
 bool isControlFlowEquivalent(const BasicBlock &BB0, const BasicBlock &BB1,
                              const DominatorTree &DT,
                              const PostDominatorTree &PDT);
 
 /// Return true if \p I can be safely moved before \p InsertPoint.
 bool isSafeToMoveBefore(Instruction &I, Instruction &InsertPoint,
-                        const DominatorTree &DT, const PostDominatorTree &PDT,
+                        DominatorTree &DT, const PostDominatorTree &PDT,
                         DependenceInfo &DI);
 
 /// Move instructions from \p FromBB bottom up to the beginning of \p ToBB
 /// when proven safe.
-void moveInstsBottomUp(BasicBlock &FromBB, BasicBlock &ToBB,
-                       const DominatorTree &DT, const PostDominatorTree &PDT,
-                       DependenceInfo &DI);
+void moveInstsBottomUp(BasicBlock &FromBB, BasicBlock &ToBB, DominatorTree &DT,
+                       const PostDominatorTree &PDT, DependenceInfo &DI);
 
 } // end namespace llvm
 
 #endif // LLVM_TRANSFORMS_UTILS_CODEMOVERUTILS_H

llvm/lib/Transforms/Utils/CodeMoverUtils.cpp

 //===- CodeMoverUtils.cpp - CodeMover Utilities ----------------------------==//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 // This family of functions perform movements on basic blocks, and instructions
 // contained within a function.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Transforms/Utils/CodeMoverUtils.h"
+#include "llvm/ADT/Optional.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/DependenceAnalysis.h"
+#include "llvm/Analysis/OrderedInstructions.h"
 #include "llvm/Analysis/PostDominators.h"
 #include "llvm/Analysis/ValueTracking.h"
 #include "llvm/IR/Dominators.h"
 
 using namespace llvm;
 
 #define DEBUG_TYPE "codemover-utils"
 
 STATISTIC(HasDependences,
           "Cannot move across instructions that has memory dependences");
 STATISTIC(MayThrowException, "Cannot move across instructions that may throw");
 STATISTIC(NotControlFlowEquivalent,
           "Instructions are not control flow equivalent");
 STATISTIC(NotMovedPHINode, "Movement of PHINodes are not supported");
 STATISTIC(NotMovedTerminator, "Movement of Terminator are not supported");
 
+namespace {
+/// Represent a control condition. A control condition is a condition of a
+/// terminator to decide which successors to execute. The pointer field
+/// represents the address of the condition of the terminator. The integer field
+/// is a bool, it is true when the basic block is executed when V is true. For
+/// example, `br %cond, bb0, bb1` %cond is a control condition of bb0 with the
+/// integer field equals to true, while %cond is a control condition of bb1 with
+/// the integer field equals to false.
+using ControlCondition = PointerIntPair<Value *, 1, bool>;
+raw_ostream &operator<<(raw_ostream &OS, const ControlCondition &C) {
+  OS << "[" << *C.getPointer() << ", " << (C.getInt() ? "true" : "false")
+     << "]";
+  return OS;
+}
+
+/// Represent a set of control conditions required to execute ToBB from FromBB.
+class ControlConditions {
+  using SelfTy = SmallVector<ControlCondition, 6>;
+
+  /// A SmallVector of control conditions.
+  SelfTy Conditions;
+
+public:
+  /// Return a ControlConditions which stores all conditions required to execute
+  /// \p BB from \p Dominator. If \p MaxLookup is non-zero, it limit for the
+  /// number of conditions to collect. Return None if not all conditions are
+  /// collected successfully.
+  static Optional<const ControlConditions>
+  collectControlConditions(const BasicBlock &BB, const BasicBlock &Dominator,
+                           const DominatorTree &DT,
+                           const PostDominatorTree &PDT,
+                           unsigned MaxLookup = 6);
+
+  /// Return true if there exists no control conditions required to execute ToBB
+  /// from FromBB.
+  bool isUnconditional() const { return Conditions.empty(); }
+
+  /// Return a constant reference of Conditions.
+  const SelfTy &getControlConditions() const { return Conditions; }
+
+  /// Add \p V as one of the ControlCondition in Condition with IsTrueCondition
+  /// equals to \p True. Return true if inserted successfully.
+  bool addControlCondition(ControlCondition C);
+
+  /// Return true if for all control conditions in Conditions, there exists an
+  /// equivalent control condition in \p Other.Conditions.
+  bool isEquivalent(const ControlConditions &Other) const;
+
+  /// Return true if \p C1 and \p C2 are equivalent.
+  static bool isEquivalent(const ControlCondition &C1,
+                           const ControlCondition &C2);
+
+private:
+  ControlConditions() = default;
+
+  static bool isEquivalent(const Value &V1, const Value &V2);
+  static bool isInverse(const Value &V1, const Value &V2);
+};
+} // namespace
+
+Optional<const ControlConditions> ControlConditions::collectControlConditions(
+    const BasicBlock &BB, const BasicBlock &Dominator, const DominatorTree &DT,
+    const PostDominatorTree &PDT, unsigned MaxLookup) {
+  assert(DT.dominates(&Dominator, &BB) && "Expecting Dominator to dominate BB");
+
+  ControlConditions Conditions;
+  unsigned NumConditions = 0;
+
+  // BB is executed unconditional from itself.
+  if (&Dominator == &BB)
+    return Conditions;
+
+  const BasicBlock *CurBlock = &BB;
+  // Walk up the dominator tree from the associated DT node for BB to the
+  // associated DT node for Dominator.
+  do {
+    assert(DT.getNode(CurBlock) && "Expecting a valid DT node for CurBlock");
+    BasicBlock *IDom = DT.getNode(CurBlock)->getIDom()->getBlock();
+    assert(DT.dominates(&Dominator, IDom) &&
+           "Expecting Dominator to dominate IDom");
+
+    // Limitation: can only handle branch instruction currently.
+    const BranchInst *BI = dyn_cast<BranchInst>(IDom->getTerminator());
+    if (!BI)
+      return None;
+
+    bool Inserted = false;
+    if (PDT.dominates(CurBlock, IDom)) {
+      LLVM_DEBUG(dbgs() << CurBlock->getName()
+                        << " is executed unconditionally from "
+                        << IDom->getName() << "\n");
+    } else if (PDT.dominates(CurBlock, BI->getSuccessor(0))) {
+      LLVM_DEBUG(dbgs() << CurBlock->getName() << " is executed when \""
+                        << *BI->getCondition() << "\" is true from "
+                        << IDom->getName() << "\n");
+      Inserted = Conditions.addControlCondition(
+          ControlCondition(BI->getCondition(), true));
+    } else if (PDT.dominates(CurBlock, BI->getSuccessor(1))) {
+      LLVM_DEBUG(dbgs() << CurBlock->getName() << " is executed when \""
+                        << *BI->getCondition() << "\" is false from "
+                        << IDom->getName() << "\n");
+      Inserted = Conditions.addControlCondition(
+          ControlCondition(BI->getCondition(), false));
+    } else
+      return None;
+
+    if (Inserted)
+      ++NumConditions;
+
+    if (MaxLookup != 0 && NumConditions > MaxLookup)
+      return None;
+
+    CurBlock = IDom;
+  } while (CurBlock != &Dominator);
+
+  return Conditions;
+}
+
+bool ControlConditions::addControlCondition(ControlCondition C) {
+  bool Inserted = false;
+  if (none_of(Conditions, [&C](ControlCondition &Exists) {
+        return ControlConditions::isEquivalent(C, Exists);
+      })) {
+    Conditions.push_back(C);
+    Inserted = true;
+  }
+
+  LLVM_DEBUG(dbgs() << (Inserted ? "Inserted " : "Not inserted ") << C << "\n");
+  return Inserted;
+}
+
+bool ControlConditions::isEquivalent(const ControlConditions &Other) const {
+  if (Conditions.empty() && Other.Conditions.empty())
+    return true;
+
+  if (Conditions.size() != Other.Conditions.size())
+    return false;
+
+  return llvm::all_of(Conditions, [&Other](const ControlCondition &C) {
+    return any_of(Other.Conditions, [&C](const ControlCondition &OtherC) {
+      return ControlConditions::isEquivalent(C, OtherC);
+    });
+  });
+}
+
+bool ControlConditions::isEquivalent(const ControlCondition &C1,
+                                     const ControlCondition &C2) {
+  if (C1.getInt() == C2.getInt()) {
+    if (isEquivalent(*C1.getPointer(), *C2.getPointer()))
+      return true;
+  } else if (isInverse(*C1.getPointer(), *C2.getPointer()))
+    return true;
+
+  return false;
+}
+
+// FIXME: Use SCEV and reuse GVN/CSE logic to check for equivalence between
+// Values.
+bool ControlConditions::isEquivalent(const Value &V1, const Value &V2) {
+  return (&V1 == &V2);
+}
+
+bool ControlConditions::isInverse(const Value &V1, const Value &V2) {
+  if (const CmpInst *Cmp1 = dyn_cast<CmpInst>(&V1))
+    if (const CmpInst *Cmp2 = dyn_cast<CmpInst>(&V2)) {
+      if (Cmp1->getPredicate() == Cmp2->getInversePredicate() &&
+          Cmp1->getOperand(0) == Cmp2->getOperand(0) &&
+          Cmp1->getOperand(1) == Cmp2->getOperand(1))
+        return true;
+
+      if (Cmp1->getPredicate() ==
+              CmpInst::getSwappedPredicate(Cmp2->getInversePredicate()) &&
+          Cmp1->getOperand(0) == Cmp2->getOperand(1) &&
+          Cmp1->getOperand(1) == Cmp2->getOperand(0))
+        return true;
+    }
+  return false;
+}
+
 bool llvm::isControlFlowEquivalent(const Instruction &I0, const Instruction &I1,
                                    const DominatorTree &DT,
                                    const PostDominatorTree &PDT) {
   return isControlFlowEquivalent(*I0.getParent(), *I1.getParent(), DT, PDT);
 }
 
 bool llvm::isControlFlowEquivalent(const BasicBlock &BB0, const BasicBlock &BB1,
                                    const DominatorTree &DT,
                                    const PostDominatorTree &PDT) {
   if (&BB0 == &BB1)
     return true;
 
-  return ((DT.dominates(&BB0, &BB1) && PDT.dominates(&BB1, &BB0)) ||
-          (PDT.dominates(&BB0, &BB1) && DT.dominates(&BB1, &BB0)));
+  if ((DT.dominates(&BB0, &BB1) && PDT.dominates(&BB1, &BB0)) ||
+      (PDT.dominates(&BB0, &BB1) && DT.dominates(&BB1, &BB0)))
+    return true;
+
+  // If the set of conditions required to execute BB0 and BB1 from their common
+  // dominator are the same, then BB0 and BB1 are control flow equivalent.
+  const BasicBlock *CommonDominator = DT.findNearestCommonDominator(&BB0, &BB1);
+  LLVM_DEBUG(dbgs() << "The nearest common dominator of " << BB0.getName()
+                    << " and " << BB1.getName() << " is "
+                    << CommonDominator->getName() << "\n");
+
+  Optional<const ControlConditions> BB0Conditions =
+      ControlConditions::collectControlConditions(BB0, *CommonDominator, DT,
+                                                  PDT);
+  if (BB0Conditions == None)
+    return false;
+
+  Optional<const ControlConditions> BB1Conditions =
+      ControlConditions::collectControlConditions(BB1, *CommonDominator, DT,
+                                                  PDT);
+  if (BB1Conditions == None)
+    return false;
+
+  return BB0Conditions->isEquivalent(*BB1Conditions);
 }
 
 static bool reportInvalidCandidate(const Instruction &I,
                                    llvm::Statistic &Stat) {
   ++Stat;
   LLVM_DEBUG(dbgs() << "Unable to move instruction: " << I << ". "
                     << Stat.getDesc());
   return false;
else {
       for (BasicBlock *Succ : successors(&I))
         WorkList.insert(&Succ->front());
     }
   };
 
   SmallPtrSet<Instruction *, 10> WorkList;
   getNextInsts(StartInst, WorkList);
   while (!WorkList.empty()) {
     Instruction *CurInst = *WorkList.begin();
     WorkList.erase(CurInst);
 
     if (CurInst == &EndInst)
       continue;
 
     if (!InBetweenInsts.insert(CurInst).second)
       continue;
 
     getNextInsts(*CurInst, WorkList);
   }
 }
 
 bool llvm::isSafeToMoveBefore(Instruction &I, Instruction &InsertPoint,
-                              const DominatorTree &DT,
-                              const PostDominatorTree &PDT,
+                              DominatorTree &DT, const PostDominatorTree &PDT,
                               DependenceInfo &DI) {
   // Cannot move itself before itself.
   if (&I == &InsertPoint)
     return false;
 
   // Not moved.
   if (I.getNextNode() == &InsertPoint)
     return true;
 
   if (isa<PHINode>(I) || isa<PHINode>(InsertPoint))
     return reportInvalidCandidate(I, NotMovedPHINode);
 
   if (I.isTerminator())
     return reportInvalidCandidate(I, NotMovedTerminator);
 
   // TODO remove this limitation.
   if (!isControlFlowEquivalent(I, InsertPoint, DT, PDT))
     return reportInvalidCandidate(I, NotControlFlowEquivalent);
 
-  // As I and InsertPoint are control flow equivalent, if I dominates
-  // InsertPoint, then I comes before InsertPoint.
-  const bool MoveForward = DT.dominates(&I, &InsertPoint);
+  const bool MoveForward = OrderedInstructions(&DT).dominates(&I, &InsertPoint);
   if (MoveForward) {
     // When I is being moved forward, we need to make sure the InsertPoint
     // dominates every users. Or else, a user may be using an undefined I.
     for (const Use &U : I.uses())
       if (auto *UserInst = dyn_cast<Instruction>(U.getUser()))
         if (UserInst != &InsertPoint && !DT.dominates(&InsertPoint, U))
           return false;
   } else {
     // When I is being moved backward, we need to make sure all its opernads
     // dominates the InsertPoint. Or else, an operand may be undefined for I.
if (std::any_of(InstsToCheck.begin(), InstsToCheck.end(),
                     return false;
                   }))
     return reportInvalidCandidate(I, HasDependences);
 
   return true;
 }
 
 void llvm::moveInstsBottomUp(BasicBlock &FromBB, BasicBlock &ToBB,
-                             const DominatorTree &DT,
-                             const PostDominatorTree &PDT, DependenceInfo &DI) {
+                             DominatorTree &DT, const PostDominatorTree &PDT,
+                             DependenceInfo &DI) {
   for (auto It = ++FromBB.rbegin(); It != FromBB.rend();) {
     Instruction *MovePos = ToBB.getFirstNonPHIOrDbg();
     Instruction &I = *It;
     // Increment the iterator before modifying FromBB.
     ++It;
 
     if (isSafeToMoveBefore(I, *MovePos, DT, PDT, DI))
       I.moveBefore(MovePos);
   }
 }

llvm/unittests/Transforms/Utils/CodeMoverUtilsTest.cpp

 //===- CodeMoverUtils.cpp - Unit tests for CodeMoverUtils ---------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Transforms/Utils/CodeMoverUtils.h"
 #include "llvm/Analysis/AssumptionCache.h"
 #include "llvm/Analysis/DependenceAnalysis.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/PostDominators.h"
 #include "llvm/Analysis/ScalarEvolutionExpander.h"
 #include "llvm/AsmParser/Parser.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/LLVMContext.h"
 #include "llvm/Support/SourceMgr.h"
 #include "gtest/gtest.h"
 
 using namespace llvm;
static void run(Module &M, StringRef FuncName,
   AssumptionCache AC(*F);
   AliasAnalysis AA(TLI);
   LoopInfo LI(DT);
   ScalarEvolution SE(*F, TLI, AC, DT, LI);
   DependenceInfo DI(F, &AA, &SE, &LI);
   Test(*F, DT, PDT, DI);
 }
 
-TEST(CodeMoverUtils, BasicTest) {
+TEST(CodeMoverUtils, IsControlFlowEquivalentSimpleTest) {
+  LLVMContext C;
+
+  // void foo(int &i, bool cond1, bool cond2) {
+  //   if (cond1)
+  //     i = 1;
+  //   if (cond1)
+  //     i = 2;
+  //   if (cond2)
+  //     i = 3;
+  // }
+  std::unique_ptr<Module> M =
+      parseIR(C, "define void @foo(i32* dereferenceable(4) %i, i1 zeroext "
+                 "%cond1, i1 zeroext %cond2) {\n"
+                 "entry:\n"
+                 "  %frombool1 = zext i1 %cond1 to i8\n"
+                 "  %frombool2 = zext i1 %cond2 to i8\n"
+                 "  %tobool1 = trunc i8 %frombool1 to i1\n"
+                 "  br i1 %tobool1, label %if.first, label %if.first.end\n"
+                 "if.first:\n"
+                 "  store i32 1, i32* %i, align 4\n"
+                 "  br label %if.first.end\n"
+                 "if.first.end:\n"
+                 "  br i1 %tobool1, label %if.second, label %if.second.end\n"
+                 "if.second:\n"
+                 "  store i32 2, i32* %i, align 4\n"
+                 "  br label %if.second.end\n"
+                 "if.second.end:\n"
+                 "  %tobool2 = trunc i8 %frombool2 to i1\n"
+                 "  br i1 %tobool2, label %if.third, label %if.third.end\n"
+                 "if.third:\n"
+                 "  store i32 3, i32* %i, align 4\n"
+                 "  br label %if.third.end\n"
+                 "if.third.end:\n"
+                 "  ret void\n"
+                 "}\n");
+  run(*M, "foo",
+      [&](Function &F, DominatorTree &DT, PostDominatorTree &PDT,
+          DependenceInfo &DI) {
+        Function::iterator FI = F.begin();
+        FI++;
+        BasicBlock *FirstIfBody = &*(FI++);
+        assert(FirstIfBody->getName() == "if.first" &&
+               "Expecting BasicBlock if.first");
+        EXPECT_TRUE(
+            isControlFlowEquivalent(*FirstIfBody, *FirstIfBody, DT, PDT));
+        FI++;
+        BasicBlock *SecondIfBody = &*(FI++);
+        assert(SecondIfBody->getName() == "if.second" &&
+               "Expecting BasicBlock if.second");
+        EXPECT_TRUE(
+            isControlFlowEquivalent(*FirstIfBody, *SecondIfBody, DT, PDT));
+
+        FI++;
+        BasicBlock *ThirdIfBody = &*(FI++);
+        assert(ThirdIfBody->getName() == "if.third" &&
+               "Expecting BasicBlock if.third");
+        EXPECT_FALSE(
+            isControlFlowEquivalent(*FirstIfBody, *ThirdIfBody, DT, PDT));
+        EXPECT_FALSE(
+            isControlFlowEquivalent(*SecondIfBody, *ThirdIfBody, DT, PDT));
+      });
+}
+
+TEST(CodeMoverUtils, IsControlFlowEquivalentOppositeCondTest) {
+  LLVMContext C;
+
+  // void foo(int &i, unsigned X, unsigned Y) {
+  //   if (X < Y)
+  //     i = 1;
+  //   if (Y > X)
+  //     i = 2;
+  //   if (X >= Y)
+  //     i = 3;
+  //   else
+  //     i = 4;
+  //   if (X == Y)
+  //     i = 5;
+  //   if (Y == X)
+  //     i = 6;
+  //   else
+  //     i = 7;
+  //   if (X != Y)
+  //     i = 8;
+  //   else
+  //     i = 9;
+  // }
+  std::unique_ptr<Module> M =
+      parseIR(C, "define void @foo(i32* dereferenceable(4) %i, i32 zeroext %X, "
+                 "i32 zeroext %Y) {\n"
+                 "entry:\n"
+                 "  %cmp1 = icmp ult i32 %X, %Y\n"
+                 "  br i1 %cmp1, label %if.first, label %if.first.end\n"
+                 "if.first:\n"
+                 "  store i32 1, i32* %i, align 4\n"
+                 "  br label %if.first.end\n"
+                 "if.first.end:\n"
+                 "  %cmp2 = icmp ugt i32 %Y, %X\n"
+                 "  br i1 %cmp2, label %if.second, label %if.second.end\n"
+                 "if.second:\n"
+                 "  store i32 2, i32* %i, align 4\n"
+                 "  br label %if.second.end\n"
+                 "if.second.end:\n"
+                 "  %cmp3 = icmp uge i32 %X, %Y\n"
+                 "  br i1 %cmp3, label %if.third, label %if.third.else\n"
+                 "if.third:\n"
+                 "  store i32 3, i32* %i, align 4\n"
+                 "  br label %if.third.end\n"
+                 "if.third.else:\n"
+                 "  store i32 4, i32* %i, align 4\n"
+                 "  br label %if.third.end\n"
+                 "if.third.end:\n"
+                 "  %cmp4 = icmp eq i32 %X, %Y\n"
+                 "  br i1 %cmp4, label %if.fourth, label %if.fourth.end\n"
+                 "if.fourth:\n"
+                 "  store i32 5, i32* %i, align 4\n"
+                 "  br label %if.fourth.end\n"
+                 "if.fourth.end:\n"
+                 "  %cmp5 = icmp eq i32 %Y, %X\n"
+                 "  br i1 %cmp5, label %if.fifth, label %if.fifth.else\n"
+                 "if.fifth:\n"
+                 "  store i32 6, i32* %i, align 4\n"
+                 "  br label %if.fifth.end\n"
+                 "if.fifth.else:\n"
+                 "  store i32 7, i32* %i, align 4\n"
+                 "  br label %if.fifth.end\n"
+                 "if.fifth.end:\n"
+                 "  %cmp6 = icmp ne i32 %X, %Y\n"
+                 "  br i1 %cmp6, label %if.sixth, label %if.sixth.else\n"
+                 "if.sixth:\n"
+                 "  store i32 8, i32* %i, align 4\n"
+                 "  br label %if.sixth.end\n"
+                 "if.sixth.else:\n"
+                 "  store i32 9, i32* %i, align 4\n"
+                 "  br label %if.sixth.end\n"
+                 "if.sixth.end:\n"
+                 "  ret void\n"
+                 "}\n");
+  run(*M, "foo",
+      [&](Function &F, DominatorTree &DT, PostDominatorTree &PDT,
+          DependenceInfo &DI) {
+        Function::iterator FI = F.begin();
+        FI++;
+        BasicBlock *FirstIfBody = &*(FI++);
+        assert(FirstIfBody->getName() == "if.first" &&
+               "Expecting BasicBlock if.first");
+        FI++;
+        BasicBlock *SecondIfBody = &*(FI++);
+        assert(SecondIfBody->getName() == "if.second" &&
+               "Expecting BasicBlock if.second");
+        FI++;
+        BasicBlock *ThirdIfBody = &*(FI++);
+        assert(ThirdIfBody->getName() == "if.third" &&
+               "Expecting BasicBlock if.third");
+        BasicBlock *ThirdElseBody = &*(FI++);
+        assert(ThirdElseBody->getName() == "if.third.else" &&
+               "Expecting BasicBlock if.third.else");
+        EXPECT_TRUE(
+            isControlFlowEquivalent(*FirstIfBody, *ThirdElseBody, DT, PDT));
+        EXPECT_TRUE(
+            isControlFlowEquivalent(*SecondIfBody, *ThirdElseBody, DT, PDT));
+        EXPECT_FALSE(
+            isControlFlowEquivalent(*ThirdIfBody, *ThirdElseBody, DT, PDT));
+
+        FI++;
+        BasicBlock *FourthIfBody = &*(FI++);
+        assert(FourthIfBody->getName() == "if.fourth" &&
+               "Expecting BasicBlock if.fourth");
+        FI++;
+        BasicBlock *FifthIfBody = &*(FI++);
+        assert(FifthIfBody->getName() == "if.fifth" &&
+               "Expecting BasicBlock if.fifth");
+        BasicBlock *FifthElseBody = &*(FI++);
+        assert(FifthElseBody->getName() == "if.fifth.else" &&
+               "Expecting BasicBlock if.fifth.else");
+        EXPECT_FALSE(
+            isControlFlowEquivalent(*FifthIfBody, *FifthElseBody, DT, PDT));
+        FI++;
+        BasicBlock *SixthIfBody = &*(FI++);
+        assert(SixthIfBody->getName() == "if.sixth" &&
+               "Expecting BasicBlock if.sixth");
+        EXPECT_TRUE(
+            isControlFlowEquivalent(*FifthElseBody, *SixthIfBody, DT, PDT));
+        BasicBlock *SixthElseBody = &*(FI++);
+        assert(SixthElseBody->getName() == "if.sixth.else" &&
+               "Expecting BasicBlock if.sixth.else");
+        EXPECT_TRUE(
+            isControlFlowEquivalent(*FourthIfBody, *SixthElseBody, DT, PDT));
+        EXPECT_TRUE(
+            isControlFlowEquivalent(*FifthIfBody, *SixthElseBody, DT, PDT));
+      });
+}
+
+TEST(CodeMoverUtils, IsControlFlowEquivalentCondNestTest) {
+  LLVMContext C;
+
+  // void foo(int &i, bool cond1, bool cond2) {
+  //   if (cond1)
+  //     if (cond2)
+  //       i = 1;
+  //   if (cond2)
+  //     if (cond1)
+  //       i = 2;
+  // }
+  std::unique_ptr<Module> M = parseIR(
+      C, "define void @foo(i32* dereferenceable(4) %i, i1 zeroext %cond1, i1 "
+         "zeroext %cond2) {\n"
+         "entry:\n"
+         "  %frombool1 = zext i1 %cond1 to i8\n"
+         "  %frombool2 = zext i1 %cond2 to i8\n"
+         "  %tobool1 = trunc i8 %frombool1 to i1\n"
+         "  %tobool2 = trunc i8 %frombool2 to i1\n"
+         "  br i1 %tobool1, label %if.outer.first, label %if.first.end\n"
+         "if.outer.first:\n"
+         "  br i1 %tobool2, label %if.inner.first, label %if.first.end\n"
+         "if.inner.first:\n"
+         "  store i32 1, i32* %i, align 4\n"
+         "  br label %if.first.end\n"
+         "if.first.end:\n"
+         "  br i1 %tobool2, label %if.outer.second, label %if.second.end\n"
+         "if.outer.second:\n"
+         "  br i1 %tobool1, label %if.inner.second, label %if.second.end\n"
+         "if.inner.second:\n"
+         "  store i32 2, i32* %i, align 4\n"
+         "  br label %if.second.end\n"
+         "if.second.end:\n"
+         "  ret void\n"
+         "}\n");
+  run(*M, "foo",
+      [&](Function &F, DominatorTree &DT, PostDominatorTree &PDT,
+          DependenceInfo &DI) {
+        Function::iterator FI = F.begin();
+        FI++;
+        BasicBlock *FirstOuterIfBody = &*(FI++);
+        assert(FirstOuterIfBody->getName() == "if.outer.first" &&
+               "Expecting BasicBlock if.outer.first");
+        BasicBlock *FirstInnerIfBody = &*(FI++);
+        assert(FirstInnerIfBody->getName() == "if.inner.first" &&
+               "Expecting BasicBlock if.inner.first");
+        FI++;
+        BasicBlock *SecondOuterIfBody = &*(FI++);
+        assert(SecondOuterIfBody->getName() == "if.outer.second" &&
+               "Expecting BasicBlock if.outer.second");
+        BasicBlock *SecondInnerIfBody = &*(FI++);
+        assert(SecondInnerIfBody->getName() == "if.inner.second" &&
+               "Expecting BasicBlock if.inner.second");
+        EXPECT_TRUE(isControlFlowEquivalent(*FirstInnerIfBody,
+                                            *SecondInnerIfBody, DT, PDT));
+        EXPECT_FALSE(isControlFlowEquivalent(*FirstOuterIfBody,
+                                             *SecondOuterIfBody, DT, PDT));
+        EXPECT_FALSE(isControlFlowEquivalent(*FirstOuterIfBody,
+                                             *SecondInnerIfBody, DT, PDT));
+        EXPECT_FALSE(isControlFlowEquivalent(*FirstInnerIfBody,
+                                             *SecondOuterIfBody, DT, PDT));
+      });
+}
+
+TEST(CodeMoverUtils, IsControlFlowEquivalentImbalanceTest) {
+  LLVMContext C;
+
+  // void foo(int &i, bool cond1, bool cond2) {
+  //   if (cond1)
+  //     if (cond2)
+  //       if (cond3)
+  //         i = 1;
+  //   if (cond2)
+  //     if (cond3)
+  //       i = 2;
+  //   if (cond1)
+  //     if (cond1)
+  //       i = 3;
+  //   if (cond1)
+  //     i = 4;
+  // }
+  std::unique_ptr<Module> M = parseIR(
+      C, "define void @foo(i32* dereferenceable(4) %i, i1 zeroext "
+         "%cond1, i1 zeroext %cond2, i1 zeroext %cond3) {\n"
+         "entry:\n"
+         "  %frombool1 = zext i1 %cond1 to i8\n"
+         "  %frombool2 = zext i1 %cond2 to i8\n"
+         "  %frombool3 = zext i1 %cond3 to i8\n"
+         "  %tobool1 = trunc i8 %frombool1 to i1\n"
+         "  br i1 %tobool1, label %if.outer.first, label %if.first.end\n"
+         "if.outer.first:\n"
+         "  %tobool21 = trunc i8 %frombool2 to i1\n"
+         "  br i1 %tobool21, label %if.middle.first, label %if.first.end\n"
+         "if.middle.first:\n"
+         "  %tobool31 = trunc i8 %frombool3 to i1\n"
+         "  br i1 %tobool31, label %if.inner.first, label %if.first.end\n"
+         "if.inner.first:\n"
+         "  store i32 1, i32* %i, align 4\n"
+         "  br label %if.first.end\n"
+         "if.first.end:\n"
+         "  %tobool22 = trunc i8 %frombool2 to i1\n"
+         "  br i1 %tobool22, label %if.outer.second, label %if.second.end\n"
+         "if.outer.second:\n"
+         "  %tobool32 = trunc i8 %frombool3 to i1\n"
+         "  br i1 %tobool32, label %if.inner.second, label %if.second.end\n"
+         "if.inner.second:\n"
+         "  store i32 2, i32* %i, align 4\n"
+         "  br label %if.second.end\n"
+         "if.second.end:\n"
+         "  br i1 %tobool1, label %if.outer.third, label %if.third.end\n"
+         "if.outer.third:\n"
+         "  br i1 %tobool1, label %if.inner.third, label %if.third.end\n"
+         "if.inner.third:\n"
+         "  store i32 3, i32* %i, align 4\n"
+         "  br label %if.third.end\n"
+         "if.third.end:\n"
+         "  br i1 %tobool1, label %if.fourth, label %if.fourth.end\n"
+         "if.fourth:\n"
+         "  store i32 4, i32* %i, align 4\n"
+         "  br label %if.fourth.end\n"
+         "if.fourth.end:\n"
+         "  ret void\n"
+         "}\n");
+  run(*M, "foo",
+      [&](Function &F, DominatorTree &DT, PostDominatorTree &PDT,
+          DependenceInfo &DI) {
+        Function::iterator FI = F.begin();
+        FI++; // entry
+        FI++; // if.outer.first
+        FI++; // if.middle.first
+        BasicBlock *FirstIfBody = &*(FI++);
+        assert(FirstIfBody->getName() == "if.inner.first" &&
+               "Expecting BasicBlock if.inner.first");
+        FI++; // if.first.end
+        FI++; // if.outer.second
+        BasicBlock *SecondIfBody = &*(FI++);
+        assert(SecondIfBody->getName() == "if.inner.second" &&
+               "Expecting BasicBlock if.inner.second");
+        EXPECT_FALSE(
+            isControlFlowEquivalent(*FirstIfBody, *SecondIfBody, DT, PDT));
+
+        FI++; // if.second.end
+        FI++; // if.outer.third
+        BasicBlock *ThirdIfBody = &*(FI++);
+        assert(ThirdIfBody->getName() == "if.inner.third" &&
+               "Expecting BasicBlock if.inner.third");
+        FI++; // if.third.end
+        BasicBlock *FourthIfBody = &*(FI++);
+        assert(FourthIfBody->getName() == "if.fourth" &&
+               "Expecting BasicBlock if.fourth");
+        EXPECT_TRUE(
+            isControlFlowEquivalent(*ThirdIfBody, *FourthIfBody, DT, PDT));
+      });
+}
+
+TEST(CodeMoverUtils, IsControlFlowEquivalentPointerTest) {
+  LLVMContext C;
+
+  // void foo(int &i, int *cond) {
+  //   if (*cond)
+  //     i = 1;
+  //   if (*cond)
+  //     i = 2;
+  //   *cond = 1;
+  //   if (*cond)
+  //     i = 3;
+  // }
+  std::unique_ptr<Module> M =
+      parseIR(C, "define void @foo(i32* dereferenceable(4) %i, i32* %cond) {\n"
+                 "entry:\n"
+                 "  %0 = load i32, i32* %cond, align 4\n"
+                 "  %tobool1 = icmp ne i32 %0, 0\n"
+                 "  br i1 %tobool1, label %if.first, label %if.first.end\n"
+                 "if.first:\n"
+                 "  store i32 1, i32* %i, align 4\n"
+                 "  br label %if.first.end\n"
+                 "if.first.end:\n"
+                 "  %1 = load i32, i32* %cond, align 4\n"
+                 "  %tobool2 = icmp ne i32 %1, 0\n"
+                 "  br i1 %tobool2, label %if.second, label %if.second.end\n"
+                 "if.second:\n"
+                 "  store i32 2, i32* %i, align 4\n"
+                 "  br label %if.second.end\n"
+                 "if.second.end:\n"
+                 "  store i32 1, i32* %cond, align 4\n"
+                 "  %2 = load i32, i32* %cond, align 4\n"
+                 "  %tobool3 = icmp ne i32 %2, 0\n"
+                 "  br i1 %tobool3, label %if.third, label %if.third.end\n"
+                 "if.third:\n"
+                 "  store i32 3, i32* %i, align 4\n"
+                 "  br label %if.third.end\n"
+                 "if.third.end:\n"
+                 "  ret void\n"
+                 "}\n");
+  run(*M, "foo",
+      [&](Function &F, DominatorTree &DT, PostDominatorTree &PDT,
+          DependenceInfo &DI) {
+        Function::iterator FI = F.begin();
+        FI++;
+        BasicBlock *FirstIfBody = &*(FI++);
+        assert(FirstIfBody->getName() == "if.first" &&
+               "Expecting BasicBlock if.first");
+        FI++;
+        BasicBlock *SecondIfBody = &*(FI++);
+        assert(SecondIfBody->getName() == "if.second" &&
+               "Expecting BasicBlock if.second");
+        // Limitation: if we can prove cond haven't been modify between %0 and
+        // %1, then we can prove FirstIfBody and SecondIfBody are control flow
+        // equivalent.
+        EXPECT_FALSE(
+            isControlFlowEquivalent(*FirstIfBody, *SecondIfBody, DT, PDT));
+
+        FI++;
+        BasicBlock *ThirdIfBody = &*(FI++);
+        assert(ThirdIfBody->getName() == "if.third" &&
+               "Expecting BasicBlock if.third");
+        EXPECT_FALSE(
+            isControlFlowEquivalent(*FirstIfBody, *ThirdIfBody, DT, PDT));
+        EXPECT_FALSE(
+            isControlFlowEquivalent(*SecondIfBody, *ThirdIfBody, DT, PDT));
+      });
+}
+
+TEST(CodeMoverUtils, IsControlFlowEquivalentNotPostdomTest) {
+  LLVMContext C;
+
+  // void foo(bool cond1, bool cond2) {
+  //   if (cond1) {
+  //     if (cond2)
+  //       return;
+  //   } else
+  //     if (cond2)
+  //       return;
+  //   return;
+  // }
+  std::unique_ptr<Module> M =
+      parseIR(C, "define void @foo(i1 %cond1, i1 %cond2) {\n"
+                 "idom:\n"
+                 "  br i1 %cond1, label %succ0, label %succ1\n"
+                 "succ0:\n"
+                 "  br i1 %cond2, label %succ0ret, label %succ0succ1\n"
+                 "succ0ret:\n"
+                 "  ret void\n"
+                 "succ0succ1:\n"
+                 "  br label %bb\n"
+                 "succ1:\n"
+                 "  br i1 %cond2, label %succ1ret, label %succ1succ1\n"
+                 "succ1ret:\n"
+                 "  ret void\n"
+                 "succ1succ1:\n"
+                 "  br label %bb\n"
+                 "bb:\n"
+                 "  ret void\n"
+                 "}\n");
+  run(*M, "foo",
+      [&](Function &F, DominatorTree &DT, PostDominatorTree &PDT,
+          DependenceInfo &DI) {
+        BasicBlock &Idom = F.front();
+        assert(Idom.getName() == "idom" && "Expecting BasicBlock idom");
+        BasicBlock &BB = F.back();
+        assert(BB.getName() == "bb" && "Expecting BasicBlock bb");
+        EXPECT_FALSE(isControlFlowEquivalent(Idom, BB, DT, PDT));
+      });
+}
+
+TEST(CodeMoverUtils, IsSafeToMoveTest) {
   LLVMContext C;
 
   // void safecall() noexcept willreturn nosync;
   // void unsafecall();
   // void foo(int * __restrict__ A, int * __restrict__ B, int * __restrict__ C,
   //          long N) {
   //   X = N / 1;
   //   safecall();