659729 - Add global value numbering to IonMonkey

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[Ryan Pearl [:rpearl]]

This is a tracking bug for adding GVN to IonMonkey.

The current plan is to implement the algorithm from "SCC-Based Value Numbering" by Cooper and Simpson as a first pass. A hash-based value algorithm may be implemented as well for the purposes of benchmarking.

Comment 1

[David Mandelin [:dmandelin]]

(In reply to comment #0)
> The current plan is to implement the algorithm from "SCC-Based Value
> Numbering" by Cooper and Simpson as a first pass.

The paper is available here:

http://llvm.cs.uiuc.edu/~vadve/CS526/public_html/Papers/sccvn.CRPC-TR95636-S.pdf

Comment 2

[Ryan Pearl [:rpearl]]

Attachment: First pass on value numbering

This is a first pass on value numbering. I'm looking for comments on structure and the algorithm and so on before I go further. This patch isn't meant to be pulled at the moment.

Things which can happen at the phase of the algorithm in the patch:
-We can do algebraic manipulations (canonicalize, cfold, etc) to find more congruencies
-We can make the computation sparse, not computing the expression congruency (valueHash() and congruentTo()) if we don't need to.

Once we have this numbering, we can do some redundancy eliminations (future patches).

Comment 3

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

Comment on attachment 537020 [details] [diff] [review]
First pass on value numbering

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

Great start! I think this is the right direction. Nothing big to say, mostly style nits.

Can you put this in your .hgrc, it makes diffs easier to read:

[defaults]
diff = -U 8 -p
qdiff = -U 8 -b

[diff]
git = 1
showfunc = true
unified = 8

::: js/src/ion/IonAnalysis.cpp
@@ +484,5 @@
> +                ValueHasher,
> +                IonAllocPolicy> ValueMap;
> +
> +static bool
> +computeValue(ValueMap &values, MInstruction *ins)

Static functions start with a capital letter in house style.

@@ +489,5 @@
> +{
> +    ValueMap::AddPtr p = values.lookupForAdd(ins);
> +
> +    if(!p)
> +        values.add(p, ins, ins->id());

HashTable::add can OOM so it's fallible, so you'll want some way to propagate an error up.

@@ +519,5 @@
> +    //
> +    // If the instruction in question's value number is not already
> +    // v, we break the congruence we have and set it to v. We repeat until
> +    // saturation. This will take at worst O(d) time, where d is the loop
> +    // connectedness of the SSA def/use graph.

Big comments explaining algorithms are great - thanks! You might want to cite the paper here.

@@ +535,5 @@
> +            MBasicBlock *block = graph.getBlock(i);
> +            // We want to process Phi instructions as well
> +            for(size_t i = 0; i < block->numPhis(); i++) {
> +                MInstruction *ins = block->getPhi(i);
> +                needsProcessing = needsProcessing || computeValue(values, ins);

Should that be | instead of ||?

::: js/src/ion/IonAnalysis.h
@@ +60,5 @@
>  RenumberInstructions(MIRGraph &graph);
>  
> +bool
> +CreateValueNumbering(MIRGraph &graph);
> +

Maybe just "ValueNumbering"

::: js/src/ion/MIR.cpp
@@ +77,1 @@
>  }

Should we make "id" and "valueNumber" the same thing, and get rid of one? Assuming the ordering property will hold.

@@ +79,5 @@
> +HashNumber
> +MInstruction::valueHash() const
> +{
> +    HashNumber out = op();
> +    for(size_t i = 0; i < numOperands(); i++) {

House style is that there should be a space between "for" and "(", similarly for all control keywords.

@@ +99,5 @@
> +    for(size_t i = 0; i < numOperands(); i++) {
> +        if(getInput(i)->valueNumber() != ins->getInput(i)->valueNumber())
> +            return false;
> +    }
> +

Not sure if you got to it yet, but MParameter will pass this test, though it probably shouldn't?

@@ +232,5 @@
> +HashNumber
> +MConstant::valueHash() const
> +{
> +    /* this loses some state... is there a better way to fold into 32 bits than
> +     * disgarding?

It's probably okay. I think I saw a 64-to-32 hash function here, though:

http://www.concentric.net/~ttwang/tech/inthash.htm

FWIW, we're trying to exclusively use C++-style comments in IonMonkey, though in the rest of the engine the C-style is /* blah */ or:

 /*
  * blah blah,
  * blah.
  */

Comment 4

[Ryan Pearl [:rpearl]]

Attachment: Another pass

This is another request-for-comments. I'm mostly to a point where I can land this, but I think I will pull out GVN into its own file and clean up a few things before I do that. 

In future patches and bugs we should do the following:
- Make the computation sparse: we need not recompute the value hash every time when it is known to not change.
- perform algebraic simplifications and constant folding as we traverse the tree for GVN to uncover more congruent definitions.
- Similarly, I think we can do unreachable code elimination in a natural way in the same pass as GVN.
- It should be pretty simple to configure a pessimistic single-pass numbering analysis using a variation of the same algorithm, and use that for a cheaper compilation on less hot functions.

Comment 5

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

Comment on attachment 542705 [details] [diff] [review]
Another pass

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

Looks good, flag me for review whenever!

Comment 6

[Ryan Pearl [:rpearl]]

Attachment: global value numbering

This is a reasonable pass at GVN which is suitable for landing in the tree. It's only a minor cleanup of the previous patch--some style nits I found were cleaned up (I'm sure review will pick up more), and I moved GVN into its own file; I had my own logging in a separate patch, and merged it in, using the spew channel mechanism we have now.

Once it lands I'll open up some follow up bugs for improvements.

Comment 7

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

Comment on attachment 544070 [details] [diff] [review]
global value numbering

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

Looks good, r=me with nits picked

::: js/src/Makefile.in
@@ +373,5 @@
>  		C1Spewer.cpp \
>  		JSONSpewer.cpp \
>  		IonSpewer.cpp \
>  		LICM.cpp \
> +		GVN.cpp \

Nit: ValueNumbering.h/cpp? I try to avoid acronyms for file names (LICM is harder, probably should be "CodeMotion" or something).

::: js/src/ion/GVN.cpp
@@ +99,5 @@
> +        changed = false;
> +        for (size_t i = 0; i < graph_.numBlocks(); i++) {
> +            MBasicBlock *block = graph_.getBlock(i);
> +
> +            MDefinitionIterator itr(block);

Nit: "iter" is our canonical name for an iterator variable.

@@ +128,5 @@
> +{
> +    InstructionMap::Ptr p = defs.lookup(ins->valueNumber());
> +    MInstruction *dom;
> +    if (!p || index > p->value->validUntil) {
> +        DominatingValue *value = new DominatingValue(ins, index + ins->block()->numDominated());

A quick comment about how the validUntil ... index + ins->block()->numDominated thing works would be good. The big comment mentions "current traversal index" but this isn't explained.

Also #1: Do we want to collect any sort of statistics on when |p && index > p->value->validUntil|? We're assuming it's rare, seems safe.
Also #2: it'd be nicer if we didn't need allocation here, but this isn't a strong objection. I assume this is so the hash function is simpler.

@@ +202,5 @@
> +                continue;
> +            }
> +
> +            IonSpew(IonSpew_GVN, "instruction %d is dominated by instruction %d (from block %d)",
> +                    ins->id(), ins->valueNumber(), dom->id(), dom->block()->id());

Is there one more argument than %d here?

::: js/src/ion/GVN.h
@@ +96,5 @@
> +  public:
> +    ValueNumberer(MIRGraph &graph);
> +    bool analyze();
> +
> +};

Nit: remove extra newline

@@ +99,5 @@
> +
> +};
> +
> +}
> +}

Nit: can you put // namespace blah after each }?

::: js/src/ion/IonAnalysis.h
@@ +67,5 @@
>  bool
>  BuildDominatorTree(MIRGraph &graph);
>  
> +bool
> +ComputeValueNumbering(MIRGraph &graph);

Should this be in GVN.h?

::: js/src/ion/MIR.cpp
@@ +64,5 @@
>  void
>  MInstruction::printName(FILE *fp)
>  {
>      PrintOpcodeName(fp, op());
> +    fprintf(fp, "%u-vn%u", id(), valueNumber());

Could you omit the -vn%u part if value numbering hasn't been performed yet?

@@ +291,5 @@
> +
> +bool
> +MParameter::congruentTo(MInstruction * const &ins) const
> +{
> +    if (!ins->isParameter()) return false;

Nit: Split into two lines.

Comment 8

[Ryan Pearl [:rpearl]]

With nits addressed (the DominatingValue being heap-allocated was cruft from old work; I've changed it to not allocate on the heap now):

http://hg.mozilla.org/users/danderson_mozilla.com/ionmonkey/file/938e06c2ee03

Comment 9

[Ryan Pearl [:rpearl]]

Follow up bugs:
Bug 669789 perform algebraic simplification and constant folding
Bug 669793 Make value numbering sparse
Bug 669795 separate functionality for a pessimistic GVN pass
Bug 669796 perform unreachable code elimination during GVN