Index: lib/Transforms/Vectorize/LoopVectorize.cpp =================================================================== --- lib/Transforms/Vectorize/LoopVectorize.cpp +++ lib/Transforms/Vectorize/LoopVectorize.cpp @@ -1427,10 +1427,9 @@ const TargetLibraryInfo *TLI, DemandedBits *DB, AssumptionCache *AC, const Function *F, const LoopVectorizeHints *Hints, - SmallPtrSetImpl &ValuesToIgnore, SCEVUnionPredicate &Preds) : TheLoop(L), SE(SE), LI(LI), Legal(Legal), TTI(TTI), TLI(TLI), DB(DB), - TheFunction(F), Hints(Hints), ValuesToIgnore(ValuesToIgnore) {} + AC(AC), TheFunction(F), Hints(Hints) {} /// Information about vectorization costs struct VectorizationFactor { @@ -1478,6 +1477,9 @@ SmallVector calculateRegisterUsage(const SmallVector &VFs); + /// Collect values we want to ignore in the cost model. + void collectValuesToIgnore(); + private: /// Returns the expected execution cost. The unit of the cost does /// not matter because we use the 'cost' units to compare different @@ -1521,11 +1523,12 @@ const TargetLibraryInfo *TLI; /// Demanded bits analysis DemandedBits *DB; + AssumptionCache *AC; const Function *TheFunction; - // Loop Vectorize Hint. + /// Loop Vectorize Hint. const LoopVectorizeHints *Hints; - // Values to ignore in the cost model. - const SmallPtrSetImpl &ValuesToIgnore; + /// Values to ignore in the cost model. + SmallPtrSet ValuesToIgnore; }; /// \brief This holds vectorization requirements that must be verified late in @@ -1770,19 +1773,10 @@ return false; } - // Collect values we want to ignore in the cost model. This includes - // type-promoting instructions we identified during reduction detection. - SmallPtrSet ValuesToIgnore; - CodeMetrics::collectEphemeralValues(L, AC, ValuesToIgnore); - for (auto &Reduction : *LVL.getReductionVars()) { - RecurrenceDescriptor &RedDes = Reduction.second; - SmallPtrSetImpl &Casts = RedDes.getCastInsts(); - ValuesToIgnore.insert(Casts.begin(), Casts.end()); - } - // Use the cost model. LoopVectorizationCostModel CM(L, SE, LI, &LVL, *TTI, TLI, DB, AC, F, &Hints, - ValuesToIgnore, Preds); + Preds); + CM.collectValuesToIgnore(); // Check the function attributes to find out if this function should be // optimized for size. @@ -5172,15 +5166,15 @@ // Ignore instructions that are never used within the loop. if (!Ends.count(I)) continue; - // Skip ignored values. - if (ValuesToIgnore.count(I)) - continue; - // Remove all of the instructions that end at this location. InstrList &List = TransposeEnds[i]; for (unsigned int j = 0, e = List.size(); j < e; ++j) OpenIntervals.erase(List[j]); + // Skip ignored values. + if (ValuesToIgnore.count(I)) + continue; + // For each VF find the maximum usage of registers. for (unsigned j = 0, e = VFs.size(); j < e; ++j) { if (VFs[j] == 1) { @@ -5636,6 +5630,67 @@ return false; } +void LoopVectorizationCostModel::collectValuesToIgnore() { + // Ignore ephemeral values. + CodeMetrics::collectEphemeralValues(TheLoop, AC, ValuesToIgnore); + + // Ignore type-promoting instructions we identified during reduction + // detection. + for (auto &Reduction : *Legal->getReductionVars()) { + RecurrenceDescriptor &RedDes = Reduction.second; + SmallPtrSetImpl &Casts = RedDes.getCastInsts(); + ValuesToIgnore.insert(Casts.begin(), Casts.end()); + } + + // Ignore induction phis that are only used in either GetElementPtr or ICmp + // instruction to exit loop. Induction variables usually have large types and + // can have big impact when estimating register usage. + for (auto &Induction : *Legal->getInductionVars()) { + int UserNum = 0; + Instruction *IncrInst = nullptr; + for (User *U : Induction.first->users()) { + Instruction *UI = cast(U); + if (UI && UI->getOpcode() == Instruction::GetElementPtr) + continue; + IncrInst = UI; + UserNum++; + } + + // We only allow one user of each induction phi other than GetElementPtr + // instructions, which updates the induction variable. + if (UserNum == 1) { + ValuesToIgnore.insert(Induction.first); + + // If the update instruction is only used in one comparison instruction + // and the induction phi, we also want to ignore it. + bool IncrInstToIgnore = true; + int UserNum = 0; + for (User *U : IncrInst->users()) { + Instruction *UI = cast(U); + if (!UI || (UI->getOpcode() != Instruction::PHI && + UI->getOpcode() != Instruction::ICmp)) { + IncrInstToIgnore = false; + break; + } + UserNum++; + } + if (IncrInstToIgnore && UserNum == 2) + ValuesToIgnore.insert(IncrInst); + } + } + + // Ignore instructions that will not be vectorized. + for (auto bb = TheLoop->block_begin(), be = TheLoop->block_end(); bb != be; + ++bb) { + for (auto &Inst : **bb) { + switch (Inst.getOpcode()) { + case Instruction::GetElementPtr: + ValuesToIgnore.insert(&Inst); + break; + } + } + } +} void InnerLoopUnroller::scalarizeInstruction(Instruction *Instr, bool IfPredicateStore) { Index: test/Transforms/LoopVectorize/X86/vector_max_bandwidth.ll =================================================================== --- test/Transforms/LoopVectorize/X86/vector_max_bandwidth.ll +++ test/Transforms/LoopVectorize/X86/vector_max_bandwidth.ll @@ -16,7 +16,7 @@ ; -vectorizer-maximize-bandwidth is indicated. ; ; CHECK-label: foo -; CHECK: LV: Selecting VF: 16. +; CHECK: LV: Selecting VF: 32. define void @foo() { entry: br label %for.body Index: test/Transforms/LoopVectorize/reg-usage.ll =================================================================== --- /dev/null +++ test/Transforms/LoopVectorize/reg-usage.ll @@ -0,0 +1,68 @@ +; RUN: opt < %s -mtriple=x86_64-unknown-unknown -mattr=+sse2 -debug-only=loop-vectorize -loop-vectorize -vectorizer-maximize-bandwidth 2>&1 | FileCheck %s + + +@a = global [1024 x i8] zeroinitializer, align 16 +@b = global [1024 x i8] zeroinitializer, align 16 + +define i32 @foo() { +; This function has a loop of SAD pattern. Here we check when VF = 16 the +; register usage doesn't exceed 16. +; +; CHECK-LABEL: foo +; CHECK: LV(REG): VF = 4 +; CHECK-NEXT: LV(REG): Found max usage: 4 +; CHECK: LV(REG): VF = 8 +; CHECK-NEXT: LV(REG): Found max usage: 7 +; CHECK: LV(REG): VF = 16 +; CHECK-NEXT: LV(REG): Found max usage: 13 + +entry: + br label %for.body + +for.cond.cleanup: + %add.lcssa = phi i32 [ %add, %for.body ] + ret i32 %add.lcssa + +for.body: + %indvars.iv = phi i64 [ 0, %entry ], [ %indvars.iv.next, %for.body ] + %s.015 = phi i32 [ 0, %entry ], [ %add, %for.body ] + %arrayidx = getelementptr inbounds [1024 x i8], [1024 x i8]* @a, i64 0, i64 %indvars.iv + %0 = load i8, i8* %arrayidx, align 1 + %conv = zext i8 %0 to i32 + %arrayidx2 = getelementptr inbounds [1024 x i8], [1024 x i8]* @b, i64 0, i64 %indvars.iv + %1 = load i8, i8* %arrayidx2, align 1 + %conv3 = zext i8 %1 to i32 + %sub = sub nsw i32 %conv, %conv3 + %ispos = icmp sgt i32 %sub, -1 + %neg = sub nsw i32 0, %sub + %2 = select i1 %ispos, i32 %sub, i32 %neg + %add = add nsw i32 %2, %s.015 + %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1 + %exitcond = icmp eq i64 %indvars.iv.next, 1024 + br i1 %exitcond, label %for.cond.cleanup, label %for.body +} + +define i64 @bar(i64* nocapture %a) { +; CHECK-LABEL: bar +; CHECK: LV(REG): VF = 2 +; CHECK: LV(REG): Found max usage: 4 +; +entry: + br label %for.body + +for.cond.cleanup: + %add2.lcssa = phi i64 [ %add2, %for.body ] + ret i64 %add2.lcssa + +for.body: + %i.012 = phi i64 [ 0, %entry ], [ %inc, %for.body ] + %s.011 = phi i64 [ 0, %entry ], [ %add2, %for.body ] + %arrayidx = getelementptr inbounds i64, i64* %a, i64 %i.012 + %0 = load i64, i64* %arrayidx, align 8 + %add = add nsw i64 %0, %i.012 + store i64 %add, i64* %arrayidx, align 8 + %add2 = add nsw i64 %add, %s.011 + %inc = add nuw nsw i64 %i.012, 1 + %exitcond = icmp eq i64 %inc, 1024 + br i1 %exitcond, label %for.cond.cleanup, label %for.body +}