LLVM intrinsic for invariants

[hfinkel]

Summary

Adds void @llvm.invariant(i1 %cond)

[hfinkel]

This adds the basic invariant intrinsic, noop lowering, and some basic properties:

• llvm.invariant(undef) and llvm.invariant(true) are dead
• llvm.invariant(false) is unreachable (this directly corresponds to the documented behavior of MSVC's __assume(0))

The intrinsic is tagged as writing arbitrarily, in order to maintain control dependencies. BasicAA has been updated, however, to return NoModRef for any particular location-based query so that we don't unnecessarily block code motion.

[hfinkel]

Rebased.

[chandlerc]

docs/LangRef.rst

9304 ↗

(On Diff #11590)

I wonder if this would be more clear spelled "llvm.assume.invariant" or just "llvm.assume".

9321–9324 ↗

(On Diff #11590)

I think we should provide some minimal guidance for FE authors here that essentially indicates that using this intrinsic is not without cost, and essentially shouldn't be used to either document basic mathematical invariants the compiler could deduce otherwise, or if the invariant holds little or no value to the optimizer.

lib/Transforms/Utils/Local.cpp

305 ↗

(On Diff #11590)

If the condition is undef, aren't they unreachable?

test/Transforms/InstSimplify/invariant.ll

3–5 ↗

(On Diff #11590)

Indent seems weird here. Use the more common 2-space indent?

[hfinkel]

Updated docs and made invariant(undef) like invariant(false) (instead of like invariant(true)).

[hfinkel]

Renamed to llvm.assume.

[reames]

With a couple of small changes mentioned inline, LGTM.

docs/LangRef.rst

9383 ↗

(On Diff #11693)

Why? Suggestion:
Please note that ''llvm.assume'' is not free and may impact the effectiveness of the optimizer in hard to predict ways. ''llvm.assume'' should be used to represent high level facts which are not otherwise available to the optimizer and only after careful consideration of the benefit and costs. In particular, 'llvm.assume'' should not be used to...

I'm not sure I really like my wording around 'free' above, but this is a starting point.

include/llvm/IR/Intrinsics.td

282 ↗

(On Diff #11693)

I understand why you're doing this, but it honestly feels like a bit of a hack. Is it possibly time to introduce a notion of control dependence that is not driven by memory access? This is essentially what you've written, but there might be a better way to factor it.

This doesn't need to be changed before submission, I'm just raising it for consideration and discussion.

lib/Analysis/BasicAliasAnalysis.cpp

799 ↗

(On Diff #11693)

I've noticed we have multiple isXIntrinsic functions scatter around the code base. We might want to think about - in a separate change - creating an isIntrinsic(IntrinsicID) function on CallSite.

lib/Transforms/Utils/Local.cpp

1199 ↗

(On Diff #11693)

Adding a comment on this case would be good. Particularly given that it required discussion to arrive at this being the right semantic.

test/CodeGen/Generic/assume.ll

1 ↗

(On Diff #11693)

This test could be stronger. Could you add a FileCheck here?

[hfinkel]

docs/LangRef.rst

9383 ↗

(On Diff #11693)

Good idea. Instead of "free", I'll say something like, "The optimizer might limit the transformations performed on values used by the intrinsic in order to preserve the instructions only used to form the intrinsic's input argument, and this might prove undesirable if the extra information provided by that intrinsic does cause sufficient overall improvement."

include/llvm/IR/Intrinsics.td

282 ↗

(On Diff #11693)

Fixing this is another major infrastructure project. :(

lib/Analysis/BasicAliasAnalysis.cpp

799 ↗

(On Diff #11693)

Good idea; I'll queue that for later refactoring.

lib/Transforms/Utils/Local.cpp

1199 ↗

(On Diff #11693)

Will do.

test/CodeGen/Generic/assume.ll

1 ↗

(On Diff #11693)

No, this is a "generic lowering" test. It runs on all targets to make sure that it does not crash (that the code generator does *something*). You'll find many such tests in that directory.

[hfinkel]

Philip accepted (with minor updates); I'll commit in the near future.

[hfinkel]

r213973, thanks!

docs/LangRef.html

<ol>
             '<tt>llvm.trap</tt>' Intrinsic</a></li>
           <li><a href="#int_debugtrap">
             '<tt>llvm.debugtrap</tt>' Intrinsic</a></li>
           <li><a href="#int_stackprotector">
             '<tt>llvm.stackprotector</tt>' Intrinsic</a></li>
           <li><a href="#int_objectsize">
             '<tt>llvm.objectsize</tt>' Intrinsic</a></li>
           <li><a href="#int_expect">
+            '<tt>llvm.invariant</tt>' Intrinsic</a></li>
+          <li><a href="#int_invariant">
             '<tt>llvm.expect</tt>' Intrinsic</a></li>
           <li><a href="#int_donothing">
             '<tt>llvm.donothing</tt>' Intrinsic</a></li>
         </ol>
       </li>
     </ol>
   </li>
 </ol>
<p>The <tt>llvm.expect</tt> intrinsic takes two arguments. The first
    be a constant value, variables are not allowed.</p>
 
 <h5>Semantics:</h5>
 <p>This intrinsic is lowered to the <tt>val</tt>.</p>
 </div>
 
 <!-- _______________________________________________________________________ -->
 <h4>
+  <a name="int_invariant">'<tt>llvm.invariant</tt>' Intrinsic</a>
+</h4>
+
+<div>
+
+<h5>Syntax:</h5>
+<pre>
+  declare void @llvm.invariant(i1 %cond)
+</pre>
+
+<h5>Overview:</h5>
+<p>The '<tt>llvm.invariant</tt>' intrinsic allows the optimizer to assume
+   that the provided condition is true. This information can then be used
+   in simplifying other parts of the code.</p>
+
+<h5>Arguments:</h5>
+
+<p>The condition which the optimizer may assume is always true.</p>
+
+<h5>Semantics:</h5>
+
+<p>The intrinsic allows the optimizer to assume that the provided condition is
+   always true. No code is generated for this intrinsic, and instructions that
+   contribute only to the provided condition are not used for code generation.</p>
+</div>
+
+<!-- _______________________________________________________________________ -->
+<h4>
   <a name="int_donothing">'<tt>llvm.donothing</tt>' Intrinsic</a>
 </h4>
 
 <div>
 
 <h5>Syntax:</h5>
 <pre>
   declare void @llvm.donothing() nounwind readnone

include/llvm/Intrinsics.td

 def int_prefetch      : Intrinsic<[],
                                   [llvm_ptr_ty, llvm_i32_ty, llvm_i32_ty,
                                    llvm_i32_ty],
                                   [IntrReadWriteArgMem, NoCapture<0>]>;
 def int_pcmarker      : Intrinsic<[], [llvm_i32_ty]>;
 
 def int_readcyclecounter : Intrinsic<[llvm_i64_ty]>;
 
+def int_invariant     : Intrinsic<[], [llvm_i1_ty], [IntrNoMem]>;
+
 // Stack Protector Intrinsic - The stackprotector intrinsic writes the stack
 // guard to the correct place on the stack frame.
 def int_stackprotector : Intrinsic<[], [llvm_ptr_ty, llvm_ptrptr_ty], []>;
 
 //===------------------- Standard C Library Intrinsics --------------------===//
 //
 
 def int_memcpy  : Intrinsic<[],