Added llvm.is.constant intrinsic
Needs ReviewPublic

Authored by jyknight on Jun 24 2014, 8:44 AM.

Details

Summary

Add support for llvm.is.constant intrinsic (PR4898)

This adds llvm-side support for post-inline evaluation of the __builtin_constant_p GCC intrinsic.

janusz retitled this revision from to Added llvm.is.constant intrinsic.Jun 24 2014, 8:44 AM
janusz updated this object.
janusz edited the test plan for this revision. (Show Details)
janusz added a reviewer: rengolin.
janusz set the repository for this revision to rL LLVM.

I'd add a bit more of tests, especially those that inspired this change...

--renato

docs/LangRef.rst
7178 ↗(On Diff #10791)

... to the best of the compiler's knowledge ... :)

janusz updated this revision to Diff 10829.Jun 25 2014, 5:29 AM

Added a test case for inlining @llvm.is.constant

janusz updated this revision to Diff 10830.Jun 25 2014, 5:32 AM

Uploading again :)

janusz set the repository for this revision to rL LLVM.Jun 25 2014, 5:36 AM
janusz added a project: deleted.
janusz added a subscriber: Unknown Object (MLST).

Thanks Janusz,

I'm adding Owen to review this patch, since it's not my area, but overall, the patch looks good.

About the tests, though the inline check is important, I was thinking something more elaborate.

Some examples that come to mind:

  • static initializer
  • generic function arguments
  • function arguments where the function is static and only called one with a constant argument
  • function arguments where the function is static and only called one with a variable argument
  • expressions that will be simplified as constant because all variables were initialised with constants
  • expressions that will NOT be simplified as constant because NOT all variables were initialised with constants

Those examples that *should* be constant and are not, should be marked as FIXME. Those examples that *should* NOT be constant and are, should be fixed before commit.

cheers,
--renato

