1 /**
2 Copyright: Copyright (c) 2013-2014 Andrey Penechko.
3 License: a$(WEB boost.org/LICENSE_1_0.txt, Boost License 1.0).
4 Authors: Andrey Penechko.
5 */
6
7 module emulator.dcpu.memoryanalyzer;
8
9 import std.array;
10 import std.algorithm : sort, find;
11 import std.conv : to;
12 import std..string : format;
13 import std.stdio : writeln, writefln;
14
15 import emulator.dcpu.dcpu;
16 import emulator.dcpu.constants;
17 import emulator.dcpu.instruction;
18 import emulator.dcpu.execution;
19
20 class MemoryAnalyzer(Cpu)
21 {
22 protected:
23 Cpu* _dcpu;
24
25 public:
26
27 MemoryMap memoryMap;
28
29 this(Cpu* dcpu)
30 {
31 _dcpu = dcpu;
32 }
33
34 // PC "jumps" to 0 at cpu start
35 enum ushort defaultEntryPoint = 0;
36
37 MemoryBlock* blockAtPos(ushort position)
38 {
39 auto blocks = find!"a.position <= b && b < a.position + a.length"
40 (memoryMap.blocks, position);
41
42 if (blocks.length) return blocks[0];
43
44 return null;
45 }
46
47 Label* labelAt(ushort position, LabelType type)
48 {
49 auto labels = find!"a.position == b"(memoryMap.labels, position);
50
51 if (labels.length)
52 {
53 if (labels[0].type == LabelType.label && type == LabelType.subroutine)
54 labels[0].type = type;
55
56 return labels[0];
57 }
58
59 auto newLabel = new Label(position, type);
60
61 writefln("New %s label at %04x ", type, position);
62
63 memoryMap.labels ~= newLabel;
64
65 return newLabel;
66 }
67
68 void buildMemoryMap()
69 {
70 auto processQueue = Appender!(Transition*[])([]); // control flow transitions (JMP and set, add, sub pc)
71
72 processQueue ~= new Transition(0,
73 labelAt(defaultEntryPoint, LabelType.label),
74 TransitionType.entry,
75 false);
76
77 void processTransition(Transition* transition)
78 {
79 ushort entryPoint = transition.target.position;
80
81 // Transition to an existing block
82 if (auto blockFound = blockAtPos(entryPoint))
83 {
84 blockFound.transitionsIn ~= transition;
85 transition.toBlock = blockFound;
86 return;
87 }
88
89 // New block
90 auto block = new MemoryBlock(entryPoint);
91 block.type = BlockType.code;
92 memoryMap.blocks ~= block;
93 transition.toBlock = block;
94
95 writefln("New block at %04x", entryPoint);
96
97 ushort pointer = entryPoint;
98 Instruction instr;
99 bool inCondition = false;
100
101 while (pointer >= entryPoint)
102 {
103 // No place to expand, other (code) block detected
104 if (auto blockFound = blockAtPos(pointer))
105 {
106 blockFound.transitionsIn ~= transition;
107 writefln("Block ended [No space] %04x..%04x\n",
108 blockFound.position, blockFound.position+blockFound.length-1);
109 return;
110 }
111
112 // Get instruction at pointer
113 instr = fetchAt(*_dcpu, pointer);
114
115 void onBlockEnd()
116 {
117 block.length = pointer + instr.size - block.position;
118 block.lastInstr = pointer;
119 writefln("Block ended [Jump] %04x..%04x\n",
120 block.position, block.position+block.length-1);
121 }
122
123 // Check instruction
124 // If SET PC, literal that it is jump
125 if (instr.operands == 2 && instr.operandB == 0x1c/*PC*/)
126 {
127 // Unconditional branching
128 if (instr.opcode == SET || instr.opcode == STI || instr.opcode == STD) // temp TODO: add, sub with literals
129 {
130 if (isOperandImmediate[instr.operandA])
131 {
132 ushort pc = cast(ushort)(pointer+1), sp = 0xFFFF;
133 ushort transitionTo = getOperandA(*_dcpu, instr.operandA, pc, sp).get();
134
135 // outcoming transition
136 auto newTransition = new Transition(pointer,
137 labelAt(transitionTo, LabelType.label),
138 TransitionType.jump,
139 inCondition,
140 block);
141
142 block.transitionsFrom ~= newTransition;
143 processQueue ~= newTransition;
144
145 writeln(*newTransition);
146 }
147
148 if (!inCondition)
149 {
150 onBlockEnd();
151 return;
152 }
153 }
154 }
155 // If JSR that it is call
156 else if (instr.operands == 1 && isOperandImmediate[instr.operandA])
157 {
158 if (instr.opcode == JSR)
159 {
160 ushort pc = cast(ushort)(pointer+1), sp = 0xFFFF;
161 ushort transitionTo = getOperandA(*_dcpu, instr.operandA, pc, sp).get();
162
163 // outcoming transition
164 auto newTransition = new Transition(pointer,
165 labelAt(transitionTo, LabelType.subroutine),
166 TransitionType.call,
167 inCondition,
168 block);
169
170 block.transitionsFrom ~= newTransition;
171 processQueue ~= newTransition;
172
173 writeln(*newTransition);
174
175 }
176 else if(instr.opcode == IAS)
177 {
178 ushort pc = cast(ushort)(pointer+1), sp = 0xFFFF;
179 ushort transitionTo = getOperandA(*_dcpu, instr.operandA, pc, sp).get();
180
181 // outcoming transition. Indirect
182 auto newTransition = new Transition(pointer,
183 labelAt(transitionTo, LabelType.int_handler),
184 TransitionType.intHandler,
185 inCondition,
186 block);
187
188 block.transitionsFrom ~= newTransition;
189 processQueue ~= newTransition;
190
191 writeln(*newTransition);
192 }
193 }
194 else if (!isValidInstruction(instr))
195 {
196 writefln("Block ended [Invalid found] %04x..%04x\n",
197 block.position, block.position+block.length-1);
198 return;
199 }
200
201 inCondition = isConditionalInstruction(instr);
202 pointer += instr.size;
203 block.length += instr.size;
204 }
205 }
206
207 uint iterations;
208 while(!processQueue.data.empty && iterations < 1000)
209 {
210 Transition* trans = processQueue.data[$-1];
211
212 memoryMap.transitions ~= trans;
213
214 processQueue.shrinkTo(processQueue.data.length-1);
215
216 if (trans.target.position == trans.from && trans.type != TransitionType.entry)
217 {
218 trans.target.type = LabelType.crash;
219 }
220
221 processTransition(trans);
222 }
223
224 // sort blocks and transitions.
225 memoryMap.transitions.sort!"a.from < b.from";
226 memoryMap.blocks.sort!"a.position < b.position";
227 memoryMap.labels.sort!"a.position < b.position";
228
229 foreach(i, transition; memoryMap.transitions)
230 {
231 transition.index = i;
232 }
233
234 foreach(i, block; memoryMap.blocks)
235 {
236 block.index = i;
237 }
238
239 uint[LabelType.max+1] labelCounters;
240 Label*[][LabelType.max+1] typeLabels; // labels of the same type;
241
242 foreach(label; memoryMap.labels)
243 {
244 label.index = labelCounters[label.type]++;
245 typeLabels[label.type] ~= label;
246 writeln(*label);
247 }
248
249 foreach(labelArray; typeLabels)
250 {
251 foreach(label; labelArray)
252 {
253 label.typeCount = labelArray.length;
254 }
255 }
256 }
257 }
258
259
260 enum TransitionType
261 {
262 call,
263 jump,
264 intHandler,
265 entry
266 }
267
268 struct Transition
269 {
270 ushort from;
271 Label* target;
272 TransitionType type;
273 bool conditional;
274 MemoryBlock* fromBlock;
275 MemoryBlock* toBlock;
276 size_t index; // index in transition list of specific type.
277
278 string toString()
279 {
280 return format("Transition %04x -> %04x %s from %04x to %04x",
281 from, target.position, type, fromBlock ? fromBlock.position : 0, toBlock ? toBlock.position : 0);
282 }
283 }
284
285 enum LabelType
286 {
287 subroutine,
288 crash,
289 label,
290 int_handler,
291 start
292 }
293
294 struct Label
295 {
296 ushort position;
297 LabelType type;
298 size_t index;
299 size_t typeCount; // Count of labels of the same type
300
301 string toString()
302 {
303 if (typeCount == 1)
304 return to!string(type);
305
306 return format("%s_%s", type, index);
307 }
308 }
309
310 enum BlockType
311 {
312 data,
313 code,
314 empty
315 }
316
317 struct MemoryBlock
318 {
319 size_t position; // in memory
320 size_t lastInstr; // position
321 size_t length; // in words;
322 Transition*[] transitionsIn; // jumps made to this block
323 Transition*[] transitionsFrom; // jumps from this block
324 BlockType type;
325 size_t index; // index in block list. Used for setting labels
326
327 string toString()
328 {
329 return format("[%3s] %04x..%s %s", index, position, length == 0 ? "Invalid" : format("%04x", lastInstr), type);
330 }
331 }
332
333 struct MemoryMap
334 {
335 Transition*[] transitions;
336 Label*[] labels;
337 MemoryBlock*[] blocks;
338 }