[SimplifyCFG] Try to change store operation type when sinking

[mssimpso]

Summary

For a given list of candidate instructions to sink, the sinking algorithm currently checks that each instruction has the same opcode and the same operand types (i.e., Instruction::isSameOperationAs). However, loaded values that are only every stored to memory are canonicalized by InstCombine to have integer types. Because this changes the operand types of the store instructions, this canonicalization can prevent store sinking in SimplifyCFG. So if the candidate instructions are stores, some of which have been canonicalized to operate on integer types while others have not, sinking will not occur. In such a situation, this patch tries to change the stores to operate on the same types so that they may be sunk.

[davide]

+1, we have a dedicated sinking pass. Not blaming on you, but unfortunately SimplifyCFG is becoming a kitchen sink, let's try to keep it at least half-sane :)

[davide]

(As I already previously advocated), instcombine & simplifyCFG shouldn't do any hoisting/sinking whatsoever, but I only had limited energy to fight this battle.

[mssimpso]

Thanks for the quick feedback Danny/Davide. I definitely appreciate the point that SimplifyCFG may not be the best place for this kind of transformation. Davide, I assume the dedicated pass you're referring to is GVNSink? I don't think that pass is enabled yet (I haven't been closely following the progress, so I'm not sure what's holding it up at this point), but it's possible GVNSink would indeed catch the cases this patch does. I haven't tested that yet.

For the record, this patch resulted from rL320749. After sinking was moved later in the pipeline, I noticed that SimplifyCFG began missing sinking opportunities that it once caught due to the load/store canonicalization in InstCombine that I mentioned. So the intent wasn't really to extend SimplifyCFG, but to restore it's functionality.

[davide]

I might consider holding my nose, if this restores something that was there.
I think the other two passes we have for doing sinking aren't currently enabled (GVNSink and Sink.cpp), although unless somebody puts effort in them this will always be a chicken-egg problem.
I'm not sure I'll have the time to review this patch carefully, I don't want to put you on the hook, but if you can consider an alternative, that would be great.
If you look at the original review you'll notice that I was fundamentally opposed to the change, see e.g. https://reviews.llvm.org/D38566#926530
(FWIW, it doesn't matter where we move sinking/hoisting there will be always some case that we can't get properly. We, of course should prioritize for the common case, at least IMHO).

[mssimpso]

In D42007#975304, @davide wrote:

I might consider holding my nose, if this restores something that was there.
I think the other two passes we have for doing sinking aren't currently enabled (GVNSink and Sink.cpp), although unless somebody puts effort in them this will always be a chicken-egg problem.
I'm not sure I'll have the time to review this patch carefully, I don't want to put you on the hook, but if you can consider an alternative, that would be great.
If you look at the original review you'll notice that I was fundamentally opposed to the change, see e.g. https://reviews.llvm.org/D38566#926530
(FWIW, it doesn't matter where we move sinking/hoisting there will be always some case that we can't get properly. We, of course should prioritize for the common case, at least IMHO).

I agree with that. I'll play around with GVNSink when I have a chance (this particular patch isn't exceptionally important to me right now). If we can enable GVNSink, perhaps we'll be able to completely remove sinking from SimplifyCFG.

lib/Transforms/Utils/SimplifyCFG.cpp

HoistTerminator:
   // Update any PHI nodes in our new successors.
   for (BasicBlock *Succ : successors(BB1))
     AddPredecessorToBlock(Succ, BIParent, BB1);
 
   EraseTerminatorInstAndDCECond(BI);
   return true;
 }
 
