[X86] Fix PR39658: avoid duplicated successors in condibr merge

[xur]

Summary

This is to fix PR39658 where duplicated successors (and phi operands) causing miscompile.

[mkazantsev]

lib/Target/X86/X86CondBrFolding.cpp

227

It is just wrong. In PR39658, we are dealing with the following situation:

A:
  sub x, y
  jg C
  jmp B
B:
  sub x, y
  jmp C
C:
  Phi [v1, A], [v2, B]

You are trying to merge A and B together, but they cannot be merged specifically for the reason that it is actually important from which block we came to C. The value of the Phi node depends on this. You cannot just say that we no longer come from B and therefore Phi never takes value v2. It does take this value if x was less or equal than y.

This patch is not helping the ogirinal miscompile. I think that the right solution is to prohibit merging blocks A and B if there is a Phi which has different incoming values for these blocks.

test/CodeGen/X86/pr39658.ll

11

Please use FileCheck to assert that the contents of Phis in question is correct.

[xur]

This is the updated version. We will bail out the optimization is there are PHIs preventing the merge.

@Max: could you tell you real test case to see if this fixes the problem.

Note that this patch still leave this optimization off by default. I will have separated patch to turn if on later.

[xbolva00]

lib/Target/X86/X86CondBrFolding.cpp

272

Remove brackets?

374

Extra newline

[xur]

Uploaded a wrong patch. This is the patch I intended to send.

[mkazantsev]

I confirm that this helps all original miscompile tests I have. I am OK with the approach in general, but have some comments about implementation. I think it should be done either faster and easier (with the same scope) or made less conservative.

lib/Target/X86/X86CondBrFolding.cpp

145

A Phi cannot be the last instruction in a block, so MI != ME is redundant.

152

You are just checking that a Phi has inputs from both MBB and RootMBB, and you check it for every Phi. It actually makes no sense: all Phis either have inputs from these two blocks or they don't.

This is actually a very conservative check. Even if you have these two blocks as predecessors, but the *same* value comes to this Phi from these blocks, then this particular Phi does not prevent you from folding.

So you should pick one of two approaches:

1. Conservative approach: do the check you are doing now, but for one Phi only. It makes no sense to check incoming blocks for all Phis because they all have the same set of incoming blocks. I am not familiar with MBBs well enough, but I guess it can be done by just checking if both MBB and RootMBB are in set of our blocks' predecessors.
2. General approach: do checks for every Phi, but only return true if different values come from RootMBB and MBB to a Phi.

[xur]

lib/Target/X86/X86CondBrFolding.cpp

152

your comments make a lot of sense. I would prefer to use the conservative approach:
(1) I don't think the general approach will touch many more cases -- they are rare.
(2) there does not seem to existing a function to compare phi values in general. I also need to remove duplicated phi-operands after updating. I don't feel it worthy for all the code needed.

For the conservative approach, as you suggested, I still check phi, but one only. I don't think checking the blocks' predecessors is better here. There are cases that we have both MBB and RootMBB as the predecessors but there is no PHI.

[xur]

Integrated Max's review comments.

[mkazantsev]

lib/Target/X86/X86CondBrFolding.cpp

152

Should be llvm::find_if(MBBI->predecessors(), ..., not successors.

test/CodeGen/X86/pr39658.ll

15

I would rather check Phi nodes we used to modify improperly, not jump instructions that can accidentally be matched in other blocks.

lib/Target/X86/X86CondBrFolding.cpp

private:
   bool findPath(MachineBasicBlock *MBB,
                 SmallVectorImpl<MachineBasicBlock *> &BranchPath);
   TargetMBBInfo *getMBBInfo(MachineBasicBlock *MBB) const {
     return MBBInfos[MBB->getNumber()].get();
   }
 };
 } // namespace
 
