1 from nmigen
import Signal
, Module
, Cat
, Const
2 from nmigen
.hdl
.ir
import Elaboratable
5 from ptw
import TLBUpdate
, PTE
, ASID_WIDTH
7 class PLRU(Elaboratable
):
8 """ PLRU - Pseudo Least Recently Used Replacement
20 def __init__(self
, entries
):
21 self
.entries
= entries
22 self
.lu_hit
= Signal(entries
)
23 self
.replace_en_o
= Signal(entries
)
24 self
.lu_access_i
= Signal()
25 # Tree (bit per entry)
26 self
.TLBSZ
= 2*(self
.entries
-1)
27 self
.plru_tree
= Signal(self
.TLBSZ
)
28 self
.plru_tree_o
= Signal(self
.TLBSZ
)
30 def elaborate(self
, platform
):
33 # Just predefine which nodes will be set/cleared
34 # E.g. for a TLB with 8 entries, the for-loop is semantically
35 # equivalent to the following pseudo-code:
37 # lu_hit[7]: plru_tree[0, 2, 6] = {1, 1, 1};
38 # lu_hit[6]: plru_tree[0, 2, 6] = {1, 1, 0};
39 # lu_hit[5]: plru_tree[0, 2, 5] = {1, 0, 1};
40 # lu_hit[4]: plru_tree[0, 2, 5] = {1, 0, 0};
41 # lu_hit[3]: plru_tree[0, 1, 4] = {0, 1, 1};
42 # lu_hit[2]: plru_tree[0, 1, 4] = {0, 1, 0};
43 # lu_hit[1]: plru_tree[0, 1, 3] = {0, 0, 1};
44 # lu_hit[0]: plru_tree[0, 1, 3] = {0, 0, 0};
45 # default: begin /* No hit */ end
47 LOG_TLB
= int(log2(self
.entries
))
49 for i
in range(self
.entries
):
50 # we got a hit so update the pointer as it was least recently used
51 hit
= Signal(reset_less
=True)
52 m
.d
.comb
+= hit
.eq(self
.lu_hit
[i
] & self
.lu_access_i
)
54 # Set the nodes to the values we would expect
55 for lvl
in range(LOG_TLB
):
57 # lvl0 <=> MSB, lvl1 <=> MSB-1, ...
58 shift
= LOG_TLB
- lvl
;
59 new_idx
= Const(~
((i
>> (shift
-1)) & 1), (1, False))
60 plru_idx
= idx_base
+ (i
>> shift
)
61 print ("plru", i
, lvl
, hex(idx_base
),
62 plru_idx
, shift
, new_idx
)
63 m
.d
.comb
+= self
.plru_tree_o
[plru_idx
].eq(new_idx
)
65 # Decode tree to write enable signals
66 # Next for-loop basically creates the following logic for e.g.
67 # an 8 entry TLB (note: pseudo-code obviously):
68 # replace_en[7] = &plru_tree[ 6, 2, 0]; #plru_tree[0,2,6]=={1,1,1}
69 # replace_en[6] = &plru_tree[~6, 2, 0]; #plru_tree[0,2,6]=={1,1,0}
70 # replace_en[5] = &plru_tree[ 5,~2, 0]; #plru_tree[0,2,5]=={1,0,1}
71 # replace_en[4] = &plru_tree[~5,~2, 0]; #plru_tree[0,2,5]=={1,0,0}
72 # replace_en[3] = &plru_tree[ 4, 1,~0]; #plru_tree[0,1,4]=={0,1,1}
73 # replace_en[2] = &plru_tree[~4, 1,~0]; #plru_tree[0,1,4]=={0,1,0}
74 # replace_en[1] = &plru_tree[ 3,~1,~0]; #plru_tree[0,1,3]=={0,0,1}
75 # replace_en[0] = &plru_tree[~3,~1,~0]; #plru_tree[0,1,3]=={0,0,0}
76 # For each entry traverse the tree. If every tree-node matches
77 # the corresponding bit of the entry's index, this is
78 # the next entry to replace.
80 for i
in range(self
.entries
):
82 for lvl
in range(LOG_TLB
):
84 # lvl0 <=> MSB, lvl1 <=> MSB-1, ...
85 shift
= LOG_TLB
- lvl
;
86 new_idx
= (i
>> (shift
-1)) & 1;
87 plru_idx
= idx_base
+ (i
>>shift
)
88 plru
= Signal(reset_less
=True,
89 name
="plru-%d-%d-%d" % (i
, lvl
, plru_idx
))
90 m
.d
.comb
+= plru
.eq(self
.plru_tree
[plru_idx
])
91 # en &= plru_tree_q[idx_base + (i>>shift)] == new_idx;
93 en
.append(~plru
) # yes inverted (using bool())
95 en
.append(plru
) # yes inverted (using bool())
97 # boolean logic manipulation:
98 # plru0 & plru1 & plru2 == ~(~plru0 | ~plru1 | ~plru2)
99 replace
.append(~
Cat(*en
).bool())
100 m
.d
.comb
+= self
.replace_en_o
.eq(Cat(*replace
))