| // Copyright (c) 2019 Google LLC |
| // |
| // Licensed under the Apache License, Version 2.0 (the "License"); |
| // you may not use this file except in compliance with the License. |
| // You may obtain a copy of the License at |
| // |
| // http://www.apache.org/licenses/LICENSE-2.0 |
| // |
| // Unless required by applicable law or agreed to in writing, software |
| // distributed under the License is distributed on an "AS IS" BASIS, |
| // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| // See the License for the specific language governing permissions and |
| // limitations under the License. |
| |
| #include "code_sink.h" |
| |
| #include <set> |
| #include <vector> |
| |
| #include "source/opt/instruction.h" |
| #include "source/opt/ir_builder.h" |
| #include "source/opt/ir_context.h" |
| #include "source/util/bit_vector.h" |
| |
| namespace spvtools { |
| namespace opt { |
| |
| Pass::Status CodeSinkingPass::Process() { |
| bool modified = false; |
| for (Function& function : *get_module()) { |
| cfg()->ForEachBlockInPostOrder(function.entry().get(), |
| [&modified, this](BasicBlock* bb) { |
| if (SinkInstructionsInBB(bb)) { |
| modified = true; |
| } |
| }); |
| } |
| return modified ? Status::SuccessWithChange : Status::SuccessWithoutChange; |
| } |
| |
| bool CodeSinkingPass::SinkInstructionsInBB(BasicBlock* bb) { |
| bool modified = false; |
| for (auto inst = bb->rbegin(); inst != bb->rend(); ++inst) { |
| if (SinkInstruction(&*inst)) { |
| inst = bb->rbegin(); |
| modified = true; |
| } |
| } |
| return modified; |
| } |
| |
| bool CodeSinkingPass::SinkInstruction(Instruction* inst) { |
| if (inst->opcode() != SpvOpLoad && inst->opcode() != SpvOpAccessChain) { |
| return false; |
| } |
| |
| if (ReferencesMutableMemory(inst)) { |
| return false; |
| } |
| |
| if (BasicBlock* target_bb = FindNewBasicBlockFor(inst)) { |
| Instruction* pos = &*target_bb->begin(); |
| while (pos->opcode() == SpvOpPhi) { |
| pos = pos->NextNode(); |
| } |
| |
| inst->InsertBefore(pos); |
| context()->set_instr_block(inst, target_bb); |
| return true; |
| } |
| return false; |
| } |
| |
| BasicBlock* CodeSinkingPass::FindNewBasicBlockFor(Instruction* inst) { |
| assert(inst->result_id() != 0 && "Instruction should have a result."); |
| BasicBlock* original_bb = context()->get_instr_block(inst); |
| BasicBlock* bb = original_bb; |
| |
| std::unordered_set<uint32_t> bbs_with_uses; |
| get_def_use_mgr()->ForEachUse( |
| inst, [&bbs_with_uses, this](Instruction* use, uint32_t idx) { |
| if (use->opcode() != SpvOpPhi) { |
| BasicBlock* use_bb = context()->get_instr_block(use); |
| if (use_bb) { |
| bbs_with_uses.insert(use_bb->id()); |
| } |
| } else { |
| bbs_with_uses.insert(use->GetSingleWordOperand(idx + 1)); |
| } |
| }); |
| |
| while (true) { |
| // If |inst| is used in |bb|, then |inst| cannot be moved any further. |
| if (bbs_with_uses.count(bb->id())) { |
| break; |
| } |
| |
| // If |bb| has one successor (succ_bb), and |bb| is the only predecessor |
| // of succ_bb, then |inst| can be moved to succ_bb. If succ_bb, has move |
| // then one predecessor, then moving |inst| into succ_bb could cause it to |
| // be executed more often, so the search has to stop. |
| if (bb->terminator()->opcode() == SpvOpBranch) { |
| uint32_t succ_bb_id = bb->terminator()->GetSingleWordInOperand(0); |
| if (cfg()->preds(succ_bb_id).size() == 1) { |
| bb = context()->get_instr_block(succ_bb_id); |
| continue; |
| } else { |
| break; |
| } |
| } |
| |
| // The remaining checks need to know the merge node. If there is no merge |
| // instruction or an OpLoopMerge, then it is a break or continue. We could |
| // figure it out, but not worth doing it now. |
| Instruction* merge_inst = bb->GetMergeInst(); |
| if (merge_inst == nullptr || merge_inst->opcode() != SpvOpSelectionMerge) { |
| break; |
| } |
| |
| // Check all of the successors of |bb| it see which lead to a use of |inst| |
| // before reaching the merge node. |
| bool used_in_multiple_blocks = false; |
| uint32_t bb_used_in = 0; |
| bb->ForEachSuccessorLabel([this, bb, &bb_used_in, &used_in_multiple_blocks, |
| &bbs_with_uses](uint32_t* succ_bb_id) { |
| if (IntersectsPath(*succ_bb_id, bb->MergeBlockIdIfAny(), bbs_with_uses)) { |
| if (bb_used_in == 0) { |
| bb_used_in = *succ_bb_id; |
| } else { |
| used_in_multiple_blocks = true; |
| } |
| } |
| }); |
| |
| // If more than one successor, which is not the merge block, uses |inst| |
| // then we have to leave |inst| in bb because there is none of the |
| // successors dominate all uses of |inst|. |
| if (used_in_multiple_blocks) { |
| break; |
| } |
| |
| if (bb_used_in == 0) { |
| // If |inst| is not used before reaching the merge node, then we can move |
| // |inst| to the merge node. |
| bb = context()->get_instr_block(bb->MergeBlockIdIfAny()); |
| } else { |
| // If the only successor that leads to a used of |inst| has more than 1 |
| // predecessor, then moving |inst| could cause it to be executed more |
| // often, so we cannot move it. |
| if (cfg()->preds(bb_used_in).size() != 1) { |
| break; |
| } |
| |
| // If |inst| is used after the merge block, then |bb_used_in| does not |
| // dominate all of the uses. So we cannot move |inst| any further. |
| if (IntersectsPath(bb->MergeBlockIdIfAny(), original_bb->id(), |
| bbs_with_uses)) { |
| break; |
| } |
| |
| // Otherwise, |bb_used_in| dominates all uses, so move |inst| into that |
| // block. |
| bb = context()->get_instr_block(bb_used_in); |
| } |
| continue; |
| } |
| return (bb != original_bb ? bb : nullptr); |
| } |
| |
| bool CodeSinkingPass::ReferencesMutableMemory(Instruction* inst) { |
| if (!inst->IsLoad()) { |
| return false; |
| } |
| |
| Instruction* base_ptr = inst->GetBaseAddress(); |
| if (base_ptr->opcode() != SpvOpVariable) { |
| return true; |
| } |
| |
| if (base_ptr->IsReadOnlyPointer()) { |
| return false; |
| } |
| |
| if (HasUniformMemorySync()) { |
| return true; |
| } |
| |
| if (base_ptr->GetSingleWordInOperand(0) != SpvStorageClassUniform) { |
| return true; |
| } |
| |
| return HasPossibleStore(base_ptr); |
| } |
| |
| bool CodeSinkingPass::HasUniformMemorySync() { |
| if (checked_for_uniform_sync_) { |
| return has_uniform_sync_; |
| } |
| |
| bool has_sync = false; |
| get_module()->ForEachInst([this, &has_sync](Instruction* inst) { |
| switch (inst->opcode()) { |
| case SpvOpMemoryBarrier: { |
| uint32_t mem_semantics_id = inst->GetSingleWordInOperand(1); |
| if (IsSyncOnUniform(mem_semantics_id)) { |
| has_sync = true; |
| } |
| break; |
| } |
| case SpvOpControlBarrier: |
| case SpvOpAtomicLoad: |
| case SpvOpAtomicStore: |
| case SpvOpAtomicExchange: |
| case SpvOpAtomicIIncrement: |
| case SpvOpAtomicIDecrement: |
| case SpvOpAtomicIAdd: |
| case SpvOpAtomicFAddEXT: |
| case SpvOpAtomicISub: |
| case SpvOpAtomicSMin: |
| case SpvOpAtomicUMin: |
| case SpvOpAtomicSMax: |
| case SpvOpAtomicUMax: |
| case SpvOpAtomicAnd: |
| case SpvOpAtomicOr: |
| case SpvOpAtomicXor: |
| case SpvOpAtomicFlagTestAndSet: |
| case SpvOpAtomicFlagClear: { |
| uint32_t mem_semantics_id = inst->GetSingleWordInOperand(2); |
| if (IsSyncOnUniform(mem_semantics_id)) { |
| has_sync = true; |
| } |
| break; |
| } |
| case SpvOpAtomicCompareExchange: |
| case SpvOpAtomicCompareExchangeWeak: |
| if (IsSyncOnUniform(inst->GetSingleWordInOperand(2)) || |
| IsSyncOnUniform(inst->GetSingleWordInOperand(3))) { |
| has_sync = true; |
| } |
| break; |
| default: |
| break; |
| } |
| }); |
| has_uniform_sync_ = has_sync; |
| return has_sync; |
| } |
| |
| bool CodeSinkingPass::IsSyncOnUniform(uint32_t mem_semantics_id) const { |
| const analysis::Constant* mem_semantics_const = |
| context()->get_constant_mgr()->FindDeclaredConstant(mem_semantics_id); |
| assert(mem_semantics_const != nullptr && |
| "Expecting memory semantics id to be a constant."); |
| assert(mem_semantics_const->AsIntConstant() && |
| "Memory semantics should be an integer."); |
| uint32_t mem_semantics_int = mem_semantics_const->GetU32(); |
| |
| // If it does not affect uniform memory, then it is does not apply to uniform |
| // memory. |
| if ((mem_semantics_int & SpvMemorySemanticsUniformMemoryMask) == 0) { |
| return false; |
| } |
| |
| // Check if there is an acquire or release. If so not, this it does not add |
| // any memory constraints. |
| return (mem_semantics_int & (SpvMemorySemanticsAcquireMask | |
| SpvMemorySemanticsAcquireReleaseMask | |
| SpvMemorySemanticsReleaseMask)) != 0; |
| } |
| |
| bool CodeSinkingPass::HasPossibleStore(Instruction* var_inst) { |
| assert(var_inst->opcode() == SpvOpVariable || |
| var_inst->opcode() == SpvOpAccessChain || |
| var_inst->opcode() == SpvOpPtrAccessChain); |
| |
| return get_def_use_mgr()->WhileEachUser(var_inst, [this](Instruction* use) { |
| switch (use->opcode()) { |
| case SpvOpStore: |
| return true; |
| case SpvOpAccessChain: |
| case SpvOpPtrAccessChain: |
| return HasPossibleStore(use); |
| default: |
| return false; |
| } |
| }); |
| } |
| |
| bool CodeSinkingPass::IntersectsPath(uint32_t start, uint32_t end, |
| const std::unordered_set<uint32_t>& set) { |
| std::vector<uint32_t> worklist; |
| worklist.push_back(start); |
| std::unordered_set<uint32_t> already_done; |
| already_done.insert(start); |
| |
| while (!worklist.empty()) { |
| BasicBlock* bb = context()->get_instr_block(worklist.back()); |
| worklist.pop_back(); |
| |
| if (bb->id() == end) { |
| continue; |
| } |
| |
| if (set.count(bb->id())) { |
| return true; |
| } |
| |
| bb->ForEachSuccessorLabel([&already_done, &worklist](uint32_t* succ_bb_id) { |
| if (already_done.insert(*succ_bb_id).second) { |
| worklist.push_back(*succ_bb_id); |
| } |
| }); |
| } |
| return false; |
| } |
| |
| // namespace opt |
| |
| } // namespace opt |
| } // namespace spvtools |
