Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Improvements to UNOPTFLAT reporting #611

Closed
veripoolbot opened this issue Feb 3, 2013 · 10 comments
Closed

Improvements to UNOPTFLAT reporting #611

veripoolbot opened this issue Feb 3, 2013 · 10 comments

Comments

@veripoolbot
Copy link

@veripoolbot veripoolbot commented Feb 3, 2013


Author Name: Jeremy Bennett (@jeremybennett)
Original Redmine Issue: 611 from https://www.veripool.org
Original Date: 2013-02-03
Original Assignee: Jeremy Bennett (@jeremybennett)


I've done a lot of work over last year on large designs where UNOPTFLAT is a recurring problem. Almost always this is due to bit-loops within vectors that can be resolved by splitting the right vector within the loop. Eventually this is something I would like to automate.

In the meantime, I have added some modifications to Verilator, to increase the amount of reporting when this warning occurs. It adds a new flag, @--unoptflat-extra@. If this is specified, each time Verilator encounters UNOPTFLAT, in addition to its standard example loop it will produce:

  1. a list of the 10 widest vectors in the array;
  2. a list of the 10 most fanned-out vectors in the array; and
  3. a GraphViz DOT format graph of the entire loop (which may be large).

The vectors identified are strong candidates for splitting to break the loop. The graph may also be of help, although for big designs, it can be very large.

Please pull a patch for this from branch unoptflat at git@github.com:jeremybennett/verilator.git. This includes a number of additional tests which demostrate UNOPTFLAT in various guises, but which are primarily provided to help in future automation of UNOPTFLAT resolution.

@veripoolbot

This comment has been minimized.

Copy link
Author

@veripoolbot veripoolbot commented Feb 3, 2013


Original Redmine Comment
Author Name: Wilson Snyder (@wsnyder)
Original Date: 2013-02-03T19:01:28Z


Good improvements.



>%Warning-UNOPTFLAT:           v.x @ t/t_unoptflat_simple_2.v:24: width 3, fanout 12

I would like the fileline first so that it matches the Example path.  This
is so Emacs will recognize it as a filename and line number and it also
looks nicer if there's a lot of variables.  Perhaps:

%Warning-UNOPTFLAT:            t/t_unoptflat_simple_2.v:24:  v.x of width 3, fanout 12


>--- a/bin/verilator
>+    --unoptflat-extra           Extra diagnostics for UNOPTFLAT

I'd suggest unoptflat-report or unoptflat-graph instead as it's a bit more descriptive.

Actually if you think it's generally useful I'm ok with always printing the report and making the graph dump the optional part.

>+In addition produces a GraphViz DOT file of the entire strongly connected
>+components within the source associated with each loop. This is produced
>+irrespective of whether --dump-tree is set. Such graphs may help in analysing
>+the problem, but can be very large indeed.

Perhaps show an example dot command line?


>diff --git a/src/V3GraphAlg.cpp b/src/V3GraphAlg.cpp
>+    bool                   m_doall;	//!< Do all loops, not just the first

Complete nit, but m_doAll.


