From dca126522d7c13d8f4e3a42dc191250bd567550d Mon Sep 17 00:00:00 2001 From: Renato Golin Date: Tue, 19 Aug 2014 17:30:43 +0000 Subject: [PATCH] Small refactor on VectorizerHint for deduplication Previously, the hint mechanism relied on clean up passes to remove redundant metadata, which still showed up if running opt at low levels of optimization. That also has shown that multiple nodes of the same type, but with different values could still coexist, even if temporary, and cause confusion if the next pass got the wrong value. This patch makes sure that, if metadata already exists in a loop, the hint mechanism will never append a new node, but always replace the existing one. It also enhances the algorithm to cope with more metadata types in the future by just adding a new type, not a lot of code. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@215994 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Transforms/Vectorize/LoopVectorize.cpp | 238 +++++++++++------- .../LoopVectorize/duplicated-metadata.ll | 30 +++ 2 files changed, 177 insertions(+), 91 deletions(-) create mode 100644 test/Transforms/LoopVectorize/duplicated-metadata.ll diff --git a/lib/Transforms/Vectorize/LoopVectorize.cpp b/lib/Transforms/Vectorize/LoopVectorize.cpp index 1ab439f724a..e0d8e939df1 100644 --- a/lib/Transforms/Vectorize/LoopVectorize.cpp +++ b/lib/Transforms/Vectorize/LoopVectorize.cpp @@ -970,7 +970,54 @@ private: /// Utility class for getting and setting loop vectorizer hints in the form /// of loop metadata. +/// This class keeps a number of loop annotations locally (as member variables) +/// and can, upon request, write them back as metadata on the loop. It will +/// initially scan the loop for existing metadata, and will update the local +/// values based on information in the loop. +/// We cannot write all values to metadata, as the mere presence of some info, +/// for example 'force', means a decision has been made. So, we need to be +/// careful NOT to add them if the user hasn't specifically asked so. class LoopVectorizeHints { + enum HintKind { + HK_WIDTH, + HK_UNROLL, + HK_FORCE + }; + + /// Hint - associates name and validation with the hint value. + struct Hint { + const char * Name; + unsigned Value; // This may have to change for non-numeric values. + HintKind Kind; + + Hint(const char * Name, unsigned Value, HintKind Kind) + : Name(Name), Value(Value), Kind(Kind) { } + + bool validate(unsigned Val) { + switch (Kind) { + case HK_WIDTH: + return isPowerOf2_32(Val) && Val <= MaxVectorWidth; + case HK_UNROLL: + return isPowerOf2_32(Val) && Val <= MaxUnrollFactor; + case HK_FORCE: + return (Val <= 1); + } + return false; + } + }; + + /// Vectorization width. + Hint Width; + /// Vectorization unroll factor. + Hint Unroll; + /// Vectorization forced + Hint Force; + /// Array to help iterating through all hints. + Hint *Hints[3] = { &Width, &Unroll, &Force }; + + /// Return the loop metadata prefix. + static StringRef Prefix() { return "llvm.loop."; } + public: enum ForceKind { FK_Undefined = -1, ///< Not selected. @@ -979,70 +1026,40 @@ public: }; LoopVectorizeHints(const Loop *L, bool DisableUnrolling) - : Width(VectorizationFactor), - Unroll(DisableUnrolling), - Force(FK_Undefined), - LoopID(L->getLoopID()) { - getHints(L); + : Width("vectorize.width", VectorizationFactor, HK_WIDTH), + Unroll("interleave.count", DisableUnrolling, HK_UNROLL), + Force("vectorize.enable", FK_Undefined, HK_FORCE), + TheLoop(L) { + // Populate values with existing loop metadata. + getHintsFromMetadata(); + // force-vector-unroll overrides DisableUnrolling. if (VectorizationUnroll.getNumOccurrences() > 0) - Unroll = VectorizationUnroll; + Unroll.Value = VectorizationUnroll; - DEBUG(if (DisableUnrolling && Unroll == 1) dbgs() + DEBUG(if (DisableUnrolling && Unroll.Value == 1) dbgs() << "LV: Unrolling disabled by the pass manager\n"); } - /// Return the loop metadata prefix. - static StringRef Prefix() { return "llvm.loop."; } - - MDNode *createHint(LLVMContext &Context, StringRef Name, unsigned V) const { - SmallVector Vals; - Vals.push_back(MDString::get(Context, Name)); - Vals.push_back(ConstantInt::get(Type::getInt32Ty(Context), V)); - return MDNode::get(Context, Vals); - } - /// Mark the loop L as already vectorized by setting the width to 1. - void setAlreadyVectorized(Loop *L) { - LLVMContext &Context = L->getHeader()->getContext(); - - Width = 1; - - // Create a new loop id with one more operand for the already_vectorized - // hint. If the loop already has a loop id then copy the existing operands. - SmallVector Vals(1); - if (LoopID) - for (unsigned i = 1, ie = LoopID->getNumOperands(); i < ie; ++i) - Vals.push_back(LoopID->getOperand(i)); - - Vals.push_back( - createHint(Context, Twine(Prefix(), "vectorize.width").str(), Width)); - Vals.push_back( - createHint(Context, Twine(Prefix(), "interleave.count").str(), 1)); - - MDNode *NewLoopID = MDNode::get(Context, Vals); - // Set operand 0 to refer to the loop id itself. - NewLoopID->replaceOperandWith(0, NewLoopID); - - L->setLoopID(NewLoopID); - if (LoopID) - LoopID->replaceAllUsesWith(NewLoopID); - - LoopID = NewLoopID; + void setAlreadyVectorized() { + Width.Value = Unroll.Value = 1; + writeHintsToMetadata({ Width, Unroll }); } + /// Dumps all the hint information. std::string emitRemark() const { Report R; - if (Force == LoopVectorizeHints::FK_Disabled) + if (Force.Value == LoopVectorizeHints::FK_Disabled) R << "vectorization is explicitly disabled"; else { R << "use -Rpass-analysis=loop-vectorize for more info"; - if (Force == LoopVectorizeHints::FK_Enabled) { + if (Force.Value == LoopVectorizeHints::FK_Enabled) { R << " (Force=true"; - if (Width != 0) - R << ", Vector Width=" << Width; - if (Unroll != 0) - R << ", Interleave Count=" << Unroll; + if (Width.Value != 0) + R << ", Vector Width=" << Width.Value; + if (Unroll.Value != 0) + R << ", Interleave Count=" << Unroll.Value; R << ")"; } } @@ -1050,14 +1067,14 @@ public: return R.str(); } - unsigned getWidth() const { return Width; } - unsigned getUnroll() const { return Unroll; } - enum ForceKind getForce() const { return Force; } - MDNode *getLoopID() const { return LoopID; } + unsigned getWidth() const { return Width.Value; } + unsigned getUnroll() const { return Unroll.Value; } + enum ForceKind getForce() const { return (ForceKind)Force.Value; } private: - /// Find hints specified in the loop metadata. - void getHints(const Loop *L) { + /// Find hints specified in the loop metadata and update local values. + void getHintsFromMetadata() { + MDNode *LoopID = TheLoop->getLoopID(); if (!LoopID) return; @@ -1086,52 +1103,91 @@ private: continue; // Check if the hint starts with the loop metadata prefix. - StringRef Hint = S->getString(); - if (!Hint.startswith(Prefix())) - continue; - // Remove the prefix. - Hint = Hint.substr(Prefix().size(), StringRef::npos); - + StringRef Name = S->getString(); if (Args.size() == 1) - getHint(Hint, Args[0]); + setHint(Name, Args[0]); } } - // Check string hint with one operand. - void getHint(StringRef Hint, Value *Arg) { + /// Checks string hint with one operand and set value if valid. + void setHint(StringRef Name, Value *Arg) { + if (!Name.startswith(Prefix())) + return; + Name = Name.substr(Prefix().size(), StringRef::npos); + const ConstantInt *C = dyn_cast(Arg); if (!C) return; unsigned Val = C->getZExtValue(); - if (Hint == "vectorize.width") { - if (isPowerOf2_32(Val) && Val <= MaxVectorWidth) - Width = Val; - else - DEBUG(dbgs() << "LV: ignoring invalid width hint metadata\n"); - } else if (Hint == "vectorize.enable") { - if (C->getBitWidth() == 1) - Force = Val == 1 ? LoopVectorizeHints::FK_Enabled - : LoopVectorizeHints::FK_Disabled; - else - DEBUG(dbgs() << "LV: ignoring invalid enable hint metadata\n"); - } else if (Hint == "interleave.count") { - if (isPowerOf2_32(Val) && Val <= MaxUnrollFactor) - Unroll = Val; - else - DEBUG(dbgs() << "LV: ignoring invalid unroll hint metadata\n"); - } else { - DEBUG(dbgs() << "LV: ignoring unknown hint " << Hint << '\n'); + for (auto H : Hints) { + if (Name == H->Name) { + if (H->validate(Val)) + H->Value = Val; + else + DEBUG(dbgs() << "LV: ignoring invalid hint '" << Name << "'\n"); + break; + } } } - /// Vectorization width. - unsigned Width; - /// Vectorization unroll factor. - unsigned Unroll; - /// Vectorization forced - enum ForceKind Force; + /// Create a new hint from name / value pair. + MDNode *createHintMetadata(StringRef Name, unsigned V) const { + LLVMContext &Context = TheLoop->getHeader()->getContext(); + SmallVector Vals; + Vals.push_back(MDString::get(Context, Name)); + Vals.push_back(ConstantInt::get(Type::getInt32Ty(Context), V)); + return MDNode::get(Context, Vals); + } + + /// Matches metadata with hint name. + bool matchesHintMetadataName(MDNode *Node, std::vector &HintTypes) { + MDString* Name = dyn_cast(Node->getOperand(0)); + if (!Name) + return false; + + for (auto H : HintTypes) + if (Name->getName().endswith(H.Name)) + return true; + return false; + } + + /// Sets current hints into loop metadata, keeping other values intact. + void writeHintsToMetadata(std::vector HintTypes) { + if (HintTypes.size() == 0) + return; + + // Reserve the first element to LoopID (see below). + SmallVector Vals(1); + // If the loop already has metadata, then ignore the existing operands. + MDNode *LoopID = TheLoop->getLoopID(); + if (LoopID) { + for (unsigned i = 1, ie = LoopID->getNumOperands(); i < ie; ++i) { + MDNode *Node = cast(LoopID->getOperand(i)); + // If node in update list, ignore old value. + if (!matchesHintMetadataName(Node, HintTypes)) + Vals.push_back(Node); + } + } + + // Now, add the missing hints. + for (auto H : HintTypes) + Vals.push_back( + createHintMetadata(Twine(Prefix(), H.Name).str(), H.Value)); + + // Replace current metadata node with new one. + LLVMContext &Context = TheLoop->getHeader()->getContext(); + MDNode *NewLoopID = MDNode::get(Context, Vals); + // Set operand 0 to refer to the loop id itself. + NewLoopID->replaceOperandWith(0, NewLoopID); + + TheLoop->setLoopID(NewLoopID); + if (LoopID) + LoopID->replaceAllUsesWith(NewLoopID); + LoopID = NewLoopID; + } - MDNode *LoopID; + /// The loop these hints belong to. + const Loop *TheLoop; }; static void emitMissedWarning(Function *F, Loop *L, @@ -1393,7 +1449,7 @@ struct LoopVectorize : public FunctionPass { } // Mark the loop as already vectorized to avoid vectorizing again. - Hints.setAlreadyVectorized(L); + Hints.setAlreadyVectorized(); DEBUG(verifyFunction(*L->getHeader()->getParent())); return true; @@ -2495,7 +2551,7 @@ void InnerLoopVectorizer::createEmptyLoop() { LoopScalarBody = OldBasicBlock; LoopVectorizeHints Hints(Lp, true); - Hints.setAlreadyVectorized(Lp); + Hints.setAlreadyVectorized(); } /// This function returns the identity element (or neutral element) for diff --git a/test/Transforms/LoopVectorize/duplicated-metadata.ll b/test/Transforms/LoopVectorize/duplicated-metadata.ll new file mode 100644 index 00000000000..8353dca41cd --- /dev/null +++ b/test/Transforms/LoopVectorize/duplicated-metadata.ll @@ -0,0 +1,30 @@ +; RUN: opt < %s -loop-vectorize -S 2>&1 | FileCheck %s +target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" +target triple = "x86_64-unknown-linux-gnu" + +; This test makes sure we don't duplicate the loop vectorizer's metadata +; while marking them as already vectorized (by setting width = 1), even +; at lower optimization levels, where no extra cleanup is done + +define void @_Z3fooPf(float* %a) { +entry: + br label %for.body + +for.body: ; preds = %for.body, %entry + %indvars.iv = phi i64 [ 0, %entry ], [ %indvars.iv.next, %for.body ] + %arrayidx = getelementptr inbounds float* %a, i64 %indvars.iv + %p = load float* %arrayidx, align 4 + %mul = fmul float %p, 2.000000e+00 + store float %mul, float* %arrayidx, align 4 + %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1 + %exitcond = icmp eq i64 %indvars.iv.next, 1024 + br i1 %exitcond, label %for.end, label %for.body, !llvm.loop !0 + +for.end: ; preds = %for.body + ret void +} + +!0 = metadata !{metadata !0, metadata !1} +!1 = metadata !{metadata !"llvm.loop.vectorize.width", i32 4} +; CHECK-NOT: !{metadata !"llvm.loop.vectorize.width", i32 4} +; CHECK: !{metadata !"llvm.loop.interleave.count", i32 1} -- 2.34.1