657816 - IonMonkey: Implement Linear Scan Register Allocation

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[Andrew Drake [:adrake]]

Tracking bug for adding register allocation to the soon-to-exist IonMonkey backend.

The current plan is to implement something similar to the strategy proposed in "Linear Scan Register Allocation on SSA Form" by Christian Wimmer and Michael Franz.

Comment 1

[Andrew Drake [:adrake]]

Attachment: Patch v0

This is the majority of a linear scan register allocator. Resolution and reification are missing, and there are some assorted performance or interface FIXMEs labeled and bug'd, but it should be good to go into the codebase. Currently the call is ifndef'd out, so the greedy allocator runs by default, but that should change to an environment variable, so I filed bug 668350 and added a code FIXME.

Comment 2

[Andrew Drake [:adrake]]

Attachment: Patch v1

Takes advantage of functionality in bug 667132 to avoid generating incorrect live intervals in loops.

Comment 3

[David Anderson [:dvander] - inactive, e-mail if emergency]

Comment on attachment 543403 [details] [diff] [review]
Patch v1

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

Getting initial nits out of the way before looking at the RegisterAllocator.*

::: js/src/Makefile.in
@@ +374,4 @@
>  		JSONSpewer.cpp \
>  		IonSpewer.cpp \
>  		LICM.cpp \
> +		RegisterAllocator.cpp \

Nit: Rename to LinearScan.cpp

::: js/src/ion/BitSet.h
@@ +118,5 @@
> +};
> +
> +class BitSet::Iterator
> +{
> +private:

Nit: two-space indent here

@@ +140,5 @@
> +    Iterator& operator++(int dummy) {
> +        JS_ASSERT(index_ <= set_.max_);
> +        do
> +            index_++;
> +        while (index_ <= set_.max_ && !set_.contains(index_));

Nit: Brace this loop

::: js/src/ion/InlineList.h
@@ +195,5 @@
>          iterator iter(where);
>          iter++;
>  
> +        remove(node);
> +        where.iter = NULL;

Why is this second line needed?

::: js/src/ion/IonAllocPolicy.h
@@ +108,5 @@
>      inline void *operator new(size_t nbytes) {
>          return GetIonContext()->temp->allocate(nbytes);
>      }
> +public:
> +    inline void *operator new(size_t nbytes, void *pos) {

What does this get used for?

::: js/src/ion/IonAnalysis.cpp
@@ +43,4 @@
>  #include "MIRGraph.h"
>  #include "Ion.h"
>  #include "IonAnalysis.h"
> +#include "BitSet.h"

Is BitSet.h needed here?

::: js/src/ion/IonLIR.cpp
@@ +58,5 @@
> +{
> +    if (phis_.length())
> +        return phis_[0]->id();
> +    else
> +        return instructions_.begin()->id();

Nit: Avoid return-after-else

@@ +66,5 @@
> +{
> +    if (instructions_.rbegin()->numDefs())
> +        return instructions_.rbegin()->getDef(instructions_.rbegin()->numDefs() - 1)->virtualRegister();
> +    else
> +        return instructions_.rbegin()->id();

Nit: Ditto

::: js/src/ion/IonLIR.h
@@ +205,5 @@
>          JS_ASSERT(isConstantValue());
>          return reinterpret_cast<const Value *>(bits_ & ~TAG_MASK);
>      }
> +
> +    static void PrintAllocation(FILE *fp, LAllocation *a);

does const LAllocation work here?

@@ +230,5 @@
>      enum Policy {
>          ANY,                // Register or stack slot.
>          REGISTER,           // Must have a register.
> +        FIXED,              // A specific register is required.
> +        RECORD              // ANY, but never move into register.

For some reason RECORD feels weird. Something about VCRs. How about:

      // Keep the used virtual register alive, and use whatever allocation is
      // available. This is similar to ANY but hints to the register allocator
      // that it is never useful to optimize this site.
      KEEPALIVE

@@ +725,5 @@
> +        return false;
> +    }
> +
> +    void next() {
> +        if (more()) {

Can this JS_ASSERT(more()) ?

::: js/src/ion/MIRGraph.h
@@ +50,1 @@
>  

Is BitSet.h needed here?

@@ +400,5 @@
> +             i != end();
> +             i++)
> +        {
> +            if (i->op() == MInstruction::Op_Snapshot)
> +                return i->toSnapshot();

Hrm, I'd rather we keep a pointer to the snapshot in the block itself than do this. Or, insert new instructions after the snapshot.

Comment 4

[Andrew Drake [:adrake]]

Any nits not responded to below have been fixed and incorporated for the next version of the patch.

> ::: js/src/ion/InlineList.h
> @@ +195,5 @@
> >          iterator iter(where);
> >          iter++;
> >  
> > +        remove(node);
> > +        where.iter = NULL;
> 
> Why is this second line needed?
> 

While not needed for correctness, it is unsafe to continue using the iterator being NULLed here following a remove. This was added to verify that this bad usage pattern was not occurring elsewhere after I tripped on it once and to prevent it from occurring again. I added a comment explaining why it ought to be here (I can put it in an #ifdef DEBUG if you want, but that seems excessive).

> ::: js/src/ion/IonAllocPolicy.h
> @@ +108,5 @@
> >      inline void *operator new(size_t nbytes) {
> >          return GetIonContext()->temp->allocate(nbytes);
> >      }
> > +public:
> > +    inline void *operator new(size_t nbytes, void *pos) {
> 
> What does this get used for?
> 

js::Vector uses placement new if you ever have a js::Vector<? extends TempObject> to initialize new elements of its arena.

> 
> @@ +400,5 @@
> > +             i != end();
> > +             i++)
> > +        {
> > +            if (i->op() == MInstruction::Op_Snapshot)
> > +                return i->toSnapshot();
> 
> Hrm, I'd rather we keep a pointer to the snapshot in the block itself than
> do this. Or, insert new instructions after the snapshot.

This one's a holdover I missed from when register allocation happened on MIR. I don't insert any new instructions into MIR at all anymore, so this can go back to the way it was.

Comment 5

[Andrew Drake [:adrake]]

Another note: the four followup patches fix some bugs present in this patch in ways that depend on prior patches, making it rather hard to migrate the fix up without just folding the patch in.

Comment 6

[David Anderson [:dvander] - inactive, e-mail if emergency]

Comment on attachment 543403 [details] [diff] [review]
Patch v1

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

Looks great. All my comments here are nits and calls for more comments. To avoid a horrible rebase feel free to do them on top of the other LSRA patches so we can get this in now.

::: js/src/ion/MIRGraph.h
@@ +315,5 @@
> +        return instructions_.begin();
> +    }
> +    MInstructionConstIterator end() const {
> +        return instructions_.end();
> +    }

Do you still need to iterate MIR in LSRA?

::: js/src/ion/RegisterAllocator.cpp
@@ +50,5 @@
> +LiveInterval *
> +LiveInterval::New(VirtualRegister *reg)
> +{
> +    LiveInterval *result = new LiveInterval(reg);
> +    return result;

This looks infallible - should callers just call new LiveInterval(reg)?

@@ +281,5 @@
> +const CodePosition CodePosition::MAX(UINT_MAX);
> +const CodePosition CodePosition::MIN(0);
> +
> +bool
> +RegisterAllocator::createDataStructures()

Reiterating, big functions like these deserve a big comment explaining what part of the algorithm they're doing, especially what the state of the algorithm is before and after.

@@ +287,5 @@
> +    allowedRegs = RegisterSet::All();
> +
> +    // Allocate free/next use data structures
> +    freeUntilPos = lir->mir()->allocate<CodePosition>(RegisterCodes::Total);
> +    nextUsePos = lir->mir()->allocate<CodePosition>(RegisterCodes::Total);

These are both fallible.

@@ +290,5 @@
> +    freeUntilPos = lir->mir()->allocate<CodePosition>(RegisterCodes::Total);
> +    nextUsePos = lir->mir()->allocate<CodePosition>(RegisterCodes::Total);
> +
> +    // Build virtual register objects
> +    vregs = new VirtualRegister[graph.numVirtualRegisters()];

This is definitely fallible.

@@ +298,5 @@
> +        for (LInstructionIterator ins = b->begin(); ins != b->end(); ins++) {
> +            if (ins->numDefs()) {
> +                for (size_t j = 0; j < ins->numDefs(); j++) {
> +                    uint32 reg = ins->getDef(j)->virtualRegister();
> +                    if (!vregs[reg].init(reg, b, *ins, ins->getDef(j)))

It might make things nicer to just make this function infallible - and ensure the ballast on every iteration. The vector isn't going to grow > 1, right?

@@ +327,5 @@
> +
> +bool
> +RegisterAllocator::buildLivenessInfo()
> +{
> +    BitSet **liveIn = new BitSet*[graph.numBlocks()];

This is never freed leaving the function. Is that intended?

@@ +332,5 @@
> +    if (!liveIn)
> +        return false;
> +
> +    for (size_t i = graph.numBlocks(); i > 0; i--) {
> +        LBlock *b = graph.getBlock(i - 1);

The canonical name for a block should just be "block" or "lir". I'm allergic to b's. I mean one letter variables.

@@ +333,5 @@
> +        return false;
> +
> +    for (size_t i = graph.numBlocks(); i > 0; i--) {
> +        LBlock *b = graph.getBlock(i - 1);
> +        MBasicBlock *mb = b->mir();

And "mblock" or "mir" here.

@@ +405,5 @@
> +        for (unsigned int i = 0; i < b->numPhis(); i++)
> +            live->remove(b->getPhi(i)->getDef(0)->virtualRegister());
> +
> +        // While not necessarily true, we make the simplifying assumption that
> +        // variables live at the loop header must be live for the entire loop.

Could you explain what this simplifies?

@@ +420,5 @@
> +    return true;
> +}
> +
> +bool
> +RegisterAllocator::allocateRegisters()

Somewhere we should cite Wimmer's papers.

@@ +443,5 @@
> +
> +        // Shift active intervals to the inactive or handled sets as appropriate
> +        for (IntervalIterator i(active.begin()); i != active.end(); ) {
> +            LiveInterval *it = *i;
> +            JS_ASSERT(it->getAllocation()->isGeneralReg());

Does this not support float registers yet?

@@ +450,5 @@
> +            if (it->end() < position) {
> +                // FIXME (668291): Free stack slots when interval ends
> +                i = active.removeAt(i);
> +                handled.insert(it);
> +            } else if (!it->covers(position)) {

Is handled ever observed in non-DEBUG code? If not, can you make something like an addToHandled() function that is debug-only?

@@ +477,5 @@
> +            }
> +        }
> +
> +#ifdef DEBUG
> +        // Sanity check all intervals in all sets

This big debug block should be a separate function.

@@ +522,5 @@
> +        if (position.ins() == current->reg()->ins()->id()) {
> +            JS_ASSERT(position.subpos() == CodePosition::OUTPUT);
> +
> +            LDefinition *def = current->reg()->def();
> +            LDefinition::Policy pol = current->reg()->def()->policy();

policy = def->policy() ?

@@ +535,5 @@
> +                LInstruction *ins = current->reg()->ins();
> +                JS_ASSERT(ins->numOperands() > 0);
> +                JS_ASSERT(ins->getOperand(0)->isUse());
> +                uint32 inputReg = ins->getOperand(0)->toUse()->virtualRegister();
> +                LiveInterval *inputInterval = vregs[inputReg].intervalFor(inputOf(ins));

Just a thought: wrapping vregs in a class that overloads [] might make this prettier.

@@ +566,5 @@
> +                }
> +            }
> +
> +            // Handle the fixed constraint if present
> +            if (fixedOp) {

What happens if there is more than one fixed constraint?

@@ +622,5 @@
> +        }
> +    }
> +
> +#ifdef DEBUG
> +    // Verify final intervals are valid

Separate this into its own function.

@@ +862,5 @@
> +{
> +    LAllocation *aa = a->getAllocation();
> +    LAllocation *ba = b->getAllocation();
> +    if (aa->isGeneralReg() && ba->isGeneralReg() &&
> +        aa->toGeneralReg()->reg() == ba->toGeneralReg()->reg())

What does "coexist" mean here? Why are only general regs supported?

::: js/src/ion/RegisterAllocator.h
@@ +54,5 @@
> +namespace ion {
> +
> +struct LOperand
> +{
> +public:

Nit: two-space indent

@@ +59,5 @@
> +    LUse *use;
> +    LInstruction *ins;
> +
> +    LOperand(LUse *use, LInstruction *ins) :
> +        use(use),

Nit: : goes on next line with a two-space indent (these two nits apply to the rest of the file)

@@ +67,5 @@
> +};
> +
> +class VirtualRegister;
> +
> +class CodePosition

Explanation about what a code position is.

@@ +82,5 @@
> +public:
> +    static const CodePosition MAX;
> +    static const CodePosition MIN;
> +
> +    enum SubPosition {

I know what this is from your IRL explanation, but given how scifi the name sounds, would be good to have a comment explaining the problem it's solving and how it's used :)

@@ +129,5 @@
> +    bool operator >=(const CodePosition &other) const {
> +        return bits_ >= other.bits_;
> +    }
> +
> +    CodePosition previous() const {

As long as we're being all operator overloady, any option on overloading -? ;)

@@ +135,5 @@
> +        return CodePosition(bits_ - 1);
> +    }
> +};
> +
> +class LiveInterval : public InlineListNode<LiveInterval>

Explanation about what a live interval is.

@@ +138,5 @@
> +
> +class LiveInterval : public InlineListNode<LiveInterval>
> +{
> +public:
> +    struct Range {

Explanation about what a range is.

@@ +190,5 @@
> +    VirtualRegister *reg() {
> +        return reg_;
> +    }
> +
> +    bool splitFrom(CodePosition pos, LiveInterval *after);

Non-trivial methods should have a comment explaining what they do (goes for the whole class).

@@ +256,5 @@
> +    }
> +
> +    bool addUse(LOperand operand) {
> +        return uses_.append(operand);
> +    }

Could you remove the newlines in between these functions? They're all pretty tiny.

@@ +280,5 @@
> +                IonAllocPolicy> LiveMap;
> +
> +typedef InlineList<LiveInterval>::iterator IntervalIterator;
> +
> +class RegisterAllocator

Rename to LinearScanAllocator or something.

Comment 7

[Andrew Drake [:adrake]]

This does currently only support general registers, I will file that. If there is more than one fixed constraint, an assertion is tripped earlier. I'm not sure what the best way to deal with that is, doing a JDK-style copy before fixed operands may be the easiest solution. I will file this as well.

Comment 8

[Andrew Drake [:adrake]]

Filed follow-up bug 670626, bug 670627, and bug 670628 for outstanding issues.

http://hg.mozilla.org/users/danderson_mozilla.com/ionmonkey/rev/eb2498df0895
http://hg.mozilla.org/users/danderson_mozilla.com/ionmonkey/rev/d6489ef29495