1 #pragma once
2
3 #include <list>
4 #include "MIPS.h"
5 #include "BasicBlock.h"
6
7 #include "BlockLookupOneWay.h"
8 #include "BlockLookupTwoWay.h"
9
RangesOverlap(uint32 x1,uint32 x2,uint32 y1,uint32 y2)10 static bool RangesOverlap(uint32 x1, uint32 x2, uint32 y1, uint32 y2)
11 {
12 assert(x1 <= x2);
13 assert(y1 <= y2);
14 return (x1 <= y2) && (y1 <= x2);
15 }
16
17 typedef uint32 (*TranslateFunctionType)(CMIPS*, uint32);
18 typedef std::shared_ptr<CBasicBlock> BasicBlockPtr;
19
20 template <typename BlockLookupType, uint32 instructionSize = 4>
21 class CGenericMipsExecutor : public CMipsExecutor
22 {
23 public:
24 enum
25 {
26 MAX_BLOCK_SIZE = 0x1000,
27 };
28
29 enum
30 {
31 RECYCLE_NOLINK_THRESHOLD = 16,
32 };
33
CGenericMipsExecutor(CMIPS & context,uint32 maxAddress)34 CGenericMipsExecutor(CMIPS& context, uint32 maxAddress)
35 : m_emptyBlock(std::make_shared<CBasicBlock>(context, MIPS_INVALID_PC, MIPS_INVALID_PC))
36 , m_context(context)
37 , m_maxAddress(maxAddress)
38 , m_addressMask(maxAddress - 1)
39 , m_blockLookup(m_emptyBlock.get(), maxAddress)
40 {
41 m_emptyBlock->Compile();
42 ResetBlockOutLinks(m_emptyBlock.get());
43
44 assert(!context.m_emptyBlockHandler);
45 context.m_emptyBlockHandler =
46 [&](CMIPS* context) {
47 uint32 address = m_context.m_State.nPC & m_addressMask;
48 PartitionFunction(address);
49 auto block = FindBlockStartingAt(address);
50 assert(!block->IsEmpty());
51 block->Execute();
52 };
53 }
54
55 virtual ~CGenericMipsExecutor() = default;
56
Execute(int cycles)57 int Execute(int cycles) override
58 {
59 m_context.m_State.cycleQuota = cycles;
60 #ifdef DEBUGGER_INCLUDED
61 m_mustBreak = false;
62 m_initQuota = cycles;
63 #endif
64 while(m_context.m_State.nHasException == 0)
65 {
66 uint32 address = m_context.m_State.nPC & m_addressMask;
67 auto block = m_blockLookup.FindBlockAt(address);
68 block->Execute();
69 }
70 m_context.m_State.nHasException &= ~MIPS_EXECUTION_STATUS_QUOTADONE;
71 #ifdef DEBUGGER_INCLUDED
72 if(m_context.m_State.nHasException == MIPS_EXCEPTION_BREAKPOINT)
73 {
74 m_mustBreak = true;
75 m_context.m_State.nHasException = MIPS_EXCEPTION_NONE;
76 }
77 m_breakpointsDisabledOnce = false;
78 #endif
79 return m_context.m_State.cycleQuota;
80 }
81
FindBlockStartingAt(uint32 address)82 CBasicBlock* FindBlockStartingAt(uint32 address) const
83 {
84 return m_blockLookup.FindBlockAt(address);
85 }
86
Reset()87 void Reset() override
88 {
89 m_blockLookup.Clear();
90 m_blocks.clear();
91 m_blockOutLinks.clear();
92 }
93
ClearActiveBlocksInRange(uint32 start,uint32 end,bool executing)94 void ClearActiveBlocksInRange(uint32 start, uint32 end, bool executing) override
95 {
96 CBasicBlock* currentBlock = nullptr;
97 if(executing)
98 {
99 currentBlock = FindBlockStartingAt(m_context.m_State.nPC);
100 assert(!currentBlock->IsEmpty());
101 }
102 ClearActiveBlocksInRangeInternal(start, end, currentBlock);
103 }
104
105 #ifdef DEBUGGER_INCLUDED
MustBreak()106 bool MustBreak() const override
107 {
108 return m_mustBreak;
109 }
110
DisableBreakpointsOnce()111 void DisableBreakpointsOnce() override
112 {
113 m_breakpointsDisabledOnce = true;
114 }
115
FilterBreakpoint()116 bool FilterBreakpoint() override
117 {
118 return ((m_initQuota == m_context.m_State.cycleQuota) && m_breakpointsDisabledOnce);
119 }
120 #endif
121
122 protected:
123 typedef std::list<BasicBlockPtr> BlockList;
124
HasBlockAt(uint32 address)125 bool HasBlockAt(uint32 address) const
126 {
127 auto block = m_blockLookup.FindBlockAt(address);
128 return !block->IsEmpty();
129 }
130
CreateBlock(uint32 start,uint32 end)131 void CreateBlock(uint32 start, uint32 end)
132 {
133 assert(!HasBlockAt(start));
134 auto block = BlockFactory(m_context, start, end);
135 ResetBlockOutLinks(block.get());
136 m_blockLookup.AddBlock(block.get());
137 m_blocks.push_back(std::move(block));
138 }
139
ResetBlockOutLinks(CBasicBlock * block)140 void ResetBlockOutLinks(CBasicBlock* block)
141 {
142 for(uint32 i = 0; i < LINK_SLOT_MAX; i++)
143 {
144 block->SetOutLink(static_cast<LINK_SLOT>(i), std::end(m_blockOutLinks));
145 }
146 }
147
BlockFactory(CMIPS & context,uint32 start,uint32 end)148 virtual BasicBlockPtr BlockFactory(CMIPS& context, uint32 start, uint32 end)
149 {
150 auto result = std::make_shared<CBasicBlock>(context, start, end);
151 result->Compile();
152 return result;
153 }
154
SetupBlockLinks(uint32 startAddress,uint32 endAddress,uint32 branchAddress)155 void SetupBlockLinks(uint32 startAddress, uint32 endAddress, uint32 branchAddress)
156 {
157 auto block = m_blockLookup.FindBlockAt(startAddress);
158
159 {
160 uint32 nextBlockAddress = (endAddress + 4) & m_addressMask;
161 const auto linkSlot = LINK_SLOT_NEXT;
162 auto link = m_blockOutLinks.insert(std::make_pair(nextBlockAddress, BLOCK_OUT_LINK{linkSlot, startAddress, false}));
163 block->SetOutLink(linkSlot, link);
164
165 auto nextBlock = m_blockLookup.FindBlockAt(nextBlockAddress);
166 if(!nextBlock->IsEmpty())
167 {
168 block->LinkBlock(linkSlot, nextBlock);
169 link->second.live = true;
170 }
171 }
172
173 if(branchAddress != 0)
174 {
175 branchAddress &= m_addressMask;
176 const auto linkSlot = LINK_SLOT_BRANCH;
177 auto link = m_blockOutLinks.insert(std::make_pair(branchAddress, BLOCK_OUT_LINK{linkSlot, startAddress, false}));
178 block->SetOutLink(linkSlot, link);
179
180 auto branchBlock = m_blockLookup.FindBlockAt(branchAddress);
181 if(!branchBlock->IsEmpty())
182 {
183 block->LinkBlock(linkSlot, branchBlock);
184 link->second.live = true;
185 }
186 }
187 else
188 {
189 block->SetOutLink(LINK_SLOT_BRANCH, std::end(m_blockOutLinks));
190 }
191
192 //Resolve any block links that could be valid now that block has been created
193 {
194 auto lowerBound = m_blockOutLinks.lower_bound(startAddress);
195 auto upperBound = m_blockOutLinks.upper_bound(startAddress);
196 for(auto blockLinkIterator = lowerBound; blockLinkIterator != upperBound; blockLinkIterator++)
197 {
198 auto& blockLink = blockLinkIterator->second;
199 if(blockLink.live) continue;
200 auto referringBlock = m_blockLookup.FindBlockAt(blockLink.srcAddress);
201 if(referringBlock->IsEmpty()) continue;
202 referringBlock->LinkBlock(blockLink.slot, block);
203 blockLink.live = true;
204 }
205 }
206 }
207
PartitionFunction(uint32 startAddress)208 virtual void PartitionFunction(uint32 startAddress)
209 {
210 uint32 endAddress = startAddress + MAX_BLOCK_SIZE;
211 uint32 branchAddress = 0;
212 for(uint32 address = startAddress; address < endAddress; address += 4)
213 {
214 uint32 opcode = m_context.m_pMemoryMap->GetInstruction(address);
215 auto branchType = m_context.m_pArch->IsInstructionBranch(&m_context, address, opcode);
216 if(branchType == MIPS_BRANCH_NORMAL)
217 {
218 branchAddress = m_context.m_pArch->GetInstructionEffectiveAddress(&m_context, address, opcode);
219 endAddress = address + 4;
220 break;
221 }
222 else if(branchType == MIPS_BRANCH_NODELAY)
223 {
224 endAddress = address;
225 break;
226 }
227 }
228 assert((endAddress - startAddress) <= MAX_BLOCK_SIZE);
229 assert(endAddress <= m_maxAddress);
230 CreateBlock(startAddress, endAddress);
231 auto block = FindBlockStartingAt(startAddress);
232 if(block->GetRecycleCount() < RECYCLE_NOLINK_THRESHOLD)
233 {
234 SetupBlockLinks(startAddress, endAddress, branchAddress);
235 }
236 }
237
238 //Unlink and removes block from all of our bookkeeping structures
OrphanBlock(CBasicBlock * block)239 void OrphanBlock(CBasicBlock* block)
240 {
241 auto orphanBlockLinkSlot =
242 [&](LINK_SLOT linkSlot) {
243 auto link = block->GetOutLink(linkSlot);
244 if(link != std::end(m_blockOutLinks))
245 {
246 if(link->second.live)
247 {
248 block->UnlinkBlock(linkSlot);
249 }
250 block->SetOutLink(linkSlot, std::end(m_blockOutLinks));
251 m_blockOutLinks.erase(link);
252 }
253 };
254 orphanBlockLinkSlot(LINK_SLOT_NEXT);
255 orphanBlockLinkSlot(LINK_SLOT_BRANCH);
256 }
257
ClearActiveBlocksInRangeInternal(uint32 start,uint32 end,CBasicBlock * protectedBlock)258 void ClearActiveBlocksInRangeInternal(uint32 start, uint32 end, CBasicBlock* protectedBlock)
259 {
260 //Widen scan range since blocks starting before the range can end in the range
261 uint32 scanStart = static_cast<uint32>(std::max<int64>(0, static_cast<uint64>(start) - MAX_BLOCK_SIZE));
262 uint32 scanEnd = end;
263 assert(scanEnd > scanStart);
264
265 std::set<CBasicBlock*> clearedBlocks;
266 for(uint32 address = scanStart; address < scanEnd; address += instructionSize)
267 {
268 auto block = m_blockLookup.FindBlockAt(address);
269 if(block->IsEmpty()) continue;
270 if(block == protectedBlock) continue;
271 if(!RangesOverlap(block->GetBeginAddress(), block->GetEndAddress(), start, end)) continue;
272 clearedBlocks.insert(block);
273 m_blockLookup.DeleteBlock(block);
274 }
275
276 //Remove pending block link entries for the blocks that are about to be cleared
277 for(auto& block : clearedBlocks)
278 {
279 OrphanBlock(block);
280 }
281
282 //Undo all stale links
283 for(auto& block : clearedBlocks)
284 {
285 auto lowerBound = m_blockOutLinks.lower_bound(block->GetBeginAddress());
286 auto upperBound = m_blockOutLinks.upper_bound(block->GetBeginAddress());
287 for(auto blockLinkIterator = lowerBound; blockLinkIterator != upperBound; blockLinkIterator++)
288 {
289 auto& blockLink = blockLinkIterator->second;
290 if(!blockLink.live) continue;
291 auto referringBlock = m_blockLookup.FindBlockAt(blockLink.srcAddress);
292 if(referringBlock->IsEmpty()) continue;
293 referringBlock->UnlinkBlock(blockLink.slot);
294 blockLink.live = false;
295 }
296 }
297
298 if(!clearedBlocks.empty())
299 {
300 m_blocks.remove_if([&](const BasicBlockPtr& block) { return clearedBlocks.find(block.get()) != std::end(clearedBlocks); });
301 }
302 }
303
304 BlockList m_blocks;
305 BasicBlockPtr m_emptyBlock;
306 BlockOutLinkMap m_blockOutLinks;
307 CMIPS& m_context;
308 uint32 m_maxAddress = 0;
309 uint32 m_addressMask = 0;
310
311 BlockLookupType m_blockLookup;
312
313 #ifdef DEBUGGER_INCLUDED
314 bool m_mustBreak = false;
315 bool m_breakpointsDisabledOnce = false;
316 int m_initQuota = 0;
317 #endif
318 };
319