ScriptStack 1.0.5
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 = executable.InstructionsInternal;
494
495 Instruction scriptInstruction = listInstructions[iIndex];
496
497 if (scriptInstruction.OpCode != OpCode.JZ && scriptInstruction.OpCode != OpCode.JNZ)
498 return;
499
500 if (scriptInstruction.First.Type != OperandType.Literal)
501 return;
502
503 if (scriptInstruction.First.Value.GetType() != typeof(bool))
504 return;
505
506 bool bCondition = (bool) scriptInstruction.First.Value;
507
508 InsertOptimiserInfo(iIndex, "Constant Conditional Jump");
509
510 OpCode opcodeJump = scriptInstruction.OpCode;
511
512 // IMPORTANT:
513 // JZ = "jump if condition is FALSE" (i.e. skip block when condition is false)
514 // JNZ = "jump if condition is TRUE"
515 // So with a constant boolean we can eliminate/replace the jump accordingly.
516 if ((opcodeJump == OpCode.JZ && !bCondition) || (opcodeJump == OpCode.JNZ && bCondition))
517 {
518 scriptInstruction.OpCode = OpCode.JMP;
519 scriptInstruction.First = scriptInstruction.Second;
520 scriptInstruction.Second = null;
521 }
522 else
523 {
524 scriptInstruction.OpCode = OpCode.NOP;
525 scriptInstruction.First = null;
526 scriptInstruction.Second = null;
527 }
528
529 done = false;
530 }
531
532 private void OptimiseIncrementsAndDecrements(int iIndex)
533 {
534
535 Instruction scriptInstruction
536 = executable.InstructionsInternal[iIndex];
537 if (scriptInstruction.OpCode != OpCode.ADD
538 && scriptInstruction.OpCode != OpCode.SUB) return;
539 if (scriptInstruction.First.Type != OperandType.Variable
540 && scriptInstruction.First.Type != OperandType.Member
541 && scriptInstruction.First.Type != OperandType.Pointer)
542 return;
543 if (scriptInstruction.Second.Type != OperandType.Literal) return;
544 object objectLiteral = scriptInstruction.Second.Value;
545 Type typeLiteral = objectLiteral.GetType();
546 if (typeLiteral != typeof(int) && typeLiteral != typeof(float)) return;
547 if (typeLiteral == typeof(int) && Math.Abs((int)objectLiteral) != 1) return;
548 if (typeLiteral == typeof(float) && Math.Abs((float)objectLiteral) != 1.0f) return;
549
550 InsertOptimiserInfo(iIndex, "Increment/Decrement Optimisation");
551
552 float fValue = 0.0f;
553
554 if (typeLiteral == typeof(int))
555 fValue = (float)(int)objectLiteral;
556 else
557 fValue = (float)objectLiteral;
558
559
560 OpCode opcodeOld = scriptInstruction.OpCode;
561 bool bIncrement = opcodeOld == OpCode.ADD && fValue > 0.0f
562 || opcodeOld == OpCode.SUB && fValue < 0.0f;
563
564 scriptInstruction.OpCode = bIncrement ? OpCode.INC : OpCode.DEC;
565 scriptInstruction.Second = null;
566
567 done = false;
568 }
569
570 private void OptimiseSingleInstructions(int iIndex)
571 {
572 EliminateSelfAssignments(iIndex);
573 OptimiseConstantConditionalJumps(iIndex);
574 OptimiseIncrementsAndDecrements(iIndex);
575 }
576
577 private void TraverseActiveInstructions(
578 Dictionary<Instruction, bool> dictScriptInstructionsActive,
579 int iNextInstuction)
580 {
581 while (true)
582 {
583 Instruction scriptInstruction
584 = executable.InstructionsInternal[iNextInstuction];
585 if (dictScriptInstructionsActive.ContainsKey(scriptInstruction))
586 return;
587
588 dictScriptInstructionsActive[scriptInstruction] = true;
589
590 switch (scriptInstruction.OpCode)
591 {
592 case OpCode.JMP:
593 iNextInstuction
594 = (int) scriptInstruction.First.InstructionPointer.Address;
595 break;
596 case OpCode.JZ:
597 case OpCode.JNZ:
598 TraverseActiveInstructions(dictScriptInstructionsActive,
599 (int)scriptInstruction.Second.InstructionPointer.Address);
600 ++iNextInstuction;
601 break;
602 case OpCode.CALL:
603 case OpCode.RUN:
604 TraverseActiveInstructions(dictScriptInstructionsActive,
605 (int)scriptInstruction.First.FunctionPointer.EntryPoint.Address);
606 ++iNextInstuction;
607 break;
608 case OpCode.RET:
609 return;
610 default:
611 ++iNextInstuction;
612 break;
613 }
614 }
615 }
616
617 private void EliminateDeadCode()
618 {
619 executable.Sort();
620
621 Dictionary<Instruction, bool> dictScriptInstructionsActive
622 = new Dictionary<Instruction, bool>();
623
624 foreach (Function scriptFunction in executable.Functions.Values)
625 {
626 TraverseActiveInstructions(dictScriptInstructionsActive,
627 (int) scriptFunction.EntryPoint.Address);
628 }
629
630 foreach (Instruction scriptInstruction in executable.InstructionsInternal)
631 {
632 if (scriptInstruction.OpCode == OpCode.DBG) continue;
633 if (scriptInstruction.OpCode == OpCode.DSB) continue;
634 if (scriptInstruction.OpCode == OpCode.DB) continue;
635
636 if (!dictScriptInstructionsActive.ContainsKey(scriptInstruction))
637 {
638 scriptInstruction.OpCode = OpCode.NOP;
639 scriptInstruction.First = null;
640 scriptInstruction.Second = null;
641
642 done = false;
643 }
644 }
645 }
646
647 private void EliminateUnusedTempVariables()
648 {
649 Dictionary<String, Instruction> dictTempVariableAssignments
650 = new Dictionary<string, Instruction>();
651
652 foreach (Instruction scriptInstruction in executable.InstructionsInternal)
653 {
654 OpCode opcode = scriptInstruction.OpCode;
655 if ((opcode == OpCode.MOV || opcode == OpCode.DC)
656 && IsTemporaryVariable(scriptInstruction.First))
657 {
658 dictTempVariableAssignments[scriptInstruction.First.Value.ToString()]
659 = scriptInstruction;
660 }
661
662 Operand operandDest = scriptInstruction.First;
663 if (operandDest == null) continue;
664 if (opcode != OpCode.MOV && IsTemporaryVariable(operandDest))
665 dictTempVariableAssignments.Remove(
666 operandDest.Value.ToString());
667 if ((operandDest.Type == OperandType.Member
668 || operandDest.Type == OperandType.Pointer)
669 && IsTemporaryVariable(operandDest.Value.ToString()))
670 dictTempVariableAssignments.Remove(
671 operandDest.Value.ToString());
672 if (operandDest.Type == OperandType.Pointer
673 && IsTemporaryVariable(operandDest.Pointer))
674 dictTempVariableAssignments.Remove(
675 operandDest.Pointer);
676 Operand operandSource = scriptInstruction.Second;
677 if (operandSource == null) continue;
678 switch (operandSource.Type)
679 {
680 case OperandType.Literal: continue;
681 case OperandType.Variable:
682 case OperandType.Member:
683 if (IsTemporaryVariable(operandSource.Value.ToString()))
684 dictTempVariableAssignments.Remove(
685 operandSource.Value.ToString());
686 break;
687 case OperandType.Pointer:
688 if (IsTemporaryVariable(operandSource.Value.ToString()))
689 dictTempVariableAssignments.Remove(
690 operandSource.Value.ToString());
691 if (IsTemporaryVariable(operandSource.Pointer))
692 dictTempVariableAssignments.Remove(
693 operandSource.Pointer);
694 break;
695 }
696 }
697 foreach (Instruction scriptInstruction
698 in dictTempVariableAssignments.Values)
699 {
700 String strOldInstruction = scriptInstruction.ToString();
701
702 scriptInstruction.OpCode = OpCode.NOP;
703 scriptInstruction.First = null;
704 scriptInstruction.Second = null;
705 }
706
707 if (dictTempVariableAssignments.Count > 0)
708 done = false;
709 }
710
711 #endregion
712
713 #region Public Methods
714
715 public Optimizer(Executable executable)
716 {
717
718 verbose = false;
719 this.executable = executable;
720
721 }
722
723 public void Optimize()
724 {
725
726 List<Instruction> instructions = executable.InstructionsInternal;
727
728 done = false;
729
730 while (!done)
731 {
732 done = true;
733
734 for (int i = 0; i < instructions.Count; i++)
735 {
736
737 if (Tripleinstruction(i))
738 OptimiseInstructionTriples(i);
739
740 if (DoubleInstruction(i))
741 OptimiseInstructionPairs(i);
742
743 OptimiseSingleInstructions(i);
744
745 executable.Clean();
746
747 }
748 }
749
750 EliminateUnusedTempVariables();
751
752 EliminateDeadCode();
753
754 executable.Clean();
755
756 }
757
758 public bool OptimizerInfo
759 {
760 get { return verbose; }
761 set { verbose = value; }
762 }
763
764 #endregion
765
766 }
767
768}
ScriptStack.Runtime.Operand.InstructionPointer
Instruction InstructionPointer
Definition Operand.cs:242
Generated by doxygen 1.15.0