source/opt/instruction_list.cpp \
source/opt/ir_context.cpp \
source/opt/ir_loader.cpp \
+ source/opt/licm_pass.cpp \
source/opt/local_access_chain_convert_pass.cpp \
source/opt/local_redundancy_elimination.cpp \
source/opt/local_single_block_elim_pass.cpp \
// same value, and remove the redundant ones.
Optimizer::PassToken CreateLocalRedundancyEliminationPass();
+// Create LICM pass.
+// This pass will look for invariant instructions inside loops and hoist them to
+// the loops preheader.
+Optimizer::PassToken CreateLoopInvariantCodeMotionPass();
+
// Create global value numbering pass.
// This pass will look for instructions where the same value is computed on all
// paths leading to the instruction. Those instructions are deleted.
instruction.h
ir_context.h
ir_loader.h
+ licm_pass.h
local_access_chain_convert_pass.h
local_redundancy_elimination.h
local_single_block_elim_pass.h
instruction_list.cpp
ir_context.cpp
ir_loader.cpp
+ licm_pass.cpp
local_access_chain_convert_pass.cpp
local_redundancy_elimination.cpp
local_single_block_elim_pass.cpp
const ir::BasicBlock* pred_blk = block(id);
bool has_branch = false;
pred_blk->ForEachSuccessorLabel([&has_branch, blk_id](uint32_t succ) {
- if (succ == blk_id) has_branch = true;
+ if (succ == blk_id) {
+ has_branch = true;
+ }
});
if (has_branch) updated_pred_list.push_back(id);
}
return str;
}
+bool Instruction::IsOpcodeCodeMotionSafe() const {
+ switch (opcode_) {
+ case SpvOpVectorExtractDynamic:
+ case SpvOpVectorInsertDynamic:
+ case SpvOpVectorShuffle:
+ case SpvOpConvertFToU:
+ case SpvOpConvertFToS:
+ case SpvOpConvertSToF:
+ case SpvOpConvertUToF:
+ case SpvOpUConvert:
+ case SpvOpSConvert:
+ case SpvOpFConvert:
+ case SpvOpQuantizeToF16:
+ case SpvOpBitcast:
+ case SpvOpSNegate:
+ case SpvOpFNegate:
+ case SpvOpIAdd:
+ case SpvOpFAdd:
+ case SpvOpISub:
+ case SpvOpFSub:
+ case SpvOpIMul:
+ case SpvOpFMul:
+ case SpvOpUDiv:
+ case SpvOpSDiv:
+ case SpvOpFDiv:
+ case SpvOpUMod:
+ case SpvOpSRem:
+ case SpvOpSMod:
+ case SpvOpFRem:
+ case SpvOpFMod:
+ case SpvOpVectorTimesScalar:
+ case SpvOpMatrixTimesScalar:
+ case SpvOpVectorTimesMatrix:
+ case SpvOpMatrixTimesVector:
+ case SpvOpMatrixTimesMatrix:
+ case SpvOpLogicalEqual:
+ case SpvOpLogicalNotEqual:
+ case SpvOpLogicalOr:
+ case SpvOpLogicalAnd:
+ case SpvOpLogicalNot:
+ case SpvOpIEqual:
+ case SpvOpINotEqual:
+ case SpvOpUGreaterThan:
+ case SpvOpSGreaterThan:
+ case SpvOpUGreaterThanEqual:
+ case SpvOpSGreaterThanEqual:
+ case SpvOpULessThan:
+ case SpvOpSLessThan:
+ case SpvOpULessThanEqual:
+ case SpvOpSLessThanEqual:
+ case SpvOpFOrdEqual:
+ case SpvOpFUnordEqual:
+ case SpvOpFOrdNotEqual:
+ case SpvOpFUnordNotEqual:
+ case SpvOpFOrdLessThan:
+ case SpvOpFUnordLessThan:
+ case SpvOpFOrdGreaterThan:
+ case SpvOpFUnordGreaterThan:
+ case SpvOpFOrdLessThanEqual:
+ case SpvOpFUnordLessThanEqual:
+ case SpvOpFOrdGreaterThanEqual:
+ case SpvOpFUnordGreaterThanEqual:
+ case SpvOpShiftRightLogical:
+ case SpvOpShiftRightArithmetic:
+ case SpvOpShiftLeftLogical:
+ case SpvOpBitwiseOr:
+ case SpvOpBitwiseXor:
+ case SpvOpBitwiseAnd:
+ case SpvOpNot:
+ return true;
+ default:
+ return false;
+ }
+}
+
} // namespace ir
} // namespace spvtools
// Spec constant.
inline bool IsConstant() const;
+ // Returns true if |this| is an instruction with an opcode safe to move
+ bool IsOpcodeCodeMotionSafe() const;
+
// Pretty-prints |inst|.
//
// Provides the disassembly of a specific instruction. Utilizes |inst|'s
--- /dev/null
+// 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 "opt/licm_pass.h"
+#include "opt/module.h"
+#include "opt/pass.h"
+
+#include <queue>
+#include <utility>
+
+namespace spvtools {
+namespace opt {
+
+Pass::Status LICMPass::Process(ir::IRContext* c) {
+ InitializeProcessing(c);
+ bool modified = false;
+
+ if (c != nullptr) {
+ modified = ProcessIRContext();
+ }
+
+ return modified ? Status::SuccessWithChange : Status::SuccessWithoutChange;
+}
+
+bool LICMPass::ProcessIRContext() {
+ bool modified = false;
+ ir::Module* module = get_module();
+
+ // Process each function in the module
+ for (ir::Function& f : *module) {
+ modified |= ProcessFunction(&f);
+ }
+ return modified;
+}
+
+bool LICMPass::ProcessFunction(ir::Function* f) {
+ bool modified = false;
+ ir::LoopDescriptor* loop_descriptor = context()->GetLoopDescriptor(f);
+
+ // Process each loop in the function
+ for (ir::Loop& loop : *loop_descriptor) {
+ // Ignore nested loops, as we will process them in order in ProcessLoop
+ if (loop.IsNested()) {
+ continue;
+ }
+ modified |= ProcessLoop(&loop, f);
+ }
+ return modified;
+}
+
+bool LICMPass::ProcessLoop(ir::Loop* loop, ir::Function* f) {
+ bool modified = false;
+
+ // Process all nested loops first
+ for (ir::Loop* nested_loop : *loop) {
+ modified |= ProcessLoop(nested_loop, f);
+ }
+
+ std::vector<ir::BasicBlock*> loop_bbs{};
+ modified |= AnalyseAndHoistFromBB(loop, f, loop->GetHeaderBlock(), &loop_bbs);
+
+ for (size_t i = 0; i < loop_bbs.size(); ++i) {
+ ir::BasicBlock* bb = loop_bbs[i];
+ // do not delete the element
+ modified |= AnalyseAndHoistFromBB(loop, f, bb, &loop_bbs);
+ }
+
+ return modified;
+}
+
+bool LICMPass::AnalyseAndHoistFromBB(ir::Loop* loop, ir::Function* f,
+ ir::BasicBlock* bb,
+ std::vector<ir::BasicBlock*>* loop_bbs) {
+ bool modified = false;
+ std::function<void(ir::Instruction*)> hoist_inst =
+ [this, &loop, &modified](ir::Instruction* inst) {
+ if (loop->ShouldHoistInstruction(this->context(), inst)) {
+ HoistInstruction(loop, inst);
+ modified = true;
+ }
+ };
+
+ if (IsImmediatelyContainedInLoop(loop, f, bb)) {
+ bb->ForEachInst(hoist_inst, false);
+ }
+
+ opt::DominatorAnalysis* dom_analysis =
+ context()->GetDominatorAnalysis(f, *cfg());
+ opt::DominatorTree& dom_tree = dom_analysis->GetDomTree();
+
+ for (opt::DominatorTreeNode* child_dom_tree_node :
+ *dom_tree.GetTreeNode(bb)) {
+ if (loop->IsInsideLoop(child_dom_tree_node->bb_)) {
+ loop_bbs->push_back(child_dom_tree_node->bb_);
+ }
+ }
+
+ return modified;
+}
+
+bool LICMPass::IsImmediatelyContainedInLoop(ir::Loop* loop, ir::Function* f,
+ ir::BasicBlock* bb) {
+ ir::LoopDescriptor* loop_descriptor = context()->GetLoopDescriptor(f);
+ return loop == (*loop_descriptor)[bb->id()];
+}
+
+void LICMPass::HoistInstruction(ir::Loop* loop, ir::Instruction* inst) {
+ ir::BasicBlock* pre_header_bb = loop->GetOrCreatePreHeaderBlock();
+ inst->InsertBefore(std::move(&(*pre_header_bb->tail())));
+ context()->set_instr_block(inst, pre_header_bb);
+}
+
+} // namespace opt
+} // namespace spvtools
--- /dev/null
+// 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.
+
+#ifndef SOURCE_OPT_LICM_PASS_H_
+#define SOURCE_OPT_LICM_PASS_H_
+
+#include "opt/basic_block.h"
+#include "opt/instruction.h"
+#include "opt/loop_descriptor.h"
+#include "opt/pass.h"
+
+#include <queue>
+
+namespace spvtools {
+namespace opt {
+
+class LICMPass : public Pass {
+ public:
+ LICMPass() {}
+
+ const char* name() const override { return "loop-invariant-code-motion"; }
+ Status Process(ir::IRContext*) override;
+
+ private:
+ // Searches the IRContext for functions and processes each, moving invariants
+ // outside loops within the function where possible
+ // Returns true if a change was made to a function within the IRContext
+ bool ProcessIRContext();
+
+ // Checks the function for loops, calling ProcessLoop on each one found.
+ // Returns true if a change was made to the function, false otherwise.
+ bool ProcessFunction(ir::Function* f);
+
+ // Checks for invariants in the loop and attempts to move them to the loops
+ // preheader. Works from inner loop to outer when nested loops are found.
+ // Returns true if a change was made to the loop, false otherwise.
+ bool ProcessLoop(ir::Loop* loop, ir::Function* f);
+
+ // Analyses each instruction in |bb|, hoisting invariants to |pre_header_bb|.
+ // Each child of |bb| wrt to |dom_tree| is pushed to |loop_bbs|
+ bool AnalyseAndHoistFromBB(ir::Loop* loop, ir::Function* f,
+ ir::BasicBlock* bb,
+ std::vector<ir::BasicBlock*>* loop_bbs);
+
+ // Returns true if |bb| is immediately contained in |loop|
+ bool IsImmediatelyContainedInLoop(ir::Loop* loop, ir::Function* f,
+ ir::BasicBlock* bb);
+
+ // Move the instruction to the given BasicBlock
+ // This method will update the instruction to block mapping for the context
+ void HoistInstruction(ir::Loop* loop, ir::Instruction* inst);
+};
+
+} // namespace opt
+} // namespace spvtools
+
+#endif // SOURCE_OPT_LICM_PASS_H_
Loop::Loop(IRContext* context, opt::DominatorAnalysis* dom_analysis,
BasicBlock* header, BasicBlock* continue_target,
BasicBlock* merge_target)
- : loop_header_(header),
+ : context_(context),
+ loop_header_(header),
loop_continue_(continue_target),
loop_merge_(merge_target),
loop_preheader_(nullptr),
parent_(nullptr) {
assert(context);
assert(dom_analysis);
- loop_preheader_ = FindLoopPreheader(context, dom_analysis);
+ loop_preheader_ = FindLoopPreheader(dom_analysis);
AddBasicBlockToLoop(header);
AddBasicBlockToLoop(continue_target);
}
-BasicBlock* Loop::FindLoopPreheader(IRContext* ir_context,
- opt::DominatorAnalysis* dom_analysis) {
- CFG* cfg = ir_context->cfg();
+BasicBlock* Loop::FindLoopPreheader(opt::DominatorAnalysis* dom_analysis) {
+ CFG* cfg = context_->cfg();
opt::DominatorTree& dom_tree = dom_analysis->GetDomTree();
opt::DominatorTreeNode* header_node = dom_tree.GetTreeNode(loop_header_);
}
bool Loop::IsInsideLoop(Instruction* inst) const {
- const BasicBlock* parent_block = inst->context()->get_instr_block(inst);
+ const BasicBlock* parent_block = context_->get_instr_block(inst);
if (!parent_block) return false;
return IsInsideLoop(parent_block);
}
bool Loop::IsBasicBlockInLoopSlow(const BasicBlock* bb) {
assert(bb->GetParent() && "The basic block does not belong to a function");
- IRContext* context = bb->GetParent()->GetParent()->context();
opt::DominatorAnalysis* dom_analysis =
- context->GetDominatorAnalysis(bb->GetParent(), *context->cfg());
+ context_->GetDominatorAnalysis(bb->GetParent(), *context_->cfg());
if (!dom_analysis->Dominates(GetHeaderBlock(), bb)) return false;
opt::PostDominatorAnalysis* postdom_analysis =
- context->GetPostDominatorAnalysis(bb->GetParent(), *context->cfg());
+ context_->GetPostDominatorAnalysis(bb->GetParent(), *context_->cfg());
if (!postdom_analysis->Dominates(GetMergeBlock(), bb)) return false;
return true;
}
-BasicBlock* Loop::GetOrCreatePreHeaderBlock(ir::IRContext* context) {
+BasicBlock* Loop::GetOrCreatePreHeaderBlock() {
if (loop_preheader_) return loop_preheader_;
Function* fn = loop_header_->GetParent();
// Create the preheader basic block.
loop_preheader_ = &*header_it.InsertBefore(std::unique_ptr<ir::BasicBlock>(
new ir::BasicBlock(std::unique_ptr<ir::Instruction>(new ir::Instruction(
- context, SpvOpLabel, 0, context->TakeNextId(), {})))));
+ context_, SpvOpLabel, 0, context_->TakeNextId(), {})))));
loop_preheader_->SetParent(fn);
uint32_t loop_preheader_id = loop_preheader_->id();
// instruction;
// - Redirect all edges coming from outside the loop to the preheader.
opt::InstructionBuilder builder(
- context, loop_preheader_,
+ context_, loop_preheader_,
ir::IRContext::kAnalysisDefUse |
ir::IRContext::kAnalysisInstrToBlockMapping);
// Patch all the phi instructions.
- loop_header_->ForEachPhiInst([&builder, context, this](Instruction* phi) {
+ loop_header_->ForEachPhiInst([&builder, this](Instruction* phi) {
std::vector<uint32_t> preheader_phi_ops;
std::vector<uint32_t> header_phi_ops;
for (uint32_t i = 0; i < phi->NumInOperands(); i += 2) {
preheader_insn_def = builder.AddPhi(phi->type_id(), preheader_phi_ops);
else
preheader_insn_def =
- context->get_def_use_mgr()->GetDef(preheader_phi_ops[0]);
+ context_->get_def_use_mgr()->GetDef(preheader_phi_ops[0]);
// Build the new incoming edge.
header_phi_ops.push_back(preheader_insn_def->result_id());
header_phi_ops.push_back(loop_preheader_->id());
builder.AddBranch(loop_header_->id());
// Redirect all out of loop branches to the header to the preheader.
- CFG* cfg = context->cfg();
+ CFG* cfg = context_->cfg();
cfg->RegisterBlock(loop_preheader_);
for (uint32_t pred_id : cfg->preds(loop_header_->id())) {
if (pred_id == loop_preheader_->id()) continue;
// Update the loop descriptors.
if (HasParent()) {
GetParent()->AddBasicBlock(loop_preheader_);
- context->GetLoopDescriptor(fn)->SetBasicBlockToLoop(loop_preheader_->id(),
- GetParent());
+ context_->GetLoopDescriptor(fn)->SetBasicBlockToLoop(loop_preheader_->id(),
+ GetParent());
}
- context->InvalidateAnalysesExceptFor(
+ context_->InvalidateAnalysesExceptFor(
builder.GetPreservedAnalysis() |
ir::IRContext::Analysis::kAnalysisLoopAnalysis |
ir::IRContext::kAnalysisCFG);
assert(IsInsideLoop(pred) &&
"A predecessor of the merge block does not belong to the loop");
}
-#endif // NDEBUG
assert(!IsInsideLoop(merge) && "The merge block is in the loop");
+#endif // NDEBUG
SetMergeBlockImpl(merge);
if (GetHeaderBlock()->GetLoopMergeInst()) {
}
}
-void Loop::GetExitBlocks(IRContext* context,
- std::unordered_set<uint32_t>* exit_blocks) const {
- ir::CFG* cfg = context->cfg();
+void Loop::GetExitBlocks(std::unordered_set<uint32_t>* exit_blocks) const {
+ ir::CFG* cfg = context_->cfg();
+ exit_blocks->clear();
for (uint32_t bb_id : GetBlocks()) {
const spvtools::ir::BasicBlock* bb = cfg->block(bb_id);
}
void Loop::GetMergingBlocks(
- IRContext* context, std::unordered_set<uint32_t>* merging_blocks) const {
+ std::unordered_set<uint32_t>* merging_blocks) const {
assert(GetMergeBlock() && "This loop is not structured");
- ir::CFG* cfg = context->cfg();
+ ir::CFG* cfg = context_->cfg();
+ merging_blocks->clear();
std::stack<const ir::BasicBlock*> to_visit;
to_visit.push(GetMergeBlock());
}
bool Loop::IsLCSSA() const {
- IRContext* context = GetHeaderBlock()->GetParent()->GetParent()->context();
- ir::CFG* cfg = context->cfg();
- opt::analysis::DefUseManager* def_use_mgr = context->get_def_use_mgr();
+ ir::CFG* cfg = context_->cfg();
+ opt::analysis::DefUseManager* def_use_mgr = context_->get_def_use_mgr();
std::unordered_set<uint32_t> exit_blocks;
- GetExitBlocks(context, &exit_blocks);
+ GetExitBlocks(&exit_blocks);
+
+ // Declare ir_context so we can capture context_ in the below lambda
+ ir::IRContext* ir_context = context_;
for (uint32_t bb_id : GetBlocks()) {
for (Instruction& insn : *cfg->block(bb_id)) {
// - In an exit block and in a phi instruction.
if (!def_use_mgr->WhileEachUser(
&insn,
- [&exit_blocks, context, this](ir::Instruction* use) -> bool {
- BasicBlock* parent = context->get_instr_block(use);
+ [&exit_blocks, ir_context, this](ir::Instruction* use) -> bool {
+ BasicBlock* parent = ir_context->get_instr_block(use);
assert(parent && "Invalid analysis");
if (IsInsideLoop(parent)) return true;
if (use->opcode() != SpvOpPhi) return false;
return true;
}
+bool Loop::ShouldHoistInstruction(IRContext* context, Instruction* inst) {
+ return AreAllOperandsOutsideLoop(context, inst) &&
+ inst->IsOpcodeCodeMotionSafe();
+}
+
+bool Loop::AreAllOperandsOutsideLoop(IRContext* context, Instruction* inst) {
+ opt::analysis::DefUseManager* def_use_mgr = context->get_def_use_mgr();
+ bool all_outside_loop = true;
+
+ const std::function<void(uint32_t*)> operand_outside_loop =
+ [this, &def_use_mgr, &all_outside_loop](uint32_t* id) {
+ if (this->IsInsideLoop(def_use_mgr->GetDef(*id))) {
+ all_outside_loop = false;
+ return;
+ }
+ };
+
+ inst->ForEachInId(operand_outside_loop);
+ return all_outside_loop;
+}
+
LoopDescriptor::LoopDescriptor(const Function* f) : loops_() {
PopulateList(f);
}
void LoopDescriptor::PopulateList(const Function* f) {
IRContext* context = f->GetParent()->context();
-
opt::DominatorAnalysis* dom_analysis =
context->GetDominatorAnalysis(f, *context->cfg());
using BasicBlockListTy = std::unordered_set<uint32_t>;
Loop()
- : loop_header_(nullptr),
+ : context_(nullptr),
+ loop_header_(nullptr),
loop_continue_(nullptr),
loop_merge_(nullptr),
loop_preheader_(nullptr),
// Returns the loop pre-header, if there is no suitable preheader it will be
// created.
- BasicBlock* GetOrCreatePreHeaderBlock(ir::IRContext* context);
+ BasicBlock* GetOrCreatePreHeaderBlock();
// Returns true if this loop contains any nested loops.
inline bool HasNestedLoops() const { return nested_loops_.size() != 0; }
- // Fills |exit_blocks| with all basic blocks that are not in the loop and has
- // at least one predecessor in the loop.
- void GetExitBlocks(IRContext* context,
- std::unordered_set<uint32_t>* exit_blocks) const;
+ // Clears and fills |exit_blocks| with all basic blocks that are not in the
+ // loop and has at least one predecessor in the loop.
+ void GetExitBlocks(std::unordered_set<uint32_t>* exit_blocks) const;
- // Fills |merging_blocks| with all basic blocks that are post-dominated by the
- // merge block. The merge block must exist.
+ // Clears and fills |merging_blocks| with all basic blocks that are
+ // post-dominated by the merge block. The merge block must exist.
// The set |merging_blocks| will only contain the merge block if it is
// unreachable.
- void GetMergingBlocks(IRContext* context,
- std::unordered_set<uint32_t>* merging_blocks) const;
+ void GetMergingBlocks(std::unordered_set<uint32_t>* merging_blocks) const;
// Returns true if the loop is in a Loop Closed SSA form.
// In LCSSA form, all in-loop definitions are used in the loop or in phi
// as a nested child loop.
inline void SetParent(Loop* parent) { parent_ = parent; }
+ // Returns true is the instruction is invariant and safe to move wrt loop
+ bool ShouldHoistInstruction(IRContext* context, Instruction* inst);
+
+ // Returns true if all operands of inst are in basic blocks not contained in
+ // loop
+ bool AreAllOperandsOutsideLoop(IRContext* context, Instruction* inst);
+
private:
+ IRContext* context_;
// The block which marks the start of the loop.
BasicBlock* loop_header_;
bool IsBasicBlockInLoopSlow(const BasicBlock* bb);
// Returns the loop preheader if it exists, returns nullptr otherwise.
- BasicBlock* FindLoopPreheader(IRContext* context,
- opt::DominatorAnalysis* dom_analysis);
+ BasicBlock* FindLoopPreheader(opt::DominatorAnalysis* dom_analysis);
// Sets |latch| as the loop unique continue block. No checks are performed
// here.
other.loops_.clear();
basic_block_to_loop_ = std::move(other.basic_block_to_loop_);
other.basic_block_to_loop_.clear();
+ dummy_top_loop_ = std::move(other.dummy_top_loop_);
}
// Destructor
// Gathers the set of basic block that are not in this loop and have at least
// one predecessor in the loop and one not in the loop.
std::unordered_set<uint32_t> exit_bb_set;
- loop_->GetExitBlocks(context_, &exit_bb_set);
+ loop_->GetExitBlocks(&exit_bb_set);
std::unordered_set<ir::BasicBlock*> new_loop_exits;
bool made_change = false;
std::unordered_set<ir::BasicBlock*> exit_bb;
{
std::unordered_set<uint32_t> exit_bb_id;
- loop_->GetExitBlocks(context_, &exit_bb_id);
+ loop_->GetExitBlocks(&exit_bb_id);
for (uint32_t bb_id : exit_bb_id) {
exit_bb.insert(cfg.block(bb_id));
}
// further than the merge block.
if (loop_->GetMergeBlock()) {
std::unordered_set<uint32_t> merging_bb_id;
- loop_->GetMergingBlocks(context_, &merging_bb_id);
+ loop_->GetMergingBlocks(&merging_bb_id);
merging_bb_id.erase(loop_->GetMergeBlock()->id());
// Reset the exit set, now only the merge block is the exit.
exit_bb.clear();
LoopUtils(ir::IRContext* context, ir::Loop* loop)
: context_(context), loop_(loop) {}
- // The make the current loop in the loop closed SSA form.
- // In the loop closed SSA, all loop exiting values goes through a dedicate SSA
+ // The converts the current loop to loop closed SSA form.
+ // In the loop closed SSA, all loop exiting values go through a dedicated Phi
// instruction. For instance:
//
// for (...) {
MakeUnique<opt::LocalRedundancyEliminationPass>());
}
+Optimizer::PassToken CreateLoopInvariantCodeMotionPass() {
+ return MakeUnique<Optimizer::PassToken::Impl>(MakeUnique<opt::LICMPass>());
+}
+
Optimizer::PassToken CreateRedundancyEliminationPass() {
return MakeUnique<Optimizer::PassToken::Impl>(
MakeUnique<opt::RedundancyEliminationPass>());
#include "inline_exhaustive_pass.h"
#include "inline_opaque_pass.h"
#include "insert_extract_elim.h"
+#include "licm_pass.h"
#include "local_access_chain_convert_pass.h"
#include "local_redundancy_elimination.h"
#include "local_single_block_elim_pass.h"
lcssa.cpp
LIBS SPIRV-Tools-opt
)
+
+add_spvtools_unittest(TARGET licm_all_loop_types
+ SRCS ../function_utils.h
+ hoist_all_loop_types.cpp
+ LIBS SPIRV-Tools-opt
+)
+
+add_spvtools_unittest(TARGET licm_hoist_independent_loops
+ SRCS ../function_utils.h
+ hoist_from_independent_loops.cpp
+ LIBS SPIRV-Tools-opt
+)
+
+add_spvtools_unittest(TARGET licm_hoist_double_nested_loops
+ SRCS ../function_utils.h
+ hoist_double_nested_loops.cpp
+ LIBS SPIRV-Tools-opt
+)
+
+add_spvtools_unittest(TARGET licm_hoist_single_nested_loops
+ SRCS ../function_utils.h
+ hoist_single_nested_loops.cpp
+ LIBS SPIRV-Tools-opt
+)
+
+add_spvtools_unittest(TARGET licm_hoist_simple_case
+ SRCS ../function_utils.h
+ hoist_simple_case.cpp
+ LIBS SPIRV-Tools-opt
+)
+
+add_spvtools_unittest(TARGET licm_hoist_no_preheader
+ SRCS ../function_utils.h
+ hoist_without_preheader.cpp
+ LIBS SPIRV-Tools-opt
+)
--- /dev/null
+// 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 <string>
+
+#include <gmock/gmock.h>
+
+#include "../pass_fixture.h"
+#include "opt/licm_pass.h"
+
+namespace {
+
+using namespace spvtools;
+using ::testing::UnorderedElementsAre;
+
+using PassClassTest = PassTest<::testing::Test>;
+
+/*
+ Tests that all loop types are handled appropriately by the LICM pass.
+
+ Generated from the following GLSL fragment shader
+--eliminate-local-multi-store has also been run on the spv binary
+#version 440 core
+void main(){
+ int i_1 = 0;
+ for (i_1 = 0; i_1 < 10; i_1++) {
+ }
+ int i_2 = 0;
+ while (i_2 < 10) {
+ i_2++;
+ }
+ int i_3 = 0;
+ do {
+ i_3++;
+ } while (i_3 < 10);
+ int hoist = 0;
+ int i_4 = 0;
+ int i_5 = 0;
+ int i_6 = 0;
+ for (i_4 = 0; i_4 < 10; i_4++) {
+ while (i_5 < 10) {
+ do {
+ hoist = i_1 + i_2 + i_3;
+ i_6++;
+ } while (i_6 < 10);
+ i_5++;
+ }
+ }
+}
+*/
+TEST_F(PassClassTest, AllLoopTypes) {
+ const std::string before_hoist = R"(OpCapability Shader
+%1 = OpExtInstImport "GLSL.std.450"
+OpMemoryModel Logical GLSL450
+OpEntryPoint Fragment %main "main"
+OpExecutionMode %main OriginUpperLeft
+OpSource GLSL 440
+OpName %main "main"
+%void = OpTypeVoid
+%4 = OpTypeFunction %void
+%int = OpTypeInt 32 1
+%_ptr_Function_int = OpTypePointer Function %int
+%int_0 = OpConstant %int 0
+%int_10 = OpConstant %int 10
+%bool = OpTypeBool
+%int_1 = OpConstant %int 1
+%main = OpFunction %void None %4
+%11 = OpLabel
+OpBranch %12
+%12 = OpLabel
+%13 = OpPhi %int %int_0 %11 %14 %15
+OpLoopMerge %16 %15 None
+OpBranch %17
+%17 = OpLabel
+%18 = OpSLessThan %bool %13 %int_10
+OpBranchConditional %18 %19 %16
+%19 = OpLabel
+OpBranch %15
+%15 = OpLabel
+%14 = OpIAdd %int %13 %int_1
+OpBranch %12
+%16 = OpLabel
+OpBranch %20
+%20 = OpLabel
+%21 = OpPhi %int %int_0 %16 %22 %23
+OpLoopMerge %24 %23 None
+OpBranch %25
+%25 = OpLabel
+%26 = OpSLessThan %bool %21 %int_10
+OpBranchConditional %26 %27 %24
+%27 = OpLabel
+%22 = OpIAdd %int %21 %int_1
+OpBranch %23
+%23 = OpLabel
+OpBranch %20
+%24 = OpLabel
+OpBranch %28
+%28 = OpLabel
+%29 = OpPhi %int %int_0 %24 %30 %31
+OpLoopMerge %32 %31 None
+OpBranch %33
+%33 = OpLabel
+%30 = OpIAdd %int %29 %int_1
+OpBranch %31
+%31 = OpLabel
+%34 = OpSLessThan %bool %30 %int_10
+OpBranchConditional %34 %28 %32
+%32 = OpLabel
+OpBranch %35
+%35 = OpLabel
+%36 = OpPhi %int %int_0 %32 %37 %38
+%39 = OpPhi %int %int_0 %32 %40 %38
+%41 = OpPhi %int %int_0 %32 %42 %38
+%43 = OpPhi %int %int_0 %32 %44 %38
+OpLoopMerge %45 %38 None
+OpBranch %46
+%46 = OpLabel
+%47 = OpSLessThan %bool %39 %int_10
+OpBranchConditional %47 %48 %45
+%48 = OpLabel
+OpBranch %49
+%49 = OpLabel
+%37 = OpPhi %int %36 %48 %50 %51
+%42 = OpPhi %int %41 %48 %52 %51
+%44 = OpPhi %int %43 %48 %53 %51
+OpLoopMerge %54 %51 None
+OpBranch %55
+%55 = OpLabel
+%56 = OpSLessThan %bool %42 %int_10
+OpBranchConditional %56 %57 %54
+%57 = OpLabel
+OpBranch %58
+%58 = OpLabel
+%59 = OpPhi %int %37 %57 %50 %60
+%61 = OpPhi %int %44 %57 %53 %60
+OpLoopMerge %62 %60 None
+OpBranch %63
+%63 = OpLabel
+%64 = OpIAdd %int %13 %21
+%50 = OpIAdd %int %64 %30
+%53 = OpIAdd %int %61 %int_1
+OpBranch %60
+%60 = OpLabel
+%65 = OpSLessThan %bool %53 %int_10
+OpBranchConditional %65 %58 %62
+%62 = OpLabel
+%52 = OpIAdd %int %42 %int_1
+OpBranch %51
+%51 = OpLabel
+OpBranch %49
+%54 = OpLabel
+OpBranch %38
+%38 = OpLabel
+%40 = OpIAdd %int %39 %int_1
+OpBranch %35
+%45 = OpLabel
+OpReturn
+OpFunctionEnd
+)";
+
+ const std::string after_hoist = R"(OpCapability Shader
+%1 = OpExtInstImport "GLSL.std.450"
+OpMemoryModel Logical GLSL450
+OpEntryPoint Fragment %main "main"
+OpExecutionMode %main OriginUpperLeft
+OpSource GLSL 440
+OpName %main "main"
+%void = OpTypeVoid
+%4 = OpTypeFunction %void
+%int = OpTypeInt 32 1
+%_ptr_Function_int = OpTypePointer Function %int
+%int_0 = OpConstant %int 0
+%int_10 = OpConstant %int 10
+%bool = OpTypeBool
+%int_1 = OpConstant %int 1
+%main = OpFunction %void None %4
+%11 = OpLabel
+OpBranch %12
+%12 = OpLabel
+%13 = OpPhi %int %int_0 %11 %14 %15
+OpLoopMerge %16 %15 None
+OpBranch %17
+%17 = OpLabel
+%18 = OpSLessThan %bool %13 %int_10
+OpBranchConditional %18 %19 %16
+%19 = OpLabel
+OpBranch %15
+%15 = OpLabel
+%14 = OpIAdd %int %13 %int_1
+OpBranch %12
+%16 = OpLabel
+OpBranch %20
+%20 = OpLabel
+%21 = OpPhi %int %int_0 %16 %22 %23
+OpLoopMerge %24 %23 None
+OpBranch %25
+%25 = OpLabel
+%26 = OpSLessThan %bool %21 %int_10
+OpBranchConditional %26 %27 %24
+%27 = OpLabel
+%22 = OpIAdd %int %21 %int_1
+OpBranch %23
+%23 = OpLabel
+OpBranch %20
+%24 = OpLabel
+OpBranch %28
+%28 = OpLabel
+%29 = OpPhi %int %int_0 %24 %30 %31
+OpLoopMerge %32 %31 None
+OpBranch %33
+%33 = OpLabel
+%30 = OpIAdd %int %29 %int_1
+OpBranch %31
+%31 = OpLabel
+%34 = OpSLessThan %bool %30 %int_10
+OpBranchConditional %34 %28 %32
+%32 = OpLabel
+%64 = OpIAdd %int %13 %21
+%50 = OpIAdd %int %64 %30
+OpBranch %35
+%35 = OpLabel
+%36 = OpPhi %int %int_0 %32 %37 %38
+%39 = OpPhi %int %int_0 %32 %40 %38
+%41 = OpPhi %int %int_0 %32 %42 %38
+%43 = OpPhi %int %int_0 %32 %44 %38
+OpLoopMerge %45 %38 None
+OpBranch %46
+%46 = OpLabel
+%47 = OpSLessThan %bool %39 %int_10
+OpBranchConditional %47 %48 %45
+%48 = OpLabel
+OpBranch %49
+%49 = OpLabel
+%37 = OpPhi %int %36 %48 %50 %51
+%42 = OpPhi %int %41 %48 %52 %51
+%44 = OpPhi %int %43 %48 %53 %51
+OpLoopMerge %54 %51 None
+OpBranch %55
+%55 = OpLabel
+%56 = OpSLessThan %bool %42 %int_10
+OpBranchConditional %56 %57 %54
+%57 = OpLabel
+OpBranch %58
+%58 = OpLabel
+%59 = OpPhi %int %37 %57 %50 %60
+%61 = OpPhi %int %44 %57 %53 %60
+OpLoopMerge %62 %60 None
+OpBranch %63
+%63 = OpLabel
+%53 = OpIAdd %int %61 %int_1
+OpBranch %60
+%60 = OpLabel
+%65 = OpSLessThan %bool %53 %int_10
+OpBranchConditional %65 %58 %62
+%62 = OpLabel
+%52 = OpIAdd %int %42 %int_1
+OpBranch %51
+%51 = OpLabel
+OpBranch %49
+%54 = OpLabel
+OpBranch %38
+%38 = OpLabel
+%40 = OpIAdd %int %39 %int_1
+OpBranch %35
+%45 = OpLabel
+OpReturn
+OpFunctionEnd
+)";
+
+ SinglePassRunAndCheck<opt::LICMPass>(before_hoist, after_hoist, true);
+}
+
+} // namespace
--- /dev/null
+// 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 <string>
+
+#include <gmock/gmock.h>
+
+#include "../pass_fixture.h"
+#include "opt/licm_pass.h"
+
+namespace {
+
+using namespace spvtools;
+using ::testing::UnorderedElementsAre;
+
+using PassClassTest = PassTest<::testing::Test>;
+
+/*
+ Tests that the LICM pass will move invariants through multiple loops
+
+ Generated from the following GLSL fragment shader
+--eliminate-local-multi-store has also been run on the spv binary
+#version 440 core
+void main(){
+ int a = 2;
+ int b = 1;
+ int hoist = 0;
+ for (int i = 0; i < 10; i++) {
+ for (int j = 0; j < 10; j++) {
+ // hoist 'hoist = a - b' out of both loops
+ hoist = a - b;
+ }
+ }
+}
+*/
+TEST_F(PassClassTest, NestedDoubleHoist) {
+ const std::string before_hoist = R"(OpCapability Shader
+%1 = OpExtInstImport "GLSL.std.450"
+OpMemoryModel Logical GLSL450
+OpEntryPoint Fragment %main "main"
+OpExecutionMode %main OriginUpperLeft
+OpSource GLSL 440
+OpName %main "main"
+%void = OpTypeVoid
+%4 = OpTypeFunction %void
+%int = OpTypeInt 32 1
+%_ptr_Function_int = OpTypePointer Function %int
+%int_2 = OpConstant %int 2
+%int_1 = OpConstant %int 1
+%int_0 = OpConstant %int 0
+%int_10 = OpConstant %int 10
+%bool = OpTypeBool
+%12 = OpUndef %int
+%main = OpFunction %void None %4
+%13 = OpLabel
+OpBranch %14
+%14 = OpLabel
+%15 = OpPhi %int %int_0 %13 %16 %17
+%18 = OpPhi %int %int_0 %13 %19 %17
+%20 = OpPhi %int %12 %13 %21 %17
+OpLoopMerge %22 %17 None
+OpBranch %23
+%23 = OpLabel
+%24 = OpSLessThan %bool %18 %int_10
+OpBranchConditional %24 %25 %22
+%25 = OpLabel
+OpBranch %26
+%26 = OpLabel
+%16 = OpPhi %int %15 %25 %27 %28
+%21 = OpPhi %int %int_0 %25 %29 %28
+OpLoopMerge %30 %28 None
+OpBranch %31
+%31 = OpLabel
+%32 = OpSLessThan %bool %21 %int_10
+OpBranchConditional %32 %33 %30
+%33 = OpLabel
+%27 = OpISub %int %int_2 %int_1
+OpBranch %28
+%28 = OpLabel
+%29 = OpIAdd %int %21 %int_1
+OpBranch %26
+%30 = OpLabel
+OpBranch %17
+%17 = OpLabel
+%19 = OpIAdd %int %18 %int_1
+OpBranch %14
+%22 = OpLabel
+OpReturn
+OpFunctionEnd
+)";
+
+ const std::string after_hoist = R"(OpCapability Shader
+%1 = OpExtInstImport "GLSL.std.450"
+OpMemoryModel Logical GLSL450
+OpEntryPoint Fragment %main "main"
+OpExecutionMode %main OriginUpperLeft
+OpSource GLSL 440
+OpName %main "main"
+%void = OpTypeVoid
+%4 = OpTypeFunction %void
+%int = OpTypeInt 32 1
+%_ptr_Function_int = OpTypePointer Function %int
+%int_2 = OpConstant %int 2
+%int_1 = OpConstant %int 1
+%int_0 = OpConstant %int 0
+%int_10 = OpConstant %int 10
+%bool = OpTypeBool
+%12 = OpUndef %int
+%main = OpFunction %void None %4
+%13 = OpLabel
+%27 = OpISub %int %int_2 %int_1
+OpBranch %14
+%14 = OpLabel
+%15 = OpPhi %int %int_0 %13 %16 %17
+%18 = OpPhi %int %int_0 %13 %19 %17
+%20 = OpPhi %int %12 %13 %21 %17
+OpLoopMerge %22 %17 None
+OpBranch %23
+%23 = OpLabel
+%24 = OpSLessThan %bool %18 %int_10
+OpBranchConditional %24 %25 %22
+%25 = OpLabel
+OpBranch %26
+%26 = OpLabel
+%16 = OpPhi %int %15 %25 %27 %28
+%21 = OpPhi %int %int_0 %25 %29 %28
+OpLoopMerge %30 %28 None
+OpBranch %31
+%31 = OpLabel
+%32 = OpSLessThan %bool %21 %int_10
+OpBranchConditional %32 %33 %30
+%33 = OpLabel
+OpBranch %28
+%28 = OpLabel
+%29 = OpIAdd %int %21 %int_1
+OpBranch %26
+%30 = OpLabel
+OpBranch %17
+%17 = OpLabel
+%19 = OpIAdd %int %18 %int_1
+OpBranch %14
+%22 = OpLabel
+OpReturn
+OpFunctionEnd
+)";
+
+ SinglePassRunAndCheck<opt::LICMPass>(before_hoist, after_hoist, true);
+}
+
+} // namespace
--- /dev/null
+// 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 <string>
+
+#include <gmock/gmock.h>
+
+#include "../pass_fixture.h"
+#include "opt/licm_pass.h"
+
+namespace {
+
+using namespace spvtools;
+using ::testing::UnorderedElementsAre;
+
+using PassClassTest = PassTest<::testing::Test>;
+
+/*
+ Tests that the LICM pass will analyse multiple independent loops in a function
+
+ Generated from the following GLSL fragment shader
+--eliminate-local-multi-store has also been run on the spv binary
+#version 440 core
+void main(){
+ int a = 1;
+ int b = 2;
+ int hoist = 0;
+ for (int i = 0; i < 10; i++) {
+ // invariant
+ hoist = a + b;
+ }
+ for (int i = 0; i < 10; i++) {
+ // invariant
+ hoist = a + b;
+ }
+ int c = 1;
+ int d = 2;
+ int hoist2 = 0;
+ for (int i = 0; i < 10; i++) {
+ // invariant
+ hoist2 = c + d;
+ }
+}
+*/
+TEST_F(PassClassTest, HoistFromIndependentLoops) {
+ const std::string before_hoist = R"(OpCapability Shader
+%1 = OpExtInstImport "GLSL.std.450"
+OpMemoryModel Logical GLSL450
+OpEntryPoint Fragment %main "main"
+OpExecutionMode %main OriginUpperLeft
+OpSource GLSL 440
+OpName %main "main"
+%void = OpTypeVoid
+%4 = OpTypeFunction %void
+%int = OpTypeInt 32 1
+%_ptr_Function_int = OpTypePointer Function %int
+%int_1 = OpConstant %int 1
+%int_2 = OpConstant %int 2
+%int_0 = OpConstant %int 0
+%int_10 = OpConstant %int 10
+%bool = OpTypeBool
+%main = OpFunction %void None %4
+%12 = OpLabel
+OpBranch %13
+%13 = OpLabel
+%14 = OpPhi %int %int_0 %12 %15 %16
+%17 = OpPhi %int %int_0 %12 %18 %16
+OpLoopMerge %19 %16 None
+OpBranch %20
+%20 = OpLabel
+%21 = OpSLessThan %bool %17 %int_10
+OpBranchConditional %21 %22 %19
+%22 = OpLabel
+%15 = OpIAdd %int %int_1 %int_2
+OpBranch %16
+%16 = OpLabel
+%18 = OpIAdd %int %17 %int_1
+OpBranch %13
+%19 = OpLabel
+OpBranch %23
+%23 = OpLabel
+%24 = OpPhi %int %14 %19 %25 %26
+%27 = OpPhi %int %int_0 %19 %28 %26
+OpLoopMerge %29 %26 None
+OpBranch %30
+%30 = OpLabel
+%31 = OpSLessThan %bool %27 %int_10
+OpBranchConditional %31 %32 %29
+%32 = OpLabel
+%25 = OpIAdd %int %int_1 %int_2
+OpBranch %26
+%26 = OpLabel
+%28 = OpIAdd %int %27 %int_1
+OpBranch %23
+%29 = OpLabel
+OpBranch %33
+%33 = OpLabel
+%34 = OpPhi %int %int_0 %29 %35 %36
+%37 = OpPhi %int %int_0 %29 %38 %36
+OpLoopMerge %39 %36 None
+OpBranch %40
+%40 = OpLabel
+%41 = OpSLessThan %bool %37 %int_10
+OpBranchConditional %41 %42 %39
+%42 = OpLabel
+%35 = OpIAdd %int %int_1 %int_2
+OpBranch %36
+%36 = OpLabel
+%38 = OpIAdd %int %37 %int_1
+OpBranch %33
+%39 = OpLabel
+OpReturn
+OpFunctionEnd
+)";
+
+ const std::string after_hoist = R"(OpCapability Shader
+%1 = OpExtInstImport "GLSL.std.450"
+OpMemoryModel Logical GLSL450
+OpEntryPoint Fragment %main "main"
+OpExecutionMode %main OriginUpperLeft
+OpSource GLSL 440
+OpName %main "main"
+%void = OpTypeVoid
+%4 = OpTypeFunction %void
+%int = OpTypeInt 32 1
+%_ptr_Function_int = OpTypePointer Function %int
+%int_1 = OpConstant %int 1
+%int_2 = OpConstant %int 2
+%int_0 = OpConstant %int 0
+%int_10 = OpConstant %int 10
+%bool = OpTypeBool
+%main = OpFunction %void None %4
+%12 = OpLabel
+%15 = OpIAdd %int %int_1 %int_2
+OpBranch %13
+%13 = OpLabel
+%14 = OpPhi %int %int_0 %12 %15 %16
+%17 = OpPhi %int %int_0 %12 %18 %16
+OpLoopMerge %19 %16 None
+OpBranch %20
+%20 = OpLabel
+%21 = OpSLessThan %bool %17 %int_10
+OpBranchConditional %21 %22 %19
+%22 = OpLabel
+OpBranch %16
+%16 = OpLabel
+%18 = OpIAdd %int %17 %int_1
+OpBranch %13
+%19 = OpLabel
+%25 = OpIAdd %int %int_1 %int_2
+OpBranch %23
+%23 = OpLabel
+%24 = OpPhi %int %14 %19 %25 %26
+%27 = OpPhi %int %int_0 %19 %28 %26
+OpLoopMerge %29 %26 None
+OpBranch %30
+%30 = OpLabel
+%31 = OpSLessThan %bool %27 %int_10
+OpBranchConditional %31 %32 %29
+%32 = OpLabel
+OpBranch %26
+%26 = OpLabel
+%28 = OpIAdd %int %27 %int_1
+OpBranch %23
+%29 = OpLabel
+%35 = OpIAdd %int %int_1 %int_2
+OpBranch %33
+%33 = OpLabel
+%34 = OpPhi %int %int_0 %29 %35 %36
+%37 = OpPhi %int %int_0 %29 %38 %36
+OpLoopMerge %39 %36 None
+OpBranch %40
+%40 = OpLabel
+%41 = OpSLessThan %bool %37 %int_10
+OpBranchConditional %41 %42 %39
+%42 = OpLabel
+OpBranch %36
+%36 = OpLabel
+%38 = OpIAdd %int %37 %int_1
+OpBranch %33
+%39 = OpLabel
+OpReturn
+OpFunctionEnd
+)";
+
+ SinglePassRunAndCheck<opt::LICMPass>(before_hoist, after_hoist, true);
+}
+
+} // namespace
--- /dev/null
+// 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 <string>
+
+#include <gmock/gmock.h>
+
+#include "../pass_fixture.h"
+#include "opt/licm_pass.h"
+
+namespace {
+
+using namespace spvtools;
+using ::testing::UnorderedElementsAre;
+
+using PassClassTest = PassTest<::testing::Test>;
+
+/*
+ A simple test for the LICM pass
+
+ Generated from the following GLSL fragment shader
+--eliminate-local-multi-store has also been run on the spv binary
+#version 440 core
+void main(){
+ int a = 1;
+ int b = 2;
+ int hoist = 0;
+ for (int i = 0; i < 10; i++) {
+ // invariant
+ hoist = a + b;
+ }
+}
+*/
+TEST_F(PassClassTest, SimpleHoist) {
+ const std::string before_hoist = R"(OpCapability Shader
+%1 = OpExtInstImport "GLSL.std.450"
+OpMemoryModel Logical GLSL450
+OpEntryPoint Fragment %main "main"
+OpExecutionMode %main OriginUpperLeft
+OpSource GLSL 440
+OpName %main "main"
+%void = OpTypeVoid
+%4 = OpTypeFunction %void
+%int = OpTypeInt 32 1
+%_ptr_Function_int = OpTypePointer Function %int
+%int_1 = OpConstant %int 1
+%int_2 = OpConstant %int 2
+%int_0 = OpConstant %int 0
+%int_10 = OpConstant %int 10
+%bool = OpTypeBool
+%main = OpFunction %void None %4
+%12 = OpLabel
+OpBranch %13
+%13 = OpLabel
+%14 = OpPhi %int %int_0 %12 %15 %16
+%17 = OpPhi %int %int_0 %12 %18 %16
+OpLoopMerge %19 %16 None
+OpBranch %20
+%20 = OpLabel
+%21 = OpSLessThan %bool %17 %int_10
+OpBranchConditional %21 %22 %19
+%22 = OpLabel
+%15 = OpIAdd %int %int_1 %int_2
+OpBranch %16
+%16 = OpLabel
+%18 = OpIAdd %int %17 %int_1
+OpBranch %13
+%19 = OpLabel
+OpReturn
+OpFunctionEnd
+)";
+
+ const std::string after_hoist = R"(OpCapability Shader
+%1 = OpExtInstImport "GLSL.std.450"
+OpMemoryModel Logical GLSL450
+OpEntryPoint Fragment %main "main"
+OpExecutionMode %main OriginUpperLeft
+OpSource GLSL 440
+OpName %main "main"
+%void = OpTypeVoid
+%4 = OpTypeFunction %void
+%int = OpTypeInt 32 1
+%_ptr_Function_int = OpTypePointer Function %int
+%int_1 = OpConstant %int 1
+%int_2 = OpConstant %int 2
+%int_0 = OpConstant %int 0
+%int_10 = OpConstant %int 10
+%bool = OpTypeBool
+%main = OpFunction %void None %4
+%12 = OpLabel
+%15 = OpIAdd %int %int_1 %int_2
+OpBranch %13
+%13 = OpLabel
+%14 = OpPhi %int %int_0 %12 %15 %16
+%17 = OpPhi %int %int_0 %12 %18 %16
+OpLoopMerge %19 %16 None
+OpBranch %20
+%20 = OpLabel
+%21 = OpSLessThan %bool %17 %int_10
+OpBranchConditional %21 %22 %19
+%22 = OpLabel
+OpBranch %16
+%16 = OpLabel
+%18 = OpIAdd %int %17 %int_1
+OpBranch %13
+%19 = OpLabel
+OpReturn
+OpFunctionEnd
+)";
+
+ SinglePassRunAndCheck<opt::LICMPass>(before_hoist, after_hoist, true);
+}
+
+} // namespace
--- /dev/null
+// 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 <string>
+
+#include <gmock/gmock.h>
+
+#include "../pass_fixture.h"
+#include "opt/licm_pass.h"
+
+namespace {
+
+using namespace spvtools;
+using ::testing::UnorderedElementsAre;
+
+using PassClassTest = PassTest<::testing::Test>;
+
+/*
+ Tests that the LICM pass will detect an move an invariant from a nested loop,
+ but not it's parent loop
+
+ Generated from the following GLSL fragment shader
+--eliminate-local-multi-store has also been run on the spv binary
+#version 440 core
+void main(){
+ int a = 2;
+ int hoist = 0;
+ for (int i = 0; i < 10; i++) {
+ for (int j = 0; j < 10; j++) {
+ // hoist 'hoist = a - i' out of j loop, but not i loop
+ hoist = a - i;
+ }
+ }
+}
+*/
+TEST_F(PassClassTest, NestedSingleHoist) {
+ const std::string before_hoist = R"(OpCapability Shader
+%1 = OpExtInstImport "GLSL.std.450"
+OpMemoryModel Logical GLSL450
+OpEntryPoint Fragment %main "main"
+OpExecutionMode %main OriginUpperLeft
+OpSource GLSL 440
+OpName %main "main"
+%void = OpTypeVoid
+%4 = OpTypeFunction %void
+%int = OpTypeInt 32 1
+%_ptr_Function_int = OpTypePointer Function %int
+%int_2 = OpConstant %int 2
+%int_0 = OpConstant %int 0
+%int_10 = OpConstant %int 10
+%bool = OpTypeBool
+%int_1 = OpConstant %int 1
+%12 = OpUndef %int
+%main = OpFunction %void None %4
+%13 = OpLabel
+OpBranch %14
+%14 = OpLabel
+%15 = OpPhi %int %int_0 %13 %16 %17
+%18 = OpPhi %int %int_0 %13 %19 %17
+%20 = OpPhi %int %12 %13 %21 %17
+OpLoopMerge %22 %17 None
+OpBranch %23
+%23 = OpLabel
+%24 = OpSLessThan %bool %18 %int_10
+OpBranchConditional %24 %25 %22
+%25 = OpLabel
+OpBranch %26
+%26 = OpLabel
+%16 = OpPhi %int %15 %25 %27 %28
+%21 = OpPhi %int %int_0 %25 %29 %28
+OpLoopMerge %30 %28 None
+OpBranch %31
+%31 = OpLabel
+%32 = OpSLessThan %bool %21 %int_10
+OpBranchConditional %32 %33 %30
+%33 = OpLabel
+%27 = OpISub %int %int_2 %18
+OpBranch %28
+%28 = OpLabel
+%29 = OpIAdd %int %21 %int_1
+OpBranch %26
+%30 = OpLabel
+OpBranch %17
+%17 = OpLabel
+%19 = OpIAdd %int %18 %int_1
+OpBranch %14
+%22 = OpLabel
+OpReturn
+OpFunctionEnd
+)";
+
+ const std::string after_hoist = R"(OpCapability Shader
+%1 = OpExtInstImport "GLSL.std.450"
+OpMemoryModel Logical GLSL450
+OpEntryPoint Fragment %main "main"
+OpExecutionMode %main OriginUpperLeft
+OpSource GLSL 440
+OpName %main "main"
+%void = OpTypeVoid
+%4 = OpTypeFunction %void
+%int = OpTypeInt 32 1
+%_ptr_Function_int = OpTypePointer Function %int
+%int_2 = OpConstant %int 2
+%int_0 = OpConstant %int 0
+%int_10 = OpConstant %int 10
+%bool = OpTypeBool
+%int_1 = OpConstant %int 1
+%12 = OpUndef %int
+%main = OpFunction %void None %4
+%13 = OpLabel
+OpBranch %14
+%14 = OpLabel
+%15 = OpPhi %int %int_0 %13 %16 %17
+%18 = OpPhi %int %int_0 %13 %19 %17
+%20 = OpPhi %int %12 %13 %21 %17
+OpLoopMerge %22 %17 None
+OpBranch %23
+%23 = OpLabel
+%24 = OpSLessThan %bool %18 %int_10
+OpBranchConditional %24 %25 %22
+%25 = OpLabel
+%27 = OpISub %int %int_2 %18
+OpBranch %26
+%26 = OpLabel
+%16 = OpPhi %int %15 %25 %27 %28
+%21 = OpPhi %int %int_0 %25 %29 %28
+OpLoopMerge %30 %28 None
+OpBranch %31
+%31 = OpLabel
+%32 = OpSLessThan %bool %21 %int_10
+OpBranchConditional %32 %33 %30
+%33 = OpLabel
+OpBranch %28
+%28 = OpLabel
+%29 = OpIAdd %int %21 %int_1
+OpBranch %26
+%30 = OpLabel
+OpBranch %17
+%17 = OpLabel
+%19 = OpIAdd %int %18 %int_1
+OpBranch %14
+%22 = OpLabel
+OpReturn
+OpFunctionEnd
+)";
+
+ SinglePassRunAndCheck<opt::LICMPass>(before_hoist, after_hoist, true);
+}
+
+} // namespace
--- /dev/null
+// 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 <string>
+
+#include <gmock/gmock.h>
+
+#include "../pass_fixture.h"
+#include "opt/licm_pass.h"
+
+namespace {
+
+using namespace spvtools;
+using ::testing::UnorderedElementsAre;
+
+using PassClassTest = PassTest<::testing::Test>;
+
+/*
+ Tests that the LICM pass will generate a preheader when one is not present
+
+ Generated from the following GLSL fragment shader
+--eliminate-local-multi-store has also been run on the spv binary
+#version 440 core
+void main(){
+ int a = 1;
+ int b = 2;
+ int hoist = 0;
+ for (int i = 0; i < 10; i++) {
+ if (i == 5) {
+ break;
+ }
+ }
+ for (int i = 0; i < 10; i++) {
+ hoist = a + b;
+ }
+}
+*/
+TEST_F(PassClassTest, HoistWithoutPreheader) {
+ const std::string before_hoist = R"(OpCapability Shader
+%1 = OpExtInstImport "GLSL.std.450"
+OpMemoryModel Logical GLSL450
+OpEntryPoint Fragment %main "main"
+OpExecutionMode %main OriginUpperLeft
+OpSource GLSL 440
+OpName %main "main"
+%void = OpTypeVoid
+%4 = OpTypeFunction %void
+%int = OpTypeInt 32 1
+%_ptr_Function_int = OpTypePointer Function %int
+%int_1 = OpConstant %int 1
+%int_2 = OpConstant %int 2
+%int_0 = OpConstant %int 0
+%int_10 = OpConstant %int 10
+%bool = OpTypeBool
+%int_5 = OpConstant %int 5
+%main = OpFunction %void None %4
+%13 = OpLabel
+OpBranch %14
+%14 = OpLabel
+%15 = OpPhi %int %int_0 %13 %16 %17
+OpLoopMerge %25 %17 None
+OpBranch %19
+%19 = OpLabel
+%20 = OpSLessThan %bool %15 %int_10
+OpBranchConditional %20 %21 %25
+%21 = OpLabel
+%22 = OpIEqual %bool %15 %int_5
+OpSelectionMerge %23 None
+OpBranchConditional %22 %24 %23
+%24 = OpLabel
+OpBranch %25
+%23 = OpLabel
+OpBranch %17
+%17 = OpLabel
+%16 = OpIAdd %int %15 %int_1
+OpBranch %14
+%25 = OpLabel
+%26 = OpPhi %int %int_0 %24 %int_0 %19 %27 %28
+%29 = OpPhi %int %int_0 %24 %int_0 %19 %30 %28
+OpLoopMerge %31 %28 None
+OpBranch %32
+%32 = OpLabel
+%33 = OpSLessThan %bool %29 %int_10
+OpBranchConditional %33 %34 %31
+%34 = OpLabel
+%27 = OpIAdd %int %int_1 %int_2
+OpBranch %28
+%28 = OpLabel
+%30 = OpIAdd %int %29 %int_1
+OpBranch %25
+%31 = OpLabel
+OpReturn
+OpFunctionEnd
+)";
+
+ const std::string after_hoist = R"(OpCapability Shader
+%1 = OpExtInstImport "GLSL.std.450"
+OpMemoryModel Logical GLSL450
+OpEntryPoint Fragment %main "main"
+OpExecutionMode %main OriginUpperLeft
+OpSource GLSL 440
+OpName %main "main"
+%void = OpTypeVoid
+%4 = OpTypeFunction %void
+%int = OpTypeInt 32 1
+%_ptr_Function_int = OpTypePointer Function %int
+%int_1 = OpConstant %int 1
+%int_2 = OpConstant %int 2
+%int_0 = OpConstant %int 0
+%int_10 = OpConstant %int 10
+%bool = OpTypeBool
+%int_5 = OpConstant %int 5
+%main = OpFunction %void None %4
+%13 = OpLabel
+OpBranch %14
+%14 = OpLabel
+%15 = OpPhi %int %int_0 %13 %16 %17
+OpLoopMerge %18 %17 None
+OpBranch %19
+%19 = OpLabel
+%20 = OpSLessThan %bool %15 %int_10
+OpBranchConditional %20 %21 %34
+%21 = OpLabel
+%22 = OpIEqual %bool %15 %int_5
+OpSelectionMerge %23 None
+OpBranchConditional %22 %24 %23
+%24 = OpLabel
+OpBranch %34
+%23 = OpLabel
+OpBranch %17
+%17 = OpLabel
+%16 = OpIAdd %int %15 %int_1
+OpBranch %14
+%34 = OpLabel
+%35 = OpPhi %int %int_0 %24 %int_0 %19
+%36 = OpPhi %int %int_0 %24 %int_0 %19
+%26 = OpIAdd %int %int_1 %int_2
+OpBranch %18
+%18 = OpLabel
+%25 = OpPhi %int %26 %27 %35 %34
+%28 = OpPhi %int %29 %27 %36 %34
+OpLoopMerge %30 %27 None
+OpBranch %31
+%31 = OpLabel
+%32 = OpSLessThan %bool %28 %int_10
+OpBranchConditional %32 %33 %30
+%33 = OpLabel
+OpBranch %27
+%27 = OpLabel
+%29 = OpIAdd %int %28 %int_1
+OpBranch %18
+%30 = OpLabel
+OpReturn
+OpFunctionEnd
+)";
+
+ SinglePassRunAndCheck<opt::LICMPass>(before_hoist, after_hoist, true);
+}
+
+} // namespace
ir::Loop* loop = ld[27];
EXPECT_EQ(loop->GetPreHeaderBlock(), nullptr);
- EXPECT_NE(loop->GetOrCreatePreHeaderBlock(context.get()), nullptr);
+ EXPECT_NE(loop->GetOrCreatePreHeaderBlock(), nullptr);
}
} // namespace
{
ir::Loop& loop = *ld[33];
EXPECT_EQ(loop.GetPreHeaderBlock(), nullptr);
- EXPECT_NE(loop.GetOrCreatePreHeaderBlock(context.get()), nullptr);
+ EXPECT_NE(loop.GetOrCreatePreHeaderBlock(), nullptr);
// Make sure the loop descriptor was properly updated.
EXPECT_EQ(ld[loop.GetPreHeaderBlock()], ld[16]);
{
{
ir::Loop& loop = *ld[41];
EXPECT_EQ(loop.GetPreHeaderBlock(), nullptr);
- EXPECT_NE(loop.GetOrCreatePreHeaderBlock(context.get()), nullptr);
+ EXPECT_NE(loop.GetOrCreatePreHeaderBlock(), nullptr);
EXPECT_EQ(ld[loop.GetPreHeaderBlock()], nullptr);
EXPECT_EQ(cfg->preds(loop.GetPreHeaderBlock()->id()).size(), 1u);
EXPECT_EQ(cfg->preds(loop.GetPreHeaderBlock()->id())[0], 25u);
optimizer->RegisterPass(CreateCFGCleanupPass());
} else if (0 == strcmp(cur_arg, "--local-redundancy-elimination")) {
optimizer->RegisterPass(CreateLocalRedundancyEliminationPass());
+ } else if (0 == strcmp(cur_arg, "--loop-invariant-code-motion")) {
+ optimizer->RegisterPass(CreateLoopInvariantCodeMotionPass());
} else if (0 == strcmp(cur_arg, "--redundancy-elimination")) {
optimizer->RegisterPass(CreateRedundancyEliminationPass());
} else if (0 == strcmp(cur_arg, "--private-to-local")) {
projects / platform / upstream / SPIRV-Tools.git / commitdiff