1 // -*- mode: C++; c-file-style: "cc-mode" -*-
2 //*************************************************************************
3 // DESCRIPTION: Verilator: Add temporaries, such as for premit nodes
4 //
5 // Code available from: https://verilator.org
6 //
7 //*************************************************************************
8 //
9 // Copyright 2003-2021 by Wilson Snyder. This program is free software; you
10 // can redistribute it and/or modify it under the terms of either the GNU
11 // Lesser General Public License Version 3 or the Perl Artistic License
12 // Version 2.0.
13 // SPDX-License-Identifier: LGPL-3.0-only OR Artistic-2.0
14 //
15 //*************************************************************************
16 // V3Premit's Transformations:
17 //
18 // Each module:
19 // For each wide OP, make a a temporary variable with the wide value
20 // For each deep expression, assign expression to temporary.
21 //
22 // Each display (independent transformation; here as Premit is a good point)
23 // If autoflush, insert a flush
24 //
25 //*************************************************************************
26
27 #include "config_build.h"
28 #include "verilatedos.h"
29
30 #include "V3Global.h"
31 #include "V3Premit.h"
32 #include "V3Ast.h"
33 #include "V3Stats.h"
34 #include "V3UniqueNames.h"
35
36 #include <algorithm>
37
38 constexpr int STATIC_CONST_MIN_WIDTH = 256; // Minimum size to extract to static constant
39
40 //######################################################################
41 // Structure for global state
42
43 class PremitAssignVisitor final : public AstNVisitor {
44 private:
45 // NODE STATE
46 // AstVar::user3() // bool; occurs on LHS of current assignment
47 const AstUser3InUse m_inuser3;
48
49 // STATE
50 bool m_noopt = false; // Disable optimization of variables in this block
51
52 // METHODS
53 VL_DEBUG_FUNC; // Declare debug()
54
55 // VISITORS
visit(AstNodeAssign * nodep)56 virtual void visit(AstNodeAssign* nodep) override {
57 // AstNode::user3ClearTree(); // Implied by AstUser3InUse
58 // LHS first as fewer varrefs
59 iterateAndNextNull(nodep->lhsp());
60 // Now find vars marked as lhs
61 iterateAndNextNull(nodep->rhsp());
62 }
visit(AstVarRef * nodep)63 virtual void visit(AstVarRef* nodep) override {
64 // it's LHS var is used so need a deep temporary
65 if (nodep->access().isWriteOrRW()) {
66 nodep->varp()->user3(true);
67 } else {
68 if (nodep->varp()->user3()) {
69 if (!m_noopt) UINFO(4, "Block has LHS+RHS var: " << nodep << endl);
70 m_noopt = true;
71 }
72 }
73 }
visit(AstNode * nodep)74 virtual void visit(AstNode* nodep) override { iterateChildren(nodep); }
75
76 public:
77 // CONSTRUCTORS
PremitAssignVisitor(AstNodeAssign * nodep)78 explicit PremitAssignVisitor(AstNodeAssign* nodep) {
79 UINFO(4, " PremitAssignVisitor on " << nodep << endl);
80 iterate(nodep);
81 }
82 virtual ~PremitAssignVisitor() override = default;
noOpt() const83 bool noOpt() const { return m_noopt; }
84 };
85
86 //######################################################################
87 // Premit state, as a visitor of each AstNode
88
89 class PremitVisitor final : public AstNVisitor {
90 private:
91 // NODE STATE
92 // AstNodeMath::user() -> bool. True if iterated already
93 // AstShiftL::user2() -> bool. True if converted to conditional
94 // AstShiftR::user2() -> bool. True if converted to conditional
95 // *::user3() -> See PremitAssignVisitor
96 const AstUser1InUse m_inuser1;
97 const AstUser2InUse m_inuser2;
98
99 // STATE
100 AstCFunc* m_cfuncp = nullptr; // Current block
101 AstNode* m_stmtp = nullptr; // Current statement
102 AstWhile* m_inWhilep = nullptr; // Inside while loop, special statement additions
103 AstTraceInc* m_inTracep = nullptr; // Inside while loop, special statement additions
104 bool m_assignLhs = false; // Inside assignment lhs, don't breakup extracts
105 V3UniqueNames m_tempNames; // For generating unique temporary variable names
106
107 VDouble0 m_extractedToConstPool; // Statistic tracking
108
109 // METHODS
110 VL_DEBUG_FUNC; // Declare debug()
111
assignNoTemp(AstNodeAssign * nodep)112 bool assignNoTemp(AstNodeAssign* nodep) {
113 return (VN_IS(nodep->lhsp(), VarRef) && !AstVar::scVarRecurse(nodep->lhsp())
114 && VN_IS(nodep->rhsp(), Const));
115 }
checkNode(AstNode * nodep)116 void checkNode(AstNode* nodep) {
117 // Consider adding a temp for this expression.
118 // We need to avoid adding temps to the following:
119 // ASSIGN(x, *here*)
120 // ASSIGN(CONST*here*, VARREF(!sc))
121 // ARRAYSEL(*here*, ...) (No wides can be in any argument but first,
122 // so we don't check which arg is wide)
123 // ASSIGN(x, SEL*HERE*(ARRAYSEL()...) (m_assignLhs==true handles this.)
124 // UINFO(9, " Check: " << nodep << endl);
125 // UINFO(9, " Detail stmtp=" << (m_stmtp?"Y":"N") << " U=" << (nodep->user1()?"Y":"N")
126 // << " IW=" << (nodep->isWide()?"Y":"N") << endl);
127 if (m_stmtp && !nodep->user1()) { // Not already done
128 if (nodep->isWide()) {
129 if (m_assignLhs) {
130 } else if (nodep->firstAbovep() && VN_IS(nodep->firstAbovep(), NodeAssign)
131 && assignNoTemp(VN_AS(nodep->firstAbovep(), NodeAssign))) {
132 // Not much point if it's just a direct assignment to a constant
133 } else if (VN_IS(nodep->backp(), Sel)
134 && VN_AS(nodep->backp(), Sel)->widthp() == nodep) {
135 // AstSel::width must remain a constant
136 } else if ((nodep->firstAbovep() && VN_IS(nodep->firstAbovep(), ArraySel))
137 || ((VN_IS(m_stmtp, CCall) || VN_IS(m_stmtp, CStmt))
138 && VN_IS(nodep, ArraySel))) {
139 // ArraySel's are pointer refs, ignore
140 } else {
141 UINFO(4, "Cre Temp: " << nodep << endl);
142 createDeepTemp(nodep, false);
143 }
144 }
145 }
146 }
147
insertBeforeStmt(AstNode * newp)148 void insertBeforeStmt(AstNode* newp) {
149 // Insert newp before m_stmtp
150 if (m_inWhilep) {
151 // Statements that are needed for the 'condition' in a while
152 // actually have to be put before & after the loop, since we
153 // can't do any statements in a while's (cond).
154 m_inWhilep->addPrecondsp(newp);
155 } else if (m_inTracep) {
156 m_inTracep->addPrecondsp(newp);
157 } else if (m_stmtp) {
158 AstNRelinker linker;
159 m_stmtp->unlinkFrBack(&linker);
160 newp->addNext(m_stmtp);
161 linker.relink(newp);
162 } else {
163 newp->v3fatalSrc("No statement insertion point.");
164 }
165 }
166
createDeepTemp(AstNode * nodep,bool noSubst)167 void createDeepTemp(AstNode* nodep, bool noSubst) {
168 if (nodep->user1SetOnce()) return; // Only add another assignment for this node
169
170 AstNRelinker relinker;
171 nodep->unlinkFrBack(&relinker);
172
173 FileLine* const fl = nodep->fileline();
174 AstVar* varp = nullptr;
175 AstConst* const constp = VN_CAST(nodep, Const);
176 const bool useConstPool = constp // Is a constant
177 && (constp->width() >= STATIC_CONST_MIN_WIDTH) // Large enough
178 && !constp->num().isFourState() // Not four state
179 && !constp->num().isString(); // Not a string
180 if (useConstPool) {
181 // Extract into constant pool.
182 const bool merge = v3Global.opt.mergeConstPool();
183 varp = v3Global.rootp()->constPoolp()->findConst(constp, merge)->varp();
184 nodep->deleteTree();
185 ++m_extractedToConstPool;
186 } else {
187 // Keep as local temporary. Name based on hash of node for output stability.
188 varp = new AstVar(fl, AstVarType::STMTTEMP, m_tempNames.get(nodep), nodep->dtypep());
189 m_cfuncp->addInitsp(varp);
190 // Put assignment before the referencing statement
191 insertBeforeStmt(new AstAssign(fl, new AstVarRef(fl, varp, VAccess::WRITE), nodep));
192 }
193
194 // Do not remove VarRefs to this in V3Const
195 if (noSubst) varp->noSubst(true);
196
197 // Replace node with VarRef to new Var
198 relinker.relink(new AstVarRef(fl, varp, VAccess::READ));
199 }
200
201 // VISITORS
visit(AstNodeModule * nodep)202 virtual void visit(AstNodeModule* nodep) override {
203 UINFO(4, " MOD " << nodep << endl);
204 iterateChildren(nodep);
205 }
visit(AstCFunc * nodep)206 virtual void visit(AstCFunc* nodep) override {
207 VL_RESTORER(m_cfuncp);
208 {
209 m_cfuncp = nodep;
210 m_tempNames.reset();
211 iterateChildren(nodep);
212 }
213 }
startStatement(AstNode * nodep)214 void startStatement(AstNode* nodep) {
215 m_assignLhs = false;
216 if (m_cfuncp) m_stmtp = nodep;
217 }
visit(AstWhile * nodep)218 virtual void visit(AstWhile* nodep) override {
219 UINFO(4, " WHILE " << nodep << endl);
220 startStatement(nodep);
221 iterateAndNextNull(nodep->precondsp());
222 startStatement(nodep);
223 m_inWhilep = nodep;
224 iterateAndNextNull(nodep->condp());
225 m_inWhilep = nullptr;
226 startStatement(nodep);
227 iterateAndNextNull(nodep->bodysp());
228 iterateAndNextNull(nodep->incsp());
229 m_stmtp = nullptr;
230 }
visit(AstNodeAssign * nodep)231 virtual void visit(AstNodeAssign* nodep) override {
232 startStatement(nodep);
233 {
234 const bool noopt = PremitAssignVisitor(nodep).noOpt();
235 if (noopt && !nodep->user1()) {
236 nodep->user1(true);
237 // Need to do this even if not wide, as e.g. a select may be on a wide operator
238 UINFO(4, "Deep temp for LHS/RHS\n");
239 createDeepTemp(nodep->rhsp(), false);
240 }
241 }
242 iterateAndNextNull(nodep->rhsp());
243 m_assignLhs = true;
244 iterateAndNextNull(nodep->lhsp());
245 m_assignLhs = false;
246 m_stmtp = nullptr;
247 }
visit(AstNodeStmt * nodep)248 virtual void visit(AstNodeStmt* nodep) override {
249 if (!nodep->isStatement()) {
250 iterateChildren(nodep);
251 return;
252 }
253 UINFO(4, " STMT " << nodep << endl);
254 startStatement(nodep);
255 iterateChildren(nodep);
256 m_stmtp = nullptr;
257 }
visit(AstTraceInc * nodep)258 virtual void visit(AstTraceInc* nodep) override {
259 startStatement(nodep);
260 m_inTracep = nodep;
261 iterateChildren(nodep);
262 m_inTracep = nullptr;
263 m_stmtp = nullptr;
264 }
visitShift(AstNodeBiop * nodep)265 void visitShift(AstNodeBiop* nodep) {
266 // Shifts of > 32/64 bits in C++ will wrap-around and generate non-0s
267 if (!nodep->user2SetOnce()) {
268 UINFO(4, " ShiftFix " << nodep << endl);
269 const AstConst* const shiftp = VN_CAST(nodep->rhsp(), Const);
270 if (shiftp && shiftp->num().mostSetBitP1() > 32) {
271 shiftp->v3error(
272 "Unsupported: Shifting of by over 32-bit number isn't supported."
273 << " (This isn't a shift of 32 bits, but a shift of 2^32, or 4 billion!)\n");
274 }
275 if (nodep->widthMin() <= 64 // Else we'll use large operators which work right
276 // C operator's width must be < maximum shift which is
277 // based on Verilog width
278 && nodep->width() < (1LL << nodep->rhsp()->widthMin())) {
279 AstNRelinker replaceHandle;
280 nodep->unlinkFrBack(&replaceHandle);
281 AstNode* constzerop;
282 const int m1value
283 = nodep->widthMin() - 1; // Constant of width-1; not changing dtype width
284 if (nodep->signedFlavor()) {
285 // Then over shifting gives the sign bit, not all zeros
286 // Note *NOT* clean output -- just like normal shift!
287 // Create equivalent of VL_SIGNONES_(node_width)
288 constzerop = new AstNegate(
289 nodep->fileline(),
290 new AstShiftR(nodep->fileline(), nodep->lhsp()->cloneTree(false),
291 new AstConst(nodep->fileline(), m1value), nodep->width()));
292 } else {
293 constzerop = new AstConst(nodep->fileline(), AstConst::WidthedValue(),
294 nodep->width(), 0);
295 }
296 constzerop->dtypeFrom(nodep); // unsigned
297
298 AstNode* const constwidthp
299 = new AstConst(nodep->fileline(), AstConst::WidthedValue(),
300 nodep->rhsp()->widthMin(), m1value);
301 constwidthp->dtypeFrom(nodep->rhsp()); // unsigned
302 AstCond* const newp = new AstCond(
303 nodep->fileline(),
304 new AstGte(nodep->fileline(), constwidthp, nodep->rhsp()->cloneTree(false)),
305 nodep, constzerop);
306 replaceHandle.relink(newp);
307 }
308 }
309 iterateChildren(nodep);
310 checkNode(nodep);
311 }
visit(AstShiftL * nodep)312 virtual void visit(AstShiftL* nodep) override { visitShift(nodep); }
visit(AstShiftR * nodep)313 virtual void visit(AstShiftR* nodep) override { visitShift(nodep); }
visit(AstShiftRS * nodep)314 virtual void visit(AstShiftRS* nodep) override { visitShift(nodep); }
315 // Operators
visit(AstNodeTermop * nodep)316 virtual void visit(AstNodeTermop* nodep) override {
317 iterateChildren(nodep);
318 checkNode(nodep);
319 }
visit(AstNodeUniop * nodep)320 virtual void visit(AstNodeUniop* nodep) override {
321 iterateChildren(nodep);
322 checkNode(nodep);
323 }
visit(AstNodeBiop * nodep)324 virtual void visit(AstNodeBiop* nodep) override {
325 iterateChildren(nodep);
326 checkNode(nodep);
327 }
visit(AstRand * nodep)328 virtual void visit(AstRand* nodep) override {
329 iterateChildren(nodep);
330 checkNode(nodep);
331 }
visit(AstUCFunc * nodep)332 virtual void visit(AstUCFunc* nodep) override {
333 iterateChildren(nodep);
334 checkNode(nodep);
335 }
visit(AstSel * nodep)336 virtual void visit(AstSel* nodep) override {
337 iterateAndNextNull(nodep->fromp());
338 { // Only the 'from' is part of the assignment LHS
339 VL_RESTORER(m_assignLhs);
340 m_assignLhs = false;
341 iterateAndNextNull(nodep->lsbp());
342 iterateAndNextNull(nodep->widthp());
343 }
344 checkNode(nodep);
345 }
visit(AstArraySel * nodep)346 virtual void visit(AstArraySel* nodep) override {
347 iterateAndNextNull(nodep->fromp());
348 { // Only the 'from' is part of the assignment LHS
349 VL_RESTORER(m_assignLhs);
350 m_assignLhs = false;
351 iterateAndNextNull(nodep->bitp());
352 }
353 checkNode(nodep);
354 }
visit(AstAssocSel * nodep)355 virtual void visit(AstAssocSel* nodep) override {
356 iterateAndNextNull(nodep->fromp());
357 { // Only the 'from' is part of the assignment LHS
358 VL_RESTORER(m_assignLhs);
359 m_assignLhs = false;
360 iterateAndNextNull(nodep->bitp());
361 }
362 checkNode(nodep);
363 }
visit(AstConst * nodep)364 virtual void visit(AstConst* nodep) override {
365 iterateChildren(nodep);
366 checkNode(nodep);
367 }
visit(AstNodeCond * nodep)368 virtual void visit(AstNodeCond* nodep) override {
369 iterateChildren(nodep);
370 if (nodep->expr1p()->isWide() && !VN_IS(nodep->condp(), Const)
371 && !VN_IS(nodep->condp(), VarRef)) {
372 // We're going to need the expression several times in the expanded code,
373 // so might as well make it a common expression
374 createDeepTemp(nodep->condp(), false);
375 }
376 checkNode(nodep);
377 }
378
379 // Autoflush
visit(AstDisplay * nodep)380 virtual void visit(AstDisplay* nodep) override {
381 startStatement(nodep);
382 iterateChildren(nodep);
383 m_stmtp = nullptr;
384 if (v3Global.opt.autoflush()) {
385 const AstNode* searchp = nodep->nextp();
386 while (searchp && VN_IS(searchp, Comment)) searchp = searchp->nextp();
387 if (searchp && VN_IS(searchp, Display)
388 && nodep->filep()->sameGateTree(VN_AS(searchp, Display)->filep())) {
389 // There's another display next; we can just wait to flush
390 } else {
391 UINFO(4, "Autoflush " << nodep << endl);
392 nodep->addNextHere(new AstFFlush(nodep->fileline(),
393 AstNode::cloneTreeNull(nodep->filep(), true)));
394 }
395 }
396 }
visit(AstSFormatF * nodep)397 virtual void visit(AstSFormatF* nodep) override {
398 iterateChildren(nodep);
399 // Any strings sent to a display must be var of string data type,
400 // to avoid passing a pointer to a temporary.
401 for (AstNode* expp = nodep->exprsp(); expp; expp = expp->nextp()) {
402 if (expp->dtypep()->basicp() && expp->dtypep()->basicp()->isString()
403 && !VN_IS(expp, VarRef)) {
404 createDeepTemp(expp, true);
405 }
406 }
407 }
408
409 //--------------------
410 // Default: Just iterate
visit(AstVar *)411 virtual void visit(AstVar*) override {} // Don't hit varrefs under vars
visit(AstNode * nodep)412 virtual void visit(AstNode* nodep) override { iterateChildren(nodep); }
413
414 public:
415 // CONSTRUCTORS
PremitVisitor(AstNetlist * nodep)416 explicit PremitVisitor(AstNetlist* nodep)
417 : m_tempNames{"__Vtemp"} {
418 iterate(nodep);
419 }
~PremitVisitor()420 virtual ~PremitVisitor() {
421 V3Stats::addStat("Optimizations, Prelim extracted value to ConstPool",
422 m_extractedToConstPool);
423 }
424 };
425
426 //----------------------------------------------------------------------
427 // Top loop
428
429 //######################################################################
430 // Premit class functions
431
premitAll(AstNetlist * nodep)432 void V3Premit::premitAll(AstNetlist* nodep) {
433 UINFO(2, __FUNCTION__ << ": " << endl);
434 { PremitVisitor{nodep}; } // Destruct before checking
435 V3Global::dumpCheckGlobalTree("premit", 0, v3Global.opt.dumpTreeLevel(__FILE__) >= 3);
436 }
437