+// Check if there are PHIs that prevent the merge.
+//     RootMBB --... --> MBB --> TargetMBB
+//                       \--> FallthoughMBB
+// For the PHIs in TargetMBB and FallthroughMBB, if one of its values from
+// MBB and there exists another value from RootMBB, we cannot merge MBB with
+// RootMBB. Here we are doing in a conservative way: if there are PHIs and
+// there is a value from RootMBB, we return true.  A more general approach
+// would be checking the PHI values and if they are the same, we still can
+// merge MBB with RootMBB.
+bool unmergeablePHI(const MachineBasicBlock *MBB,
+                    const MachineBasicBlock *RootMBB) {
+  for (auto MBBI : MBB->successors()) {
+    MachineInstr *MI = &*MBBI->begin();
+    if (!MI->isPHI())
+      continue;
+    // If RootMBB is MBBI's pred, we don't merge.
+    auto SI =
+        llvm::find_if(MBBI->successors(), [&RootMBB](const MachineBasicBlock *SI){
+          return SI == RootMBB;
+        });
+    if (SI != MBBI->pred_end())
+      return true;
+  }
+  return false;
+}
+
 // Find a valid path that we can reuse the CondCode.
 // The resulted path (if return true) is stored in BranchPath.
 // Return value:
 //  false: is no valid path is found.
 //  true: a valid path is found and the targetBB can be reached.
 bool X86CondBrFolding::findPath(
     MachineBasicBlock *MBB, SmallVectorImpl<MachineBasicBlock *> &BranchPath) {
   TargetMBBInfo *MBBInfo = getMBBInfo(MBB);
for (unsigned i = 2, e = MI->getNumOperands() + 1; i != e; i += 2) {
       MachineOperand &MO = MI->getOperand(i);
       if (MO.getMBB() == OldMBB)
         MO.setMBB(NewMBB);
     }
 }
 
 // Utility function to set branch probability for edge MBB->SuccMBB.
 static inline bool setBranchProb(MachineBasicBlock *MBB,
                                  MachineBasicBlock *SuccMBB,
                                  BranchProbability Prob) {
   auto MBBI = std::find(MBB->succ_begin(), MBB->succ_end(), SuccMBB);
   if (MBBI == MBB->succ_end())
     return false;
   MBB->setSuccProbability(MBBI, Prob);
   return true;
 }
 
if (MBBInfo->TBB == OrigDest) {
     MBBInfo->BrInstr = MIB.getInstr();
   } else { // Should be the unconditional jump stmt.
     MachineBasicBlock::iterator UncondBrI = findUncondBrI(MBB);
     BuildMI(*MBB, UncondBrI, MBB->findDebugLoc(UncondBrI), TII->get(X86::JMP_1))
         .addMBB(NewDest);
     MBBInfo->FBB = NewDest;
     BrMI = &*UncondBrI;
   }
+
+  auto SI =
+      llvm::find_if(MBB->successors(), [&NewDest](const MachineBasicBlock *SI) {
+        return SI == NewDest;
+      });
+  BranchProbability Prob = MBPI->getEdgeProbability(MBB, OrigDest);
+  if (SI == MBB->succ_end()) {
+    MBB->addSuccessor(NewDest);
+  } else
+    Prob += MBPI->getEdgeProbability(MBB, NewDest);
   fixPHIsInSucc(NewDest, OrigDest, MBB);
+  setBranchProb(MBB, NewDest, Prob);
   BrMI->eraseFromParent();
