Introduce metadata for avoiding loop predication

[anna]

Summary

This patch introduces the llvm.cond.no_loop_predication which will be
annotated on boolean conditions that are used in branches.
This is used by loop predication to identify loops that should not be
predicated. When the conditional instruction is used as the latch check
in the loop, predicating the loop can cause the widened checks to fail
spuriously.
Such coarse checks (which can later become the latch check through
passes such as loop rotate) can be introduced by the front end or by
downstream passes. Given this metadata is a property of the condition,
we cannot attach it to llvm.loop metadata.

[anna]

Artur had an idea offline that we could use BPI to identify if the latch exit is very rarely taken compared to other exits in the loop. We can teach loop predication to use that information and avoid predication, instead of depending on llvm.cond.donot_predicate metadata.

I'm going to abandon this revision for now and get back in case the above idea of using BPI doesn't pan out for some reason.

docs/LangRef.rst

 .. code-block:: llvm
 
    !0 = !{!"llvm.loop.distribute.enable", i1 0}
    !1 = !{!"llvm.loop.distribute.enable", i1 1}
 
 This metadata should be used in conjunction with ``llvm.loop`` loop
 identification metadata.
 
+'``llvm.cond``'
+^^^^^^^^^^^^^^^
+
+Metadata types used to annotate conditional instructions with information
+helpful for optimizations are prefixed with ``llvm.cond``.
+
+'``llvm.cond.no_loop_predication``' Metadata
+^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
+
+Loop predication tries to convert loop variant range checks to loop invariant
+by widening the checks across loop iterations. This widening is done based on
+the latch check of the loop. In some cases, if the latch check is too coarse,
+it will cause the range check to fail unconditionally when widened to an
+invariant one. These checks which cause the range check to fail spuriously, may 
+be introduced by the front end and LLVM optimizations can transform the loop
+such that this check becomes the latch check.
+The ``llvm.cond.no_loop_predication`` metadata annotated on a conditional
+instruction (for example, icmp) implies that a loop containing this condition
+as the latch condition should not be predicated (see LoopPredication pass).
+
+.. code-block:: llvm
+
+   for.header:
+     %res = call i32 @foo()
+     %origcond = icmp eq i32 %iv, %res
+     br i1 %origcond, label %for.body, label %for.end
+
+   for.body:
+     call void @llvm.experimental.guard(i1 %cond)
+     ...
+     %exitcond = icmp ult i32 %iv, %chunksize, !llvm.cond.no_loop_predication !{}
+     ...
+     br i1 %exitcond, label %for.end, label %for.header
+
+   for.end:
+   ...
+
+During loop predication, we try to predicate the loop above so that the guard
+cond becomes loop invariant. However, the exitcond is too coarse and the real
+loop termination condition is origcond.  Passes (such as loop rotation)
+transformed the loop so that exitcond is the latch condition now.
+So, predicating the loop based on exitcond will cause the guard to fail
+spuriously, whereas it would never fail if left in the loop.
+
 '``llvm.mem``'
 ^^^^^^^^^^^^^^^
 
 Metadata types used to annotate memory accesses with information helpful
 for optimizations are prefixed with ``llvm.mem``.
 
 '``llvm.mem.parallel_loop_access``' Metadata
 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

include/llvm/IR/LLVMContext.h

