[Loop Vectorizer] Support predication of div/rem

[gilr]

Summary

div/rem instructions in basic blocks that require predication currently prevent vectorization. This patch extends the existing mechanism for predicating stores to handle other instructions and leverages it to predicate divs and rems.

The generated vector extracts and inserts are now moved into the predicated block (reflected in the cost model for scalarization).

[anemet]

lib/Transforms/Vectorize/LoopVectorize.cpp

3825–3834

Only a drive-by comment, please don't make vectorizeLoop any more unreadable than it already is. Please consider prequel to this patch that moves store-predication into its own function.

[eli.friedman]

You might want to consider special-casing division by a constant integer. For example, on x86, we can convert a 16-bit unsigned divide by a constant into a pmulhuw+psrlw.

[mkuper]

lib/Transforms/Vectorize/LoopVectorize.cpp

3327

I'm not entirely sure what "the cost of a phi" means, especially without a type.

Also, I don't believe any in-tree target actually assigns a non-zero to PHIs right now. So if you actually want a meaningful cost here for, say, x86, you may want to look into the cost model as well...

3825

...that need predication?
(Before, we really would predicate *any* store)

3825–3834

+1

3833

We don't run anything that will sink this later in the pipeline?
(To be honest, even if we do, I'm not sure whether we should do the cleanup here or rely on a later pass, but I'm curious)

3835

Any reason not to use a range for over the operands?

3841

Do you know if we have an isOnlyUserOf helper?
I know we have one for SDNode... but, I couldn't find one in IR.

3859

I->hasOneUse()? Or do you care specifically about the users() list? In any case, no need to compute std::distance.

3860

I->user_begin()?

4251

FRem looks out of place. Did you mean URem?

4254

To expand on what Eli said, if we have division by a non-zero constant, then:

1. It may be efficiently lowered.
2. Since the constant is non-zero, it doesn't need predication.

4264

And, correspondingly, this should probably be FRem.

5070

As long as you're touching this - remove this comment?

[gilr]

lib/Transforms/Vectorize/LoopVectorize.cpp

3327

So IIRC I took it from CostModelAnalysis::getInstructionCost(), but I'll remove it if it makes no sense.

3833

Actually the vectorizer currently seems to expect inst-combine to do so (see the deleted VEC-IC case in if-pred-stores.ll), but IINM the cost model didn't reflect that.
I agree, there's the general issue of generating efficient code here vs relying on later passes to clean up, which I think this was also brought up here.

3835

No, will fix.

3841

Me either - anyone?

3859

Right, will fix.

3860

Right, will fix.

4251

Yes.

4264

Indeed.

[mkuper]

lib/Transforms/Vectorize/LoopVectorize.cpp

3327

I'm not sure what makes sense here, to be honest.
What cost, in the final generated code, are you trying to account for? An extra register copy?

4251

Too bad there wasn't a test that would have failed because of this. ;-)

[gilr]

Implemented several reviewer comments, notably avoiding predication when dividing by a non-zero constant.

[gilr]

Added may-divide-by-zero logic to cost model (was missing in previous patch); moved logic to its own helper function.

[anemet]

More drive-by comments.

lib/Transforms/Vectorize/LoopVectorize.cpp

3831–3840

Would be good to describe the high-level strategy of how we predicate these instruction, perhaps with an IR example.

3850–3851

I think that Twine knows how to concatenate string-like things. You only need the explicit ctor on the first one.

test/Transforms/LoopVectorize/if-pred-non-void.ll

19–52

I *think* we're pretty consistent about using uppercase for the named regexes. That helps readability.

[gilr]

lib/Transforms/Vectorize/LoopVectorize.cpp

3327

I actually wasn't trying to model any specific cost in the generated code, just trying to be consistent about accounting for every generated instruction at IR level (and letting TTI decide their cost).
So if PHIs have zero cost by definition/convention and should not be taken into account in cost models then I should just remove this. Otherwise, placing the call now makes sure we don't miss that cost if targets start modelling it. What say you?

3850–3851

Right, will fix.

[mkuper]

lib/Transforms/Vectorize/LoopVectorize.cpp

3327

We're not even consistent about it in our different cost models - CostModelAnalysis::getInstructionCost() calls getCFInstrCost(), while (the admittedly, old) BBVectorizer cost model just reutrns 0.
But I get what you're saying. If you prefer to leave it, leave it, but I think it'd be nice to document the fact you don't currently expect a real cost here.

[gilr]

• Merged with prequel patch r277595 (D23013).
• Changed named registers in new lit test to uppercase.
• Documented predication logic
• Removed unnecessary Twine ctor calls.

[mkuper]

LGTM, but please wait a bit for anemet, in case he also wants to review this in non-drive-by-mode. :-)

[anemet]

lib/Transforms/Vectorize/LoopVectorize.cpp

3313–3314

There is something wrong with this sentence.

3316

Predicate->Predicated

Same in the other functions.

3344–3345

Explain in the comment how this guys is different from the previous one.

3359–3360

Same here.

3361

Type* -> Type *

Did you run clang-format on the diff?

4049

auto *

4052–4059

Is this any different than OpInst->hasOneUse?

4079–4082

Is there a test for the non-insertelt case?

4082

Why is the undef correct here?

4241

auto *

[gilr]

lib/Transforms/Vectorize/LoopVectorize.cpp

4052–4059

