OSDN -- オープンソース・ソフトウェアの開発とダウンロード
日本語の翻訳状況 translation status for ja

Android-x86
Fork

  • R/O
  • HTTP
  • SSH
  • HTTPS
Fork

external-swiftshader: コミット

external/swiftshader


コミットメタ情報

リビジョン932640b2d9cd2611ff60907a3d3d1ba0ad966c14 (tree)
日時2018-06-23 03:25:25
作者Alexis Hetu <sugoi@goog...>
コミッターAlexis Hétu

ログメッセージ

Std:unordered_map removed from Optimizer for improved performance

The use of std::unordered_map was the main source of slowdowns in
the optimizer code, so it was re-written without any maps. In order
to do so, the information originally carried by the maps was moved
to user-defined information stored within Subzero classes. The
optimizer now manages the memory used to store this information.

Bug swiftshader:69
Bug b/67872293

Change-Id: I2757169f0d3d467766317af6e00e149b4317fb9c
Reviewed-on: https://swiftshader-review.googlesource.com/19508
Tested-by: Alexis Hétu <sugoi@google.com>
Reviewed-by: Nicolas Capens <nicolascapens@google.com>

変更サマリ

差分

--- a/src/Reactor/Optimizer.cpp
+++ b/src/Reactor/Optimizer.cpp
@@ -17,7 +17,6 @@
1717 #include "src/IceCfg.h"
1818 #include "src/IceCfgNode.h"
1919
20-#include <unordered_map>
2120 #include <vector>
2221
2322 namespace
@@ -61,9 +60,35 @@ namespace
6160 std::vector<Ice::Inst*> stores;
6261 };
6362
64- std::unordered_map<Ice::Operand*, Uses> uses;
65- std::unordered_map<Ice::Inst*, Ice::CfgNode*> node;
66- std::unordered_map<Ice::Variable*, Ice::Inst*> definition;
63+ struct LoadStoreInst
64+ {
65+ LoadStoreInst(Ice::Inst* inst, bool isStore)
66+ : inst(inst),
67+ address(isStore ? storeAddress(inst) : loadAddress(inst)),
68+ isStore(isStore)
69+ {
70+ }
71+
72+ Ice::Inst* inst;
73+ Ice::Operand *address;
74+ bool isStore;
75+ };
76+
77+ Optimizer::Uses* getUses(Ice::Operand*);
78+ void setUses(Ice::Operand*, Optimizer::Uses*);
79+ bool hasUses(Ice::Operand*) const;
80+
81+ Ice::CfgNode* getNode(Ice::Inst*);
82+ void setNode(Ice::Inst*, Ice::CfgNode*);
83+
84+ Ice::Inst* getDefinition(Ice::Variable*);
85+ void setDefinition(Ice::Variable*, Ice::Inst*);
86+
87+ const std::vector<LoadStoreInst>& getLoadStoreInsts(Ice::CfgNode*);
88+ void setLoadStoreInsts(Ice::CfgNode*, std::vector<LoadStoreInst>*);
89+ bool hasLoadStoreInsts(Ice::CfgNode* node) const;
90+
91+ std::vector<Optimizer::Uses*> allocatedUses;
6792 };
6893
6994 void Optimizer::run(Ice::Cfg *function)
@@ -78,6 +103,12 @@ namespace
78103 eliminateLoadsFollowingSingleStore();
79104 optimizeStoresInSingleBasicBlock();
80105 eliminateDeadCode();
106+
107+ for(auto uses : allocatedUses)
108+ {
109+ delete uses;
110+ }
111+ allocatedUses.clear();
81112 }
82113
83114 void Optimizer::eliminateDeadCode()
@@ -123,8 +154,13 @@ namespace
123154 }
124155
125156 Ice::Operand *address = alloca.getDest();
126- const auto &addressEntry = uses.find(address);
127- const auto &addressUses = addressEntry->second;
157+
158+ if(!hasUses(address))
159+ {
160+ return;
161+ }
162+
163+ const auto &addressUses = *getUses(address);
128164
129165 if(!addressUses.areOnlyLoadStore())
130166 {
@@ -137,26 +173,29 @@ namespace
137173 {
138174 Ice::Variable *loadData = load->getDest();
139175
140- for(Ice::Inst *use : uses[loadData])
176+ if(hasUses(loadData))
141177 {
142- for(Ice::SizeT i = 0; i < use->getSrcSize(); i++)
178+ for(Ice::Inst *use : *getUses(loadData))
143179 {
144- if(use->getSrc(i) == loadData)
180+ for(Ice::SizeT i = 0; i < use->getSrcSize(); i++)
145181 {
146- auto *undef = context->getConstantUndef(loadData->getType());
182+ if(use->getSrc(i) == loadData)
183+ {
184+ auto *undef = context->getConstantUndef(loadData->getType());
147185
148- use->replaceSource(i, undef);
186+ use->replaceSource(i, undef);
187+ }
149188 }
150189 }
151- }
152190
153- uses.erase(loadData);
191+ setUses(loadData, nullptr);
192+ }
154193
155194 load->setDeleted();
156195 }
157196
158197 alloca.setDeleted();
159- uses.erase(addressEntry);
198+ setUses(address, nullptr);
160199 }
161200 }
162201 }
@@ -178,8 +217,13 @@ namespace
178217 }
179218
180219 Ice::Operand *address = alloca.getDest();
181- const auto &addressEntry = uses.find(address);
182- auto &addressUses = addressEntry->second;
220+
221+ if(!hasUses(address))
222+ {
223+ return;
224+ }
225+
226+ auto &addressUses = *getUses(address);
183227
184228 if(!addressUses.areOnlyLoadStore())
185229 {
@@ -236,23 +280,26 @@ namespace
236280
237281 alloca.setDeleted();
238282 store->setDeleted();
239- uses.erase(address);
240-
241- auto &valueUses = uses[storeValue];
283+ setUses(address, nullptr);
242284
243- for(size_t i = 0; i < valueUses.size(); i++)
285+ if(hasUses(storeValue))
244286 {
245- if(valueUses[i] == store)
287+ auto &valueUses = *getUses(storeValue);
288+
289+ for(size_t i = 0; i < valueUses.size(); i++)
246290 {
247- valueUses[i] = valueUses.back();
248- valueUses.pop_back();
249- break;
291+ if(valueUses[i] == store)
292+ {
293+ valueUses[i] = valueUses.back();
294+ valueUses.pop_back();
295+ break;
296+ }
250297 }
251- }
252298
253- if(valueUses.empty())
254- {
255- uses.erase(storeValue);
299+ if(valueUses.empty())
300+ {
301+ setUses(storeValue, nullptr);
302+ }
256303 }
257304
258305 break;
@@ -266,21 +313,7 @@ namespace
266313 {
267314 Ice::CfgNode *entryBlock = function->getEntryNode();
268315
269- struct LoadStoreInst
270- {
271- LoadStoreInst(Ice::Inst* inst, bool isStore)
272- : inst(inst),
273- address(isStore ? storeAddress(inst) : loadAddress(inst)),
274- isStore(isStore)
275- {
276- }
277-
278- Ice::Inst* inst;
279- Ice::Operand *address;
280- bool isStore;
281- };
282-
283- std::unordered_map<Ice::CfgNode*, std::vector<LoadStoreInst> > loadStoreMap;
316+ std::vector<std::vector<LoadStoreInst>* > allocatedVectors;
284317
285318 for(Ice::Inst &alloca : entryBlock->getInsts())
286319 {
@@ -295,20 +328,25 @@ namespace
295328 }
296329
297330 Ice::Operand *address = alloca.getDest();
298- const auto &addressEntry = uses.find(address);
299- const auto &addressUses = addressEntry->second;
331+
332+ if(!hasUses(address))
333+ {
334+ return;
335+ }
336+
337+ const auto &addressUses = *getUses(address);
300338
301339 if(!addressUses.areOnlyLoadStore())
302340 {
303341 continue;
304342 }
305343
306- Ice::CfgNode *singleBasicBlock = node[addressUses.stores[0]];
344+ Ice::CfgNode *singleBasicBlock = getNode(addressUses.stores[0]);
307345
308346 for(size_t i = 1; i < addressUses.stores.size(); i++)
309347 {
310348 Ice::Inst *store = addressUses.stores[i];
311- if(node[store] != singleBasicBlock)
349+ if(getNode(store) != singleBasicBlock)
312350 {
313351 singleBasicBlock = nullptr;
314352 break;
@@ -317,9 +355,11 @@ namespace
317355
318356 if(singleBasicBlock)
319357 {
320- if(loadStoreMap.find(singleBasicBlock) == loadStoreMap.end())
358+ if(!hasLoadStoreInsts(singleBasicBlock))
321359 {
322- std::vector<LoadStoreInst> &loadStoreVector = loadStoreMap[singleBasicBlock];
360+ std::vector<LoadStoreInst>* loadStoreInstVector = new std::vector<LoadStoreInst>();
361+ setLoadStoreInsts(singleBasicBlock, loadStoreInstVector);
362+ allocatedVectors.push_back(loadStoreInstVector);
323363 for(Ice::Inst &inst : singleBasicBlock->getInsts())
324364 {
325365 if(inst.isDeleted())
@@ -332,7 +372,7 @@ namespace
332372
333373 if(isStoreInst || isLoadInst)
334374 {
335- loadStoreVector.push_back(LoadStoreInst(&inst, isStoreInst));
375+ loadStoreInstVector->push_back(LoadStoreInst(&inst, isStoreInst));
336376 }
337377 }
338378 }
@@ -341,7 +381,7 @@ namespace
341381 Ice::Operand *storeValue = nullptr;
342382 bool unmatchedLoads = false;
343383
344- for (auto& loadStoreInst : loadStoreMap[singleBasicBlock])
384+ for (auto& loadStoreInst : getLoadStoreInsts(singleBasicBlock))
345385 {
346386 Ice::Inst* inst = loadStoreInst.inst;
347387
@@ -380,14 +420,15 @@ namespace
380420 }
381421 }
382422 }
423+
424+ for(auto loadStoreInstVector : allocatedVectors)
425+ {
426+ delete loadStoreInstVector;
427+ }
383428 }
384429
385430 void Optimizer::analyzeUses(Ice::Cfg *function)
386431 {
387- uses.clear();
388- node.clear();
389- definition.clear();
390-
391432 for(Ice::CfgNode *basicBlock : function->getNodes())
392433 {
393434 for(Ice::Inst &instruction : basicBlock->getInsts())
@@ -397,8 +438,11 @@ namespace
397438 continue;
398439 }
399440
400- node[&instruction] = basicBlock;
401- definition[instruction.getDest()] = &instruction;
441+ setNode(&instruction, basicBlock);
442+ if(instruction.getDest())
443+ {
444+ setDefinition(instruction.getDest(), &instruction);
445+ }
402446
403447 for(Ice::SizeT i = 0; i < instruction.getSrcSize(); i++)
404448 {
@@ -414,7 +458,7 @@ namespace
414458 if(i == unique)
415459 {
416460 Ice::Operand *src = instruction.getSrc(i);
417- uses[src].insert(src, &instruction);
461+ getUses(src)->insert(src, &instruction);
418462 }
419463 }
420464 }
@@ -430,23 +474,26 @@ namespace
430474 newValue = context->getConstantUndef(oldValue->getType());
431475 }
432476
433- for(Ice::Inst *use : uses[oldValue])
477+ if(hasUses(oldValue))
434478 {
435- assert(!use->isDeleted()); // Should have been removed from uses already
436-
437- for(Ice::SizeT i = 0; i < use->getSrcSize(); i++)
479+ for(Ice::Inst *use : *getUses(oldValue))
438480 {
439- if(use->getSrc(i) == oldValue)
481+ assert(!use->isDeleted()); // Should have been removed from uses already
482+
483+ for(Ice::SizeT i = 0; i < use->getSrcSize(); i++)
440484 {
441- use->replaceSource(i, newValue);
485+ if(use->getSrc(i) == oldValue)
486+ {
487+ use->replaceSource(i, newValue);
488+ }
442489 }
490+
491+ getUses(newValue)->insert(newValue, use);
443492 }
444493
445- uses[newValue].insert(newValue, use);
494+ setUses(oldValue, nullptr);
446495 }
447496
448- uses.erase(oldValue);
449-
450497 deleteInstruction(instruction);
451498 }
452499
@@ -463,21 +510,19 @@ namespace
463510 {
464511 Ice::Operand *src = instruction->getSrc(i);
465512
466- const auto &srcEntry = uses.find(src);
467-
468- if(srcEntry != uses.end())
513+ if(hasUses(src))
469514 {
470- auto &srcUses = srcEntry->second;
515+ auto &srcUses = *getUses(src);
471516
472517 srcUses.erase(instruction);
473518
474519 if(srcUses.empty())
475520 {
476- uses.erase(srcEntry);
521+ setUses(src, nullptr);
477522
478523 if(Ice::Variable *var = llvm::dyn_cast<Ice::Variable>(src))
479524 {
480- deleteInstruction(definition[var]);
525+ deleteInstruction(getDefinition(var));
481526 }
482527 }
483528 }
@@ -490,17 +535,25 @@ namespace
490535
491536 if(dest)
492537 {
493- return uses[dest].empty() && !instruction->hasSideEffects();
538+ return (!hasUses(dest) || getUses(dest)->empty()) && !instruction->hasSideEffects();
494539 }
495540 else if(isStore(*instruction))
496541 {
497542 if(Ice::Variable *address = llvm::dyn_cast<Ice::Variable>(storeAddress(instruction)))
498543 {
499- Ice::Inst *def = definition[address];
544+ Ice::Inst *def = getDefinition(address);
500545
501546 if(def && llvm::isa<Ice::InstAlloca>(def))
502547 {
503- return uses[address].size() == uses[address].stores.size(); // Dead if all uses are stores
548+ if(hasUses(address))
549+ {
550+ Optimizer::Uses* uses = getUses(address);
551+ return uses->size() == uses->stores.size(); // Dead if all uses are stores
552+ }
553+ else
554+ {
555+ return true; // No uses
556+ }
504557 }
505558 }
506559 }
@@ -654,6 +707,63 @@ namespace
654707 return false;
655708 }
656709
710+ Optimizer::Uses* Optimizer::getUses(Ice::Operand* operand)
711+ {
712+ Optimizer::Uses* uses = (Optimizer::Uses*)operand->Ice::Operand::getExternalData();
713+ if(!uses)
714+ {
715+ uses = new Optimizer::Uses;
716+ setUses(operand, uses);
717+ allocatedUses.push_back(uses);
718+ }
719+ return uses;
720+ }
721+
722+ void Optimizer::setUses(Ice::Operand* operand, Optimizer::Uses* uses)
723+ {
724+ operand->Ice::Operand::setExternalData(uses);
725+ }
726+
727+ bool Optimizer::hasUses(Ice::Operand* operand) const
728+ {
729+ return operand->Ice::Operand::getExternalData() != nullptr;
730+ }
731+
732+ Ice::CfgNode* Optimizer::getNode(Ice::Inst* inst)
733+ {
734+ return (Ice::CfgNode*)inst->Ice::Inst::getExternalData();
735+ }
736+
737+ void Optimizer::setNode(Ice::Inst* inst, Ice::CfgNode* node)
738+ {
739+ inst->Ice::Inst::setExternalData(node);
740+ }
741+
742+ Ice::Inst* Optimizer::getDefinition(Ice::Variable* var)
743+ {
744+ return (Ice::Inst*)var->Ice::Variable::getExternalData();
745+ }
746+
747+ void Optimizer::setDefinition(Ice::Variable* var, Ice::Inst* inst)
748+ {
749+ var->Ice::Variable::setExternalData(inst);
750+ }
751+
752+ const std::vector<Optimizer::LoadStoreInst>& Optimizer::getLoadStoreInsts(Ice::CfgNode* node)
753+ {
754+ return *((const std::vector<LoadStoreInst>*)node->Ice::CfgNode::getExternalData());
755+ }
756+
757+ void Optimizer::setLoadStoreInsts(Ice::CfgNode* node, std::vector<LoadStoreInst>* insts)
758+ {
759+ node->Ice::CfgNode::setExternalData(insts);
760+ }
761+
762+ bool Optimizer::hasLoadStoreInsts(Ice::CfgNode* node) const
763+ {
764+ return node->Ice::CfgNode::getExternalData() != nullptr;
765+ }
766+
657767 bool Optimizer::Uses::areOnlyLoadStore() const
658768 {
659769 return size() == (loads.size() + stores.size());
--- a/third_party/subzero/src/IceCfgNode.h
+++ b/third_party/subzero/src/IceCfgNode.h
@@ -127,6 +127,9 @@ public:
127127 }
128128 CfgNode *shortCircuit();
129129
130+ inline void* getExternalData() const { return externalData; }
131+ inline void setExternalData(void* data) { externalData = data; }
132+
130133 private:
131134 CfgNode(Cfg *Func, SizeT Number)
132135 : Func(Func), Number(Number), NumberOrig(Number),
@@ -145,6 +148,11 @@ private:
145148 NodeList OutEdges; /// in no particular order
146149 PhiList Phis; /// unordered set of phi instructions
147150 InstList Insts; /// ordered list of non-phi instructions
151+
152+ /// External data can be set by an optimizer to compute and retain any
153+ /// information related to the current node. All the memory used to
154+ /// store this information must be managed by the optimizer.
155+ void* externalData = nullptr;
148156 };
149157
150158 } // end of namespace Ice
--- a/third_party/subzero/src/IceInst.h
+++ b/third_party/subzero/src/IceInst.h
@@ -199,6 +199,9 @@ public:
199199 llvm::report_fatal_error("Inst unexpectedly deleted");
200200 }
201201
202+ inline void* getExternalData() const { return externalData; }
203+ inline void setExternalData(void* data) { externalData = data; }
204+
202205 protected:
203206 Inst(Cfg *Func, InstKind Kind, SizeT MaxSrcs, Variable *Dest);
204207 void addSource(Operand *Src) {
@@ -236,6 +239,10 @@ protected:
236239 /// live range recorded in a basic block has at most one start and at most one
237240 /// end.
238241 bool IsDestRedefined = false;
242+ /// External data can be set by an optimizer to compute and retain any
243+ /// information related to the current instruction. All the memory used to
244+ /// store this information must be managed by the optimizer.
245+ void* externalData = nullptr;
239246
240247 Variable *Dest;
241248 const SizeT MaxSrcs; // only used for assert
--- a/third_party/subzero/src/IceOperand.h
+++ b/third_party/subzero/src/IceOperand.h
@@ -106,6 +106,9 @@ public:
106106 return 0;
107107 }
108108
109+ inline void* getExternalData() const { return externalData; }
110+ inline void setExternalData(void* data) { externalData = data; }
111+
109112 protected:
110113 Operand(OperandKind Kind, Type Ty) : Ty(Ty), Kind(Kind) {
111114 // It is undefined behavior to have a larger value in the enum
@@ -117,6 +120,11 @@ protected:
117120 /// Vars and NumVars are initialized by the derived class.
118121 SizeT NumVars = 0;
119122 Variable **Vars = nullptr;
123+
124+ /// External data can be set by an optimizer to compute and retain any
125+ /// information related to the current operand. All the memory used to
126+ /// store this information must be managed by the optimizer.
127+ void* externalData = nullptr;
120128 };
121129
122130 template <class StreamType>
@@ -854,6 +862,9 @@ public:
854862
855863 SizeT hashValue() const override { return std::hash<SizeT>()(getIndex()); }
856864
865+ inline void* getExternalData() const { return externalData; }
866+ inline void setExternalData(void* data) { externalData = data; }
867+
857868 protected:
858869 Variable(const Cfg *Func, OperandKind K, Type Ty, SizeT Index)
859870 : Operand(K, Ty), Number(Index),
@@ -895,6 +906,10 @@ protected:
895906 /// This Variable may be "linked" to another Variable, such that if neither
896907 /// Variable gets a register, they are guaranteed to share a stack location.
897908 Variable *LinkedTo = nullptr;
909+ /// External data can be set by an optimizer to compute and retain any
910+ /// information related to the current variable. All the memory used to
911+ /// store this information must be managed by the optimizer.
912+ void* externalData = nullptr;
898913 };
899914
900915 // Variable64On32 represents a 64-bit variable on a 32-bit architecture. In
旧リポジトリブラウザで表示