[LangRef] Adds llvm.loop.mustprogress loop metadata

[atmnpatel]

Summary

This patch adds the llvm.loop.mustprogress loop metadata. This is to be
added to loops where the frontend language requires that the loop makes
observable interactions with the environment. This is the loop-level
equivalent to the function attribute mustprogress defined in D86233.

[jdoerfert]

llvm/include/llvm/Transforms/Utils/Cloning.h

189

this is not needed in this patch

[atmnpatel]

Removed extra file.

[atmnpatel]

buildkite fix.

[jdoerfert]

LGTM

[atmnpatel]

Rebase.

llvm/docs/LangRef.rst

.. code-block:: llvm
 
    outer.for.end:                                          ; preds = %for.body
    ...
    !1 = distinct !{!1, !{!"llvm.loop.parallel_accesses", !3}}     ; metadata for the inner loop
    !2 = distinct !{!2, !{!"llvm.loop.parallel_accesses", !3, !4}} ; metadata for the outer loop
    !3 = distinct !{} ; access group for instructions in the inner loop (which are implicitly contained in outer loop as well)
    !4 = distinct !{} ; access group for instructions in the outer, but not the inner loop
 
+'``llvm.loop.mustprogress``' Metadata
+^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
+
+The ``llvm.loop.mustprogress`` metadata indicates that this loop is required to
+terminate, unwind, or interact with the environment in an observable way e.g.
+via a volatile memory access, I/O, or other synchronization. If such a loop is
+not found to interact with the environment in an observable way, the loop may
+be removed. This corresponds to the ``mustprogress`` function attribute.
+
 '``irr_loop``' Metadata
 ^^^^^^^^^^^^^^^^^^^^^^^
 
 ``irr_loop`` metadata may be attached to the terminator instruction of a basic
 block that's an irreducible loop header (note that an irreducible loop has more
 than once header basic blocks.) If ``irr_loop`` metadata is attached to the
 terminator instruction of a basic block that is not really an irreducible loop
 header, the behavior is undefined. The intent of this metadata is to improve the

llvm/include/llvm/Analysis/LoopInfo.h

public:
   /// Add llvm.loop.unroll.disable to this loop's loop id metadata.
   ///
   /// Remove existing unroll metadata and add unroll disable metadata to
   /// indicate the loop has already been unrolled.  This prevents a loop
   /// from being unrolled more than is directed by a pragma if the loop
   /// unrolling pass is run more than once (which it generally is).
   void setLoopAlreadyUnrolled();
 
+  /// Add llvm.loop.mustprogress to this loop's loop id metadata.
+  void setLoopMustProgress();
+
   void dump() const;
   void dumpVerbose() const;
 
   /// Return the debug location of the start of this loop.
   /// This looks for a BB terminating instruction with a known debug
   /// location by looking at the preheader and header blocks. If it
   /// cannot find a terminating instruction with location information,
   /// it returns an unknown location.

llvm/include/llvm/Transforms/Utils/Cloning.h

 /// the auxiliary results produced by it.
 class InlineFunctionInfo {
 public:
   explicit InlineFunctionInfo(
       CallGraph *cg = nullptr,
       function_ref<AssumptionCache &(Function &)> GetAssumptionCache = nullptr,
       ProfileSummaryInfo *PSI = nullptr,
       BlockFrequencyInfo *CallerBFI = nullptr,
-      BlockFrequencyInfo *CalleeBFI = nullptr)
+      BlockFrequencyInfo *CalleeBFI = nullptr, LoopInfo *CalleeLI = nullptr)
       : CG(cg), GetAssumptionCache(GetAssumptionCache), PSI(PSI),
-        CallerBFI(CallerBFI), CalleeBFI(CalleeBFI) {}
+        CallerBFI(CallerBFI), CalleeBFI(CalleeBFI), CalleeLI(CalleeLI) {}
 
   /// If non-null, InlineFunction will update the callgraph to reflect the
   /// changes it makes.
   CallGraph *CG;
   function_ref<AssumptionCache &(Function &)> GetAssumptionCache;
   ProfileSummaryInfo *PSI;
   BlockFrequencyInfo *CallerBFI, *CalleeBFI;
+  LoopInfo *CalleeLI;
 
   /// InlineFunction fills this in with all static allocas that get copied into
   /// the caller.
   SmallVector<AllocaInst *, 4> StaticAllocas;
 
   /// InlineFunction fills this in with callsites that were inlined from the
   /// callee. This is only filled in if CG is non-null.
   SmallVector<WeakTrackingVH, 8> InlinedCalls;

llvm/lib/Analysis/LoopInfo.cpp

void Loop::setLoopAlreadyUnrolled() {
   MDNode *DisableUnrollMD =
       MDNode::get(Context, MDString::get(Context, "llvm.loop.unroll.disable"));
   MDNode *LoopID = getLoopID();
   MDNode *NewLoopID = makePostTransformationMetadata(
       Context, LoopID, {"llvm.loop.unroll."}, {DisableUnrollMD});
   setLoopID(NewLoopID);
 }
 
+void Loop::setLoopMustProgress() {
+  LLVMContext &Context = getHeader()->getContext();
+
+  MDNode *MustProgress = findOptionMDForLoop(this, "llvm.loop.mustprogress");
+
+  if (MustProgress)
+    return;
+
+  MDNode *MustProgressMD =
+      MDNode::get(Context, MDString::get(Context, "llvm.loop.mustprogress"));
+  MDNode *LoopID = getLoopID();
+  MDNode *NewLoopID =
+      makePostTransformationMetadata(Context, LoopID, {}, {MustProgressMD});
+  setLoopID(NewLoopID);
+}
+
 bool Loop::isAnnotatedParallel() const {
   MDNode *DesiredLoopIdMetadata = getLoopID();
 
   if (!DesiredLoopIdMetadata)
     return false;
 
   MDNode *ParallelAccesses =
       findOptionMDForLoop(this, "llvm.loop.parallel_accesses");