1234921 - Optimize MIR Operands iterations

Status: REOPENED

(Core :: JavaScript Engine: JIT, defect, P5)

Description

[Nicolas B. Pierron [:nbp]]

In some phases of the compiler, we iterate over the operands and use getOperand for each operand of the MIR instruction.

When we iterate over the operands, we should use at most 2 virtual methods calls, one for the length, and one for the beginning of the operands vector, as they are stored linearly in memory.

Comment 1

[Nicolas B. Pierron [:nbp]]

Attachment: Add MOperandIterator to reduce the number of virtual method calls.

This patch only converts uses of numOperands and getOperand where the type
is not statically known.

Comment 2

[Dan Gohman [:sunfish]]

Comment on attachment 8701584 [details] [diff] [review]
Add MOperandIterator to reduce the number of virtual method calls.

Review of attachment 8701584 [details] [diff] [review]:
-----------------------------------------------------------------

I like where this is going :-). However, I wonder if it's feasible to go a step further and use C++11 range-based for loops. As a rough sketch:

 - Make an MOperandIterator class which just holds a single MUse*.
 - Make an MOperandRange class which holds two MOperandIterators and exposes them as begin() and end().
 - Add a method to MNode like "virtual MOperandRange operands() = 0;" and override in subclasses as needed.

Usage might look like this:

  for (MDefinition *op : node->operands()) {
    ...
  }

As a bonus, it'd avoid the 2 switches in the init function in the patch here, because one virtual call can do everything directly without additional dispatching. Many classes inherit from MAryInstruction and won't need their own implementation, so it shouldn't require a lot of duplicated code.

The one tricky part I can see at first glance is that code which in the current patch calls the index() function. Possibly this could be implemented as an indexOf function on the MOperandRange class, which would be similar to the indexOf function currently on MNode. Usage might look like:

  MOperandRange operands = node->operands();
  for (MDefinition *op : operands) {
    ...
    ... operands.indexOf(op) ...
    ...
  }

What do you think?

Comment 3

[Nicolas B. Pierron [:nbp]]

(In reply to Dan Gohman [:sunfish] from comment #2)
> What do you think?

I think this is an interesting idea.  Unfortunately I do not think we can safely have something like:

  for (MDefinition* op : operands)
    … operands.indexOf(op) …

because this implies that we cannot distinguish an operand by its definition.

I guess we can make something like

  for (MOperandDefinition op : operands)
    … op.index() …

where MOperandDefinition is a simple structure which holds an index into the operands vector, and a reference to the operands.

But then we add complexity for getting the definition out of it.  Thus, we might need to have a way to return the MDefinition* out of it.

  for (MOperandDefinition op : operands)
    … op.def()->block() … // def()  returns  operands[index].

or maybe we can overload the  operator()  instead, to make it shorter.

Comment 4

[Dan Gohman [:sunfish]]

> this implies that we cannot distinguish an operand by its definition.

I assumed that if we need to know the consumer of the operand inside the loop, we'd just remember where we got the operands from:

  for (MDefinition *op : node->operands()) {
    ...
    ... node ...
    ...
  }

Does this address your concern?

Alternatively, we could make an interface that returns the MUses themselves, like this:

  for (MUse *use : node->operandUses()) {
    ...
    ... use->producer() ...
    ... use->consumer() ...
    ...
  }

This looks to me like it'd be less convenient in the common case though.

Comment 5

[Jan de Mooij [:jandem]]

(In reply to Dan Gohman [:sunfish] from comment #4)
> > this implies that we cannot distinguish an operand by its definition.
> 
> I assumed that if we need to know the consumer of the operand inside the
> loop, we'd just remember where we got the operands from:

I think the concern was that an instruction can have multiple operands pointing at the same MDefinition, for instance MAdd(x, x), so operands.indexOf(def) will always return the first one :)

Comment 6

[Dan Gohman [:sunfish]]

(In reply to Jan de Mooij [:jandem] from comment #5)
> I think the concern was that an instruction can have multiple operands
> pointing at the same MDefinition, for instance MAdd(x, x), so
> operands.indexOf(def) will always return the first one :)

Ah, you're right. In that case, what if we add both operands() and operandUses() as sketched out above, and use operandUses() when we need the index value? operands() could mostly be a thin wrapper around operandUses() to avoid duplicating code.

Comment 7

[Nicolas B. Pierron [:nbp]]

I think having operandsUses would work well for the indexes, I am just a bit worried that having "Use" in the name would be misleading, as we are expecting to iterate over the operands, and not the uses.

Maybe we should do something like:

  typedef MUse MOperand;

Then we would have something like

  MOperandRange operands(node->operands<MOperand>);
  for (MOperand* op : operands) {
    … op->producer() …
    … operands.indexOf(op) …
  }

and

  for (MDefinition *op : node->operands<MDefinition>()) {
    … op->block() …
  }

Comment 8

[Nicolas B. Pierron [:nbp]]

Thinking more about it, we should probably make something like:

  MOperandRange<MOperand> operands(node);
  for (MOperand* op : operands) {
    … op->producer() …
    … operands.indexOf(op) …
  }

and

  for (MDefinition *op : MOperandRange<MDefinition>(node)) {
    … op->block() …
  }

as the MOperandRange provides the begin() function from which the type is taken from.
The node function does not care about the return type, it will initialize the MOperandRange identically anyway.

  M*::initOperandRange(MOperandRangeData& data) {
    data.begin = …;
    data.length = …;
  }

Should we rename MOperandRange to MOperandsView / MOperandsArray ?

Comment 9

[Dan Gohman [:sunfish]]

The template syntax makes it look complicated, and there would only be two supported types. And I like "range" in the name because it's what C++11 likes to call these things.

I took your idea of an operator to return the MDefinition and some of the other discussion above and experimented a bit and came up with the following. One improvement over my earlier suggestions is that it keeps the MUse encapsulated. How does this look?

class MOperandRange;

class MOperand {
  MUse *use_;
  friend class MOperandRange;

public:
  explicit MOperand(MUse *use) : use_(use) {}

  operator MDefinition *() const { return use_->producer(); }
};

class MOperandIterator {
  MUse *current_;

public:
  explicit MOperandIterator(MUse *current) : current_(current) {}

  MOperand operator*() const { return MOperand(current); }
  MOperandIterator operator++() { ++current_; return *this; }
  bool operator==(MOperandIterator other) const {
    return current_ == other.current_;
  }
  // and so on
};

class MOperandRange {
  MUse *begin_;
  MUse *end_;

public:
  MOperandRange(MUse *begin, MUse *end) : begin_(begin), end_(end) {
    MOZ_ASSERT(begin <= end);
  }

  MOperandIterator begin() const { return MOperandIterator(begin_); }
  MOperandIterator end() const { return MOperandIterator(end_); }

  size_t indexOf(MOperand op) {
    MOZ_ASSERT(begin_ <= op.use_ && op.use_ < end_);
    return op.use_ - begin_;
  }
};

class MNode {
  // ...
  virtual MOperandRange operands() const = 0;
  // ...
};

Comment 10

[Nicolas B. Pierron [:nbp]]

I was a little concerned by the extra pair of parenthesis in the following patterns  (*op)->block()  and  (**it)->block  , but at the end I think I like it because we do dereference a pointer to access the producer of the operand.

I will update my current patch and change it that way.

Comment 11

[Dan Gohman [:sunfish]]

With the implicit conversion from MOperand to MDefinition *, I'm hoping we could write code like this:

  // Common case where indexOf isn't needed:
  for (MDefinition *op : node->operands()) {
    op->block();
  }

  // Case where indexOf is needed:
  MOperandRange operands = node->operands();
  for (MOperand op : operands) {
    MDefinition *opDef = op;
    opDef->block();
    operands.indexOf(op);
  }

Does this work?

Comment 12

[Dan Gohman [:sunfish]]

Attachment: moperandrange.patch

Attached is a patch which changes the same places, using the MOperandRange + MOperand technique sketched out above. What do you think of this interface?

Comment 13

[Nicolas B. Pierron [:nbp]]

Comment on attachment 8710215 [details] [diff] [review]
moperandrange.patch

Review of attachment 8710215 [details] [diff] [review]:
-----------------------------------------------------------------

Sweet!
Thanks for taking over this patch.

Comment 14

[Dan Gohman [:sunfish]]

Attachment: moperandrange.patch

Submitting an updated patch; this fleshes out MOperandIterator a little more, and adds comments.

I'm requesting another r? because the patch introduces a significant new way to access MIR node operands, so I want to make sure people like it. Jan, the main changes here are in MIR.h; see especially the comment above the MOperandRange class. The rest of the patch contains examples of how it's used.

Comment 15

[Dan Gohman [:sunfish]]

Attachment: more-moperandrange.patch

This patch converts even more for loops to range-based for loops.

Comment 16

[Nicolas B. Pierron [:nbp]]

Comment on attachment 8711229 [details] [diff] [review]
more-moperandrange.patch

Review of attachment 8711229 [details] [diff] [review]:
-----------------------------------------------------------------

::: js/src/jit/MIR.cpp
@@ +229,5 @@
>  HashNumber
>  MDefinition::valueHash() const
>  {
>      HashNumber out = op();
> +    for (MDefinition* op : const_cast<MDefinition*>(this)->operands())

Could we add const variant of these operands functions, insated of having const_cast?

Comment 17

[Jan de Mooij [:jandem]]

Comment on attachment 8711228 [details] [diff] [review]
moperandrange.patch

Review of attachment 8711228 [details] [diff] [review]:
-----------------------------------------------------------------

Beautiful. Thanks!

::: js/src/jit/MIR.h
@@ +247,5 @@
> +    MUse* use_;
> +
> +    explicit MOperand(MUse* use) : use_(use) {}
> +
> +public:

Nit: indent with 2 spaces, also twice below.

@@ +250,5 @@
> +
> +public:
> +    // Replace this operand's producer.
> +    void replace(MDefinition* def) {
> +      use_->replaceProducer(def);

Nit: add 2 more spaces here and in the method below

::: js/src/jit/ValueNumbering.cpp
@@ +319,5 @@
>  bool
>  ValueNumberer::releaseOperands(MDefinition* def)
>  {
> +    for (MOperand it : def->operands()) {
> +        MDefinition *op = it;

Nit: MDefinition* op

Comment 18

[Nicolas B. Pierron [:nbp]]

Comment on attachment 8711229 [details] [diff] [review]
more-moperandrange.patch

Review of attachment 8711229 [details] [diff] [review]:
-----------------------------------------------------------------

(cancel review until comment  16 is answered, re-ask once answered)

Comment 19

[Dan Gohman [:sunfish]]

Attachment: moperand-constness.patch

Per request, here's a patch which templatizes MOperand, MOperandRange, and MOperandIterator to propagate constness, eliminating the need for const_cast in consumers.

There's still a const_cast in the implementation, but it's very well encapsulated, and avoids the need for duplicating the operands() implementations in numerous subclasses.

Comment 20

[Dan Gohman [:sunfish]]

Comment on attachment 8711229 [details] [diff] [review]
more-moperandrange.patch

Review of attachment 8711229 [details] [diff] [review]:
-----------------------------------------------------------------

Re-requesting review with another patch addressing the review feedback.

Comment 21

[Nicolas B. Pierron [:nbp]]

Comment on attachment 8714155 [details] [diff] [review]
moperand-constness.patch

Review of attachment 8714155 [details] [diff] [review]:
-----------------------------------------------------------------

::: js/src/jit/MIR.h
@@ +279,5 @@
>  
>  // Iterator over a MIR node's operands.
> +template <bool IsConst>
> +class MOperandIteratorTemplate {
> +    friend class MOperandIteratorTemplate<!IsConst>;

before this line, add:

    typedef MOperandTemplate<IsConst> MOperand;
    typedef MOperandIteratorTemplate<IsConst> MOperandIterator;
    // Relies on inlining to forbid const -> non-const coercion.
    typedef MOperandIteratorTemplate<!IsConst> OtherMOperandIterator;

and replace all references to IsConst below, such as a template like:

    template <bool OtherIsConst>
    bool operator==(MOperandIteratorTemplate<OtherIsConst> other) const {
        return current_ == other.current_;
    }

is changed to rely only on overloading:

    bool operator==(MOperandIterator other) const { return current_ == other.current_; }
    bool operator==(OtherMOperandIterator other) const { return current_ == other.current_; }

@@ +433,5 @@
>      virtual size_t numOperands() const = 0;
>      virtual size_t indexOf(const MUse* u) const = 0;
>      virtual MOperandRange operands() = 0;
> +    ConstMOperandRange operands() const {
> +      return const_cast<MNode*>(this)->operands();

From what I understand, most of the operands() method could be const, except for the MIR nodes which are embedding the memory of the MUse vector/array.

Would it make sense to do the opposite and thus move this const_cast only where it is necessary?

Comment 22

[Nicolas B. Pierron [:nbp]]

Comment on attachment 8711229 [details] [diff] [review]
more-moperandrange.patch

Review of attachment 8711229 [details] [diff] [review]:
-----------------------------------------------------------------

Sorry, I cannot r+ the current patch with the current const_cast, because if the next patch is backed out and not this one, we would still have a const_cast in the code base.

Comment 23

[BMO Automation]

Per policy at https://wiki.mozilla.org/Bug_Triage/Projects/Bug_Handling/Bug_Husbandry#Inactive_Bugs. If this bug is not an enhancement request or a bug not present in a supported release of Firefox, then it may be reopened.

Comment 24

[BugBot [:suhaib / :marco/ :calixte]]

The bug assignee is inactive on Bugzilla, so the assignee is being reset.