From 16a2253e4011d27a9426f81f55501fd5dfb863bd Mon Sep 17 00:00:00 2001 From: Arnold Schwaighofer Date: Tue, 20 Aug 2013 21:21:45 +0000 Subject: [PATCH] SLPVectorizer: Fix invalid iterator errors Update iterator when the SLP vectorizer changes the instructions in the basic block by restarting the traversal of the basic block. Patch by Yi Jiang! Fixes PR 16899. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@188832 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Transforms/Vectorize/SLPVectorizer.cpp | 64 ++++++++++++++++---- test/Transforms/SLPVectorizer/X86/pr16899.ll | 30 +++++++++ 2 files changed, 81 insertions(+), 13 deletions(-) create mode 100644 test/Transforms/SLPVectorizer/X86/pr16899.ll diff --git a/lib/Transforms/Vectorize/SLPVectorizer.cpp b/lib/Transforms/Vectorize/SLPVectorizer.cpp index ee9c5f2de7d..3c24af8d8b6 100644 --- a/lib/Transforms/Vectorize/SLPVectorizer.cpp +++ b/lib/Transforms/Vectorize/SLPVectorizer.cpp @@ -1875,6 +1875,8 @@ bool SLPVectorizer::tryToVectorize(BinaryOperator *V, BoUpSLP &R) { bool SLPVectorizer::vectorizeChainsInBlock(BasicBlock *BB, BoUpSLP &R) { bool Changed = false; SmallVector Incoming; + SmallSet VisitedInstrs; + // Collect the incoming values from the PHIs. for (BasicBlock::iterator instr = BB->begin(), ie = BB->end(); instr != ie; ++instr) { @@ -1883,9 +1885,21 @@ bool SLPVectorizer::vectorizeChainsInBlock(BasicBlock *BB, BoUpSLP &R) { if (!P) break; + // We may go through BB multiple times so skip the one we have checked. + if (VisitedInstrs.count(instr)) + continue; + VisitedInstrs.insert(instr); + // Stop constructing the list when you reach a different type. if (Incoming.size() && P->getType() != Incoming[0]->getType()) { - Changed |= tryToVectorizeList(Incoming, R); + if (tryToVectorizeList(Incoming, R)) { + // We would like to start over since some instructions are deleted + // and the iterator may become invalid value. + Changed = true; + instr = BB->begin(); + ie = BB->end(); + } + Incoming.clear(); } @@ -1895,14 +1909,20 @@ bool SLPVectorizer::vectorizeChainsInBlock(BasicBlock *BB, BoUpSLP &R) { if (Incoming.size() > 1) Changed |= tryToVectorizeList(Incoming, R); - llvm::Instruction *I; - for (BasicBlock::iterator it = BB->begin(), e = BB->end(); it != e;) { - I = it++; - if (isa(I)) + VisitedInstrs.clear(); + + for (BasicBlock::iterator it = BB->begin(), e = BB->end(); it != e; it++) { + + // We may go through BB multiple times so skip the one we have checked. + if (VisitedInstrs.count(it)) + continue; + VisitedInstrs.insert(it); + + if (isa(it)) continue; // Try to vectorize reductions that use PHINodes. - if (PHINode *P = dyn_cast(I)) { + if (PHINode *P = dyn_cast(it)) { // Check that the PHI is a reduction PHI. if (P->getNumIncomingValues() != 2) return Changed; @@ -1919,20 +1939,38 @@ bool SLPVectorizer::vectorizeChainsInBlock(BasicBlock *BB, BoUpSLP &R) { if (Inst == P) Inst = BI->getOperand(1); - Changed |= tryToVectorize(dyn_cast(Inst), R); + if (tryToVectorize(dyn_cast(Inst), R)) { + // We would like to start over since some instructions are deleted + // and the iterator may become invalid value. + Changed = true; + it = BB->begin(); + e = BB->end(); + } continue; } // Try to vectorize trees that start at compare instructions. - if (CmpInst *CI = dyn_cast(I)) { + if (CmpInst *CI = dyn_cast(it)) { if (tryToVectorizePair(CI->getOperand(0), CI->getOperand(1), R)) { - Changed |= true; + Changed = true; + // We would like to start over since some instructions are deleted + // and the iterator may become invalid value. + it = BB->begin(); + e = BB->end(); continue; } - for (int i = 0; i < 2; ++i) - if (BinaryOperator *BI = dyn_cast(CI->getOperand(i))) - Changed |= - tryToVectorizePair(BI->getOperand(0), BI->getOperand(1), R); + + for (int i = 0; i < 2; ++i) { + if (BinaryOperator *BI = dyn_cast(CI->getOperand(i))) { + if (tryToVectorizePair(BI->getOperand(0), BI->getOperand(1), R)) { + Changed = true; + // We would like to start over since some instructions are deleted + // and the iterator may become invalid value. + it = BB->begin(); + e = BB->end(); + } + } + } continue; } } diff --git a/test/Transforms/SLPVectorizer/X86/pr16899.ll b/test/Transforms/SLPVectorizer/X86/pr16899.ll new file mode 100644 index 00000000000..d7152395694 --- /dev/null +++ b/test/Transforms/SLPVectorizer/X86/pr16899.ll @@ -0,0 +1,30 @@ +; RUN: opt < %s -slp-vectorizer -S -mtriple=i386--netbsd -mcpu=i486 +target datalayout = "e-p:32:32:32-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:32:64-f32:32:32-f64:32:64-v64:64:64-v128:128:128-a0:0:64-f80:32:32-n8:16:32-S128" +target triple = "i386--netbsd" + +@a = common global i32* null, align 4 + +; Function Attrs: noreturn nounwind readonly +define i32 @fn1() #0 { +entry: + %0 = load i32** @a, align 4, !tbaa !0 + %1 = load i32* %0, align 4, !tbaa !3 + %arrayidx1 = getelementptr inbounds i32* %0, i32 1 + %2 = load i32* %arrayidx1, align 4, !tbaa !3 + br label %do.body + +do.body: ; preds = %do.body, %entry + %c.0 = phi i32 [ %2, %entry ], [ %add2, %do.body ] + %b.0 = phi i32 [ %1, %entry ], [ %add, %do.body ] + %add = add nsw i32 %b.0, %c.0 + %add2 = add nsw i32 %add, 1 + br label %do.body +} + +attributes #0 = { noreturn nounwind readonly "less-precise-fpmad"="false" "no-frame-pointer-elim"="true" "no-frame-pointer-elim-non-leaf"="true" "no-infs-fp-math"="false" "no-nans-fp-math"="false" "stack-protector-buffer-size"="8" "unsafe-fp-math"="false" "use-soft-float"="false" } + +!0 = metadata !{metadata !"any pointer", metadata !1} +!1 = metadata !{metadata !"omnipotent char", metadata !2} +!2 = metadata !{metadata !"Simple C/C++ TBAA"} +!3 = metadata !{metadata !"int", metadata !1} + -- 2.34.1