test/CodeGen/Generic/inline-is-constant.ll
4 ↗(On Diff #10830)

a more robust way would be to have two run lines, one with O0, another with O3, and use FileCheck for the True/False results.

I agree that we should have more tests. I'd prefer to have an agreement that we want to add llvm.is.constant intrinsic before spending too much time on writing tests.

A follow up work is to add support for the new intrinsic in clang (__builtin_constant_p -> llvm.is.constant) and write more tests in C.

I have a few questions.

  1. Do we want the code to promote or expand llvm.is.constant? On one hand it would make the code more complete but on the other it is not really required because zext() and trunc() don't change the 'constantness'
	%a = zext i1 %b to i32
	%v = call i1 @llvm.is.constant.i32(i32 %a)

and

	%a = trunc i256 %b to i32
	%v = call i1 @llvm.is.constant.i32(i32 %a)

will do the job. Is there a preference in the llvm community?

  1. In my implementation llvm.is.constant is lowered to true/false rather late. Would it help in some cases if we added an early check in InstCombine? InstCombine would lower llvm.is.constant to true if the argument is known to be constant. Otherwise InstCombine would leave it unmodified.
janusz added inline comments.Jun 25 2014, 8:22 AM
test/CodeGen/Generic/inline-is-constant.ll
4 ↗(On Diff #10830)

If using lli is frowned upon, then the resolution is to call 'llc -debug' and search for the debug strings with FileCheck

Ccing nick since it seems related to the enable_if attribute.

janusz updated this revision to Diff 10884.Jun 26 2014, 7:03 AM

Moved lowering llvm.is.constant to False from LegalizeDAG to SelectionDAG. Code to promote or expand llvm.is.constant is not required any more and the intrinsic works fine with different input integer types.

rengolin added inline comments.Jun 30 2014, 3:34 AM
docs/LangRef.rst
7164 ↗(On Diff #10884)

As I understand, __builtin_constant_p can be used with any valid expression, and "constant" is the C semantics, so a numeric expression is constant if all its arguments are, string literals are always constant, but pointers are a bit more complicated.

Since this is a GNU extension and we're trying to implement it, it would be wise to add a FIXME and some comments on this documentation to that effect, if our intentions is to not expand to full expresisons, or to do so in the future.

janusz updated this object.Jul 14 2014, 5:24 AM
In D4276#14, @janusz wrote:
  1. Do we want the code to promote or expand llvm.is.constant? On one hand it would make the code more complete but on the other it is not really required because zext() and trunc() don't change the 'constantness'

Depends on how hard would it be to infer constantness at a lower level with the added complexity. I'd say, as a general idea, leaving the IR untouched and adding logic to infer that later would be better, but I'm not sure of all the cases.

  1. In my implementation llvm.is.constant is lowered to true/false rather late. Would it help in some cases if we added an early check in InstCombine? InstCombine would lower llvm.is.constant to true if the argument is known to be constant. Otherwise InstCombine would leave it unmodified.

Yes, that'd be great. I think we could teach even Clang about that, so that pre-processor constantness is explited at the front-end level. Though, I understand if those things take their time to get implemented.

Any progress in this? If not, can we close this review?

rengolin resigned from this revision.Mar 13 2015, 3:13 AM
rengolin removed a reviewer: rengolin.
jyknight commandeered this revision.Apr 13 2018, 10:02 AM
jyknight added a reviewer: janusz.
jyknight added a subscriber: jyknight.

Taking this over.

jyknight updated this revision to Diff 142433.Apr 13 2018, 10:14 AM

Rewrote patch significantly.

  • Added support for other types.
  • Deleted SelectionDAG-side IS_CONSTANT as unneeded.
  • Added support in CodeGenPrepare to lower to false, as ISel cannot eliminate unreachable blocks. (similar to llvm.objectsize)

Updated and added more tests;

jyknight edited the summary of this revision. (Show Details)Apr 13 2018, 10:15 AM
jyknight added a reviewer: void.

It seems like you're waiting to fold llvm.is.constant until really late in the optimization pipeline; we probably want to fold it sometime in the "middle", so we get better optimization. Maybe just after function simplification passes; at that point, we're unlikely to get any more useful information about whether the argument is constant, and we want to simplify the code as much as possible before we run transforms like loop vectorization.

llvm/lib/Analysis/ConstantFolding.cpp
1592

Probably doesn't make sense to check for ConstantExpr here; if isManifestConstant is true for all the operands of a ConstantExpr, it should get constant-folded.

llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp
5762

Indentation.

jyknight added a comment.EditedApr 13 2018, 12:43 PM

It seems like you're waiting to fold llvm.is.constant until really late in the optimization pipeline; we probably want to fold it sometime in the "middle", so we get better optimization. Maybe just after function simplification passes; at that point, we're unlikely to get any more useful information about whether the argument is constant, and we want to simplify the code as much as possible before we run transforms like loop vectorization.

The most important constraint is that it needs to occur after inlining.

However, we already have llvm.objectsize intrinsic, and I wanted to handle the final failure in the same place, so that __builtin_constant_p works when given __builtin_object_size as an argument, even when the __builtin_object_size is unevaluable (and returns -1).

E.g. in GCC, this code:

int f1(char* x) {
    if (__builtin_constant_p(__builtin_object_size(x, 0))) {
        return __builtin_object_size(x, 0);
    }
    return -9999;
}

int f2() {
    char x[1000];
    return f1(x);
}

compiles such that:

f1 -> returns (constant) -1.
f2 -> returns (constant) 1000.

It's possible that both of them should move somewhere else, though...

llvm/lib/Analysis/ConstantFolding.cpp
1592

If I remove that, then this clause fails in the test case:

@llvm.is.constant.p0i64(i64* inttoptr (i32 42 to i64*))

because there's no way to express a pointer with a constant value directly.

I guess lowering llvm.objectsize and llvm.is.constant at the same time makes sense; okay. They should probably both be lowered earlier, though.

llvm/lib/Analysis/ConstantFolding.cpp
1592

Okay.

void added inline comments.Apr 13 2018, 2:29 PM
llvm/docs/LangRef.rst
14432–14433

This is true only for expressions that evaluate to constants not immediates, right?

Should you also mention that if a function with llvm.is.constant() is inlined, any constants fed into the inlined function may cause llvm.is.constant() to return true? (or something to that affect)

llvm/include/llvm/IR/Intrinsics.td
838

80-columns?

llvm/lib/Transforms/Scalar/SCCP.cpp
1176

This seems unrelated. Was it meant to be in this patch? If so, could you comment that it's specifically related to llvm.is.constant()?

jyknight updated this revision to Diff 142474.Apr 13 2018, 3:17 PM
jyknight edited the summary of this revision. (Show Details)

Ran clang-format.
Expanded on docs.

llvm/docs/LangRef.rst
14432–14433

If you build with -O0, constant folding is not done, so even the @test_constant() function will return false.

(Of course, at the C level, the __builtin_constant_p intrinsic will still return true at -O0 when given a frontend constant).

Updated the docs to mention inlining explicitly.

llvm/include/llvm/IR/Intrinsics.td
838

Fixed.

llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp
5762

Fixed.

llvm/lib/Transforms/Scalar/SCCP.cpp
1176

It's due to llvm.is.constant being able to take a struct type as an argument. This code gets confused by seeing a call for which is canConstantFoldCallTo() returns true, but which can take a struct as an argument.

I'll add a bit to the commit message remarking why the change was made, but I don't think the code here really need mention llvm.is.constant.

void added inline comments.Apr 13 2018, 4:24 PM
llvm/docs/LangRef.rst
14432–14433

My comment is for documenting the llvm.is.constant intrinsic, not __builtin_constant_p(). :-) (People can write their own .ll files.) I just wanted to make sure that people know that this will evaluate to "true" even without constant folding:

%0 = i1 llvm.is.constant.i32(i32 37)
llvm/lib/Transforms/Scalar/SCCP.cpp
1176

I'm still a bit confused. This change will affect all call sites, not just those to llvm.is.constant. Or are you saying that the only time this situation will come up is when it involves the llvm.is.constant call?

jyknight added inline comments.Apr 13 2018, 5:42 PM
llvm/docs/LangRef.rst
14432–14433

Except that that it really _doesn't_ evaluate to true. :)

The only thing that turns a call to llvm.is.constant into "true" is the constant folding code, which doesn't get run in O0.

llvm/lib/Transforms/Scalar/SCCP.cpp
1176

This code cannot handle calls with a struct as an argument, it hits an assertion failure about not expecting a struct.

But it only ran in the first place when canConstantFoldCallTo returns true (see up a few lines at 1171), so it didn't actually come up before, because the other functions don't take structs as arguments.

void added inline comments.Apr 15 2018, 3:08 AM
llvm/docs/LangRef.rst
14432–14433

But why couldn't it evaluate to true at O0? Is there a valid reason why not? I mean, the intrinsic has to be lowered somehow at O0, so why not just evaluate it to true in cases like this?

llvm/lib/Transforms/Scalar/SCCP.cpp
1176

Ah! I see. Thanks.

void added a comment.Apr 18 2018, 11:33 AM

Friendly ping? :-)

jyknight added inline comments.Apr 19 2018, 6:30 PM
llvm/docs/LangRef.rst
14432–14433

Yes, all the places it's lowered to false now in O0 (GlobalISel/IRTranslator.cpp, SelectionDAG/FastISel.cpp, SelectionDAG/SelectionDAGBuilder.cpp) could check if it can be folded to true first. It feels somewhat ugly to have to do that, though.

Of course, it's ugly that we have to do this last-chance lowering in 3 places in the first place. Same issue exists for llvm.objectsize too. Like efriedma suggested earlier, they should probably be both be lowered somewhere else...I'm not really sure where the best elsewhere to move it would be, though.

void added a comment.Apr 19 2018, 6:35 PM

I have no more concerns with this patch.

Eli, Are you okay to approve this?

llvm/docs/LangRef.rst
14432–14433

It certainly is ugly that we have this in three places instead of one. Anyway, I suppose that as long as we document its behavior correctly, people won't complain. (And it's at -O0, so speed isn't the issue I suppose.)

Needs a testcase for the SCCP fix. Otherwise LGTM.

void added a comment.Jun 3 2018, 10:44 PM

Friendly ping. :-)

