1 // Copyright (c) 2018 Google LLC
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 "source/reduce/reduction_util.h"
16
17 #include "source/opt/ir_context.h"
18 #include "source/util/make_unique.h"
19
20 namespace spvtools {
21 namespace reduce {
22
23 const uint32_t kTrueBranchOperandIndex = 1;
24 const uint32_t kFalseBranchOperandIndex = 2;
25
FindOrCreateGlobalVariable(opt::IRContext * context,uint32_t pointer_type_id)26 uint32_t FindOrCreateGlobalVariable(opt::IRContext* context,
27 uint32_t pointer_type_id) {
28 for (auto& inst : context->module()->types_values()) {
29 if (inst.opcode() != spv::Op::OpVariable) {
30 continue;
31 }
32 if (inst.type_id() == pointer_type_id) {
33 return inst.result_id();
34 }
35 }
36 const uint32_t variable_id = context->TakeNextId();
37 auto variable_inst = MakeUnique<opt::Instruction>(
38 context, spv::Op::OpVariable, pointer_type_id, variable_id,
39 opt::Instruction::OperandList(
40 {{SPV_OPERAND_TYPE_STORAGE_CLASS,
41 {static_cast<uint32_t>(context->get_type_mgr()
42 ->GetType(pointer_type_id)
43 ->AsPointer()
44 ->storage_class())}}}));
45 context->module()->AddGlobalValue(std::move(variable_inst));
46 return variable_id;
47 }
48
FindOrCreateFunctionVariable(opt::IRContext * context,opt::Function * function,uint32_t pointer_type_id)49 uint32_t FindOrCreateFunctionVariable(opt::IRContext* context,
50 opt::Function* function,
51 uint32_t pointer_type_id) {
52 // The pointer type of a function variable must have Function storage class.
53 assert(context->get_type_mgr()
54 ->GetType(pointer_type_id)
55 ->AsPointer()
56 ->storage_class() == spv::StorageClass::Function);
57
58 // Go through the instructions in the function's first block until we find a
59 // suitable variable, or go past all the variables.
60 opt::BasicBlock::iterator iter = function->begin()->begin();
61 for (;; ++iter) {
62 // We will either find a suitable variable, or find a non-variable
63 // instruction; we won't exhaust all instructions.
64 assert(iter != function->begin()->end());
65 if (iter->opcode() != spv::Op::OpVariable) {
66 // If we see a non-variable, we have gone through all the variables.
67 break;
68 }
69 if (iter->type_id() == pointer_type_id) {
70 return iter->result_id();
71 }
72 }
73 // At this point, iter refers to the first non-function instruction of the
74 // function's entry block.
75 const uint32_t variable_id = context->TakeNextId();
76 auto variable_inst = MakeUnique<opt::Instruction>(
77 context, spv::Op::OpVariable, pointer_type_id, variable_id,
78 opt::Instruction::OperandList(
79 {{SPV_OPERAND_TYPE_STORAGE_CLASS,
80 {uint32_t(spv::StorageClass::Function)}}}));
81 iter->InsertBefore(std::move(variable_inst));
82 return variable_id;
83 }
84
FindOrCreateGlobalUndef(opt::IRContext * context,uint32_t type_id)85 uint32_t FindOrCreateGlobalUndef(opt::IRContext* context, uint32_t type_id) {
86 for (auto& inst : context->module()->types_values()) {
87 if (inst.opcode() != spv::Op::OpUndef) {
88 continue;
89 }
90 if (inst.type_id() == type_id) {
91 return inst.result_id();
92 }
93 }
94 const uint32_t undef_id = context->TakeNextId();
95 auto undef_inst =
96 MakeUnique<opt::Instruction>(context, spv::Op::OpUndef, type_id, undef_id,
97 opt::Instruction::OperandList());
98 assert(undef_id == undef_inst->result_id());
99 context->module()->AddGlobalValue(std::move(undef_inst));
100 return undef_id;
101 }
102
AdaptPhiInstructionsForRemovedEdge(uint32_t from_id,opt::BasicBlock * to_block)103 void AdaptPhiInstructionsForRemovedEdge(uint32_t from_id,
104 opt::BasicBlock* to_block) {
105 to_block->ForEachPhiInst([&from_id](opt::Instruction* phi_inst) {
106 opt::Instruction::OperandList new_in_operands;
107 // Go through the OpPhi's input operands in (variable, parent) pairs.
108 for (uint32_t index = 0; index < phi_inst->NumInOperands(); index += 2) {
109 // Keep all pairs where the parent is not the block from which the edge
110 // is being removed.
111 if (phi_inst->GetInOperand(index + 1).words[0] != from_id) {
112 new_in_operands.push_back(phi_inst->GetInOperand(index));
113 new_in_operands.push_back(phi_inst->GetInOperand(index + 1));
114 }
115 }
116 phi_inst->SetInOperands(std::move(new_in_operands));
117 });
118 }
119
120 } // namespace reduce
121 } // namespace spvtools
122