Author: hans Date: Mon Aug 15 11:06:31 2016 New Revision: 278674 URL: http://llvm.org/viewvc/llvm-project?rev=278674&view=rev Log: Merging r278573 (and r277399, r278157, r278569):
------------------------------------------------------------------------ r278573 | timshen | 2016-08-12 15:47:13 -0700 (Fri, 12 Aug 2016) | 8 lines [LoopVectorize] Detect loops in the innermost loop before creating InnerLoopVectorizer InnerLoopVectorizer shouldn't handle a loop with cycles inside the loop body, even if that cycle isn't a natural loop. Fixes PR28541. Differential Revision: https://reviews.llvm.org/D22952 ------------------------------------------------------------------------ ------------------------------------------------------------------------ r277399 | timshen | 2016-08-01 15:32:20 -0700 (Mon, 01 Aug 2016) | 9 lines [ADT] NFC: Generalize GraphTraits requirement of "NodeType *" in interfaces to "NodeRef", and migrate SCCIterator.h to use NodeRef Summary: By generalize the interface, users are able to inject more flexible Node token into the algorithm, for example, a pair of vector<Node>* and index integer. Currently I only migrated SCCIterator to use NodeRef, but more is coming. It's a NFC. Reviewers: dblaikie, chandlerc Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D22937 ------------------------------------------------------------------------ ------------------------------------------------------------------------ r278157 | timshen | 2016-08-09 13:23:13 -0700 (Tue, 09 Aug 2016) | 7 lines [ADT] Change iterator_adaptor_base's default template arguments to forward more underlying typedefs Reviewers: chandlerc Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D23217 ------------------------------------------------------------------------ ------------------------------------------------------------------------ r278569 | timshen | 2016-08-12 15:03:28 -0700 (Fri, 12 Aug 2016) | 3 lines [ADT] Add filter_iterator for filtering elements Differential Revision: https://reviews.llvm.org/D22951 ------------------------------------------------------------------------ Added: llvm/branches/release_39/test/Transforms/LoopVectorize/pr28541.ll - copied unchanged from r278573, llvm/trunk/test/Transforms/LoopVectorize/pr28541.ll Modified: llvm/branches/release_39/ (props changed) llvm/branches/release_39/include/llvm/ADT/GraphTraits.h llvm/branches/release_39/include/llvm/ADT/SCCIterator.h llvm/branches/release_39/include/llvm/ADT/STLExtras.h llvm/branches/release_39/include/llvm/ADT/iterator.h llvm/branches/release_39/include/llvm/Analysis/CallGraph.h llvm/branches/release_39/include/llvm/CodeGen/MachineBasicBlock.h llvm/branches/release_39/include/llvm/IR/CFG.h llvm/branches/release_39/lib/Analysis/BlockFrequencyInfoImpl.cpp llvm/branches/release_39/lib/Transforms/IPO/FunctionAttrs.cpp llvm/branches/release_39/lib/Transforms/Vectorize/LoopVectorize.cpp llvm/branches/release_39/unittests/ADT/SCCIteratorTest.cpp llvm/branches/release_39/unittests/Support/IteratorTest.cpp Propchange: llvm/branches/release_39/ ------------------------------------------------------------------------------ --- svn:mergeinfo (original) +++ svn:mergeinfo Mon Aug 15 11:06:31 2016 @@ -1,3 +1,3 @@ /llvm/branches/Apple/Pertwee:110850,110961 /llvm/branches/type-system-rewrite:133420-134817 -/llvm/trunk:155241,275868-275870,275879,275898,275928,275935,275946,275978,275981,276015,276051,276077,276109,276119,276181,276209,276236-276237,276358,276364,276368,276389,276435,276438,276479,276510,276648,276676,276712,276740,276823,276956,276980,277093,277114,277135,277371,277500,277504,277625,277691,277693,277773,278002,278086,278133,278370,278413 +/llvm/trunk:155241,275868-275870,275879,275898,275928,275935,275946,275978,275981,276015,276051,276077,276109,276119,276181,276209,276236-276237,276358,276364,276368,276389,276435,276438,276479,276510,276648,276676,276712,276740,276823,276956,276980,277093,277114,277135,277371,277399,277500,277504,277625,277691,277693,277773,278002,278086,278133,278157,278370,278413,278569,278573 Modified: llvm/branches/release_39/include/llvm/ADT/GraphTraits.h URL: http://llvm.org/viewvc/llvm-project/llvm/branches/release_39/include/llvm/ADT/GraphTraits.h?rev=278674&r1=278673&r2=278674&view=diff ============================================================================== --- llvm/branches/release_39/include/llvm/ADT/GraphTraits.h (original) +++ llvm/branches/release_39/include/llvm/ADT/GraphTraits.h Mon Aug 15 11:06:31 2016 @@ -27,19 +27,24 @@ template<class GraphType> struct GraphTraits { // Elements to provide: + // NOTICE: We are in a transition from migration interfaces that require + // NodeType *, to NodeRef. NodeRef is required to be cheap to copy, but does + // not have to be a raw pointer. In the transition, user should define + // NodeType, and NodeRef = NodeType *. + // // typedef NodeType - Type of Node in the graph + // typedef NodeRef - NodeType * // typedef ChildIteratorType - Type used to iterate over children in graph - // static NodeType *getEntryNode(const GraphType &) + // static NodeRef getEntryNode(const GraphType &) // Return the entry node of the graph - // static ChildIteratorType child_begin(NodeType *) - // static ChildIteratorType child_end (NodeType *) + // static ChildIteratorType child_begin(NodeRef) + // static ChildIteratorType child_end (NodeRef) // Return iterators that point to the beginning and ending of the child // node list for the specified node. // - // typedef ...iterator nodes_iterator; // static nodes_iterator nodes_begin(GraphType *G) // static nodes_iterator nodes_end (GraphType *G) @@ -57,7 +62,7 @@ struct GraphTraits { // your argument to XXX_begin(...) is unknown or needs to have the proper .h // file #include'd. // - typedef typename GraphType::UnknownGraphTypeError NodeType; + typedef typename GraphType::UnknownGraphTypeError NodeRef; }; Modified: llvm/branches/release_39/include/llvm/ADT/SCCIterator.h URL: http://llvm.org/viewvc/llvm-project/llvm/branches/release_39/include/llvm/ADT/SCCIterator.h?rev=278674&r1=278673&r2=278674&view=diff ============================================================================== --- llvm/branches/release_39/include/llvm/ADT/SCCIterator.h (original) +++ llvm/branches/release_39/include/llvm/ADT/SCCIterator.h Mon Aug 15 11:06:31 2016 @@ -37,23 +37,22 @@ namespace llvm { /// build up a vector of nodes in a particular SCC. Note that it is a forward /// iterator and thus you cannot backtrack or re-visit nodes. template <class GraphT, class GT = GraphTraits<GraphT>> -class scc_iterator - : public iterator_facade_base< - scc_iterator<GraphT, GT>, std::forward_iterator_tag, - const std::vector<typename GT::NodeType *>, ptrdiff_t> { - typedef typename GT::NodeType NodeType; +class scc_iterator : public iterator_facade_base< + scc_iterator<GraphT, GT>, std::forward_iterator_tag, + const std::vector<typename GT::NodeRef>, ptrdiff_t> { + typedef typename GT::NodeRef NodeRef; typedef typename GT::ChildIteratorType ChildItTy; - typedef std::vector<NodeType *> SccTy; + typedef std::vector<NodeRef> SccTy; typedef typename scc_iterator::reference reference; /// Element of VisitStack during DFS. struct StackElement { - NodeType *Node; ///< The current node pointer. + NodeRef Node; ///< The current node pointer. ChildItTy NextChild; ///< The next child, modified inplace during DFS. unsigned MinVisited; ///< Minimum uplink value of all children of Node. - StackElement(NodeType *Node, const ChildItTy &Child, unsigned Min) - : Node(Node), NextChild(Child), MinVisited(Min) {} + StackElement(NodeRef Node, const ChildItTy &Child, unsigned Min) + : Node(Node), NextChild(Child), MinVisited(Min) {} bool operator==(const StackElement &Other) const { return Node == Other.Node && @@ -67,10 +66,10 @@ class scc_iterator /// /// nodeVisitNumbers are per-node visit numbers, also used as DFS flags. unsigned visitNum; - DenseMap<NodeType *, unsigned> nodeVisitNumbers; + DenseMap<NodeRef, unsigned> nodeVisitNumbers; /// Stack holding nodes of the SCC. - std::vector<NodeType *> SCCNodeStack; + std::vector<NodeRef> SCCNodeStack; /// The current SCC, retrieved using operator*(). SccTy CurrentSCC; @@ -80,7 +79,7 @@ class scc_iterator std::vector<StackElement> VisitStack; /// A single "visit" within the non-recursive DFS traversal. - void DFSVisitOne(NodeType *N); + void DFSVisitOne(NodeRef N); /// The stack-based DFS traversal; defined below. void DFSVisitChildren(); @@ -88,7 +87,7 @@ class scc_iterator /// Compute the next SCC using the DFS traversal. void GetNextSCC(); - scc_iterator(NodeType *entryN) : visitNum(0) { + scc_iterator(NodeRef entryN) : visitNum(0) { DFSVisitOne(entryN); GetNextSCC(); } @@ -131,7 +130,7 @@ public: /// This informs the \c scc_iterator that the specified \c Old node /// has been deleted, and \c New is to be used in its place. - void ReplaceNode(NodeType *Old, NodeType *New) { + void ReplaceNode(NodeRef Old, NodeRef New) { assert(nodeVisitNumbers.count(Old) && "Old not in scc_iterator?"); nodeVisitNumbers[New] = nodeVisitNumbers[Old]; nodeVisitNumbers.erase(Old); @@ -139,7 +138,7 @@ public: }; template <class GraphT, class GT> -void scc_iterator<GraphT, GT>::DFSVisitOne(NodeType *N) { +void scc_iterator<GraphT, GT>::DFSVisitOne(NodeRef N) { ++visitNum; nodeVisitNumbers[N] = visitNum; SCCNodeStack.push_back(N); @@ -155,8 +154,8 @@ void scc_iterator<GraphT, GT>::DFSVisitC assert(!VisitStack.empty()); while (VisitStack.back().NextChild != GT::child_end(VisitStack.back().Node)) { // TOS has at least one more child so continue DFS - NodeType *childN = *VisitStack.back().NextChild++; - typename DenseMap<NodeType *, unsigned>::iterator Visited = + NodeRef childN = *VisitStack.back().NextChild++; + typename DenseMap<NodeRef, unsigned>::iterator Visited = nodeVisitNumbers.find(childN); if (Visited == nodeVisitNumbers.end()) { // this node has never been seen. @@ -176,7 +175,7 @@ template <class GraphT, class GT> void s DFSVisitChildren(); // Pop the leaf on top of the VisitStack. - NodeType *visitingN = VisitStack.back().Node; + NodeRef visitingN = VisitStack.back().Node; unsigned minVisitNum = VisitStack.back().MinVisited; assert(VisitStack.back().NextChild == GT::child_end(visitingN)); VisitStack.pop_back(); @@ -212,7 +211,7 @@ bool scc_iterator<GraphT, GT>::hasLoop() assert(!CurrentSCC.empty() && "Dereferencing END SCC iterator!"); if (CurrentSCC.size() > 1) return true; - NodeType *N = CurrentSCC.front(); + NodeRef N = CurrentSCC.front(); for (ChildItTy CI = GT::child_begin(N), CE = GT::child_end(N); CI != CE; ++CI) if (*CI == N) Modified: llvm/branches/release_39/include/llvm/ADT/STLExtras.h URL: http://llvm.org/viewvc/llvm-project/llvm/branches/release_39/include/llvm/ADT/STLExtras.h?rev=278674&r1=278673&r2=278674&view=diff ============================================================================== --- llvm/branches/release_39/include/llvm/ADT/STLExtras.h (original) +++ llvm/branches/release_39/include/llvm/ADT/STLExtras.h Mon Aug 15 11:06:31 2016 @@ -26,10 +26,18 @@ #include <memory> #include <utility> // for std::pair +#include "llvm/ADT/Optional.h" +#include "llvm/ADT/iterator.h" #include "llvm/ADT/iterator_range.h" #include "llvm/Support/Compiler.h" namespace llvm { +namespace detail { + +template <typename RangeT> +using IterOfRange = decltype(std::begin(std::declval<RangeT>())); + +} // End detail namespace //===----------------------------------------------------------------------===// // Extra additions to <functional> @@ -235,6 +243,90 @@ auto reverse( llvm::make_reverse_iterator(std::begin(C))); } +/// An iterator adaptor that filters the elements of given inner iterators. +/// +/// The predicate parameter should be a callable object that accepts the wrapped +/// iterator's reference type and returns a bool. When incrementing or +/// decrementing the iterator, it will call the predicate on each element and +/// skip any where it returns false. +/// +/// \code +/// int A[] = { 1, 2, 3, 4 }; +/// auto R = make_filter_range(A, [](int N) { return N % 2 == 1; }); +/// // R contains { 1, 3 }. +/// \endcode +template <typename WrappedIteratorT, typename PredicateT> +class filter_iterator + : public iterator_adaptor_base< + filter_iterator<WrappedIteratorT, PredicateT>, WrappedIteratorT, + typename std::common_type< + std::forward_iterator_tag, + typename std::iterator_traits< + WrappedIteratorT>::iterator_category>::type> { + using BaseT = iterator_adaptor_base< + filter_iterator<WrappedIteratorT, PredicateT>, WrappedIteratorT, + typename std::common_type< + std::forward_iterator_tag, + typename std::iterator_traits<WrappedIteratorT>::iterator_category>:: + type>; + + struct PayloadType { + WrappedIteratorT End; + PredicateT Pred; + }; + + Optional<PayloadType> Payload; + + void findNextValid() { + assert(Payload && "Payload should be engaged when findNextValid is called"); + while (this->I != Payload->End && !Payload->Pred(*this->I)) + BaseT::operator++(); + } + + // Construct the begin iterator. The begin iterator requires to know where end + // is, so that it can properly stop when it hits end. + filter_iterator(WrappedIteratorT Begin, WrappedIteratorT End, PredicateT Pred) + : BaseT(std::move(Begin)), + Payload(PayloadType{std::move(End), std::move(Pred)}) { + findNextValid(); + } + + // Construct the end iterator. It's not incrementable, so Payload doesn't + // have to be engaged. + filter_iterator(WrappedIteratorT End) : BaseT(End) {} + +public: + using BaseT::operator++; + + filter_iterator &operator++() { + BaseT::operator++(); + findNextValid(); + return *this; + } + + template <typename RT, typename PT> + friend iterator_range<filter_iterator<detail::IterOfRange<RT>, PT>> + make_filter_range(RT &&, PT); +}; + +/// Convenience function that takes a range of elements and a predicate, +/// and return a new filter_iterator range. +/// +/// FIXME: Currently if RangeT && is a rvalue reference to a temporary, the +/// lifetime of that temporary is not kept by the returned range object, and the +/// temporary is going to be dropped on the floor after the make_iterator_range +/// full expression that contains this function call. +template <typename RangeT, typename PredicateT> +iterator_range<filter_iterator<detail::IterOfRange<RangeT>, PredicateT>> +make_filter_range(RangeT &&Range, PredicateT Pred) { + using FilterIteratorT = + filter_iterator<detail::IterOfRange<RangeT>, PredicateT>; + return make_range(FilterIteratorT(std::begin(std::forward<RangeT>(Range)), + std::end(std::forward<RangeT>(Range)), + std::move(Pred)), + FilterIteratorT(std::end(std::forward<RangeT>(Range)))); +} + //===----------------------------------------------------------------------===// // Extra additions to <utility> //===----------------------------------------------------------------------===// Modified: llvm/branches/release_39/include/llvm/ADT/iterator.h URL: http://llvm.org/viewvc/llvm-project/llvm/branches/release_39/include/llvm/ADT/iterator.h?rev=278674&r1=278673&r2=278674&view=diff ============================================================================== --- llvm/branches/release_39/include/llvm/ADT/iterator.h (original) +++ llvm/branches/release_39/include/llvm/ADT/iterator.h Mon Aug 15 11:06:31 2016 @@ -155,7 +155,14 @@ template < typename T = typename std::iterator_traits<WrappedIteratorT>::value_type, typename DifferenceTypeT = typename std::iterator_traits<WrappedIteratorT>::difference_type, - typename PointerT = T *, typename ReferenceT = T &, + typename PointerT = typename std::conditional< + std::is_same<T, typename std::iterator_traits< + WrappedIteratorT>::value_type>::value, + typename std::iterator_traits<WrappedIteratorT>::pointer, T *>::type, + typename ReferenceT = typename std::conditional< + std::is_same<T, typename std::iterator_traits< + WrappedIteratorT>::value_type>::value, + typename std::iterator_traits<WrappedIteratorT>::reference, T &>::type, // Don't provide these, they are mostly to act as aliases below. typename WrappedTraitsT = std::iterator_traits<WrappedIteratorT>> class iterator_adaptor_base @@ -168,15 +175,7 @@ protected: iterator_adaptor_base() = default; - template <typename U> - explicit iterator_adaptor_base( - U &&u, - typename std::enable_if< - !std::is_base_of<typename std::remove_cv< - typename std::remove_reference<U>::type>::type, - DerivedT>::value, - int>::type = 0) - : I(std::forward<U &&>(u)) {} + explicit iterator_adaptor_base(WrappedIteratorT u) : I(std::move(u)) {} const WrappedIteratorT &wrapped() const { return I; } Modified: llvm/branches/release_39/include/llvm/Analysis/CallGraph.h URL: http://llvm.org/viewvc/llvm-project/llvm/branches/release_39/include/llvm/Analysis/CallGraph.h?rev=278674&r1=278673&r2=278674&view=diff ============================================================================== --- llvm/branches/release_39/include/llvm/Analysis/CallGraph.h (original) +++ llvm/branches/release_39/include/llvm/Analysis/CallGraph.h Mon Aug 15 11:06:31 2016 @@ -410,6 +410,7 @@ public: // traversals. template <> struct GraphTraits<CallGraphNode *> { typedef CallGraphNode NodeType; + typedef CallGraphNode *NodeRef; typedef CallGraphNode::CallRecord CGNPairTy; typedef std::pointer_to_unary_function<CGNPairTy, CallGraphNode *> @@ -431,6 +432,7 @@ template <> struct GraphTraits<CallGraph template <> struct GraphTraits<const CallGraphNode *> { typedef const CallGraphNode NodeType; + typedef const CallGraphNode *NodeRef; typedef CallGraphNode::CallRecord CGNPairTy; typedef std::pointer_to_unary_function<CGNPairTy, const CallGraphNode *> Modified: llvm/branches/release_39/include/llvm/CodeGen/MachineBasicBlock.h URL: http://llvm.org/viewvc/llvm-project/llvm/branches/release_39/include/llvm/CodeGen/MachineBasicBlock.h?rev=278674&r1=278673&r2=278674&view=diff ============================================================================== --- llvm/branches/release_39/include/llvm/CodeGen/MachineBasicBlock.h (original) +++ llvm/branches/release_39/include/llvm/CodeGen/MachineBasicBlock.h Mon Aug 15 11:06:31 2016 @@ -740,6 +740,7 @@ struct MBB2NumberFunctor : template <> struct GraphTraits<MachineBasicBlock *> { typedef MachineBasicBlock NodeType; + typedef MachineBasicBlock *NodeRef; typedef MachineBasicBlock::succ_iterator ChildIteratorType; static NodeType *getEntryNode(MachineBasicBlock *BB) { return BB; } @@ -753,6 +754,7 @@ template <> struct GraphTraits<MachineBa template <> struct GraphTraits<const MachineBasicBlock *> { typedef const MachineBasicBlock NodeType; + typedef const MachineBasicBlock *NodeRef; typedef MachineBasicBlock::const_succ_iterator ChildIteratorType; static NodeType *getEntryNode(const MachineBasicBlock *BB) { return BB; } @@ -772,6 +774,7 @@ template <> struct GraphTraits<const Mac // template <> struct GraphTraits<Inverse<MachineBasicBlock*> > { typedef MachineBasicBlock NodeType; + typedef MachineBasicBlock *NodeRef; typedef MachineBasicBlock::pred_iterator ChildIteratorType; static NodeType *getEntryNode(Inverse<MachineBasicBlock *> G) { return G.Graph; @@ -786,6 +789,7 @@ template <> struct GraphTraits<Inverse<M template <> struct GraphTraits<Inverse<const MachineBasicBlock*> > { typedef const MachineBasicBlock NodeType; + typedef const MachineBasicBlock *NodeRef; typedef MachineBasicBlock::const_pred_iterator ChildIteratorType; static NodeType *getEntryNode(Inverse<const MachineBasicBlock*> G) { return G.Graph; Modified: llvm/branches/release_39/include/llvm/IR/CFG.h URL: http://llvm.org/viewvc/llvm-project/llvm/branches/release_39/include/llvm/IR/CFG.h?rev=278674&r1=278673&r2=278674&view=diff ============================================================================== --- llvm/branches/release_39/include/llvm/IR/CFG.h (original) +++ llvm/branches/release_39/include/llvm/IR/CFG.h Mon Aug 15 11:06:31 2016 @@ -155,6 +155,7 @@ struct isPodLike<TerminatorInst::SuccIte template <> struct GraphTraits<BasicBlock*> { typedef BasicBlock NodeType; + typedef BasicBlock *NodeRef; typedef succ_iterator ChildIteratorType; static NodeType *getEntryNode(BasicBlock *BB) { return BB; } @@ -168,6 +169,7 @@ template <> struct GraphTraits<BasicBloc template <> struct GraphTraits<const BasicBlock*> { typedef const BasicBlock NodeType; + typedef const BasicBlock *NodeRef; typedef succ_const_iterator ChildIteratorType; static NodeType *getEntryNode(const BasicBlock *BB) { return BB; } @@ -187,6 +189,7 @@ template <> struct GraphTraits<const Bas // template <> struct GraphTraits<Inverse<BasicBlock*> > { typedef BasicBlock NodeType; + typedef BasicBlock *NodeRef; typedef pred_iterator ChildIteratorType; static NodeType *getEntryNode(Inverse<BasicBlock *> G) { return G.Graph; } static inline ChildIteratorType child_begin(NodeType *N) { @@ -199,6 +202,7 @@ template <> struct GraphTraits<Inverse<B template <> struct GraphTraits<Inverse<const BasicBlock*> > { typedef const BasicBlock NodeType; + typedef const BasicBlock *NodeRef; typedef const_pred_iterator ChildIteratorType; static NodeType *getEntryNode(Inverse<const BasicBlock*> G) { return G.Graph; Modified: llvm/branches/release_39/lib/Analysis/BlockFrequencyInfoImpl.cpp URL: http://llvm.org/viewvc/llvm-project/llvm/branches/release_39/lib/Analysis/BlockFrequencyInfoImpl.cpp?rev=278674&r1=278673&r2=278674&view=diff ============================================================================== --- llvm/branches/release_39/lib/Analysis/BlockFrequencyInfoImpl.cpp (original) +++ llvm/branches/release_39/lib/Analysis/BlockFrequencyInfoImpl.cpp Mon Aug 15 11:06:31 2016 @@ -623,6 +623,7 @@ template <> struct GraphTraits<Irreducib typedef bfi_detail::IrreducibleGraph GraphT; typedef const GraphT::IrrNode NodeType; + typedef const GraphT::IrrNode *NodeRef; typedef GraphT::IrrNode::iterator ChildIteratorType; static const NodeType *getEntryNode(const GraphT &G) { Modified: llvm/branches/release_39/lib/Transforms/IPO/FunctionAttrs.cpp URL: http://llvm.org/viewvc/llvm-project/llvm/branches/release_39/lib/Transforms/IPO/FunctionAttrs.cpp?rev=278674&r1=278673&r2=278674&view=diff ============================================================================== --- llvm/branches/release_39/lib/Transforms/IPO/FunctionAttrs.cpp (original) +++ llvm/branches/release_39/lib/Transforms/IPO/FunctionAttrs.cpp Mon Aug 15 11:06:31 2016 @@ -332,6 +332,7 @@ struct ArgumentUsesTracker : public Capt namespace llvm { template <> struct GraphTraits<ArgumentGraphNode *> { typedef ArgumentGraphNode NodeType; + typedef ArgumentGraphNode *NodeRef; typedef SmallVectorImpl<ArgumentGraphNode *>::iterator ChildIteratorType; static inline NodeType *getEntryNode(NodeType *A) { return A; } Modified: llvm/branches/release_39/lib/Transforms/Vectorize/LoopVectorize.cpp URL: http://llvm.org/viewvc/llvm-project/llvm/branches/release_39/lib/Transforms/Vectorize/LoopVectorize.cpp?rev=278674&r1=278673&r2=278674&view=diff ============================================================================== --- llvm/branches/release_39/lib/Transforms/Vectorize/LoopVectorize.cpp (original) +++ llvm/branches/release_39/lib/Transforms/Vectorize/LoopVectorize.cpp Mon Aug 15 11:06:31 2016 @@ -50,6 +50,7 @@ #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/Hashing.h" #include "llvm/ADT/MapVector.h" +#include "llvm/ADT/SCCIterator.h" #include "llvm/ADT/SetVector.h" #include "llvm/ADT/SmallPtrSet.h" #include "llvm/ADT/SmallSet.h" @@ -220,6 +221,81 @@ class LoopVectorizationLegality; class LoopVectorizationCostModel; class LoopVectorizationRequirements; +// A traits type that is intended to be used in graph algorithms. The graph it +// models starts at the loop header, and traverses the BasicBlocks that are in +// the loop body, but not the loop header. Since the loop header is skipped, +// the back edges are excluded. +struct LoopBodyTraits { + using NodeRef = std::pair<const Loop *, BasicBlock *>; + + // This wraps a const Loop * into the iterator, so we know which edges to + // filter out. + class WrappedSuccIterator + : public iterator_adaptor_base< + WrappedSuccIterator, succ_iterator, + typename std::iterator_traits<succ_iterator>::iterator_category, + NodeRef, std::ptrdiff_t, NodeRef *, NodeRef> { + using BaseT = iterator_adaptor_base< + WrappedSuccIterator, succ_iterator, + typename std::iterator_traits<succ_iterator>::iterator_category, + NodeRef, std::ptrdiff_t, NodeRef *, NodeRef>; + + const Loop *L; + + public: + WrappedSuccIterator(succ_iterator Begin, const Loop *L) + : BaseT(Begin), L(L) {} + + NodeRef operator*() const { return {L, *I}; } + }; + + struct LoopBodyFilter { + bool operator()(NodeRef N) const { + const Loop *L = N.first; + return N.second != L->getHeader() && L->contains(N.second); + } + }; + + using ChildIteratorType = + filter_iterator<WrappedSuccIterator, LoopBodyFilter>; + + static NodeRef getEntryNode(const Loop &G) { return {&G, G.getHeader()}; } + + static ChildIteratorType child_begin(NodeRef Node) { + return make_filter_range(make_range<WrappedSuccIterator>( + {succ_begin(Node.second), Node.first}, + {succ_end(Node.second), Node.first}), + LoopBodyFilter{}) + .begin(); + } + + static ChildIteratorType child_end(NodeRef Node) { + return make_filter_range(make_range<WrappedSuccIterator>( + {succ_begin(Node.second), Node.first}, + {succ_end(Node.second), Node.first}), + LoopBodyFilter{}) + .end(); + } +}; + +/// Returns true if the given loop body has a cycle, excluding the loop +/// itself. +static bool hasCyclesInLoopBody(const Loop &L) { + if (!L.empty()) + return true; + + for (const auto SCC : + make_range(scc_iterator<Loop, LoopBodyTraits>::begin(L), + scc_iterator<Loop, LoopBodyTraits>::end(L))) { + if (SCC.size() > 1) { + DEBUG(dbgs() << "LVL: Detected a cycle in the loop body:\n"); + DEBUG(L.dump()); + return true; + } + } + return false; +} + /// \brief This modifies LoopAccessReport to initialize message with /// loop-vectorizer-specific part. class VectorizationReport : public LoopAccessReport { @@ -1782,12 +1858,14 @@ private: Instruction *UnsafeAlgebraInst; }; -static void addInnerLoop(Loop &L, SmallVectorImpl<Loop *> &V) { - if (L.empty()) - return V.push_back(&L); - +static void addAcyclicInnerLoop(Loop &L, SmallVectorImpl<Loop *> &V) { + if (L.empty()) { + if (!hasCyclesInLoopBody(L)) + V.push_back(&L); + return; + } for (Loop *InnerL : L) - addInnerLoop(*InnerL, V); + addAcyclicInnerLoop(*InnerL, V); } /// The LoopVectorize Pass. @@ -4395,6 +4473,9 @@ bool LoopVectorizationLegality::canVecto return false; } + // FIXME: The code is currently dead, since the loop gets sent to + // LoopVectorizationLegality is already an innermost loop. + // // We can only vectorize innermost loops. if (!TheLoop->empty()) { emitAnalysis(VectorizationReport() << "loop is not the innermost loop"); @@ -6639,7 +6720,7 @@ bool LoopVectorizePass::runImpl( SmallVector<Loop *, 8> Worklist; for (Loop *L : *LI) - addInnerLoop(*L, Worklist); + addAcyclicInnerLoop(*L, Worklist); LoopsAnalyzed += Worklist.size(); Modified: llvm/branches/release_39/unittests/ADT/SCCIteratorTest.cpp URL: http://llvm.org/viewvc/llvm-project/llvm/branches/release_39/unittests/ADT/SCCIteratorTest.cpp?rev=278674&r1=278673&r2=278674&view=diff ============================================================================== --- llvm/branches/release_39/unittests/ADT/SCCIteratorTest.cpp (original) +++ llvm/branches/release_39/unittests/ADT/SCCIteratorTest.cpp Mon Aug 15 11:06:31 2016 @@ -230,6 +230,7 @@ public: template <unsigned N> struct GraphTraits<Graph<N> > { typedef typename Graph<N>::NodeType NodeType; + typedef typename Graph<N>::NodeType *NodeRef; typedef typename Graph<N>::ChildIterator ChildIteratorType; static inline NodeType *getEntryNode(const Graph<N> &G) { return G.AccessNode(0); } Modified: llvm/branches/release_39/unittests/Support/IteratorTest.cpp URL: http://llvm.org/viewvc/llvm-project/llvm/branches/release_39/unittests/Support/IteratorTest.cpp?rev=278674&r1=278673&r2=278674&view=diff ============================================================================== --- llvm/branches/release_39/unittests/Support/IteratorTest.cpp (original) +++ llvm/branches/release_39/unittests/Support/IteratorTest.cpp Mon Aug 15 11:06:31 2016 @@ -16,6 +16,24 @@ using namespace llvm; namespace { +template <int> struct Shadow; + +struct WeirdIter : std::iterator<std::input_iterator_tag, Shadow<0>, Shadow<1>, + Shadow<2>, Shadow<3>> {}; + +struct AdaptedIter : iterator_adaptor_base<AdaptedIter, WeirdIter> {}; + +// Test that iterator_adaptor_base forwards typedefs, if value_type is +// unchanged. +static_assert(std::is_same<typename AdaptedIter::value_type, Shadow<0>>::value, + ""); +static_assert( + std::is_same<typename AdaptedIter::difference_type, Shadow<1>>::value, ""); +static_assert(std::is_same<typename AdaptedIter::pointer, Shadow<2>>::value, + ""); +static_assert(std::is_same<typename AdaptedIter::reference, Shadow<3>>::value, + ""); + TEST(PointeeIteratorTest, Basic) { int arr[4] = { 1, 2, 3, 4 }; SmallVector<int *, 4> V; @@ -98,4 +116,73 @@ TEST(PointeeIteratorTest, SmartPointer) EXPECT_EQ(End, I); } +TEST(FilterIteratorTest, Lambda) { + auto IsOdd = [](int N) { return N % 2 == 1; }; + int A[] = {0, 1, 2, 3, 4, 5, 6}; + auto Range = make_filter_range(A, IsOdd); + SmallVector<int, 3> Actual(Range.begin(), Range.end()); + EXPECT_EQ((SmallVector<int, 3>{1, 3, 5}), Actual); +} + +TEST(FilterIteratorTest, CallableObject) { + int Counter = 0; + struct Callable { + int &Counter; + + Callable(int &Counter) : Counter(Counter) {} + + bool operator()(int N) { + Counter++; + return N % 2 == 1; + } + }; + Callable IsOdd(Counter); + int A[] = {0, 1, 2, 3, 4, 5, 6}; + auto Range = make_filter_range(A, IsOdd); + EXPECT_EQ(2, Counter); + SmallVector<int, 3> Actual(Range.begin(), Range.end()); + EXPECT_GE(Counter, 7); + EXPECT_EQ((SmallVector<int, 3>{1, 3, 5}), Actual); +} + +TEST(FilterIteratorTest, FunctionPointer) { + bool (*IsOdd)(int) = [](int N) { return N % 2 == 1; }; + int A[] = {0, 1, 2, 3, 4, 5, 6}; + auto Range = make_filter_range(A, IsOdd); + SmallVector<int, 3> Actual(Range.begin(), Range.end()); + EXPECT_EQ((SmallVector<int, 3>{1, 3, 5}), Actual); +} + +TEST(FilterIteratorTest, Composition) { + auto IsOdd = [](int N) { return N % 2 == 1; }; + std::unique_ptr<int> A[] = {make_unique<int>(0), make_unique<int>(1), + make_unique<int>(2), make_unique<int>(3), + make_unique<int>(4), make_unique<int>(5), + make_unique<int>(6)}; + using PointeeIterator = pointee_iterator<std::unique_ptr<int> *>; + auto Range = make_filter_range( + make_range(PointeeIterator(std::begin(A)), PointeeIterator(std::end(A))), + IsOdd); + SmallVector<int, 3> Actual(Range.begin(), Range.end()); + EXPECT_EQ((SmallVector<int, 3>{1, 3, 5}), Actual); +} + +TEST(FilterIteratorTest, InputIterator) { + struct InputIterator + : iterator_adaptor_base<InputIterator, int *, std::input_iterator_tag> { + using BaseT = + iterator_adaptor_base<InputIterator, int *, std::input_iterator_tag>; + + InputIterator(int *It) : BaseT(It) {} + }; + + auto IsOdd = [](int N) { return N % 2 == 1; }; + int A[] = {0, 1, 2, 3, 4, 5, 6}; + auto Range = make_filter_range( + make_range(InputIterator(std::begin(A)), InputIterator(std::end(A))), + IsOdd); + SmallVector<int, 3> Actual(Range.begin(), Range.end()); + EXPECT_EQ((SmallVector<int, 3>{1, 3, 5}), Actual); +} + } // anonymous namespace _______________________________________________ llvm-branch-commits mailing list llvm-branch-commits@lists.llvm.org http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-branch-commits