Yes, for Instructions that use the same value more than once (see Michael's comment).

4079–4082

No. We currently always create an insertelement on scalarization. I added support for the non-insertelement case for completeness, since predication is done separately from scalarization.
IIUC this case will need to be supported if & when Matthew's patch is committed, but for now it's really FFU.
I'll replace this case with an assertion for this patch and leave it to Matthew to resurrect in his patch as needed.

4082

We are re-introducing the original scalar conditional execution of an instruction here. This undef can reach either

• a select that will blend it out, or
• a Use dominated by this instruction's BB that is either
  • predicated by (at least) the same predicate, which won't use the undef, or
  • not predicated due to no side effects, where undef would be safe

[mssimpso]

lib/Transforms/Vectorize/LoopVectorize.cpp

4079–4082

Gil,

For the non-insert cases that might arise with my patch, I think it would be better to leave the case here (don't add an assert), but include a test with this patch that would break with the other patch. Does that make sense? That will keep the patches better self-contained and prevent us from having to revisit this.

You will need a test where the div only feeds an instruction that will also be scalar (like a GEP). If this patch lands before the other one, it will be cleaner if in the other we just have to change the test. Presumably, that would involve replacing the PHI for the inserts with a PHI for the predicated instruction, since the inserts will no longer be there? If the other patch lands first, there will be no issue since you'll already have a test for the non-insert case.

[Ayal]

lib/Transforms/Vectorize/LoopVectorize.cpp

3328–3329

Suggest to first add the cost of the InsertElement and then the (optional) cost of the Phi, just to keep things in the same order they will be executed. Furthermore, cost if Extract should precede that of Insert.

4240–4241

Suggest to rename Op2 to Divisor.

It may be worthwhile to generalize and check isKnownNonZero(). Non-zero divisors that are not compile-time constants will not be converted into multiplication, so we will still end up scalarizing the division, but can do so w/o predication.

[mssimpso]

Also, store predication is currently behind a flag that defaults to false (-enable-cond-stores-vec). Since you're reusing the store predication logic, I'm wondering if the mayDivideByZero cases should be under the flag as well. What do you think?

Matt.

[mkuper]

In D22918#511194, @mssimpso wrote:

Also, store predication is currently behind a flag that defaults to false (-enable-cond-stores-vec). Since you're reusing the store predication logic, I'm wondering if the mayDivideByZero cases should be under the flag as well. What do you think?

Matt.

The reason enable-cond-stores-vec defaults to false is the lack of cost modeling for predicated stores.
The change to getScalarizationOverhead() is supposed to solve this for divs. But I guess it depends on the real-world performance impact this patch has.

[gilr]

• Per Matt's comment: code continues to support the non-insertelement case; added an FFU test that should fail once the vectorizer supports direct scalar-scalar use.
• Implemented (hopefully) all other review comments
• Ran clang-format again

[mssimpso]

test/Transforms/LoopVectorize/if-pred-non-void.ll

137–139

Thanks for adding the additional "future" test. I don't think it will exercise the non-insert case, though. I'm very sorry for not being more clear previously. Here, %rsd will always have to be inserted into a vector since it will be directly used by a select instruction, which will remain vectorized. I didn't think of this when I last commented. But I think if you add an additional instruction, this should produce the desired effect. Something like:

if.then:
  %tmp = sdiv i32 %psd, %lsd
  %rsd = sdiv i32 %tmp, %lsd
  br label %if.end

When I ran the modified test with this patch and the scalar patch, the non-insert case was used for %tmp and the insert case was used for %rsd. This makes sense becase %tmp is only used by %rsd (will be scalar), and %rsd will again feed the vector select.

[gilr]

test/Transforms/LoopVectorize/if-pred-non-void.ll

137–139

Argh, sorry about that. Your explanation was clear - just a hasty implementation on my side :(
Yes, the second sdiv should go under the same condition - will fix.

[gilr]

Fixed FFU test case.

[mssimpso]

test/Transforms/LoopVectorize/if-pred-non-void.ll

138–140

The test looks good to me now. Thanks!

[gilr]

Adam,

Do you have any other comments? Am I good to go with this change?
Thanks!

[anemet]

Gil, I will look at this today.

[anemet]

lib/Transforms/Vectorize/LoopVectorize.cpp

4049–4075

I would also include the select instruction in this excerpt (omitting anything in between with a ...). Then you can explain in the initial comment that the value produced on the false branch is not used (the conditional execution is only reintroduced to avoid side-effects).

4052–4059

OK, is this difference relevant? If yes, add a helper either in this module or at a more global place and use it.

You can probably also writes this with std::all_of or something.

4055

"So for the first element of a scalarized instruction, e.g."

4082

We are re-introducing the original scalar conditional execution of an instruction here. This undef can reach either

Makes sense but we need a comment for this. I think the best is to explain this on the excerpt at the beginning, see my comment there.

test/Transforms/LoopVectorize/if-pred-non-void.ll

9–10

As a demo for how this works it would be actually good to include at least one of the second element sequences as well.

21–22

Can you please name and match this extract as well, it helps reading. Everywhere in these tests.

23–24

It would be also good to check the extractelements feeding the divs here.

[gilr]

lib/Transforms/Vectorize/LoopVectorize.cpp

4052–4059

It shouldn't make a difference for the currently predicated instructions. I'll replace with hasOneUse with a comment to capture the possible (conservative) inaccuracy.

[gilr]

Implemented Adam's comments.

[gilr]

Ping

[anemet]

LGTM too with the comments addressed below. Thanks!

lib/Transforms/Vectorize/LoopVectorize.cpp

4058

Please remove the '; pred =' comments

You may want to add a

// ...

after the for.body: label in all these loops. That is where the div operand would be loaded, etc.

4070

s/selected-out/if-converted using a select/

4080–4081

%33 and %34 are not used, please remove

lib/Transforms/Vectorize/LoopVectorize.cpp

protected:
   void widenPHIInstruction(Instruction *PN, VectorParts &Entry, unsigned UF,
                            unsigned VF, PhiVector *PV);
 
   /// Insert the new loop to the loop hierarchy and pass manager
   /// and update the analysis passes.
   void updateAnalysis();
 
   /// This instruction is un-vectorizable. Implement it as a sequence
-  /// of scalars. If \p IfPredicateStore is true we need to 'hide' each
+  /// of scalars. If \p IfPredicateInstr is true we need to 'hide' each
   /// scalarized instruction behind an if block predicated on the control
   /// dependence of the instruction.
   virtual void scalarizeInstruction(Instruction *Instr,
-                                    bool IfPredicateStore = false);
+                                    bool IfPredicateInstr = false);
 
   /// Vectorize Load and Store instructions,
   virtual void vectorizeMemoryInstruction(Instruction *Instr);
 
   /// Create a broadcast instruction. This method generates a broadcast
   /// instruction (shuffle) for loop invariant values and for the induction
   /// value. If this is the induction variable then we extend it to N, N+1, ...
   /// this is needed because each iteration in the loop corresponds to a SIMD
protected:
   /// ScalarIVMap maps induction variables from the original loop that are not
   /// vectorized to their scalar equivalents in the vector loop. Maintaining a
   /// separate map for scalarized induction variables allows us to avoid
   /// unnecessary scalar-to-vector-to-scalar conversions.
   DenseMap<Value *, SmallVector<Value *, 8>> ScalarIVMap;
 
   /// Store instructions that should be predicated, as a pair
   ///   <StoreInst, Predicate>
-  SmallVector<std::pair<StoreInst *, Value *>, 4> PredicatedStores;
+  SmallVector<std::pair<Instruction *, Value *>, 4> PredicatedInstructions;
   EdgeMaskCache MaskCache;
   /// Trip count of the original loop.
   Value *TripCount;
   /// Trip count of the widened loop (TripCount - TripCount % (VF*UF))
   Value *VectorTripCount;
 
   /// Map of scalar integer values to the smallest bitwidth they can be legally
   /// represented as. The vector equivalents of these values should be truncated
InnerLoopUnroller(Loop *OrigLoop, PredicatedScalarEvolution &PSE,
                     const TargetLibraryInfo *TLI,
                     const TargetTransformInfo *TTI, AssumptionCache *AC,
                     OptimizationRemarkEmitter *ORE, unsigned UnrollFactor)
       : InnerLoopVectorizer(OrigLoop, PSE, LI, DT, TLI, TTI, AC, ORE, 1,
                             UnrollFactor) {}
 
 private:
   void scalarizeInstruction(Instruction *Instr,
-                            bool IfPredicateStore = false) override;
+                            bool IfPredicateInstr = false) override;
   void vectorizeMemoryInstruction(Instruction *Instr) override;
   Value *getBroadcastInstrs(Value *V) override;
   Value *getStepVector(Value *Val, int StartIdx, Value *Step,
                        Instruction::BinaryOps Opcode =
                        Instruction::BinaryOpsEnd) override;
   Value *reverseVector(Value *Vec) override;
 };
 
