[CodeGenPrepare]Skip sext promotion if operands for multiple users is detected

[junbuml]

Summary

Do not allow address type promtion if detecting an instruction which has multiple users in the middle of promotion. In such case, ISel could lose opportunities to fold the extension as part of address modes. The added test case should show the case.

[eastig]

lib/CodeGen/CodeGenPrepare.cpp

3361–3362

Don't you think a caller of getAction can get this information itself?

bool hasMultiUserOperand = false;
if (Instruction *ExtOpnd = dyn_cast<Instruction>(I->getOperand(0)))
   hasMultiUserOperand = !ExtOpnd->hasOneUse();
getAction(I, ...);

'getAction' does not use hasMultiUserOperand nor puts it into Action. This parameter looks like exposing internal calculations of the getAction function. If something is changed in the function and there is no hasOneUse call the function would have to continue calculating hasMultiUserOperand as a part of the contract.

4572–4573

Do you assume that the Exts vector always has only one instruction? Otherwise the value of hasMultiUserOperand can be changed from true to false.

4815

The calculation of hasMultiUserOperand is too far from its use. Is it possible to bring it closer?
Do we need other calculations/actions if we know an operand has many users before trying to promote?
What I see we try to promote and discard results if hasMultiUserOperand is true. 'hasMultiUserOperand' can be set up before and transformations. Are there cases when hasMultiUserOperand is set up after transformations?

test/CodeGen/AArch64/arm64-addr-type-promotion.ll

99–100

Does this guarantee lowering to multi usage? Is it possible to write a test in MIR?

[junbuml]

lib/CodeGen/CodeGenPrepare.cpp

3361–3362

I think it's possible to calculate hasMultiUserOperand in caller as we need this only for address type promotion.

4572–4573

I do not assume only one instruction in Exts. After hasMultiUserOperand is initialized as false in optimizeExt(), hasMultiUserOperand can turn into true only when encountering any operand used by multiple users. I cannot see the case where hasMultiUserOperand turn from true to false ? Please let me know if you see such case.

4815

We try to promote sext speculatively which is used in two optimizations : 1) for ExtLoad and 2) address type promotion (initially implemented in aarch64-type-promotion pass) and hasMultiUserOperand is used only for the address type promotion. I think the speculative promotion during the profitability check is just reasonable, and reusing the result of speculative promotions for address type promotion is also reasonable.

I agree that the calculation of hasMultiUserOperand is too far from its use, but I cannot see any other better way of doing this while reusing the result of speculative promotions.

Quentin, do you have any suggestion ?

test/CodeGen/AArch64/arm64-addr-type-promotion.ll

99–100

In this test, I intended to make %add have two users: 1) in %sext1 and 2) in %j.l. In such case, we do not allow moving %sext up through %add.

[eastig]

lib/CodeGen/CodeGenPrepare.cpp

4572–4573

Yes, you are right. It can be changed only from false to true and never back.

test/CodeGen/AArch64/arm64-addr-type-promotion.ll

99–100

I see. Thank you for explanation.

lib/CodeGen/CodeGenPrepare.cpp

private:
     bool optimizeExtractElementInst(Instruction *Inst);
     bool dupRetToEnableTailCallOpts(BasicBlock *BB);
     bool placeDbgValues(Function &F);
     bool canFormExtLd(const SmallVectorImpl<Instruction *> &MovedExts,
                       LoadInst *&LI, Instruction *&Inst, bool HasPromoted);
     bool tryToPromoteExts(TypePromotionTransaction &TPT,
                           const SmallVectorImpl<Instruction *> &Exts,
                           SmallVectorImpl<Instruction *> &ProfitablyMovedExts,
+                          bool *hasMultiUserOperand = nullptr,
                           unsigned CreatedInstsCost = 0);
     bool mergeSExts(Function &F);
     bool performAddressTypePromotion(
         Instruction *&Inst,
         bool AllowPromotionWithoutCommonHeader,
         bool HasPromoted, TypePromotionTransaction &TPT,
         SmallVectorImpl<Instruction *> &SpeculativelyMovedExts);
     bool splitBranchCondition(Function &F);
public:
   /// action to promote the operand of \p Ext instead of using Ext.
   /// \return NULL if no promotable action is possible with the current
   /// sign extension.
   /// \p InsertedInsts keeps track of all the instructions inserted by the
   /// other CodeGenPrepare optimizations. This information is important
   /// because we do not want to promote these instructions as CodeGenPrepare
   /// will reinsert them later. Thus creating an infinite loop: create/remove.
   /// \p PromotedInsts maps the instructions to their type before promotion.
