From 84ccd0b9ae1c4008bb3a36c527827fcabb354468 Mon Sep 17 00:00:00 2001 From: Alexander Johnston Date: Mon, 29 Jan 2018 10:39:55 +0000 Subject: [PATCH 1/1] Loop invariant code motion initial implementation --- Android.mk | 1 + include/spirv-tools/optimizer.hpp | 5 + source/opt/CMakeLists.txt | 2 + source/opt/cfg.cpp | 4 +- source/opt/instruction.cpp | 75 ++++++ source/opt/instruction.h | 3 + source/opt/licm_pass.cpp | 125 +++++++++ source/opt/licm_pass.h | 68 +++++ source/opt/loop_descriptor.cpp | 84 +++--- source/opt/loop_descriptor.h | 31 ++- source/opt/loop_utils.cpp | 6 +- source/opt/loop_utils.h | 4 +- source/opt/optimizer.cpp | 4 + source/opt/passes.h | 1 + test/opt/loop_optimizations/CMakeLists.txt | 36 +++ .../loop_optimizations/hoist_all_loop_types.cpp | 284 +++++++++++++++++++++ .../hoist_double_nested_loops.cpp | 161 ++++++++++++ .../hoist_from_independent_loops.cpp | 200 +++++++++++++++ test/opt/loop_optimizations/hoist_simple_case.cpp | 125 +++++++++ .../hoist_single_nested_loops.cpp | 161 ++++++++++++ .../loop_optimizations/hoist_without_preheader.cpp | 171 +++++++++++++ test/opt/loop_optimizations/loop_descriptions.cpp | 2 +- test/opt/loop_optimizations/nested_loops.cpp | 4 +- tools/opt/opt.cpp | 2 + 24 files changed, 1507 insertions(+), 52 deletions(-) create mode 100644 source/opt/licm_pass.cpp create mode 100644 source/opt/licm_pass.h create mode 100644 test/opt/loop_optimizations/hoist_all_loop_types.cpp create mode 100644 test/opt/loop_optimizations/hoist_double_nested_loops.cpp create mode 100644 test/opt/loop_optimizations/hoist_from_independent_loops.cpp create mode 100644 test/opt/loop_optimizations/hoist_simple_case.cpp create mode 100644 test/opt/loop_optimizations/hoist_single_nested_loops.cpp create mode 100644 test/opt/loop_optimizations/hoist_without_preheader.cpp diff --git a/Android.mk b/Android.mk index f0ad67c..501d8db 100644 --- a/Android.mk +++ b/Android.mk @@ -92,6 +92,7 @@ SPVTOOLS_OPT_SRC_FILES := \ 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 \ diff --git a/include/spirv-tools/optimizer.hpp b/include/spirv-tools/optimizer.hpp index becd024..e738b50 100644 --- a/include/spirv-tools/optimizer.hpp +++ b/include/spirv-tools/optimizer.hpp @@ -463,6 +463,11 @@ Optimizer::PassToken CreateMergeReturnPass(); // 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. diff --git a/source/opt/CMakeLists.txt b/source/opt/CMakeLists.txt index f43ac77..a0d98ec 100644 --- a/source/opt/CMakeLists.txt +++ b/source/opt/CMakeLists.txt @@ -47,6 +47,7 @@ add_library(SPIRV-Tools-opt 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 @@ -116,6 +117,7 @@ add_library(SPIRV-Tools-opt 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 diff --git a/source/opt/cfg.cpp b/source/opt/cfg.cpp index 404d192..0b30711 100644 --- a/source/opt/cfg.cpp +++ b/source/opt/cfg.cpp @@ -56,7 +56,9 @@ void CFG::RemoveNonExistingEdges(uint32_t blk_id) { 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); } diff --git a/source/opt/instruction.cpp b/source/opt/instruction.cpp index 8321561..99e50d3 100644 --- a/source/opt/instruction.cpp +++ b/source/opt/instruction.cpp @@ -499,5 +499,80 @@ std::ostream& operator<<(std::ostream& str, const ir::Instruction& inst) { 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 diff --git a/source/opt/instruction.h b/source/opt/instruction.h index 093bf9a..b04f66d 100644 --- a/source/opt/instruction.h +++ b/source/opt/instruction.h @@ -380,6 +380,9 @@ class Instruction : public utils::IntrusiveNodeBase { // 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 diff --git a/source/opt/licm_pass.cpp b/source/opt/licm_pass.cpp new file mode 100644 index 0000000..7faa21d --- /dev/null +++ b/source/opt/licm_pass.cpp @@ -0,0 +1,125 @@ +// 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 +#include + +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 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* loop_bbs) { + bool modified = false; + std::function 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 diff --git a/source/opt/licm_pass.h b/source/opt/licm_pass.h new file mode 100644 index 0000000..1d8ae20 --- /dev/null +++ b/source/opt/licm_pass.h @@ -0,0 +1,68 @@ +// 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 + +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* 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_ diff --git a/source/opt/loop_descriptor.cpp b/source/opt/loop_descriptor.cpp index c5318fd..a2b9546 100644 --- a/source/opt/loop_descriptor.cpp +++ b/source/opt/loop_descriptor.cpp @@ -32,21 +32,21 @@ namespace ir { 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_); @@ -85,26 +85,25 @@ BasicBlock* Loop::FindLoopPreheader(IRContext* ir_context, } 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(); @@ -117,7 +116,7 @@ BasicBlock* Loop::GetOrCreatePreHeaderBlock(ir::IRContext* context) { // Create the preheader basic block. loop_preheader_ = &*header_it.InsertBefore(std::unique_ptr( new ir::BasicBlock(std::unique_ptr(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(); @@ -132,11 +131,11 @@ BasicBlock* Loop::GetOrCreatePreHeaderBlock(ir::IRContext* context) { // 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 preheader_phi_ops; std::vector header_phi_ops; for (uint32_t i = 0; i < phi->NumInOperands(); i += 2) { @@ -158,7 +157,7 @@ BasicBlock* Loop::GetOrCreatePreHeaderBlock(ir::IRContext* context) { 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()); @@ -174,7 +173,7 @@ BasicBlock* Loop::GetOrCreatePreHeaderBlock(ir::IRContext* context) { 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; @@ -190,11 +189,11 @@ BasicBlock* Loop::GetOrCreatePreHeaderBlock(ir::IRContext* context) { // 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); @@ -226,8 +225,8 @@ void Loop::SetMergeBlock(BasicBlock* merge) { 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()) { @@ -235,9 +234,9 @@ void Loop::SetMergeBlock(BasicBlock* merge) { } } -void Loop::GetExitBlocks(IRContext* context, - std::unordered_set* exit_blocks) const { - ir::CFG* cfg = context->cfg(); +void Loop::GetExitBlocks(std::unordered_set* 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); @@ -250,9 +249,10 @@ void Loop::GetExitBlocks(IRContext* context, } void Loop::GetMergingBlocks( - IRContext* context, std::unordered_set* merging_blocks) const { + std::unordered_set* 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 to_visit; to_visit.push(GetMergeBlock()); @@ -269,12 +269,14 @@ void Loop::GetMergingBlocks( } 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 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)) { @@ -283,8 +285,8 @@ bool Loop::IsLCSSA() const { // - 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; @@ -296,6 +298,27 @@ bool Loop::IsLCSSA() const { 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 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); } @@ -304,7 +327,6 @@ LoopDescriptor::~LoopDescriptor() { ClearLoops(); } void LoopDescriptor::PopulateList(const Function* f) { IRContext* context = f->GetParent()->context(); - opt::DominatorAnalysis* dom_analysis = context->GetDominatorAnalysis(f, *context->cfg()); diff --git a/source/opt/loop_descriptor.h b/source/opt/loop_descriptor.h index fb53b4c..b4651d7 100644 --- a/source/opt/loop_descriptor.h +++ b/source/opt/loop_descriptor.h @@ -47,7 +47,8 @@ class Loop { using BasicBlockListTy = std::unordered_set; Loop() - : loop_header_(nullptr), + : context_(nullptr), + loop_header_(nullptr), loop_continue_(nullptr), loop_merge_(nullptr), loop_preheader_(nullptr), @@ -115,22 +116,20 @@ class Loop { // 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* 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* 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* merging_blocks) const; + void GetMergingBlocks(std::unordered_set* 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 @@ -200,7 +199,15 @@ class Loop { // 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_; @@ -229,8 +236,7 @@ class Loop { 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. @@ -266,6 +272,7 @@ class LoopDescriptor { 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 diff --git a/source/opt/loop_utils.cpp b/source/opt/loop_utils.cpp index 86bc2eb..6c2a15f 100644 --- a/source/opt/loop_utils.cpp +++ b/source/opt/loop_utils.cpp @@ -331,7 +331,7 @@ void LoopUtils::CreateLoopDedicatedExits() { // 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 exit_bb_set; - loop_->GetExitBlocks(context_, &exit_bb_set); + loop_->GetExitBlocks(&exit_bb_set); std::unordered_set new_loop_exits; bool made_change = false; @@ -448,7 +448,7 @@ void LoopUtils::MakeLoopClosedSSA() { std::unordered_set exit_bb; { std::unordered_set 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)); } @@ -463,7 +463,7 @@ void LoopUtils::MakeLoopClosedSSA() { // further than the merge block. if (loop_->GetMergeBlock()) { std::unordered_set 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(); diff --git a/source/opt/loop_utils.h b/source/opt/loop_utils.h index fcee9e3..65a5431 100644 --- a/source/opt/loop_utils.h +++ b/source/opt/loop_utils.h @@ -30,8 +30,8 @@ class LoopUtils { 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 (...) { diff --git a/source/opt/optimizer.cpp b/source/opt/optimizer.cpp index bdcc684..9f36f19 100644 --- a/source/opt/optimizer.cpp +++ b/source/opt/optimizer.cpp @@ -342,6 +342,10 @@ Optimizer::PassToken CreateLocalRedundancyEliminationPass() { MakeUnique()); } +Optimizer::PassToken CreateLoopInvariantCodeMotionPass() { + return MakeUnique(MakeUnique()); +} + Optimizer::PassToken CreateRedundancyEliminationPass() { return MakeUnique( MakeUnique()); diff --git a/source/opt/passes.h b/source/opt/passes.h index 96d0568..890e16e 100644 --- a/source/opt/passes.h +++ b/source/opt/passes.h @@ -35,6 +35,7 @@ #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" diff --git a/test/opt/loop_optimizations/CMakeLists.txt b/test/opt/loop_optimizations/CMakeLists.txt index 613ccf5..947f5c5 100644 --- a/test/opt/loop_optimizations/CMakeLists.txt +++ b/test/opt/loop_optimizations/CMakeLists.txt @@ -30,3 +30,39 @@ add_spvtools_unittest(TARGET lcssa_test 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 +) diff --git a/test/opt/loop_optimizations/hoist_all_loop_types.cpp b/test/opt/loop_optimizations/hoist_all_loop_types.cpp new file mode 100644 index 0000000..bb42fdd --- /dev/null +++ b/test/opt/loop_optimizations/hoist_all_loop_types.cpp @@ -0,0 +1,284 @@ +// 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 + +#include + +#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(before_hoist, after_hoist, true); +} + +} // namespace diff --git a/test/opt/loop_optimizations/hoist_double_nested_loops.cpp b/test/opt/loop_optimizations/hoist_double_nested_loops.cpp new file mode 100644 index 0000000..46bb562 --- /dev/null +++ b/test/opt/loop_optimizations/hoist_double_nested_loops.cpp @@ -0,0 +1,161 @@ +// 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 + +#include + +#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(before_hoist, after_hoist, true); +} + +} // namespace diff --git a/test/opt/loop_optimizations/hoist_from_independent_loops.cpp b/test/opt/loop_optimizations/hoist_from_independent_loops.cpp new file mode 100644 index 0000000..1c7beba --- /dev/null +++ b/test/opt/loop_optimizations/hoist_from_independent_loops.cpp @@ -0,0 +1,200 @@ +// 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 + +#include + +#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(before_hoist, after_hoist, true); +} + +} // namespace diff --git a/test/opt/loop_optimizations/hoist_simple_case.cpp b/test/opt/loop_optimizations/hoist_simple_case.cpp new file mode 100644 index 0000000..ce29c63 --- /dev/null +++ b/test/opt/loop_optimizations/hoist_simple_case.cpp @@ -0,0 +1,125 @@ +// 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 + +#include + +#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(before_hoist, after_hoist, true); +} + +} // namespace diff --git a/test/opt/loop_optimizations/hoist_single_nested_loops.cpp b/test/opt/loop_optimizations/hoist_single_nested_loops.cpp new file mode 100644 index 0000000..563c489 --- /dev/null +++ b/test/opt/loop_optimizations/hoist_single_nested_loops.cpp @@ -0,0 +1,161 @@ +// 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 + +#include + +#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(before_hoist, after_hoist, true); +} + +} // namespace diff --git a/test/opt/loop_optimizations/hoist_without_preheader.cpp b/test/opt/loop_optimizations/hoist_without_preheader.cpp new file mode 100644 index 0000000..6a36a64 --- /dev/null +++ b/test/opt/loop_optimizations/hoist_without_preheader.cpp @@ -0,0 +1,171 @@ +// 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 + +#include + +#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(before_hoist, after_hoist, true); +} + +} // namespace diff --git a/test/opt/loop_optimizations/loop_descriptions.cpp b/test/opt/loop_optimizations/loop_descriptions.cpp index a6032db..90e585e 100644 --- a/test/opt/loop_optimizations/loop_descriptions.cpp +++ b/test/opt/loop_optimizations/loop_descriptions.cpp @@ -200,7 +200,7 @@ TEST_F(PassClassTest, LoopWithNoPreHeader) { ir::Loop* loop = ld[27]; EXPECT_EQ(loop->GetPreHeaderBlock(), nullptr); - EXPECT_NE(loop->GetOrCreatePreHeaderBlock(context.get()), nullptr); + EXPECT_NE(loop->GetOrCreatePreHeaderBlock(), nullptr); } } // namespace diff --git a/test/opt/loop_optimizations/nested_loops.cpp b/test/opt/loop_optimizations/nested_loops.cpp index a2ebadf..480a280 100644 --- a/test/opt/loop_optimizations/nested_loops.cpp +++ b/test/opt/loop_optimizations/nested_loops.cpp @@ -725,7 +725,7 @@ TEST_F(PassClassTest, CreatePreheaderTest) { { 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]); { @@ -762,7 +762,7 @@ TEST_F(PassClassTest, CreatePreheaderTest) { { 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); diff --git a/tools/opt/opt.cpp b/tools/opt/opt.cpp index c4ed61e..4525e30 100644 --- a/tools/opt/opt.cpp +++ b/tools/opt/opt.cpp @@ -456,6 +456,8 @@ OptStatus ParseFlags(int argc, const char** argv, Optimizer* optimizer, 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")) { -- 2.7.4