[CodeGenPrep]Restructure promoting Ext to form ExtLoad

[junbuml]

Summary

Instead of just looking for a load which is mergable with Ext to form ExtLoad, trying to promote Exts as long as the cost is acceptable. This change is not a NFC as it continue promoting Exts even after finding a load during promotions; the change in arm64-codegen-prepare-extload.ll described in 2.b might show the case.
This change was motivated from D26524. Based on this change, I will move the transformation performed in aarch64-type-promotion into CGP.

[qcolombet]

Hi Jun,

Just so that I get the idea, when you say:

Based on this change, I will move the transformation performed in aarch64-type-promotion into CGP.

You mean that you are going to add more transformation that will reuse that refactoring, right?

Because as it is, if I understand the code correctly (I haven't finished the review yet), the promotions are gated on forming an extending load, which is probably not what we want on the long run.

Second question, do you have performance number for the current version?

I remember that I settled on only strict improvement in the cost model to stop, i.e., I was not waiting for the cost to become unprofitable, because the cost model was not precise enough and supposedly neutral transformations ended up in regressions.

Cheers,
-Quentin

lib/CodeGen/CodeGenPrepare.cpp

4251

I don't quite get the last sentence.

[junbuml]

You mean that you are going to add more transformation that will reuse that refactoring, right?

Yes, on top of this patch, I'm plaining on moving the transformation done in aarch64-type-promotion into CGP. The main purpose of this patch is to prepare merging the transformation done in aarch64-type-promotion into CGP. And then, I want to implement D26524 in CGP.

Second question, do you have performance number for the current version?

I haven't tried performance with/without the current version (moveExtToFormExtLoad()) itself. I only ran spec2000/spec2006 in aarch64 for this change vs current version, and I didn't see any clear change in performance. I observed +3% in spec2006/astar only when performing the transformation tried in D26524, where I sunk SExt into its user blocks if foldable with its users. Please let me know if you have plan on current version itself.

[qcolombet]

lib/CodeGen/CodeGenPrepare.cpp

4247

[...]save the promoted Ext[...]
You mean save the promoted instructions, right?

4289

"I" is not promoted here, we shouldn't push it.

4296

Shouldn't we keep this check before TypePromotionHelper::getAction?

4324

"I" is not promoted here.

4372

Ditto.

[junbuml]

Addressed Quentin's comments.

lib/CodeGen/CodeGenPrepare.cpp

4247

I meant the last moved extensions which reach to unpromotable point. I use them to find the last Value feeding to an extension after all possible promotions. Renamed "PromotedExts" to "LastMovedExts".

4289

"I" is an extension, which cannot be moved up any more. We need to save it to get the Value feeding to the extension after promotions and to determine if the extension is derived from a load.

4296

Yes, we should check "if (!TLI)" before TypePromotionHelper::getAction().

4324

Looks like the name of "PromotedExts" caused the confusion. I saved an extension in PromotedExts when it reach to an unpromotable/unprofitable point. Added a comment and rename "PromotedExts" to "LastExts".

[junbuml]

Fixed minor bugs.
Based on this change I will submit one more patch to migrate aarch64-address-type promotion pass in CGP soon.

[mcrosier]

I'm still trying to understand the interaction between this patch and D28680. In the mean time I do have one quick comment about an existing bug.

lib/CodeGen/CodeGenPrepare.cpp

4314

You might also write this as

TotalCreatedInstsCost = std::max(0, TotalCreatedInstsCost - ExtCost);

Can you please add a comment as to why we ensure TotalCreatedInstsCost is non-negative? I believe it's because we're passing a signed value to tryToPromoteExts(), which expects an unsigned argument.

Lastly, is this something that could be fixed independently of this patch? And do you have a test case that covers this change?

[junbuml]

lib/CodeGen/CodeGenPrepare.cpp

4314

Yes, the signed value TotalCreatedInstsCost is passed as unsigned argument, the negative value of TotalCreatedInstsCost could mislead the cost model.

Let me separate this as an independent patch with a test case.

[junbuml]

Rebase

[junbuml]

lib/CodeGen/CodeGenPrepare.cpp

4314

This is fixed in rL293307.

[junbuml]

Kindly ping?

[junbuml]

Kindly ping. Please note that this is the first step to move aarch64-type-promotion pass to CGP (https://reviews.llvm.org/D28680). Once we move the aarch64-type-promotion pass to CGP, I want to sink sext when foldable in user GEPs (https://reviews.llvm.org/D28701) which improved 3% in spec2006/astar.

[qcolombet]

Thanks for your patience, I'll try to have a look tomorrow.

[qcolombet]

lib/CodeGen/CodeGenPrepare.cpp

4245–4249

\p ... /p => ... \p
Right?

4282–4283

Shouldn't we continue instead of returning?

4338

I am confused we are checking that we can form an extended load and that is profitable.
The condition shouldn't use the ! operator, right?

4340

I get that this MovedExt is not profitable only if the previous condition is inverted (the ! operator).

4345

If NewPromoted is false, that means that everything is profitable, so we shouldn't rollback and or mark 'I' at the unprofitable point.

That part is somehow consistent with the inverted condition I mentioned, but given I cannot make sense out of that condition, I cannot make sense of that part either :P.

[junbuml]

It seems that my comments and variable names cause some confusions, so updated comments and variable names.

[junbuml]

lib/CodeGen/CodeGenPrepare.cpp

4282–4283

The only 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. For example, in the case below, we can move %s to BB0 even with DisableExtLdPromotion=true or TLI->enableExtLdPromotion()=false since no promotion is required:

BB0:
  %ld = load 
BB1:
  %s  = sext %ld

I cannot see any case where the 2nd element in Exts is detected as a load after we do "continue" for the 1st element in Exts when the if statement (line 4272) is true. For example, in the case below, we cannot even promote %a if DisableExtLdPromotion=true :

BB0:
  %ld = load 
BB1:
  %a = add %ld, 1
  %s  = sext %a

4338

In this function (tryToPromoteExts()), we speculatively promote extensions and save extensions profitably moved up, in ProfitablyMovedExts.

Note that ProfitablyMovedExts contains profitable extensions which is not necessarily fed by a load. To find an extended load, we use canFormExtLd(), which will determine if the final output of ProfitablyMovedExts contains an extension which can be used to form an extendable load.

The final output of ProfitablyMovedExts after recursion will contain the last profitable extensions moved up during the speculative promotion, and it will be used in my second patch (https://reviews.llvm.org/D28680) which moves aarch64-type-promotion pass to CGP

4340

At this point MovedExt is profitable, so save it.

4345

If NewPromoted is false, that means none of speculative promotions for NewExts tried in the recursive call is profitable. So we should rollback and save the current extension (I) as its last profitable extension.

[junbuml]

Kindly ping. Please let me know any comments.

[qcolombet]

Thanks for your patience.

I was on paternity leave and I am trying to catch up now.

Thanks for the clarification, I get the intend now.

lib/CodeGen/CodeGenPrepare.cpp

4282–4283

Good point.
Add a comment about that.

4338

If we record all the extensions that are profitable shouldn't we do:

if (**!**isa<LoadInst>(ExtOperand) **||** !(StressExtLdPromotion || NewCreatedInstsCost <= ExtCost ||
           (ExtOperand->hasOneUse() || hasSameExtUse(ExtOperand, *TLI)))))

I.e., we should invert the first half of the original condition as well.

4345

The code makes sense now, I am still not convince about the initial condition though.
At the very least, that means you need to add comment to explain that part.

[junbuml]

Thanks Quentin for the review and congrats for your new baby.
Added comments in the code and see my inline comments. Please let me know any other question or comment.

Thanks,
Jun

lib/CodeGen/CodeGenPrepare.cpp

4338

Since we record all the extensions that are profitable, we should not "continue" for non-load instructions added in ProfitablyMovedExts line 4324 in it's recursive call. This check should be done for load which is added in line 4275 as it could potentially be merged into an extld. In this change, ProfitablyMovedExts is only used to find an extendable load in canFormExtLd(). Non-load instructions could be promoted in D28680 which migrate aarch64-type-promotion to CGP based on this change.

[qcolombet]

Hi Jun,

I think the new comments make the code more approachable. Thanks again for pushing that through.

LGTM.

Cheers,
-Quentin

lib/CodeGen/CodeGenPrepare.cpp

4335

extra this

>

this extra

4336

The condition makes sense now

[junbuml]

Thank you very much for the review. I will commit it and also rebase D28680 which depend on this change.

lib/CodeGen/CodeGenPrepare.cpp

private:
     bool optimizeLoadExt(LoadInst *I);
     bool optimizeSelectInst(SelectInst *SI);
     bool optimizeShuffleVectorInst(ShuffleVectorInst *SI);
     bool optimizeSwitchInst(SwitchInst *CI);
     bool optimizeExtractElementInst(Instruction *Inst);
     bool dupRetToEnableTailCallOpts(BasicBlock *BB);
     bool placeDbgValues(Function &F);
     bool sinkAndCmp(Function &F);
-    bool extLdPromotion(TypePromotionTransaction &TPT, LoadInst *&LI,
-                        Instruction *&Inst,
+    bool canFormExtLd(const SmallVectorImpl<Instruction *> &MovedExts,
+                      LoadInst *&LI, Instruction *&Inst, bool HasPromoted);
+    bool tryToPromoteExts(TypePromotionTransaction &TPT,
                           const SmallVectorImpl<Instruction *> &Exts,
-                        unsigned CreatedInstCost);
+                          SmallVectorImpl<Instruction *> &ProfitablyMovedExts,
+                          unsigned CreatedInstsCost = 0);
     bool splitBranchCondition(Function &F);
     bool simplifyOffsetableRelocate(Instruction &I);
   };
 }
 
 char CodeGenPrepare::ID = 0;
 INITIALIZE_TM_PASS_BEGIN(CodeGenPrepare, "codegenprepare",
                          "Optimize for code generation", false, false)
