1 // Copyright (c) 2016 Google Inc. 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/opt/basic_block.h" 16 17 #include <ostream> 18 19 #include "source/opt/function.h" 20 #include "source/opt/ir_context.h" 21 #include "source/opt/module.h" 22 #include "source/opt/reflect.h" 23 #include "source/util/make_unique.h" 24 25 namespace spvtools { 26 namespace opt { 27 namespace { 28 29 const uint32_t kLoopMergeContinueBlockIdInIdx = 1; 30 const uint32_t kLoopMergeMergeBlockIdInIdx = 0; 31 const uint32_t kSelectionMergeMergeBlockIdInIdx = 0; 32 33 } // namespace 34 35 BasicBlock* BasicBlock::Clone(IRContext* context) const { 36 BasicBlock* clone = new BasicBlock( 37 std::unique_ptr<Instruction>(GetLabelInst()->Clone(context))); 38 for (const auto& inst : insts_) { 39 // Use the incoming context 40 clone->AddInstruction(std::unique_ptr<Instruction>(inst.Clone(context))); 41 } 42 43 if (context->AreAnalysesValid( 44 IRContext::Analysis::kAnalysisInstrToBlockMapping)) { 45 for (auto& inst : *clone) { 46 context->set_instr_block(&inst, clone); 47 } 48 } 49 50 return clone; 51 } 52 53 const Instruction* BasicBlock::GetMergeInst() const { 54 const Instruction* result = nullptr; 55 // If it exists, the merge instruction immediately precedes the 56 // terminator. 57 auto iter = ctail(); 58 if (iter != cbegin()) { 59 --iter; 60 const auto opcode = iter->opcode(); 61 if (opcode == SpvOpLoopMerge || opcode == SpvOpSelectionMerge) { 62 result = &*iter; 63 } 64 } 65 return result; 66 } 67 68 Instruction* BasicBlock::GetMergeInst() { 69 Instruction* result = nullptr; 70 // If it exists, the merge instruction immediately precedes the 71 // terminator. 72 auto iter = tail(); 73 if (iter != begin()) { 74 --iter; 75 const auto opcode = iter->opcode(); 76 if (opcode == SpvOpLoopMerge || opcode == SpvOpSelectionMerge) { 77 result = &*iter; 78 } 79 } 80 return result; 81 } 82 83 const Instruction* BasicBlock::GetLoopMergeInst() const { 84 if (auto* merge = GetMergeInst()) { 85 if (merge->opcode() == SpvOpLoopMerge) { 86 return merge; 87 } 88 } 89 return nullptr; 90 } 91 92 Instruction* BasicBlock::GetLoopMergeInst() { 93 if (auto* merge = GetMergeInst()) { 94 if (merge->opcode() == SpvOpLoopMerge) { 95 return merge; 96 } 97 } 98 return nullptr; 99 } 100 101 void BasicBlock::KillAllInsts(bool killLabel) { 102 ForEachInst([killLabel](Instruction* ip) { 103 if (killLabel || ip->opcode() != SpvOpLabel) { 104 ip->context()->KillInst(ip); 105 } 106 }); 107 } 108 109 void BasicBlock::ForEachSuccessorLabel( 110 const std::function<void(const uint32_t)>& f) const { 111 const auto br = &insts_.back(); 112 switch (br->opcode()) { 113 case SpvOpBranch: { 114 f(br->GetOperand(0).words[0]); 115 } break; 116 case SpvOpBranchConditional: 117 case SpvOpSwitch: { 118 bool is_first = true; 119 br->ForEachInId([&is_first, &f](const uint32_t* idp) { 120 if (!is_first) f(*idp); 121 is_first = false; 122 }); 123 } break; 124 default: 125 break; 126 } 127 } 128 129 void BasicBlock::ForEachSuccessorLabel( 130 const std::function<void(uint32_t*)>& f) { 131 auto br = &insts_.back(); 132 switch (br->opcode()) { 133 case SpvOpBranch: { 134 uint32_t tmp_id = br->GetOperand(0).words[0]; 135 f(&tmp_id); 136 if (tmp_id != br->GetOperand(0).words[0]) br->SetOperand(0, {tmp_id}); 137 } break; 138 case SpvOpBranchConditional: 139 case SpvOpSwitch: { 140 bool is_first = true; 141 br->ForEachInId([&is_first, &f](uint32_t* idp) { 142 if (!is_first) f(idp); 143 is_first = false; 144 }); 145 } break; 146 default: 147 break; 148 } 149 } 150 151 bool BasicBlock::IsSuccessor(const BasicBlock* block) const { 152 uint32_t succId = block->id(); 153 bool isSuccessor = false; 154 ForEachSuccessorLabel([&isSuccessor, succId](const uint32_t label) { 155 if (label == succId) isSuccessor = true; 156 }); 157 return isSuccessor; 158 } 159 160 void BasicBlock::ForMergeAndContinueLabel( 161 const std::function<void(const uint32_t)>& f) { 162 auto ii = insts_.end(); 163 --ii; 164 if (ii == insts_.begin()) return; 165 --ii; 166 if (ii->opcode() == SpvOpSelectionMerge || ii->opcode() == SpvOpLoopMerge) { 167 ii->ForEachInId([&f](const uint32_t* idp) { f(*idp); }); 168 } 169 } 170 171 uint32_t BasicBlock::MergeBlockIdIfAny() const { 172 auto merge_ii = cend(); 173 --merge_ii; 174 uint32_t mbid = 0; 175 if (merge_ii != cbegin()) { 176 --merge_ii; 177 if (merge_ii->opcode() == SpvOpLoopMerge) { 178 mbid = merge_ii->GetSingleWordInOperand(kLoopMergeMergeBlockIdInIdx); 179 } else if (merge_ii->opcode() == SpvOpSelectionMerge) { 180 mbid = merge_ii->GetSingleWordInOperand(kSelectionMergeMergeBlockIdInIdx); 181 } 182 } 183 184 return mbid; 185 } 186 187 uint32_t BasicBlock::ContinueBlockIdIfAny() const { 188 auto merge_ii = cend(); 189 --merge_ii; 190 uint32_t cbid = 0; 191 if (merge_ii != cbegin()) { 192 --merge_ii; 193 if (merge_ii->opcode() == SpvOpLoopMerge) { 194 cbid = merge_ii->GetSingleWordInOperand(kLoopMergeContinueBlockIdInIdx); 195 } 196 } 197 return cbid; 198 } 199 200 std::ostream& operator<<(std::ostream& str, const BasicBlock& block) { 201 str << block.PrettyPrint(); 202 return str; 203 } 204 205 void BasicBlock::Dump() const { 206 std::cerr << "Basic block #" << id() << "\n" << *this << "\n "; 207 } 208 209 std::string BasicBlock::PrettyPrint(uint32_t options) const { 210 std::ostringstream str; 211 ForEachInst([&str, options](const Instruction* inst) { 212 str << inst->PrettyPrint(options); 213 if (!IsTerminatorInst(inst->opcode())) { 214 str << std::endl; 215 } 216 }); 217 return str.str(); 218 } 219 220 BasicBlock* BasicBlock::SplitBasicBlock(IRContext* context, uint32_t label_id, 221 iterator iter) { 222 assert(!insts_.empty()); 223 224 std::unique_ptr<BasicBlock> new_block_temp = 225 MakeUnique<BasicBlock>(MakeUnique<Instruction>( 226 context, SpvOpLabel, 0, label_id, std::initializer_list<Operand>{})); 227 BasicBlock* new_block = new_block_temp.get(); 228 function_->InsertBasicBlockAfter(std::move(new_block_temp), this); 229 230 new_block->insts_.Splice(new_block->end(), &insts_, iter, end()); 231 new_block->SetParent(GetParent()); 232 233 context->AnalyzeDefUse(new_block->GetLabelInst()); 234 235 // Update the phi nodes in the successor blocks to reference the new block id. 236 const_cast<const BasicBlock*>(new_block)->ForEachSuccessorLabel( 237 [new_block, this, context](const uint32_t label) { 238 BasicBlock* target_bb = context->get_instr_block(label); 239 target_bb->ForEachPhiInst( 240 [this, new_block, context](Instruction* phi_inst) { 241 bool changed = false; 242 for (uint32_t i = 1; i < phi_inst->NumInOperands(); i += 2) { 243 if (phi_inst->GetSingleWordInOperand(i) == this->id()) { 244 changed = true; 245 phi_inst->SetInOperand(i, {new_block->id()}); 246 } 247 } 248 249 if (changed) { 250 context->UpdateDefUse(phi_inst); 251 } 252 }); 253 }); 254 255 if (context->AreAnalysesValid(IRContext::kAnalysisInstrToBlockMapping)) { 256 context->set_instr_block(new_block->GetLabelInst(), new_block); 257 new_block->ForEachInst([new_block, context](Instruction* inst) { 258 context->set_instr_block(inst, new_block); 259 }); 260 } 261 262 return new_block; 263 } 264 265 } // namespace opt 266 } // namespace spvtools 267