blob: 43ec15f805f99fdd8b76a69e16fbc311c10a3dad [file] [log] [blame]
// Copyright (c) 2018 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 "source/opt/simplification_pass.h"
#include <set>
#include <unordered_set>
#include <vector>
#include "source/opt/fold.h"
namespace spvtools {
namespace opt {
Pass::Status SimplificationPass::Process() {
bool modified = false;
for (Function& function : *get_module()) {
modified |= SimplifyFunction(&function);
}
return (modified ? Status::SuccessWithChange : Status::SuccessWithoutChange);
}
void SimplificationPass::AddNewOperands(
Instruction* folded_inst, std::unordered_set<Instruction*>* inst_seen,
std::vector<Instruction*>* work_list) {
analysis::DefUseManager* def_use_mgr = get_def_use_mgr();
folded_inst->ForEachInId(
[&inst_seen, &def_use_mgr, &work_list](uint32_t* iid) {
Instruction* iid_inst = def_use_mgr->GetDef(*iid);
if (!inst_seen->insert(iid_inst).second) return;
work_list->push_back(iid_inst);
});
}
bool SimplificationPass::SimplifyFunction(Function* function) {
if (function->IsDeclaration()) {
return false;
}
bool modified = false;
// Phase 1: Traverse all instructions in dominance order.
// The second phase will only be on the instructions whose inputs have changed
// after being processed during phase 1. Since OpPhi instructions are the
// only instructions whose inputs do not necessarily dominate the use, we keep
// track of the OpPhi instructions already seen, and add them to the work list
// for phase 2 when needed.
std::vector<Instruction*> work_list;
std::unordered_set<Instruction*> process_phis;
std::unordered_set<Instruction*> inst_to_kill;
std::unordered_set<Instruction*> in_work_list;
std::unordered_set<Instruction*> inst_seen;
const InstructionFolder& folder = context()->get_instruction_folder();
cfg()->ForEachBlockInReversePostOrder(
function->entry().get(),
[&modified, &process_phis, &work_list, &in_work_list, &inst_to_kill,
&folder, &inst_seen, this](BasicBlock* bb) {
for (Instruction* inst = &*bb->begin(); inst; inst = inst->NextNode()) {
inst_seen.insert(inst);
if (inst->opcode() == SpvOpPhi) {
process_phis.insert(inst);
}
bool is_foldable_copy =
inst->opcode() == SpvOpCopyObject &&
context()->get_decoration_mgr()->HaveSubsetOfDecorations(
inst->result_id(), inst->GetSingleWordInOperand(0));
if (is_foldable_copy || folder.FoldInstruction(inst)) {
modified = true;
context()->AnalyzeUses(inst);
get_def_use_mgr()->ForEachUser(inst, [&work_list, &process_phis,
&in_work_list](
Instruction* use) {
if (process_phis.count(use) && in_work_list.insert(use).second) {
work_list.push_back(use);
}
});
AddNewOperands(inst, &inst_seen, &work_list);
if (inst->opcode() == SpvOpCopyObject) {
context()->ReplaceAllUsesWithPredicate(
inst->result_id(), inst->GetSingleWordInOperand(0),
[](Instruction* user) {
const auto opcode = user->opcode();
if (!spvOpcodeIsDebug(opcode) &&
!spvOpcodeIsDecoration(opcode)) {
return true;
}
return false;
});
inst_to_kill.insert(inst);
in_work_list.insert(inst);
} else if (inst->opcode() == SpvOpNop) {
inst_to_kill.insert(inst);
in_work_list.insert(inst);
}
}
}
});
// Phase 2: process the instructions in the work list until all of the work is
// done. This time we add all users to the work list because phase 1
// has already finished.
for (size_t i = 0; i < work_list.size(); ++i) {
Instruction* inst = work_list[i];
in_work_list.erase(inst);
inst_seen.insert(inst);
bool is_foldable_copy =
inst->opcode() == SpvOpCopyObject &&
context()->get_decoration_mgr()->HaveSubsetOfDecorations(
inst->result_id(), inst->GetSingleWordInOperand(0));
if (is_foldable_copy || folder.FoldInstruction(inst)) {
modified = true;
context()->AnalyzeUses(inst);
get_def_use_mgr()->ForEachUser(
inst, [&work_list, &in_work_list](Instruction* use) {
if (!use->IsDecoration() && use->opcode() != SpvOpName &&
in_work_list.insert(use).second) {
work_list.push_back(use);
}
});
AddNewOperands(inst, &inst_seen, &work_list);
if (inst->opcode() == SpvOpCopyObject) {
context()->ReplaceAllUsesWithPredicate(
inst->result_id(), inst->GetSingleWordInOperand(0),
[](Instruction* user) {
const auto opcode = user->opcode();
if (!spvOpcodeIsDebug(opcode) && !spvOpcodeIsDecoration(opcode)) {
return true;
}
return false;
});
inst_to_kill.insert(inst);
in_work_list.insert(inst);
} else if (inst->opcode() == SpvOpNop) {
inst_to_kill.insert(inst);
in_work_list.insert(inst);
}
}
}
// Phase 3: Kill instructions we know are no longer needed.
for (Instruction* inst : inst_to_kill) {
context()->KillInst(inst);
}
return modified;
}
} // namespace opt
} // namespace spvtools