+  /// \p hasMultiUserOperand Set true if we encounter an operand which has
+  /// multiple users.
   static Action getAction(Instruction *Ext, const SetOfInstrs &InsertedInsts,
                           const TargetLowering &TLI,
-                          const InstrToOrigTy &PromotedInsts);
+                          const InstrToOrigTy &PromotedInsts,
+                          bool *hasMultiUserOperand = nullptr);
 };
 
 bool TypePromotionHelper::canGetThrough(const Instruction *Inst,
                                         Type *ConsideredExtType,
                                         const InstrToOrigTy &PromotedInsts,
                                         bool IsSExt) {
   // The promotion helper does not know how to deal with vector types yet.
   // To be able to fix that, we would need to fix the places where we
bool TypePromotionHelper::canGetThrough(const Instruction *Inst,
 
   // #2 check that the truncate just drops extended bits.
   return Inst->getType()->getIntegerBitWidth() >=
          OpndType->getIntegerBitWidth();
 }
 
 TypePromotionHelper::Action TypePromotionHelper::getAction(
     Instruction *Ext, const SetOfInstrs &InsertedInsts,
-    const TargetLowering &TLI, const InstrToOrigTy &PromotedInsts) {
+    const TargetLowering &TLI, const InstrToOrigTy &PromotedInsts,
+    bool *hasMultiUserOperand) {
   assert((isa<SExtInst>(Ext) || isa<ZExtInst>(Ext)) &&
          "Unexpected instruction type");
   Instruction *ExtOpnd = dyn_cast<Instruction>(Ext->getOperand(0));
   Type *ExtTy = Ext->getType();
   bool IsSExt = isa<SExtInst>(Ext);
   // If the operand of the extension is not an instruction, we cannot
   // get through.
   // If it, check we can get through.
TypePromotionHelper::Action TypePromotionHelper::getAction(
   // SExt or Trunc instructions.
   // Return the related handler.
   if (isa<SExtInst>(ExtOpnd) || isa<TruncInst>(ExtOpnd) ||
       isa<ZExtInst>(ExtOpnd))
     return promoteOperandForTruncAndAnyExt;
 
   // Regular instruction.
   // Abort early if we will have to insert non-free instructions.
-  if (!ExtOpnd->hasOneUse() && !TLI.isTruncateFree(ExtTy, ExtOpnd->getType()))
+
+  if (!ExtOpnd->hasOneUse()) {
+    if (hasMultiUserOperand)
+      *hasMultiUserOperand = true;
+    if (!TLI.isTruncateFree(ExtTy, ExtOpnd->getType()))
       return nullptr;
+  }
+
   return IsSExt ? signExtendOperandForOther : zeroExtendOperandForOther;
 }
 
 Value *TypePromotionHelper::promoteOperandForTruncAndAnyExt(
     llvm::Instruction *SExt, TypePromotionTransaction &TPT,
     InstrToOrigTy &PromotedInsts, unsigned &CreatedInstsCost,
     SmallVectorImpl<Instruction *> *Exts,
     SmallVectorImpl<Instruction *> *Truncs, const TargetLowering &TLI) {

 /// profitable. Save extensions profitably moved up, in \p ProfitablyMovedExts.
 /// When some promotion happened, \p TPT contains the proper state to revert
 /// them.
 ///
 /// \return true if some promotion happened, false otherwise.
 bool CodeGenPrepare::tryToPromoteExts(
     TypePromotionTransaction &TPT, const SmallVectorImpl<Instruction *> &Exts,
     SmallVectorImpl<Instruction *> &ProfitablyMovedExts,
-    unsigned CreatedInstsCost) {
+    bool *hasMultiUserOperand, unsigned CreatedInstsCost) {
   bool Promoted = false;
 
   // Iterate over all the extensions to try to promote them.
   for (auto I : Exts) {
     // Early check if we directly have ext(load).
     if (isa<LoadInst>(I->getOperand(0))) {
       ProfitablyMovedExts.push_back(I);
       continue;
     }
 
     // Check whether or not we want to do any promotion.  The reason we have
     // this check inside the for loop is to catch the case where an extension
     // is directly fed by a load because in such case the extension can be moved
     // up without any promotion on its operands.
     if (!TLI || !TLI->enableExtLdPromotion() || DisableExtLdPromotion)
       return false;
 
     // Get the action to perform the promotion.
-    TypePromotionHelper::Action TPH =
-        TypePromotionHelper::getAction(I, InsertedInsts, *TLI, PromotedInsts);
+    TypePromotionHelper::Action TPH = TypePromotionHelper::getAction(
+        I, InsertedInsts, *TLI, PromotedInsts, hasMultiUserOperand);
     // Check if we can promote.
     if (!TPH) {
       // Save the current extension as we cannot move up through its operand.
       ProfitablyMovedExts.push_back(I);
       continue;
     }
 
     // Save the current state.
if (!StressExtLdPromotion &&
       // save the current extension in ProfitablyMovedExts as the latest
       // speculative promotion turned out to be unprofitable.
       TPT.rollback(LastKnownGood);
       ProfitablyMovedExts.push_back(I);
       continue;
     }
     // Continue promoting NewExts as far as doing so is profitable.
     SmallVector<Instruction *, 2> NewlyMovedExts;
-    (void)tryToPromoteExts(TPT, NewExts, NewlyMovedExts, TotalCreatedInstsCost);
+    (void)tryToPromoteExts(TPT, NewExts, NewlyMovedExts, hasMultiUserOperand,
+                           TotalCreatedInstsCost);
     bool NewPromoted = false;
     for (auto ExtInst : NewlyMovedExts) {
       Instruction *MovedExt = cast<Instruction>(ExtInst);
       Value *ExtOperand = MovedExt->getOperand(0);
       // If we have reached to a load, we need this extra profitability check
       // as it could potentially be merged into an ext(load).
       if (isa<LoadInst>(ExtOperand) &&
           !(StressExtLdPromotion || NewCreatedInstsCost <= ExtCost ||
bool CodeGenPrepare::optimizeExt(Instruction *&Inst) {
   bool ATPConsiderable = TTI->shouldConsiderAddressTypePromotion(
       *Inst, AllowPromotionWithoutCommonHeader);
   TypePromotionTransaction TPT(RemovedInsts);
   TypePromotionTransaction::ConstRestorationPt LastKnownGood =
       TPT.getRestorationPoint();
   SmallVector<Instruction *, 1> Exts;
   SmallVector<Instruction *, 2> SpeculativelyMovedExts;
   Exts.push_back(Inst);
-
-  bool HasPromoted = tryToPromoteExts(TPT, Exts, SpeculativelyMovedExts);
+  bool hasMultiUserOperand = false;
+  bool HasPromoted =
+      tryToPromoteExts(TPT, Exts, SpeculativelyMovedExts, &hasMultiUserOperand);
 
   // Look for a load being extended.
   LoadInst *LI = nullptr;
   Instruction *ExtFedByLoad;
 
   // Try to promote a chain of computation if it allows to form an extended
   // load.
   if (canFormExtLd(SpeculativelyMovedExts, LI, ExtFedByLoad, HasPromoted)) {
if (canFormExtLd(SpeculativelyMovedExts, LI, ExtFedByLoad, HasPromoted)) {
     // part of the load. Therefore we conservatively reuse the same debug
     // location for the load and the zext.
     ExtFedByLoad->setDebugLoc(LI->getDebugLoc());
     ++NumExtsMoved;
     Inst = ExtFedByLoad;
     return true;
   }
 
-  // Continue promoting SExts if known as considerable depending on targets.
-  if (ATPConsiderable &&
+  // Continue promoting SExts if known as considerable depending on targets. We
+  // do not allow address type promtion if detecting an instruction which has
+  // multiple users in the middle of promotion. In such case, ISel could lose
+  // opportunities to fold the extension as part of address modes.
+  if (ATPConsiderable && !hasMultiUserOperand &&
       performAddressTypePromotion(Inst, AllowPromotionWithoutCommonHeader,
                                   HasPromoted, TPT, SpeculativelyMovedExts))
     return true;
 
   TPT.rollback(LastKnownGood);
   return false;
 }
 

test/CodeGen/AArch64/arm64-addr-type-promotion.ll

if.then36:                                        ; preds = %if.end25
   %cmp39 = icmp ugt i8 %tmp5, %tmp6
   %conv41 = zext i1 %cmp39 to i8
   br label %return
 
 return:                                           ; preds = %if.then36, %if.end25, %if.then19, %if.then
   %retval.0 = phi i8 [ %conv9, %if.then ], [ %conv24, %if.then19 ], [ %conv41, %if.then36 ], [ 0, %if.end25 ]
   ret i8 %retval.0
 }
+
+%struct.GlobalData = type { [32000 x float], [3 x i32]}
+@global_data = common global %struct.GlobalData zeroinitializer, align 16
+define i32 @multipleUser(i8 %c, i32 %j, float %s)  {
+; CHECK: multipleUser
+; CHECK-NOT: sxtw x{{[0-9]+}}, w{{[0-9]+}}
+; CHECK: str  s{{[0-9]+}}, [x{{[0-9]+}}, w{{[0-9]+}}, sxtw #2]
+entry:
+  %c1 = icmp  eq i8 %c, 0
+  br i1 %c1, label %if.then, label %end
+
+if.then:
+  %add = add nsw i32 %j, 1
+  %sext1 = sext i32 %add to i64
+  %arrayidx = getelementptr inbounds %struct.GlobalData, %struct.GlobalData* @global_data, i64 0, i32 0, i64 %sext1
+  store float %s, float* %arrayidx, align 4
+  br label %end
+
+end:
+  %j.1 = phi i32 [ %add, %if.then ], [ %j, %entry ]
+  ret i32 %j.1
+}