Allow arbitrary constant expressions to be assigned to const items #570

Closed
brson opened this Issue Jun 24, 2011 · 19 comments

Comments

Projects
None yet
6 participants
@brson
Contributor

brson commented Jun 24, 2011

Right now constants have to be literals and this is getting pretty painful.

@brson

This comment has been minimized.

Show comment Hide comment
@brson

brson Oct 12, 2011

Contributor

This is a pretty good starter project.

Contributor

brson commented Oct 12, 2011

This is a pretty good starter project.

@jwise

This comment has been minimized.

Show comment Hide comment
@jwise

jwise Nov 7, 2011

Contributor

I took a look at this earlier tonight, since I ran into it.

There are a few things; my first attempt was to go after trans_const_expr, and make that function recursive; I'm not sure what the result it would generate would be, though. I tried adding, for instance, a Shl() call, but Shl() takes a block_ctxt, and I've only got a crate_ctxt... Would LLVM be able to reduce this down if I emitted the operations for it? I don't really understand this path very well.

The other option would be to have a reduction mechanism that constant folds down to a literal. This seems like it would be somewhat painful in light of how complex trans_crate_lit is... and it also seems like it is somewhat overly specific to one particular task, whereas constant folding is a pretty general thing.

How do others think that one should approach this?

(I'm not claiming this one just yet. But it's a possibility.)

Contributor

jwise commented Nov 7, 2011

I took a look at this earlier tonight, since I ran into it.

There are a few things; my first attempt was to go after trans_const_expr, and make that function recursive; I'm not sure what the result it would generate would be, though. I tried adding, for instance, a Shl() call, but Shl() takes a block_ctxt, and I've only got a crate_ctxt... Would LLVM be able to reduce this down if I emitted the operations for it? I don't really understand this path very well.

The other option would be to have a reduction mechanism that constant folds down to a literal. This seems like it would be somewhat painful in light of how complex trans_crate_lit is... and it also seems like it is somewhat overly specific to one particular task, whereas constant folding is a pretty general thing.

How do others think that one should approach this?

(I'm not claiming this one just yet. But it's a possibility.)

@brson

This comment has been minimized.

Show comment Hide comment
@brson

brson Nov 7, 2011

Contributor

There's going to have to be a pass before trans that at least reports errors for non-constant const expressions. It could possibly fold the constants and build up a side table in the session object, but then I'm not sure what you would do when constant expressions referred to constants in external crates.

Contributor

brson commented Nov 7, 2011

There's going to have to be a pass before trans that at least reports errors for non-constant const expressions. It could possibly fold the constants and build up a side table in the session object, but then I'm not sure what you would do when constant expressions referred to constants in external crates.

@pcwalton

This comment has been minimized.

Show comment Hide comment
@pcwalton

pcwalton Nov 7, 2011

Contributor

"There are a few things; my first attempt was to go after trans_const_expr, and make that function recursive; I'm not sure what the result it would generate would be, though. I tried adding, for instance, a Shl() call, but Shl() takes a block_ctxt, and I've only got a crate_ctxt... Would LLVM be able to reduce this down if I emitted the operations for it? I don't really understand this path very well."

You need to use the Constant variants of all the operations. These don't need contexts. See the instructions prefixed with LLVMConst in comp/lib/llvm.rs (e.g. LLVMConstShl).

"There's going to have to be a pass before trans that at least reports errors for non-constant const expressions. It could possibly fold the constants and build up a side table in the session object, but then I'm not sure what you would do when constant expressions referred to constants in external crates."

The pass also needs to make sure that constants aren't recursive, rejecting e.g. const a : int = b; const b : int = a + 1.

If we want to support constant expressions that refer to cross-crate constant values, we need an IR. We want an IR for other reasons (monomorphizing), but creating an IR makes this bug decidedly not 'easy' :) For now it would be much easier to support only constant expressions that can be fully resolved by looking in the current crate.

Contributor

pcwalton commented Nov 7, 2011

"There are a few things; my first attempt was to go after trans_const_expr, and make that function recursive; I'm not sure what the result it would generate would be, though. I tried adding, for instance, a Shl() call, but Shl() takes a block_ctxt, and I've only got a crate_ctxt... Would LLVM be able to reduce this down if I emitted the operations for it? I don't really understand this path very well."

You need to use the Constant variants of all the operations. These don't need contexts. See the instructions prefixed with LLVMConst in comp/lib/llvm.rs (e.g. LLVMConstShl).

"There's going to have to be a pass before trans that at least reports errors for non-constant const expressions. It could possibly fold the constants and build up a side table in the session object, but then I'm not sure what you would do when constant expressions referred to constants in external crates."

The pass also needs to make sure that constants aren't recursive, rejecting e.g. const a : int = b; const b : int = a + 1.

If we want to support constant expressions that refer to cross-crate constant values, we need an IR. We want an IR for other reasons (monomorphizing), but creating an IR makes this bug decidedly not 'easy' :) For now it would be much easier to support only constant expressions that can be fully resolved by looking in the current crate.