if (OpInfo.ConstraintType == TargetLowering::C_Memory &&
       MadeChange |= optimizeMemoryInst(CS, OpVal, OpVal->getType(), ~0u);
     } else if (OpInfo.Type == InlineAsm::isInput)
       ArgNo++;
   }
 
   return MadeChange;
 }
 
-/// \brief Check if all the uses of \p Inst are equivalent (or free) zero or
+/// \brief Check if all the uses of \p Val are equivalent (or free) zero or
 /// sign extensions.
-static bool hasSameExtUse(Instruction *Inst, const TargetLowering &TLI) {
-  assert(!Inst->use_empty() && "Input must have at least one use");
-  const Instruction *FirstUser = cast<Instruction>(*Inst->user_begin());
+static bool hasSameExtUse(Value *Val, const TargetLowering &TLI) {
+  assert(!Val->use_empty() && "Input must have at least one use");
+  const Instruction *FirstUser = cast<Instruction>(*Val->user_begin());
   bool IsSExt = isa<SExtInst>(FirstUser);
   Type *ExtTy = FirstUser->getType();
-  for (const User *U : Inst->users()) {
+  for (const User *U : Val->users()) {
     const Instruction *UI = cast<Instruction>(U);
     if ((IsSExt && !isa<SExtInst>(UI)) || (!IsSExt && !isa<ZExtInst>(UI)))
       return false;
     Type *CurTy = UI->getType();
     // Same input and output types: Same instruction after CSE.
     if (CurTy == ExtTy)
       continue;
 
     // If IsSExt is true, we are in this situation:
-    // a = Inst
+    // a = Val
     // b = sext ty1 a to ty2
     // c = sext ty1 a to ty3
     // Assuming ty2 is shorter than ty3, this could be turned into:
-    // a = Inst
+    // a = Val
     // b = sext ty1 a to ty2
     // c = sext ty2 b to ty3
     // However, the last sext is not free.
     if (IsSExt)
       return false;
 
     // This is a ZExt, maybe this is free to extend from one type to another.
     // In that case, we would not account for a different use.
for (const User *U : Val->users()) {
 
     if (!TLI.isZExtFree(NarrowTy, LargeTy))
       return false;
   }
   // All uses are the same or can be derived from one another for free.
   return true;
 }
 
-/// \brief Try to form ExtLd by promoting \p Exts until they reach a
-/// load instruction.
-/// If an ext(load) can be formed, it is returned via \p LI for the load
-/// and \p Inst for the extension.
-/// Otherwise LI == nullptr and Inst == nullptr.
-/// When some promotion happened, \p TPT contains the proper state to
-/// revert them.
+/// \brief Try to speculatively promote extensions in \p Exts and continue
+/// promoting through newly promoted operands recursively as far as doing so is
+/// profitable. Save extensions profitably moved up, in \p ProfitablyMovedExts.
+/// When some promotion happened, \p TPT contains the proper state to revert
+/// them.
 ///
-/// \return true when promoting was necessary to expose the ext(load)
-/// opportunity, false otherwise.
+/// \return true if some promotion happened, false otherwise.
 ///
 /// Example:
 /// \code
 /// %ld = load i32* %addr
 /// %add = add nuw i32 %ld, 4
 /// %zext = zext i32 %add to i64
 /// \endcode
 /// =>
 /// \code
 /// %ld = load i32* %addr
 /// %zext = zext i32 %ld to i64
 /// %add = add nuw i64 %zext, 4
 /// \endcode
 /// Thanks to the promotion, we can match zext(load i32*) to i64.
-bool CodeGenPrepare::extLdPromotion(TypePromotionTransaction &TPT,
-                                    LoadInst *&LI, Instruction *&Inst,
-                                    const SmallVectorImpl<Instruction *> &Exts,
-                                    unsigned CreatedInstsCost = 0) {
-  // Iterate over all the extensions to see if one form an ext(load).
+bool CodeGenPrepare::tryToPromoteExts(
+    TypePromotionTransaction &TPT, const SmallVectorImpl<Instruction *> &Exts,
+    SmallVectorImpl<Instruction *> &ProfitablyMovedExts,
+    unsigned CreatedInstsCost) {
+  bool Promoted = false;
+
+  // Iterate over all the extensions to try to promote them.
   for (auto I : Exts) {
-    // Check if we directly have ext(load).
-    if ((LI = dyn_cast<LoadInst>(I->getOperand(0)))) {
-      Inst = I;
-      // No promotion happened here.
-      return false;
+    // 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.
     if (!TLI || !TLI->enableExtLdPromotion() || DisableExtLdPromotion)
-      continue;
+      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);
     // Check if we can promote.
-    if (!TPH)
+    if (!TPH) {
+      // Save the current extension as we cannot move up through its operand.
+      ProfitablyMovedExts.push_back(I);
       continue;
+    }
+
     // Save the current state.
     TypePromotionTransaction::ConstRestorationPt LastKnownGood =
         TPT.getRestorationPoint();
     SmallVector<Instruction *, 4> NewExts;
     unsigned NewCreatedInstsCost = 0;
     unsigned ExtCost = !TLI->isExtFree(I);
     // Promote.
     Value *PromotedVal = TPH(I, TPT, PromotedInsts, NewCreatedInstsCost,
                              &NewExts, nullptr, *TLI);
     assert(PromotedVal &&
            "TypePromotionHelper should have filtered out those cases");
 
     // We would be able to merge only one extension in a load.
     // Therefore, if we have more than 1 new extension we heuristically
     // cut this search path, because it means we degrade the code quality.
     // With exactly 2, the transformation is neutral, because we will merge
     // one extension but leave one. However, we optimistically keep going,
     // because the new extension may be removed too.
     long long TotalCreatedInstsCost = CreatedInstsCost + NewCreatedInstsCost;
     // FIXME: It would be possible to propagate a negative value instead of
     // conservatively ceiling it to 0. 
     TotalCreatedInstsCost =
         std::max((long long)0, (TotalCreatedInstsCost - ExtCost));
     if (!StressExtLdPromotion &&
         (TotalCreatedInstsCost > 1 ||
          !isPromotedInstructionLegal(*TLI, *DL, PromotedVal))) {
-      // The promotion is not profitable, rollback to the previous state.
+      // This promotion is not profitable, rollback to the previous state, and
+      // save the current extension in ProfitablyMovedExts as the latest
+      // speculative promotion turned out to be unprofitable.
       TPT.rollback(LastKnownGood);
+      ProfitablyMovedExts.push_back(I);
       continue;
     }
-    // The promotion is profitable.
-    // Check if it exposes an ext(load).
-    (void)extLdPromotion(TPT, LI, Inst, NewExts, TotalCreatedInstsCost);
-    if (LI && (StressExtLdPromotion || NewCreatedInstsCost <= ExtCost ||
-               // If we have created a new extension, i.e., now we have two
-               // extensions. We must make sure one of them is merged with
-               // the load, otherwise we may degrade the code quality.
-               (LI->hasOneUse() || hasSameExtUse(LI, *TLI))))
-      // Promotion happened.
-      return true;
-    // If this does not help to expose an ext(load) then, rollback.
+    // Continue promoting NewExts as far as doing so is profitable.
+    SmallVector<Instruction *, 2> NewlyMovedExts;
+    (void)tryToPromoteExts(TPT, NewExts, NewlyMovedExts,
+                           TotalCreatedInstsCost);
+    bool NewPromoted = false;
+    for (auto ExtInst : NewlyMovedExts) {
+      Instruction *MovedExt = cast<Instruction>(ExtInst);
+      Value *ExtOperand = MovedExt->getOperand(0);
+      if (isa<LoadInst>(ExtOperand) &&
+          !(StressExtLdPromotion || NewCreatedInstsCost <= ExtCost ||
+           (ExtOperand->hasOneUse() || hasSameExtUse(ExtOperand, *TLI))))
+        continue;
+
+      ProfitablyMovedExts.push_back(MovedExt);
+      NewPromoted = true;
+    }
+
+    // If none of speculative promotions for NewExts is profitable, rollback
+    // and save the current extension (I) as the last profitable extension.
+    if (!NewPromoted) {
       TPT.rollback(LastKnownGood);
+      ProfitablyMovedExts.push_back(I);
+      continue;
+    }
+    // The promotion is profitable.
+    Promoted = true;
   }
-  // None of the extension can form an ext(load).
-  LI = nullptr;
-  Inst = nullptr;
+  return Promoted;
+}
+
+/// Return true, if an ext(load) can be formed from an extension in
+/// \p MovedExts.
+bool CodeGenPrepare::canFormExtLd(
+    const SmallVectorImpl<Instruction *> &MovedExts, LoadInst *&LI,
+    Instruction *&Inst, bool HasPromoted) {
+  for (auto *MovedExtInst : MovedExts) {
+    if (isa<LoadInst>(MovedExtInst->getOperand(0))) {
+      LI = cast<LoadInst>(MovedExtInst->getOperand(0));
+      Inst = MovedExtInst;
+      break;
+    }
+  }
+  if (!LI)
+    return false;
+
+  // If they're already in the same block, there's nothing to do.
+  // Make the cheap checks first if we did not promote.
+  // If we promoted, we need to check if it is indeed profitable.
+  if (!HasPromoted && LI->getParent() == Inst->getParent())
+    return false;
+
+  EVT VT = TLI->getValueType(*DL, Inst->getType());
+  EVT LoadVT = TLI->getValueType(*DL, LI->getType());
+
+  // If the load has other users and the truncate is not free, this probably
+  // isn't worthwhile.
+  if (!LI->hasOneUse() && (TLI->isTypeLegal(LoadVT) || !TLI->isTypeLegal(VT)) &&
+      !TLI->isTruncateFree(Inst->getType(), LI->getType()))
     return false;
+
+  // Check whether the target supports casts folded into loads.
+  unsigned LType;
+  if (isa<ZExtInst>(Inst))
+    LType = ISD::ZEXTLOAD;
+  else {
+    assert(isa<SExtInst>(Inst) && "Unexpected ext type!");
+    LType = ISD::SEXTLOAD;
+  }
+
+  return TLI->isLoadExtLegal(LType, VT, LoadVT);
 }
 
 /// Move a zext or sext fed by a load into the same basic block as the load,
 /// unless conditions are unfavorable. This allows SelectionDAG to fold the
 /// extend into the load.
 /// \p I[in/out] the extension may be modified during the process if some
 /// promotions apply.
 ///
 bool CodeGenPrepare::moveExtToFormExtLoad(Instruction *&I) {
   // ExtLoad formation infrastructure requires TLI to be effective.
-  if (!TLI)
     return false;
 
   // Try to promote a chain of computation if it allows to form
   // an extended load.
   TypePromotionTransaction TPT;
   TypePromotionTransaction::ConstRestorationPt LastKnownGood =
       TPT.getRestorationPoint();
   SmallVector<Instruction *, 1> Exts;
+ SmallVector<Instruction *, 2> LastMovedExts;
   Exts.push_back(I);
+
+  bool HasPromoted = tryToPromoteExts(TPT, Exts, LastMovedExts);
+
   // Look for a load being extended.
   LoadInst *LI = nullptr;
   Instruction *OldExt = I;
-  bool HasPromoted = extLdPromotion(TPT, LI, I, Exts);
-  if (!LI || !I) {
-    assert(!HasPromoted && !LI && "If we did not match any load instruction "
-                                  "the code must remain the same");
-    I = OldExt;
-    return false;
-  }
-
-  // If they're already in the same block, there's nothing to do.
-  // Make the cheap checks first if we did not promote.
-  // If we promoted, we need to check if it is indeed profitable.
-  if (!HasPromoted && LI->getParent() == I->getParent())
-    return false;
-
-  EVT VT = TLI->getValueType(*DL, I->getType());
-  EVT LoadVT = TLI->getValueType(*DL, LI->getType());
-
-  // If the load has other users and the truncate is not free, this probably
-  // isn't worthwhile.
-  if (!LI->hasOneUse() &&
-      (TLI->isTypeLegal(LoadVT) || !TLI->isTypeLegal(VT)) &&
-      !TLI->isTruncateFree(I->getType(), LI->getType())) {
-    I = OldExt;
-    TPT.rollback(LastKnownGood);
-    return false;
-  }
-
-  // Check whether the target supports casts folded into loads.
-  unsigned LType;
-  if (isa<ZExtInst>(I))
-    LType = ISD::ZEXTLOAD;
-  else {
-    assert(isa<SExtInst>(I) && "Unexpected ext type!");
-    LType = ISD::SEXTLOAD;
-  }
-  if (!TLI->isLoadExtLegal(LType, VT, LoadVT)) {
+  if (!canFormExtLd(LastMovedExts, LI, I, HasPromoted)) {
     I = OldExt;
     TPT.rollback(LastKnownGood);
     return false;
   }
 
   // Move the extend into the same block as the load, so that SelectionDAG
   // can fold it.
   TPT.commit();
   I->removeFromParent();
   I->insertAfter(LI);
   // CGP does not check if the zext would be speculatively executed when moved
   // to the same basic block as the load. Preserving its original location would
-  // pessimize the debugging experience, as well as negatively impact the 
+  // pessimize the debugging experience, as well as negatively impact the
   // quality of sample pgo. We don't want to use "line 0" as that has a
   // size cost in the line-table section and logically the zext can be seen as
   // part of the load. Therefore we conservatively reuse the same debug location
   // for the load and the zext.
   I->setDebugLoc(LI->getDebugLoc());
   ++NumExtsMoved;
   return true;
 }

test/CodeGen/AArch64/arm64-codegen-prepare-extload.ll

 ; Here is what is happening in this test (not necessarly in this order):
 ; 1. We try to promote the operand of %sextadd.
 ;    a. This creates one sext of %ld2 and one of %zextld
 ;    b. The sext of %ld2 can be combine with %ld2, so we remove one sext but
 ;       introduced one. This is fine with the current heuristic: neutral.
 ;    => We have one zext of %zextld left and we created one sext of %ld2.
 ; 2. We try to promote the operand of %sextaddza.
 ;    a. This creates one sext of %zexta and one of %zextld
-;    b. The sext of %zexta does not lead to any load, it stays here, even if it
-;       could have been combine with the zext of %a.
+;    b. The sext of %zexta can be combined with the zext of %a.
 ;    c. The sext of %zextld leads to %ld and can be combined with it. This is
 ;       done by promoting %zextld. This is fine with the current heuristic:
 ;       neutral.
 ;    => We have created a new zext of %ld and we created one sext of %zexta.
 ; 3. We try to promote the operand of %sextaddb.
 ;    a. This creates one sext of %b and one of %zextld
 ;    b. The sext of %b is a dead-end, nothing to be done.
 ;    c. Same thing as 2.c. happens.
 ;    => We have created a new zext of %ld and we created one sext of %b.
 ; 4. We try to promote the operand of the zext of %zextld introduced in #1.
 ;    a. Same thing as 2.c. happens.
 ;    b. %zextld does not have any other uses. It is dead coded.
 ;    => We have created a new zext of %ld and we removed a zext of %zextld and
 ;       a zext of %ld.
 ; Currently we do not try to reuse existing extensions, so in the end we have
 ; 3 identical zext of %ld. The extensions will be CSE'ed by SDag.
 ;
 ; OPTALL-LABEL: @severalPromotions
 ; OPTALL: [[LD:%[a-zA-Z_0-9-]+]] = load i8, i8* %addr1
 ; OPT-NEXT: [[ZEXTLD1_1:%[a-zA-Z_0-9-]+]] = zext i8 [[LD]] to i64
 ; OPT-NEXT: [[ZEXTLD1_2:%[a-zA-Z_0-9-]+]] = zext i8 [[LD]] to i64
-; OPT-NEXT: [[ZEXTLD1_3:%[a-zA-Z_0-9-]+]] = zext i8 [[LD]] to i64
 ; OPT-NEXT: [[LD2:%[a-zA-Z_0-9-]+]] = load i32, i32* %addr2
 ; OPT-NEXT: [[SEXTLD2:%[a-zA-Z_0-9-]+]] = sext i32 [[LD2]] to i64
-; OPT-NEXT: [[RES:%[a-zA-Z_0-9-]+]] = add nsw i64 [[SEXTLD2]], [[ZEXTLD1_1]]
-; We do not combine this one: see 2.b.
-; OPT-NEXT: [[ZEXTA:%[a-zA-Z_0-9-]+]] = zext i8 %a to i32
-; OPT-NEXT: [[SEXTZEXTA:%[a-zA-Z_0-9-]+]] = sext i32 [[ZEXTA]] to i64
-; OPT-NEXT: [[RESZA:%[a-zA-Z_0-9-]+]] = add nsw i64 [[SEXTZEXTA]], [[ZEXTLD1_3]]
+; OPT-NEXT: [[ZEXTLD1_3:%[a-zA-Z_0-9-]+]] = zext i8 [[LD]] to i64
+; OPT-NEXT: [[RES:%[a-zA-Z_0-9-]+]] = add nsw i64 [[SEXTLD2]], [[ZEXTLD1_3]]
+; OPT-NEXT: [[ZEXTLD1_4:%[a-zA-Z_0-9-]+]] = zext i8 %a to i64
+; OPT-NEXT: [[RESZA:%[a-zA-Z_0-9-]+]] = add nsw i64 [[ZEXTLD1_4]], [[ZEXTLD1_2]]
 ; OPT-NEXT: [[SEXTB:%[a-zA-Z_0-9-]+]] = sext i32 %b to i64
-; OPT-NEXT: [[RESB:%[a-zA-Z_0-9-]+]] = add nsw i64 [[SEXTB]], [[ZEXTLD1_2]]
+; OPT-NEXT: [[RESB:%[a-zA-Z_0-9-]+]] = add nsw i64 [[SEXTB]], [[ZEXTLD1_1]]
 ;
 ; DISABLE: [[ADD:%[a-zA-Z_0-9-]+]] = add nsw i32
 ; DISABLE: [[RES:%[a-zA-Z_0-9-]+]]  = sext i32 [[ADD]] to i64
 ; DISABLE: [[ADDZA:%[a-zA-Z_0-9-]+]] = add nsw i32
 ; DISABLE: [[RESZA:%[a-zA-Z_0-9-]+]]  = sext i32 [[ADDZA]] to i64
 ; DISABLE: [[ADDB:%[a-zA-Z_0-9-]+]] = add nsw i32
 ; DISABLE: [[RESB:%[a-zA-Z_0-9-]+]]  = sext i32 [[ADDB]] to i64
 ;

test/CodeGen/X86/codegen-prepare-extload.ll

 ; Here is what is happening in this test (not necessarly in this order):
 ; 1. We try to promote the operand of %sextadd.
 ;    a. This creates one sext of %ld2 and one of %zextld
 ;    b. The sext of %ld2 can be combine with %ld2, so we remove one sext but
 ;       introduced one. This is fine with the current heuristic: neutral.
 ;    => We have one zext of %zextld left and we created one sext of %ld2.
 ; 2. We try to promote the operand of %sextaddza.
 ;    a. This creates one sext of %zexta and one of %zextld
-;    b. The sext of %zexta does not lead to any load, it stays here, even if it
-;       could have been combine with the zext of %a.
+;    b. The sext of %zexta can be combined with the zext of %a.
 ;    c. The sext of %zextld leads to %ld and can be combined with it. This is
 ;       done by promoting %zextld. This is fine with the current heuristic:
 ;       neutral.
 ;    => We have created a new zext of %ld and we created one sext of %zexta.
 ; 3. We try to promote the operand of %sextaddb.
 ;    a. This creates one sext of %b and one of %zextld
 ;    b. The sext of %b is a dead-end, nothing to be done.
 ;    c. Same thing as 2.c. happens.
 ;    => We have created a new zext of %ld and we created one sext of %b.
 ; 4. We try to promote the operand of the zext of %zextld introduced in #1.
 ;    a. Same thing as 2.c. happens.
 ;    b. %zextld does not have any other uses. It is dead coded.
 ;    => We have created a new zext of %ld and we removed a zext of %zextld and
 ;       a zext of %ld.
 ; Currently we do not try to reuse existing extensions, so in the end we have
 ; 3 identical zext of %ld. The extensions will be CSE'ed by SDag.
 ;
 ; OPTALL-LABEL: @severalPromotions
 ; OPTALL: [[LD:%[a-zA-Z_0-9-]+]] = load i8, i8* %addr1
 ; OPT-NEXT: [[ZEXTLD1_1:%[a-zA-Z_0-9-]+]] = zext i8 [[LD]] to i64
 ; OPT-NEXT: [[ZEXTLD1_2:%[a-zA-Z_0-9-]+]] = zext i8 [[LD]] to i64
-; OPT-NEXT: [[ZEXTLD1_3:%[a-zA-Z_0-9-]+]] = zext i8 [[LD]] to i64
 ; OPT-NEXT: [[LD2:%[a-zA-Z_0-9-]+]] = load i32, i32* %addr2
 ; OPT-NEXT: [[SEXTLD2:%[a-zA-Z_0-9-]+]] = sext i32 [[LD2]] to i64
-; OPT-NEXT: [[RES:%[a-zA-Z_0-9-]+]] = add nsw i64 [[SEXTLD2]], [[ZEXTLD1_1]]
-; We do not combine this one: see 2.b.
-; OPT-NEXT: [[ZEXTA:%[a-zA-Z_0-9-]+]] = zext i8 %a to i32
-; OPT-NEXT: [[SEXTZEXTA:%[a-zA-Z_0-9-]+]] = sext i32 [[ZEXTA]] to i64
-; OPT-NEXT: [[RESZA:%[a-zA-Z_0-9-]+]] = add nsw i64 [[SEXTZEXTA]], [[ZEXTLD1_3]]
+; OPT-NEXT: [[ZEXTLD1_3:%[a-zA-Z_0-9-]+]] = zext i8 [[LD]] to i64
+; OPT-NEXT: [[RES:%[a-zA-Z_0-9-]+]] = add nsw i64 [[SEXTLD2]], [[ZEXTLD1_3]]
+; OPT-NEXT: [[ZEXTLD1_4:%[a-zA-Z_0-9-]+]] = zext i8 %a to i64
+; OPT-NEXT: [[RESZA:%[a-zA-Z_0-9-]+]] = add nsw i64 [[ZEXTLD1_4]], [[ZEXTLD1_2]]
 ; OPT-NEXT: [[SEXTB:%[a-zA-Z_0-9-]+]] = sext i32 %b to i64
-; OPT-NEXT: [[RESB:%[a-zA-Z_0-9-]+]] = add nsw i64 [[SEXTB]], [[ZEXTLD1_2]]
+; OPT-NEXT: [[RESB:%[a-zA-Z_0-9-]+]] = add nsw i64 [[SEXTB]], [[ZEXTLD1_1]]
 ;
 ; DISABLE: [[ADD:%[a-zA-Z_0-9-]+]] = add nsw i32
 ; DISABLE: [[RES:%[a-zA-Z_0-9-]+]]  = sext i32 [[ADD]] to i64
 ; DISABLE: [[ADDZA:%[a-zA-Z_0-9-]+]] = add nsw i32
 ; DISABLE: [[RESZA:%[a-zA-Z_0-9-]+]]  = sext i32 [[ADDZA]] to i64
 ; DISABLE: [[ADDB:%[a-zA-Z_0-9-]+]] = add nsw i32
 ; DISABLE: [[RESB:%[a-zA-Z_0-9-]+]]  = sext i32 [[ADDB]] to i64
 ;