>--- a/src/V3Order.cpp
>+++ b/src/V3Order.cpp
>@@ -128,6 +128,43 @@ void OrderGraph::loopsVertexCb(V3GraphVertex* vertexp) {
>+//! Copy a vertex into a new graph for UNOPTFLAT diagnosis
>+
>+//! Does logic and vars. Also will need eventually to do:

Nit, here and elsewhere please put //! on the blank like above so that the
comment looks like it all goes together.


>+V3GraphVertex *OrderGraph::copyVertexCb(V3GraphVertex* vertexp) {
>+    if (OrderLogicVertex *lvp = dynamic_cast<OrderLogicVertex *>(vertexp)) {
>+	UnoptflatLogicVertex *newVertexp =
>+	    new UnoptflatLogicVertex (this, lvp);
>+	newVertexp->name (lvp->name());
>+	newVertexp->dotColor (lvp->dotColor());
>+	return newVertexp;
>+    } else if (OrderVarVertex *vvp = dynamic_cast<OrderVarVertex *>(vertexp)) {
>+	UnoptflatVarVertex *newVertexp =
>+	    new UnoptflatVarVertex (this, vvp);
>+	newVertexp->name (vvp->name());
>+	newVertexp->dotColor (vvp->dotColor());
>+	return newVertexp;
>+    } else {
>+	v3fatalSrc("No copy callback for this UNOPTFLAT vertex\n");
>+	return  NULL;
>+    }
>+}
>
>+//! Copy an edge into a new graph for UNOPTFLAT diagnosis
>+V3GraphEdge *OrderGraph::copyEdgeCb(V3GraphEdge *edgep, V3GraphVertex *fromp,
>+				    V3GraphVertex *top) {
>+    UnoptflatEdge *newEdgep =
>+	new UnoptflatEdge (this, fromp, top, edgep->weight(), edgep->cutable());
>+    newEdgep->name (edgep->name());
>+    newEdgep->dotColor (edgep->dotColor());
>+    return newEdgep;

Instead of these functions please make a virtual clone(graphp) function in
the V3Graph base classes and add overriding virtual clone functions
elsewhere (see how clone in AstNode works).  Then you can can call
vertexp->clone(newGraphp) or edgep->clone(newGraphp) to get whatever node
type you want.


>@@ -285,6 +342,7 @@ private:
> protected:
>     friend class OrderMoveDomScope;
>     V3List<OrderMoveDomScope*>  m_pomReadyDomScope;	// List of ready domain/scope pairs, by loopId
>+    vector<OrderVarStdVertex *>	m_unoptflatVars;	// Vector of variables in UNOPTFLAT loop
 
Nit, extra space before *.


>+++ b/test_regress/t/t_unoptflat_simple.v
>+//
>+// Use this file as a template for submitting bugs, etc.
>+// This module takes a single clock input, and should either
>+//	$write("*-* All Finished *-*\n");
>+//	$finish;
>+// on success, or $stop.
>+//
>+// The code as shown applies a random vector to the Test
>+// module, then calculates a CRC on the Test module's outputs.
>+//
>+// **If you do not wish for your code to be released to the public
>+// please note it here, otherwise:**
>+//

Nit, please remove the section of comments quoted above in new .v test files.


>\ No newline at end of file

Needs newline.


@veripoolbot

This comment has been minimized.

Copy link
Author

@veripoolbot veripoolbot commented Feb 8, 2013


Original Redmine Comment
Author Name: Jeremy Bennett (@jeremybennett)
Original Date: 2013-02-08T19:52:05Z


Thanks for all the comments. Here is what I have done:

The reports now match the layout of the Example: lines

The option is now --unoptflat-report. I've kept everything optional for now.

Corrected the nits.

Tidied up commenting of .v test files and renamed .pl files with _bad suffix, since they are intended to fail. I haven't renamed the .v files, since I hope in the future we may be able to automatically fix UNOPTFLAT.

I couldn't work out which file was missing a newline at the end of file.

The one change I have yet to make is adding the clone() function. I can see how to do this, but conventionally clone() takes no arguments. Which for a graph vertex or edge means it would create a copy of the vertex or edge in the same graph. Yet what I want is to create a copy of the vertex or edge in a different graph.

I think there are three options - please let me know which one you think best:

  1. Give clone() an argument of type V3Graph, so it knows the graph into which it should clone
  2. Call the function something else to avoid confusion - cloneOtherGraph() perhaps
  3. Leave the code as it is.

Let me know what you prefer. In the meantime I have updated branch unoptflat at git@github.com:jeremybennett/verilator.git.

@veripoolbot

This comment has been minimized.

Copy link
Author

@veripoolbot veripoolbot commented Feb 8, 2013


Original Redmine Comment
Author Name: Wilson Snyder (@wsnyder)
Original Date: 2013-02-08T22:46:58Z


It is fine and correct for clone() to have a V3Graph because that is what the normal constructor requires. Other clones such as in AstNode don't have parameters only because their constructors don't need information about their parent. If you can update that I'm otherwise happy and will merge.

@veripoolbot

This comment has been minimized.

Copy link
Author

@veripoolbot veripoolbot commented Feb 15, 2013


Original Redmine Comment
Author Name: Jeremy Bennett (@jeremybennett)
Original Date: 2013-02-15T15:05:35Z


Took a little longer to do than I thought, but now all in there. Regression tests all pass.

I'd appreciate your thoughts on my C++ for implementing the @clone()@ function. It can't be a true copy constructor, because there are some parts of the class we don't want to copy. I would have liked to have something like:

virtual V3GraphVertex *clone(V3Graph *graphp) const {
     V3GraphVertex *clonep = new V3GraphVertex(graphp);
     clonep->fanout(m_fanout);
     clonep->color(m_color);
     clonep->rank(m_rank);
     return clonep;
}

with a derived class then being

virtual OrderEitherVertex *clone(V3Graph *graphp) const {
     OrderEitherVertex *clonep = V3GraphVertex::clone(graphp);
     clonep->m_scopep = m_scopep;
     clonep->domainp(m_domainp);
     clonep->inLoop(m_inLoop);
     clonep->isFromInput(m_isFromInput);
     return clonep;
}

The trouble is the type returned by the base class @clone()@ is @V3GraphVertex *@, not @OrderEitherVertex *@. Unlike with a constructor, this explicit calling of a base class method, really doesn't work with functions that return the class as type. So my solution is to separate out into a virtual clone() function which calls the constructor and then calls a separate protected virtual @cloneContents()@ instruction to copy the data. A subclass then just needs to implement a @cloneContents()@ function that calls the base class @cloneContents()@ function, then copies the contents specific to this class. For example:

virtual void cloneContents(OrderEitherVertex *clonep) const {
     V3GraphVertex::cloneContents(clonep);
     clonep->m_scopep = m_scopep;
     clonep->domainp(m_domainp);
     clonep->inLoop(m_inLoop);
     clonep->isFromInput(m_isFromInput);
}

This achieves what is wanted, but I can't help feeling there is a cleaner way to do this.

Please pull the latest version from branch unoptflat at git@github.com:jeremybennett/verilator.git.

@veripoolbot

This comment has been minimized.

Copy link
Author

@veripoolbot veripoolbot commented Feb 15, 2013


Original Redmine Comment
Author Name: Wilson Snyder (@wsnyder)
Original Date: 2013-02-15T23:49:09Z


Maybe I'm not understanding the problem properly, but you should be using the constructor to pass the arguments and the return type can vary up the tree and the compiler will work it all out. See how V3OrderGraph.h does it. For example:

#include <stdio.h>
#include <stdarg.h>
#include <stdint.h>
struct Base {
     virtual Base* clone() { printf("Base::clone\n"); return new Base(); }
};
struct BaseA : Base {
     virtual BaseA* clone() { printf("BaseA::clone\n"); return new BaseA(); }
};
struct BaseAC : BaseA {
     virtual BaseA* clone() { printf("BaseAC::clone\n"); return new BaseAC(); }
};
struct BaseAD : BaseA {
     virtual BaseA* clone() { printf("BaseAD::clone\n"); return new BaseAD(); }
};
int main() {
     BaseAD* ad = new BaseAD();
     ad->clone();
     BaseA* a = ad;
     a->clone();  // Calls BaseAD::clone() - note that return type downcasts for us
}

Also minor nit, I prefer "Typename* foo" not "Typename * foo" or * then foo with no space. The former is more common in C++ the latter in C. The reason is the pointer is part of the type. Yes, the programmer does need to know though that "Typename* foo, bar" will not make bar a pointer, but that's bad form.

@veripoolbot

This comment has been minimized.

Copy link
Author

@veripoolbot veripoolbot commented Feb 23, 2013


Original Redmine Comment
Author Name: Wilson Snyder (@wsnyder)
Original Date: 2013-02-23T01:56:35Z


Is there another rev coming with the clone fixed?

@veripoolbot

This comment has been minimized.

Copy link
Author

@veripoolbot veripoolbot commented Feb 24, 2013


Original Redmine Comment
Author Name: Jeremy Bennett (@jeremybennett)
Original Date: 2013-02-24T13:58:33Z


Hi Wilson,

Sorry for the delay - urgent customer work has kept me away from this for over a week. The problem I was trying to get round was cloning parts of the class which are not set in a constructor. I'll add the necessary constructors, so I can use this approach (which will be simpler than adding a cloneContents method). I'll try to get to this later today.

Best wishes,

Jeremy

@veripoolbot

This comment has been minimized.

Copy link
Author

@veripoolbot veripoolbot commented Feb 25, 2013


Original Redmine Comment
Author Name: Jeremy Bennett (@jeremybennett)
Original Date: 2013-02-25T15:29:34Z


The revised code is pushed to GitHub. I've extended some constructors with optional arguments, which allows the hierarchy of constructors to be used. There is a minor wrinkle, in that some of the intermediate classes are abstract, and thus do not permit a clone function returning a concrete result. This is resolved by requiring the derived class(es) to do the necessary construction (or in one case the derived classes of the derived class).

I believe I have turned all @t v@ into @t v@, apologies if I missed any.

Please pull the updated code from branch unoptflat at git@github.com:jeremybennett/verilator.git.

@veripoolbot

This comment has been minimized.

Copy link
Author

@veripoolbot veripoolbot commented Feb 27, 2013


Original Redmine Comment
Author Name: Wilson Snyder (@wsnyder)
Original Date: 2013-02-27T03:29:11Z


Pushed to git towards 3.846.

I made some changes to the clone stuff so the base classes were cleaner, and decided to rename it to --report-unoptflat simply so if we add other reports all the options will be next to each other in the docs.

Thanks for the patches!

@veripoolbot

This comment has been minimized.

Copy link
Author

@veripoolbot veripoolbot commented Mar 9, 2013


Original Redmine Comment
Author Name: Wilson Snyder (@wsnyder)
Original Date: 2013-03-09T21:51:54Z


In 3.846.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
1 participant
You can’t perform that action at this time.