1// Copyright 2016 The SwiftShader Authors. All Rights Reserved.
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7// http://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14
15#include "Optimizer.hpp"
16
17#include "src/IceCfg.h"
18#include "src/IceCfgNode.h"
19
20#include <vector>
21
22namespace
23{
24 class Optimizer
25 {
26 public:
27 void run(Ice::Cfg *function);
28
29 private:
30 void analyzeUses(Ice::Cfg *function);
31 void eliminateDeadCode();
32 void eliminateUnitializedLoads();
33 void eliminateLoadsFollowingSingleStore();
34 void optimizeStoresInSingleBasicBlock();
35
36 void replace(Ice::Inst *instruction, Ice::Operand *newValue);
37 void deleteInstruction(Ice::Inst *instruction);
38 bool isDead(Ice::Inst *instruction);
39
40 static const Ice::InstIntrinsicCall *asLoadSubVector(const Ice::Inst *instruction);
41 static const Ice::InstIntrinsicCall *asStoreSubVector(const Ice::Inst *instruction);
42 static bool isLoad(const Ice::Inst &instruction);
43 static bool isStore(const Ice::Inst &instruction);
44 static Ice::Operand *storeAddress(const Ice::Inst *instruction);
45 static Ice::Operand *loadAddress(const Ice::Inst *instruction);
46 static Ice::Operand *storeData(const Ice::Inst *instruction);
47 static std::size_t storeSize(const Ice::Inst *instruction);
48 static bool loadTypeMatchesStore(const Ice::Inst *load, const Ice::Inst *store);
49
50 Ice::Cfg *function;
51 Ice::GlobalContext *context;
52
53 struct Uses : std::vector<Ice::Inst*>
54 {
55 bool areOnlyLoadStore() const;
56 void insert(Ice::Operand *value, Ice::Inst *instruction);
57 void erase(Ice::Inst *instruction);
58
59 std::vector<Ice::Inst*> loads;
60 std::vector<Ice::Inst*> stores;
61 };
62
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;
92 };
93
94 void Optimizer::run(Ice::Cfg *function)
95 {
96 this->function = function;
97 this->context = function->getContext();
98
99 analyzeUses(function);
100
101 eliminateDeadCode();
102 eliminateUnitializedLoads();
103 eliminateLoadsFollowingSingleStore();
104 optimizeStoresInSingleBasicBlock();
105 eliminateDeadCode();
106
107 for(auto uses : allocatedUses)
108 {
109 delete uses;
110 }
111 allocatedUses.clear();
112 }
113
114 void Optimizer::eliminateDeadCode()
115 {
116 bool modified;
117 do
118 {
119 modified = false;
120 for(Ice::CfgNode *basicBlock : function->getNodes())
121 {
122 for(Ice::Inst &inst : Ice::reverse_range(basicBlock->getInsts()))
123 {
124 if(inst.isDeleted())
125 {
126 continue;
127 }
128
129 if(isDead(&inst))
130 {
131 deleteInstruction(&inst);
132 modified = true;
133 }
134 }
135 }
136 }
137 while(modified);
138 }
139
140 void Optimizer::eliminateUnitializedLoads()
141 {
142 Ice::CfgNode *entryBlock = function->getEntryNode();
143
144 for(Ice::Inst &alloca : entryBlock->getInsts())
145 {
146 if(alloca.isDeleted())
147 {
148 continue;
149 }
150
151 if(!llvm::isa<Ice::InstAlloca>(alloca))
152 {
153 break; // Allocas are all at the top
154 }
155
156 Ice::Operand *address = alloca.getDest();
157
158 if(!hasUses(address))
159 {
160 continue;
161 }
162
163 const auto &addressUses = *getUses(address);
164
165 if(!addressUses.areOnlyLoadStore())
166 {
167 continue;
168 }
169
170 if(addressUses.stores.empty())
171 {
172 for(Ice::Inst *load : addressUses.loads)
173 {
174 Ice::Variable *loadData = load->getDest();
175
176 if(hasUses(loadData))
177 {
178 for(Ice::Inst *use : *getUses(loadData))
179 {
180 for(Ice::SizeT i = 0; i < use->getSrcSize(); i++)
181 {
182 if(use->getSrc(i) == loadData)
183 {
184 auto *undef = context->getConstantUndef(loadData->getType());
185
186 use->replaceSource(i, undef);
187 }
188 }
189 }
190
191 setUses(loadData, nullptr);
192 }
193
194 load->setDeleted();
195 }
196
197 alloca.setDeleted();
198 setUses(address, nullptr);
199 }
200 }
201 }
202
203 void Optimizer::eliminateLoadsFollowingSingleStore()
204 {
205 Ice::CfgNode *entryBlock = function->getEntryNode();
206
207 for(Ice::Inst &alloca : entryBlock->getInsts())
208 {
209 if(alloca.isDeleted())
210 {
211 continue;
212 }
213
214 if(!llvm::isa<Ice::InstAlloca>(alloca))
215 {
216 break; // Allocas are all at the top
217 }
218
219 Ice::Operand *address = alloca.getDest();
220
221 if(!hasUses(address))
222 {
223 continue;
224 }
225
226 auto &addressUses = *getUses(address);
227
228 if(!addressUses.areOnlyLoadStore())
229 {
230 continue;
231 }
232
233 if(addressUses.stores.size() == 1)
234 {
235 Ice::Inst *store = addressUses.stores[0];
236 Ice::Operand *storeValue = storeData(store);
237
238 for(Ice::Inst *load = &*++store->getIterator(), *next = nullptr; load != next; next = load, load = &*++store->getIterator())
239 {
240 if(load->isDeleted() || !isLoad(*load))
241 {
242 continue;
243 }
244
245 if(loadAddress(load) != address)
246 {
247 continue;
248 }
249
250 if(!loadTypeMatchesStore(load, store))
251 {
252 continue;
253 }
254
255 replace(load, storeValue);
256
257 for(size_t i = 0; i < addressUses.loads.size(); i++)
258 {
259 if(addressUses.loads[i] == load)
260 {
261 addressUses.loads[i] = addressUses.loads.back();
262 addressUses.loads.pop_back();
263 break;
264 }
265 }
266
267 for(size_t i = 0; i < addressUses.size(); i++)
268 {
269 if(addressUses[i] == load)
270 {
271 addressUses[i] = addressUses.back();
272 addressUses.pop_back();
273 break;
274 }
275 }
276
277 if(addressUses.size() == 1)
278 {
279 assert(addressUses[0] == store);
280
281 alloca.setDeleted();
282 store->setDeleted();
283 setUses(address, nullptr);
284
285 if(hasUses(storeValue))
286 {
287 auto &valueUses = *getUses(storeValue);
288
289 for(size_t i = 0; i < valueUses.size(); i++)
290 {
291 if(valueUses[i] == store)
292 {
293 valueUses[i] = valueUses.back();
294 valueUses.pop_back();
295 break;
296 }
297 }
298
299 if(valueUses.empty())
300 {
301 setUses(storeValue, nullptr);
302 }
303 }
304
305 break;
306 }
307 }
308 }
309 }
310 }
311
312 void Optimizer::optimizeStoresInSingleBasicBlock()
313 {
314 Ice::CfgNode *entryBlock = function->getEntryNode();
315
316 std::vector<std::vector<LoadStoreInst>* > allocatedVectors;
317
318 for(Ice::Inst &alloca : entryBlock->getInsts())
319 {
320 if(alloca.isDeleted())
321 {
322 continue;
323 }
324
325 if(!llvm::isa<Ice::InstAlloca>(alloca))
326 {
327 break; // Allocas are all at the top
328 }
329
330 Ice::Operand *address = alloca.getDest();
331
332 if(!hasUses(address))
333 {
334 continue;
335 }
336
337 const auto &addressUses = *getUses(address);
338
339 if(!addressUses.areOnlyLoadStore())
340 {
341 continue;
342 }
343
344 Ice::CfgNode *singleBasicBlock = getNode(addressUses.stores[0]);
345
346 for(size_t i = 1; i < addressUses.stores.size(); i++)
347 {
348 Ice::Inst *store = addressUses.stores[i];
349 if(getNode(store) != singleBasicBlock)
350 {
351 singleBasicBlock = nullptr;
352 break;
353 }
354 }
355
356 if(singleBasicBlock)
357 {
358 if(!hasLoadStoreInsts(singleBasicBlock))
359 {
360 std::vector<LoadStoreInst>* loadStoreInstVector = new std::vector<LoadStoreInst>();
361 setLoadStoreInsts(singleBasicBlock, loadStoreInstVector);
362 allocatedVectors.push_back(loadStoreInstVector);
363 for(Ice::Inst &inst : singleBasicBlock->getInsts())
364 {
365 if(inst.isDeleted())
366 {
367 continue;
368 }
369
370 bool isStoreInst = isStore(inst);
371 bool isLoadInst = isLoad(inst);
372
373 if(isStoreInst || isLoadInst)
374 {
375 loadStoreInstVector->push_back(LoadStoreInst(&inst, isStoreInst));
376 }
377 }
378 }
379
380 Ice::Inst *store = nullptr;
381 Ice::Operand *storeValue = nullptr;
382 bool unmatchedLoads = false;
383
384 for (auto& loadStoreInst : getLoadStoreInsts(singleBasicBlock))
385 {
386 Ice::Inst* inst = loadStoreInst.inst;
387
388 if((loadStoreInst.address != address) || inst->isDeleted())
389 {
390 continue;
391 }
392
393 if(loadStoreInst.isStore)
394 {
395 // New store found. If we had a previous one, try to eliminate it.
396 if(store && !unmatchedLoads)
397 {
398 // If the previous store is wider than the new one, we can't eliminate it
399 // because there could be a wide load reading its non-overwritten data.
400 if(storeSize(inst) >= storeSize(store))
401 {
402 deleteInstruction(store);
403 }
404 }
405
406 store = inst;
407 storeValue = storeData(store);
408 unmatchedLoads = false;
409 }
410 else
411 {
412 if(!loadTypeMatchesStore(inst, store))
413 {
414 unmatchedLoads = true;
415 continue;
416 }
417
418 replace(inst, storeValue);
419 }
420 }
421 }
422 }
423
424 for(auto loadStoreInstVector : allocatedVectors)
425 {
426 delete loadStoreInstVector;
427 }
428 }
429
430 void Optimizer::analyzeUses(Ice::Cfg *function)
431 {
432 for(Ice::CfgNode *basicBlock : function->getNodes())
433 {
434 for(Ice::Inst &instruction : basicBlock->getInsts())
435 {
436 if(instruction.isDeleted())
437 {
438 continue;
439 }
440
441 setNode(&instruction, basicBlock);
442 if(instruction.getDest())
443 {
444 setDefinition(instruction.getDest(), &instruction);
445 }
446
447 for(Ice::SizeT i = 0; i < instruction.getSrcSize(); i++)
448 {
449 Ice::SizeT unique = 0;
450 for(; unique < i; unique++)
451 {
452 if(instruction.getSrc(i) == instruction.getSrc(unique))
453 {
454 break;
455 }
456 }
457
458 if(i == unique)
459 {
460 Ice::Operand *src = instruction.getSrc(i);
461 getUses(src)->insert(src, &instruction);
462 }
463 }
464 }
465 }
466 }
467
468 void Optimizer::replace(Ice::Inst *instruction, Ice::Operand *newValue)
469 {
470 Ice::Variable *oldValue = instruction->getDest();
471
472 if(!newValue)
473 {
474 newValue = context->getConstantUndef(oldValue->getType());
475 }
476
477 if(hasUses(oldValue))
478 {
479 for(Ice::Inst *use : *getUses(oldValue))
480 {
481 assert(!use->isDeleted()); // Should have been removed from uses already
482
483 for(Ice::SizeT i = 0; i < use->getSrcSize(); i++)
484 {
485 if(use->getSrc(i) == oldValue)
486 {
487 use->replaceSource(i, newValue);
488 }
489 }
490
491 getUses(newValue)->insert(newValue, use);
492 }
493
494 setUses(oldValue, nullptr);
495 }
496
497 deleteInstruction(instruction);
498 }
499
500 void Optimizer::deleteInstruction(Ice::Inst *instruction)
501 {
502 if(!instruction || instruction->isDeleted())
503 {
504 return;
505 }
506
507 instruction->setDeleted();
508
509 for(Ice::SizeT i = 0; i < instruction->getSrcSize(); i++)
510 {
511 Ice::Operand *src = instruction->getSrc(i);
512
513 if(hasUses(src))
514 {
515 auto &srcUses = *getUses(src);
516
517 srcUses.erase(instruction);
518
519 if(srcUses.empty())
520 {
521 setUses(src, nullptr);
522
523 if(Ice::Variable *var = llvm::dyn_cast<Ice::Variable>(src))
524 {
525 deleteInstruction(getDefinition(var));
526 }
527 }
528 }
529 }
530 }
531
532 bool Optimizer::isDead(Ice::Inst *instruction)
533 {
534 Ice::Variable *dest = instruction->getDest();
535
536 if(dest)
537 {
538 return (!hasUses(dest) || getUses(dest)->empty()) && !instruction->hasSideEffects();
539 }
540 else if(isStore(*instruction))
541 {
542 if(Ice::Variable *address = llvm::dyn_cast<Ice::Variable>(storeAddress(instruction)))
543 {
544 Ice::Inst *def = getDefinition(address);
545
546 if(def && llvm::isa<Ice::InstAlloca>(def))
547 {
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 }
557 }
558 }
559 }
560
561 return false;
562 }
563
564 const Ice::InstIntrinsicCall *Optimizer::asLoadSubVector(const Ice::Inst *instruction)
565 {
566 if(auto *instrinsic = llvm::dyn_cast<Ice::InstIntrinsicCall>(instruction))
567 {
568 if(instrinsic->getIntrinsicInfo().ID == Ice::Intrinsics::LoadSubVector)
569 {
570 return instrinsic;
571 }
572 }
573
574 return nullptr;
575 }
576
577 const Ice::InstIntrinsicCall *Optimizer::asStoreSubVector(const Ice::Inst *instruction)
578 {
579 if(auto *instrinsic = llvm::dyn_cast<Ice::InstIntrinsicCall>(instruction))
580 {
581 if(instrinsic->getIntrinsicInfo().ID == Ice::Intrinsics::StoreSubVector)
582 {
583 return instrinsic;
584 }
585 }
586
587 return nullptr;
588 }
589
590 bool Optimizer::isLoad(const Ice::Inst &instruction)
591 {
592 if(llvm::isa<Ice::InstLoad>(&instruction))
593 {
594 return true;
595 }
596
597 return asLoadSubVector(&instruction) != nullptr;
598 }
599
600 bool Optimizer::isStore(const Ice::Inst &instruction)
601 {
602 if(llvm::isa<Ice::InstStore>(&instruction))
603 {
604 return true;
605 }
606
607 return asStoreSubVector(&instruction) != nullptr;
608 }
609
610 Ice::Operand *Optimizer::storeAddress(const Ice::Inst *instruction)
611 {
612 assert(isStore(*instruction));
613
614 if(auto *store = llvm::dyn_cast<Ice::InstStore>(instruction))
615 {
616 return store->getAddr();
617 }
618
619 if(auto *storeSubVector = asStoreSubVector(instruction))
620 {
621 return storeSubVector->getSrc(2);
622 }
623
624 return nullptr;
625 }
626
627 Ice::Operand *Optimizer::loadAddress(const Ice::Inst *instruction)
628 {
629 assert(isLoad(*instruction));
630
631 if(auto *load = llvm::dyn_cast<Ice::InstLoad>(instruction))
632 {
633 return load->getSourceAddress();
634 }
635
636 if(auto *loadSubVector = asLoadSubVector(instruction))
637 {
638 return loadSubVector->getSrc(1);
639 }
640
641 return nullptr;
642 }
643
644 Ice::Operand *Optimizer::storeData(const Ice::Inst *instruction)
645 {
646 assert(isStore(*instruction));
647
648 if(auto *store = llvm::dyn_cast<Ice::InstStore>(instruction))
649 {
650 return store->getData();
651 }
652
653 if(auto *storeSubVector = asStoreSubVector(instruction))
654 {
655 return storeSubVector->getSrc(1);
656 }
657
658 return nullptr;
659 }
660
661 std::size_t Optimizer::storeSize(const Ice::Inst *store)
662 {
663 assert(isStore(*store));
664
665 if(auto *instStore = llvm::dyn_cast<Ice::InstStore>(store))
666 {
667 return Ice::typeWidthInBytes(instStore->getData()->getType());
668 }
669
670 if(auto *storeSubVector = asStoreSubVector(store))
671 {
672 return llvm::cast<Ice::ConstantInteger32>(storeSubVector->getSrc(3))->getValue();
673 }
674
675 return 0;
676 }
677
678 bool Optimizer::loadTypeMatchesStore(const Ice::Inst *load, const Ice::Inst *store)
679 {
680 if(!load || !store)
681 {
682 return false;
683 }
684
685 assert(isLoad(*load) && isStore(*store));
686 assert(loadAddress(load) == storeAddress(store));
687
688 if(auto *instStore = llvm::dyn_cast<Ice::InstStore>(store))
689 {
690 if(auto *instLoad = llvm::dyn_cast<Ice::InstLoad>(load))
691 {
692 return instStore->getData()->getType() == instLoad->getDest()->getType();
693 }
694 }
695
696 if(auto *storeSubVector = asStoreSubVector(store))
697 {
698 if(auto *loadSubVector = asLoadSubVector(load))
699 {
700 // Check for matching type and sub-vector width.
701 return storeSubVector->getSrc(1)->getType() == loadSubVector->getDest()->getType() &&
702 llvm::cast<Ice::ConstantInteger32>(storeSubVector->getSrc(3))->getValue() ==
703 llvm::cast<Ice::ConstantInteger32>(loadSubVector->getSrc(2))->getValue();
704 }
705 }
706
707 return false;
708 }
709
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
767 bool Optimizer::Uses::areOnlyLoadStore() const
768 {
769 return size() == (loads.size() + stores.size());
770 }
771
772 void Optimizer::Uses::insert(Ice::Operand *value, Ice::Inst *instruction)
773 {
774 push_back(instruction);
775
776 if(isLoad(*instruction))
777 {
778 if(value == loadAddress(instruction))
779 {
780 loads.push_back(instruction);
781 }
782 }
783 else if(isStore(*instruction))
784 {
785 if(value == storeAddress(instruction))
786 {
787 stores.push_back(instruction);
788 }
789 }
790 }
791
792 void Optimizer::Uses::erase(Ice::Inst *instruction)
793 {
794 auto &uses = *this;
795
796 for(size_t i = 0; i < uses.size(); i++)
797 {
798 if(uses[i] == instruction)
799 {
800 uses[i] = back();
801 pop_back();
802
803 for(size_t i = 0; i < loads.size(); i++)
804 {
805 if(loads[i] == instruction)
806 {
807 loads[i] = loads.back();
808 loads.pop_back();
809 break;
810 }
811 }
812
813 for(size_t i = 0; i < stores.size(); i++)
814 {
815 if(stores[i] == instruction)
816 {
817 stores[i] = stores.back();
818 stores.pop_back();
819 break;
820 }
821 }
822
823 break;
824 }
825 }
826 }
827}
828
829namespace rr
830{
831 void optimize(Ice::Cfg *function)
832 {
833 Optimizer optimizer;
834
835 optimizer.run(function);
836 }
837}