define void @hoge() {
bb:
  br label %bb1

bb1:                                              ; preds = %bb12, %bb
  %tmp = phi i32 [ 0, %bb ], [ 1, %bb12 ]
  br label %bb3


bb3:                                              ; preds = %bb8, %bb2
  %tmp4 = phi i32 [ %tmp, %bb1 ], [ %tmp9, %bb8 ]
  br i1 undef, label %bb12, label %bb5

bb5:                                              ; preds = %bb10, %bb3
  %tmp6 = phi i32 [ %tmp11, %bb10 ], [ %tmp4, %bb3 ]
  br label %bb7

bb7:                                              ; preds = %bb5
  br i1 undef, label %bb10, label %bb8

bb8:                                              ; preds = %bb7
  %tmp9 = phi i32 [ %tmp6, %bb7 ]
  br label %bb3

bb10:                                             ; preds = %bb7
  %tmp11 = phi i32 [ %tmp6, %bb7 ]
  br label %bb5

bb12:                                             ; preds = %bb3
  br label %bb1
}


RPO order is as display.
RPO VN algorithm applied without unreachable edge elimination

VN(tmp) = meet(0, 1) = tmp
VN(tmp4) = meet(VN(tmp), VN(tmp9)) = meet(tmp, TOP) = tmp
VN(tmp6) = meet(VN(tmp11), VN(tmp4)) = meet(TOP, tmp) = tmp
VN(tmp9) = meet(VN(tmp6)) = meet(tmp) = tmp
VN(tmp11) = meet(VN(tmp6)) = meet(tmp) = tmp

End state at iteration 1:
VN(tmp) = tmp
VN(tmp4) = tmp
VN(tmp6) = tmp
VN(tmp9) = tmp
VN(tmp11) = tmp

Iteration 2:

VN(tmp) = meet(0, 1) = tmp
VN(tmp4) = meet(VN(tmp), VN(tmp9)) = meet(tmp, tmp) = tmp
VN(tmp6) = meet(VN(tmp11), VN(tmp4)) = meet(tmp, tmp) = tmp
VN(tmp9) = meet(VN(tmp6)) = meet(tmp) = tmp
VN(tmp11) = meet(VN(tmp6)) = meet(tmp) = tmp

End state at iteration 2:
VN(tmp) = tmp
VN(tmp4) = tmp
VN(tmp6) = tmp
VN(tmp9) = tmp
VN(tmp11) = tmp

we are done.


Same algorithm, initially ignoring unreachable edges.
In this case, that's bb12->bb1 to start

VN(tmp) = meet(0, unreachable) = 0
VN(tmp4) = meet(VN(tmp), VN(tmp9)) = meet(0, TOP) = 0
VN(tmp6) = meet(VN(tmp11), VN(tmp4)) = meet(TOP, 0) = 0
VN(tmp9) = meet(VN(tmp6)) = meet(tmp) = 0
VN(tmp11) = meet(VN(tmp6)) = meet(tmp) = 0
bb12->bb1 is marked reachable

End state at iteration 1:
VN(tmp) = 0
VN(tmp4) = 0
VN(tmp6) = 0
VN(tmp9) = 0
VN(tmp11) = 0

Iteration 2:

VN(tmp) = meet(0, 1) = tmp
VN(tmp4) = meet(VN(tmp), VN(tmp9)) = meet(tmp, 0) = tmp4
VN(tmp6) = meet(VN(tmp11), VN(tmp4)) = meet(0, tmp4) = tmp6
VN(tmp9) = meet(VN(tmp6)) = meet(tmp6) = tmp6
VN(tmp11) = meet(VN(tmp6)) = meet(tmp6) = tmp6

End state at iteration 2:
VN(tmp) = tmp
VN(tmp4) = tmp4
VN(tmp6) = tmp6
VN(tmp9) = tmp6
VN(tmp11) = tmp6

Iteration 3:

VN(tmp) = meet(0, 1) = tmp
VN(tmp4) = meet(VN(tmp), VN(tmp9)) = meet(tmp, tmp6) = tmp4
VN(tmp6) = meet(VN(tmp11), VN(tmp4)) = meet(tmp6, tmp4) = tmp6
VN(tmp9) = meet(VN(tmp6)) = meet(tmp6) = tmp6
VN(tmp11) = meet(VN(tmp6)) = meet(tmp6) = tmp6

End state at iteration 3:
VN(tmp) = tmp
VN(tmp4) = tmp4
VN(tmp6) = tmp6
VN(tmp9) = tmp6
VN(tmp11) = tmp6

we are done.