Add a phase that removes ResolvedTypeRefs before codegen #534

fitzgen · 2017-02-21T16:54:03Z

Ever since we got the graphviz visualizations of our IR graph, it has become immediately clear that we have a TON of ResolvedTypeRefs all over the place. In fact, 8 out of 15 IR items (more than half!) are ResolvedTypeRefs in this example I happen to be looking at:

A pass over the IR items where we replace all references to ResolvedTypeRefs with references to the type being transitively referenced via the ResolvedTypeRef would probably give us speed ups in codegen and analysis, because we wouldn't have to look at useless items anymore. It would also make looking at these graphs easier, since there would be less visual noise :-P

A good time to do this would be in ir::context::BindgenContext::gen, after we resolve unresolved type refs in resolve_typerefs. https://github.com/servo/rust-bindgen/blob/master/src/ir/context.rs#L529

I can mentor whoever would like to take a stab at this.

The text was updated successfully, but these errors were encountered:

fitzgen · 2017-02-21T16:58:58Z

If you want to pick this up, leave a comment and I can assign you :)

samliu · 2017-02-21T17:48:25Z

Hey Nick! (How are you?!) I've been learning Rust and this looks really interesting. I'd be down to take a stab :)

fitzgen · 2017-02-21T18:33:44Z

Great! Let me know if you have any questions or anything like that.

I just realized that fully removing ResolvedTypeRefs would require modifying ir::traversal::Trace to be generic over either &mut ItemId edges or just ItemIds like it is now. This is a bit more tricky than I anticipated, and so I think we should resign ourselves to flattening ResolvedTypeRef chains to a single ResolvedTypeRef. That is,

ResolvedTypeRef -> ResolvedTypeRef -> ResolvedTypeRef -> SomeType

should become:

ResolvedTypeRef -> SomeType

The core of this new phase should look something like this pseudo code:

impl BindgenContext {
    // ...

    fn flatten_resolved_type_ref(&mut self) {
        for (id, item) in self.items {
            if item is a resolved type ref {
                self.flatten_one_resolved_type_ref(id);
            }
        }
    }

    // Recursively walk the chain of ResolvedTypeRefs and flatten it as we
    // come back out of the recursion.
    fn flatten_one_resolved_type_ref(&mut self, id: ItemId) -> ItemId { 
        if id's item is a resolved type ref {
            let final_referenced_id = self.flatten_one_resolved_type_ref(item's referenced type);
            item's referenced type = final_referenced_id;
            final_referenced_id
        } else {
            id
        }
    }

    // ...
}

Bonus points for keeping a debug-only set of items we've walked in the recursive function and asserting that we don't get a cycle :) See https://github.com/servo/rust-bindgen/blob/master/src/ir/item.rs#L69-L87

fitzgen · 2017-02-21T19:39:06Z

(Also, woah! Hey! Didn't read your username very carefully, at first! :-P)

emilio · 2017-02-22T11:06:30Z

I have an issue with this, and is that this would lose the constness information, which we do use for code generation.

fitzgen · 2017-02-22T15:44:52Z

I have an issue with this, and is that this would lose the constness information, which we do use for code generation.

Crap, I forgot about that. It would be great if we separated the concept of a resolved type reference from a const <type>, then we could move forward here.

@samliu interested in this prerequisite groundwork?

samliu · 2017-02-22T16:44:37Z

Definitely!

…

On Feb 22, 2017 7:44 AM, "Nick Fitzgerald" ***@***.***> wrote: I have an issue with this, and is that this would lose the constness information, which we do use for code generation. Crap, I forgot about that. It would be great if we separated the concept of a resolved type reference from a const <type>, then we could move forward here. @samliu <https://github.com/samliu> interested in this prerequisite groundwork? — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub <#534 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AAIS_T9m-04rdhW-glpN8zWbTZbxX0e6ks5rfFf1gaJpZM4MHk79> .

emilio · 2017-02-23T00:01:53Z

As an idea, we probably want to call this something like QualifiedType,
and it'd be something like:

struct Qualifiers {
    is_const: bool,
}

struct QualifiedType {
    ty: ItemId,
    qualifiers: Qualifiers,
}

fitzgen · 2017-02-23T00:08:27Z

Yep, exactly what I was imagining!

It will also need to be Traced from the impl Trace for Type as well (either directly there, or as a second Trace implementation that is called from there).

fitzgen · 2017-02-23T00:09:24Z

(And there would be a new TypeKind variant called TypeKind::Qualified(QualifiedType) or something)

emilio · 2017-02-23T00:37:29Z

(And there would be a new TypeKind variant called TypeKind::Qualified(QualifiedType) or something)

Why would that be needed? We only care about qualifiers in top-level types, right?

I.e., const StructName* foo; would be a TypeKind::Pointer(QualifiedType), and so on with fields, arrays, etc.

Am I missing something?

emilio · 2017-02-23T00:38:15Z

Why would that be needed? We only care about qualifiers in top-level types, right?

With top-level types, I mean in the stuff that holds from TypeKind, Var, etc.

fitzgen · 2017-02-23T00:40:30Z

I don't understand the distinction you are trying to make, sorry if I'm being thick...

fitzgen · 2017-02-23T00:48:55Z

I.e., const StructName* foo; would be a TypeKind::Pointer(QualifiedType), and so on with fields, arrays, etc.

Aha, I see where our imaginations are diverging.

I would imagine const Structname* to result in IR like

ItemId(0) = Item(TypeKind::Pointer(ItemId(1)))
ItemId(1) = Item(TypeKind::Qualified(ItemId(2)))
ItemId(2) = Item(TypeKind::Comp(StructName))

emilio · 2017-02-23T01:23:10Z

Right, I was imagining making QualifiedType a thin wrapper on top of an ItemId. I think it's worth for a few reasons:

First, you don't need all the memory impact of an Item to just indicate that a type is const.
Second, I think the qualifications are orthogonal to the type, so I think having a type being a qualified type is confusing. Also, we'd need to guarantee that a TypeKind::Qualified wouldn't point to another of the same kind, etc.
Third, the approach you're suggesting makes us having to create two items in common paths that now create one (like pointer construction), which would be a bigger refactor than needed IMO.
Finally, clang seems to agree with me in this regard, and it uses internally a structure similar to this (see the QualType definition).

WDYT? I think representing a struct field like:

struct foo {
    const struct bar* const bar_field;
};

As:

QualifiedType(ItemId(1), const)

where:

ItemId(1): TypeKind::Pointer(QualifiedType(ItemId(2), const))
ItemId(2): TypeKind::Comp(..)

Is more appealing than using the already arguably somewhat bloated Type.

fitzgen · 2017-02-23T01:29:14Z

Ok, yeah that sounds well-motivated.

fitzgen · 2017-03-06T18:16:56Z

@samliu any progress? any questions I can help answer? :)

samliu · 2017-03-06T18:20:09Z

