1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265
|
// -*- mode: C++; c-file-style: "cc-mode" -*-
//*************************************************************************
// DESCRIPTION: Verilator: Recreate loops to help pack caches
//
// Code available from: http://www.veripool.org/verilator
//
//*************************************************************************
//
// Copyright 2003-2019 by Wilson Snyder. This program is free software; you can
// redistribute it and/or modify it under the terms of either the GNU
// Lesser General Public License Version 3 or the Perl Artistic License
// Version 2.0.
//
// Verilator is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
// GNU General Public License for more details.
//
//*************************************************************************
// V3Reloop's Transformations:
//
// Each CFunc:
// Look for a series of assignments that would look better in a loop:
//
// ASSIGN(ARRAYREF(var, #), ARRAYREF(var, #))
// ASSIGN(ARRAYREF(var, #+1), ARRAYREF(var, #+1))
// ->
// Create __Vilp local variable
// FOR(__Vilp = low; __Vilp <= high; ++__Vlip)
// ASSIGN(ARRAYREF(var, __Vilp), ARRAYREF(var, __Vilp))
//
// Likewise vector assign to the same constant converted to a loop.
//
//*************************************************************************
#include "config_build.h"
#include "verilatedos.h"
#include "V3Global.h"
#include "V3Reloop.h"
#include "V3Stats.h"
#include "V3Ast.h"
#include <algorithm>
#include <cstdarg>
#define RELOOP_MIN_ITERS 40 // Need at least this many loops to do this optimization
//######################################################################
class ReloopVisitor : public AstNVisitor {
private:
// TYPES
typedef std::vector<AstNodeAssign*> AssVec;
// NODE STATE
// AstCFunc::user1p -> Var* for temp var, 0=not set yet
AstUser1InUse m_inuser1;
// STATE
V3Double0 m_statReloops; // Statistic tracking
V3Double0 m_statReItems; // Statistic tracking
AstCFunc* m_cfuncp; // Current block
AssVec m_mgAssignps; // List of assignments merging
AstCFunc* m_mgCfuncp; // Parent C function
AstNode* m_mgNextp; // Next node
AstNodeSel* m_mgSelLp; // Parent select, NULL = idle
AstNodeSel* m_mgSelRp; // Parent select, NULL = constant
AstNodeVarRef* m_mgVarrefLp; // Parent varref
AstNodeVarRef* m_mgVarrefRp; // Parent varref, NULL = constant
AstConst* m_mgConstRp; // Parent RHS constant, NULL = sel
uint32_t m_mgIndexLo; // Merge range
uint32_t m_mgIndexHi; // Merge range
// METHODS
VL_DEBUG_FUNC; // Declare debug()
AstVar* findCreateVarTemp(FileLine* fl, AstCFunc* cfuncp) {
AstVar* varp = VN_CAST(cfuncp->user1p(), Var);
if (!varp) {
string newvarname = string("__Vilp");
varp = new AstVar(fl, AstVarType::STMTTEMP,
newvarname, VFlagLogicPacked(), 32);
if (!cfuncp) fl->v3fatalSrc("Assignment not under a function");
cfuncp->addInitsp(varp);
cfuncp->user1p(varp);
}
return varp;
}
void mergeEnd() {
if (!m_mgAssignps.empty()) {
uint32_t items = m_mgIndexHi - m_mgIndexLo + 1;
UINFO(9, "End merge iter="<<items<<" "<<m_mgIndexHi<<":"<<m_mgIndexLo
<<" "<<m_mgAssignps[0]<<endl);
if (items >= RELOOP_MIN_ITERS) {
UINFO(6, "Reloop merging items="<<items<<" "<<m_mgIndexHi<<":"<<m_mgIndexLo
<<" "<<m_mgAssignps[0]<<endl);
++m_statReloops;
m_statReItems += items;
// Transform first assign into for loop body
AstNodeAssign* bodyp = m_mgAssignps.front();
if (bodyp->lhsp() != m_mgSelLp) bodyp->v3fatalSrc("Corrupt queue/state");
FileLine* fl = bodyp->fileline();
AstVar* itp = findCreateVarTemp(fl, m_mgCfuncp);
AstNode* initp = new AstAssign(fl, new AstVarRef(fl, itp, true),
new AstConst(fl, m_mgIndexLo));
AstNode* condp = new AstLte(fl, new AstVarRef(fl, itp, false),
new AstConst(fl, m_mgIndexHi));
AstNode* incp = new AstAssign(fl, new AstVarRef(fl, itp, true),
new AstAdd(fl, new AstConst(fl, 1),
new AstVarRef(fl, itp, false)));
AstWhile* whilep = new AstWhile(fl, condp, NULL, incp);
initp->addNext(whilep);
bodyp->replaceWith(initp);
whilep->addBodysp(bodyp);
// Replace constant index with new loop index
AstNode* lbitp = m_mgSelLp->bitp();
lbitp->replaceWith(new AstVarRef(fl, itp, false));
lbitp->deleteTree(); VL_DANGLING(lbitp);
if (m_mgSelRp) { // else constant and no replace
AstNode* rbitp = m_mgSelRp->bitp();
rbitp->replaceWith(new AstVarRef(fl, itp, false));
rbitp->deleteTree(); VL_DANGLING(lbitp);
}
if (debug()>=9) initp->dumpTree(cout, "-new: ");
if (debug()>=9) whilep->dumpTree(cout, "-new: ");
// Remove remaining assigns
for (AssVec::iterator it=m_mgAssignps.begin(); it!=m_mgAssignps.end(); ++it) {
AstNodeAssign* assp = *it;
if (assp != bodyp) {
assp->unlinkFrBack()->deleteTree(); VL_DANGLING(assp);
}
}
}
// Setup for next merge
m_mgAssignps.clear();
m_mgSelLp = NULL;
m_mgSelRp = NULL;
m_mgVarrefLp = NULL;
m_mgVarrefRp = NULL;
m_mgConstRp = NULL;
}
}
// VISITORS
virtual void visit(AstCFunc* nodep) {
m_cfuncp = nodep;
iterateChildren(nodep);
m_cfuncp = NULL;
}
virtual void visit(AstNodeAssign* nodep) {
if (!m_cfuncp) return;
// Left select WordSel or ArraySel
AstNodeSel* lselp = VN_CAST(nodep->lhsp(), NodeSel);
if (!lselp) { mergeEnd(); return; } // Not ever merged
// Of a constant index
AstConst* lbitp = VN_CAST(lselp->bitp(), Const);
if (!lbitp) { mergeEnd(); return; }
uint32_t index = lbitp->toUInt();
// Of variable
AstNodeVarRef* lvarrefp = VN_CAST(lselp->fromp(), NodeVarRef);
if (!lvarrefp) { mergeEnd(); return; }
// RHS is a constant or a select
AstConst* rconstp = VN_CAST(nodep->rhsp(), Const);
AstNodeSel* rselp = VN_CAST(nodep->rhsp(), NodeSel);
AstNodeVarRef* rvarrefp = NULL;
if (rconstp) { // Ok
} else {
if (!rselp) { mergeEnd(); return; }
AstConst* rbitp = VN_CAST(rselp->bitp(), Const);
rvarrefp = VN_CAST(rselp->fromp(), NodeVarRef);
if (!rbitp || rbitp->toUInt() != index
|| !rvarrefp
|| lvarrefp->varp() == rvarrefp->varp()) {
mergeEnd(); return;
}
}
if (m_mgSelLp) { // Old merge
if (m_mgCfuncp == m_cfuncp
&& m_mgNextp == nodep
&& m_mgSelLp->same(lselp)
&& m_mgVarrefLp->same(lvarrefp)
&& (m_mgConstRp
? (rconstp && m_mgConstRp->same(rconstp))
: (rselp
&& m_mgSelRp->same(rselp)
&& m_mgVarrefRp->same(rvarrefp)))
&& (index == m_mgIndexLo-1
|| index == m_mgIndexHi+1)) {
// Sequentially next to last assign; continue merge
if (index == m_mgIndexLo-1) m_mgIndexLo = index;
else if (index == m_mgIndexHi+1) m_mgIndexHi = index;
UINFO(9, "Continue merge i="<<index
<<" "<<m_mgIndexHi<<":"<<m_mgIndexLo<<" "<<nodep<<endl);
m_mgAssignps.push_back(nodep);
m_mgNextp = nodep->nextp();
return;
}
else {
// This assign doesn't merge with previous assign,
// but should start a new merge
mergeEnd();
}
}
// Merge start
m_mgAssignps.push_back(nodep);
m_mgCfuncp = m_cfuncp;
m_mgNextp = nodep->nextp();
m_mgSelLp = lselp;
m_mgSelRp = rselp;
m_mgVarrefLp = lvarrefp;
m_mgVarrefRp = rvarrefp;
m_mgConstRp = rconstp;
m_mgIndexLo = index;
m_mgIndexHi = index;
UINFO(9, "Start merge i="<<index<<" "<<nodep<<endl);
}
//--------------------
// Default: Just iterate
virtual void visit(AstVar* nodep) {} // Speedup
virtual void visit(AstNodeMath* nodep) {} // Speedup
virtual void visit(AstNode* nodep) {
iterateChildren(nodep);
}
public:
// CONSTUCTORS
explicit ReloopVisitor(AstNetlist* nodep) {
m_cfuncp = NULL;
m_mgCfuncp = NULL;
m_mgNextp = NULL;
m_mgSelLp = NULL;
m_mgSelRp = NULL;
m_mgVarrefLp = NULL;
m_mgVarrefRp = NULL;
m_mgConstRp = NULL;
m_mgIndexLo = 0;
m_mgIndexHi = 0;
iterate(nodep);
}
virtual ~ReloopVisitor() {
V3Stats::addStat("Optimizations, Reloops", m_statReloops);
V3Stats::addStat("Optimizations, Reloop iterations", m_statReItems);
}
};
//######################################################################
// Reloop class functions
void V3Reloop::reloopAll(AstNetlist* nodep) {
UINFO(2,__FUNCTION__<<": "<<endl);
{
ReloopVisitor visitor(nodep);
} // Destruct before checking
V3Global::dumpCheckGlobalTree("reloop", 0, v3Global.opt.dumpTreeLevel(__FILE__) >= 6);
}
|