[StructurizeCFG] Fix boolean not bug

[foad]

Summary

D118623 added code to fold not-of-compare into a compare
with the inverted predicate, if the compare had no other
uses. This relies on accurate use lists in the IR but it
was run before setPhiValues, when some phi inputs are still
stored in a data structure on the side, instead of being
real uses in the IR. The effect was that a phi that should
be using the original compare result would now get an
inverted result instead.

Fix this by moving simplifyConditions after setPhiValues.

[mareko]

@arsenm @foad Can we backport it to LLVM 14? LLVM 14 is unusable because of this bug.

[arsenm]

In D120312#3707620, @mareko wrote:

@arsenm @foad Can we backport it to LLVM 14? LLVM 14 is unusable because of this bug.

I'm not sure if any more llvm 14 stable releases are planned but I opened https://github.com/llvm/llvm-project/issues/57012

llvm/lib/Transforms/Scalar/StructurizeCFG.cpp

bool StructurizeCFG::run(Region *R, DominatorTree *DT) {
   Func = R->getEntry()->getParent();
   ParentRegion = R;
 
   orderNodes();
   collectInfos();
   createFlow();
   insertConditions(false);
   insertConditions(true);
-  simplifyConditions();
   setPhiValues();
+  simplifyConditions();
   simplifyAffectedPhis();
   rebuildSSA();
 
   // Cleanup
   Order.clear();
   Visited.clear();
   DeletedPhis.clear();
   AddedPhis.clear();

llvm/test/Transforms/StructurizeCFG/invert-condition.ll

bb2:                                              ; preds = %bb2, %bb
   %tmp3 = fcmp oge float %tmp, %tmp1
   %tmp4 = xor i1 %arg, %tmp3
   br i1 %tmp4, label %bb2, label %bb5
 
 bb5:                                              ; preds = %bb2
   ret void
 }
 
-; FIXME: StructurizeCFG modifies I5 in-place without updating the use of I5 in
-; the phi instruction.
 define void @invert_condition_phi(i32 %arg) {
 ; CHECK-LABEL: @invert_condition_phi(
 ; CHECK-NEXT:  main_body:
-; CHECK-NEXT:    [[I5:%.*]] = icmp ne i32 [[ARG:%.*]], 0
-; CHECK-NEXT:    br i1 [[I5]], label [[IF1:%.*]], label [[ENDIF1:%.*]]
+; CHECK-NEXT:    [[I5:%.*]] = icmp eq i32 [[ARG:%.*]], 0
+; CHECK-NEXT:    [[I5_INV:%.*]] = xor i1 [[I5]], true
+; CHECK-NEXT:    br i1 [[I5_INV]], label [[IF1:%.*]], label [[ENDIF1:%.*]]
 ; CHECK:       if1:
 ; CHECK-NEXT:    br label [[ENDIF1]]
 ; CHECK:       endif1:
 ; CHECK-NEXT:    [[I7:%.*]] = phi i1 [ [[I5]], [[MAIN_BODY:%.*]] ], [ false, [[IF1]] ]
 ; CHECK-NEXT:    [[I7_INV:%.*]] = xor i1 [[I7]], true
 ; CHECK-NEXT:    br i1 [[I7_INV]], label [[IF4:%.*]], label [[ENDIF4:%.*]]
 ; CHECK:       if4:
 ; CHECK-NEXT:    br label [[ENDIF4]]