Small refactor on VectorizerHint for deduplication

[rengolin]

Summary

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.

Fixes PR20655.

[ArchDRobison]

Minor editorial comments. I'm not an LLVM expert.

lib/Transforms/Vectorize/LoopVectorize.cpp

1117

Should the cast be dyn_cast?

1137

Is it safe to assume that the operands are all MDNode and not other kinds of values? If not, consider not casting here, and instead pass a Value* to "matchesHintMetadataName" and do the check for MDNode-ness there.

1139

The if/continue/else seems a bit wordy. It would be shorter to write:

if (!matchesHintMetadataNameNode, HintTypes))

Vals.push_back(Node);

1180–1181

"this" should be "these".

[rengolin]

Thanks for the review, Arch.

Sending a new patch with the updates.

cheers,
--renato

lib/Transforms/Vectorize/LoopVectorize.cpp

1117

Yes, thanks!

1137

It should, since this is the only class touching that part. But I agree it's not the safest way to go. One needs to revise the metadata handling in the loop vectorizer as a whole, I believe. Maybe not for this patch, though.

1139

That's the result of a different piece of code. Updated, thanks!

1180–1181

Thanks!

[rengolin]

Updating from Arch's comments.

[aschwaighofer]

Hi Renato,

This LGTM. I have only minor stylistic comments:

I think this would reads easier if we refer to Hint and Hints instead of HintType(s).

We concatenate and split "llvm.loop" and "vectorize.foo". I think it would simplify the code if the Hints refer to the full string?

Can we centralize the logic if we move the validation logic into a member function "validate" that switches on a hint kind? Validation and the hint are intrinsically connected.

struct Hint {
 enum Kind {
  kUnroll, ...} HintKind;

  Hint(Kind K, StringRef Name...) {}

  bool validate() {
   switch(HintKind) { 
      case kUnroll:
   }
 }
};

Thanks for fixing this.

[rengolin]

Hi Arnold,

Thanks for your review. Replies inline.

In D4913#10, @aschwaighofer wrote:

I think this would reads easier if we refer to Hint and Hints instead of HintType(s).

Fair enough, I can change that.

We concatenate and split "llvm.loop" and "vectorize.foo". I think it would simplify the code if the Hints refer to the full string?

We do that to validate and only warn if it's an invalid "llvm.loop." metadata, so we don't even scan the others (like tbaa, etc). Adding it to the name will simplify the pattern match on the hint but would make warning a bit harder. I will move the matching on the prefix to the parseHint() to make it a bit more isolated, and easier to change in the future.

Can we centralize the logic if we move the validation logic into a member function "validate" that switches on a hint kind? Validation and the hint are intrinsically connected.

So, I though about using an enum to validate, but that meant we'd have to construct a new Hint from a string and assign a kind just to check if it's a valid hint at all, and then add InvalidHint objects and making sure none of the objects are duplicated. It got a bit complex...

Since we don't use static initializers, and this is only built once, and the constructor is statically set on the right validation lambda for each string, I thought it'd be at least safe. I agree it's not pretty.

I'll give it a few more tries...

cheers,
--renato

[rengolin]

Right, found an easy way to work around the validation problem. Committed in r215994.

Thanks!
--renato

[rengolin]

Accepting to close

lib/Transforms/Vectorize/LoopVectorize.cpp

   const TargetLibraryInfo *TLI;
   const Function *TheFunction;
   // Loop Vectorize Hint.
   const LoopVectorizeHints *Hints;
 };
 
 /// 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 {
 public:
   enum ForceKind {
     FK_Undefined = -1, ///< Not selected.
     FK_Disabled = 0,   ///< Forcing disabled.
     FK_Enabled = 1,    ///< Forcing enabled.
   };
 
+  /// HintType - associates name and validation with the hint value.
+  struct HintType {
+    const char * Name;
+    unsigned Value; // This may have to change for non-numeric values.
+    std::function<bool(unsigned)> validate;
+    HintType(const char * Name, unsigned Value, std::function<bool(unsigned)> F)
+      : Name(Name), Value(Value), validate(F) {}
+  };
+
+  /// Return the loop metadata prefix.
+  static StringRef Prefix() { return "llvm.loop."; }
+
   LoopVectorizeHints(const Loop *L, bool DisableUnrolling)
