ScriptStack 1.0.4
Loading...
Searching...
No Matches
Optimizer.cs
Go to the documentation of this file.
1using System;
2using System.Collections.Generic;
3using System.Text;
4
5using ScriptStack.Runtime;
6
7namespace ScriptStack.Compiler
8{
9
10 internal class Optimizer
11 {
12
13 #region Private Variables
14
15 private Executable executable;
16 private bool verbose;
17 private bool done;
18
19 #endregion
20
21 #region Private Methods
22
23 private bool Tripleinstruction(int i)
24 {
25 return i < executable.InstructionsInternal.Count - 2;
26 }
27
28 private bool DoubleInstruction(int i)
29 {
30 return i < executable.InstructionsInternal.Count - 1;
31 }
32
33 private bool IsTemporaryVariable(string identifier)
34 {
35 return identifier.StartsWith("[");
36 }
37
38 private bool IsTemporaryVariable(Operand operand)
39 {
40
41 if (operand.Type != OperandType.Variable)
42 return false;
43
44 return IsTemporaryVariable(operand.Value.ToString());
45
46 }
47
48 private bool IsTemporaryVariableIndex(Operand operand)
49 {
50
51 if (operand.Type != OperandType.Pointer)
52 return false;
53
54 return operand.Pointer.StartsWith("[");
55
56 }
57
58 private bool IsUnaryOperator(OpCode opcode)
59 {
60
61 switch (opcode)
62 {
63
64 case OpCode.INC:
65 case OpCode.DEC:
66 case OpCode.NEG:
67 case OpCode.NOT:
68 return true;
69
70 default:
71 return false;
72
73 }
74
75 }
76
77 private bool IsBinaryOperator(OpCode opcode)
78 {
79
80 switch (opcode)
81 {
82
83 case OpCode.ADD:
84 case OpCode.SUB:
85 case OpCode.MUL:
86 case OpCode.DIV:
87 case OpCode.CEQ:
88 case OpCode.CNE:
89 case OpCode.CG:
90 case OpCode.CGE:
91 case OpCode.CL:
92 case OpCode.CLE:
93 case OpCode.OR:
94 case OpCode.AND:
95 return true;
96
97 default:
98 return false;
99
100 }
101
102 }
103
104 private void InsertOptimiserInfo(int i, string message)
105 {
106
107 if (!verbose)
108 return;
109
110 executable.InstructionsInternal.Insert(i, new Instruction(OpCode.DBG, Operand.Literal(0), Operand.Literal("OPTIMIZER: " + message)));
111
112 }
113
114 private void OptimiseBinaryExpressionEvaluation(int i)
115 {
116
117 List<Instruction> instructions = executable.InstructionsInternal;
118
119 Instruction instruction0 = instructions[i];
120
121 Instruction instruction1 = instructions[i + 1];
122
123 Instruction instruction2 = instructions[i + 2];
124
125 if (instruction0.OpCode != OpCode.MOV)
126 return;
127
128 if (instruction1.OpCode != OpCode.MOV)
129 return;
130
131 if (!IsBinaryOperator(instruction2.OpCode))
132 return;
133
134 if (!IsTemporaryVariable(instruction0.First))
135 return;
136
137 if (!IsTemporaryVariable(instruction1.First))
138 return;
139
140 if (!IsTemporaryVariable(instruction2.First))
141 return;
142
143 if (!IsTemporaryVariable(instruction2.Second))
144 return;
145
146 if (instruction0.First.Value.ToString() == instruction1.First.Value.ToString())
147 return;
148
149 if (instruction0.First.Value.ToString() != instruction2.First.Value.ToString())
150 return;
151
152 if (instruction1.First.Value.ToString() != instruction2.Second.Value.ToString())
153 return;
154
155 InsertOptimiserInfo(i, "Binary Expression Evaluation");
156
157 instruction1.OpCode = instruction2.OpCode;
158
159 instruction1.First = instruction0.First;
160
161 instruction2.OpCode = OpCode.NOP;
162
163 instruction2.First = null;
164
165 instruction2.Second = null;
166
167 done = false;
168
169 }
170
171 private void OptimiseUnaryExpressionAssignment(int iIndex)
172 {
173
174 List<Instruction> listInstructions
175 = executable.InstructionsInternal;
176
177 Instruction scriptInstruction0 = listInstructions[iIndex];
178
179 Instruction scriptInstruction1 = listInstructions[iIndex + 1];
180
181 Instruction scriptInstruction2 = listInstructions[iIndex + 2];
182
183 if (scriptInstruction0.OpCode != OpCode.MOV)
184 return;
185
186 if (!IsUnaryOperator(scriptInstruction1.OpCode))
187 return;
188
189 if (scriptInstruction2.OpCode != OpCode.MOV)
190 return;
191
192 if (!IsTemporaryVariable(scriptInstruction0.First))
193 return;
194
195 if (!IsTemporaryVariable(scriptInstruction1.First))
196 return;
197
198 if (!IsTemporaryVariable(scriptInstruction2.Second))
199 return;
200
201 if (scriptInstruction0.First.Value.ToString() != scriptInstruction1.First.Value.ToString())
202 return;
203
204 if (scriptInstruction0.First.Value.ToString() != scriptInstruction2.Second.Value.ToString())
205 return;
206
207 InsertOptimiserInfo(iIndex, "Unary Expression Assignment");
208
209 scriptInstruction0.First = scriptInstruction2.First;
210
211 scriptInstruction1.First = scriptInstruction2.First;
212
213 scriptInstruction2.OpCode = OpCode.NOP;
214
215 scriptInstruction2.First = null;
216
217 scriptInstruction2.Second = null;
218
219 done = false;
220
221 }
222
223 private void OptimiseBinaryExpressionAssignment(int iIndex)
224 {
225
226 List<Instruction> listInstructions = executable.InstructionsInternal;
227
228 Instruction scriptInstruction0 = listInstructions[iIndex];
229 Instruction scriptInstruction1 = listInstructions[iIndex + 1];
230 Instruction scriptInstruction2 = listInstructions[iIndex + 2];
231
232 if (scriptInstruction0.OpCode != OpCode.MOV) return;
233 if (!IsBinaryOperator(scriptInstruction1.OpCode)) return;
234 if (scriptInstruction2.OpCode != OpCode.MOV) return;
235 if (!IsTemporaryVariable(scriptInstruction0.First)) return;
236 if (!IsTemporaryVariable(scriptInstruction1.First)) return;
237 if (!IsTemporaryVariable(scriptInstruction2.Second)) return;
238 if (scriptInstruction0.First.Value.ToString()
239 != scriptInstruction1.First.Value.ToString())
240 return;
241 if (scriptInstruction0.First.Value.ToString()
242 != scriptInstruction2.Second.Value.ToString())
243 return;
244
245 InsertOptimiserInfo(iIndex, "Binary Expression Assignment");
246
247 scriptInstruction0.First = scriptInstruction2.First;
248 scriptInstruction1.First = scriptInstruction2.First;
249 scriptInstruction2.OpCode = OpCode.NOP;
250 scriptInstruction2.First = null;
251 scriptInstruction2.Second = null;
252
253 done = false;
254 }
255
256 private void OptimiseInstructionTriples(int iIndex)
257 {
258 OptimiseUnaryExpressionAssignment(iIndex);
259
260 OptimiseBinaryExpressionEvaluation(iIndex);
261 OptimiseBinaryExpressionAssignment(iIndex);
262 }
263
264 private void OptimisePushOperation(int iIndex)
265 {
266
267 List<Instruction> listInstructions
268 = executable.InstructionsInternal;
269
270 Instruction scriptInstruction0
271 = listInstructions[iIndex];
272 Instruction scriptInstruction1
273 = listInstructions[iIndex + 1];
274
275 if (scriptInstruction0.OpCode != OpCode.MOV) return;
276 if (scriptInstruction1.OpCode != OpCode.PUSH) return;
277
278 if (!IsTemporaryVariable(scriptInstruction0.First)) return;
279 if (!IsTemporaryVariable(scriptInstruction1.First)) return;
280 if (scriptInstruction0.First.Value.ToString()
281 != scriptInstruction1.First.Value.ToString())
282 return;
283
284 InsertOptimiserInfo(iIndex, "Push Operation");
285
286 scriptInstruction0.OpCode = OpCode.PUSH;
287 scriptInstruction0.First = scriptInstruction0.Second;
288 scriptInstruction0.Second = null;
289 scriptInstruction1.OpCode = OpCode.NOP;
290 scriptInstruction1.First = null;
291 scriptInstruction1.Second = null;
292
293 done = false;
294 }
295
296 private void OptimisePopOperation(int iIndex)
297 {
298
299 List<Instruction> listInstructions
300 = executable.InstructionsInternal;
301
302 Instruction scriptInstruction0
303 = listInstructions[iIndex];
304 Instruction scriptInstruction1
305 = listInstructions[iIndex + 1];
306
307 if (scriptInstruction0.OpCode != OpCode.POP) return;
308 if (scriptInstruction1.OpCode != OpCode.MOV) return;
309
310 if (!IsTemporaryVariable(scriptInstruction0.First)) return;
311 if (!IsTemporaryVariable(scriptInstruction1.Second)) return;
312 if (scriptInstruction0.First.Value.ToString()
313 != scriptInstruction1.Second.Value.ToString())
314 return;
315
316 InsertOptimiserInfo(iIndex, "Pop Operation");
317
318 scriptInstruction0.OpCode = OpCode.POP;
319 scriptInstruction0.First = scriptInstruction1.First;
320 scriptInstruction1.OpCode = OpCode.NOP;
321 scriptInstruction1.First = null;
322 scriptInstruction1.Second = null;
323
324 done = false;
325 }
326
327 private void OptimiseLiteralAssignment(int iIndex)
328 {
329
330 List<Instruction> listInstructions
331 = executable.InstructionsInternal;
332
333 Instruction scriptInstruction0
334 = listInstructions[iIndex];
335 Instruction scriptInstruction1
336 = listInstructions[iIndex + 1];
337 if (scriptInstruction0.OpCode != OpCode.MOV) return;
338 if (scriptInstruction1.OpCode != OpCode.MOV) return;
339 if (!IsTemporaryVariable(scriptInstruction0.First)) return;
340 if (!IsTemporaryVariable(scriptInstruction1.Second)) return;
341 if (scriptInstruction0.First.Value.ToString()
342 != scriptInstruction1.Second.Value.ToString())
343 return;
344
345 InsertOptimiserInfo(iIndex, "Literal Assignment");
346
347 scriptInstruction0.First = scriptInstruction1.First;
348 scriptInstruction1.OpCode = OpCode.NOP;
349 scriptInstruction1.First = null;
350 scriptInstruction1.Second = null;
351
352 done = false;
353 }
354
355 private void OptimiseConditionalJumps(int iIndex)
356 {
357
358 List<Instruction> listInstructions
359 = executable.InstructionsInternal;
360
361 Instruction scriptInstruction0
362 = listInstructions[iIndex];
363 Instruction scriptInstruction1
364 = listInstructions[iIndex + 1];
365 if (scriptInstruction0.OpCode != OpCode.MOV) return;
366 if (scriptInstruction1.OpCode != OpCode.JZ
367 && scriptInstruction1.OpCode != OpCode.JNZ) return;
368 if (!IsTemporaryVariable(scriptInstruction0.First)) return;
369 if (!IsTemporaryVariable(scriptInstruction1.First)) return;
370 if (scriptInstruction0.First.Value.ToString()
371 != scriptInstruction1.First.Value.ToString())
372 return;
373
374 InsertOptimiserInfo(iIndex, "Conditional Jump Expressions");
375
376 scriptInstruction0.OpCode = scriptInstruction1.OpCode;
377 scriptInstruction0.First = scriptInstruction0.Second;
378 scriptInstruction0.Second = scriptInstruction1.Second;
379 scriptInstruction1.OpCode = OpCode.NOP;
380 scriptInstruction1.First = null;
381 scriptInstruction1.Second = null;
382
383 done = false;
384 }
385
386 private void OptimiseArrayIndices(int iIndex)
387 {
388
389 List<Instruction> listInstructions
390 = executable.InstructionsInternal;
391
392 Instruction scriptInstruction0
393 = listInstructions[iIndex];
394 Instruction scriptInstruction1
395 = listInstructions[iIndex + 1];
396 if (scriptInstruction0.OpCode != OpCode.MOV) return;
397 if (scriptInstruction1.OpCode != OpCode.MOV) return;
398 if (scriptInstruction0.Second.Type != OperandType.Variable) return;
399 if (scriptInstruction1.First.Type
400 != OperandType.Pointer) return;
401 if (!IsTemporaryVariable(scriptInstruction0.First)) return;
402 if (!IsTemporaryVariableIndex(scriptInstruction1.First)) return;
403 if (scriptInstruction0.First.Value.ToString()
404 != scriptInstruction1.First.Pointer)
405 return;
406
407 InsertOptimiserInfo(iIndex, "Array Index");
408
409 scriptInstruction0.First = scriptInstruction1.First;
410 scriptInstruction0.First.Pointer
411 = scriptInstruction0.Second.Value.ToString();
412 scriptInstruction0.Second = scriptInstruction1.Second;
413 scriptInstruction1.OpCode = OpCode.NOP;
414 scriptInstruction1.First = null;
415 scriptInstruction1.Second = null;
416
417 done = false;
418 }
419
420 private void EliminateSequentialJumps(int iIndex)
421 {
422
423 List<Instruction> listInstructions
424 = executable.InstructionsInternal;
425
426 Instruction scriptInstruction0
427 = listInstructions[iIndex];
428 Instruction scriptInstruction1
429 = listInstructions[iIndex + 1];
430 if (scriptInstruction0.OpCode != OpCode.JMP) return;
431 if (scriptInstruction0.First.InstructionPointer
432 != scriptInstruction1) return;
433
434 InsertOptimiserInfo(iIndex, "Sequentual Jump Elimination");
435
436 scriptInstruction0.OpCode = OpCode.NOP;
437 scriptInstruction0.First = null;
438 scriptInstruction0.Second = null;
439
440 done = false;
441 }
442
443 private void OptimiseInstructionPairs(int iIndex)
444 {
445 OptimisePushOperation(iIndex);
446 OptimisePopOperation(iIndex);
447 OptimiseLiteralAssignment(iIndex);
448 OptimiseConditionalJumps(iIndex);
449 OptimiseArrayIndices(iIndex);
450 EliminateSequentialJumps(iIndex);
451 }
452
453 private void EliminateSelfAssignments(int iIndex)
454 {
455
456 Instruction scriptInstruction
457 = executable.InstructionsInternal[iIndex];
458 if (scriptInstruction.OpCode != OpCode.MOV) return;
459 Operand operand0 = scriptInstruction.First;
460 Operand operand1 = scriptInstruction.Second;
461 if (operand0.Type != operand1.Type) return;
462 if (operand0.Type != OperandType.Variable
463 && operand0.Type != OperandType.Member
464 && operand1.Type != OperandType.Pointer)
465 return;
466 if (operand0.Value.ToString() != operand1.Value.ToString())
467 return;
468 switch (operand0.Type)
469 {
470 case OperandType.Member:
471 if (operand0.Member.ToString()
472 != operand1.Member.ToString())
473 return;
474 break;
475 case OperandType.Pointer:
476 if (operand0.Pointer != operand1.Pointer)
477 return;
478 break;
479 }
480
481 InsertOptimiserInfo(iIndex, "Self Assignment Removal");
482
483 scriptInstruction.OpCode = OpCode.NOP;
484 scriptInstruction.First = null;
485 scriptInstruction.Second = null;
486
487 done = false;
488 }
489
490 private void OptimiseConstantConditionalJumps(int iIndex)
491 {
492
493 List<Instruction> listInstructions
494 = executable.InstructionsInternal;
495
496 Instruction scriptInstruction
497 = listInstructions[iIndex];
498 if (scriptInstruction.OpCode != OpCode.JZ
499 && scriptInstruction.OpCode != OpCode.JNZ) return;
500 if (scriptInstruction.First.Type != OperandType.Literal) return;
501 if (scriptInstruction.First.Value.GetType() != typeof(bool)) return;
502 bool bCondition = (bool) scriptInstruction.First.Value;
503
504 InsertOptimiserInfo(iIndex, "Constant Conditional Jump");
505
506 OpCode opcodeJump = scriptInstruction.OpCode;
507 if ((opcodeJump == OpCode.JZ && bCondition)
508 || (opcodeJump == OpCode.JNZ && !bCondition))
509 {
510 scriptInstruction.OpCode = OpCode.JMP;
511 scriptInstruction.First = scriptInstruction.Second;
512 scriptInstruction.Second = null;
513 }
514 else
515 {
516 scriptInstruction.OpCode = OpCode.NOP;
517 scriptInstruction.First = null;
518 scriptInstruction.Second = null;
519 }
520
521 done = false;
522 }
523
524 private void OptimiseIncrementsAndDecrements(int iIndex)
525 {
526
527 Instruction scriptInstruction
528 = executable.InstructionsInternal[iIndex];
529 if (scriptInstruction.OpCode != OpCode.ADD
530 && scriptInstruction.OpCode != OpCode.SUB) return;
531 if (scriptInstruction.First.Type != OperandType.Variable
532 && scriptInstruction.First.Type != OperandType.Member
533 && scriptInstruction.First.Type != OperandType.Pointer)
534 return;
535 if (scriptInstruction.Second.Type != OperandType.Literal) return;
536 object objectLiteral = scriptInstruction.Second.Value;
537 Type typeLiteral = objectLiteral.GetType();
538 if (typeLiteral != typeof(int) && typeLiteral != typeof(float)) return;
539 if (typeLiteral == typeof(int) && Math.Abs((int)objectLiteral) != 1) return;
540 if (typeLiteral == typeof(float) && Math.Abs((float)objectLiteral) != 1.0f) return;
541
542 InsertOptimiserInfo(iIndex, "Increment/Decrement Optimisation");
543
544 float fValue = 0.0f;
545
546 if (typeLiteral == typeof(int))
547 fValue = (float)(int)objectLiteral;
548 else
549 fValue = (float)objectLiteral;
550
551
552 OpCode opcodeOld = scriptInstruction.OpCode;
553 bool bIncrement = opcodeOld == OpCode.ADD && fValue > 0.0f
554 || opcodeOld == OpCode.SUB && fValue < 0.0f;
555
556 scriptInstruction.OpCode = bIncrement ? OpCode.INC : OpCode.DEC;
557 scriptInstruction.Second = null;
558
559 done = false;
560 }
561
562 private void OptimiseSingleInstructions(int iIndex)
563 {
564 EliminateSelfAssignments(iIndex);
565 OptimiseConstantConditionalJumps(iIndex);
566 OptimiseIncrementsAndDecrements(iIndex);
567 }
568
569 private void TraverseActiveInstructions(
570 Dictionary<Instruction, bool> dictScriptInstructionsActive,
571 int iNextInstuction)
572 {
573 while (true)
574 {
575 Instruction scriptInstruction
576 = executable.InstructionsInternal[iNextInstuction];
577 if (dictScriptInstructionsActive.ContainsKey(scriptInstruction))
578 return;
579
580 dictScriptInstructionsActive[scriptInstruction] = true;
581
582 switch (scriptInstruction.OpCode)
583 {
584 case OpCode.JMP:
585 iNextInstuction
586 = (int) scriptInstruction.First.InstructionPointer.Address;
587 break;
588 case OpCode.JZ:
589 case OpCode.JNZ:
590 TraverseActiveInstructions(dictScriptInstructionsActive,
591 (int)scriptInstruction.Second.InstructionPointer.Address);
592 ++iNextInstuction;
593 break;
594 case OpCode.CALL:
595 case OpCode.RUN:
596 TraverseActiveInstructions(dictScriptInstructionsActive,
597 (int)scriptInstruction.First.FunctionPointer.EntryPoint.Address);
598 ++iNextInstuction;
599 break;
600 case OpCode.RET:
601 return;
602 default:
603 ++iNextInstuction;
604 break;
605 }
606 }
607 }
608
609 private void EliminateDeadCode()
610 {
611 executable.Sort();
612
613 Dictionary<Instruction, bool> dictScriptInstructionsActive
614 = new Dictionary<Instruction, bool>();
615
616 foreach (Function scriptFunction in executable.Functions.Values)
617 {
618 TraverseActiveInstructions(dictScriptInstructionsActive,
619 (int) scriptFunction.EntryPoint.Address);
620 }
621
622 foreach (Instruction scriptInstruction in executable.InstructionsInternal)
623 {
624 if (scriptInstruction.OpCode == OpCode.DBG) continue;
625 if (scriptInstruction.OpCode == OpCode.DSB) continue;
626 if (scriptInstruction.OpCode == OpCode.DB) continue;
627
628 if (!dictScriptInstructionsActive.ContainsKey(scriptInstruction))
629 {
630 scriptInstruction.OpCode = OpCode.NOP;
631 scriptInstruction.First = null;
632 scriptInstruction.Second = null;
633
634 done = false;
635 }
636 }
637 }
638
639 private void EliminateUnusedTempVariables()
640 {
641 Dictionary<String, Instruction> dictTempVariableAssignments
642 = new Dictionary<string, Instruction>();
643
644 foreach (Instruction scriptInstruction in executable.InstructionsInternal)
645 {
646 OpCode opcode = scriptInstruction.OpCode;
647 if ((opcode == OpCode.MOV || opcode == OpCode.DC)
648 && IsTemporaryVariable(scriptInstruction.First))
649 {
650 dictTempVariableAssignments[scriptInstruction.First.Value.ToString()]
651 = scriptInstruction;
652 }
653
654 Operand operandDest = scriptInstruction.First;
655 if (operandDest == null) continue;
656 if (opcode != OpCode.MOV && IsTemporaryVariable(operandDest))
657 dictTempVariableAssignments.Remove(
658 operandDest.Value.ToString());
659 if ((operandDest.Type == OperandType.Member
660 || operandDest.Type == OperandType.Pointer)
661 && IsTemporaryVariable(operandDest.Value.ToString()))
662 dictTempVariableAssignments.Remove(
663 operandDest.Value.ToString());
664 if (operandDest.Type == OperandType.Pointer
665 && IsTemporaryVariable(operandDest.Pointer))
666 dictTempVariableAssignments.Remove(
667 operandDest.Pointer);
668 Operand operandSource = scriptInstruction.Second;
669 if (operandSource == null) continue;
670 switch (operandSource.Type)
671 {
672 case OperandType.Literal: continue;
673 case OperandType.Variable:
674 case OperandType.Member:
675 if (IsTemporaryVariable(operandSource.Value.ToString()))
676 dictTempVariableAssignments.Remove(
677 operandSource.Value.ToString());
678 break;
679 case OperandType.Pointer:
680 if (IsTemporaryVariable(operandSource.Value.ToString()))
681 dictTempVariableAssignments.Remove(
682 operandSource.Value.ToString());
683 if (IsTemporaryVariable(operandSource.Pointer))
684 dictTempVariableAssignments.Remove(
685 operandSource.Pointer);
686 break;
687 }
688 }
689 foreach (Instruction scriptInstruction
690 in dictTempVariableAssignments.Values)
691 {
692 String strOldInstruction = scriptInstruction.ToString();
693
694 scriptInstruction.OpCode = OpCode.NOP;
695 scriptInstruction.First = null;
696 scriptInstruction.Second = null;
697 }
698
699 if (dictTempVariableAssignments.Count > 0)
700 done = false;
701 }
702
703 #endregion
704
705 #region Public Methods
706
707 public Optimizer(Executable executable)
708 {
709
710 verbose = false;
711 this.executable = executable;
712
713 }
714
715 public void Optimize()
716 {
717
718 List<Instruction> instructions = executable.InstructionsInternal;
719
720 done = false;
721
722 while (!done)
723 {
724 done = true;
725
726 for (int i = 0; i < instructions.Count; i++)
727 {
728
729 if (Tripleinstruction(i))
730 OptimiseInstructionTriples(i);
731
732 if (DoubleInstruction(i))
733 OptimiseInstructionPairs(i);
734
735 OptimiseSingleInstructions(i);
736
737 executable.Clean();
738
739 }
740 }
741
742 EliminateUnusedTempVariables();
743
744 EliminateDeadCode();
745
746 executable.Clean();
747
748 }
749
750 public bool OptimizerInfo
751 {
752 get { return verbose; }
753 set { verbose = value; }
754 }
755
756 #endregion
757
758 }
759
760}
ScriptStack.Runtime.Operand.InstructionPointer
Instruction InstructionPointer
Definition Operand.cs:242