/
MemoryAccessElimination.cs
129 lines (119 loc) · 5.58 KB
/
MemoryAccessElimination.cs
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
121
122
123
124
125
126
127
128
129
using System.Collections.Generic;
using Flame.Compiler.Analysis;
using Flame.Compiler.Instructions;
namespace Flame.Compiler.Transforms
{
/// <summary>
/// A pass that tries to eliminate loads and stores, replacing them with
/// local value copies instead.
/// </summary>
public sealed class MemoryAccessElimination : IntraproceduralOptimization
{
private MemoryAccessElimination()
{ }
/// <summary>
/// An instance of the memory access elimination pass.
/// </summary>
public static readonly MemoryAccessElimination Instance
= new MemoryAccessElimination();
/// <inheritdoc/>
public override FlowGraph Apply(FlowGraph graph)
{
var memSSA = graph.GetAnalysisResult<MemorySSA>();
var aliasing = graph.GetAnalysisResult<AliasAnalysisResult>();
var effectfulness = graph.GetAnalysisResult<EffectfulInstructions>();
var builder = graph.ToBuilder();
// First try and eliminate loads and stores based on their memory SSA
// states.
foreach (var instruction in builder.NamedInstructions)
{
var proto = instruction.Prototype;
if (proto is LoadPrototype)
{
// Loads can be eliminated if we know the memory contents.
var loadProto = (LoadPrototype)proto;
var state = memSSA.GetMemoryAfter(instruction);
ValueTag value;
if (state.TryGetValueAt(
loadProto.GetPointer(instruction.Instruction),
graph,
out value))
{
instruction.Instruction = Instruction.CreateCopy(
instruction.ResultType,
value);
}
}
else if (proto is StorePrototype)
{
// Stores can be eliminated if they don't affect the memory state.
var storeProto = (StorePrototype)proto;
var stateBefore = memSSA.GetMemoryBefore(instruction);
var stateAfter = memSSA.GetMemoryAfter(instruction);
if (stateBefore == stateAfter)
{
EliminateStore(instruction);
}
}
}
// Then try to coalesce stores by iterating through basic blocks.
foreach (var block in builder.BasicBlocks)
{
var pendingStores = new List<NamedInstructionBuilder>();
foreach (var instruction in block.NamedInstructions)
{
var proto = instruction.Prototype;
if (proto is StorePrototype)
{
var storeProto = (StorePrototype)proto;
var pointer = storeProto.GetPointer(instruction.Instruction);
var newPending = new List<NamedInstructionBuilder>();
foreach (var pending in pendingStores)
{
var pendingProto = (StorePrototype)pending.Prototype;
var pendingPointer = pendingProto.GetPointer(pending.Instruction);
var aliasState = aliasing.GetAliasing(pointer, pendingPointer);
if (aliasState == Aliasing.MustAlias)
{
// Yes, do it. Delete the pending store.
EliminateStore(pending);
}
else if (aliasState == Aliasing.NoAlias)
{
// We can't eliminate the pending store, but we can keep it
// in the pending list.
newPending.Add(pending);
}
}
pendingStores = newPending;
// Add this store to the list of pending stores as well.
pendingStores.Add(instruction);
}
else if (proto is LoadPrototype || proto is CopyPrototype)
{
// Loads are perfectly benign. They *may* be effectful in the sense
// that they can trigger a segfault and make the program blow up, but
// there's no way we can catch that anyway. We'll just allow store
// coalescing across load boundaries.
//
// We also want to test for copy instructions here because our effectfulness
// analysis is slightly outdated and we may have turned loads/stores into copies.
}
else if (effectfulness.Instructions.Contains(instruction))
{
// Effectful instructions are a barrier for store coalescing.
pendingStores.Clear();
}
}
}
return builder.ToImmutable();
}
private void EliminateStore(NamedInstructionBuilder instruction)
{
var storeProto = (StorePrototype)instruction.Prototype;
instruction.Instruction = Instruction.CreateCopy(
instruction.ResultType,
storeProto.GetValue(instruction.Instruction));
}
}
}