Last Comment Bug 659729 - Add global value numbering to IonMonkey
: Add global value numbering to IonMonkey
Status: RESOLVED FIXED
:
Product: Core
Classification: Components
Component: JavaScript Engine (show other bugs)
: unspecified
: All All
: -- normal (vote)
: ---
Assigned To: Ryan Pearl [:rpearl]
:
: Jason Orendorff [:jorendorff]
Mentors:
Depends on: 666426 667601
Blocks: IonMonkey
  Show dependency treegraph
 
Reported: 2011-05-25 12:33 PDT by Ryan Pearl [:rpearl]
Modified: 2011-07-06 17:00 PDT (History)
11 users (show)
See Also:
Crash Signature:
(edit)
QA Whiteboard:
Iteration: ---
Points: ---
Has Regression Range: ---
Has STR: ---


Attachments
First pass on value numbering (6.26 KB, patch)
2011-06-02 16:24 PDT, Ryan Pearl [:rpearl]
dvander: feedback+
Details | Diff | Splinter Review
Another pass (15.61 KB, patch)
2011-06-28 18:42 PDT, Ryan Pearl [:rpearl]
dvander: feedback+
Details | Diff | Splinter Review
global value numbering (22.17 KB, patch)
2011-07-05 14:44 PDT, Ryan Pearl [:rpearl]
dvander: review+
Details | Diff | Splinter Review

Description Ryan Pearl [:rpearl] 2011-05-25 12:33:52 PDT
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] 2011-05-25 13:17:02 PDT
(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] 2011-06-02 16:24:47 PDT
Created attachment 537020 [details] [diff] [review]
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] 2011-06-02 23:07:28 PDT
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] 2011-06-28 18:42:29 PDT
Created attachment 542705 [details] [diff] [review]
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] 2011-07-05 11:41:36 PDT
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] 2011-07-05 14:44:38 PDT
Created attachment 544070 [details] [diff] [review]
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] 2011-07-05 17:26:14 PDT
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] 2011-07-06 15:28:49 PDT
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] 2011-07-06 17:00:46 PDT
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

Note You need to log in before you can comment on or make changes to this bug.