1
//*************************************************************************
2
// DESCRIPTION: Verilator: Add temporaries, such as for unroll nodes
4
// Code available from: http://www.veripool.org/verilator
6
// AUTHORS: Wilson Snyder with Paul Wasson, Duane Gabli
8
//*************************************************************************
10
// Copyright 2003-2010 by Wilson Snyder. This program is free software; you can
11
// redistribute it and/or modify it under the terms of either the GNU
12
// Lesser General Public License Version 3 or the Perl Artistic License
15
// Verilator is distributed in the hope that it will be useful,
16
// but WITHOUT ANY WARRANTY; without even the implied warranty of
17
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
18
// GNU General Public License for more details.
20
//*************************************************************************
21
// V3Unroll's Transformations:
22
// Note is called twice. Once on modules for GenFor unrolling,
23
// Again after V3Scope for normal for loop unrolling.
26
// Look for "FOR" loops and unroll them if <= 32 loops.
27
// (Eventually, a better way would be to simulate the entire loop; ala V3Table.)
28
// Convert remaining FORs to WHILEs
30
//*************************************************************************
32
#include "config_build.h"
33
#include "verilatedos.h"
45
//######################################################################
46
// Unroll state, as a visitor of each AstNode
48
class UnrollVisitor : public AstNVisitor {
51
AstVar* m_forVarp; // Iterator variable
52
AstVarScope* m_forVscp; // Iterator variable scope (NULL for generate pass)
53
AstConst* m_varValuep; // Current value of loop
54
AstNode* m_ignoreIncp; // Increment node to ignore
55
bool m_varModeCheck; // Just checking RHS assignments
56
bool m_varModeReplace; // Replacing varrefs
57
bool m_varAssignHit; // Assign var hit
58
bool m_inBegin; // Inside a begin/end loop
59
bool m_generate; // Expand single generate For loop
60
V3Double0 m_statLoops; // Statistic tracking
61
V3Double0 m_statIters; // Statistic tracking
65
static int level = -1;
66
if (VL_UNLIKELY(level < 0)) level = v3Global.opt.debugSrcLevel(__FILE__);
71
bool cantUnroll(AstNode* nodep, const char* reason) {
73
nodep->v3error("Unsupported: Can't unroll generate for; "<<reason);
75
UINFO(3," Can't Unroll: "<<reason<<" :"<<nodep<<endl);
76
V3Stats::addStatSum(string("Unrolling gave up, ")+reason, 1);
81
return m_generate ? v3Global.opt.unrollCount()*16
82
: v3Global.opt.unrollCount();
85
bool forUnrollCheck(AstNode* nodep,
86
AstNode* initp, // Maybe under nodep (no nextp), or standalone (ignore nextp)
87
AstNode* precondsp, AstNode* condp,
88
AstNode* incp, // Maybe under nodep or in bodysp
90
// To keep the IF levels low, we return as each test fails.
91
UINFO(4, " FOR Check "<<nodep<<endl);
92
if (initp) UINFO(6, " Init "<<initp<<endl);
93
if (precondsp) UINFO(6, " Pcon "<<precondsp<<endl);
94
if (condp) UINFO(6, " Cond "<<condp<<endl);
95
if (incp) UINFO(6, " Inc "<<incp<<endl);
96
// Initial value check
97
AstAssign* initAssp = initp->castAssign();
98
if (!initAssp) return cantUnroll(nodep, "no initial assignment");
99
if (initp->nextp() && initp->nextp()!=nodep) nodep->v3fatalSrc("initial assignment shouldn't be a list");
100
if (!initAssp->lhsp()->castVarRef()) return cantUnroll(nodep, "no initial assignment to simple variable");
101
m_forVarp = initAssp->lhsp()->castVarRef()->varp();
102
m_forVscp = initAssp->lhsp()->castVarRef()->varScopep();
103
if (nodep->castGenFor() && !m_forVarp->isGenVar()) {
104
nodep->v3error("Non-genvar used in generate for: "<<m_forVarp->name()<<endl);
106
if (m_generate) V3Const::constifyParamsEdit(initAssp->rhsp()); // rhsp may change
107
AstConst* constInitp = initAssp->rhsp()->castConst();
108
if (!constInitp) return cantUnroll(nodep, "non-constant initializer");
111
if (condp->nextp()) nodep->v3fatalSrc("conditional shouldn't be a list");
113
// Assignment of next value check
114
AstAssign* incAssp = incp->castAssign();
115
if (!incAssp) return cantUnroll(nodep, "no increment assignment");
116
if (incAssp->nextp()) nodep->v3fatalSrc("increment shouldn't be a list");
117
AstNodeBiop* incInstrp = incAssp->rhsp()->castNodeBiop();
119
if (m_forVscp) { UINFO(8, " Loop Variable: "<<m_forVscp<<endl); }
120
else { UINFO(8, " Loop Variable: "<<m_forVarp<<endl); }
121
if (debug()>=9) nodep->dumpTree(cout,"- for: ");
123
// Extract the constant loop bounds
124
bool subtract = incInstrp->castSub();
126
if (!subtract && !incInstrp->castAdd()) return cantUnroll(nodep, "missing add/sub for incrementer");
127
AstVarRef* incVarrp = (subtract ? incInstrp->lhsp()->castVarRef()
128
: incInstrp->rhsp()->castVarRef());
129
if (!incVarrp) return cantUnroll(nodep, "missing variable in incrementer");
130
if (incVarrp->varp() != m_forVarp
131
|| incVarrp->varScopep() != m_forVscp) {
132
return cantUnroll(nodep, "different variables in incrementer");
136
// Adds have the # on the lhsp because V3Const pushes rhs consts over to the lhs
137
// Subtracts have it on the rhs, because you write i=i-1; i=1-i is non-sensible.
138
AstConst* preconstIncp = (subtract ? incInstrp->rhsp()->castConst()
139
: incInstrp->lhsp()->castConst());
140
if (m_generate) preconstIncp = V3Const::constifyParamsEdit(preconstIncp)->castConst();
141
AstConst* constIncp = (subtract ? incInstrp->rhsp()->castConst()
142
: incInstrp->lhsp()->castConst());
143
UINFO(8, " Inc expr ok: "<<constIncp<<endl);
144
if (!constIncp) return cantUnroll(nodep, "non-constant increment");
145
if (constIncp->isZero()) return cantUnroll(nodep, "zero increment"); // Or we could loop forever below...
147
bool lt = condp->castLt() || condp->castLtS();
148
bool lte = condp->castLte() || condp->castLteS();
149
bool gt = condp->castGt() || condp->castGtS();
150
bool gte = condp->castGte() || condp->castGteS();
151
if (!lt && !lte && !gt && !gte)
152
return cantUnroll(nodep, "condition not <= or <");
153
AstNodeBiop* condBip = condp->castNodeBiop();
154
if (!condBip->lhsp()->castVarRef())
155
return cantUnroll(nodep, "no variable on lhs of condition");
156
if (condBip->lhsp()->castVarRef()->varp() != m_forVarp
157
|| condBip->lhsp()->castVarRef()->varScopep() != m_forVscp)
158
return cantUnroll(nodep, "different variable in condition");
159
if (m_generate) V3Const::constifyParamsEdit(condBip->rhsp()); // rhsp may change
160
AstConst* constStopp = condBip->rhsp()->castConst();
161
if (!constStopp) return cantUnroll(nodep, "non-constant final value");
162
UINFO(8, " Stop expr ok: "<<constStopp<<endl);
164
if (constInitp->width()>32 || constInitp->num().isFourState()
165
|| constStopp->width()>32 || constStopp->num().isFourState()
166
|| constIncp->width()>32 || constIncp->num().isFourState())
167
return cantUnroll(nodep, "init/final/increment too large or four state");
168
vlsint32_t valInit = constInitp->num().toSInt();
169
vlsint32_t valStop = constStopp->num().toSInt();
170
if (lte) valStop++; if (gte) valStop--;
171
vlsint32_t valInc = constIncp->num().toSInt();
172
if (subtract) valInc = -valInc;
173
UINFO(8," In Numbers: for (v="<<valInit<<"; v<"<<valStop<<"; v=v+"<<valInc<<")\n");
176
UINFO(8, " ~Iters: "<<((valStop - valInit)/valInc)<<" c="<<unrollCount()<<endl);
177
if (((valStop - valInit)/valInc) > unrollCount())
178
return cantUnroll(nodep, "too many iterations");
180
// Less than 10 statements in the body?
182
for (AstNode* bodp = precondsp; bodp; bodp=bodp->nextp()) {
185
for (AstNode* bodp = bodysp; bodp; bodp=bodp->nextp()) {
188
for (AstNode* bodp = incp; bodp; bodp=bodp->nextp()) {
191
if (bodySize > v3Global.opt.unrollStmts())
192
return cantUnroll(nodep, "too many statements");
195
// Now, make sure there's no assignment to this variable in the loop
196
m_varModeCheck = true;
197
m_varAssignHit = false;
199
precondsp->iterateAndNext(*this);
200
bodysp->iterateAndNext(*this);
201
incp->iterateAndNext(*this);
202
m_varModeCheck = false;
204
if (m_varAssignHit) return cantUnroll(nodep, "genvar assigned *inside* loop");
206
// Finally, we can do it
207
forUnroller(nodep, initp, precondsp, condp, incp, bodysp,
209
condBip, constStopp->num(),
210
incInstrp, constIncp->num()); nodep = NULL;
215
void forUnroller(AstNode* nodep,
217
AstNode* precondsp, AstNode* condp,
218
AstNode* incp, AstNode* bodysp,
219
const V3Number& numInit,
220
AstNodeBiop* cmpInstrp, const V3Number& numStop,
221
AstNodeBiop* incInstrp, const V3Number& numInc) {
222
UINFO(4, " Unroll for var="<<numInit<<"; var<"<<numStop<<"; var+="<<numInc<<endl);
223
UINFO(6, " cmpI "<<cmpInstrp<<endl);
224
UINFO(6, " IncI "<<incInstrp<<endl);
225
AstNode* stmtsp = NULL;
227
initp->unlinkFrBack(); // Always a single statement; nextp() may be nodep
228
// Don't add to list, we do it once, and setting loop index isn't needed as we're constant propagating it
231
precondsp->unlinkFrBackWithNext();
232
stmtsp = stmtsp->addNextNull(precondsp);
235
bodysp->unlinkFrBackWithNext();
236
stmtsp = stmtsp->addNextNull(bodysp); // Maybe null if no body
238
if (incp && !nodep->castGenFor()) { // Generates don't need to increment loop index
239
incp->unlinkFrBackWithNext();
240
stmtsp = stmtsp->addNextNull(incp); // Maybe null if no body
242
// If it's a While, then incp is already part of bodysp.
243
V3Number loopValue(nodep->fileline(), m_forVarp->width()); // May differ in size from numInitp
244
loopValue.opAssign(numInit);
246
AstNode* newbodysp = NULL;
251
UINFO(8," Looping "<<loopValue<<endl);
252
// if loopValue<valStop
253
V3Number contin (nodep->fileline(), 1);
254
cmpInstrp->numberOperate(contin, loopValue, numStop);
255
if (contin.isEqZero()) {
256
break; // Done with the loop
258
// Replace iterator values with constant.
259
AstNode* oneloopp = stmtsp->cloneTree(true);
261
m_varValuep = new AstConst(nodep->fileline(), loopValue);
263
// Iteration requires a back, so put under temporary node
265
AstBegin* tempp = new AstBegin(oneloopp->fileline(),"[EditWrapper]",oneloopp);
266
m_varModeReplace = true;
267
tempp->stmtsp()->iterateAndNext(*this);
268
m_varModeReplace = false;
269
tempp->stmtsp()->unlinkFrBackWithNext(); tempp->deleteTree(); tempp=NULL;
272
if (newbodysp) newbodysp->addNext(oneloopp);
273
else newbodysp = oneloopp;
276
if (++times > unrollCount()*3) {
277
nodep->v3error("Loop unrolling took too long; probably this is an infinite loop, or set --unroll-count above "<<unrollCount());
281
//loopValue += valInc
282
V3Number newnum(nodep->fileline(), m_forVarp->width()); // Can't increment in-place
283
incInstrp->numberOperate(newnum, loopValue, numInc);
284
loopValue.opAssign(newnum);
286
pushDeletep(m_varValuep); m_varValuep=NULL;
291
if (newbodysp) nodep->replaceWith(newbodysp);
292
else nodep->unlinkFrBack();
293
if (bodysp) { pushDeletep(bodysp); bodysp=NULL; }
294
if (precondsp) { pushDeletep(precondsp); precondsp=NULL; }
295
if (initp) { pushDeletep(initp); initp=NULL; }
296
if (debug()>=9) newbodysp->dumpTree(cout,"- _new: ");
299
virtual void visit(AstWhile* nodep, AstNUser*) {
300
nodep->iterateChildren(*this);
301
if (m_varModeCheck || m_varModeReplace) {
303
// Constify before unroll call, as it may change what is underneath.
304
if (nodep->precondsp()) V3Const::constifyEdit(nodep->precondsp()); // precondsp may change
305
if (nodep->condp()) V3Const::constifyEdit(nodep->condp()); //condp may change
306
// Grab initial value
307
AstNode* initp = NULL; // Should be statement before the while.
308
if (nodep->backp()->nextp() == nodep) initp=nodep->backp();
309
if (initp) { V3Const::constifyEdit(initp); initp=NULL; }
310
if (nodep->backp()->nextp() == nodep) initp=nodep->backp();
312
AstNode* incp = NULL; // Should be last statement
313
if (nodep->incsp()) V3Const::constifyEdit(nodep->incsp());
314
if (nodep->incsp()) incp = nodep->incsp();
316
for (incp = nodep->bodysp(); incp && incp->nextp(); incp = incp->nextp()) {}
317
if (incp) { V3Const::constifyEdit(incp); incp=NULL; }
318
for (incp = nodep->bodysp(); incp && incp->nextp(); incp = incp->nextp()) {} // Again, as may have changed
321
if (forUnrollCheck(nodep, initp,
322
nodep->precondsp(), nodep->condp(),
323
incp, nodep->bodysp())) {
324
pushDeletep(nodep); nodep=NULL; // Did replacement
328
virtual void visit(AstGenFor* nodep, AstNUser*) {
329
if (!m_generate || m_varModeReplace) {
330
nodep->iterateChildren(*this);
331
} // else V3Param will recursively call each for loop to be unrolled for us
332
if (m_varModeCheck || m_varModeReplace) {
334
// Constify before unroll call, as it may change what is underneath.
335
if (nodep->initsp()) V3Const::constifyEdit(nodep->initsp()); // initsp may change
336
if (nodep->condp()) V3Const::constifyEdit(nodep->condp()); // condp may change
337
if (nodep->incsp()) V3Const::constifyEdit(nodep->incsp()); // incsp may change
338
if (nodep->condp()->isZero()) {
339
// We don't need to do any loops. Remove the GenFor,
340
// Genvar's don't care about any initial assignments.
342
// Note normal For's can't do exactly this deletion, as
343
// we'd need to initialize the variable to the initial
344
// condition, but they'll become while's which can be
345
// deleted by V3Const.
346
nodep->unlinkFrBack()->deleteTree(); nodep=NULL;
347
} else if (forUnrollCheck(nodep, nodep->initsp(),
348
NULL, nodep->condp(),
349
nodep->incsp(), nodep->bodysp())) {
350
pushDeletep(nodep); nodep=NULL; // Did replacement
352
nodep->v3error("For loop doesn't have genvar index, or is misformed");
356
virtual void visit(AstNodeFor* nodep, AstNUser*) {
357
if (m_generate) { // Ignore for's when expanding genfor's
358
nodep->iterateChildren(*this);
360
nodep->v3error("V3Begin should have removed standard FORs");
364
virtual void visit(AstBegin* nodep, AstNUser*) {
365
// Naming inside loop body; must have been a generate for.
366
// We need to only rename the 'upper' begin,
367
// anything lower will be renamed "uppernewname.lowerbegin"
368
bool lastBegin = m_inBegin;
370
nodep->iterateChildren(*this);
371
m_inBegin = lastBegin;
373
if (m_varModeReplace && !m_inBegin // no upper begin, excluding this one
375
// Rename it, as otherwise we may get a conflict
376
// V3Begin sees these DOTs and makes CellInlines for us.
377
string index = AstNode::encodeNumber(m_varValuep->toSInt());
378
string nname = (string)"genfor"+index+"__DOT__"+nodep->name();
379
// Verilog seems to drop the for loop name and tack on [#]
380
nname = nodep->name() + "__BRA__" + index + "__KET__";
381
//UINFO(8," Rename begin "<<nname<<" "<<nodep<<endl);
386
virtual void visit(AstVarRef* nodep, AstNUser*) {
388
&& nodep->varp() == m_forVarp
389
&& nodep->varScopep() == m_forVscp
390
&& nodep->lvalue()) {
391
UINFO(8," Itervar assigned to: "<<nodep<<endl);
392
m_varAssignHit = true;
395
&& nodep->varp() == m_forVarp
396
&& nodep->varScopep() == m_forVscp
398
&& !nodep->backp()->castAttrOf()) { // Most likely under a select
399
AstNode* newconstp = m_varValuep->cloneTree(false);
400
nodep->replaceWith(newconstp);
405
//--------------------
406
// Default: Just iterate
407
virtual void visit(AstNode* nodep, AstNUser*) {
408
if (m_varModeCheck && nodep == m_ignoreIncp) {
409
// Ignore subtree that is the increment
411
nodep->iterateChildren(*this);
417
UnrollVisitor(AstNode* nodep, bool generate) {
421
m_varModeCheck = false;
422
m_varModeReplace = false;
424
m_generate = generate;
426
nodep->accept(*this);
428
virtual ~UnrollVisitor() {
429
V3Stats::addStat("Optimizations, Unrolled Loops", m_statLoops);
430
V3Stats::addStat("Optimizations, Unrolled Iterations", m_statIters);
434
//######################################################################
435
// Unroll class functions
437
void V3Unroll::unrollAll(AstNetlist* nodep) {
438
UINFO(2,__FUNCTION__<<": "<<endl);
439
UnrollVisitor visitor (nodep, false);
442
void V3Unroll::unrollGen(AstNodeFor* nodep) {
443
UINFO(2,__FUNCTION__<<": "<<endl);
444
UnrollVisitor visitor (nodep, true);