1 # based on ariane plru, from tlb.sv
3 # old PLRU API, once all users have migrated to new API in plru2.py, then
4 # plru2.py will be renamed to plru.py, replacing this file.
6 from nmigen
import Signal
, Module
, Cat
, Const
, Repl
, Array
7 from nmigen
.hdl
.ir
import Elaboratable
8 from nmigen
.cli
import rtlil
9 from nmigen
.utils
import log2_int
10 from nmigen
.lib
.coding
import Decoder
11 from warnings
import warn
14 class PLRU(Elaboratable
):
15 r
""" PLRU - Pseudo Least Recently Used Replacement
28 def __init__(self
, BITS
):
29 warn("nmutil.plru.PLRU is deprecated due to having a broken API, use "
30 "nmutil.plru2.PLRU instead", DeprecationWarning, stacklevel
=2)
32 self
.acc_i
= Signal(BITS
)
33 self
.acc_en
= Signal()
34 self
.lru_o
= Signal(BITS
)
36 self
._plru
_tree
= Signal(self
.TLBSZ
)
37 """ exposed only for testing """
41 return 2 * (self
.BITS
- 1)
43 def elaborate(self
, platform
=None):
46 # Tree (bit per entry)
48 # Just predefine which nodes will be set/cleared
49 # E.g. for a TLB with 8 entries, the for-loop is semantically
50 # equivalent to the following pseudo-code:
52 # acc_en[7]: plru_tree[0, 2, 6] = {1, 1, 1};
53 # acc_en[6]: plru_tree[0, 2, 6] = {1, 1, 0};
54 # acc_en[5]: plru_tree[0, 2, 5] = {1, 0, 1};
55 # acc_en[4]: plru_tree[0, 2, 5] = {1, 0, 0};
56 # acc_en[3]: plru_tree[0, 1, 4] = {0, 1, 1};
57 # acc_en[2]: plru_tree[0, 1, 4] = {0, 1, 0};
58 # acc_en[1]: plru_tree[0, 1, 3] = {0, 0, 1};
59 # acc_en[0]: plru_tree[0, 1, 3] = {0, 0, 0};
60 # default: begin /* No hit */ end
63 LOG_TLB
= log2_int(self
.BITS
, False)
64 hit
= Signal(self
.BITS
, reset_less
=True)
65 m
.d
.comb
+= hit
.eq(Repl(self
.acc_en
, self
.BITS
) & self
.acc_i
)
67 for i
in range(self
.BITS
):
68 # we got a hit so update the pointer as it was least recently used
70 # Set the nodes to the values we would expect
71 for lvl
in range(LOG_TLB
):
72 idx_base
= (1 << lvl
)-1
73 # lvl0 <=> MSB, lvl1 <=> MSB-1, ...
75 new_idx
= Const(~
((i
>> (shift
-1)) & 1), 1)
76 plru_idx
= idx_base
+ (i
>> shift
)
77 # print("plru", i, lvl, hex(idx_base),
78 # plru_idx, shift, new_idx)
79 m
.d
.sync
+= self
._plru
_tree
[plru_idx
].eq(new_idx
)
81 # Decode tree to write enable signals
82 # Next for-loop basically creates the following logic for e.g.
83 # an 8 entry TLB (note: pseudo-code obviously):
84 # replace_en[7] = &plru_tree[ 6, 2, 0]; #plru_tree[0,2,6]=={1,1,1}
85 # replace_en[6] = &plru_tree[~6, 2, 0]; #plru_tree[0,2,6]=={1,1,0}
86 # replace_en[5] = &plru_tree[ 5,~2, 0]; #plru_tree[0,2,5]=={1,0,1}
87 # replace_en[4] = &plru_tree[~5,~2, 0]; #plru_tree[0,2,5]=={1,0,0}
88 # replace_en[3] = &plru_tree[ 4, 1,~0]; #plru_tree[0,1,4]=={0,1,1}
89 # replace_en[2] = &plru_tree[~4, 1,~0]; #plru_tree[0,1,4]=={0,1,0}
90 # replace_en[1] = &plru_tree[ 3,~1,~0]; #plru_tree[0,1,3]=={0,0,1}
91 # replace_en[0] = &plru_tree[~3,~1,~0]; #plru_tree[0,1,3]=={0,0,0}
92 # For each entry traverse the tree. If every tree-node matches
93 # the corresponding bit of the entry's index, this is
94 # the next entry to replace.
96 for i
in range(self
.BITS
):
98 for lvl
in range(LOG_TLB
):
99 idx_base
= (1 << lvl
)-1
100 # lvl0 <=> MSB, lvl1 <=> MSB-1, ...
101 shift
= LOG_TLB
- lvl
102 new_idx
= (i
>> (shift
-1)) & 1
103 plru_idx
= idx_base
+ (i
>> shift
)
104 plru
= Signal(reset_less
=True,
105 name
="plru-%d-%d-%d-%d" %
106 (i
, lvl
, plru_idx
, new_idx
))
107 m
.d
.comb
+= plru
.eq(self
._plru
_tree
[plru_idx
])
109 en
.append(~plru
) # yes inverted (using bool() below)
111 en
.append(plru
) # yes inverted (using bool() below)
112 #print("plru", i, en)
113 # boolean logic manipulation:
114 # plru0 & plru1 & plru2 == ~(~plru0 | ~plru1 | ~plru2)
115 replace
.append(~
Cat(*en
).bool())
116 m
.d
.comb
+= self
.lru_o
.eq(Cat(*replace
))
121 return [self
.acc_en
, self
.lru_o
, self
.acc_i
]
124 class PLRUs(Elaboratable
):
125 def __init__(self
, n_plrus
, n_bits
):
126 warn("nmutil.plru.PLRUs is deprecated due to having a broken API, use "
127 "nmutil.plru2.PLRUs instead", DeprecationWarning, stacklevel
=2)
128 self
.n_plrus
= n_plrus
130 self
.valid
= Signal()
131 self
.way
= Signal(n_bits
)
132 self
.index
= Signal(n_plrus
.bit_length())
133 self
.isel
= Signal(n_plrus
.bit_length())
134 self
.o_index
= Signal(n_bits
)
136 def elaborate(self
, platform
):
137 """Generate TLB PLRUs
142 if self
.n_plrus
== 0:
145 # Binary-to-Unary one-hot, enabled by valid
146 m
.submodules
.te
= te
= Decoder(self
.n_plrus
)
147 comb
+= te
.n
.eq(~self
.valid
)
148 comb
+= te
.i
.eq(self
.index
)
150 out
= Array(Signal(self
.n_bits
, name
="plru_out%d" % x
)
151 for x
in range(self
.n_plrus
))
153 for i
in range(self
.n_plrus
):
155 m
.submodules
["plru_%d" % i
] = plru
= PLRU(self
.n_bits
)
157 comb
+= plru
.acc_en
.eq(te
.o
[i
])
158 comb
+= plru
.acc_i
.eq(self
.way
)
159 comb
+= out
[i
].eq(plru
.lru_o
)
161 # select output based on index
162 comb
+= self
.o_index
.eq(out
[self
.isel
])
167 return [self
.valid
, self
.way
, self
.index
, self
.isel
, self
.o_index
]
170 if __name__
== '__main__':
172 vl
= rtlil
.convert(dut
, ports
=dut
.ports())
173 with
open("test_plru.il", "w") as f
:
177 vl
= rtlil
.convert(dut
, ports
=dut
.ports())
178 with
open("test_plrus.il", "w") as f
: