Closed Bug 659729 Opened 13 years ago Closed 13 years ago

Add global value numbering to IonMonkey

Categories

(Core :: JavaScript Engine, defect)

defect
Not set
normal

Tracking

()

RESOLVED FIXED

People

(Reporter: rpearl, Assigned: rpearl)

References

(Blocks 1 open bug)

Details

Attachments

(1 file, 2 obsolete files)

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.
(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
Attached patch First pass on value numbering (obsolete) — Splinter Review
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).
Attachment #537020 - Flags: feedback?(dvander)
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.
  */
Attachment #537020 - Flags: feedback?(dvander) → feedback+
Depends on: 666426
Depends on: 667601
Attached patch Another pass (obsolete) — Splinter Review
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.
Attachment #537020 - Attachment is obsolete: true
Attachment #542705 - Flags: feedback?(dvander)
Comment on attachment 542705 [details] [diff] [review]
Another pass

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

Looks good, flag me for review whenever!
Attachment #542705 - Flags: feedback?(dvander) → feedback+
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.
Attachment #542705 - Attachment is obsolete: true
Attachment #544070 - Flags: review?(dvander)
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.
Attachment #544070 - Flags: review?(dvander) → review+
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
Status: NEW → RESOLVED
Closed: 13 years ago
Resolution: --- → FIXED
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
You need to log in before you can comment on or make changes to this bug.