Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(150)

Side by Side Diff: src/IceInst.cpp

Issue 652633002: Subzero: Improve performance of liveness analysis and live range construction. (Closed) Base URL: https://chromium.googlesource.com/native_client/pnacl-subzero.git@master
Patch Set: Remove TODO Created 6 years, 2 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch
« no previous file with comments | « src/IceInst.h ('k') | src/IceLiveness.h » ('j') | no next file with comments »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
OLDNEW
1 //===- subzero/src/IceInst.cpp - High-level instruction implementation ----===// 1 //===- subzero/src/IceInst.cpp - High-level instruction implementation ----===//
2 // 2 //
3 // The Subzero Code Generator 3 // The Subzero Code Generator
4 // 4 //
5 // This file is distributed under the University of Illinois Open Source 5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details. 6 // License. See LICENSE.TXT for details.
7 // 7 //
8 //===----------------------------------------------------------------------===// 8 //===----------------------------------------------------------------------===//
9 // 9 //
10 // This file implements the Inst class, primarily the various 10 // This file implements the Inst class, primarily the various
(...skipping 53 matching lines...) Expand 10 before | Expand all | Expand 10 after
64 { str } \ 64 { str } \
65 , 65 ,
66 ICEINSTICMP_TABLE 66 ICEINSTICMP_TABLE
67 #undef X 67 #undef X
68 }; 68 };
69 69
70 } // end of anonymous namespace 70 } // end of anonymous namespace
71 71
72 Inst::Inst(Cfg *Func, InstKind Kind, SizeT MaxSrcs, Variable *Dest) 72 Inst::Inst(Cfg *Func, InstKind Kind, SizeT MaxSrcs, Variable *Dest)
73 : Kind(Kind), Number(Func->newInstNumber()), Deleted(false), Dead(false), 73 : Kind(Kind), Number(Func->newInstNumber()), Deleted(false), Dead(false),
74 HasSideEffects(false), Dest(Dest), MaxSrcs(MaxSrcs), NumSrcs(0), 74 HasSideEffects(false), IsDestNonKillable(false), Dest(Dest),
75 MaxSrcs(MaxSrcs), NumSrcs(0),
75 Srcs(Func->allocateArrayOf<Operand *>(MaxSrcs)), LiveRangesEnded(0) {} 76 Srcs(Func->allocateArrayOf<Operand *>(MaxSrcs)), LiveRangesEnded(0) {}
76 77
77 // Assign the instruction a new number. 78 // Assign the instruction a new number.
78 void Inst::renumber(Cfg *Func) { 79 void Inst::renumber(Cfg *Func) {
79 Number = isDeleted() ? NumberDeleted : Func->newInstNumber(); 80 Number = isDeleted() ? NumberDeleted : Func->newInstNumber();
80 } 81 }
81 82
82 // Delete the instruction if its tentative Dead flag is still set 83 // Delete the instruction if its tentative Dead flag is still set
83 // after liveness analysis. 84 // after liveness analysis.
84 void Inst::deleteIfDead() { 85 void Inst::deleteIfDead() {
(...skipping 19 matching lines...) Expand all
104 } 105 }
105 Mask >>= 1; 106 Mask >>= 1;
106 if (Mask == 0) 107 if (Mask == 0)
107 return false; // another early-exit optimization 108 return false; // another early-exit optimization
108 } 109 }
109 } 110 }
110 } 111 }
111 return false; 112 return false;
112 } 113 }
113 114
114 void Inst::livenessLightweight(Cfg *Func, llvm::BitVector &Live) { 115 void Inst::livenessLightweight(Cfg *Func, LivenessBV &Live) {
115 assert(!isDeleted()); 116 assert(!isDeleted());
116 if (llvm::isa<InstFakeKill>(this)) 117 if (llvm::isa<InstFakeKill>(this))
117 return; 118 return;
118 resetLastUses(); 119 resetLastUses();
120 VariablesMetadata *VMetadata = Func->getVMetadata();
119 SizeT VarIndex = 0; 121 SizeT VarIndex = 0;
120 for (SizeT I = 0; I < getSrcSize(); ++I) { 122 for (SizeT I = 0; I < getSrcSize(); ++I) {
121 Operand *Src = getSrc(I); 123 Operand *Src = getSrc(I);
122 SizeT NumVars = Src->getNumVars(); 124 SizeT NumVars = Src->getNumVars();
123 for (SizeT J = 0; J < NumVars; ++J, ++VarIndex) { 125 for (SizeT J = 0; J < NumVars; ++J, ++VarIndex) {
124 const Variable *Var = Src->getVar(J); 126 const Variable *Var = Src->getVar(J);
125 if (Func->getVMetadata()->isMultiBlock(Var)) 127 if (VMetadata->isMultiBlock(Var))
126 continue; 128 continue;
127 SizeT Index = Var->getIndex(); 129 SizeT Index = Var->getIndex();
128 if (Live[Index]) 130 if (Live[Index])
129 continue; 131 continue;
130 Live[Index] = true; 132 Live[Index] = true;
131 setLastUse(VarIndex); 133 setLastUse(VarIndex);
132 } 134 }
133 } 135 }
134 } 136 }
135 137
136 void Inst::liveness(InstNumberT InstNumber, llvm::BitVector &Live, 138 void Inst::liveness(InstNumberT InstNumber, LivenessBV &Live,
137 Liveness *Liveness, const CfgNode *Node) { 139 Liveness *Liveness, LiveBeginEndMap *LiveBegin,
140 LiveBeginEndMap *LiveEnd) {
138 assert(!isDeleted()); 141 assert(!isDeleted());
139 if (llvm::isa<InstFakeKill>(this)) 142 if (llvm::isa<InstFakeKill>(this))
140 return; 143 return;
141 144
142 std::vector<InstNumberT> &LiveBegin = Liveness->getLiveBegin(Node);
143 std::vector<InstNumberT> &LiveEnd = Liveness->getLiveEnd(Node);
144 Dead = false; 145 Dead = false;
145 if (Dest) { 146 if (Dest) {
146 SizeT VarNum = Liveness->getLiveIndex(Dest); 147 SizeT VarNum = Liveness->getLiveIndex(Dest->getIndex());
147 if (Live[VarNum]) { 148 if (Live[VarNum]) {
148 Live[VarNum] = false; 149 if (!isDestNonKillable()) {
149 LiveBegin[VarNum] = InstNumber; 150 Live[VarNum] = false;
151 if (LiveBegin) {
152 LiveBegin->push_back(std::make_pair(VarNum, InstNumber));
153 }
154 }
150 } else { 155 } else {
151 if (!hasSideEffects()) 156 if (!hasSideEffects())
152 Dead = true; 157 Dead = true;
153 } 158 }
154 } 159 }
155 if (Dead) 160 if (Dead)
156 return; 161 return;
157 // Phi arguments only get added to Live in the predecessor node, but 162 // Phi arguments only get added to Live in the predecessor node, but
158 // we still need to update LiveRangesEnded. 163 // we still need to update LiveRangesEnded.
159 bool IsPhi = llvm::isa<InstPhi>(this); 164 bool IsPhi = llvm::isa<InstPhi>(this);
160 resetLastUses(); 165 resetLastUses();
161 SizeT VarIndex = 0; 166 SizeT VarIndex = 0;
162 for (SizeT I = 0; I < getSrcSize(); ++I) { 167 for (SizeT I = 0; I < getSrcSize(); ++I) {
163 Operand *Src = getSrc(I); 168 Operand *Src = getSrc(I);
164 SizeT NumVars = Src->getNumVars(); 169 SizeT NumVars = Src->getNumVars();
165 for (SizeT J = 0; J < NumVars; ++J, ++VarIndex) { 170 for (SizeT J = 0; J < NumVars; ++J, ++VarIndex) {
166 const Variable *Var = Src->getVar(J); 171 const Variable *Var = Src->getVar(J);
167 SizeT VarNum = Liveness->getLiveIndex(Var); 172 SizeT VarNum = Liveness->getLiveIndex(Var->getIndex());
168 if (!Live[VarNum]) { 173 if (!Live[VarNum]) {
169 setLastUse(VarIndex); 174 setLastUse(VarIndex);
170 if (!IsPhi) { 175 if (!IsPhi) {
171 Live[VarNum] = true; 176 Live[VarNum] = true;
172 // For a variable in SSA form, its live range can end at 177 // For a variable in SSA form, its live range can end at
173 // most once in a basic block. However, after lowering to 178 // most once in a basic block. However, after lowering to
174 // two-address instructions, we end up with sequences like 179 // two-address instructions, we end up with sequences like
175 // "t=b;t+=c;a=t" where t's live range begins and ends 180 // "t=b;t+=c;a=t" where t's live range begins and ends
176 // twice. ICE only allows a variable to have a single 181 // twice. ICE only allows a variable to have a single
177 // liveness interval in a basic block (except for blocks 182 // liveness interval in a basic block (except for blocks
178 // where a variable is live-in and live-out but there is a 183 // where a variable is live-in and live-out but there is a
179 // gap in the middle, and except for the special 184 // gap in the middle, and except for the special
180 // InstFakeKill instruction that can appear multiple 185 // InstFakeKill instruction that can appear multiple
181 // times in the same block). Therefore, this lowered 186 // times in the same block). Therefore, this lowered
182 // sequence needs to represent a single conservative live 187 // sequence needs to represent a single conservative live
183 // range for t. Since the instructions are being traversed 188 // range for t. Since the instructions are being traversed
184 // backwards, we make sure LiveEnd is only set once by 189 // backwards, we make sure LiveEnd is only set once by
185 // setting it only when LiveEnd[VarNum]==0 (sentinel value). 190 // setting it only when LiveEnd[VarNum]==0 (sentinel value).
186 // Note that it's OK to set LiveBegin multiple times because 191 // Note that it's OK to set LiveBegin multiple times because
187 // of the backwards traversal. 192 // of the backwards traversal.
188 if (LiveEnd[VarNum] == 0) { 193 if (LiveEnd) {
189 LiveEnd[VarNum] = InstNumber; 194 // Ideally, we would verify that VarNum wasn't already
195 // added in this block, but this can't be done very
196 // efficiently with LiveEnd as a vector. Instead,
197 // livenessPostprocess() verifies this after the vector
198 // has been sorted.
199 LiveEnd->push_back(std::make_pair(VarNum, InstNumber));
190 } 200 }
191 } 201 }
192 } 202 }
193 } 203 }
194 } 204 }
195 } 205 }
196 206
197 InstAlloca::InstAlloca(Cfg *Func, Operand *ByteCount, uint32_t AlignInBytes, 207 InstAlloca::InstAlloca(Cfg *Func, Operand *ByteCount, uint32_t AlignInBytes,
198 Variable *Dest) 208 Variable *Dest)
199 : InstHighLevel(Func, Inst::Alloca, 1, Dest), AlignInBytes(AlignInBytes) { 209 : InstHighLevel(Func, Inst::Alloca, 1, Dest), AlignInBytes(AlignInBytes) {
(...skipping 113 matching lines...) Expand 10 before | Expand all | Expand 10 after
313 if (Labels[I] == Target) 323 if (Labels[I] == Target)
314 return getSrc(I); 324 return getSrc(I);
315 } 325 }
316 llvm_unreachable("Phi target not found"); 326 llvm_unreachable("Phi target not found");
317 return NULL; 327 return NULL;
318 } 328 }
319 329
320 // Updates liveness for a particular operand based on the given 330 // Updates liveness for a particular operand based on the given
321 // predecessor edge. Doesn't mark the operand as live if the Phi 331 // predecessor edge. Doesn't mark the operand as live if the Phi
322 // instruction is dead or deleted. 332 // instruction is dead or deleted.
323 void InstPhi::livenessPhiOperand(llvm::BitVector &Live, CfgNode *Target, 333 void InstPhi::livenessPhiOperand(LivenessBV &Live, CfgNode *Target,
324 Liveness *Liveness) { 334 Liveness *Liveness) {
325 if (isDeleted() || Dead) 335 if (isDeleted() || Dead)
326 return; 336 return;
327 for (SizeT I = 0; I < getSrcSize(); ++I) { 337 for (SizeT I = 0; I < getSrcSize(); ++I) {
328 if (Labels[I] == Target) { 338 if (Labels[I] == Target) {
329 if (Variable *Var = llvm::dyn_cast<Variable>(getSrc(I))) { 339 if (Variable *Var = llvm::dyn_cast<Variable>(getSrc(I))) {
330 SizeT SrcIndex = Liveness->getLiveIndex(Var); 340 SizeT SrcIndex = Liveness->getLiveIndex(Var->getIndex());
331 if (!Live[SrcIndex]) { 341 if (!Live[SrcIndex]) {
332 setLastUse(I); 342 setLastUse(I);
333 Live[SrcIndex] = true; 343 Live[SrcIndex] = true;
334 } 344 }
335 } 345 }
336 return; 346 return;
337 } 347 }
338 } 348 }
339 llvm_unreachable("Phi operand not found for specified target node"); 349 llvm_unreachable("Phi operand not found for specified target node");
340 } 350 }
(...skipping 400 matching lines...) Expand 10 before | Expand all | Expand 10 after
741 dumpSources(Func); 751 dumpSources(Func);
742 } 752 }
743 753
744 void InstTarget::dump(const Cfg *Func) const { 754 void InstTarget::dump(const Cfg *Func) const {
745 Ostream &Str = Func->getContext()->getStrDump(); 755 Ostream &Str = Func->getContext()->getStrDump();
746 Str << "[TARGET] "; 756 Str << "[TARGET] ";
747 Inst::dump(Func); 757 Inst::dump(Func);
748 } 758 }
749 759
750 } // end of namespace Ice 760 } // end of namespace Ice
OLDNEW
« no previous file with comments | « src/IceInst.h ('k') | src/IceLiveness.h » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698