[Loop Vectorize] Vectorize Loops with Backward Dependence

[DIVYA]

Summary

This is the LLVM pass which is intended to be run before loop vectorizer. This pass checks if there is a backward dependence between instructions ,and if so, then it tries to reorders instructions, so as to convert non-vectorizable loop into vectorizable form. The pass uses the LoopAccessAnalysis and MemorySSA analysis to check for dependences, inorder to reorder the instructions.

Worked in collaboration with Aditya Kumar

[fhahn]

I just had a quick look and left a few comments. I'm just curious, what kind of testing did you do & did you run any benchmarks?

include/llvm/Transforms/Vectorize.h

128 ↗

(On Diff #109000)

Indent is off.

include/llvm/Transforms/Vectorize/LoopVectorizePred.h

2 ↗

(On Diff #109000)

This should go on line 1 I think, see first line of Vectorize.h for example.

lib/Transforms/IPO/PassManagerBuilder.cpp

831 ↗

(On Diff #109000)

I think people might be more comfortable with adding the new pass if there is an option to completely disable it, as in not adding it to the pass manager (like with LoopInterchange for example). This way, the pass can go in being disabled by default and makes it easier for people to test it/run benchmarks.

lib/Transforms/Vectorize/LoopVectorizePred.cpp

111 ↗

(On Diff #109000)

I think this function could do with slightly more comments, e.g. what the loops are doing and so on.

115 ↗

(On Diff #109000)

Is there a more meaningful name instead of temprit?

152 ↗

(On Diff #109000)

I think you could use Dep.isBackward(), which is shorter.

160 ↗

(On Diff #109000)

Could be a for loop?

[DIVYA]

[DIVYA]

• Added comments
• Made option to disable pass

[DIVYA]

lib/Transforms/Vectorize/LoopVectorizePred.cpp

152 ↗

(On Diff #109000)

Dep.isBackward() will take BackwardVectorizable, Backward and BackwardVectorizableButPreventsForwarding cases into consideration.But Here its done only for Backward dependences

[hiraditya]

include/llvm/Transforms/Vectorize/LoopVectorizePred.h

12 ↗

(On Diff #109231)

s/reorders/reorder

lib/Transforms/Vectorize/LoopVectorizePred.cpp

188 ↗

(On Diff #109231)

|= false is a noop.

[hiraditya]

lib/Transforms/Vectorize/LoopVectorizePred.cpp

114 ↗

(On Diff #109231)

We can make moved a bool

168 ↗

(On Diff #109231)

I think we do not need a dyn_cast here, we can just compare the instructions.

[hiraditya]

@hfinkel , I'd appreciate your feedback, and suggestions for improvement.
Thanks,

[DIVYA]

ping

[hfinkel]

include/llvm/Transforms/IPO/PassManagerBuilder.h

151 ↗

(On Diff #109799)

I don't think we need a special pass-manager option for this. We can put it behind a cl::opt flag, but once it is judged to be ready for the default pipeline, I imagine we'll always enable it whenever vectorization is enabled (at least at -O3).

include/llvm/Transforms/Vectorize/LoopVectorizePred.h

10 ↗

(On Diff #109799)

This first sentence seems inaccurate. It does not need to be run, nor does it need to run before the vectorizer. You can say that it is intended to be run before the vectorizer.

11 ↗

(On Diff #109799)

" instructions ,if so, " -> " instructions, and if so, "

13 ↗

(On Diff #109799)

"and generates target-independent LLVM-IR" - all passes do this unless other noted. No need to say that here.

13 ↗

(On Diff #109799)

"The vectorizer uses" - Is this a statement about the vectorizer or this pass?

14 ↗

(On Diff #109799)

the LoopAccessAnalysis -> remove "the" and the extra spaces on this line.

lib/Transforms/Vectorize/LoopVectorizePred.cpp

12 ↗

(On Diff #109799)

See comments from the header file. They apply here too.

17 ↗

(On Diff #109799)

Please put here some pseudo-cost/C examples, before/after, showing what the transformation does.

57 ↗

(On Diff #109799)

space before and

58 ↗

(On Diff #109799)

remove comma before if.

111 ↗

(On Diff #109799)

Please add a comment explaining what this function does.

113 ↗

(On Diff #109799)

Local variable names need to start with a capital letter.

116 ↗

(On Diff #109799)

Is this algorithm quadratic?

118 ↗

(On Diff #109799)

Please be careful with the formatting of comments. Only once space in between words. A single space goes after a comma, none before.

130 ↗

(On Diff #109799)

Can you do this with std::find and op_begin/op_end?

175 ↗

(On Diff #109799)

It also makes the load loop invariant. Why does LICM not hoist it?

210 ↗

(On Diff #109799)

Please describe what this function does.

226 ↗

(On Diff #109799)

Please describe what this function does.

[• dberlin]

lib/Transforms/Vectorize/LoopVectorizePred.cpp

111 ↗

(On Diff #109799)

This funciton looks like it tries to figure out if the operands can be moved upward. You don't need to iterate through the instructions at all to do this.
You can just use the def-use chains and stop when your chain is above the other instruction.
If you need local-to-block ordering, use OrderedInstructions->dominates to tell when you are above the

179 ↗

(On Diff #109799)

You are guaranteed this is a MemoryUseOrDef, since oyu asked about a load.
There is no need for a dyn_cast_or_null, a simple cast will suffice.

184 ↗

(On Diff #109799)

This check does not make much sense.
The right check to see if it's not dependent in the loop would be to see if the defining access is above the loop. As hal says, that makes it loop invariant.
The right check to see if it not dependent on the store would be to see if the defining access dominates (in the global sense, so if it's part of the same block, it must come before) the store, and is not part of an SCC of the memoryssa use-def graph that contains the store's memory access.

(If it is not part of an scc, it cannot be changing in the loop. If the store's memory access does not appear in the SCC, it cannot be part of whatever cycle affects this load)

IE even in the case that the store is below the load:

a = memoryphi(foo, bar)
baz = memorydef(a)
memoryuse(baz)
bar = memorydef(baz)

This will give the right answer.

[DIVYA]

• Modified checkDepAndReorder() function to use use-def chain and OrderedInstructions
• added extra checks using MemorySSA results and OrderedInstructions( in reorderInstructions() functions), to check when checkDepAndReorder() be invoked
• Modified some comments and formatting

[DIVYA]

include/llvm/Transforms/IPO/PassManagerBuilder.h

151 ↗

(On Diff #109799)

I had already added cl::opt flag "EnableLoopVectorizePred" in PassManagerBuilder.cpp to have an option to disable the pass.Do I need add to anything else?

[DIVYA]

ping

[hfinkel]

include/llvm/Transforms/IPO/PassManagerBuilder.h

151 ↗

(On Diff #109799)

Remove this variable (make the cl::opt default to off for now). We don't want a proliferation of these for each pass.

include/llvm/Transforms/Vectorize/LoopVectorizePred.h

16 ↗

(On Diff #110726)

inorder -> in order

lib/Transforms/Vectorize/LoopVectorizePred.cpp

129 ↗

(On Diff #110726)

Do you mean "aliasing store instruction" or do you mean "backward-dependent store instruction"? I think the latter.

131 ↗

(On Diff #110726)

Is what you're doing here sufficient? What happens if you have memory-access instructions , function calls, etc. that need to be moved because of (potential) memory dependencies?

187 ↗

(On Diff #110726)

I'm somewhat concerned that a number of these cases are actually handling loop-invariant values, meaning that we're doing a suboptimal handling of something that LICM should handle more fully. The problem is that dealing with these after vectorization could be more difficult than before, and if we have a phase-ordering problem such that we're missing these cases, we might just end up with suboptimal code. Are you seeing these cases in practice?

200 ↗

(On Diff #110726)

Are you assuming here that the Phi must be the loop backedge? What if there's control flow in the loop (note that the vectorizer can do if conversion).

[DIVYA]

• Modified Comments

lib/Transforms/Vectorize/LoopVectorizePred.cpp

131 ↗

(On Diff #110726)

If there are any memory-access instructions, or function calls , on which the load instruction depends, then the MemorySSA analysis will find that out, and the control will never reach this function.

187 ↗

(On Diff #110726)

I think the loop invariant codes will be already hoisted outside the loop before this pass.The Defining access will be liveOnEntry for the loads and stores from pointer arguments .
For example in the below code, the defining access for the load Instruction for a[i+1], is Live on Entry .However the load instruction is not loop invariant.

For the case
int foo1(int n,int * restrict a, int * restrict b, int *restrict m){

int i;
for (i = 0; i < n; i++){
  a[i] = b[i];
  m[i] = a[i+1];
}

}

200 ↗

(On Diff #110726)

Even if the Phi is not from loop backedge , rather from control flow, still if the store Instruction dominates the load, the load can be moved above the store Instruction.Since the store Instruction remains below the defining access(which is memory phi)

[• dberlin]

lib/Transforms/Vectorize/LoopVectorizePred.cpp

187 ↗

(On Diff #110726)

I'm surprised it can prove that it does not conflict with the store.
The load instruction actually is loop invariant in the sense of whether a given loaded address can change during the loop, it just takes on different loop invariant values each iteration.

It is possible to hoist it out of this loop, it just requires making a different loop :)

In particular, this generates the same result:

int foo1(int n,int * restrict a, int * restrict b, int *restrict m){

int i;
for (i = 0; i < n; i++){
  m[i] = a[i+1];
}
for (i = 0; i < n; i++){
  a[i] = b[i];
}
}

[mssimpso]

lib/Transforms/Vectorize/LoopVectorizePred.cpp

187 ↗

(On Diff #110726)

I wonder if our loop distribution pass (disabled by default) can handle this case?

[• dberlin]

This comment has been deleted.

lib/Transforms/Vectorize/LoopVectorizePred.cpp

187 ↗

(On Diff #110726)

I also wonder if one of our passes could ever transform it to memcpy, since it's just a memcpy(m, a+1, n*sizeof(a))

[hiraditya]

lib/Transforms/Vectorize/LoopVectorizePred.cpp

187 ↗

(On Diff #110726)

@hfinkel
Since LICM does not hoist the invariant load, we do not see any performance degradation with this patch. Also, this patch handles other cases where the memory access is not live on entry. If LICM improves to handle invariant loads as you stated, or if we run loop distribution before vectorization, then we can disable that part. Other cases where the load is not loop invariant but can be reordered to enable vectorization can still be useful.

@mssimpso
Maybe just improving LICM could achieve the distribution of this loop, and then running loop-idiom would convert to memcpy.
I think since LICM does not use MemorySSA, it is unable to establish the invariance of load.

[DIVYA]

ping

[DIVYA]

ping

[hfinkel]

Two high-level thoughts:

1. Is this transformation always profitable even if we don't later vectorize? I worry that you're taking a stream of accesses that generally appear in order and making them appear out of order. That could have odd effects. Maybe this should all be a utility that the vectorizer uses more directly?
2. I don't think a goal of this should be to provide backup handling of things that LICM misses but MemorySSA can prove are loop invariant. We should improve LICM by making it use MemorySSA (see work on this in D35741 - pushing this along might help?). We could run LICM right before we vectorize too.

[hiraditya]

In D36113#849679, @hfinkel wrote:

Two high-level thoughts:

1. Is this transformation always profitable even if we don't later vectorize? I worry that you're taking a stream of accesses that generally appear in order and making them appear out of order. That could have odd effects. Maybe this should all be a utility that the vectorizer uses more directly?
2. I don't think a goal of this should be to provide backup handling of things that LICM misses but MemorySSA can prove are loop invariant. We should improve LICM by making it use MemorySSA (see work on this in D35741 - pushing this along might help?). We could run LICM right before we vectorize too.

Adding comments from @dberlin which got missed for some reason:

I'm definitely with Hal on the second point. We alreayd know there are deficiencies there, and the right way is to improve LICM.
If the goal is "move loop invariants", we want one pass that does that, not 6.

It's fine to have multiple passes when the job is so large that it can't sanely be done optimally by one thing, but i don't think this is ojne of those cases ....

[hiraditya]

In D36113#849679, @hfinkel wrote:

Two high-level thoughts:

1. Is this transformation always profitable even if we don't later vectorize? I worry that you're taking a stream of accesses that generally appear in order and making them appear out of order. That could have odd effects. Maybe this should all be a utility that the vectorizer uses more directly?

Agreed, we will evaluate if we can this pass as a utility for vectorizer. In the past we tried that but got stuck because we were unable to recompute loop-access-info once the instructions have been reordered. Maybe you can help us here.

2. I don't think a goal of this should be to provide backup handling of things that LICM misses but MemorySSA can prove are loop invariant. We should improve LICM by making it use MemorySSA (see work on this in D35741 - pushing this along might help?). We could run LICM right before we vectorize too.

The goal is to vectorize instructions by reordering, it just happens to catch cases missed by LICM. Once D35741 is merged, it will still catch cases currently missed by vectorizer e.g., when loads are not loop-invariant.

[DIVYA]

@hfinkel
we tried adding this patch to loop vectorizer. but after reordering the instructions, canVectorizeMemory() needs to be called again to check if it can now be vectorized.However,we are unable to recompute loop-access-info once the instructions have been reordered.So it stills holds the old loop-access-info(before reordering) and does not vectorize. Is is there any way to recompute loop-access-info after reordering the instructions?

[hfinkel]

In D36113#850469, @DIVYA wrote:

@hfinkel
we tried adding this patch to loop vectorizer. but after reordering the instructions, canVectorizeMemory() needs to be called again to check if it can now be vectorized.However,we are unable to recompute loop-access-info once the instructions have been reordered.So it stills holds the old loop-access-info(before reordering) and does not vectorize. Is is there any way to recompute loop-access-info after reordering the instructions?

Do you want to recompute the LAA, or just update it to remove the dependencies that you'll later remove when you generate the vectorized code? Ideally, the reordering would just become part of the vectorizartion plan (the vplan infrastructure is now committed). Maybe you can update the instruction ordering in the MemDepChecker's ordering map, and then have it recompute dependencies with the new ordering. We could have a corresponding ordering map in the vectorization plan as well.

lib/Transforms/Vectorize/LoopVectorize.cpp

if (VF > 1) {
     return VF * DL.getTypeAllocSize(Ty) != DL.getTypeStoreSize(VectorTy);
   }
 
   // If the vectorization factor is one, we just check if an array of type Ty
   // requires padding between elements.
   return DL.getTypeAllocSizeInBits(Ty) != DL.getTypeSizeInBits(Ty);
 }
 
-/// A helper function that returns the reciprocal of the block probability of
-/// predicated blocks. If we return X, we are assuming the predicated block
-/// will execute once for for every X iterations of the loop header.
-///
-/// TODO: We should use actual block probability here, if available. Currently,
-///       we always assume predicated blocks have a 50% chance of executing.
-static unsigned getReciprocalPredBlockProb() { return 2; }
-
 /// A helper function that adds a 'fast' flag to floating-point operations.
 static Value *addFastMathFlag(Value *V) {
   if (isa<FPMathOperator>(V)) {
     FastMathFlags Flags;
     Flags.setUnsafeAlgebra();
     cast<Instruction>(V)->setFastMathFlags(Flags);
   }
   return V;

 class LoopVectorizationCostModel {
 public:
   LoopVectorizationCostModel(Loop *L, PredicatedScalarEvolution &PSE,
                              LoopInfo *LI, LoopVectorizationLegality *Legal,
                              const TargetTransformInfo &TTI,
                              const TargetLibraryInfo *TLI, DemandedBits *DB,
                              AssumptionCache *AC,
                              OptimizationRemarkEmitter *ORE, const Function *F,
-                             const LoopVectorizeHints *Hints)
+                             const LoopVectorizeHints *Hints,
+                             BlockFrequencyInfo *BFI )
       : TheLoop(L), PSE(PSE), LI(LI), Legal(Legal), TTI(TTI), TLI(TLI), DB(DB),
-        AC(AC), ORE(ORE), TheFunction(F), Hints(Hints) {}
+        AC(AC), ORE(ORE), TheFunction(F), Hints(Hints), BFI(BFI) {}
 
   /// \return An upper bound for the vectorization factor, or None if
   /// vectorization should be avoided up front.
   Optional<unsigned> computeMaxVF(bool OptForSize);
 
   /// Information about vectorization costs
   struct VectorizationFactor {
     unsigned Width; // Vector width with best cost
bool isOptimizableIVTruncate(Instruction *I, unsigned VF) {
     Value *Op = Trunc->getOperand(0);
     if (Op != Legal->getPrimaryInduction() && TTI.isTruncateFree(SrcTy, DestTy))
       return false;
 
     // If the truncated value is not an induction variable, return false.
     return Legal->isInductionVariable(Op);
   }
 
+  /// Returns the reciprocal of the block probability of predicated blocks
+  /// If we return X, we are assuming the predicated block will execute
+  /// once for for every X iterations of the loop header.
+
+  unsigned getReciprocalPredBlockProb(BasicBlock *BB) {
+    if ((BFI->getBlockFreq(BB)).getFrequency() == 0 ||
+        (BFI->getBlockFreq(TheLoop->getHeader())).getFrequency() == 0)
+      return 2;
+    return (BFI->getBlockFreq(TheLoop->getHeader())).getFrequency() /
+           (BFI->getBlockFreq(BB)).getFrequency();
+  }
+
+
 private:
   /// \return An upper bound for the vectorization factor, larger than zero.
   /// One is returned if vectorization should best be avoided due to cost.
   unsigned computeFeasibleMaxVF(bool OptForSize);
 
   /// The vectorization cost is a combination of the cost itself and a boolean
   /// indicating whether any of the contributing operations will actually
   /// operate on
public:
   /// Assumption cache.
   AssumptionCache *AC;
   /// Interface to emit optimization remarks.
   OptimizationRemarkEmitter *ORE;
 
   const Function *TheFunction;
   /// Loop Vectorize Hint.
   const LoopVectorizeHints *Hints;
+  /// Block Frequency Info
+  BlockFrequencyInfo *BFI;
   /// Values to ignore in the cost model.
   SmallPtrSet<const Value *, 16> ValuesToIgnore;
   /// Values to ignore in the cost model when VF > 1.
   SmallPtrSet<const Value *, 16> VecValuesToIgnore;
 };
 
 /// LoopVectorizationPlanner - drives the vectorization process after having
 /// passed Legality checks.
for (Use &U : I->operands())
         if (canBeScalarized(J))
           Worklist.push_back(J);
         else if (needsExtract(J))
           ScalarCost += TTI.getScalarizationOverhead(
                               ToVectorTy(J->getType(),VF), false, true);
       }
 
     // Scale the total scalar cost by block probability.
-    ScalarCost /= getReciprocalPredBlockProb();
+    ScalarCost /= getReciprocalPredBlockProb(I->getParent());
 
     // Compute the discount. A non-negative discount means the vector version
     // of the instruction costs more, and scalarizing would be beneficial.
     Discount += VectorCost - ScalarCost;
     ScalarCosts[I] = ScalarCost;
   }
 
   return Discount;
for (BasicBlock *BB : TheLoop->blocks()) {
     }
 
     // If we are vectorizing a predicated block, it will have been
     // if-converted. This means that the block's instructions (aside from
     // stores and instructions that may divide by zero) will now be
     // unconditionally executed. For the scalar case, we may not always execute
     // the predicated block. Thus, scale the block's cost by the probability of
     // executing it.
-    if (VF == 1 && Legal->blockNeedsPredication(BB))
-      BlockCost.first /= getReciprocalPredBlockProb();
+    if (VF == 1 && Legal->blockNeedsPredication(BB)) {
+      BlockCost.first /= getReciprocalPredBlockProb(BB);
+      DEBUG(dbgs() << "LV: Found an estimated cost of " << BlockCost.first
+                   << " for VF " << VF << " For BasicBlock: " << BB->getName()
+                   << '\n');
+    }
+
 
     Cost.first += BlockCost.first;
     Cost.second |= BlockCost.second;
   }
 
   return Cost;
 }
 
unsigned LoopVectorizationCostModel::getMemInstScalarizationCost(Instruction *I,
   // Get the overhead of the extractelement and insertelement instructions
   // we might create due to scalarization.
   Cost += getScalarizationOverhead(I, VF, TTI);
 
   // If we have a predicated store, it may not be executed for each vector
   // lane. Scale the cost by the probability of executing the predicated
   // block.
   if (Legal->isScalarWithPredication(I))
-    Cost /= getReciprocalPredBlockProb();
+    Cost /= getReciprocalPredBlockProb(I->getParent());
 
   return Cost;
 }
 
 unsigned LoopVectorizationCostModel::getConsecutiveMemOpCost(Instruction *I,
                                                              unsigned VF) {
   Type *ValTy = getMemInstValueType(I);
   Type *VectorTy = ToVectorTy(ValTy, VF);
if (VF > 1 && Legal->isScalarWithPredication(I)) {
 
       // The cost of insertelement and extractelement instructions needed for
       // scalarization.
       Cost += getScalarizationOverhead(I, VF, TTI);
 
       // Scale the cost by the probability of executing the predicated blocks.
       // This assumes the predicated block for each vector lane is equally
       // likely.
-      return Cost / getReciprocalPredBlockProb();
+      return Cost / getReciprocalPredBlockProb(I->getParent());
     }
     LLVM_FALLTHROUGH;
   case Instruction::Add:
   case Instruction::FAdd:
   case Instruction::Sub:
   case Instruction::FSub:
   case Instruction::Mul:
   case Instruction::FMul:
ORE->emit(
         createMissedAnalysis(Hints.vectorizeAnalysisPassName(), "UnsafeFP", L)
         << "loop not vectorized due to unsafe FP support.");
     emitMissedWarning(F, L, Hints, ORE);
     return false;
   }
 
   // Use the cost model.
   LoopVectorizationCostModel CM(L, PSE, LI, &LVL, *TTI, TLI, DB, AC, ORE, F,
-                                &Hints);
+                                &Hints, BFI);
   CM.collectValuesToIgnore();
 
   // Use the planner for vectorization.
   LoopVectorizationPlanner LVP(L, LI, &LVL, CM);
 
   // Get user vectorization factor.
   unsigned UserVF = Hints.getWidth();
 

test/Transforms/LoopVectorize/AArch64/aarch64-predication.ll

 ; REQUIRES: asserts
 ; RUN: opt < %s -loop-vectorize -disable-output -debug-only=loop-vectorize 2>&1 | FileCheck %s --check-prefix=COST
 ; RUN: opt < %s -loop-vectorize -force-vector-width=2 -instcombine -simplifycfg -S | FileCheck %s
 
 target datalayout = "e-m:e-i64:64-i128:128-n32:64-S128"
 target triple = "aarch64--linux-gnu"
 
 ; This test checks that we correctly compute the scalarized operands for a
 ; user-specified vectorization factor when interleaving is disabled. We use the
 ; "optsize" attribute to disable all interleaving calculations.  A cost of 4
 ; for %tmp4 indicates that we would scalarize it's operand (%tmp3), giving
 ; %tmp4 a lower scalarization overhead.
 ;
 ; COST-LABEL:  predicated_udiv_scalarized_operand
-; COST:        LV: Found an estimated cost of 4 for VF 2 For instruction: %tmp4 = udiv i64 %tmp2, %tmp3
+; COST:        LV: Found an estimated cost of 11 for VF 2 For instruction: %tmp4 = udiv i64 %tmp2, %tmp3
 ;
 ; CHECK-LABEL: @predicated_udiv_scalarized_operand(
 ; CHECK:       vector.body:
 ; CHECK-NEXT:    [[INDEX:%.*]] = phi i64 [ 0, %entry ], [ [[INDEX_NEXT:%.*]], %[[PRED_UDIV_CONTINUE2:.*]] ]
 ; CHECK-NEXT:    [[VEC_PHI:%.*]] = phi <2 x i64> [ zeroinitializer, %entry ], [ [[TMP17:%.*]], %[[PRED_UDIV_CONTINUE2]] ]
 ; CHECK-NEXT:    [[TMP0:%.*]] = getelementptr inbounds i64, i64* %a, i64 [[INDEX]]
 ; CHECK-NEXT:    [[TMP1:%.*]] = bitcast i64* [[TMP0]] to <2 x i64>*
 ; CHECK-NEXT:    [[WIDE_LOAD:%.*]] = load <2 x i64>, <2 x i64>* [[TMP1]], align 4
 ; CHECK-NEXT:    [[TMP2:%.*]] = icmp sgt <2 x i64> [[WIDE_LOAD]], zeroinitializer
+; CHECK-NEXT:    [[TMP6:%.*]] = add nsw <2 x i64> [[WIDE_LOAD]], %broadcast.splat2
 ; CHECK-NEXT:    [[TMP3:%.*]] = extractelement <2 x i1> [[TMP2]], i32 0
 ; CHECK-NEXT:    br i1 [[TMP3]], label %[[PRED_UDIV_IF:.*]], label %[[PRED_UDIV_CONTINUE:.*]]
 ; CHECK:       [[PRED_UDIV_IF]]:
 ; CHECK-NEXT:    [[TMP4:%.*]] = extractelement <2 x i64> [[WIDE_LOAD]], i32 0
-; CHECK-NEXT:    [[TMP5:%.*]] = extractelement <2 x i64> [[WIDE_LOAD]], i32 0
-; CHECK-NEXT:    [[TMP6:%.*]] = add nsw i64 [[TMP5]], %x
-; CHECK-NEXT:    [[TMP7:%.*]] = udiv i64 [[TMP4]], [[TMP6]]
+; CHECK-NEXT:    [[TMP5:%.*]] = extractelement <2 x i64> [[TMP6]], i32 0
+; CHECK-NEXT:    [[TMP7:%.*]] = udiv i64 [[TMP4]], [[TMP5]]
 ; CHECK-NEXT:    [[TMP8:%.*]] = insertelement <2 x i64> undef, i64 [[TMP7]], i32 0
 ; CHECK-NEXT:    br label %[[PRED_UDIV_CONTINUE]]
 ; CHECK:       [[PRED_UDIV_CONTINUE]]:
 ; CHECK-NEXT:    [[TMP9:%.*]] = phi <2 x i64> [ undef, %vector.body ], [ [[TMP8]], %[[PRED_UDIV_IF]] ]
 ; CHECK-NEXT:    [[TMP10:%.*]] = extractelement <2 x i1> [[TMP2]], i32 1
 ; CHECK-NEXT:    br i1 [[TMP10]], label %[[PRED_UDIV_IF1:.*]], label %[[PRED_UDIV_CONTINUE2]]
 ; CHECK:       [[PRED_UDIV_IF1]]:
 ; CHECK-NEXT:    [[TMP11:%.*]] = extractelement <2 x i64> [[WIDE_LOAD]], i32 1
-; CHECK-NEXT:    [[TMP12:%.*]] = extractelement <2 x i64> [[WIDE_LOAD]], i32 1
-; CHECK-NEXT:    [[TMP13:%.*]] = add nsw i64 [[TMP12]], %x
-; CHECK-NEXT:    [[TMP14:%.*]] = udiv i64 [[TMP11]], [[TMP13]]
+; CHECK-NEXT:    [[TMP12:%.*]] = extractelement <2 x i64> [[TMP6]], i32 1
+; CHECK-NEXT:    [[TMP14:%.*]] = udiv i64 [[TMP11]], [[TMP12]]
 ; CHECK-NEXT:    [[TMP15:%.*]] = insertelement <2 x i64> [[TMP9]], i64 [[TMP14]], i32 1
 ; CHECK-NEXT:    br label %[[PRED_UDIV_CONTINUE2]]
 ; CHECK:       [[PRED_UDIV_CONTINUE2]]:
 ; CHECK-NEXT:    [[TMP16:%.*]] = phi <2 x i64> [ [[TMP9]], %[[PRED_UDIV_CONTINUE]] ], [ [[TMP15]], %[[PRED_UDIV_IF1]] ]
 ; CHECK-NEXT:    [[PREDPHI:%.*]] = select <2 x i1> [[TMP2]], <2 x i64> [[TMP16]], <2 x i64> [[WIDE_LOAD]]
 ; CHECK-NEXT:    [[TMP17]] = add <2 x i64> [[VEC_PHI]], [[PREDPHI]]
 ; CHECK-NEXT:    [[INDEX_NEXT]] = add i64 [[INDEX]], 2
 ; CHECK:         br i1 {{.*}}, label %middle.block, label %vector.body

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

+; RUN: opt < %s -loop-vectorize -disable-output -debug-only=loop-vectorize 2>&1 | FileCheck %s --check-prefix=COST
+
+target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64-S128"
+
+
+@a = global i32* null, align 8
+@b = global i32* null, align 8
+@c = global i32* null, align 8
+
+; This test checks that the frequency of the predicated block(for computing the cost)
+; is obtained from BlockFrequencyInfo Class
+; COST-LABEL: foo
+; COST:       LV: Found an estimated cost of 4 for VF 1 For BasicBlock: if.then3.i
+
+
+define void @foo(i32 %p1) {
+entry:
+  %cmp88 = icmp sgt i32 %p1, 0
+  br i1 %cmp88, label %for.body.lr.ph, label %for.end
+
+for.body.lr.ph:
+  %0 = load i32*, i32** @b, align 8
+  %1 = load i32*, i32** @a, align 8
+  %2 = load i32*, i32** @c, align 8
+  br label %for.body
+
+for.body:
+  %indvars.iv = phi i64 [ 0, %for.body.lr.ph ], [ %indvars.iv.next, %if.end3.i ]
+  %arrayidx = getelementptr inbounds i32, i32* %0, i64 %indvars.iv
+  %3 = load i32, i32* %arrayidx, align 4  %4 = trunc i64 %indvars.iv to i32
+  %and.i = and i32 %4, 1
+  %tobool.i.i = icmp eq i32 %and.i, 0
+  br i1 %tobool.i.i, label %if.end.i, label %if.then.i
+
+if.then.i:
+  %and.i.i = lshr i32 %3, 2
+  %cmp.i = icmp sgt i32 %and.i.i, 0
+  %conv.i = zext i1 %cmp.i to i32
+  br label %if.end.i
+
+if.end.i:
+  %p1.addr.0.i = phi i32 [ %conv.i, %if.then.i ], [ %3, %for.body ]
+  %5 = trunc i64 %indvars.iv to i32
+  %and1.i = and i32 %5, 7
+  %tobool2.i = icmp eq i32 %and1.i, 0
+  br i1 %tobool2.i, label  %if.end3.i, label %if.then3.i
+
+if.then3.i:
+  %p1.addr.0.lobit.i = lshr i32 %p1.addr.0.i, 31
+  %and6.i = and i32 %p1.addr.0.i, 1
+  %or.i = or i32 %p1.addr.0.lobit.i, %and6.i
+  br label %if.end3.i
+
+if.end3.i:
+%p1.addr.1.i = phi i32 [ %or.i, %if.then3.i ], [ %p1.addr.0.i, %if.end.i ]
+
+  %6 = trunc i64 %indvars.iv to i32
+  %shr.i = ashr i32 %6, 1
+  %arrayidx7 = getelementptr inbounds i32, i32* %2, i64 %indvars.iv
+  store i32 %p1.addr.1.i, i32* %arrayidx7, align 4  %indvars.iv.next = add i64 %indvars.iv, 1
+  %lftr.wideiv = trunc i64 %indvars.iv.next to i32
+  %exitcond = icmp ne i32 %lftr.wideiv, %p1
+  br i1 %exitcond, label %for.body, label %for.cond.for.end_crit_edge
+
+for.cond.for.end_crit_edge:
+  br label %for.end
+
+for.end:
+  ret void
+}