+// Try to change stored value types to encourage sinking.
+//
+// Loads that are only ever used by store instructions are canonicalized to
+// operate on integer types. For example, a load/store sequence operating on
+// doubles, such as the following:
+//
+//   %tmp0 = load double, double* %ptr0
+//   store double %tmp0, double* %ptr1
+//
+// is replaced by an equivalent sequence operating on integer types:
+//
+//   %ptr2 = bitcast double* %ptr0 to i64*
+//   %tmp1 = load i64, i64* %ptr2
+//   %ptr3 = bitcast double* %ptr1 to i64*
+//   store i64 %tmp1, i64* %ptr3
+//
+// This kind of transformation can prevent the sinking performed here due to
+// current limitations of the implementation. To be sinkable, all candidate
+// instructions in the given list must have the same opcode and operand types
+// (i.e., Instruction::isSameOperationAs must be true). If the candidate
+// instructions are stores, and some of them have been canonicalized to operate
+// on integer types and others have not, sinking will not occur. This function
+// tries to detect this situation, and if discovered, modify the operand types
+// of the store instructions such that they can be sunk.
+static void tryToChangeStoreOperationType(ArrayRef<Instruction *> Insts) {
+
+  // All of the instructions must be stores.
+  if (any_of(Insts, [](Instruction *I) { return !isa<StoreInst>(I); }))
+    return;
+
+  // At least one stored value type must be non-integral.
+  auto It = find_if(Insts, [](Instruction *I) {
+    auto *Store = cast<StoreInst>(I);
+    return !Store->getValueOperand()->getType()->isIntegerTy();
+  });
+  if (It == Insts.end())
+    return;
+  Type *NonIntTy = cast<StoreInst>(*It)->getValueOperand()->getType();
+
+  // There must be at least two different stored value types, including the
+  // non-integer type.
+  if (all_of(Insts, [NonIntTy](Instruction *I) {
+        return cast<StoreInst>(I)->getValueOperand()->getType() == NonIntTy;
+      }))
+    return;
+
+  // Compute the bitwidth of the non-integer type.
+  uint64_t BitWidth =
+      Insts[0]->getModule()->getDataLayout().getTypeSizeInBits(NonIntTy);
+
+  // Ensure that each stored value type is either the non-integer type
+  // previously identified or an integer type of the same bitwidth. This code
+  // also ensures that the pointer operand of the stores with integer types is
+  // a bitcast having a single use and whose source type is the non-integer
+  // type.
+  for (auto *I : Insts) {
+    auto *Store = cast<StoreInst>(I);
+    if (Store->getValueOperand()->getType() == NonIntTy)
+      continue;
+    if (!Store->getValueOperand()->getType()->isIntegerTy(BitWidth))
+      return;
+    auto *StorePtrCast = dyn_cast<BitCastInst>(Store->getPointerOperand());
+    if (!StorePtrCast || !StorePtrCast->hasOneUse() ||
+        cast<PointerType>(StorePtrCast->getSrcTy())->getElementType() !=
+            NonIntTy)
+      return;
+  }
+
+  // We now know that we want to change the type of at least one store
+  // instruction.
+  for (auto *I : Insts) {
+    auto *Store = cast<StoreInst>(I);
+    if (Store->getValueOperand()->getType() == NonIntTy)
+      continue;
+    auto *StorePtrCast = cast<BitCastInst>(Store->getPointerOperand());
+
+    // We will cast the stored value to the non-integer type. We choose an
+    // insertion point as early as possible in the same block as the store so
+    // that we don't prevent further sinking.
+    auto *InsertionPt = &*Store->getParent()->getFirstInsertionPt();
+    if (auto *Inst = dyn_cast<Instruction>(Store->getValueOperand()))
+      if (!isa<PHINode>(Inst) && Inst->getParent() == Store->getParent())
+        InsertionPt = &*std::next(BasicBlock::iterator(Inst));
+    IRBuilder<> Builder(InsertionPt);
+
+    // Change the operands of the store, and erase the old pointer operand.
+    Store->setOperand(
+        0, Builder.CreateBitOrPointerCast(Store->getValueOperand(), NonIntTy));
+    Store->setOperand(1, StorePtrCast->getOperand(0));
+    StorePtrCast->eraseFromParent();
+  }
+}
+
 // All instructions in Insts belong to different blocks that all unconditionally
 // branch to a common successor. Analyze each instruction and return true if it
 // would be possible to sink them into their successor, creating one common
 // instruction instead. For every value that would be required to be provided by
 // PHI node (because an operand varies in each input block), add to PHIOperands.
 static bool canSinkInstructions(
     ArrayRef<Instruction *> Insts,
     DenseMap<Instruction *, SmallVector<Value *, 4>> &PHIOperands) {
if (const auto *C = dyn_cast<CallInst>(I))
         return false;
 
     // Everything must have only one use too, apart from stores which
     // have no uses.
     if (!isa<StoreInst>(I) && !I->hasOneUse())
       return false;
   }
 
+  // Try to change stored value types to encourage sinking. If the instructions
+  // are stores, some of which may be been canonicalized to operate on integer
+  // types, try to modify the stores so that they all operate on the same type.
+  tryToChangeStoreOperationType(Insts);
+
   const Instruction *I0 = Insts.front();
   for (auto *I : Insts)
     if (!I->isSameOperationAs(I0))
       return false;
 
   // All instructions in Insts are known to be the same opcode. If they aren't
   // stores, check the only user of each is a PHI or in the same block as the
   // instruction, because if a user is in the same block as an instruction

test/Transforms/SimplifyCFG/sink-common-code.ll

if.end:
   ret i32 1
 }
 
 ; CHECK-LABEL: @test_insertvalue
 ; CHECK: select
 ; CHECK: insertvalue
 ; CHECK-NOT: insertvalue
 