This feature would be very useful to us and testing this patch against our code base gave us an interesting case where llvm.is.constant (used in a conditional) is lowered to false in CodeGenPrepare and the dead branch that arises out of this lowering does not get eliminated. The code that gets generated after CodeGenPrepare pass has "br i1 false .." with both true and false conditions preserved and this propagates further and remains the same in the final assembly code.

In CodeGenPrepare::runOnFunction, ConstantFoldTerminator (which handles the br i1 false condition) is called only once and if after the transformation of ConstantFoldTerminator() and DeleteDeadBlock(), if we end up with code like "br i1 false", there is no further opportunity to clean them up. So calling the code under ' if (!DisableBranchOpts)' in a loop that is conditioned on MadeChange (similar to other places), fixes the issue. Is this reasonable ?

I wrote a patch to test this and I have one regression with llvm/test/CodeGen/AMDGPU/nested-loop-conditions.ll. I'm having some difficulty to determine if this warrants rewriting the test case to adjust with the new results or if this is a real issue.

Any pointers would be greatly appreciated. My simple fix (without any indentation changes) is:

--- a/llvm/lib/CodeGen/CodeGenPrepare.cpp
+++ b/llvm/lib/CodeGen/CodeGenPrepare.cpp
@@ -316,7 +316,9 @@ bool CodeGenPrepare::runOnFunction(Function &F) {
 
   SunkAddrs.clear();
 
+  MadeChange = true;
   if (!DisableBranchOpts) {
+  while (MadeChange) {
     MadeChange = false;
     SmallPtrSet<BasicBlock*, 8> WorkList;
     for (BasicBlock &BB : F) {
@@ -352,6 +354,7 @@ bool CodeGenPrepare::runOnFunction(Function &F) {
 
     EverMadeChange |= MadeChange;
   }
+ }
 
   if (!DisableGCOpts) {
     SmallVector<Instruction *, 2> Statepoints;

Thanks.

void added a comment.Aug 28 2018, 2:33 AM

What's the status of this patch? I'm running into a situation where evaluating __builtin_constant_p through inlining may be useful.

niravd added a subscriber: niravd.Mon, Oct 1, 1:16 PM