[SimplifyCFG] Hoist implying condition

[nikic]

https://alive2.llvm.org/ce/z/Dj_5qY

define i32 @src(ptr %contents.0, i64 %contents.1) {
start:
  %cmp1 = icmp ugt i64 %contents.1, 7
  br i1 %cmp1, label %if, label %exit

if:
  %load = load i64, ptr %contents.0
  %cmp2 = icmp eq i64 %load, 123
  %cmp3 = icmp eq i64 %contents.1, 16
  %and = and i1 %cmp2, %cmp3
  br i1 %and, label %if2, label %exit

if2:
  ret i32 1

exit:
  ret i32 0
}

define i32 @tgt(ptr %contents.0, i64 %contents.1) {
start:
  %cmp1 = icmp eq i64 %contents.1, 16
  br i1 %cmp1, label %if, label %exit

if:
  %load = load i64, ptr %contents.0
  %cmp2 = icmp eq i64 %load, 123
  %cmp3 = icmp eq i64 %contents.1, 16
  %and = and i1 %cmp2, true
  br i1 %and, label %if2, label %exit

if2:
  ret i32 1

exit:
  ret i32 0
}

In this example, %if2 is taken if %cmp1, %cmp2 and %cmp3 are all true, otherwise %exit is taken. However, %cmp3 implies %cmp1. So we can check %cmp3 first. This means that the %if block is not executed anymore in more cases, so it's only possible if it is side-effect free.

[VedantParanjape]

I want to work on this.

[VedantParanjape]

A rough algorithm for this might be:

1. Check if icmp result is used in a branch
2. Check both branches for icmps that compute on the same variable as used in the parent branch.
3. Check if the child icmp's imply the parent icmp.

But how do I figure out if the "if" branch is side effect free, is there some utility pass that checks that?

likely, I need to implement a version of isImpliedByDomCondition for post dominator implied conditions.