[SimplifyCFG] Fix SimplifyBranchOnICmpChain to be undef/poison safe.

[hyeongyukim]

Summary

This patch fixes the problem of SimplifyBranchOnICmpChain that occurs
when extra values are Undef or poison.

Suppose the %mode is 51 and the %Cond is poison, and let's look at the
case below.

	%A = icmp ne i32 %mode, 0
	%B = icmp ne i32 %mode, 51
	%C = select i1 %A, i1 %B, i1 false
	%D = select i1 %C, i1 %Cond, i1 false
	br i1 %D, label %T, label %F
=>
	br i1 %Cond, label %switch.early.test, label %F
switch.early.test:
	switch i32 %mode, label %T [
		i32 51, label %F
		i32 0, label %F
	]

incorrectness: https://alive2.llvm.org/ce/z/BWScX

Code before transformation will not raise UB because %C and %D is false,
and it will not use %Cond. But after transformation, %Cond is being used
immediately, and it will raise UB.

This problem can be solved by adding freeze instruction.

correctness: https://alive2.llvm.org/ce/z/x9x4oY

[aqjune]

In favor of this patch, I'll abandon mine; I'm occupied with something else ATM :/
@hyeongyukim Do you want to see how many assembly files from llvm testsuite are affected by this patch? If there is a significant assembly change, you'd like to see which pass is blocked by this.

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

4266

Is it possible to pass a dominator tree to this function?

[nikic]

I have a general policy question here: Do we care about miscompiles that are caused by undef, but not poison? This makes a difference for transforms like these, e.g. no freeze is required if the condition is first in a logical or (or at any position in bitwise or) if we only care about poison.

As we are moving from undef to poison across the board, I'm not sure we should introduce mitigations that would become irrelevant once undef no longer exists. My view here is that miscompiles involving undef are mostly nominal, in that the undef value really should be a poison value and we just haven't switched it one yet.

[aqjune]

In D104569#2828921, @nikic wrote:

I have a general policy question here: Do we care about miscompiles that are caused by undef, but not poison? This makes a difference for transforms like these, e.g. no freeze is required if the condition is first in a logical or (or at any position in bitwise or) if we only care about poison.

As we are moving from undef to poison across the board, I'm not sure we should introduce mitigations that would become irrelevant once undef no longer exists. My view here is that miscompiles involving undef are mostly nominal, in that the undef value really should be a poison value and we just haven't switched it one yet.

+1 for caring about poison only.

It allows using isGuaranteedNotToBePoison (not isGuaranteedNotToBeUndefOrPoison) for this patch, which is a better analysis.

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

4243–4244

If it is settled to ignore the undef case, can we leave a comment here saying that TODO: Once undef value is removed, this check isn't necessary?

[nlopes]

In D104569#2828921, @nikic wrote:

I have a general policy question here: Do we care about miscompiles that are caused by undef, but not poison? This makes a difference for transforms like these, e.g. no freeze is required if the condition is first in a logical or (or at any position in bitwise or) if we only care about poison.

As we are moving from undef to poison across the board, I'm not sure we should introduce mitigations that would become irrelevant once undef no longer exists. My view here is that miscompiles involving undef are mostly nominal, in that the undef value really should be a poison value and we just haven't switched it one yet.

I agree we shouldn't waste time with miscompilations of undef only, unless they show up in real life. That's why in the Alive2 dashboard I've separated the issues that are correct if undef didn't exist.
This particular patch fixes issues with poison as well (see @test10_select), so I think we should fix it. Plus, as the MSAN hack shows, even the undef bit was causing headaches. So maybe this time it's useful to fix both poison & undef.

That said, some of the tests clearly don't need freeze. This patch is introducing freeze on an existing branch (e.g., @test9). For some reason isGuaranteedNotToBeUndefOrPoison is not working here.

[hyeongyukim]

I modified my code to add the freeze instruction only if extra values are poison.
And I also pass dominator tree to isGuaranteedNotToBePosion, but unnecessary freeze instruction is still being added.

[hyeongyukim]