Sorry no progress :( haven't had time to get to this, out of town past two weekends. What is a good timeline for addressing issues? I definitely want to do this but probably need to prioritize better.

…

On Mon, Mar 6, 2017 at 10:16 AM, Nick Fitzgerald ***@***.***> wrote: @samliu <https://github.com/samliu> any progress? any questions I can help answer? :) — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub <#534 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AAIS_djT-OVgvS41bTkY8CI5T7FBge_Pks5rjE2ZgaJpZM4MHk79> .

fitzgen · 2017-03-06T18:51:16Z

No worries!

There's no rush with this, so as long as you still plan on tackling it, we can keep it assigned. If for whatever reason you don't want to or can't work on this anymore, then we can unassign and let someone else grab it.

samliu · 2017-03-06T18:56:36Z

Thanks Nick. I'll do my best to make progress in a timely fashion nonetheless, or give it up if I can't commit to that anymore.

…

On Mar 6, 2017 10:51 AM, "Nick Fitzgerald" ***@***.***> wrote: No worries! There's no rush with this, so as long as you still plan on tackling it, we can keep it assigned. If for whatever reason you don't want to or can't work on this anymore, then we can unassign and let someone else grab it. — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub <#534 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AAIS_Q_coMCsHuok11vPmaI_jQO4kj6Pks5rjFWlgaJpZM4MHk79> .

RReverser · 2017-07-27T17:15:46Z

Was just about to report this (more precisely, #511), but looks like a known issue. Is there anything I could help with?

fitzgen · 2017-07-27T17:26:35Z

@RReverser if you wanted to pick this up, I think that's fine, given that there's been silence for a while.

@samliu you're not still planning on doing this, are you?

samliu · 2017-07-27T17:38:03Z

Sorry yeah I won't be able to get to this :( feel free to reassign

…

On Jul 27, 2017 10:26 AM, "Nick Fitzgerald" ***@***.***> wrote: @RReverser <https://github.com/rreverser> if you wanted to pick this up, I think that's fine, given that there's been silence for a while. @samliu <https://github.com/samliu> you're not still planning on doing this, are you? — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub <#534 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AAIS_efYnSN0QZ9Z9FD9HDpZEPnx2W_1ks5sSMhMgaJpZM4MHk79> .

fitzgen added the E-less-easy label Feb 21, 2017

fitzgen mentioned this issue Feb 21, 2017

Looking for something to work on? servo/servo#15162

Closed

fitzgen added the C-assigned label Feb 21, 2017

emilio mentioned this issue Feb 27, 2017

pointer constness is applied to pointee #511

Closed

fitzgen removed the C-assigned label Jul 27, 2017

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Add a phase that removes ResolvedTypeRefs before codegen #534

Add a phase that removes ResolvedTypeRefs before codegen #534

fitzgen commented Feb 21, 2017

fitzgen commented Feb 21, 2017

samliu commented Feb 21, 2017

fitzgen commented Feb 21, 2017

fitzgen commented Feb 21, 2017

emilio commented Feb 22, 2017

fitzgen commented Feb 22, 2017

samliu commented Feb 22, 2017 via email

emilio commented Feb 23, 2017

fitzgen commented Feb 23, 2017

fitzgen commented Feb 23, 2017

emilio commented Feb 23, 2017

emilio commented Feb 23, 2017

fitzgen commented Feb 23, 2017

fitzgen commented Feb 23, 2017

emilio commented Feb 23, 2017

fitzgen commented Feb 23, 2017

fitzgen commented Mar 6, 2017

samliu commented Mar 6, 2017 via email

fitzgen commented Mar 6, 2017

samliu commented Mar 6, 2017 via email

RReverser commented Jul 27, 2017 •

edited

Loading

fitzgen commented Jul 27, 2017

samliu commented Jul 27, 2017 via email

Add a phase that removes ResolvedTypeRefs before codegen #534

Add a phase that removes ResolvedTypeRefs before codegen #534

Comments

fitzgen commented Feb 21, 2017

fitzgen commented Feb 21, 2017

samliu commented Feb 21, 2017

fitzgen commented Feb 21, 2017

fitzgen commented Feb 21, 2017

emilio commented Feb 22, 2017

fitzgen commented Feb 22, 2017

samliu commented Feb 22, 2017 via email

emilio commented Feb 23, 2017

fitzgen commented Feb 23, 2017

fitzgen commented Feb 23, 2017

emilio commented Feb 23, 2017

emilio commented Feb 23, 2017

fitzgen commented Feb 23, 2017

fitzgen commented Feb 23, 2017

emilio commented Feb 23, 2017

fitzgen commented Feb 23, 2017

fitzgen commented Mar 6, 2017

samliu commented Mar 6, 2017 via email

fitzgen commented Mar 6, 2017

samliu commented Mar 6, 2017 via email

RReverser commented Jul 27, 2017 • edited Loading

fitzgen commented Jul 27, 2017

samliu commented Jul 27, 2017 via email

RReverser commented Jul 27, 2017 •

edited

Loading