-  MBB->addSuccessor(NewDest);
-  setBranchProb(MBB, NewDest, MBPI->getEdgeProbability(MBB, OrigDest));
   MBB->removeSuccessor(OrigDest);
 }
 
 // Change the CondCode and BrInstr according to MBBInfo.
 void X86CondBrFolding::fixupModifiedCond(MachineBasicBlock *MBB) {
   TargetMBBInfo *MBBInfo = getMBBInfo(MBB);
   if (!MBBInfo->Modified)
     return;
if (CC != X86::COND_E) {
     BuildMI(*RootMBB, UncondBrI, RootMBB->findDebugLoc(UncondBrI),
             TII->get(GetCondBranchFromCond(NewCC)))
         .addMBB(RootMBBInfo->FBB);
 
     // RootMBB: Jump to TargetMBB
     BuildMI(*RootMBB, UncondBrI, RootMBB->findDebugLoc(UncondBrI),
             TII->get(X86::JMP_1))
         .addMBB(TargetMBB);
+
+    auto SI = llvm::find_if(
+        RootMBB->successors(),
+        [&TargetMBB](const MachineBasicBlock *SI) { return SI == TargetMBB; });
+    if (SI == RootMBB->succ_end())
       RootMBB->addSuccessor(TargetMBB);
     fixPHIsInSucc(TargetMBB, &MBB, RootMBB);
+
     RootMBB->erase(UncondBrI);
   } else {
     replaceBrDest(RootMBB, RootMBBInfo->TBB, TargetMBB);
   }
 
   // Fix RootMBB's CmpValue to MBB's CmpValue to TargetMBB. Don't set Imm
   // directly. Move MBB's stmt to here as the opcode might be different.
   if (RootMBBInfo->CmpValue != MBBInfo->CmpValue) {
if (!MBBInfo || !MBBInfo->CmpBrOnly)
       continue;
     if (MBB.pred_size() != 1)
       continue;
     LLVM_DEBUG(dbgs() << "Work on MBB." << MBB.getNumber()
                       << " CmpValue: " << MBBInfo->CmpValue << "\n");
     SmallVector<MachineBasicBlock *, 4> BranchPath;
     if (!findPath(&MBB, BranchPath))
       continue;
+    if (unmergeablePHI(&MBB, BranchPath.back()))
+      continue;
 
 #ifndef NDEBUG
     LLVM_DEBUG(dbgs() << "Found one path (len=" << BranchPath.size() << "):\n");
     int Index = 1;
     LLVM_DEBUG(dbgs() << "Target MBB is: " << MBB << "\n");
     for (auto I = BranchPath.rbegin(); I != BranchPath.rend(); ++I, ++Index) {
       MachineBasicBlock *PMBB = *I;
       TargetMBBInfo *PMBBInfo = getMBBInfo(PMBB);
bool X86CondBrFoldingPass::runOnMachineFunction(MachineFunction &MF) {
   const X86Subtarget &ST = MF.getSubtarget<X86Subtarget>();
   if (!ST.threewayBranchProfitable())
     return false;
   const X86InstrInfo *TII = ST.getInstrInfo();
   const MachineBranchProbabilityInfo *MBPI =
       &getAnalysis<MachineBranchProbabilityInfo>();
 
   X86CondBrFolding CondBr(TII, MBPI, MF);
-  return CondBr.optimize();
+  bool Ret = CondBr.optimize();
+#ifdef EXPENSIVE_CHECKS
+  if (Ret)
+    MF.verify();
+#endif
+  return Ret;
 }

test/CodeGen/X86/pr39658.ll

+; RUN: llc -x86-condbr-folding=true -mtriple=x86_64-linux-gnu -mcpu=sandybridge %s -o - -verify-machineinstrs | FileCheck %s
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+@s = common dso_local local_unnamed_addr global i32 0, align 4
+
+define i32 @case1(i32 %n, i32 %v1, i32 %v2, i32 %v3, i32 %v4, i32 %v5) {
+entry:
+  %add = add nsw i32 %v1, 100
+  %cmp = icmp sgt i32 %n, 43
+  br i1 %cmp, label %if.end11, label %if.else
+; CHECK_LABEL: case1
+; CHECK: jg
+; CHECK-NOT: jge
+
+if.else:
+  %cmp1 = icmp eq i32 %n, 43
+  br i1 %cmp1, label %if.end11, label %if.else3
+
+if.else3:
+  %cmp4 = icmp sgt i32 %n, 41
+  br i1 %cmp4, label %if.end11, label %if.else6
+
+if.else6:
+  %cmp7 = icmp eq i32 %n, 41
+  br i1 %cmp7, label %if.then8, label %if.end11
+
+if.then8:
+  %call = tail call i32 (...) @bar1()
+  br label %if.end11
+
+if.end11:
+  %v.0 = phi i32 [ %add, %if.then8 ], [ %add, %if.else6 ], [ %v2, %entry ], [ %v3, %if.else ], [ %v4, %if.else3 ]
+  %call12 = tail call i32 @bar3(i32 %v.0)
+  ret i32 %call12
+}
+
+define i32 @case2(i32 %n, i32 %v1, i32 %v3, i32 %v4, i32 %v5) {
+entry:
+  %add = add nsw i32 %v1, 100
+  %cmp = icmp sgt i32 %n, 43
+  br i1 %cmp, label %if.end11, label %if.else
+; CHECK_LABEL: case1
+; CHECK: jg
+; CHECK-NOT: jge
+
+if.else:
+  %cmp1 = icmp eq i32 %n, 43
+  br i1 %cmp1, label %if.end11, label %if.else3
+
+if.else3:
+  %cmp4 = icmp sgt i32 %n, 41
+  br i1 %cmp4, label %if.end11, label %if.else6
+
+if.else6:
+  %cmp7 = icmp eq i32 %n, 41
+  br i1 %cmp7, label %if.then8, label %if.end11
+
+if.then8:
+  %call = tail call i32 (...) @bar1()
+  br label %if.end11
+
+if.end11:
+  %v.0 = phi i32 [ %add, %if.then8 ], [ %add, %if.else6 ], [ %add, %entry ], [ %v3, %if.else ], [ %v4, %if.else3 ]
+  %call12 = tail call i32 @bar3(i32 %v.0)
+  ret i32 %call12
+}
+
+define i32 @case3(i32 %n, i32 %v1, i32 %v2, i32 %v3) {
+entry:
+  %cmp = icmp sgt i32 %n, 41
+  br i1 %cmp, label %if.then, label %if.else
+; CHECK_LABEL: case2
+; CHECK: jl
+; CHECK: jle
+
+if.then:
+  %call = tail call i32 (...) @bar1()
+  br label %if.end4
+
+if.else:
+  %cmp1 = icmp eq i32 %n, 41
+  br i1 %cmp1, label %if.then2, label %if.end4
+
+if.then2:
+  %call3 = tail call i32 (...) @bar2()
+  br label %if.end4
+
+if.end4:
+  %v.0 = phi i32 [ %v2, %if.then ], [ %v3, %if.then2 ], [ %v1, %if.else ]
+  %call5 = tail call i32 @bar3(i32 %v.0)
+  %0 = load i32, i32* @s, align 4
+  ret i32 %0
+}
+
+declare i32 @bar1(...)
+declare i32 @bar2(...)
+declare i32 @bar3(i32)