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
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
|
//===-- AllocaManager.h ---------------------------------------------------===//
//
// The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This pass declares the AllocaManager class.
//
//===----------------------------------------------------------------------===//
#ifndef JSBACKEND_ALLOCAMANAGER_H
#define JSBACKEND_ALLOCAMANAGER_H
#include "llvm/ADT/BitVector.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/SetVector.h"
namespace llvm {
class AllocaInst;
class BasicBlock;
class CallInst;
class DataLayout;
class Function;
/// Compute frame layout for allocas.
class AllocaManager {
const DataLayout *DL;
const Function *LifetimeStart;
const Function *LifetimeEnd;
const Function *F;
// Per-block lifetime information.
struct BlockLifetimeInfo {
BitVector Start;
BitVector End;
BitVector LiveIn;
BitVector LiveOut;
};
typedef DenseMap<const BasicBlock *, BlockLifetimeInfo> LivenessMap;
LivenessMap BlockLiveness;
// Worklist for inter-block liveness analysis.
typedef SmallSetVector<const BasicBlock *, 8> InterBlockWorklistVec;
InterBlockWorklistVec InterBlockTopDownWorklist;
InterBlockWorklistVec InterBlockBottomUpWorklist;
// Map allocas to their index in AllocasByIndex.
typedef DenseMap<const AllocaInst *, size_t> AllocaMap;
AllocaMap Allocas;
// Information about an alloca. Note that the size and alignment may vary
// from what's in the actual AllocaInst when an alloca is also representing
// another with perhaps greater size and/or alignment needs.
//
// When an alloca is represented by another, its AllocaInfo is marked as
// "forwarded", at which point it no longer holds a size and alignment, but
// the index of the representative AllocaInfo.
class AllocaInfo {
const AllocaInst *Inst;
uint64_t Size;
unsigned Alignment;
public:
AllocaInfo(const AllocaInst *I, uint64_t S, unsigned A)
: Inst(I), Size(S), Alignment(A) {
assert(I != NULL);
assert(A != 0);
assert(!isForwarded());
}
bool isForwarded() const { return Alignment == 0; }
size_t getForwardedID() const {
assert(isForwarded());
return static_cast<size_t>(Size);
}
void forward(size_t i) {
assert(!isForwarded());
Alignment = 0;
Size = i;
assert(isForwarded());
assert(getForwardedID() == i);
}
const AllocaInst *getInst() const { return Inst; }
uint64_t getSize() const { assert(!isForwarded()); return Size; }
unsigned getAlignment() const { assert(!isForwarded()); return Alignment; }
void mergeSize(uint64_t S) {
assert(!isForwarded());
Size = std::max(Size, S);
assert(!isForwarded());
}
void mergeAlignment(unsigned A) {
assert(A != 0);
assert(!isForwarded());
Alignment = std::max(Alignment, A);
assert(!isForwarded());
}
};
typedef SmallVector<AllocaInfo, 32> AllocaVec;
AllocaVec AllocasByIndex;
// For each alloca, which allocas can it safely represent? Allocas are
// identified by AllocasByIndex index.
// TODO: Vector-of-vectors isn't the fastest data structure possible here.
typedef SmallVector<BitVector, 32> AllocaCompatibilityVec;
AllocaCompatibilityVec AllocaCompatibility;
// This is for allocas that will eventually be sorted.
SmallVector<AllocaInfo, 32> SortedAllocas;
// Static allocation results.
struct StaticAllocation {
const AllocaInst *Representative;
uint64_t Offset;
StaticAllocation() {}
StaticAllocation(const AllocaInst *A, uint64_t O)
: Representative(A), Offset(O) {}
};
typedef DenseMap<const AllocaInst *, StaticAllocation> StaticAllocaMap;
StaticAllocaMap StaticAllocas;
uint64_t FrameSize;
uint64_t getSize(const AllocaInst *AI);
unsigned getAlignment(const AllocaInst *AI);
AllocaInfo getInfo(const AllocaInst *AI);
const AllocaInst *getAllocaFromIntrinsic(const CallInst *CI);
static int AllocaSort(const void *l, const void *r);
void collectMarkedAllocas();
void collectBlocks();
void computeInterBlockLiveness();
void computeIntraBlockLiveness();
void computeRepresentatives();
void computeFrameOffsets();
public:
AllocaManager();
/// Analyze the given function and prepare for getRepresentative queries.
void analyze(const Function &Func, const DataLayout &Layout,
bool PerformColoring);
/// Reset all stored state.
void clear();
/// Return the representative alloca for the given alloca. When allocas are
/// merged, one is chosen as the representative to stand for the rest.
/// References to the alloca should take the form of references to the
/// representative.
const AllocaInst *getRepresentative(const AllocaInst *AI) const;
/// Set *offset to the frame offset for the given alloca. Return true if the
/// given alloca is representative, meaning that it needs an explicit
/// definition in the function entry. Return false if some other alloca
/// represents this one.
bool getFrameOffset(const AllocaInst *AI, uint64_t *offset) const;
/// Return the total frame size for all static allocas and associated padding.
uint64_t getFrameSize() const { return FrameSize; }
};
} // namespace llvm
#endif
|