enum : unsigned {
     MD_align = 17,                    // "align"
     MD_loop = 18,                     // "llvm.loop"
     MD_type = 19,                     // "type"
     MD_section_prefix = 20,           // "section_prefix"
     MD_absolute_symbol = 21,          // "absolute_symbol"
     MD_associated = 22,               // "associated"
     MD_callees = 23,                  // "callees"
     MD_irr_loop = 24,                 // "irr_loop"
+    MD_cond_no_loop_predication = 25, // "llvm.cond.no_loop_predication"
   };
 
   /// Known operand bundle tag IDs, which always have the same value.  All
   /// operand bundle tags that LLVM has special knowledge of are listed here.
   /// Additionally, this scheme allows LLVM to efficiently check for specific
   /// operand bundle tags without comparing strings.
   enum : unsigned {
     OB_deopt = 0,         // "deopt"

lib/IR/LLVMContext.cpp

std::pair<unsigned, StringRef> MDKinds[] = {
     {MD_align, "align"},
     {MD_loop, "llvm.loop"},
     {MD_type, "type"},
     {MD_section_prefix, "section_prefix"},
     {MD_absolute_symbol, "absolute_symbol"},
     {MD_associated, "associated"},
     {MD_callees, "callees"},
     {MD_irr_loop, "irr_loop"},
+    {MD_cond_no_loop_predication, "llvm.cond.no_loop_predication"},
   };
 
   for (auto &MDKind : MDKinds) {
     unsigned ID = getMDKindID(MDKind.second);
     assert(ID == MDKind.first && "metadata kind id drifted");
     (void)ID;
   }
 

lib/Transforms/Scalar/LoopPredication.cpp

if (!match(LoopLatch->getTerminator(),
     DEBUG(dbgs() << "Failed to match the latch terminator!\n");
     return None;
   }
   assert((TrueDest == L->getHeader() || FalseDest == L->getHeader()) &&
          "One of the latch's destinations must be the header");
   if (TrueDest != L->getHeader())
     Pred = ICmpInst::getInversePredicate(Pred);
 
+  {
+    // Loop with latch condition marked with loop predication disable metadata
+    // should not be predicated. This can happen if we rotated the loop
+    // such that this LatchCmp is now the latch condition.
+    auto *LatchCmp = cast<ICmpInst>(
+        cast<BranchInst>(LoopLatch->getTerminator())->getCondition());
+    if (LatchCmp->getMetadata(LLVMContext::MD_cond_no_loop_predication)) {
+      DEBUG(dbgs() << "Marked with loop predication disable metadata!\n");
+      return None;
+    }
+  }
   auto Result = parseLoopICmp(Pred, LHS, RHS);
   if (!Result) {
     DEBUG(dbgs() << "Failed to parse the loop latch condition!\n");
     return None;
   }
 
   // Check affine first, so if it's not we don't try to compute the step
   // recurrence.

test/ThinLTO/X86/lazyload_metadata.ll

 ; Do setup work for all below tests: generate bitcode and combined index
 ; RUN: opt -module-summary %s -o %t.bc -bitcode-mdindex-threshold=0
 ; RUN: opt -module-summary %p/Inputs/lazyload_metadata.ll -o %t2.bc -bitcode-mdindex-threshold=0
 ; RUN: llvm-lto -thinlto-action=thinlink -o %t3.bc %t.bc %t2.bc
 ; REQUIRES: asserts
 
 ; Check that importing @globalfunc1 does not trigger loading all the global
 ; metadata for @globalfunc2 and @globalfunc3
 
 ; RUN: llvm-lto -thinlto-action=import %t2.bc -thinlto-index=%t3.bc \
 ; RUN:          -o /dev/null -stats \
 ; RUN:  2>&1 | FileCheck %s -check-prefix=LAZY
-; LAZY: 55 bitcode-reader  - Number of Metadata records loaded
+; LAZY: 57 bitcode-reader  - Number of Metadata records loaded
 ; LAZY: 2 bitcode-reader  - Number of MDStrings loaded
 
 ; RUN: llvm-lto -thinlto-action=import %t2.bc -thinlto-index=%t3.bc \
 ; RUN:          -o /dev/null -disable-ondemand-mds-loading -stats \
 ; RUN:  2>&1 | FileCheck %s -check-prefix=NOTLAZY
-; NOTLAZY: 64 bitcode-reader  - Number of Metadata records loaded
+; NOTLAZY: 66 bitcode-reader  - Number of Metadata records loaded
 ; NOTLAZY: 7 bitcode-reader  - Number of MDStrings loaded
 
 
 target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-apple-macosx10.11.0"
 
 define void @globalfunc1(i32 %arg) {
   %x = call i1 @llvm.type.test(i8* undef, metadata !"typeid1")

test/Transforms/LoopPredication/basic.ll

; CHECK-NEXT: call void (i1, ...) @llvm.experimental.guard(i1 %within.bounds, i32 9) [ "deopt"() ]
   %i.next = add nuw i32 %i, 1
   %continue = icmp ult i32 %i.next, %n
   br i1 %continue, label %loop, label %exit
 
 exit:
   %result = phi i32 [ 0, %entry ], [ %loop.acc.next, %loop ]
   ret i32 %result
 }
+
+; Avoid predicating the loop if we have a llvm.cond.no_loop_predication
+define i64 @donot_predicate(i64* nocapture readonly %arg, i32 %length, i64* nocapture readonly %arg2, i64* nocapture readonly %n_addr, i64 %i) #0 gc "azul" {
+; CHECK-LABEL: donot_predicate(
+entry:
+  %length.ext = zext i32 %length to i64
+  %n.pre = load i64, i64* %n_addr, align 4
+  br label %Header
+
+; CHECK-LABEL: Header:
+; CHECK:         %within.bounds = icmp ult i64 %j2, %length.ext
+; CHECK-NEXT:    call void (i1, ...) @llvm.experimental.guard(i1 %within.bounds, i32 9)
+Header:                                          ; preds = %entry, %Latch
+  %result.in3 = phi i64* [ %arg2, %entry ], [ %arg, %Latch ]
+  %j2 = phi i64 [ 0, %entry ], [ %j.next, %Latch ]
+  %within.bounds = icmp ult i64 %j2, %length.ext
+  call void (i1, ...) @llvm.experimental.guard(i1 %within.bounds, i32 9) [ "deopt"() ]
+  %innercmp = icmp eq i64 %j2, %n.pre
+  %j.next = add nuw nsw i64 %j2, 1
+  br i1 %innercmp, label %exit, label %Latch
+
+Latch:                                           ; preds = %Header
+  %speculate_trip_count = icmp ult i64 %j.next, 1048576, !llvm.cond.no_loop_predication !{}
+  br i1 %speculate_trip_count, label %deopt, label %Header
+
+deopt:                                            ; preds = %Latch
+  %counted_speculation_failed = call i64 (...) @llvm.experimental.deoptimize.i64(i64 30) [ "deopt"(i32 0) ]
+  ret i64 %counted_speculation_failed
+
+exit:                                             ; preds = %Header
+  %result.in3.lcssa = phi i64* [ %result.in3, %Header ]
+  %result.le = load i64, i64* %result.in3.lcssa, align 8
+  ret i64 %result.le
+}
+declare i64 @llvm.experimental.deoptimize.i64(...)