@jwise

This comment has been minimized.

Show comment Hide comment
@jwise

jwise Nov 7, 2011

Contributor

Right, yeah. I just rolled out of bed and looked at my e-mail, and I saw "[...] constants in external crates [...]", and went "Uh-oh... I'm not sure on what planet this is 'easy'..." :)

So I guess the next thing to look at is where to insert another pass. I'll take a look at that if I get some free time today.

Contributor

jwise commented Nov 7, 2011

Right, yeah. I just rolled out of bed and looked at my e-mail, and I saw "[...] constants in external crates [...]", and went "Uh-oh... I'm not sure on what planet this is 'easy'..." :)

So I guess the next thing to look at is where to insert another pass. I'll take a look at that if I get some free time today.

@jwise

This comment has been minimized.

Show comment Hide comment
@jwise

jwise Nov 8, 2011

Contributor

We discussed this on IRC today, and here are the conclusions so far:

  • A pass should be added in rustc::driver::rustc::compile_input before translation just to verify that constant expressions are 1) constant, and 2) non-recursive. The way to do this would be to set up an AST visitor looking for ast::item_const.
  • By the time trans_const_expr is invoked, the crate_ctxt already has a translation from every AST node_id (i.e., every other const) to a ValueRef. So, for constants that reference other constants, they can be translated on demand, and then their ValueRef can be used. To generate ValueRefs for other constants, look at LLVMConstShl and friends.

I think I'm going to take a swing at the constant verification pass first, since I know that if I do the trans pass first, I won't want to bother coming back to the verification pass. We'll see how it goes.

Contributor

jwise commented Nov 8, 2011

We discussed this on IRC today, and here are the conclusions so far:

  • A pass should be added in rustc::driver::rustc::compile_input before translation just to verify that constant expressions are 1) constant, and 2) non-recursive. The way to do this would be to set up an AST visitor looking for ast::item_const.
  • By the time trans_const_expr is invoked, the crate_ctxt already has a translation from every AST node_id (i.e., every other const) to a ValueRef. So, for constants that reference other constants, they can be translated on demand, and then their ValueRef can be used. To generate ValueRefs for other constants, look at LLVMConstShl and friends.

I think I'm going to take a swing at the constant verification pass first, since I know that if I do the trans pass first, I won't want to bother coming back to the verification pass. We'll see how it goes.

@jwise

This comment has been minimized.

Show comment Hide comment
@jwise

jwise Nov 9, 2011

Contributor

So, here's a question -- which AST nodes do we wish to allow? There are plenty of things that "can" be constant, but would be a huge pain -- consider:

const a : int = {
    let b = 5;
    b
};

This doesn't translate obviously to an LLVMConst expression. Similarly, the following is constant, and even provably constant!, but a big pain:

const a : int = if true then {3; 5} else {4; 6};

But, the following should presumably be permitted:

const a : int = true ? 5 : 6;

How do we decide what to allow? Rust doesn't have a meaningful definition of an "expression", like C does, so we can't very well just say "only expressions, not blocks, are allowed". Thoughts?

Contributor

jwise commented Nov 9, 2011

So, here's a question -- which AST nodes do we wish to allow? There are plenty of things that "can" be constant, but would be a huge pain -- consider:

const a : int = {
    let b = 5;
    b
};

This doesn't translate obviously to an LLVMConst expression. Similarly, the following is constant, and even provably constant!, but a big pain:

const a : int = if true then {3; 5} else {4; 6};

But, the following should presumably be permitted:

const a : int = true ? 5 : 6;

How do we decide what to allow? Rust doesn't have a meaningful definition of an "expression", like C does, so we can't very well just say "only expressions, not blocks, are allowed". Thoughts?

@jwise

This comment has been minimized.

Show comment Hide comment
@jwise

jwise Nov 9, 2011

Contributor

Well, actually, the "if" example is not so big of a pain ... but the "let" example certainly is.

Contributor

jwise commented Nov 9, 2011

Well, actually, the "if" example is not so big of a pain ... but the "let" example certainly is.

@brson

This comment has been minimized.

Show comment Hide comment
@brson

brson Nov 9, 2011

Contributor

I would start with something small, that has an obvious implementation, like scalars with binops and unops. Nothing that involves branching. We can always expand what's legal later.

Contributor

brson commented Nov 9, 2011

I would start with something small, that has an obvious implementation, like scalars with binops and unops. Nothing that involves branching. We can always expand what's legal later.

@jwise

This comment has been minimized.

Show comment Hide comment
@jwise

jwise Nov 9, 2011

Contributor

I have bits in flight -- see the above referenced commits. Since make check seemed to crash and burn on my OS X laptop even before I touched anything, I'm kicking off a make check on my (slow) Linux machine; if all goes well, I'll submit a pull request when I wake up.

Contributor

jwise commented Nov 9, 2011

I have bits in flight -- see the above referenced commits. Since make check seemed to crash and burn on my OS X laptop even before I touched anything, I'm kicking off a make check on my (slow) Linux machine; if all goes well, I'll submit a pull request when I wake up.

@brson

This comment has been minimized.

Show comment Hide comment
@brson

brson Nov 9, 2011

Contributor

Why was make check failing on OS X?

Contributor

brson commented Nov 9, 2011

Why was make check failing on OS X?

@jwise

This comment has been minimized.

Show comment Hide comment
@jwise

jwise Nov 9, 2011

Contributor

Tests ended up being fine, so I'm opening a pull request. I had to test with --disable-valgrind, otherwise I got:

location should start with fun: or obj:
==21742== FATAL: in suppressions file '../src/etc/x86.supp': location should start with 'fun:' or 'obj:'
==21742== exiting now.

make check was failing on OS X because my laptop's valgrind install is also completely toast.

Contributor

jwise commented Nov 9, 2011

Tests ended up being fine, so I'm opening a pull request. I had to test with --disable-valgrind, otherwise I got:

location should start with fun: or obj:
==21742== FATAL: in suppressions file '../src/etc/x86.supp': location should start with 'fun:' or 'obj:'
==21742== exiting now.

make check was failing on OS X because my laptop's valgrind install is also completely toast.

@boggle

This comment has been minimized.

Show comment Hide comment
@boggle

boggle Nov 26, 2011

Contributor

Can you please consider #1215 in this context?

Contributor

boggle commented Nov 26, 2011

Can you please consider #1215 in this context?

@jwise

This comment has been minimized.

Show comment Hide comment
@jwise

jwise Nov 26, 2011

Contributor

@boggle, I could add this as a special case in this logic, but it seems that the mechanism you described in #1215 -- dropping it in a pass -- seems like the right thing. Thoughts from others?

Contributor

jwise commented Nov 26, 2011

@boggle, I could add this as a special case in this logic, but it seems that the mechanism you described in #1215 -- dropping it in a pass -- seems like the right thing. Thoughts from others?

@boggle

This comment has been minimized.

Show comment Hide comment
@boggle

boggle Dec 2, 2011

Contributor

Have submitted a patch for #1215 that allows trivial casts (cast to machine-equivalent type) in const exprs. Are you aware of #571? Are you working on allowing references to other consts in const exprs? As soon as that is there, I could simplify std::math* once more.

Contributor

boggle commented Dec 2, 2011

Have submitted a patch for #1215 that allows trivial casts (cast to machine-equivalent type) in const exprs. Are you aware of #571? Are you working on allowing references to other consts in const exprs? As soon as that is there, I could simplify std::math* once more.

@ghost ghost assigned catamorphism Mar 15, 2012

@catamorphism

This comment has been minimized.

Show comment Hide comment
@catamorphism

catamorphism Mar 15, 2012

Contributor

@jwise - are you still working on this? If not, I'll take over.

Contributor

catamorphism commented Mar 15, 2012

@jwise - are you still working on this? If not, I'll take over.

@jwise

This comment has been minimized.

Show comment Hide comment
@jwise

jwise Mar 15, 2012

Contributor

I got around as far as seemed easy for me. If you have a clear path forward, go for it!

I am also on IRC sometimes (ping me as joshua_), but less today and tomorrow (on vacation). If you have other stuff to parallelize out to me, I have some time to hack on Rust this weekend.

Tim Chevalier reply@reply.github.com wrote:

@jwise - are you still working on this? If not, I'll take over.


Reply to this email directly or view it on GitHub:
mozilla#570 (comment)

Contributor

jwise commented Mar 15, 2012

I got around as far as seemed easy for me. If you have a clear path forward, go for it!

I am also on IRC sometimes (ping me as joshua_), but less today and tomorrow (on vacation). If you have other stuff to parallelize out to me, I have some time to hack on Rust this weekend.

Tim Chevalier reply@reply.github.com wrote:

@jwise - are you still working on this? If not, I'll take over.


Reply to this email directly or view it on GitHub:
mozilla#570 (comment)

@catamorphism

This comment has been minimized.

Show comment Hide comment
@catamorphism

catamorphism Mar 15, 2012

Contributor

@jwise -- Ok, I have quite a few issues on my plate, so feel free to do more work on it if you're not seeing progress here, but otherwise I'll get around to it eventually.

Contributor

catamorphism commented Mar 15, 2012

@jwise -- Ok, I have quite a few issues on my plate, so feel free to do more work on it if you're not seeing progress here, but otherwise I'll get around to it eventually.

@brson

This comment has been minimized.

Show comment Hide comment
@brson

brson Apr 5, 2012

Contributor

@boggle: consts can reference other consts now, but only within the same crate.

Contributor

brson commented Apr 5, 2012

@boggle: consts can reference other consts now, but only within the same crate.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment