664547 - IM: LICM (Loop Invariant Code Motion)

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[Andrew Scheff]

Attachment: Added LICM class and some support in MIR.h

I've added a LICM optimization pass to ionmonkey.  Currently it only flags instructions as loop invariant in a pretty naive way.  I would like to get some feedback on the design before actually moving code around or trying anything fancy.

Comment 1

[Andrew Scheff]

Attachment: Added LICM class and some support in MIR.h

Comment 2

[Andrew Scheff]

Attachment: Test case I've been using

Comment 3

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

Comment on attachment 539637 [details] [diff] [review]
Added LICM class and some support in MIR.h

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

Some style comments first --

::: js/src/Makefile.in
@@ +383,1 @@
>  		$(NULL)

Looks like this should be a hard tab indent.

::: js/src/ion/Ion.cpp
@@ +147,5 @@
>  
> +
> +    LICM licm(graph);
> +    licm.go();
> +

Need to check the return value here. Also, could you add a spew run after LICM? Bonus points if the spew could annotate whether an instruction was loop invariant.

::: js/src/ion/LICM.cpp
@@ +59,5 @@
> +
> +
> +bool
> +LICM::go()
> +{

Could you rename this to "analyze" for consistency with the other analysis passes?

@@ +61,5 @@
> +bool
> +LICM::go()
> +{
> +    printf("Beginning LICM pass...\n");
> +    

Do we need a general debug-spew mechanism for IonMonkey? I'd like to keep raw printfs (all of them - commented, uncommented, or #ifdef) out of the tree. methodjit/Logging.cpp would not be hard to replicate.

@@ +70,5 @@
> +    BlockQueue blockQueue;
> +    blockQueue.insert(blockQueue.begin(), block);
> +    
> +    BlockSet inQueueBlocks;
> +    inQueueBlocks.init();

init() is fallible.

@@ +73,5 @@
> +    BlockSet inQueueBlocks;
> +    inQueueBlocks.init();
> +    inQueueBlocks.put(block);
> +
> +    //BFS through CFG looking for backedges

Style nits: Space after //, comments should generally be complete sentences too, like:

// Perform a breadth-first search through the CFG to look for backedges.

@@ +78,5 @@
> +    while (!blockQueue.empty()) {
> +        block = blockQueue.popCopy();
> +        inQueueBlocks.remove(block);
> +
> +        block->mark(); //mark as visited

Comment should go above the line.

@@ +81,5 @@
> +
> +        block->mark(); //mark as visited
> +
> +        //get control instruction which contains pointers to successors
> +        control = block->lastIns();

There's a nicer API for this now, just block->numSuccessors(), block->getSuccessor().

@@ +94,5 @@
> +                inQueueBlocks.put(successor);
> +            }
> +            //if the successor has been visitedBlocks.. we have a backedge
> +            else if ( successor->isMarked() ) {
> +                //printf("Backedge from block %d back to block %d!!!\n", block->id(), successor->id());

For if-elseif statements, the house style is:

if (condition) {
    // Comment about this case...
} else if (condition) {
    // Comment about this case...
}

@@ +118,5 @@
> +Loop::Loop(MBasicBlock *from, MBasicBlock *to)
> +          : optimized_(false),
> +            header_(to),
> +            preLoop_(NULL)
> +{

two-space indent for :

@@ +142,5 @@
> +        //printf("Block %d determined to be in the loop\n", current->id());
> +
> +        //add any instructions to a list of instructions to process, mark all as in worklist
> +        for ( int i = 0; i < current->numPhis(); i ++ ) {
> +            ins = current->getPhi(i);

for (int i = 0; i < current->numPhis(); i++) {

Same spacing applies to the other for loops.

@@ +264,5 @@
> +
> +
> +bool
> +Loop::isControlInstruction(MInstruction *ins)
> +{

If this feels too hacky you could also add an isControlInstruction() virtual to MInstruction.

::: js/src/ion/LICM.h
@@ +68,5 @@
> +
> +  private:
> +
> +
> +

There seems to be a lot of random new lines, not sure if an editor messed up the line endings or something.

@@ +77,5 @@
> +
> +    public:
> +
> +        //a loop is constructed on a backedge found in the cfg
> +        Loop(MBasicBlock *from, MBasicBlock *to);

Two-space indents for "public", i.e.:

class Loop
{
  public:
    Loop(...

Comment 4

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

Comment on attachment 539637 [details] [diff] [review]
Added LICM class and some support in MIR.h

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

::: js/src/ion/LICM.cpp
@@ +85,5 @@
> +        control = block->lastIns();
> +
> +        //for each successor of this block
> +        for (int i = 0; i < control->numSuccessors(); i ++) {
> +            successor = control->getSuccessor(i);

I think you can get away with something much simpler, now that we have block reordering and loop-header bits: For each block in reverse-postorder, if that block is a loop header, get its last successor. Then you can get rid of most of the bookkeeping here.

@@ +127,5 @@
> +    //every basic block we encounter is inside this loop
> +    BlockQueue blockQueue;
> +    BlockSet loopBlocks;
> +    loopBlocks.init();
> +

This is fallible, so you probably want to separate this out of the ctor into a separate function, and call it from analyze().

@@ +141,5 @@
> +
> +        //printf("Block %d determined to be in the loop\n", current->id());
> +
> +        //add any instructions to a list of instructions to process, mark all as in worklist
> +        for ( int i = 0; i < current->numPhis(); i ++ ) {

There's now an MDefinitionIterator that could help you eliminate some redundancy here. At first I wasn't sure if phis could be loop invariant but Paul points out that something like:

   if (a)
      x = b;
   else
      x = c;

If a, b, and c are all loop invariant, then the phi is too, though this is harder to hoist.

@@ +160,5 @@
> +        //only push children on queue if we haven't reached the loop header yet
> +        if (current != to) {
> +            for ( int i = 0; i < current->numPredecessors(); i ++ ) {
> +                pred = current->getPredecessor(i);
> +

|pred| isn't used until here, so you can move the definition down for clarity.

@@ +164,5 @@
> +
> +                //if we haven't yet seen this predecessor in the loop, add it to the queue
> +                if (!loopBlocks.has(pred)) {
> +                    loopBlocks.put(pred);
> +                    blockQueue.insert(blockQueue.begin(), pred);

insert() is fallible, but if you wanted, you could probably convert the queue to a loop. You have the loop header, and the loop successor, and they're ordered such that all contained blocks N are: header->id() <= N <= successor->id(). And, |graph.getBlock(i)->id() == i|, so iterating over that range is easy.

Comment 5

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

Andrew points out that my last comment is wrong, our ordering doesn't guarantee the loop body is in between the header and successor, just that the header comes before the successor.

Comment 6

[David Mandelin [:dmandelin]]

(In reply to comment #3)
> Do we need a general debug-spew mechanism for IonMonkey? 

Yes. :-)

> I'd like to keep
> raw printfs (all of them - commented, uncommented, or #ifdef) out of the
> tree. methodjit/Logging.cpp would not be hard to replicate.

Comment 7

[David Mandelin [:dmandelin]]

Comment on attachment 539637 [details] [diff] [review]
Added LICM class and some support in MIR.h

You don't need my review for this, just David's.

Comment 8

[Andrew Scheff]

Attachment: Updated and improved LICM class / routine

I've addressed all of your comments in this version except for spewing.  There are still printfs in there but will be gone tomorrow.

Comment 9

[Andrew Scheff]

Attachment: Updated and improved LICM class / routine

I've addressed all of your comments except spewing. There are still printfs but there wont be tomorrow.

Comment 10

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

Comment on attachment 539958 [details] [diff] [review]
Updated and improved LICM class / routine

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

::: js/src/ion/LICM.cpp
@@ +63,5 @@
> +{
> +
> +    // Generate a post ordering of the blocks in the graph.
> +    BlockQueue RPOblocks;
> +    postOrder(graph.getBlock(0), &RPOblocks);

Blocks are already in RPO, so is this needed?

@@ +64,5 @@
> +
> +    // Generate a post ordering of the blocks in the graph.
> +    BlockQueue RPOblocks;
> +    postOrder(graph.getBlock(0), &RPOblocks);
> +    unmarkBlocks();

Let's make a contract on analysis steps that both before and after, all blocks and instructions are unmarked. So just remove this, and make sure that mark bits are cleared at the end.

@@ +72,5 @@
> +    MBasicBlock *header, *footer;
> +
> +    // In reverse post order, look for loops:
> +    while (!RPOblocks.empty()) {
> +        header = RPOblocks.popCopy();

Move the declaration of header to here.

@@ +76,5 @@
> +        header = RPOblocks.popCopy();
> +        if (header->isLoopHeader()) {
> +
> +            // The loop footer is the last predecessor of the loop header.
> +            footer = header->getPredecessor(header->numPredecessors() - 1);

Move the declaration of footer to here.

@@ +83,5 @@
> +            Loop loop(footer, header);
> +            if (!loop.init())
> +                return false;
> +           
> +            unmarkBlocks();

Move this call to the bottom of init() for clarity, since init "owns" the process of marking blocks.

@@ +141,5 @@
> +    BlockQueue blockQueue;
> +    MInstruction *ins;
> +    MBasicBlock *current;
> +
> +    if (!blockQueue.insert(blockQueue.begin(), footer_))

This can just be .append(footer_)

@@ +155,5 @@
> +        MDefinitionIterator definitions(current);
> +        while (definitions.more()) {
> +
> +            ins = *definitions;
> +            loopInstructions_.put(ins);

This is fallible, but I think you can get rid of it (comments in optimize).

@@ +166,5 @@
> +            definitions.next();
> +        }
> +
> +        // Stop once we reach loop header
> +        if (current != header_) {

Is it possible to invert this expression and early-break out of the loop? If so that seems more explicit (given the "stop" comment) and would let you unindent the logic below.

@@ +169,5 @@
> +        // Stop once we reach loop header
> +        if (current != header_) {
> +             MBasicBlock *pred;
> +             for (size_t i = 0; i < current->numPredecessors(); i++) {
> +                pred = current->getPredecessor(i);

Move the declaration of pred to here.

@@ +172,5 @@
> +             for (size_t i = 0; i < current->numPredecessors(); i++) {
> +                pred = current->getPredecessor(i);
> +
> +                // If we haven't already included this predecessor in the loop, add it to the queue.
> +                if (!pred->isMarked()) {

Similar, I'd invert this and put a continue.

@@ +175,5 @@
> +                // If we haven't already included this predecessor in the loop, add it to the queue.
> +                if (!pred->isMarked()) {
> +                    pred->mark();
> +
> +                    if(!blockQueue.insert(blockQueue.begin(), pred))

Since the queue is a vector, prepending in a loop is O(n^2). I'm not sure if this matters yet and it's definitely not worth fixing while prototyping, but worth mentioning.

@@ +209,5 @@
> +
> +            // If the operand is in the loop and not loop invariant itself...
> +            if (loopInstructions_.has(ins->getInput(i)) &&
> +                !ins->getInput(i)->isLoopInvariant()) {
> +    

You should never see a use inside the loop whose def comes after the loop body. So you should be able to remove the hash table and check |ins->getInput(i)->block()->id() < loopHeader->id()|, which will tell you if the instruction is defined before the loop header.

::: js/src/ion/LICM.h
@@ +51,5 @@
> +class MBasicBlock;
> +
> +
> +typedef HashSet<MBasicBlock*, DefaultHasher<MBasicBlock*>, IonAllocPolicy> BlockSet;
> +typedef HashSet<MInstruction*, DefaultHasher<MInstruction*>, IonAllocPolicy> InstructionSet;

InstructionSet and BlockSet aren't used anymore.

@@ +92,5 @@
> +    MBasicBlock *footer_;
> +
> +    InstructionSet loopInstructions_;
> +
> +    MBasicBlock* preLoop_; //this is where hoisted operations will go

Looks like this file missed the comment space changes.

Comment 11

[Andrew Scheff]

Attachment: Comments addressed

-Got rid of my double RPOing.  You're right the blocks are already in RPO

-Made unmarkBlocks a method of graph, I think that makes more sense and passes are responsible for calling it.

-Changed declarations as requested

-Inverted loop checks, changed to continues.  Is there a benefit here besides style?

-Removed loopInstructions hashset, replaced with your method of inloop checking using block IDs

-For all Vector operations (typedefed as BlockList and InstructionList) I plan on changing the code to use to js::Deque datastructure when it's ready, so I wont worry about changing inserts to appends.

-Again, ignore print statements, will be changed to spew

Comment 12

[David Mandelin [:dmandelin]]

Comment on attachment 540646 [details] [diff] [review]
Comments addressed

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

A few drive-by comments:

::: js/src/ion/LICM.cpp
@@ +90,5 @@
> +Loop::init() 
> +{
> +
> +    // Breadth-first search through predecessor pointers starting from loop footer.
> +    // When we reach the loop header, we've seen all blocks in the loop.

Why does it need to BFS? Can't we just use PO or something like that to find all the blocks in the loop?

Also: it would be nice to factor out a method "iterateLoopBlocks" or something like that: it would make the intent much clearer here.

@@ +150,5 @@
> +    InstructionQueue invariantInstructions;
> +    MUse *use;
> +    MInstruction* ins;
> +    bool invariant = false;
> +    bool needHoist = false;

These declarations should go down to their first use/initialization.

@@ +174,5 @@
> +
> +                invariant = false;
> +                break;
> +            }
> +        }

It'd probably be nice to factor out this loop: that way you wouldn't need the break and the 'invariant' variable.

::: js/src/ion/LICM.h
@@ +88,5 @@
> +  private:
> +
> +    bool optimized_;
> +    MBasicBlock *header_;
> +    MBasicBlock *footer_;

Please add detailed comments explaining what these blocks are and how exactly the define the loop.

@@ +89,5 @@
> +
> +    bool optimized_;
> +    MBasicBlock *header_;
> +    MBasicBlock *footer_;
> +    MIRGraph &graph;

This should probably be the first member declared.

@@ +91,5 @@
> +    MBasicBlock *header_;
> +    MBasicBlock *footer_;
> +    MIRGraph &graph;
> +
> +    MBasicBlock* preLoop_; // This is where hoisted operations will go.

Please add a detailed comment explaining where this is inserted in relation to the other parts of the loop.

Comment 13

[Andrew Scheff]

Attachment: Comments addressed

Addressed above comments except for this one:

---
@@ +174,5 @@
> +
> +                invariant = false;
> +                break;
> +            }
> +        }

It'd probably be nice to factor out this loop: that way you wouldn't need the break and the 'invariant' variable.
---

What do you mean by factor out this loop?  Don't I need to check all operands?  Or should I just not have a loop and check first operand, then check second operand...

Comment 14

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

Comment on attachment 541250 [details] [diff] [review]
Comments addressed

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

Looks great! Just a few remaining style nits. For spew, I've checked in bug 664882, so you can change the printfs to:

IonSpew(IonSpew_LICM, "blah blah...");

You can see the spew with:

IONFLAGS=licm path/to/js blah.js

::: js/src/ion/LICM.cpp
@@ +59,5 @@
> +    // In reverse post order, look for loops:
> +    for (size_t i = 0; i < graph.numBlocks(); i ++) {    
> +        MBasicBlock *header = graph.getBlock(i);
> +        if (header->isLoopHeader()) {
> +

Nit: No newline needed here. Same comment goes for control structures in iterateLoopBlocks().

::: js/src/ion/LICM.h
@@ +66,5 @@
> +  private:
> +
> +    void unmarkBlocks();
> +    void postOrder(MBasicBlock *block, BlockQueue *output);
> +};

Nit: So there's no confusion, spacing should look something like this:

class LICM
{
    MIRGraph &graph;

  public:
    LICM(MIRGraph &graph);
    bool analyze();

  private:
    ...
};

::: js/src/ion/MIRGraph.cpp
@@ +82,5 @@
> +        getBlock(i)->unmark();  
> +    }
> +}
> +
> +

Nit: extra space

Comment 15

[David Mandelin [:dmandelin]]

(In reply to comment #13)
> Created attachment 541250 [details] [diff] [review] [review]
> Comments addressed
> 
> Addressed above comments except for this one:
> 
> ---
> @@ +174,5 @@
> > +
> > +                invariant = false;
> > +                break;
> > +            }
> > +        }
> 
> It'd probably be nice to factor out this loop: that way you wouldn't need
> the break and the 'invariant' variable.
> ---
> 
> What do you mean by factor out this loop?  Don't I need to check all
> operands?  Or should I just not have a loop and check first operand, then
> check second operand...

I was speaking informally, sorry for the confusion. By "factor out this loop", I meant "extract this loop to a separate function": It seems to have a meaningful purpose in isolation, and I think it would reduce the amount of mutable state a bit to pull it out, which is always nice.

Comment 16

[Andrew Scheff]

Attachment: One more pass, everything addressed

Comment 17

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

Comment on attachment 541855 [details] [diff] [review]
One more pass, everything addressed

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

::: js/src/ion/IonSpewer.cpp
@@ +127,4 @@
>  
>      fprintf(stderr, "[%s] ", ChannelNames[channel]);
>      vfprintf(stderr, fmt, ap);
> +    //fprintf(stderr, "\n");

Just remove it entirely, and make sure to fix up callers to have \n

Comment 18

[Andrew Scheff]

Attachment: Added naive code hoisting

I've added a first attempt at code hoisting.

I have a few questions:
-What's the proper design pattern for flagging operations as always hoistable, never hoistable, or sometimes hoistable.  I don't think a big if .. or .. or .. is the way to go.

-Am I correct in saying that constant operations should never be hoisted unless that allows another op to be hoisted as well?  If so, I'll need to add a mechanism for checking that

Comment 19

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

Comment on attachment 542684 [details] [diff] [review]
Added naive code hoisting

removeEnd() strikes me as a little hacky :) what about using insertBefore() and giving the control instruction?

Comment 20

[Andrew Scheff]

Attachment: somewhat less naive code hoisting

Constant operations are only hoisted when they allow other operations to be hoisted as well.

Phi and control instructions are never hoisted

Comment 21

[David Mandelin [:dmandelin]]

(In reply to comment #20)
> Created attachment 543255 [details] [diff] [review] [review]
> somewhat less naive code hoisting

I forgot to mention this earlier: we usually try to follow a "one patch per bug" rule. So this bug should probably be morphed to "Identify loop invariant ops", and then a new bug added "hoist loop invariant ops" and a tracking bug for LICM that depends on those two.

Comment 22

[Ryan Pearl [:rpearl]]

We can use the results of GVN to perform value-driven code motion as well, which may subsume LICM, or at least augment the results.


This paper talks about the idea: http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.52.4572