entry:
  %cmp = icmp ult i8 %c, 33                           ; ExtraCase
  %cmp4 = icmp eq i8 %c, 46
  %or.cond = or i1 %cmp, %cmp4
  %cmp9 = icmp eq i8 %c, 44
  %or.cond1 = or i1 %or.cond, %cmp9
  %cmp14 = icmp eq i8 %c, 58
  %or.cond2 = or i1 %or.cond1, %cmp14
  %cmp19 = icmp eq i8 %c, 59
  %or.cond3 = or i1 %or.cond2, %cmp19
  %cmp24 = icmp eq i8 %c, 60
  %or.cond4 = or i1 %or.cond3, %cmp24
  %cmp29 = icmp eq i8 %c, 62
  %or.cond5 = or i1 %or.cond4, %cmp29
  %cmp34 = icmp eq i8 %c, 34
  %or.cond6 = or i1 %or.cond5, %cmp34
  %cmp39 = icmp eq i8 %c, 92
  %or.cond7 = or i1 %or.cond6, %cmp39
  br i1 %or.cond7, label %lor.end, label %lor.rhs    ; BI
====
    // Currently isGuaranteedNotToBePoison returns false.
    if (!isGuaranteedNotToBePoison(ExtraCase, AC, BI, DT))
      ExtraCase = Builder.CreateFreeze(ExtraCase);

%or.cond7 cannot be poison because %or.cond7 is a branching condition.
Also, %cmp cannot be poison because %or.cond7 is not poison.
But isGuaranteedNotToBePosion is returning false, and an unnecessary freeze is generated.

I think this situation does not appear to be considered in the current implementation of isGuaranteedNotToBePosion.
Therefore, it seems that isGuaranteedNotToBePosion should be modified so that this case can be dealt with. (I would like to add a code that handles the case when 'CtxI' is a branching instruction.)

Of course, I may have misused isGuaranteedNotToBePosition, and if there is anything wrong with me, please let me know.

[aqjune]

IIUC, the result of isGuaranteedNotToBePoison is suboptimal because mustTriggerUB does not consider br poison as UB.

Could you try D92739 and see whether the unnecessary freeze instructions disappear?

BTW, it is possible that the redundant freeze instructions actually don't matter; compiling benchmarks and seeing assembly diffs will be helpful for determining this.

[hyeongyukim]

In D104569#2831268, @aqjune wrote:

IIUC, the result of isGuaranteedNotToBePoison is suboptimal because mustTriggerUB does not consider br poison as UB.

Could you try D92739 and see whether the unnecessary freeze instructions disappear?

BTW, it is possible that the redundant freeze instructions actually don't matter; compiling benchmarks and seeing assembly diffs will be helpful for determining this.

When I applied D92739, redundant freeze instructions was removed.
Also, a small difference was found when comparing assembly diffs of llvm testsuite.
Of the 5,200 examples, 121 changes were observed.

diff_list.txt513 KBDownload

Example of assembly diff is below.

diff_example.txt56 KBDownload

Although it is a small difference, I think the difference that D92739 makes is meaningful.
It seems better to solve D92739 first and then solve this issue again. Is it okay to solve D92739 first?

[hyeongyukim]

I've changed isGuaranteedNotToBeUndefOrPoison to isGuaranteedNotToBePoison before, but these two are actually the same function. And I want to enable SimplifyCFG when MSAN is on, so I reverted my code to isGuaranteedNotToBeUndefOrPoison.

As I mentioned earlier, an unnecessary freeze is being added.
However, I think it is better to solve the only miscompilation problem in this PR and deal with an unnecessary freeze in a separate PR.
When I check the compiled assembly of LLVM testsuite, I think that the performance degradation caused by this patch is slight. I have attached the diff files, so please check them.

I'm done writing the code, so I'd appreciate it if you could review it.

diff_files.tar.gz20 KBDownload

[nikic]

It looks like you only uploaded your last change, not the whole patch.

[hyeongyukim]

Rebase and uploaded the entire patch.

[nikic]

I'm willing to accept the simple patch and see if any regressions are reported. If they are, we can switch to a more sophisticated poison-only approach.

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

4269

SimplifyCFG only preserves DT, it should not use it during transforms. You should pass nullptr instead.

[aqjune]

To address possible performance issues, do you want to take https://reviews.llvm.org/D82317 ? The validity of noundef flag is already checked by reviewers, the only necessary thing is to turn the flag on.

llvm/test/Transforms/SimplifyCFG/switch_msan.ll

81

This is an improvement, which is nice.

[hyeongyukim]

In D104569#2845996, @aqjune wrote:

To address possible performance issues, do you want to take https://reviews.llvm.org/D82317 ? The validity of noundef flag is already checked by reviewers, the only necessary thing is to turn the flag on.

Sounds good, I'll take that.

[hyeongyukim]

Modify to disable DT on Transform.

[hyeongyukim]

I was curious about the impact of this patch, so I ran llvm-test-suite (benchmarks only) and found that only assembly files were different among 1977.
Three of them are just syntactic differences (@aqjune made a patch for this), but two of them had meaningful differences. The reason was as follows.

v = load ptr
cond = freeze(icmp (and v, const), const')
br cond, ...

Since cond was frozen, value analysis didn't work well.
I think adding this optimization to InstCombine can be helpful:

v = load ptr
freeze(icmp (and v, const), const')
=>
v = load ptr
v' = freeze v
icmp (and v', const), const'

What do you think?

[nikic]

@hyeongyukim Yes, that's definitely a good idea. Generally, we should try to push freeze through instructions that propagate but don't produce poison as far as possible.

[hyeongyukim]

Add optimization for freeze to InstCombine.

[hyeongyukim]

I added new optimization to InstCombine, but I didn't write a new test yet.
Would it be better to add a test?

[hyeongyukim]

Delete the added InstCombine.
It will be handled at another patch.

[hyeongyukim]

After D105392 was applied, there is little change in the Assembly.
There are five changes of the 1977 files included in LLVM testsuite, but they are all synthetic changes.
You can check the difference in the attached file.

diff_files.tar.gz5 KBDownload

This patch fixes miscompilation and does not add assembly, so I think it's the right time to review.

[nikic]

LGTM. Looks like most of the remaining diffs are covered by D105344. The one in libclamav_regex_regcomp.c was a bit too large to understand at a glance, but it mostly looks like code movement.

[hyeongyukim]

In D104569#2871466, @nikic wrote:

LGTM. Looks like most of the remaining diffs are covered by D105344. The one in libclamav_regex_regcomp.c was a bit too large to understand at a glance, but it mostly looks like code movement.

I forgot to mention that D105344 changed the patch's assembly.
I should have added more details, and thank you for writing it down for me.
Next time, I'll write it down in more detail so it's easier to review.

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

bool SimplifyCFGOpt::SimplifyBranchOnICmpChain(BranchInst *BI,
 
   // Figure out which block is which destination.
   BasicBlock *DefaultBB = BI->getSuccessor(1);
   BasicBlock *EdgeBB = BI->getSuccessor(0);
   if (!TrueWhenEqual)
     std::swap(DefaultBB, EdgeBB);
 
   BasicBlock *BB = BI->getParent();
 
-  // MSAN does not like undefs as branch condition which can be introduced
-  // with "explicit branch".
-  if (ExtraCase && BB->getParent()->hasFnAttribute(Attribute::SanitizeMemory))
-    return false;
-
   LLVM_DEBUG(dbgs() << "Converting 'icmp' chain with " << Values.size()
                     << " cases into SWITCH.  BB is:\n"
                     << *BB);
 
   SmallVector<DominatorTree::UpdateType, 2> Updates;
 
   // If there are any extra values that couldn't be folded into the switch
   // then we evaluate them with an explicit branch first. Split the block
   // right before the condbr to handle it.
   if (ExtraCase) {
     BasicBlock *NewBB = SplitBlock(BB, BI, DTU, /*LI=*/nullptr,
                                    /*MSSAU=*/nullptr, "switch.early.test");
 
     // Remove the uncond branch added to the old block.
     Instruction *OldTI = BB->getTerminator();
     Builder.SetInsertPoint(OldTI);
 
+    // There can be an unintended UB if extra values are Poison. Before the
+    // transformation, extra values may not be evaluated according to the
+    // condition, and it will not raise UB. But after transformation, we are
+    // evaluating extra values before checking the condition, and it will raise
+    // UB. It can be solved by adding freeze instruction to extra values.
+    AssumptionCache *AC = Options.AC;
+
+    if (!isGuaranteedNotToBeUndefOrPoison(ExtraCase, AC, BI, nullptr))
+      ExtraCase = Builder.CreateFreeze(ExtraCase);
+
     if (TrueWhenEqual)
       Builder.CreateCondBr(ExtraCase, EdgeBB, NewBB);
     else
       Builder.CreateCondBr(ExtraCase, NewBB, EdgeBB);
 
     OldTI->eraseFromParent();
 
     if (DTU)

llvm/test/Transforms/SimplifyCFG/switch_create-custom-dl.ll

UnifiedReturnBlock:             ; preds = %shortcirc_done.4, %shortcirc_next.4
   ret i1 %UnifiedRetVal
 
 }
 
 define void @test7(i8 zeroext %c, i32 %x) nounwind ssp noredzone {
 ; CHECK-LABEL: @test7(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ult i32 [[X:%.*]], 32
-; CHECK-NEXT:    br i1 [[CMP]], label [[IF_THEN:%.*]], label [[SWITCH_EARLY_TEST:%.*]]
+; CHECK-NEXT:    [[TMP0:%.*]] = freeze i1 [[CMP]]
+; CHECK-NEXT:    br i1 [[TMP0]], label [[IF_THEN:%.*]], label [[SWITCH_EARLY_TEST:%.*]]
 ; CHECK:       switch.early.test:
 ; CHECK-NEXT:    switch i8 [[C:%.*]], label [[COMMON_RET:%.*]] [
 ; CHECK-NEXT:    i8 99, label [[IF_THEN]]
 ; CHECK-NEXT:    i8 97, label [[IF_THEN]]
 ; CHECK-NEXT:    ]
 ; CHECK:       common.ret:
 ; CHECK-NEXT:    ret void
 ; CHECK:       if.then:

 }
 
 define i32 @test8(i8 zeroext %c, i32 %x, i1 %C) nounwind ssp noredzone {
 ; CHECK-LABEL: @test8(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br i1 [[C:%.*]], label [[N:%.*]], label [[IF_THEN:%.*]]
 ; CHECK:       N:
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ult i32 [[X:%.*]], 32
-; CHECK-NEXT:    br i1 [[CMP]], label [[IF_THEN]], label [[SWITCH_EARLY_TEST:%.*]]
+; CHECK-NEXT:    [[TMP0:%.*]] = freeze i1 [[CMP]]
+; CHECK-NEXT:    br i1 [[TMP0]], label [[IF_THEN]], label [[SWITCH_EARLY_TEST:%.*]]
 ; CHECK:       switch.early.test:
 ; CHECK-NEXT:    switch i8 [[C:%.*]], label [[COMMON_RET:%.*]] [
 ; CHECK-NEXT:    i8 99, label [[IF_THEN]]
 ; CHECK-NEXT:    i8 97, label [[IF_THEN]]
 ; CHECK-NEXT:    ]
 ; CHECK:       common.ret:
 ; CHECK-NEXT:    [[COMMON_RET_OP:%.*]] = phi i32 [ [[A:%.*]], [[IF_THEN]] ], [ 0, [[SWITCH_EARLY_TEST]] ]
 ; CHECK-NEXT:    ret i32 [[COMMON_RET_OP]]

 
 }
 
 ;; This is "Example 7" from http://blog.regehr.org/archives/320
 define i32 @test9(i8 zeroext %c) nounwind ssp noredzone {
 ; CHECK-LABEL: @test9(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ult i8 [[C:%.*]], 33
-; CHECK-NEXT:    br i1 [[CMP]], label [[LOR_END:%.*]], label [[SWITCH_EARLY_TEST:%.*]]
+; CHECK-NEXT:    [[TMP0:%.*]] = freeze i1 [[CMP]]
+; CHECK-NEXT:    br i1 [[TMP0]], label [[LOR_END:%.*]], label [[SWITCH_EARLY_TEST:%.*]]
 ; CHECK:       switch.early.test:
 ; CHECK-NEXT:    switch i8 [[C]], label [[LOR_RHS:%.*]] [
 ; CHECK-NEXT:    i8 92, label [[LOR_END]]
 ; CHECK-NEXT:    i8 62, label [[LOR_END]]
 ; CHECK-NEXT:    i8 60, label [[LOR_END]]
 ; CHECK-NEXT:    i8 59, label [[LOR_END]]
 ; CHECK-NEXT:    i8 58, label [[LOR_END]]
 ; CHECK-NEXT:    i8 46, label [[LOR_END]]
 ; CHECK-NEXT:    i8 44, label [[LOR_END]]
 ; CHECK-NEXT:    i8 34, label [[LOR_END]]
 ; CHECK-NEXT:    i8 39, label [[LOR_END]]
 ; CHECK-NEXT:    ]
 ; CHECK:       lor.rhs:
 ; CHECK-NEXT:    br label [[LOR_END]]
 ; CHECK:       lor.end:
-; CHECK-NEXT:    [[TMP0:%.*]] = phi i1 [ true, [[SWITCH_EARLY_TEST]] ], [ false, [[LOR_RHS]] ], [ true, [[ENTRY:%.*]] ], [ true, [[SWITCH_EARLY_TEST]] ], [ true, [[SWITCH_EARLY_TEST]] ], [ true, [[SWITCH_EARLY_TEST]] ], [ true, [[SWITCH_EARLY_TEST]] ], [ true, [[SWITCH_EARLY_TEST]] ], [ true, [[SWITCH_EARLY_TEST]] ], [ true, [[SWITCH_EARLY_TEST]] ], [ true, [[SWITCH_EARLY_TEST]] ]
-; CHECK-NEXT:    [[CONV46:%.*]] = zext i1 [[TMP0]] to i32
+; CHECK-NEXT:    [[TMP1:%.*]] = phi i1 [ true, [[SWITCH_EARLY_TEST]] ], [ false, [[LOR_RHS]] ], [ true, [[ENTRY:%.*]] ], [ true, [[SWITCH_EARLY_TEST]] ], [ true, [[SWITCH_EARLY_TEST]] ], [ true, [[SWITCH_EARLY_TEST]] ], [ true, [[SWITCH_EARLY_TEST]] ], [ true, [[SWITCH_EARLY_TEST]] ], [ true, [[SWITCH_EARLY_TEST]] ], [ true, [[SWITCH_EARLY_TEST]] ], [ true, [[SWITCH_EARLY_TEST]] ]
+; CHECK-NEXT:    [[CONV46:%.*]] = zext i1 [[TMP1]] to i32
 ; CHECK-NEXT:    ret i32 [[CONV46]]
 ;
 entry:
   %cmp = icmp ult i8 %c, 33
   br i1 %cmp, label %lor.end, label %lor.lhs.false
 
 lor.lhs.false:                                    ; preds = %entry
   %cmp4 = icmp eq i8 %c, 46
lor.end:                                          ; preds = %lor.rhs, %lor.lhs.false36, %lor.lhs.false31, %lor.lhs.false26, %lor.lhs.false21, %lor.lhs.false16, %lor.lhs.false11, %lor.lhs.false6, %lor.lhs.false, %entry
   %conv46 = zext i1 %0 to i32
   ret i32 %conv46
 
 
 }
 
 define i32 @test10(i32 %mode, i1 %Cond) {
 ; CHECK-LABEL: @test10(
-; CHECK-NEXT:    br i1 [[COND:%.*]], label [[SWITCH_EARLY_TEST:%.*]], label [[F:%.*]]
+; CHECK-NEXT:    [[TMP1:%.*]] = freeze i1 [[COND:%.*]]
+; CHECK-NEXT:    br i1 [[TMP1]], label [[SWITCH_EARLY_TEST:%.*]], label [[F:%.*]]
 ; CHECK:       switch.early.test:
 ; CHECK-NEXT:    switch i32 [[MODE:%.*]], label [[T:%.*]] [
 ; CHECK-NEXT:    i32 51, label [[F]]
 ; CHECK-NEXT:    i32 0, label [[F]]
 ; CHECK-NEXT:    ]
 ; CHECK:       common.ret:
 ; CHECK-NEXT:    [[COMMON_RET_OP:%.*]] = phi i32 [ 123, [[T]] ], [ 324, [[F]] ]
 ; CHECK-NEXT:    ret i32 [[COMMON_RET_OP]]

llvm/test/Transforms/SimplifyCFG/switch_create.ll

UnifiedReturnBlock:             ; preds = %shortcirc_done.4, %shortcirc_next.4
   ret i1 %UnifiedRetVal
 
 }
 
 define void @test7(i8 zeroext %c, i32 %x) nounwind ssp noredzone {
 ; CHECK-LABEL: @test7(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ult i32 [[X:%.*]], 32
-; CHECK-NEXT:    br i1 [[CMP]], label [[IF_THEN:%.*]], label [[SWITCH_EARLY_TEST:%.*]]
+; CHECK-NEXT:    [[TMP0:%.*]] = freeze i1 [[CMP]]
+; CHECK-NEXT:    br i1 [[TMP0]], label [[IF_THEN:%.*]], label [[SWITCH_EARLY_TEST:%.*]]
 ; CHECK:       switch.early.test:
 ; CHECK-NEXT:    switch i8 [[C:%.*]], label [[COMMON_RET:%.*]] [
 ; CHECK-NEXT:    i8 99, label [[IF_THEN]]
 ; CHECK-NEXT:    i8 97, label [[IF_THEN]]
 ; CHECK-NEXT:    ]
 ; CHECK:       common.ret:
 ; CHECK-NEXT:    ret void
 ; CHECK:       if.then:

 }
 
 define i32 @test8(i8 zeroext %c, i32 %x, i1 %C) nounwind ssp noredzone {
 ; CHECK-LABEL: @test8(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br i1 [[C:%.*]], label [[N:%.*]], label [[IF_THEN:%.*]]
 ; CHECK:       N:
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ult i32 [[X:%.*]], 32
-; CHECK-NEXT:    br i1 [[CMP]], label [[IF_THEN]], label [[SWITCH_EARLY_TEST:%.*]]
+; CHECK-NEXT:    [[TMP0:%.*]] = freeze i1 [[CMP]]
+; CHECK-NEXT:    br i1 [[TMP0]], label [[IF_THEN]], label [[SWITCH_EARLY_TEST:%.*]]
 ; CHECK:       switch.early.test:
 ; CHECK-NEXT:    switch i8 [[C:%.*]], label [[COMMON_RET:%.*]] [
 ; CHECK-NEXT:    i8 99, label [[IF_THEN]]
 ; CHECK-NEXT:    i8 97, label [[IF_THEN]]
 ; CHECK-NEXT:    ]
 ; CHECK:       common.ret:
 ; CHECK-NEXT:    [[COMMON_RET_OP:%.*]] = phi i32 [ [[A:%.*]], [[IF_THEN]] ], [ 0, [[SWITCH_EARLY_TEST]] ]
 ; CHECK-NEXT:    ret i32 [[COMMON_RET_OP]]

 
 }
 
 ;; This is "Example 7" from http://blog.regehr.org/archives/320
 define i32 @test9(i8 zeroext %c) nounwind ssp noredzone {
 ; CHECK-LABEL: @test9(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ult i8 [[C:%.*]], 33
-; CHECK-NEXT:    br i1 [[CMP]], label [[LOR_END:%.*]], label [[SWITCH_EARLY_TEST:%.*]]
+; CHECK-NEXT:    [[TMP0:%.*]] = freeze i1 [[CMP]]
+; CHECK-NEXT:    br i1 [[TMP0]], label [[LOR_END:%.*]], label [[SWITCH_EARLY_TEST:%.*]]
 ; CHECK:       switch.early.test:
 ; CHECK-NEXT:    switch i8 [[C]], label [[LOR_RHS:%.*]] [
 ; CHECK-NEXT:    i8 92, label [[LOR_END]]
 ; CHECK-NEXT:    i8 62, label [[LOR_END]]
 ; CHECK-NEXT:    i8 60, label [[LOR_END]]
 ; CHECK-NEXT:    i8 59, label [[LOR_END]]
 ; CHECK-NEXT:    i8 58, label [[LOR_END]]
 ; CHECK-NEXT:    i8 46, label [[LOR_END]]
 ; CHECK-NEXT:    i8 44, label [[LOR_END]]
 ; CHECK-NEXT:    i8 34, label [[LOR_END]]
 ; CHECK-NEXT:    i8 39, label [[LOR_END]]
 ; CHECK-NEXT:    ]
 ; CHECK:       lor.rhs:
 ; CHECK-NEXT:    br label [[LOR_END]]
 ; CHECK:       lor.end:
-; CHECK-NEXT:    [[TMP0:%.*]] = phi i1 [ true, [[SWITCH_EARLY_TEST]] ], [ false, [[LOR_RHS]] ], [ true, [[ENTRY:%.*]] ], [ true, [[SWITCH_EARLY_TEST]] ], [ true, [[SWITCH_EARLY_TEST]] ], [ true, [[SWITCH_EARLY_TEST]] ], [ true, [[SWITCH_EARLY_TEST]] ], [ true, [[SWITCH_EARLY_TEST]] ], [ true, [[SWITCH_EARLY_TEST]] ], [ true, [[SWITCH_EARLY_TEST]] ], [ true, [[SWITCH_EARLY_TEST]] ]
-; CHECK-NEXT:    [[CONV46:%.*]] = zext i1 [[TMP0]] to i32
+; CHECK-NEXT:    [[TMP1:%.*]] = phi i1 [ true, [[SWITCH_EARLY_TEST]] ], [ false, [[LOR_RHS]] ], [ true, [[ENTRY:%.*]] ], [ true, [[SWITCH_EARLY_TEST]] ], [ true, [[SWITCH_EARLY_TEST]] ], [ true, [[SWITCH_EARLY_TEST]] ], [ true, [[SWITCH_EARLY_TEST]] ], [ true, [[SWITCH_EARLY_TEST]] ], [ true, [[SWITCH_EARLY_TEST]] ], [ true, [[SWITCH_EARLY_TEST]] ], [ true, [[SWITCH_EARLY_TEST]] ]
+; CHECK-NEXT:    [[CONV46:%.*]] = zext i1 [[TMP1]] to i32
 ; CHECK-NEXT:    ret i32 [[CONV46]]
 ;
 entry:
   %cmp = icmp ult i8 %c, 33
   br i1 %cmp, label %lor.end, label %lor.lhs.false
 
 lor.lhs.false:                                    ; preds = %entry
   %cmp4 = icmp eq i8 %c, 46
lor.end:                                          ; preds = %lor.rhs, %lor.lhs.false36, %lor.lhs.false31, %lor.lhs.false26, %lor.lhs.false21, %lor.lhs.false16, %lor.lhs.false11, %lor.lhs.false6, %lor.lhs.false, %entry
   %conv46 = zext i1 %0 to i32
   ret i32 %conv46
 
 
 }
 
 define i32 @test10(i32 %mode, i1 %Cond) {
 ; CHECK-LABEL: @test10(
-; CHECK-NEXT:    br i1 [[COND:%.*]], label [[SWITCH_EARLY_TEST:%.*]], label [[F:%.*]]
+; CHECK-NEXT:    [[TMP1:%.*]] = freeze i1 [[COND:%.*]]
+; CHECK-NEXT:    br i1 [[TMP1]], label [[SWITCH_EARLY_TEST:%.*]], label [[F:%.*]]
 ; CHECK:       switch.early.test:
 ; CHECK-NEXT:    switch i32 [[MODE:%.*]], label [[T:%.*]] [
 ; CHECK-NEXT:    i32 51, label [[F]]
 ; CHECK-NEXT:    i32 0, label [[F]]
 ; CHECK-NEXT:    ]
 ; CHECK:       common.ret:
 ; CHECK-NEXT:    [[COMMON_RET_OP:%.*]] = phi i32 [ 123, [[T]] ], [ 324, [[F]] ]
 ; CHECK-NEXT:    ret i32 [[COMMON_RET_OP]]

 F:
   call void @foo2()
   ret i32 324
 
 }
 
 define i32 @test10_select(i32 %mode, i1 %Cond) {
 ; CHECK-LABEL: @test10_select(
-; CHECK-NEXT:    br i1 [[COND:%.*]], label [[SWITCH_EARLY_TEST:%.*]], label [[F:%.*]]
+; CHECK-NEXT:    [[TMP1:%.*]] = freeze i1 [[COND:%.*]]
+; CHECK-NEXT:    br i1 [[TMP1]], label [[SWITCH_EARLY_TEST:%.*]], label [[F:%.*]]
 ; CHECK:       switch.early.test:
 ; CHECK-NEXT:    switch i32 [[MODE:%.*]], label [[T:%.*]] [
 ; CHECK-NEXT:    i32 51, label [[F]]
 ; CHECK-NEXT:    i32 0, label [[F]]
 ; CHECK-NEXT:    ]
 ; CHECK:       common.ret:
 ; CHECK-NEXT:    [[COMMON_RET_OP:%.*]] = phi i32 [ 123, [[T]] ], [ 324, [[F]] ]
 ; CHECK-NEXT:    ret i32 [[COMMON_RET_OP]]
F:
   call void @foo2()
   ret i32 324
 
 }
 
 ; TODO: %Cond doesn't need freeze
 define i32 @test10_select_and(i32 %mode, i1 %Cond) {
 ; CHECK-LABEL: @test10_select_and(
-; CHECK-NEXT:    br i1 [[COND:%.*]], label [[SWITCH_EARLY_TEST:%.*]], label [[F:%.*]]
+; CHECK-NEXT:    [[TMP1:%.*]] = freeze i1 [[COND:%.*]]
+; CHECK-NEXT:    br i1 [[TMP1]], label [[SWITCH_EARLY_TEST:%.*]], label [[F:%.*]]
 ; CHECK:       switch.early.test:
 ; CHECK-NEXT:    switch i32 [[MODE:%.*]], label [[T:%.*]] [
 ; CHECK-NEXT:    i32 51, label [[F]]
 ; CHECK-NEXT:    i32 0, label [[F]]
 ; CHECK-NEXT:    ]
 ; CHECK:       common.ret:
 ; CHECK-NEXT:    [[COMMON_RET_OP:%.*]] = phi i32 [ 123, [[T]] ], [ 324, [[F]] ]
 ; CHECK-NEXT:    ret i32 [[COMMON_RET_OP]]

llvm/test/Transforms/SimplifyCFG/switch_msan.ll

 ; CHECK-NEXT:    [[C:%.*]] = call fastcc signext i8 @next_char()
 ; CHECK-NEXT:    [[C_10:%.*]] = icmp eq i8 [[C]], 10
 ; CHECK-NEXT:    [[C_13:%.*]] = icmp eq i8 [[C]], 13
 ; CHECK-NEXT:    [[C_10_OR_13:%.*]] = or i1 [[C_10]], [[C_13]]
 ; CHECK-NEXT:    [[NEXT_MAYBE_UNDEF]] = or i1 [[MAYBE_UNDEF]], [[C_10_OR_13]]
 ; CHECK-NEXT:    [[C_NOT_10_OR_13:%.*]] = xor i1 [[C_10_OR_13]], true
 ; CHECK-NEXT:    br i1 [[C_NOT_10_OR_13]], label [[WHILE_BODY_I]], label [[WHILE_BODY_I_BREAK:%.*]]
 ; CHECK:       while.body.i.break:
-; CHECK-NEXT:    br i1 [[MAYBE_UNDEF]], label [[WHILE_BODY]], label [[SWITCH_EARLY_TEST:%.*]]
+; CHECK-NEXT:    [[TMP0:%.*]] = freeze i1 [[MAYBE_UNDEF]]
+; CHECK-NEXT:    br i1 [[TMP0]], label [[WHILE_BODY]], label [[SWITCH_EARLY_TEST:%.*]]
 ; CHECK:       switch.early.test:
 ; CHECK-NEXT:    switch i8 [[C]], label [[RETURN:%.*]] [
 ; CHECK-NEXT:    i8 13, label [[WHILE_BODY]]
 ; CHECK-NEXT:    i8 10, label [[WHILE_BODY]]
 ; CHECK-NEXT:    ]
 ; CHECK:       return:
 ; CHECK-NEXT:    ret void
 ;

 ; CHECK-NEXT:    [[C:%.*]] = call fastcc signext i8 @next_char()
 ; CHECK-NEXT:    [[C_10:%.*]] = icmp eq i8 [[C]], 10
 ; CHECK-NEXT:    [[C_13:%.*]] = icmp eq i8 [[C]], 13
 ; CHECK-NEXT:    [[C_10_OR_13:%.*]] = or i1 [[C_10]], [[C_13]]
 ; CHECK-NEXT:    [[NEXT_MAYBE_UNDEF]] = or i1 [[MAYBE_UNDEF]], [[C_10_OR_13]]
 ; CHECK-NEXT:    [[C_NOT_10_OR_13:%.*]] = xor i1 [[C_10_OR_13]], true
 ; CHECK-NEXT:    br i1 [[C_NOT_10_OR_13]], label [[WHILE_BODY_I]], label [[WHILE_BODY_I_BREAK:%.*]]
 ; CHECK:       while.body.i.break:
-; CHECK-NEXT:    br i1 [[NEXT_MAYBE_UNDEF]], label [[WHILE_BODY]], label [[RETURN:%.*]]
+; CHECK-NEXT:    [[TMP0:%.*]] = freeze i1 [[MAYBE_UNDEF]]
+; CHECK-NEXT:    br i1 [[TMP0]], label [[WHILE_BODY]], label [[SWITCH_EARLY_TEST:%.*]]
+; CHECK:       switch.early.test:
+; CHECK-NEXT:    switch i8 [[C]], label [[RETURN:%.*]] [
+; CHECK-NEXT:    i8 13, label [[WHILE_BODY]]
+; CHECK-NEXT:    i8 10, label [[WHILE_BODY]]
+; CHECK-NEXT:    ]
 ; CHECK:       return:
 ; CHECK-NEXT:    ret void
 ;
 
 entry:
   br label %while.body
 
 while.body: