[SimplifyCFG] Fix for PR34219: Preserve alignment after merging conditional stores.

[ABataev]

Summary

If SimplifyCFG pass is able to merge conditional stores into single one,
it loses the alignment. This may lead to incorrect codegen. Patch
sets the alignment of the new instruction if it is set in the original
one.

[efriedma]

lib/Transforms/Utils/SimplifyCFG.cpp

2969 ↗

(On Diff #111539)

This looks weird; why are we calling "PStore->getAAMetadata" twice?

2972 ↗

(On Diff #111539)

What happens if PStore and QStore have different alignment?

[ABataev]

lib/Transforms/Utils/SimplifyCFG.cpp

2972 ↗

(On Diff #111539)

Generally speaking, they must be the same.

[efriedma]

lib/Transforms/Utils/SimplifyCFG.cpp

2972 ↗

(On Diff #111539)

I don't see any code to ensure they are the same. (Or do you mean we shouldn't do this transform if the alignment is different?)

[ABataev]

lib/Transforms/Utils/SimplifyCFG.cpp

2972 ↗

(On Diff #111539)

Actually, PStore and QStore work with the same values, so they must have the same alignment because it is the same operations. We just merge them into the single one. I'm not sure, if they may have the different alignments. If they may have the different alignments, we can choose the one that is greater.

[efriedma]

lib/Transforms/Utils/SimplifyCFG.cpp

2972 ↗

(On Diff #111539)

I think you have to take the smaller of the two alignments? Even if the pointer value is the same "Value*", it could have different alignment along different codepaths.

[ABataev]

lib/Transforms/Utils/SimplifyCFG.cpp

2972 ↗

(On Diff #111539)

Why? If have 2 stores with different alignments, we know that it is safe to use both of them. We should use the biggest one.

[efriedma]

Why? If have 2 stores with different alignments, we know that it is safe to use both of them. We should use the biggest one.

If we could prove both stores execute, we could use biggest one. In this case, though, we only know that one of the stores executes (assuming I'm reading this code correctly). And we don't know it's safe to take the alignment from a store that doesn't execute. So we have to use the smaller alignment.

[ABataev]

Update after review

[efriedma]

lib/Transforms/Utils/SimplifyCFG.cpp

2976 ↗

(On Diff #112895)

This isn't really handling zero alignment correctly; to get the right number here, you have to convert to the actual alignment using datalayout. (I'm planning to write a patch soon to get rid of this whole zero alignment crap; it's unnecessary given that datalayout is now mandatory, and it's bitten us too many times.)

It would be nice to have a comment briefly explaining why we pick the minimum.

2969 ↗

(On Diff #111539)

No comment on the getAAMetadata() calls?

[ABataev]

lib/Transforms/Utils/SimplifyCFG.cpp

2976 ↗

(On Diff #112895)

Ok, will do this, but tomorrow.

2969 ↗

(On Diff #111539)

I don't know what's going here, it is another problem. I just want to fix one PR here.

[ABataev]

Update after review.

[ABataev]

lib/Transforms/Utils/SimplifyCFG.cpp

2969 ↗

(On Diff #111539)

Most probably, it is a copy-paste error. Must be

PStore->getAAMetadata(AAMD, /*Merge=*/false);
QStore->getAAMetadata(AAMD, /*Merge=*/true);

[efriedma]

LGTM.

llvm/trunk/lib/Transforms/Utils/SimplifyCFG.cpp

if (PredBB != BB)
       PHI->addIncoming(
           AlternativeV ? AlternativeV : UndefValue::get(V->getType()), PredBB);
   return PHI;
 }
 
 static bool mergeConditionalStoreToAddress(BasicBlock *PTB, BasicBlock *PFB,
                                            BasicBlock *QTB, BasicBlock *QFB,
                                            BasicBlock *PostBB, Value *Address,
-                                           bool InvertPCond, bool InvertQCond) {
+                                           bool InvertPCond, bool InvertQCond,
+                                           const DataLayout &DL) {
   auto IsaBitcastOfPointerType = [](const Instruction &I) {
     return Operator::getOpcode(&I) == Instruction::BitCast &&
            I.getType()->isPointerTy();
   };
 
   // If we're not in aggressive mode, we only optimize if we have some
   // confidence that by optimizing we'll allow P and/or Q to be if-converted.
   auto IsWorthwhile = [&](BasicBlock *BB) {
static bool mergeConditionalStoreToAddress(BasicBlock *PTB, BasicBlock *PFB,
   auto *T =
       SplitBlockAndInsertIfThen(CombinedPred, &*QB.GetInsertPoint(), false);
   QB.SetInsertPoint(T);
   StoreInst *SI = cast<StoreInst>(QB.CreateStore(QPHI, Address));
   AAMDNodes AAMD;
   PStore->getAAMetadata(AAMD, /*Merge=*/false);
   PStore->getAAMetadata(AAMD, /*Merge=*/true);
   SI->setAAMetadata(AAMD);
+  unsigned PAlignment = PStore->getAlignment();
+  unsigned QAlignment = QStore->getAlignment();
+  unsigned TypeAlignment =
+      DL.getABITypeAlignment(SI->getValueOperand()->getType());
+  unsigned MinAlignment;
+  unsigned MaxAlignment;
+  std::tie(MinAlignment, MaxAlignment) = std::minmax(PAlignment, QAlignment);
+  // Choose the minimum alignment. If we could prove both stores execute, we
+  // could use biggest one.  In this case, though, we only know that one of the
+  // stores executes.  And we don't know it's safe to take the alignment from a
+  // store that doesn't execute.
+  if (MinAlignment != 0) {
+    // Choose the minimum of all non-zero alignments.
+    SI->setAlignment(MinAlignment);
+  } else if (MaxAlignment != 0) {
+    // Choose the minimal alignment between the non-zero alignment and the ABI
+    // default alignment for the type of the stored value.
+    SI->setAlignment(std::min(MaxAlignment, TypeAlignment));
+  } else {
+    // If both alignments are zero, use ABI default alignment for the type of
+    // the stored value.
+    SI->setAlignment(TypeAlignment);
+  }
 
   QStore->eraseFromParent();
   PStore->eraseFromParent();
 
   return true;
 }
 
-static bool mergeConditionalStores(BranchInst *PBI, BranchInst *QBI) {
+static bool mergeConditionalStores(BranchInst *PBI, BranchInst *QBI,
+                                   const DataLayout &DL) {
   // The intention here is to find diamonds or triangles (see below) where each
   // conditional block contains a store to the same address. Both of these
   // stores are conditional, so they can't be unconditionally sunk. But it may
   // be profitable to speculatively sink the stores into one merged store at the
   // end, and predicate the merged store on the union of the two conditions of
   // PBI and QBI.
   //
   // This can reduce the number of stores executed if both of the conditions are
static bool mergeConditionalStores(BranchInst *PBI, BranchInst *QBI,
   set_intersect(PStoreAddresses, QStoreAddresses);
   // set_intersect mutates PStoreAddresses in place. Rename it here to make it
   // clear what it contains.
   auto &CommonAddresses = PStoreAddresses;
 
   bool Changed = false;
   for (auto *Address : CommonAddresses)
     Changed |= mergeConditionalStoreToAddress(
-        PTB, PFB, QTB, QFB, PostBB, Address, InvertPCond, InvertQCond);
+        PTB, PFB, QTB, QFB, PostBB, Address, InvertPCond, InvertQCond, DL);
   return Changed;
 }
 
 /// If we have a conditional branch as a predecessor of another block,
 /// this function tries to simplify it.  We know
 /// that PBI and BI are both conditional branches, and BI is in one of the
 /// successor blocks of PBI - PBI branches to BI.
 static bool SimplifyCondBranchToCondBranch(BranchInst *PBI, BranchInst *BI,
static bool SimplifyCondBranchToCondBranch(BranchInst *PBI, BranchInst *BI,
 
   if (auto *CE = dyn_cast<ConstantExpr>(BI->getCondition()))
     if (CE->canTrap())
       return false;
 
   // If both branches are conditional and both contain stores to the same
   // address, remove the stores from the conditionals and create a conditional
   // merged store at the end.
-  if (MergeCondStores && mergeConditionalStores(PBI, BI))
+  if (MergeCondStores && mergeConditionalStores(PBI, BI, DL))
     return true;
 
   // If this is a conditional branch in an empty block, and if any
   // predecessors are a conditional branch to one of our destinations,
   // fold the conditions into logical ops and one cond br.
   BasicBlock::iterator BBI = BB->begin();
   // Ignore dbg intrinsics.
   while (isa<DbgInfoIntrinsic>(BBI))
if (BranchInst *PBI = dyn_cast<BranchInst>((*PI)->getTerminator()))
         if (SimplifyCondBranchToCondBranch(PBI, BI, DL))
           return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true;
 
   // Look for diamond patterns.
   if (MergeCondStores)
     if (BasicBlock *PrevBB = allPredecessorsComeFromSameSource(BB))
       if (BranchInst *PBI = dyn_cast<BranchInst>(PrevBB->getTerminator()))
         if (PBI != BI && PBI->isConditional())
-          if (mergeConditionalStores(PBI, BI))
+          if (mergeConditionalStores(PBI, BI, DL))
             return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true;
 
   return false;
 }
 
 /// Check if passing a value to an instruction will cause undefined behavior.
 static bool passingValueIsAlwaysUndefined(Value *V, Instruction *I) {
   Constant *C = dyn_cast<Constant>(V);

llvm/trunk/test/Transforms/SimplifyCFG/preserve-store-alignment.ll

 ; CHECK-NEXT:    [[AND4:%.*]] = and i64 [[TMP2]], 2
 ; CHECK-NEXT:    [[TOBOOL5:%.*]] = icmp eq i64 [[AND4]], 0
 ; CHECK-NEXT:    [[TMP5:%.*]] = add nsw <2 x i64> [[TMP4]], <i64 1, i64 1>
 ; CHECK-NEXT:    [[DOT:%.*]] = select i1 [[TOBOOL5]], <2 x i64> [[TMP4]], <2 x i64> [[TMP5]]
 ; CHECK-NEXT:    [[TMP6:%.*]] = xor i1 [[TOBOOL]], true
 ; CHECK-NEXT:    [[TMP7:%.*]] = xor i1 [[TOBOOL5]], true
 ; CHECK-NEXT:    [[TMP8:%.*]] = or i1 [[TMP6]], [[TMP7]]
 ; CHECK-NEXT:    br i1 [[TMP8]], label [[TMP9:%.*]], label [[TMP10:%.*]]
-; CHECK:         store <2 x i64> [[DOT]], <2 x i64>* bitcast (i64* getelementptr inbounds (%struct.Counters, %struct.Counters* @counters, i64 0, i32 1) to <2 x i64>*)
+; CHECK:         store <2 x i64> [[DOT]], <2 x i64>* bitcast (i64* getelementptr inbounds (%struct.Counters, %struct.Counters* @counters, i64 0, i32 1) to <2 x i64>*), align 8
 ; CHECK-NEXT:    br label [[TMP10]]
 ; CHECK:         ret i32 0
 ;
 entry:
   %0 = load <2 x i64>, <2 x i64>* bitcast (i64* getelementptr inbounds (%struct.Counters, %struct.Counters* @counters, i64 0, i32 1) to <2 x i64>*), align 8
   %1 = add nsw <2 x i64> %0, <i64 1, i64 1>
   store <2 x i64> %1, <2 x i64>* bitcast (i64* getelementptr inbounds (%struct.Counters, %struct.Counters* @counters, i64 0, i32 1) to <2 x i64>*), align 8
   %2 = load i64, i64* @m, align 8

 ; CHECK-NEXT:    [[AND4:%.*]] = and i64 [[TMP2]], 2
 ; CHECK-NEXT:    [[TOBOOL5:%.*]] = icmp eq i64 [[AND4]], 0
 ; CHECK-NEXT:    [[TMP5:%.*]] = add nsw <2 x i64> [[TMP4]], <i64 1, i64 1>
 ; CHECK-NEXT:    [[DOT:%.*]] = select i1 [[TOBOOL5]], <2 x i64> [[TMP4]], <2 x i64> [[TMP5]]
 ; CHECK-NEXT:    [[TMP6:%.*]] = xor i1 [[TOBOOL]], true
 ; CHECK-NEXT:    [[TMP7:%.*]] = xor i1 [[TOBOOL5]], true
 ; CHECK-NEXT:    [[TMP8:%.*]] = or i1 [[TMP6]], [[TMP7]]
 ; CHECK-NEXT:    br i1 [[TMP8]], label [[TMP9:%.*]], label [[TMP10:%.*]]
-; CHECK:         store <2 x i64> [[DOT]], <2 x i64>* bitcast (i64* getelementptr inbounds (%struct.Counters, %struct.Counters* @counters, i64 0, i32 1) to <2 x i64>*)
+; CHECK:         store <2 x i64> [[DOT]], <2 x i64>* bitcast (i64* getelementptr inbounds (%struct.Counters, %struct.Counters* @counters, i64 0, i32 1) to <2 x i64>*), align 8
 ; CHECK-NEXT:    br label [[TMP10]]
 ; CHECK:         ret i32 0
 ;
 entry:
   %0 = load <2 x i64>, <2 x i64>* bitcast (i64* getelementptr inbounds (%struct.Counters, %struct.Counters* @counters, i64 0, i32 1) to <2 x i64>*), align 8
   %1 = add nsw <2 x i64> %0, <i64 1, i64 1>
   store <2 x i64> %1, <2 x i64>* bitcast (i64* getelementptr inbounds (%struct.Counters, %struct.Counters* @counters, i64 0, i32 1) to <2 x i64>*), align 8
   %2 = load i64, i64* @m, align 8

 ; CHECK-NEXT:    [[AND4:%.*]] = and i64 [[TMP2]], 2
 ; CHECK-NEXT:    [[TOBOOL5:%.*]] = icmp eq i64 [[AND4]], 0
 ; CHECK-NEXT:    [[TMP5:%.*]] = add nsw <2 x i64> [[TMP4]], <i64 1, i64 1>
 ; CHECK-NEXT:    [[DOT:%.*]] = select i1 [[TOBOOL5]], <2 x i64> [[TMP4]], <2 x i64> [[TMP5]]
 ; CHECK-NEXT:    [[TMP6:%.*]] = xor i1 [[TOBOOL]], true
 ; CHECK-NEXT:    [[TMP7:%.*]] = xor i1 [[TOBOOL5]], true
 ; CHECK-NEXT:    [[TMP8:%.*]] = or i1 [[TMP6]], [[TMP7]]
 ; CHECK-NEXT:    br i1 [[TMP8]], label [[TMP9:%.*]], label [[TMP10:%.*]]
-; CHECK:         store <2 x i64> [[DOT]], <2 x i64>* bitcast (i64* getelementptr inbounds (%struct.Counters, %struct.Counters* @counters, i64 0, i32 1) to <2 x i64>*)
+; CHECK:         store <2 x i64> [[DOT]], <2 x i64>* bitcast (i64* getelementptr inbounds (%struct.Counters, %struct.Counters* @counters, i64 0, i32 1) to <2 x i64>*), align 8
 ; CHECK-NEXT:    br label [[TMP10]]
 ; CHECK:         ret i32 0
 ;
 entry:
   %0 = load <2 x i64>, <2 x i64>* bitcast (i64* getelementptr inbounds (%struct.Counters, %struct.Counters* @counters, i64 0, i32 1) to <2 x i64>*), align 8
   %1 = add nsw <2 x i64> %0, <i64 1, i64 1>
   store <2 x i64> %1, <2 x i64>* bitcast (i64* getelementptr inbounds (%struct.Counters, %struct.Counters* @counters, i64 0, i32 1) to <2 x i64>*), align 8
   %2 = load i64, i64* @m, align 8

 ; CHECK-NEXT:    [[AND4:%.*]] = and i64 [[TMP2]], 2
 ; CHECK-NEXT:    [[TOBOOL5:%.*]] = icmp eq i64 [[AND4]], 0
 ; CHECK-NEXT:    [[TMP5:%.*]] = add nsw <2 x i64> [[TMP4]], <i64 1, i64 1>
 ; CHECK-NEXT:    [[DOT:%.*]] = select i1 [[TOBOOL5]], <2 x i64> [[TMP4]], <2 x i64> [[TMP5]]
 ; CHECK-NEXT:    [[TMP6:%.*]] = xor i1 [[TOBOOL]], true
 ; CHECK-NEXT:    [[TMP7:%.*]] = xor i1 [[TOBOOL5]], true
 ; CHECK-NEXT:    [[TMP8:%.*]] = or i1 [[TMP6]], [[TMP7]]
 ; CHECK-NEXT:    br i1 [[TMP8]], label [[TMP9:%.*]], label [[TMP10:%.*]]
-; CHECK:         store <2 x i64> [[DOT]], <2 x i64>* bitcast (i64* getelementptr inbounds (%struct.Counters, %struct.Counters* @counters, i64 0, i32 1) to <2 x i64>*)
+; CHECK:         store <2 x i64> [[DOT]], <2 x i64>* bitcast (i64* getelementptr inbounds (%struct.Counters, %struct.Counters* @counters, i64 0, i32 1) to <2 x i64>*), align 16
 ; CHECK-NEXT:    br label [[TMP10]]
 ; CHECK:         ret i32 0
 ;
 entry:
   %0 = load <2 x i64>, <2 x i64>* bitcast (i64* getelementptr inbounds (%struct.Counters, %struct.Counters* @counters, i64 0, i32 1) to <2 x i64>*), align 8
   %1 = add nsw <2 x i64> %0, <i64 1, i64 1>
   store <2 x i64> %1, <2 x i64>* bitcast (i64* getelementptr inbounds (%struct.Counters, %struct.Counters* @counters, i64 0, i32 1) to <2 x i64>*), align 8
   %2 = load i64, i64* @m, align 8

 ; CHECK-NEXT:    [[AND4:%.*]] = and i64 [[TMP2]], 2
 ; CHECK-NEXT:    [[TOBOOL5:%.*]] = icmp eq i64 [[AND4]], 0
 ; CHECK-NEXT:    [[TMP5:%.*]] = add nsw <2 x i64> [[TMP4]], <i64 1, i64 1>
 ; CHECK-NEXT:    [[DOT:%.*]] = select i1 [[TOBOOL5]], <2 x i64> [[TMP4]], <2 x i64> [[TMP5]]
 ; CHECK-NEXT:    [[TMP6:%.*]] = xor i1 [[TOBOOL]], true
 ; CHECK-NEXT:    [[TMP7:%.*]] = xor i1 [[TOBOOL5]], true
 ; CHECK-NEXT:    [[TMP8:%.*]] = or i1 [[TMP6]], [[TMP7]]
 ; CHECK-NEXT:    br i1 [[TMP8]], label [[TMP9:%.*]], label [[TMP10:%.*]]
-; CHECK:         store <2 x i64> [[DOT]], <2 x i64>* bitcast (i64* getelementptr inbounds (%struct.Counters, %struct.Counters* @counters, i64 0, i32 1) to <2 x i64>*)
+; CHECK:         store <2 x i64> [[DOT]], <2 x i64>* bitcast (i64* getelementptr inbounds (%struct.Counters, %struct.Counters* @counters, i64 0, i32 1) to <2 x i64>*), align 16
 ; CHECK-NEXT:    br label [[TMP10]]
 ; CHECK:         ret i32 0
 ;
 entry:
   %0 = load <2 x i64>, <2 x i64>* bitcast (i64* getelementptr inbounds (%struct.Counters, %struct.Counters* @counters, i64 0, i32 1) to <2 x i64>*), align 8
   %1 = add nsw <2 x i64> %0, <i64 1, i64 1>
   store <2 x i64> %1, <2 x i64>* bitcast (i64* getelementptr inbounds (%struct.Counters, %struct.Counters* @counters, i64 0, i32 1) to <2 x i64>*), align 8
   %2 = load i64, i64* @m, align 8