if (CreateGatherScatter) {
         NewLI = Builder.CreateAlignedLoad(VecPtr, Alignment, "wide.load");
       Entry[Part] = Reverse ? reverseVector(NewLI) : NewLI;
     }
     addMetadata(NewLI, LI);
   }
 }
 
 void InnerLoopVectorizer::scalarizeInstruction(Instruction *Instr,
-                                               bool IfPredicateStore) {
+                                               bool IfPredicateInstr) {
   assert(!Instr->getType()->isAggregateType() && "Can't handle vectors");
+  DEBUG(dbgs() << "LV: Scalarizing"
+        << (IfPredicateInstr ? " and predicating:" : ":")
+        << *Instr << '\n');
   // Holds vector parameters or scalars, in case of uniform vals.
   SmallVector<VectorParts, 4> Params;
 
   setDebugLocFromInst(Builder, Instr);
 
   // Find all of the vectorized parameters.
   for (Value *SrcOp : Instr->operands()) {
     // If we are accessing the old induction variable, use the new one.
void InnerLoopVectorizer::scalarizeInstruction(Instruction *Instr,
 
   Value *UndefVec =
       IsVoidRetTy ? nullptr
                   : UndefValue::get(VectorType::get(Instr->getType(), VF));
   // Create a new entry in the WidenMap and initialize it to Undef or Null.
   VectorParts &VecResults = WidenMap.splat(Instr, UndefVec);
 
   VectorParts Cond;
-  if (IfPredicateStore) {
+  if (IfPredicateInstr) {
     assert(Instr->getParent()->getSinglePredecessor() &&
            "Only support single predecessor blocks");
     Cond = createEdgeMask(Instr->getParent()->getSinglePredecessor(),
                           Instr->getParent());
   }
 
   // For each vector unroll 'part':
   for (unsigned Part = 0; Part < UF; ++Part) {
     // For each scalar that we create:
     for (unsigned Width = 0; Width < VF; ++Width) {
 
       // Start if-block.
       Value *Cmp = nullptr;
-      if (IfPredicateStore) {
+      if (IfPredicateInstr) {
         Cmp = Builder.CreateExtractElement(Cond[Part], Builder.getInt32(Width));
         Cmp = Builder.CreateICmp(ICmpInst::ICMP_EQ, Cmp,
                                  ConstantInt::get(Cmp->getType(), 1));
       }
 
       Instruction *Cloned = Instr->clone();
       if (!IsVoidRetTy)
         Cloned->setName(Instr->getName() + ".cloned");
for (unsigned Width = 0; Width < VF; ++Width) {
           AC->registerAssumption(II);
 
       // If the original scalar returns a value we need to place it in a vector
       // so that future users will be able to use it.
       if (!IsVoidRetTy)
         VecResults[Part] = Builder.CreateInsertElement(VecResults[Part], Cloned,
                                                        Builder.getInt32(Width));
       // End if-block.
-      if (IfPredicateStore)
-        PredicatedStores.push_back(
-            std::make_pair(cast<StoreInst>(Cloned), Cmp));
+      if (IfPredicateInstr)
+        PredicatedInstructions.push_back(std::make_pair(Cloned, Cmp));
     }
   }
 }
 
 PHINode *InnerLoopVectorizer::createInductionVariable(Loop *L, Value *Start,
                                                       Value *End, Value *Step,
                                                       Instruction *DL) {
   BasicBlock *Header = L->getHeader();
static Value *addFastMathFlag(Value *V) {
   if (isa<FPMathOperator>(V)) {
     FastMathFlags Flags;
     Flags.setUnsafeAlgebra();
     cast<Instruction>(V)->setFastMathFlags(Flags);
   }
   return V;
 }
 
-/// Estimate the overhead of scalarizing a value. Insert and Extract are set if
-/// the result needs to be inserted and/or extracted from vectors.
+/// \brief Estimate the overhead of scalarizing a value. Insert and Extract are
+/// set if the result needs to be inserted and/or extracted from vectors.
+/// If the instruction is also to be predicated, insertion cost is added the
+/// cost of the PHI node required.
 static unsigned getScalarizationOverhead(Type *Ty, bool Insert, bool Extract,
+                                         bool Predicate,
                                          const TargetTransformInfo &TTI) {
   if (Ty->isVoidTy())
     return 0;
 
   assert(Ty->isVectorTy() && "Can only scalarize vectors");
   unsigned Cost = 0;
 
   for (unsigned I = 0, E = Ty->getVectorNumElements(); I < E; ++I) {
-    if (Insert)
+    if (Insert) {
+      if (Predicate)
+        Cost += TTI.getCFInstrCost(Instruction::PHI);
       Cost += TTI.getVectorInstrCost(Instruction::InsertElement, Ty, I);
+    }
     if (Extract)
       Cost += TTI.getVectorInstrCost(Instruction::ExtractElement, Ty, I);
   }
 
+  // We assume that if-converted blocks have a 50% chance of being executed.
+  // Predicated scalarized instructions are avoided due to the CF that bypasses
+  // turned off lanes. The extracts and inserts will be sinked/hoisted to the
+  // predicated basic-block and are subjected to the same assumption.
+  if (Predicate)
+    Cost /= 2;
+
   return Cost;
 }
 
+/// \brief Estimate the overhead of scalarizing an instruction based on the
+/// types of its operand and return value.
+static unsigned getScalarizationOverhead(SmallVectorImpl<Type *>& OpTys,
+                                         Type *RetTy, bool Predicate,
+                                         const TargetTransformInfo &TTI) {
+  unsigned ScalarizationCost =
+      getScalarizationOverhead(RetTy, true, false, Predicate, TTI);
+
+  for (Type *Ty : OpTys)
+    ScalarizationCost +=
+        getScalarizationOverhead(Ty, false, true, Predicate, TTI);
+
+  return ScalarizationCost;
+}
+
+/// \brief Estimate the overhead of scalarizing an instruction based on the
+/// types of its operand and return value.
+static unsigned getScalarizationOverhead(Instruction *I, Type* RetTy,
+                                         unsigned VF, bool Predicate,
+                                         const TargetTransformInfo &TTI) {
+  if (VF == 1)
+    return 0;
+
+  SmallVector<Type *, 4> OpTys;
+  unsigned OperandsNum = I->getNumOperands();
+  for (unsigned OpInd = 0; OpInd < OperandsNum; ++OpInd)
+    OpTys.push_back(ToVectorTy(I->getOperand(OpInd)->getType(), VF));
+
+  return getScalarizationOverhead(OpTys, RetTy, Predicate, TTI);
+}
+
 // Estimate cost of a call instruction CI if it were vectorized with factor VF.
 // Return the cost of the instruction, including scalarization overhead if it's
 // needed. The flag NeedToScalarize shows if the call needs to be scalarized -
 // i.e. either vector version isn't available, or is too expensive.
 static unsigned getVectorCallCost(CallInst *CI, unsigned VF,
                                   const TargetTransformInfo &TTI,
                                   const TargetLibraryInfo *TLI,
                                   bool &NeedToScalarize) {
static unsigned getVectorCallCost(CallInst *CI, unsigned VF,
 
   // Compute corresponding vector type for return value and arguments.
   Type *RetTy = ToVectorTy(ScalarRetTy, VF);
   for (Type *ScalarTy : ScalarTys)
     Tys.push_back(ToVectorTy(ScalarTy, VF));
 
   // Compute costs of unpacking argument values for the scalar calls and
   // packing the return values to a vector.
-  unsigned ScalarizationCost =
-      getScalarizationOverhead(RetTy, true, false, TTI);
-  for (Type *Ty : Tys)
-    ScalarizationCost += getScalarizationOverhead(Ty, false, true, TTI);
+  unsigned ScalarizationCost = getScalarizationOverhead(Tys, RetTy, false, TTI);
 
   unsigned Cost = ScalarCallCost * VF + ScalarizationCost;
 
   // If we can't emit a vector call for this function, then the currently found
   // cost is the cost we need to return.
   NeedToScalarize = true;
   if (!TLI || !TLI->isFunctionVectorizable(FnName, VF) || CI->isNoBuiltin())
     return Cost;
for (PHINode *Phi : PHIsToFix) {
     Phi->setIncomingValue(IncomingEdgeBlockIdx, LoopExitInst);
   } // end of for each Phi in PHIsToFix.
 
   fixLCSSAPHIs();
 
   // Make sure DomTree is updated.
   updateAnalysis();
 
-  // Predicate any stores.
-  for (auto KV : PredicatedStores) {
+  // Predicate any instructions.
+  for (auto KV : PredicatedInstructions) {
     BasicBlock::iterator I(KV.first);
-    auto *BB = SplitBlock(I->getParent(), &*std::next(I), DT, LI);
+    BasicBlock *Head = I->getParent();
+    auto *BB = SplitBlock(Head, &*std::next(I), DT, LI);
     auto *T = SplitBlockAndInsertIfThen(KV.second, &*I, /*Unreachable=*/false,
                                         /*BranchWeights=*/nullptr, DT, LI);
     I->moveBefore(T);
-    I->getParent()->setName("pred.store.if");
-    BB->setName("pred.store.continue");
+    // Try to move any extract-element we may have created for the predicated
+    // instruction into the Then block.
+    for (unsigned In = 0; In < I->getNumOperands(); ++In) {
+      ExtractElementInst *OpInst =
+          dyn_cast<ExtractElementInst>(I->getOperand(In));
+      if (!OpInst)
+        continue;
+      bool CanSinkToUse = true;
+      for (User *U : OpInst->users()) {
+        if (U != &*I) {
+          CanSinkToUse = false;
+          break;
+        }
+      }
+      if (CanSinkToUse)
+        OpInst->moveBefore(&*I);
+    }
+    I->getParent()->setName(Twine("pred.") + Twine(I->getOpcodeName()) +
+                            Twine(".if"));
+    BB->setName(Twine("pred.") + Twine(I->getOpcodeName()) +
+                Twine(".continue"));
+    // If the instruction is non-void create a Phi node at reconvergence point.
+    if (!I->getType()->isVoidTy()) {
+      Value *IncomingTrue = nullptr;
+      Value *IncomingFalse = nullptr;
+      auto Users = I->users();
+      if (std::distance(Users.begin(), Users.end()) == 1 &&
+          isa<InsertElementInst>(*I->users().begin())) {
+        // If the predicated instruction is feeding an insert-element, move it
+        // into the Then block; Phi node will be created for the vector.
+        InsertElementInst *IEI = cast<InsertElementInst>(*Users.begin());
+        IEI->moveBefore(T);
+        IncomingTrue = IEI; // the new vector with the inserted element.
+        IncomingFalse = IEI->getOperand(0); // the unmodified vector
+      } else {
+        // Phi node will be created for the scalar predicated instruction.
+        IncomingTrue = &*I;
+        IncomingFalse = UndefValue::get(I->getType());
+      }
+      BasicBlock *PostDom = I->getParent()->getSingleSuccessor();
+      assert(PostDom && "Then block has multiple successors");
+      PHINode *Phi =
+          PHINode::Create(IncomingTrue->getType(), 2, "", &PostDom->front());
+      IncomingTrue->replaceAllUsesWith(Phi);
+      Phi->addIncoming(IncomingFalse, Head);
+      Phi->addIncoming(IncomingTrue, I->getParent());
+    }
   }
   DEBUG(DT->verifyDomTree());
   // Remove redundant induction instructions.
   cse(LoopVectorBody);
 }
 
 void InnerLoopVectorizer::fixFirstOrderRecurrence(PHINode *Phi) {
 
if (!LCSSAPhi)
       break;
     if (LCSSAPhi->getNumIncomingValues() == 1)
       LCSSAPhi->addIncoming(UndefValue::get(LCSSAPhi->getType()),
                             LoopMiddleBlock);
   }
 }
 
 InnerLoopVectorizer::VectorParts
 InnerLoopVectorizer::createEdgeMask(BasicBlock *Src, BasicBlock *Dst) {
   assert(std::find(pred_begin(Dst), pred_end(Dst), Src) != pred_end(Dst) &&
          "Invalid edge");
 
   // Look for cached value.
   std::pair<BasicBlock *, BasicBlock *> Edge(Src, Dst);
   EdgeMaskCache::iterator ECEntryIt = MaskCache.find(Edge);
   if (ECEntryIt != MaskCache.end())
     return ECEntryIt->second;
 
   VectorParts SrcMask = createBlockInMask(Src);
 
   // The terminator has to be a branch inst!
   BranchInst *BI = dyn_cast<BranchInst>(Src->getTerminator());
   assert(BI && "Unexpected terminator found");
 
   if (BI->isConditional()) {
     VectorParts EdgeMask = getVectorValue(BI->getCondition());
 
     if (BI->getSuccessor(0) != Dst)
       for (unsigned part = 0; part < UF; ++part)
         EdgeMask[part] = Builder.CreateNot(EdgeMask[part]);
 
     for (unsigned part = 0; part < UF; ++part)
       EdgeMask[part] = Builder.CreateAnd(EdgeMask[part], SrcMask[part]);
 
     MaskCache[Edge] = EdgeMask;
     return EdgeMask;
   }
 
   MaskCache[Edge] = SrcMask;
   return SrcMask;
 }
 
 InnerLoopVectorizer::VectorParts
 InnerLoopVectorizer::createBlockInMask(BasicBlock *BB) {
   assert(OrigLoop->contains(BB) && "Block is not a part of a loop");
 
   // Loop incoming mask is all-one.
   if (OrigLoop->getHeader() == BB) {
     Value *C = ConstantInt::get(IntegerType::getInt1Ty(BB->getContext()), 1);
     return getVectorValue(C);

 void InnerLoopVectorizer::vectorizeBlockInLoop(BasicBlock *BB, PhiVector *PV) {
   // For each instruction in the old loop.
   for (Instruction &I : *BB) {
     VectorParts &Entry = WidenMap.get(&I);
 
     switch (I.getOpcode()) {
     case Instruction::Br:
       // Nothing to do for PHIs and BR, since we already took care of the
       // loop control flow instructions.
       continue;
     case Instruction::PHI: {
       // Vectorize PHINodes.
       widenPHIInstruction(&I, Entry, UF, VF, PV);
       continue;
     } // End of PHI.
 
+    case Instruction::UDiv:
+    case Instruction::SDiv:
+    case Instruction::SRem:
+    case Instruction::FRem:
+      // Scalarize if block needs predication, otherwise fallthrough.
+      if (Legal->blockNeedsPredication(I.getParent())) {
+        scalarizeInstruction(&I, true);
+        continue;
+      }
     case Instruction::Add:
     case Instruction::FAdd:
     case Instruction::Sub:
     case Instruction::FSub:
     case Instruction::Mul:
     case Instruction::FMul:
-    case Instruction::UDiv:
-    case Instruction::SDiv:
     case Instruction::FDiv:
     case Instruction::URem:
-    case Instruction::SRem:
-    case Instruction::FRem:
     case Instruction::Shl:
     case Instruction::LShr:
     case Instruction::AShr:
     case Instruction::And:
     case Instruction::Or:
     case Instruction::Xor: {
       // Just widen binops.
       auto *BinOp = cast<BinaryOperator>(&I);
if (I.mayReadFromMemory()) {
         }
         // !llvm.mem.parallel_loop_access implies if-conversion safety.
         if (IsAnnotatedParallel)
           continue;
         return false;
       }
     }
 
     // We don't predicate stores at the moment.
     if (I.mayWriteToMemory()) {
       auto *SI = dyn_cast<StoreInst>(&I);
       // We only support predication of stores in basic blocks with one
       // predecessor.
       if (!SI)
         return false;
 
       // Build a masked store if it is legal for the target.
       if (isLegalMaskedStore(SI->getValueOperand()->getType(),
                              SI->getPointerOperand()) ||
           isLegalMaskedScatter(SI->getValueOperand()->getType())) {
         MaskedOp.insert(SI);
         continue;
       }
 
       bool isSafePtr = (SafePtrs.count(SI->getPointerOperand()) != 0);
       bool isSinglePredecessor = SI->getParent()->getSinglePredecessor();
 
       if (++NumPredStores > NumberOfStoresToPredicate || !isSafePtr ||
           !isSinglePredecessor)
         return false;
     }
     if (I.mayThrow())
       return false;
-
-    // The instructions below can trap.
-    switch (I.getOpcode()) {
-    default:
-      continue;
-    case Instruction::UDiv:
-    case Instruction::SDiv:
-    case Instruction::URem:
-    case Instruction::SRem:
-      return false;
-    }
   }
 
   return true;
 }
 
 void InterleavedAccessInfo::collectConstStrideAccesses(
     MapVector<Instruction *, StrideDescriptor> &AccessStrideInfo,
     const ValueToValueMap &Strides) {
LoopVectorizationCostModel::calculateRegisterUsage(ArrayRef<unsigned> VFs) {
   }
 
   return RUs;
 }
 
 LoopVectorizationCostModel::VectorizationCostTy
 LoopVectorizationCostModel::expectedCost(unsigned VF) {
   VectorizationCostTy Cost;
-
   // For each block.
   for (BasicBlock *BB : TheLoop->blocks()) {
     VectorizationCostTy BlockCost;
 
     // For each instruction in the old loop.
     for (Instruction &I : *BB) {
       // Skip dbg intrinsics.
       if (isa<DbgInfoIntrinsic>(I))
case Instruction::PHI: {
     // First-order recurrences are replaced by vector shuffles inside the loop.
     if (VF > 1 && Legal->isFirstOrderRecurrence(Phi))
       return TTI.getShuffleCost(TargetTransformInfo::SK_ExtractSubvector,
                                 VectorTy, VF - 1, VectorTy);
 
     // TODO: IF-converted IFs become selects.
     return 0;
   }
+  case Instruction::UDiv:
+  case Instruction::SDiv:
+  case Instruction::URem:
+  case Instruction::SRem:
+    // We assume that if-converted blocks have a 50% chance of being executed.
+    // Predicated scalarized instructions are avoided due to the CF that
+    // bypasses turned off lanes. If we are not predicating, fallthrough.
+    if (VF > 1 && Legal->blockNeedsPredication(I->getParent()))
+      return VF * TTI.getArithmeticInstrCost(I->getOpcode(), RetTy) / 2 +
+             getScalarizationOverhead(I, VectorTy, VF, true, TTI);
   case Instruction::Add:
   case Instruction::FAdd:
   case Instruction::Sub:
   case Instruction::FSub:
   case Instruction::Mul:
   case Instruction::FMul:
-  case Instruction::UDiv:
-  case Instruction::SDiv:
   case Instruction::FDiv:
-  case Instruction::URem:
-  case Instruction::SRem:
   case Instruction::FRem:
   case Instruction::Shl:
   case Instruction::LShr:
   case Instruction::AShr:
   case Instruction::And:
   case Instruction::Or:
   case Instruction::Xor: {
     // Since we will replace the stride by 1 the multiplication should go away.
unsigned LoopVectorizationCostModel::getInstructionCost(Instruction *I,
   case Instruction::Call: {
     bool NeedToScalarize;
     CallInst *CI = cast<CallInst>(I);
     unsigned CallCost = getVectorCallCost(CI, VF, TTI, TLI, NeedToScalarize);
     if (getVectorIntrinsicIDForCall(CI, TLI))
       return std::min(CallCost, getVectorIntrinsicCost(CI, VF, TTI, TLI));
     return CallCost;
   }
-  default: {
-    // We are scalarizing the instruction. Return the cost of the scalar
-    // instruction, plus the cost of insert and extract into vector
-    // elements, times the vector width.
-    unsigned Cost = 0;
-
-    if (!RetTy->isVoidTy() && VF != 1) {
-      unsigned InsCost =
-          TTI.getVectorInstrCost(Instruction::InsertElement, VectorTy);
-      unsigned ExtCost =
-          TTI.getVectorInstrCost(Instruction::ExtractElement, VectorTy);
-
-      // The cost of inserting the results plus extracting each one of the
-      // operands.
-      Cost += VF * (InsCost + ExtCost * I->getNumOperands());
-    }
-
+  default:
     // The cost of executing VF copies of the scalar instruction. This opcode
     // is unknown. Assume that it is the same as 'mul'.
-    Cost += VF * TTI.getArithmeticInstrCost(Instruction::Mul, VectorTy);
-    return Cost;
-  }
+    return VF * TTI.getArithmeticInstrCost(Instruction::Mul, VectorTy) +
+           getScalarizationOverhead(I, VectorTy, VF, false, TTI);
   } // end of switch.
 }
 
 char LoopVectorize::ID = 0;
 static const char lv_name[] = "Loop Vectorization";
 INITIALIZE_PASS_BEGIN(LoopVectorize, LV_NAME, lv_name, false, false)
 INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(BasicAAWrapperPass)
if (std::all_of(PN->user_begin(), PN->user_end(),
                     })) {
       VecValuesToIgnore.insert(PN);
       VecValuesToIgnore.insert(UpdateV);
     }
   }
 }
 
 void InnerLoopUnroller::scalarizeInstruction(Instruction *Instr,
-                                             bool IfPredicateStore) {
+                                             bool IfPredicateInstr) {
   assert(!Instr->getType()->isAggregateType() && "Can't handle vectors");
   // Holds vector parameters or scalars, in case of uniform vals.
   SmallVector<VectorParts, 4> Params;
 
   setDebugLocFromInst(Builder, Instr);
 
   // Find all of the vectorized parameters.
   for (Value *SrcOp : Instr->operands()) {
void InnerLoopUnroller::scalarizeInstruction(Instruction *Instr,
   // Does this instruction return a value ?
   bool IsVoidRetTy = Instr->getType()->isVoidTy();
 
   Value *UndefVec = IsVoidRetTy ? nullptr : UndefValue::get(Instr->getType());
   // Create a new entry in the WidenMap and initialize it to Undef or Null.
   VectorParts &VecResults = WidenMap.splat(Instr, UndefVec);
 
   VectorParts Cond;
-  if (IfPredicateStore) {
+  if (IfPredicateInstr) {
     assert(Instr->getParent()->getSinglePredecessor() &&
            "Only support single predecessor blocks");
     Cond = createEdgeMask(Instr->getParent()->getSinglePredecessor(),
                           Instr->getParent());
   }
 
   // For each vector unroll 'part':
   for (unsigned Part = 0; Part < UF; ++Part) {
     // For each scalar that we create:
 
     // Start an "if (pred) a[i] = ..." block.
     Value *Cmp = nullptr;
-    if (IfPredicateStore) {
+    if (IfPredicateInstr) {
       if (Cond[Part]->getType()->isVectorTy())
         Cond[Part] =
             Builder.CreateExtractElement(Cond[Part], Builder.getInt32(0));
       Cmp = Builder.CreateICmp(ICmpInst::ICMP_EQ, Cond[Part],
                                ConstantInt::get(Cond[Part]->getType(), 1));
     }
 
     Instruction *Cloned = Instr->clone();
if (auto *II = dyn_cast<IntrinsicInst>(Cloned))
         AC->registerAssumption(II);
 
     // If the original scalar returns a value we need to place it in a vector
     // so that future users will be able to use it.
     if (!IsVoidRetTy)
       VecResults[Part] = Cloned;
 
     // End if-block.
-    if (IfPredicateStore)
-      PredicatedStores.push_back(std::make_pair(cast<StoreInst>(Cloned), Cmp));
+    if (IfPredicateInstr)
+      PredicatedInstructions.push_back(std::make_pair(Cloned, Cmp));
   }
 }
 
 void InnerLoopUnroller::vectorizeMemoryInstruction(Instruction *Instr) {
   auto *SI = dyn_cast<StoreInst>(Instr);
-  bool IfPredicateStore = (SI && Legal->blockNeedsPredication(SI->getParent()));
+  bool IfPredicateInstr = (SI && Legal->blockNeedsPredication(SI->getParent()));
 
-  return scalarizeInstruction(Instr, IfPredicateStore);
+  return scalarizeInstruction(Instr, IfPredicateInstr);
 }
 
 Value *InnerLoopUnroller::reverseVector(Value *Vec) { return Vec; }
 
 Value *InnerLoopUnroller::getBroadcastInstrs(Value *V) { return V; }
 
 Value *InnerLoopUnroller::getStepVector(Value *Val, int StartIdx, Value *Step,
                                         Instruction::BinaryOps BinOp) {

test/Transforms/LoopVectorize/if-pred-non-void.ll

+; RUN: opt -S -force-vector-width=2 -force-vector-interleave=1 -loop-vectorize -enable-cond-stores-vec -verify-loop-info -simplifycfg < %s | FileCheck %s
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+; Test predication of non-void instructions, specifically the creation of an
+; insertelement and a Phi node.
+define void @test(i32* nocapture %a) {
+entry:
+  br label %for.body
+
+for.cond.cleanup:                                 ; preds = %if.end
+  ret void
+
+; CHECK-LABEL: test
+; CHECK: vector.body:
+; CHECK:   br i1 %{{.*}}, label %[[cond:[a-zA-Z0-9.]+]], label %[[else:[a-zA-Z0-9.]+]]
+; CHECK: [[cond]]:
+; CHECK:  %[[v0:[a-zA-Z0-9]+]] = sdiv i32 %{{.*}}, %{{.*}}
+; CHECK:  %[[v1:[a-zA-Z0-9]+]] = insertelement <2 x i32> undef, i32 %[[v0]], i32 0
+; CHECK:   br label %[[else]]
+; CHECK: [[else]]:
+; CHECK:   %{{.*}} = phi <2 x i32> [ undef, %vector.body ], [ %[[v1]], %[[cond]] ]
+
+for.body:                                         ; preds = %if.end, %entry
+  %indvars.iv = phi i64 [ 0, %entry ], [ %indvars.iv.next, %if.end ]
+  %arrayidx = getelementptr inbounds i32, i32* %a, i64 %indvars.iv
+  %0 = load i32, i32* %arrayidx, align 4
+  %add = add nsw i32 %0, 27
+  %cmp1 = icmp slt i32 %0, 100
+  br i1 %cmp1, label %if.then, label %if.end
+
+if.then:                                          ; preds = %for.body
+  %div = sdiv i32 %add, %0
+  br label %if.end
+
+if.end:                                           ; preds = %if.then, %for.body
+  %y.0 = phi i32 [ %div, %if.then ], [ %add, %for.body ]
+  store i32 %y.0, i32* %arrayidx, align 4
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  %exitcond = icmp eq i64 %indvars.iv.next, 128
+  br i1 %exitcond, label %for.cond.cleanup, label %for.body
+}

test/Transforms/LoopVectorize/if-pred-stores.ll

 ; RUN: opt -S -vectorize-num-stores-pred=1 -force-vector-width=1 -force-vector-interleave=2 -loop-vectorize -verify-loop-info -simplifycfg < %s | FileCheck %s --check-prefix=UNROLL
 ; RUN: opt -S -vectorize-num-stores-pred=1 -force-vector-width=1 -force-vector-interleave=2 -loop-vectorize -verify-loop-info < %s | FileCheck %s --check-prefix=UNROLL-NOSIMPLIFY
 ; RUN: opt -S -vectorize-num-stores-pred=1 -force-vector-width=2 -force-vector-interleave=1 -loop-vectorize -enable-cond-stores-vec -verify-loop-info -simplifycfg < %s | FileCheck %s --check-prefix=VEC
-; RUN: opt -S -vectorize-num-stores-pred=1 -force-vector-width=2 -force-vector-interleave=1 -loop-vectorize -enable-cond-stores-vec -verify-loop-info -simplifycfg -instcombine < %s | FileCheck %s --check-prefix=VEC-IC
 
 target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-apple-macosx10.9.0"
 
 ; Test predication of stores.
 define i32 @test(i32* nocapture %f) #0 {
 entry:
   br label %for.body
 
 ; VEC-LABEL: test
 ; VEC:   %[[v8:.+]] = icmp sgt <2 x i32> %{{.*}}, <i32 100, i32 100>
 ; VEC:   %[[v9:.+]] = add nsw <2 x i32> %{{.*}}, <i32 20, i32 20>
 ; VEC:   %[[v10:.+]] = and <2 x i1> %[[v8]], <i1 true, i1 true>
 ; VEC:   %[[v11:.+]] = extractelement <2 x i1> %[[v10]], i32 0
 ; VEC:   %[[v12:.+]] = icmp eq i1 %[[v11]], true
-; VEC:   %[[v13:.+]] = extractelement <2 x i32> %[[v9]], i32 0
-; VEC:   %[[v14:.+]] = extractelement <2 x i32*> %{{.*}}, i32 0
 ; VEC:   br i1 %[[v12]], label %[[cond:.+]], label %[[else:.+]]
 ;
 ; VEC: [[cond]]:
+; VEC:   %[[v13:.+]] = extractelement <2 x i32> %[[v9]], i32 0
+; VEC:   %[[v14:.+]] = extractelement <2 x i32*> %{{.*}}, i32 0
 ; VEC:   store i32 %[[v13]], i32* %[[v14]], align 4
 ; VEC:   br label %[[else:.+]]
 ;
 ; VEC: [[else]]:
 ; VEC:   %[[v15:.+]] = extractelement <2 x i1> %[[v10]], i32 1
 ; VEC:   %[[v16:.+]] = icmp eq i1 %[[v15]], true
-; VEC:   %[[v17:.+]] = extractelement <2 x i32> %[[v9]], i32 1
-; VEC:   %[[v18:.+]] = extractelement <2 x i32*> %{{.+}} i32 1
 ; VEC:   br i1 %[[v16]], label %[[cond2:.+]], label %[[else2:.+]]
 ;
 ; VEC: [[cond2]]:
+; VEC:   %[[v17:.+]] = extractelement <2 x i32> %[[v9]], i32 1
+; VEC:   %[[v18:.+]] = extractelement <2 x i32*> %{{.+}} i32 1
 ; VEC:   store i32 %[[v17]], i32* %[[v18]], align 4
 ; VEC:   br label %[[else2:.+]]
 ;
 ; VEC: [[else2]]:
 
-; VEC-IC-LABEL: test
-; VEC-IC:   %[[v1:.+]] = icmp sgt <2 x i32> %{{.*}}, <i32 100, i32 100>
-; VEC-IC:   %[[v2:.+]] = add nsw <2 x i32> %{{.*}}, <i32 20, i32 20>
-; VEC-IC:   %[[v3:.+]] = extractelement <2 x i1> %[[v1]], i32 0
-; VEC-IC:   br i1 %[[v3]], label %[[cond:.+]], label %[[else:.+]]
-;
-; VEC-IC: [[cond]]:
-; VEC-IC:   %[[v4:.+]] = extractelement <2 x i32> %[[v2]], i32 0
-; VEC-IC:   store i32 %[[v4]], i32* %{{.*}}, align 4
-; VEC-IC:   br label %[[else:.+]]
-;
-; VEC-IC: [[else]]:
-; VEC-IC:   %[[v5:.+]] = extractelement <2 x i1> %[[v1]], i32 1
-; VEC-IC:   br i1 %[[v5]], label %[[cond2:.+]], label %[[else2:.+]]
-;
-; VEC-IC: [[cond2]]:
-; VEC-IC:   %[[v6:.+]] = extractelement <2 x i32> %[[v2]], i32 1
-; VEC-IC:   store i32 %[[v6]], i32* %{{.*}}, align 4
-; VEC-IC:   br label %[[else2:.+]]
-;
-; VEC-IC: [[else2]]:
-
 ; UNROLL-LABEL: test
 ; UNROLL: vector.body:
 ; UNROLL:   %[[IND:[a-zA-Z0-9]+]] = add i64 %{{.*}}, 0
 ; UNROLL:   %[[IND1:[a-zA-Z0-9]+]] = add i64 %{{.*}}, 1
 ; UNROLL:   %[[v0:[a-zA-Z0-9]+]] = getelementptr inbounds i32, i32* %f, i64 %[[IND]]
 ; UNROLL:   %[[v1:[a-zA-Z0-9]+]] = getelementptr inbounds i32, i32* %f, i64 %[[IND1]]
 ; UNROLL:   %[[v2:[a-zA-Z0-9]+]] = load i32, i32* %[[v0]], align 4
 ; UNROLL:   %[[v3:[a-zA-Z0-9]+]] = load i32, i32* %[[v1]], align 4