-      : Width(VectorizationFactor),
-        Unroll(DisableUnrolling),
-        Force(FK_Undefined),
-        LoopID(L->getLoopID()) {
-    getHints(L);
+      : Width("vectorize.width", VectorizationFactor, validateWidth),
+        Unroll("interleave.count", DisableUnrolling, validateUnroll),
+        Force("vectorize.enable", FK_Undefined, validateForce),
+        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<Value*, 2> 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<Value*, 4> 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 << ")";
       }
     }
 
     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;
 
     // First operand should refer to the loop id itself.
     assert(LoopID->getNumOperands() > 0 && "requires at least one operand");
     assert(LoopID->getOperand(0) == LoopID && "invalid loop id");
 
     for (unsigned i = 1, ie = LoopID->getNumOperands(); i < ie; ++i) {

       // 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);
 
       if (Args.size() == 1)
-        getHint(Hint, Args[0]);
+        parseHint(Hint, 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 parseHint(StringRef Hint, Value *Arg) {
     const ConstantInt *C = dyn_cast<ConstantInt>(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 (Hint == H->Name) {
+        if (H->validate(Val))
+          H->Value = Val;
+        else
+          DEBUG(dbgs() << "LV: ignoring invalid hint '" << Hint << "'\n");
+        break;
+      }
     }
   }
 
+  /// Create a new hint from name / value pair.
+  MDNode *createHintMetadata(StringRef Name, unsigned V) const {
+    LLVMContext &Context = TheLoop->getHeader()->getContext();
+    SmallVector<Value*, 2> 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<HintType> &HintTypes) {
+    MDString* Name = dyn_cast<MDString>(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<HintType> HintTypes) {
+    if (HintTypes.size() == 0)
+      return;
+
+    // Reserve the first element to LoopID (see below).
+    SmallVector<Value*, 4> 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<MDNode>(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;
+  }
+
   /// Vectorization width.
-  unsigned Width;
+  HintType Width;
+  static bool validateWidth (unsigned Val) {
+    return isPowerOf2_32(Val) && Val <= MaxVectorWidth;
+  }
   /// Vectorization unroll factor.
-  unsigned Unroll;
+  HintType Unroll;
+  static bool validateUnroll (unsigned Val) {
+    return isPowerOf2_32(Val) && Val <= MaxUnrollFactor;
+  }
   /// Vectorization forced
-  enum ForceKind Force;
+  HintType Force;
+  static bool validateForce (unsigned Val) {
+    return (Val <= 1);
+  }
+  /// Array to help iterating through all hints.
+  HintType *Hints[3] = { &Width, &Unroll, &Force };
 
-  MDNode *LoopID;
+  /// The loop thess hints belong to.
+  const Loop *TheLoop;
 };
 
 static void emitMissedWarning(Function *F, Loop *L,
                               const LoopVectorizeHints &LH) {
   emitOptimizationRemarkMissed(F->getContext(), DEBUG_TYPE, *F,
                                L->getStartLoc(), LH.emitRemark());
 
   if (LH.getForce() == LoopVectorizeHints::FK_Enabled) {

       // Report the vectorization decision.
       emitOptimizationRemark(
           F->getContext(), DEBUG_TYPE, *F, L->getStartLoc(),
           Twine("vectorized loop (vectorization factor: ") + Twine(VF.Width) +
               ", unrolling interleave factor: " + Twine(UF) + ")");
     }
 
     // Mark the loop as already vectorized to avoid vectorizing again.
-    Hints.setAlreadyVectorized(L);
+    Hints.setAlreadyVectorized();
 
     DEBUG(verifyFunction(*L->getHeader()->getParent()));
     return true;
   }
 
   void getAnalysisUsage(AnalysisUsage &AU) const override {
     AU.addRequiredID(LoopSimplifyID);
     AU.addRequiredID(LCSSAID);

   LoopVectorPreHeader = VectorPH;
   LoopScalarPreHeader = ScalarPH;
   LoopMiddleBlock = MiddleBlock;
   LoopExitBlock = ExitBlock;
   LoopVectorBody.push_back(VecBody);
   LoopScalarBody = OldBasicBlock;
 
   LoopVectorizeHints Hints(Lp, true);
-  Hints.setAlreadyVectorized(Lp);
+  Hints.setAlreadyVectorized();
 }
 
 /// This function returns the identity element (or neutral element) for
 /// the operation K.
 Constant*
 LoopVectorizationLegality::getReductionIdentity(ReductionKind K, Type *Tp) {
   switch (K) {
   case RK_IntegerXor:

test/Transforms/LoopVectorize/duplicated-metadata.ll

+; 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}