1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
|
using System;
using System.Collections.Generic;
using System.Diagnostics;
namespace Ryujinx.Cpu.LightningJit.CodeGen.Arm64
{
class TailMerger
{
private enum BranchType
{
Conditional,
Unconditional,
}
private readonly List<(BranchType, int)> _branchPointers;
public TailMerger()
{
_branchPointers = new();
}
public void AddConditionalReturn(CodeWriter writer, in Assembler asm, ArmCondition returnCondition)
{
_branchPointers.Add((BranchType.Conditional, writer.InstructionPointer));
asm.B(returnCondition, 0);
}
public void AddConditionalZeroReturn(CodeWriter writer, in Assembler asm, Operand value)
{
_branchPointers.Add((BranchType.Conditional, writer.InstructionPointer));
asm.Cbz(value, 0);
}
public void AddUnconditionalReturn(CodeWriter writer, in Assembler asm)
{
_branchPointers.Add((BranchType.Unconditional, writer.InstructionPointer));
asm.B(0);
}
public void WriteReturn(CodeWriter writer, Action writeEpilogue)
{
if (_branchPointers.Count == 0)
{
return;
}
int targetIndex = writer.InstructionPointer;
int startIndex = _branchPointers.Count - 1;
if (startIndex >= 0 &&
_branchPointers[startIndex].Item1 == BranchType.Unconditional &&
_branchPointers[startIndex].Item2 == targetIndex - 1)
{
// Remove the last branch if it is redundant.
writer.RemoveLastInstruction();
startIndex--;
targetIndex--;
}
Assembler asm = new(writer);
writeEpilogue();
asm.Ret();
for (int i = startIndex; i >= 0; i--)
{
(BranchType type, int branchIndex) = _branchPointers[i];
uint encoding = writer.ReadInstructionAt(branchIndex);
int delta = targetIndex - branchIndex;
if (type == BranchType.Conditional)
{
uint branchMask = 0x7ffff;
int branchMax = (int)(branchMask + 1) / 2;
if (delta >= -branchMax && delta < branchMax)
{
writer.WriteInstructionAt(branchIndex, (encoding & ~(branchMask << 5)) | (uint)((delta & branchMask) << 5));
}
else
{
// If the branch target is too far away, we use a regular unconditional branch
// instruction instead which has a much higher range.
// We branch directly to the end of the function, where we put the conditional branch,
// and then branch back to the next instruction or return the branch target depending
// on the branch being taken or not.
delta = writer.InstructionPointer - branchIndex;
uint branchInst = 0x14000000u | ((uint)delta & 0x3ffffff);
Debug.Assert(ExtractSImm26Times4(branchInst) == delta * 4);
writer.WriteInstructionAt(branchIndex, branchInst);
int movedBranchIndex = writer.InstructionPointer;
writer.WriteInstruction(0u); // Placeholder
asm.B((branchIndex + 1 - writer.InstructionPointer) * 4);
delta = targetIndex - movedBranchIndex;
writer.WriteInstructionAt(movedBranchIndex, (encoding & ~(branchMask << 5)) | (uint)((delta & branchMask) << 5));
}
}
else
{
Debug.Assert(type == BranchType.Unconditional);
writer.WriteInstructionAt(branchIndex, (encoding & ~0x3ffffffu) | (uint)(delta & 0x3ffffff));
}
}
}
private static int ExtractSImm26Times4(uint encoding)
{
return (int)(encoding << 6) >> 4;
}
}
}
|