+define void @changeOperationType_0(i1 %c, double* %s, double* %d, double %x, double %y) {
+; CHECK-LABEL: @changeOperationType_0(
+; CHECK:       if.then:
+; CHECK-NEXT:    %tmp0 = getelementptr inbounds double, double* %s, i64 %i
+; CHECK-NEXT:    %tmp1 = bitcast double* %tmp0 to i64*
+; CHECK-NEXT:    %tmp2 = load i64, i64* %tmp1, align 8
+; CHECK-NEXT:    [[CAST:%.*]] = bitcast i64 %tmp2 to double
+; CHECK-NEXT:    br label %for.inc
+; CHECK:       if.end:
+; CHECK-NEXT:    %tmp6 = fsub contract double %x, %y
+; CHECK-NEXT:    br label %for.inc
+; CHECK:       for.inc:
+; CHECK-NEXT:    [[SINK0:%.*]] = phi i64 [ -800002, %if.end ], [ 800035, %if.then ]
+; CHECK-NEXT:    [[SINK1:%.*]] = phi double [ %tmp6, %if.end ], [ [[CAST]], %if.then ]
+; CHECK-NEXT:    %tmp7 = add nsw i64 %i, [[SINK0]]
+; CHECK-NEXT:    %tmp8 = getelementptr inbounds double, double* %d, i64 %tmp7
+; CHECK-NEXT:    store double [[SINK1]], double* %tmp8, align 8
+; CHECK:         br i1 %cmp, label %for.body, label %for.end
+;
+entry:
+  br label %for.body
+
+for.body:
+  %i = phi i64 [ 0, %entry ], [ %i.next, %for.inc ]
+  br i1 %c, label %if.end, label %if.then
+
+if.then:
+  %tmp0 = getelementptr inbounds double, double* %s, i64 %i
+  %tmp1 = bitcast double* %tmp0 to i64*
+  %tmp2 = load i64, i64* %tmp1, align 8
+  %tmp3 = add nuw nsw i64 %i, 800035
+  %tmp4 = getelementptr inbounds double, double* %d, i64 %tmp3
+  %tmp5 = bitcast double* %tmp4 to i64*
+  store i64 %tmp2, i64* %tmp5, align 8
+  br label %for.inc
+
+if.end:
+  %tmp6 = fsub contract double %x, %y
+  %tmp7 = add nsw i64 %i, -800002
+  %tmp8 = getelementptr inbounds double, double* %d, i64 %tmp7
+  store double %tmp6, double* %tmp8, align 8
+  br label %for.inc
+
+for.inc:
+  %i.next = add nuw nsw i64 %i, 20
+  %cmp = icmp ult i64 %i.next, 208000000
+  br i1 %cmp, label %for.body, label %for.end
+
+for.end:
+  ret void
+}
+
+define  void @changeOperationType_1(i1 %c0, i1 %c1, i64 %i, i64 %x, i8*** %a) {
+; CHECK-LABEL: @changeOperationType_1(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br i1 %c0, label %if.then0, label %if.end
+; CHECK:       if.then0:
+; CHECK-NEXT:    %tmp3 = load i8**, i8*** %a, align 8
+; CHECK-NEXT:    %tmp4 = getelementptr inbounds i8*, i8** %tmp3, i64 %i
+; CHECK-NEXT:    [[CAST:%.*]] = inttoptr i64 %x to i8*
+; CHECK-NEXT:    [[SINK:%.*]] = select i1 %c1, i8* null, i8* [[CAST]]
+; CHECK-NEXT:    store i8* [[SINK]], i8** %tmp4, align 8
+; CHECK-NEXT:    br label %if.end
+; CHECK:       if.end:
+; CHECK-NEXT:    ret void
+;
+entry:
+  br i1 %c0, label %if.then0, label %if.end
+
+if.then0:
+  br i1 %c1, label %if.else, label %if.then1
+
+if.then1:
+  %tmp0 = load i8**, i8*** %a, align 8
+  %tmp1 = getelementptr inbounds i8*, i8** %tmp0, i64 %i
+  %tmp2 = bitcast i8** %tmp1 to i64*
+  store i64 %x, i64* %tmp2, align 8
+  br label %if.end
+
+if.else:
+  %tmp3 = load i8**, i8*** %a, align 8
+  %tmp4 = getelementptr inbounds i8*, i8** %tmp3, i64 %i
+  store i8* null, i8** %tmp4, align 8
+  br label %if.end
+
+if.end:
+  ret void
+}
 ; CHECK: ![[$TBAA]] = !{![[TYPE:[0-9]]], ![[TYPE]], i64 0}
 ; CHECK: ![[TYPE]] = !{!"float", ![[TEXT:[0-9]]]}
 ; CHECK: ![[TEXT]] = !{!"an example type tree"}