Add register liveness analysis.
For each function, the analysis determine which SSA registers are live
at the beginning of each basic block and which one are killed at
the end of the basic block.
It also includes utilities to simulate the register pressure for loop
fusion and fission.
The implementation is based on the paper "A non-iterative data-flow
algorithm for computing liveness sets in strict ssa programs" from
Boissinot et al.
diff --git a/Android.mk b/Android.mk
index f6ac829..4199afc 100644
--- a/Android.mk
+++ b/Android.mk
@@ -119,6 +119,7 @@
source/opt/private_to_local_pass.cpp \
source/opt/propagator.cpp \
source/opt/redundancy_elimination.cpp \
+ source/opt/register_pressure.cpp \
source/opt/remove_duplicates_pass.cpp \
source/opt/replace_invalid_opc.cpp \
source/opt/scalar_analysis.cpp \
diff --git a/source/opt/CMakeLists.txt b/source/opt/CMakeLists.txt
index 114c3a5..408ed31 100644
--- a/source/opt/CMakeLists.txt
+++ b/source/opt/CMakeLists.txt
@@ -76,6 +76,7 @@
propagator.h
redundancy_elimination.h
reflect.h
+ register_pressure.h
remove_duplicates_pass.h
replace_invalid_opc.h
scalar_analysis.h
@@ -154,6 +155,7 @@
private_to_local_pass.cpp
propagator.cpp
redundancy_elimination.cpp
+ register_pressure.cpp
remove_duplicates_pass.cpp
replace_invalid_opc.cpp
scalar_analysis.cpp
diff --git a/source/opt/basic_block.h b/source/opt/basic_block.h
index 0df1f76..d34b047 100644
--- a/source/opt/basic_block.h
+++ b/source/opt/basic_block.h
@@ -19,6 +19,7 @@
#define LIBSPIRV_OPT_BASIC_BLOCK_H_
#include <functional>
+#include <iterator>
#include <memory>
#include <ostream>
#include <utility>
@@ -39,6 +40,9 @@
public:
using iterator = InstructionList::iterator;
using const_iterator = InstructionList::const_iterator;
+ using reverse_iterator = std::reverse_iterator<InstructionList::iterator>;
+ using const_reverse_iterator =
+ std::reverse_iterator<InstructionList::const_iterator>;
// Creates a basic block with the given starting |label|.
inline explicit BasicBlock(std::unique_ptr<Instruction> label);
@@ -87,6 +91,21 @@
const_iterator cbegin() const { return insts_.cbegin(); }
const_iterator cend() const { return insts_.cend(); }
+ reverse_iterator rbegin() { return reverse_iterator(end()); }
+ reverse_iterator rend() { return reverse_iterator(begin()); }
+ const_reverse_iterator rbegin() const {
+ return const_reverse_iterator(cend());
+ }
+ const_reverse_iterator rend() const {
+ return const_reverse_iterator(cbegin());
+ }
+ const_reverse_iterator crbegin() const {
+ return const_reverse_iterator(cend());
+ }
+ const_reverse_iterator crend() const {
+ return const_reverse_iterator(cbegin());
+ }
+
// Returns an iterator pointing to the last instruction. This may only
// be used if this block has an instruction other than the OpLabel
// that defines it.
diff --git a/source/opt/cfg.cpp b/source/opt/cfg.cpp
index 6767570..d13bdab 100644
--- a/source/opt/cfg.cpp
+++ b/source/opt/cfg.cpp
@@ -90,6 +90,19 @@
root, get_structured_successors, ignore_block, post_order, ignore_edge);
}
+void CFG::ForEachBlockInPostOrder(BasicBlock* bb,
+ const std::function<void(BasicBlock*)>& f) {
+ std::vector<BasicBlock*> po;
+ std::unordered_set<BasicBlock*> seen;
+ ComputePostOrderTraversal(bb, &po, &seen);
+
+ for (BasicBlock* current_bb : po) {
+ if (!IsPseudoExitBlock(current_bb) && !IsPseudoEntryBlock(current_bb)) {
+ f(current_bb);
+ }
+ }
+}
+
void CFG::ForEachBlockInReversePostOrder(
BasicBlock* bb, const std::function<void(BasicBlock*)>& f) {
std::vector<BasicBlock*> po;
diff --git a/source/opt/cfg.h b/source/opt/cfg.h
index ffff7e1..98d06a7 100644
--- a/source/opt/cfg.h
+++ b/source/opt/cfg.h
@@ -71,6 +71,12 @@
void ComputeStructuredOrder(ir::Function* func, ir::BasicBlock* root,
std::list<ir::BasicBlock*>* order);
+ // Applies |f| to the basic block in post order starting with |bb|.
+ // Note that basic blocks that cannot be reached from |bb| node will not be
+ // processed.
+ void ForEachBlockInPostOrder(BasicBlock* bb,
+ const std::function<void(BasicBlock*)>& f);
+
// Applies |f| to the basic block in reverse post order starting with |bb|.
// Note that basic blocks that cannot be reached from |bb| node will not be
// processed.
diff --git a/source/opt/ir_context.cpp b/source/opt/ir_context.cpp
index 856e403..ea1c0b9 100644
--- a/source/opt/ir_context.cpp
+++ b/source/opt/ir_context.cpp
@@ -48,6 +48,9 @@
if (set & kAnalysisScalarEvolution) {
BuildScalarEvolutionAnalysis();
}
+ if (set & kAnalysisRegisterPressure) {
+ BuildRegPressureAnalysis();
+ }
}
void IRContext::InvalidateAnalysesExceptFor(
diff --git a/source/opt/ir_context.h b/source/opt/ir_context.h
index bb44b49..ec34b97 100644
--- a/source/opt/ir_context.h
+++ b/source/opt/ir_context.h
@@ -24,6 +24,7 @@
#include "feature_manager.h"
#include "loop_descriptor.h"
#include "module.h"
+#include "register_pressure.h"
#include "scalar_analysis.h"
#include "type_manager.h"
@@ -60,7 +61,8 @@
kAnalysisLoopAnalysis = 1 << 6,
kAnalysisNameMap = 1 << 7,
kAnalysisScalarEvolution = 1 << 8,
- kAnalysisEnd = 1 << 9
+ kAnalysisRegisterPressure = 1 << 9,
+ kAnalysisEnd = 1 << 10
};
friend inline Analysis operator|(Analysis lhs, Analysis rhs);
@@ -206,6 +208,15 @@
return def_use_mgr_.get();
}
+ // Returns a pointer to a liveness analysis. If the liveness analysis is
+ // invalid, it is rebuilt first.
+ opt::LivenessAnalysis* GetLivenessAnalysis() {
+ if (!AreAnalysesValid(kAnalysisRegisterPressure)) {
+ BuildRegPressureAnalysis();
+ }
+ return reg_pressure_.get();
+ }
+
// Returns the basic block for instruction |instr|. Re-builds the instruction
// block map, if needed.
ir::BasicBlock* get_instr_block(ir::Instruction* instr) {
@@ -394,10 +405,20 @@
opt::DominatorAnalysis* GetDominatorAnalysis(const ir::Function* f,
const ir::CFG&);
+ // Gets the dominator analysis for function |f|.
+ opt::DominatorAnalysis* GetDominatorAnalysis(const ir::Function* f) {
+ return GetDominatorAnalysis(f, *cfg());
+ }
+
// Gets the postdominator analysis for function |f|.
opt::PostDominatorAnalysis* GetPostDominatorAnalysis(const ir::Function* f,
const ir::CFG&);
+ // Gets the postdominator analysis for function |f|.
+ opt::PostDominatorAnalysis* GetPostDominatorAnalysis(const ir::Function* f) {
+ return GetPostDominatorAnalysis(f, *cfg());
+ }
+
// Remove the dominator tree of |f| from the cache.
inline void RemoveDominatorAnalysis(const ir::Function* f) {
dominator_trees_.erase(f);
@@ -460,6 +481,12 @@
valid_analyses_ = valid_analyses_ | kAnalysisScalarEvolution;
}
+ // Builds the liveness analysis from scratch, even if it was already valid.
+ void BuildRegPressureAnalysis() {
+ reg_pressure_.reset(new opt::LivenessAnalysis(this));
+ valid_analyses_ = valid_analyses_ | kAnalysisRegisterPressure;
+ }
+
// Removes all computed dominator and post-dominator trees. This will force
// the context to rebuild the trees on demand.
void ResetDominatorAnalysis() {
@@ -563,6 +590,9 @@
// The cache scalar evolution analysis node.
std::unique_ptr<opt::ScalarEvolutionAnalysis> scalar_evolution_analysis_;
+
+ // The liveness analysis |module_|.
+ std::unique_ptr<opt::LivenessAnalysis> reg_pressure_;
};
inline ir::IRContext::Analysis operator|(ir::IRContext::Analysis lhs,
diff --git a/source/opt/iterator.h b/source/opt/iterator.h
index d43dfbe..13ff979 100644
--- a/source/opt/iterator.h
+++ b/source/opt/iterator.h
@@ -166,6 +166,105 @@
IteratorType(&container, container.cend())};
}
+// Wrapping iterator class that only consider elements that satisfy the given
+// predicate |Predicate|. When moving to the next element of the iterator, the
+// FilterIterator will iterate over the range until it finds an element that
+// satisfies |Predicate| or reaches the end of the iterator.
+//
+// Currently this iterator is always an input iterator.
+template <typename SubIterator, typename Predicate>
+class FilterIterator
+ : public std::iterator<
+ std::input_iterator_tag, typename SubIterator::value_type,
+ typename SubIterator::difference_type, typename SubIterator::pointer,
+ typename SubIterator::reference> {
+ public:
+ // Iterator interface.
+ using iterator_category = typename SubIterator::iterator_category;
+ using value_type = typename SubIterator::value_type;
+ using pointer = typename SubIterator::pointer;
+ using reference = typename SubIterator::reference;
+ using difference_type = typename SubIterator::difference_type;
+
+ using Range = IteratorRange<FilterIterator>;
+
+ FilterIterator(const IteratorRange<SubIterator>& iteration_range,
+ Predicate predicate)
+ : cur_(iteration_range.begin()),
+ end_(iteration_range.end()),
+ predicate_(predicate) {
+ if (!IsPredicateSatisfied()) {
+ MoveToNextPosition();
+ }
+ }
+
+ FilterIterator(const SubIterator& end, Predicate predicate)
+ : FilterIterator({end, end}, predicate) {}
+
+ inline FilterIterator& operator++() {
+ MoveToNextPosition();
+ return *this;
+ }
+ inline FilterIterator operator++(int) {
+ FilterIterator old = *this;
+ MoveToNextPosition();
+ return old;
+ }
+
+ reference operator*() const { return *cur_; }
+ pointer operator->() { return &*cur_; }
+
+ inline bool operator==(const FilterIterator& rhs) const {
+ return cur_ == rhs.cur_ && end_ == rhs.end_;
+ }
+ inline bool operator!=(const FilterIterator& rhs) const {
+ return !(*this == rhs);
+ }
+
+ // Returns the underlying iterator.
+ SubIterator Get() const { return cur_; }
+
+ // Returns the sentinel iterator.
+ FilterIterator GetEnd() const { return FilterIterator(end_, predicate_); }
+
+ private:
+ // Returns true if the predicate is satisfied or the current iterator reached
+ // the end.
+ bool IsPredicateSatisfied() { return cur_ == end_ || predicate_(*cur_); }
+
+ void MoveToNextPosition() {
+ if (cur_ == end_) return;
+
+ do {
+ ++cur_;
+ } while (!IsPredicateSatisfied());
+ }
+
+ SubIterator cur_;
+ SubIterator end_;
+ Predicate predicate_;
+};
+
+template <typename SubIterator, typename Predicate>
+FilterIterator<SubIterator, Predicate> MakeFilterIterator(
+ const IteratorRange<SubIterator>& sub_iterator_range, Predicate predicate) {
+ return FilterIterator<SubIterator, Predicate>(sub_iterator_range, predicate);
+}
+
+template <typename SubIterator, typename Predicate>
+FilterIterator<SubIterator, Predicate> MakeFilterIterator(
+ const SubIterator& begin, const SubIterator& end, Predicate predicate) {
+ return MakeFilterIterator(make_range(begin, end), predicate);
+}
+
+template <typename SubIterator, typename Predicate>
+typename FilterIterator<SubIterator, Predicate>::Range MakeFilterIteratorRange(
+ const SubIterator& begin, const SubIterator& end, Predicate predicate) {
+ return typename FilterIterator<SubIterator, Predicate>::Range(
+ MakeFilterIterator(begin, end, predicate),
+ MakeFilterIterator(end, end, predicate));
+}
+
template <typename VT, bool IC>
inline UptrVectorIterator<VT, IC>& UptrVectorIterator<VT, IC>::operator++() {
++iterator_;
diff --git a/source/opt/loop_descriptor.h b/source/opt/loop_descriptor.h
index 7ccab1b..210ec89 100644
--- a/source/opt/loop_descriptor.h
+++ b/source/opt/loop_descriptor.h
@@ -59,8 +59,6 @@
Loop(IRContext* context, opt::DominatorAnalysis* analysis, BasicBlock* header,
BasicBlock* continue_target, BasicBlock* merge_target);
- ~Loop() {}
-
// Iterators over the immediate sub-loops.
inline iterator begin() { return nested_loops_.begin(); }
inline iterator end() { return nested_loops_.end(); }
@@ -405,6 +403,9 @@
using iterator = opt::PostOrderTreeDFIterator<Loop>;
using const_iterator = opt::PostOrderTreeDFIterator<const Loop>;
+ using pre_iterator = opt::TreeDFIterator<Loop>;
+ using const_pre_iterator = opt::TreeDFIterator<const Loop>;
+
// Creates a loop object for all loops found in |f|.
explicit LoopDescriptor(const Function* f);
@@ -458,6 +459,17 @@
return const_iterator::end(&dummy_top_loop_);
}
+ // Iterators for pre-order depth first traversal of the loops.
+ // Inner most loops will be visited first.
+ inline pre_iterator pre_begin() { return ++pre_iterator(&dummy_top_loop_); }
+ inline pre_iterator pre_end() { return pre_iterator(); }
+ inline const_pre_iterator pre_begin() const { return pre_cbegin(); }
+ inline const_pre_iterator pre_end() const { return pre_cend(); }
+ inline const_pre_iterator pre_cbegin() const {
+ return ++const_pre_iterator(&dummy_top_loop_);
+ }
+ inline const_pre_iterator pre_cend() const { return const_pre_iterator(); }
+
// Returns the inner most loop that contains the basic block |bb|.
inline void SetBasicBlockToLoop(uint32_t bb_id, Loop* loop) {
basic_block_to_loop_[bb_id] = loop;
diff --git a/source/opt/register_pressure.cpp b/source/opt/register_pressure.cpp
new file mode 100644
index 0000000..d414e70
--- /dev/null
+++ b/source/opt/register_pressure.cpp
@@ -0,0 +1,578 @@
+// 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 "register_pressure.h"
+
+#include <iterator>
+
+#include "cfg.h"
+#include "def_use_manager.h"
+#include "dominator_tree.h"
+#include "function.h"
+#include "ir_context.h"
+#include "iterator.h"
+
+namespace spvtools {
+namespace opt {
+
+namespace {
+// Predicate for the FilterIterator to only consider instructions that are not
+// phi instructions defined in the basic block |bb|.
+class ExcludePhiDefinedInBlock {
+ public:
+ ExcludePhiDefinedInBlock(ir::IRContext* context, const ir::BasicBlock* bb)
+ : context_(context), bb_(bb) {}
+
+ bool operator()(ir::Instruction* insn) const {
+ return !(insn->opcode() == SpvOpPhi &&
+ context_->get_instr_block(insn) == bb_);
+ }
+
+ private:
+ ir::IRContext* context_;
+ const ir::BasicBlock* bb_;
+};
+
+// Returns true if |insn| generates a SSA register that is likely to require a
+// physical register.
+bool CreatesRegisterUsage(ir::Instruction* insn) {
+ if (!insn->HasResultId()) return false;
+ if (insn->opcode() == SpvOpUndef) return false;
+ if (ir::IsConstantInst(insn->opcode())) return false;
+ if (insn->opcode() == SpvOpLabel) return false;
+ return true;
+}
+
+// Compute the register liveness for each basic block of a function. This also
+// fill-up some information about the pick register usage and a break down of
+// register usage. This implements: "A non-iterative data-flow algorithm for
+// computing liveness sets in strict ssa programs" from Boissinot et al.
+class ComputeRegisterLiveness {
+ public:
+ ComputeRegisterLiveness(RegisterLiveness* reg_pressure, ir::Function* f)
+ : reg_pressure_(reg_pressure),
+ context_(reg_pressure->GetContext()),
+ function_(f),
+ cfg_(*reg_pressure->GetContext()->cfg()),
+ def_use_manager_(*reg_pressure->GetContext()->get_def_use_mgr()),
+ dom_tree_(
+ reg_pressure->GetContext()->GetDominatorAnalysis(f)->GetDomTree()),
+ loop_desc_(*reg_pressure->GetContext()->GetLoopDescriptor(f)) {}
+
+ // Computes the register liveness for |function_| and then estimate the
+ // register usage. The liveness algorithm works in 2 steps:
+ // - First, compute the liveness for each basic blocks, but will ignore any
+ // back-edge;
+ // - Second, walk loop forest to propagate registers crossing back-edges
+ // (add iterative values into the liveness set).
+ void Compute() {
+ cfg_.ForEachBlockInPostOrder(
+ &*function_->begin(),
+ [this](ir::BasicBlock* bb) { ComputePartialLiveness(bb); });
+ DoLoopLivenessUnification();
+ EvaluateRegisterRequirements();
+ }
+
+ private:
+ // Registers all SSA register used by successors of |bb| in their phi
+ // instructions.
+ void ComputePhiUses(const ir::BasicBlock& bb,
+ RegisterLiveness::RegionRegisterLiveness::LiveSet* live) {
+ uint32_t bb_id = bb.id();
+ bb.ForEachSuccessorLabel([live, bb_id, this](uint32_t sid) {
+ ir::BasicBlock* succ_bb = cfg_.block(sid);
+ succ_bb->ForEachPhiInst([live, bb_id, this](const ir::Instruction* phi) {
+ for (uint32_t i = 0; i < phi->NumInOperands(); i += 2) {
+ if (phi->GetSingleWordInOperand(i + 1) == bb_id) {
+ ir::Instruction* insn_op =
+ def_use_manager_.GetDef(phi->GetSingleWordInOperand(i));
+ if (CreatesRegisterUsage(insn_op)) {
+ live->insert(insn_op);
+ break;
+ }
+ }
+ }
+ });
+ });
+ }
+
+ // Computes register liveness for each basic blocks but ignores all
+ // back-edges.
+ void ComputePartialLiveness(ir::BasicBlock* bb) {
+ assert(reg_pressure_->Get(bb) == nullptr &&
+ "Basic block already processed");
+
+ RegisterLiveness::RegionRegisterLiveness* live_inout =
+ reg_pressure_->GetOrInsert(bb->id());
+ ComputePhiUses(*bb, &live_inout->live_out_);
+
+ const ir::BasicBlock* cbb = bb;
+ cbb->ForEachSuccessorLabel([&live_inout, bb, this](uint32_t sid) {
+ // Skip back edges.
+ if (dom_tree_.Dominates(sid, bb->id())) {
+ return;
+ }
+
+ ir::BasicBlock* succ_bb = cfg_.block(sid);
+ RegisterLiveness::RegionRegisterLiveness* succ_live_inout =
+ reg_pressure_->Get(succ_bb);
+ assert(succ_live_inout &&
+ "Successor liveness analysis was not performed");
+
+ ExcludePhiDefinedInBlock predicate(context_, succ_bb);
+ auto filter = ir::MakeFilterIteratorRange(
+ succ_live_inout->live_in_.begin(), succ_live_inout->live_in_.end(),
+ predicate);
+ live_inout->live_out_.insert(filter.begin(), filter.end());
+ });
+
+ live_inout->live_in_ = live_inout->live_out_;
+ for (ir::Instruction& insn : ir::make_range(bb->rbegin(), bb->rend())) {
+ if (insn.opcode() == SpvOpPhi) {
+ live_inout->live_in_.insert(&insn);
+ break;
+ }
+ live_inout->live_in_.erase(&insn);
+ insn.ForEachInId([live_inout, this](uint32_t* id) {
+ ir::Instruction* insn_op = def_use_manager_.GetDef(*id);
+ if (CreatesRegisterUsage(insn_op)) {
+ live_inout->live_in_.insert(insn_op);
+ }
+ });
+ }
+ }
+
+ // Propagates the register liveness information of each loop iterators.
+ void DoLoopLivenessUnification() {
+ for (const ir::Loop* loop : *loop_desc_.GetDummyRootLoop()) {
+ DoLoopLivenessUnification(*loop);
+ }
+ }
+
+ // Propagates the register liveness information of loop iterators trough-out
+ // the loop body.
+ void DoLoopLivenessUnification(const ir::Loop& loop) {
+ auto blocks_in_loop = ir::MakeFilterIteratorRange(
+ loop.GetBlocks().begin(), loop.GetBlocks().end(),
+ [&loop, this](uint32_t bb_id) {
+ return bb_id != loop.GetHeaderBlock()->id() &&
+ loop_desc_[bb_id] == &loop;
+ });
+
+ RegisterLiveness::RegionRegisterLiveness* header_live_inout =
+ reg_pressure_->Get(loop.GetHeaderBlock());
+ assert(header_live_inout &&
+ "Liveness analysis was not performed for the current block");
+
+ ExcludePhiDefinedInBlock predicate(context_, loop.GetHeaderBlock());
+ auto live_loop = ir::MakeFilterIteratorRange(
+ header_live_inout->live_in_.begin(), header_live_inout->live_in_.end(),
+ predicate);
+
+ for (uint32_t bb_id : blocks_in_loop) {
+ ir::BasicBlock* bb = cfg_.block(bb_id);
+
+ RegisterLiveness::RegionRegisterLiveness* live_inout =
+ reg_pressure_->Get(bb);
+ live_inout->live_in_.insert(live_loop.begin(), live_loop.end());
+ live_inout->live_out_.insert(live_loop.begin(), live_loop.end());
+ }
+
+ for (const ir::Loop* inner_loop : loop) {
+ RegisterLiveness::RegionRegisterLiveness* live_inout =
+ reg_pressure_->Get(inner_loop->GetHeaderBlock());
+ live_inout->live_in_.insert(live_loop.begin(), live_loop.end());
+ live_inout->live_out_.insert(live_loop.begin(), live_loop.end());
+
+ DoLoopLivenessUnification(*inner_loop);
+ }
+ }
+
+ // Get the number of required registers for this each basic block.
+ void EvaluateRegisterRequirements() {
+ for (ir::BasicBlock& bb : *function_) {
+ RegisterLiveness::RegionRegisterLiveness* live_inout =
+ reg_pressure_->Get(bb.id());
+ assert(live_inout != nullptr && "Basic block not processed");
+
+ size_t reg_count = live_inout->live_out_.size();
+ for (ir::Instruction* insn : live_inout->live_out_) {
+ live_inout->AddRegisterClass(insn);
+ }
+ live_inout->used_registers_ = reg_count;
+
+ std::unordered_set<uint32_t> die_in_block;
+ for (ir::Instruction& insn : ir::make_range(bb.rbegin(), bb.rend())) {
+ // If it is a phi instruction, the register pressure will not change
+ // anymore.
+ if (insn.opcode() == SpvOpPhi) {
+ break;
+ }
+
+ insn.ForEachInId(
+ [live_inout, &die_in_block, ®_count, this](uint32_t* id) {
+ ir::Instruction* op_insn = def_use_manager_.GetDef(*id);
+ if (!CreatesRegisterUsage(op_insn) ||
+ live_inout->live_out_.count(op_insn)) {
+ // already taken into account.
+ return;
+ }
+ if (!die_in_block.count(*id)) {
+ live_inout->AddRegisterClass(def_use_manager_.GetDef(*id));
+ reg_count++;
+ die_in_block.insert(*id);
+ }
+ });
+ live_inout->used_registers_ =
+ std::max(live_inout->used_registers_, reg_count);
+ if (CreatesRegisterUsage(&insn)) {
+ reg_count--;
+ }
+ }
+ }
+ }
+
+ RegisterLiveness* reg_pressure_;
+ ir::IRContext* context_;
+ ir::Function* function_;
+ ir::CFG& cfg_;
+ analysis::DefUseManager& def_use_manager_;
+ DominatorTree& dom_tree_;
+ ir::LoopDescriptor& loop_desc_;
+};
+} // namespace
+
+// Get the number of required registers for each basic block.
+void RegisterLiveness::RegionRegisterLiveness::AddRegisterClass(
+ ir::Instruction* insn) {
+ assert(CreatesRegisterUsage(insn) && "Instruction does not use a register");
+ analysis::Type* type =
+ insn->context()->get_type_mgr()->GetType(insn->type_id());
+
+ RegisterLiveness::RegisterClass reg_class{type, false};
+
+ insn->context()->get_decoration_mgr()->WhileEachDecoration(
+ insn->result_id(), SpvDecorationUniform,
+ [®_class](const ir::Instruction&) {
+ reg_class.is_uniform_ = true;
+ return false;
+ });
+
+ AddRegisterClass(reg_class);
+}
+
+void RegisterLiveness::Analyze(ir::Function* f) {
+ block_pressure_.clear();
+ ComputeRegisterLiveness(this, f).Compute();
+}
+
+void RegisterLiveness::ComputeLoopRegisterPressure(
+ const ir::Loop& loop, RegionRegisterLiveness* loop_reg_pressure) const {
+ loop_reg_pressure->Clear();
+
+ const RegionRegisterLiveness* header_live_inout = Get(loop.GetHeaderBlock());
+ loop_reg_pressure->live_in_ = header_live_inout->live_in_;
+
+ std::unordered_set<uint32_t> exit_blocks;
+ loop.GetExitBlocks(&exit_blocks);
+
+ for (uint32_t bb_id : exit_blocks) {
+ const RegionRegisterLiveness* live_inout = Get(bb_id);
+ loop_reg_pressure->live_out_.insert(live_inout->live_in_.begin(),
+ live_inout->live_in_.end());
+ }
+
+ std::unordered_set<uint32_t> seen_insn;
+ for (ir::Instruction* insn : loop_reg_pressure->live_out_) {
+ loop_reg_pressure->AddRegisterClass(insn);
+ seen_insn.insert(insn->result_id());
+ }
+ for (ir::Instruction* insn : loop_reg_pressure->live_in_) {
+ if (!seen_insn.count(insn->result_id())) {
+ continue;
+ }
+ loop_reg_pressure->AddRegisterClass(insn);
+ seen_insn.insert(insn->result_id());
+ }
+
+ loop_reg_pressure->used_registers_ = 0;
+
+ for (uint32_t bb_id : loop.GetBlocks()) {
+ ir::BasicBlock* bb = context_->cfg()->block(bb_id);
+
+ const RegionRegisterLiveness* live_inout = Get(bb_id);
+ assert(live_inout != nullptr && "Basic block not processed");
+ loop_reg_pressure->used_registers_ = std::max(
+ loop_reg_pressure->used_registers_, live_inout->used_registers_);
+
+ for (ir::Instruction& insn : *bb) {
+ if (insn.opcode() == SpvOpPhi || !CreatesRegisterUsage(&insn) ||
+ seen_insn.count(insn.result_id())) {
+ continue;
+ }
+ loop_reg_pressure->AddRegisterClass(&insn);
+ }
+ }
+}
+
+void RegisterLiveness::SimulateFusion(
+ const ir::Loop& l1, const ir::Loop& l2,
+ RegionRegisterLiveness* sim_result) const {
+ sim_result->Clear();
+
+ // Compute the live-in state:
+ // sim_result.live_in = l1.live_in U l2.live_in
+ // This assumes that |l1| does not generated register that is live-out for
+ // |l1|.
+ const RegionRegisterLiveness* l1_header_live_inout = Get(l1.GetHeaderBlock());
+ sim_result->live_in_ = l1_header_live_inout->live_in_;
+
+ const RegionRegisterLiveness* l2_header_live_inout = Get(l2.GetHeaderBlock());
+ sim_result->live_in_.insert(l2_header_live_inout->live_in_.begin(),
+ l2_header_live_inout->live_in_.end());
+
+ // The live-out set of the fused loop is the l2 live-out set.
+ std::unordered_set<uint32_t> exit_blocks;
+ l2.GetExitBlocks(&exit_blocks);
+
+ for (uint32_t bb_id : exit_blocks) {
+ const RegionRegisterLiveness* live_inout = Get(bb_id);
+ sim_result->live_out_.insert(live_inout->live_in_.begin(),
+ live_inout->live_in_.end());
+ }
+
+ // Compute the register usage information.
+ std::unordered_set<uint32_t> seen_insn;
+ for (ir::Instruction* insn : sim_result->live_out_) {
+ sim_result->AddRegisterClass(insn);
+ seen_insn.insert(insn->result_id());
+ }
+ for (ir::Instruction* insn : sim_result->live_in_) {
+ if (!seen_insn.count(insn->result_id())) {
+ continue;
+ }
+ sim_result->AddRegisterClass(insn);
+ seen_insn.insert(insn->result_id());
+ }
+
+ sim_result->used_registers_ = 0;
+
+ // The loop fusion is injecting the l1 before the l2, the latch of l1 will be
+ // connected to the header of l2.
+ // To compute the register usage, we inject the loop live-in (union of l1 and
+ // l2 live-in header blocks) into the the live in/out of each basic block of
+ // l1 to get the peak register usage. We then repeat the operation to for l2
+ // basic blocks but in this case we inject the live-out of the latch of l1.
+ auto live_loop = ir::MakeFilterIteratorRange(
+ sim_result->live_in_.begin(), sim_result->live_in_.end(),
+ [&l1, &l2](ir::Instruction* insn) {
+ ir::BasicBlock* bb = insn->context()->get_instr_block(insn);
+ return insn->HasResultId() &&
+ !(insn->opcode() == SpvOpPhi &&
+ (bb == l1.GetHeaderBlock() || bb == l2.GetHeaderBlock()));
+ });
+
+ for (uint32_t bb_id : l1.GetBlocks()) {
+ ir::BasicBlock* bb = context_->cfg()->block(bb_id);
+
+ const RegionRegisterLiveness* live_inout_info = Get(bb_id);
+ assert(live_inout_info != nullptr && "Basic block not processed");
+ RegionRegisterLiveness::LiveSet live_out = live_inout_info->live_out_;
+ live_out.insert(live_loop.begin(), live_loop.end());
+ sim_result->used_registers_ =
+ std::max(sim_result->used_registers_,
+ live_inout_info->used_registers_ + live_out.size() -
+ live_inout_info->live_out_.size());
+
+ for (ir::Instruction& insn : *bb) {
+ if (insn.opcode() == SpvOpPhi || !CreatesRegisterUsage(&insn) ||
+ seen_insn.count(insn.result_id())) {
+ continue;
+ }
+ sim_result->AddRegisterClass(&insn);
+ }
+ }
+
+ const RegionRegisterLiveness* l1_latch_live_inout_info =
+ Get(l1.GetLatchBlock()->id());
+ assert(l1_latch_live_inout_info != nullptr && "Basic block not processed");
+ RegionRegisterLiveness::LiveSet l1_latch_live_out =
+ l1_latch_live_inout_info->live_out_;
+ l1_latch_live_out.insert(live_loop.begin(), live_loop.end());
+
+ auto live_loop_l2 =
+ ir::make_range(l1_latch_live_out.begin(), l1_latch_live_out.end());
+
+ for (uint32_t bb_id : l2.GetBlocks()) {
+ ir::BasicBlock* bb = context_->cfg()->block(bb_id);
+
+ const RegionRegisterLiveness* live_inout_info = Get(bb_id);
+ assert(live_inout_info != nullptr && "Basic block not processed");
+ RegionRegisterLiveness::LiveSet live_out = live_inout_info->live_out_;
+ live_out.insert(live_loop_l2.begin(), live_loop_l2.end());
+ sim_result->used_registers_ =
+ std::max(sim_result->used_registers_,
+ live_inout_info->used_registers_ + live_out.size() -
+ live_inout_info->live_out_.size());
+
+ for (ir::Instruction& insn : *bb) {
+ if (insn.opcode() == SpvOpPhi || !CreatesRegisterUsage(&insn) ||
+ seen_insn.count(insn.result_id())) {
+ continue;
+ }
+ sim_result->AddRegisterClass(&insn);
+ }
+ }
+}
+
+void RegisterLiveness::SimulateFission(
+ const ir::Loop& loop,
+ const std::unordered_set<ir::Instruction*>& moved_inst,
+ const std::unordered_set<ir::Instruction*>& copied_inst,
+ RegionRegisterLiveness* l1_sim_result,
+ RegionRegisterLiveness* l2_sim_result) const {
+ l1_sim_result->Clear();
+ l2_sim_result->Clear();
+
+ // Filter predicates: consider instructions that only belong to the first and
+ // second loop.
+ auto belong_to_loop1 = [&moved_inst, &copied_inst,
+ &loop](ir::Instruction* insn) {
+ return moved_inst.count(insn) || copied_inst.count(insn) ||
+ !loop.IsInsideLoop(insn);
+ };
+ auto belong_to_loop2 = [&moved_inst](ir::Instruction* insn) {
+ return !moved_inst.count(insn);
+ };
+
+ const RegionRegisterLiveness* header_live_inout = Get(loop.GetHeaderBlock());
+ // l1 live-in
+ {
+ auto live_loop = ir::MakeFilterIteratorRange(
+ header_live_inout->live_in_.begin(), header_live_inout->live_in_.end(),
+ belong_to_loop1);
+ l1_sim_result->live_in_.insert(live_loop.begin(), live_loop.end());
+ }
+ // l2 live-in
+ {
+ auto live_loop = ir::MakeFilterIteratorRange(
+ header_live_inout->live_in_.begin(), header_live_inout->live_in_.end(),
+ belong_to_loop2);
+ l2_sim_result->live_in_.insert(live_loop.begin(), live_loop.end());
+ }
+
+ std::unordered_set<uint32_t> exit_blocks;
+ loop.GetExitBlocks(&exit_blocks);
+
+ // l2 live-out.
+ for (uint32_t bb_id : exit_blocks) {
+ const RegionRegisterLiveness* live_inout = Get(bb_id);
+ l2_sim_result->live_out_.insert(live_inout->live_in_.begin(),
+ live_inout->live_in_.end());
+ }
+ // l1 live-out.
+ {
+ auto live_out = ir::MakeFilterIteratorRange(
+ l2_sim_result->live_out_.begin(), l2_sim_result->live_out_.end(),
+ belong_to_loop1);
+ l1_sim_result->live_out_.insert(live_out.begin(), live_out.end());
+ }
+ {
+ auto live_out = ir::MakeFilterIteratorRange(l2_sim_result->live_in_.begin(),
+ l2_sim_result->live_in_.end(),
+ belong_to_loop1);
+ l1_sim_result->live_out_.insert(live_out.begin(), live_out.end());
+ }
+ // Lives out of l1 are live out of l2 so are live in of l2 as well.
+ l2_sim_result->live_in_.insert(l1_sim_result->live_out_.begin(),
+ l1_sim_result->live_out_.end());
+
+ for (ir::Instruction* insn : l1_sim_result->live_in_) {
+ l1_sim_result->AddRegisterClass(insn);
+ }
+ for (ir::Instruction* insn : l2_sim_result->live_in_) {
+ l2_sim_result->AddRegisterClass(insn);
+ }
+
+ l1_sim_result->used_registers_ = 0;
+ l2_sim_result->used_registers_ = 0;
+
+ for (uint32_t bb_id : loop.GetBlocks()) {
+ ir::BasicBlock* bb = context_->cfg()->block(bb_id);
+
+ const RegisterLiveness::RegionRegisterLiveness* live_inout = Get(bb_id);
+ assert(live_inout != nullptr && "Basic block not processed");
+ auto l1_block_live_out = ir::MakeFilterIteratorRange(
+ live_inout->live_out_.begin(), live_inout->live_out_.end(),
+ belong_to_loop1);
+ auto l2_block_live_out = ir::MakeFilterIteratorRange(
+ live_inout->live_out_.begin(), live_inout->live_out_.end(),
+ belong_to_loop2);
+
+ size_t l1_reg_count =
+ std::distance(l1_block_live_out.begin(), l1_block_live_out.end());
+ size_t l2_reg_count =
+ std::distance(l2_block_live_out.begin(), l2_block_live_out.end());
+
+ std::unordered_set<uint32_t> die_in_block;
+ for (ir::Instruction& insn : ir::make_range(bb->rbegin(), bb->rend())) {
+ if (insn.opcode() == SpvOpPhi) {
+ break;
+ }
+
+ bool does_belong_to_loop1 = belong_to_loop1(&insn);
+ bool does_belong_to_loop2 = belong_to_loop2(&insn);
+ insn.ForEachInId([live_inout, &die_in_block, &l1_reg_count, &l2_reg_count,
+ does_belong_to_loop1, does_belong_to_loop2,
+ this](uint32_t* id) {
+ ir::Instruction* op_insn = context_->get_def_use_mgr()->GetDef(*id);
+ if (!CreatesRegisterUsage(op_insn) ||
+ live_inout->live_out_.count(op_insn)) {
+ // already taken into account.
+ return;
+ }
+ if (!die_in_block.count(*id)) {
+ if (does_belong_to_loop1) {
+ l1_reg_count++;
+ }
+ if (does_belong_to_loop2) {
+ l2_reg_count++;
+ }
+ die_in_block.insert(*id);
+ }
+ });
+ l1_sim_result->used_registers_ =
+ std::max(l1_sim_result->used_registers_, l1_reg_count);
+ l2_sim_result->used_registers_ =
+ std::max(l2_sim_result->used_registers_, l2_reg_count);
+ if (CreatesRegisterUsage(&insn)) {
+ if (does_belong_to_loop1) {
+ if (!l1_sim_result->live_in_.count(&insn)) {
+ l1_sim_result->AddRegisterClass(&insn);
+ }
+ l1_reg_count--;
+ }
+ if (does_belong_to_loop2) {
+ if (!l2_sim_result->live_in_.count(&insn)) {
+ l2_sim_result->AddRegisterClass(&insn);
+ }
+ l2_reg_count--;
+ }
+ }
+ }
+ }
+}
+
+} // namespace opt
+} // namespace spvtools
diff --git a/source/opt/register_pressure.h b/source/opt/register_pressure.h
new file mode 100644
index 0000000..d827a20
--- /dev/null
+++ b/source/opt/register_pressure.h
@@ -0,0 +1,201 @@
+// 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 LIBSPIRV_OPT_REGISTER_PRESSURE_H_
+#define LIBSPIRV_OPT_REGISTER_PRESSURE_H_
+
+#include <unordered_map>
+#include <unordered_set>
+#include <utility>
+#include <vector>
+
+#include "function.h"
+#include "types.h"
+
+namespace spvtools {
+namespace ir {
+class IRContext;
+class Loop;
+class LoopDescriptor;
+} // namespace ir
+
+namespace opt {
+
+// Handles the register pressure of a function for different regions (function,
+// loop, basic block). It also contains some utilities to foresee the register
+// pressure following code transformations.
+class RegisterLiveness {
+ public:
+ // Classification of SSA registers.
+ struct RegisterClass {
+ analysis::Type* type_;
+ bool is_uniform_;
+
+ bool operator==(const RegisterClass& rhs) const {
+ return std::tie(type_, is_uniform_) ==
+ std::tie(rhs.type_, rhs.is_uniform_);
+ }
+ };
+
+ struct RegionRegisterLiveness {
+ using LiveSet = std::unordered_set<ir::Instruction*>;
+ using RegClassSetTy = std::vector<std::pair<RegisterClass, size_t>>;
+
+ // SSA register live when entering the basic block.
+ LiveSet live_in_;
+ // SSA register live when exiting the basic block.
+ LiveSet live_out_;
+
+ // Maximum number of required registers.
+ size_t used_registers_;
+ // Break down of the number of required registers per class of register.
+ RegClassSetTy registers_classes_;
+
+ void Clear() {
+ live_out_.clear();
+ live_in_.clear();
+ used_registers_ = 0;
+ registers_classes_.clear();
+ }
+
+ void AddRegisterClass(const RegisterClass& reg_class) {
+ auto it = std::find_if(
+ registers_classes_.begin(), registers_classes_.end(),
+ [®_class](const std::pair<RegisterClass, size_t>& class_count) {
+ return class_count.first == reg_class;
+ });
+ if (it != registers_classes_.end()) {
+ it->second++;
+ } else {
+ registers_classes_.emplace_back(std::move(reg_class),
+ static_cast<size_t>(1));
+ }
+ }
+
+ void AddRegisterClass(ir::Instruction* insn);
+ };
+
+ RegisterLiveness(ir::IRContext* context, ir::Function* f)
+ : context_(context) {
+ Analyze(f);
+ }
+
+ // Returns liveness and register information for the basic block |bb|. If no
+ // entry exist for the basic block, the function returns null.
+ const RegionRegisterLiveness* Get(const ir::BasicBlock* bb) const {
+ return Get(bb->id());
+ }
+
+ // Returns liveness and register information for the basic block id |bb_id|.
+ // If no entry exist for the basic block, the function returns null.
+ const RegionRegisterLiveness* Get(uint32_t bb_id) const {
+ RegionRegisterLivenessMap::const_iterator it = block_pressure_.find(bb_id);
+ if (it != block_pressure_.end()) {
+ return &it->second;
+ }
+ return nullptr;
+ }
+
+ ir::IRContext* GetContext() const { return context_; }
+
+ // Returns liveness and register information for the basic block |bb|. If no
+ // entry exist for the basic block, the function returns null.
+ RegionRegisterLiveness* Get(const ir::BasicBlock* bb) {
+ return Get(bb->id());
+ }
+
+ // Returns liveness and register information for the basic block id |bb_id|.
+ // If no entry exist for the basic block, the function returns null.
+ RegionRegisterLiveness* Get(uint32_t bb_id) {
+ RegionRegisterLivenessMap::iterator it = block_pressure_.find(bb_id);
+ if (it != block_pressure_.end()) {
+ return &it->second;
+ }
+ return nullptr;
+ }
+
+ // Returns liveness and register information for the basic block id |bb_id| or
+ // create a new empty entry if no entry already existed.
+ RegionRegisterLiveness* GetOrInsert(uint32_t bb_id) {
+ return &block_pressure_[bb_id];
+ }
+
+ // Compute the register pressure for the |loop| and store the result into
+ // |reg_pressure|. The live-in set corresponds to the live-in set of the
+ // header block, the live-out set of the loop corresponds to the union of the
+ // live-in sets of each exit basic block.
+ void ComputeLoopRegisterPressure(const ir::Loop& loop,
+ RegionRegisterLiveness* reg_pressure) const;
+
+ // Estimate the register pressure for the |l1| and |l2| as if they were making
+ // one unique loop. The result is stored into |simulation_result|.
+ void SimulateFusion(const ir::Loop& l1, const ir::Loop& l2,
+ RegionRegisterLiveness* simulation_result) const;
+
+ // Estimate the register pressure of |loop| after it has been fissioned
+ // according to |moved_instructions| and |copied_instructions|. The function
+ // assumes that the fission creates a new loop before |loop|, moves any
+ // instructions present inside |moved_instructions| and copies any
+ // instructions present inside |copied_instructions| into this new loop.
+ // The set |loop1_sim_result| store the simulation result of the loop with the
+ // moved instructions. The set |loop2_sim_result| store the simulation result
+ // of the loop with the removed instructions.
+ void SimulateFission(
+ const ir::Loop& loop,
+ const std::unordered_set<ir::Instruction*>& moved_instructions,
+ const std::unordered_set<ir::Instruction*>& copied_instructions,
+ RegionRegisterLiveness* loop1_sim_result,
+ RegionRegisterLiveness* loop2_sim_result) const;
+
+ private:
+ using RegionRegisterLivenessMap =
+ std::unordered_map<uint32_t, RegionRegisterLiveness>;
+
+ ir::IRContext* context_;
+ RegionRegisterLivenessMap block_pressure_;
+
+ void Analyze(ir::Function* f);
+};
+
+// Handles the register pressure of a function for different regions (function,
+// loop, basic block). It also contains some utilities to foresee the register
+// pressure following code transformations.
+class LivenessAnalysis {
+ using LivenessAnalysisMap =
+ std::unordered_map<const ir::Function*, RegisterLiveness>;
+
+ public:
+ LivenessAnalysis(ir::IRContext* context) : context_(context) {}
+
+ // Computes the liveness analysis for the function |f| and cache the result.
+ // If the analysis was performed for this function, then the cached analysis
+ // is returned.
+ const RegisterLiveness* Get(ir::Function* f) {
+ LivenessAnalysisMap::iterator it = analysis_cache_.find(f);
+ if (it != analysis_cache_.end()) {
+ return &it->second;
+ }
+ return &analysis_cache_.emplace(f, RegisterLiveness{context_, f})
+ .first->second;
+ }
+
+ private:
+ ir::IRContext* context_;
+ LivenessAnalysisMap analysis_cache_;
+};
+
+} // namespace opt
+} // namespace spvtools
+
+#endif // ! LIBSPIRV_OPT_REGISTER_PRESSURE_H_
diff --git a/test/opt/CMakeLists.txt b/test/opt/CMakeLists.txt
index 07b2d1e..e3d83d6 100644
--- a/test/opt/CMakeLists.txt
+++ b/test/opt/CMakeLists.txt
@@ -297,6 +297,11 @@
LIBS SPIRV-Tools-opt
)
+add_spvtools_unittest(TARGET register_liveness
+ SRCS register_liveness.cpp
+ LIBS SPIRV-Tools-opt
+)
+
add_spvtools_unittest(TARGET simplification
SRCS simplification_test.cpp pass_utils.cpp
LIBS SPIRV-Tools-opt
diff --git a/test/opt/iterator_test.cpp b/test/opt/iterator_test.cpp
index 5afe88c..5918430 100644
--- a/test/opt/iterator_test.cpp
+++ b/test/opt/iterator_test.cpp
@@ -214,4 +214,53 @@
EXPECT_EQ(count, range.size());
}
+TEST(Iterator, FilterIterator) {
+ struct Placeholder {
+ int val;
+ };
+ std::vector<Placeholder> data = {{1}, {2}, {3}, {4}, {5},
+ {6}, {7}, {8}, {9}, {10}};
+
+ // Predicate to only consider odd values.
+ struct Predicate {
+ bool operator()(const Placeholder& data) { return data.val % 2; }
+ };
+ Predicate pred;
+
+ auto filter_range =
+ ir::MakeFilterIteratorRange(data.begin(), data.end(), pred);
+
+ EXPECT_EQ(filter_range.begin().Get(), data.begin());
+ EXPECT_EQ(filter_range.end(), filter_range.begin().GetEnd());
+
+ for (Placeholder& data : filter_range) {
+ EXPECT_EQ(data.val % 2, 1);
+ }
+
+ for (auto it = filter_range.begin(); it != filter_range.end(); it++) {
+ EXPECT_EQ(it->val % 2, 1);
+ EXPECT_EQ((*it).val % 2, 1);
+ }
+
+ for (auto it = filter_range.begin(); it != filter_range.end(); ++it) {
+ EXPECT_EQ(it->val % 2, 1);
+ EXPECT_EQ((*it).val % 2, 1);
+ }
+
+ EXPECT_EQ(ir::MakeFilterIterator(data.begin(), data.end(), pred).Get(),
+ data.begin());
+ EXPECT_EQ(ir::MakeFilterIterator(data.end(), data.end(), pred).Get(),
+ data.end());
+ EXPECT_EQ(ir::MakeFilterIterator(data.begin(), data.end(), pred).GetEnd(),
+ ir::MakeFilterIterator(data.end(), data.end(), pred));
+ EXPECT_NE(ir::MakeFilterIterator(data.begin(), data.end(), pred),
+ ir::MakeFilterIterator(data.end(), data.end(), pred));
+
+ // Empty range: no values satisfies the predicate.
+ auto empty_range = ir::MakeFilterIteratorRange(
+ data.begin(), data.end(),
+ [](const Placeholder& data) { return data.val > 10; });
+ EXPECT_EQ(empty_range.begin(), empty_range.end());
+}
+
} // anonymous namespace
diff --git a/test/opt/register_liveness.cpp b/test/opt/register_liveness.cpp
new file mode 100644
index 0000000..1425cf9
--- /dev/null
+++ b/test/opt/register_liveness.cpp
@@ -0,0 +1,1279 @@
+// 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 <gmock/gmock.h>
+
+#include <memory>
+#include <string>
+#include <vector>
+
+#include "assembly_builder.h"
+#include "function_utils.h"
+#include "opt/register_pressure.h"
+#include "pass_fixture.h"
+#include "pass_utils.h"
+
+namespace {
+
+using namespace spvtools;
+using ::testing::UnorderedElementsAre;
+
+using PassClassTest = PassTest<::testing::Test>;
+
+static void CompareSets(const std::unordered_set<ir::Instruction*>& computed,
+ const std::unordered_set<uint32_t>& expected) {
+ for (ir::Instruction* insn : computed) {
+ EXPECT_TRUE(expected.count(insn->result_id()))
+ << "Unexpected instruction in live set: " << *insn;
+ }
+ EXPECT_EQ(computed.size(), expected.size());
+}
+
+/*
+Generated from the following GLSL
+
+#version 330
+in vec4 BaseColor;
+flat in int Count;
+void main()
+{
+ vec4 color = BaseColor;
+ vec4 acc;
+ if (Count == 0) {
+ acc = color;
+ }
+ else {
+ acc = color + vec4(0,1,2,0);
+ }
+ gl_FragColor = acc + color;
+}
+*/
+TEST_F(PassClassTest, LivenessWithIf) {
+ const std::string text = R"(
+ OpCapability Shader
+ %1 = OpExtInstImport "GLSL.std.450"
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint Fragment %4 "main" %11 %15 %32
+ OpExecutionMode %4 OriginLowerLeft
+ OpSource GLSL 330
+ OpName %4 "main"
+ OpName %11 "BaseColor"
+ OpName %15 "Count"
+ OpName %32 "gl_FragColor"
+ OpDecorate %11 Location 0
+ OpDecorate %15 Flat
+ OpDecorate %15 Location 0
+ OpDecorate %32 Location 0
+ %2 = OpTypeVoid
+ %3 = OpTypeFunction %2
+ %6 = OpTypeFloat 32
+ %7 = OpTypeVector %6 4
+ %10 = OpTypePointer Input %7
+ %11 = OpVariable %10 Input
+ %13 = OpTypeInt 32 1
+ %14 = OpTypePointer Input %13
+ %15 = OpVariable %14 Input
+ %17 = OpConstant %13 0
+ %18 = OpTypeBool
+ %26 = OpConstant %6 0
+ %27 = OpConstant %6 1
+ %28 = OpConstant %6 2
+ %29 = OpConstantComposite %7 %26 %27 %28 %26
+ %31 = OpTypePointer Output %7
+ %32 = OpVariable %31 Output
+ %4 = OpFunction %2 None %3
+ %5 = OpLabel
+ %12 = OpLoad %7 %11
+ %16 = OpLoad %13 %15
+ %19 = OpIEqual %18 %16 %17
+ OpSelectionMerge %21 None
+ OpBranchConditional %19 %20 %24
+ %20 = OpLabel
+ OpBranch %21
+ %24 = OpLabel
+ %30 = OpFAdd %7 %12 %29
+ OpBranch %21
+ %21 = OpLabel
+ %36 = OpPhi %7 %12 %20 %30 %24
+ %35 = OpFAdd %7 %36 %12
+ OpStore %32 %35
+ OpReturn
+ OpFunctionEnd
+ )";
+ std::unique_ptr<ir::IRContext> context =
+ BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, text,
+ SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
+ ir::Module* module = context->module();
+ EXPECT_NE(nullptr, module) << "Assembling failed for shader:\n"
+ << text << std::endl;
+ ir::Function* f = &*module->begin();
+ opt::LivenessAnalysis* liveness_analysis = context->GetLivenessAnalysis();
+ const opt::RegisterLiveness* register_liveness = liveness_analysis->Get(f);
+ {
+ SCOPED_TRACE("Block 5");
+ auto live_sets = register_liveness->Get(5);
+ std::unordered_set<uint32_t> live_in{
+ 11, // %11 = OpVariable %10 Input
+ 15, // %15 = OpVariable %14 Input
+ 32, // %32 = OpVariable %31 Output
+ };
+ CompareSets(live_sets->live_in_, live_in);
+
+ std::unordered_set<uint32_t> live_out{
+ 12, // %12 = OpLoad %7 %11
+ 32, // %32 = OpVariable %31 Output
+ };
+ CompareSets(live_sets->live_out_, live_out);
+ }
+ {
+ SCOPED_TRACE("Block 20");
+ auto live_sets = register_liveness->Get(20);
+ std::unordered_set<uint32_t> live_inout{
+ 12, // %12 = OpLoad %7 %11
+ 32, // %32 = OpVariable %31 Output
+ };
+ CompareSets(live_sets->live_in_, live_inout);
+ CompareSets(live_sets->live_out_, live_inout);
+ }
+ {
+ SCOPED_TRACE("Block 24");
+ auto live_sets = register_liveness->Get(24);
+ std::unordered_set<uint32_t> live_in{
+ 12, // %12 = OpLoad %7 %11
+ 32, // %32 = OpVariable %31 Output
+ };
+ CompareSets(live_sets->live_in_, live_in);
+
+ std::unordered_set<uint32_t> live_out{
+ 12, // %12 = OpLoad %7 %11
+ 30, // %30 = OpFAdd %7 %12 %29
+ 32, // %32 = OpVariable %31 Output
+ };
+ CompareSets(live_sets->live_out_, live_out);
+ }
+ {
+ SCOPED_TRACE("Block 21");
+ auto live_sets = register_liveness->Get(21);
+ std::unordered_set<uint32_t> live_in{
+ 12, // %12 = OpLoad %7 %11
+ 32, // %32 = OpVariable %31 Output
+ 36, // %36 = OpPhi %7 %12 %20 %30 %24
+ };
+ CompareSets(live_sets->live_in_, live_in);
+
+ std::unordered_set<uint32_t> live_out{};
+ CompareSets(live_sets->live_out_, live_out);
+ }
+}
+
+/*
+Generated from the following GLSL
+#version 330
+in vec4 bigColor;
+in vec4 BaseColor;
+in float f;
+flat in int Count;
+flat in uvec4 v4;
+void main()
+{
+ vec4 color = BaseColor;
+ for (int i = 0; i < Count; ++i)
+ color += bigColor;
+ float sum = 0.0;
+ for (int i = 0; i < 4; ++i) {
+ float acc = 0.0;
+ if (sum == 0.0) {
+ acc = v4[i];
+ }
+ else {
+ acc = BaseColor[i];
+ }
+ sum += acc + v4[i];
+ }
+ vec4 tv4;
+ for (int i = 0; i < 4; ++i)
+ tv4[i] = v4[i] * 4u;
+ color += vec4(sum) + tv4;
+ vec4 r;
+ r.xyz = BaseColor.xyz;
+ for (int i = 0; i < Count; ++i)
+ r.w = f;
+ color.xyz += r.xyz;
+ for (int i = 0; i < 16; i += 4)
+ for (int j = 0; j < 4; j++)
+ color *= f;
+ gl_FragColor = color + tv4;
+}
+*/
+TEST_F(PassClassTest, RegisterLiveness) {
+ const std::string text = R"(
+ OpCapability Shader
+ %1 = OpExtInstImport "GLSL.std.450"
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint Fragment %4 "main" %11 %24 %28 %55 %124 %176
+ OpExecutionMode %4 OriginLowerLeft
+ OpSource GLSL 330
+ OpName %4 "main"
+ OpName %11 "BaseColor"
+ OpName %24 "Count"
+ OpName %28 "bigColor"
+ OpName %55 "v4"
+ OpName %84 "tv4"
+ OpName %124 "f"
+ OpName %176 "gl_FragColor"
+ OpDecorate %11 Location 0
+ OpDecorate %24 Flat
+ OpDecorate %24 Location 0
+ OpDecorate %28 Location 0
+ OpDecorate %55 Flat
+ OpDecorate %55 Location 0
+ OpDecorate %124 Location 0
+ OpDecorate %176 Location 0
+ %2 = OpTypeVoid
+ %3 = OpTypeFunction %2
+ %6 = OpTypeFloat 32
+ %7 = OpTypeVector %6 4
+ %8 = OpTypePointer Function %7
+ %10 = OpTypePointer Input %7
+ %11 = OpVariable %10 Input
+ %13 = OpTypeInt 32 1
+ %16 = OpConstant %13 0
+ %23 = OpTypePointer Input %13
+ %24 = OpVariable %23 Input
+ %26 = OpTypeBool
+ %28 = OpVariable %10 Input
+ %33 = OpConstant %13 1
+ %35 = OpTypePointer Function %6
+ %37 = OpConstant %6 0
+ %45 = OpConstant %13 4
+ %52 = OpTypeInt 32 0
+ %53 = OpTypeVector %52 4
+ %54 = OpTypePointer Input %53
+ %55 = OpVariable %54 Input
+ %57 = OpTypePointer Input %52
+ %63 = OpTypePointer Input %6
+ %89 = OpConstant %52 4
+ %102 = OpTypeVector %6 3
+ %124 = OpVariable %63 Input
+ %158 = OpConstant %13 16
+ %175 = OpTypePointer Output %7
+ %176 = OpVariable %175 Output
+ %195 = OpUndef %7
+ %4 = OpFunction %2 None %3
+ %5 = OpLabel
+ %84 = OpVariable %8 Function
+ %12 = OpLoad %7 %11
+ OpBranch %17
+ %17 = OpLabel
+ %191 = OpPhi %7 %12 %5 %31 %18
+ %184 = OpPhi %13 %16 %5 %34 %18
+ %25 = OpLoad %13 %24
+ %27 = OpSLessThan %26 %184 %25
+ OpLoopMerge %19 %18 None
+ OpBranchConditional %27 %18 %19
+ %18 = OpLabel
+ %29 = OpLoad %7 %28
+ %31 = OpFAdd %7 %191 %29
+ %34 = OpIAdd %13 %184 %33
+ OpBranch %17
+ %19 = OpLabel
+ OpBranch %39
+ %39 = OpLabel
+ %188 = OpPhi %6 %37 %19 %73 %51
+ %185 = OpPhi %13 %16 %19 %75 %51
+ %46 = OpSLessThan %26 %185 %45
+ OpLoopMerge %41 %51 None
+ OpBranchConditional %46 %40 %41
+ %40 = OpLabel
+ %49 = OpFOrdEqual %26 %188 %37
+ OpSelectionMerge %51 None
+ OpBranchConditional %49 %50 %61
+ %50 = OpLabel
+ %58 = OpAccessChain %57 %55 %185
+ %59 = OpLoad %52 %58
+ %60 = OpConvertUToF %6 %59
+ OpBranch %51
+ %61 = OpLabel
+ %64 = OpAccessChain %63 %11 %185
+ %65 = OpLoad %6 %64
+ OpBranch %51
+ %51 = OpLabel
+ %210 = OpPhi %6 %60 %50 %65 %61
+ %68 = OpAccessChain %57 %55 %185
+ %69 = OpLoad %52 %68
+ %70 = OpConvertUToF %6 %69
+ %71 = OpFAdd %6 %210 %70
+ %73 = OpFAdd %6 %188 %71
+ %75 = OpIAdd %13 %185 %33
+ OpBranch %39
+ %41 = OpLabel
+ OpBranch %77
+ %77 = OpLabel
+ %186 = OpPhi %13 %16 %41 %94 %78
+ %83 = OpSLessThan %26 %186 %45
+ OpLoopMerge %79 %78 None
+ OpBranchConditional %83 %78 %79
+ %78 = OpLabel
+ %87 = OpAccessChain %57 %55 %186
+ %88 = OpLoad %52 %87
+ %90 = OpIMul %52 %88 %89
+ %91 = OpConvertUToF %6 %90
+ %92 = OpAccessChain %35 %84 %186
+ OpStore %92 %91
+ %94 = OpIAdd %13 %186 %33
+ OpBranch %77
+ %79 = OpLabel
+ %96 = OpCompositeConstruct %7 %188 %188 %188 %188
+ %97 = OpLoad %7 %84
+ %98 = OpFAdd %7 %96 %97
+ %100 = OpFAdd %7 %191 %98
+ %104 = OpVectorShuffle %102 %12 %12 0 1 2
+ %106 = OpVectorShuffle %7 %195 %104 4 5 6 3
+ OpBranch %108
+ %108 = OpLabel
+ %197 = OpPhi %7 %106 %79 %208 %133
+ %196 = OpPhi %13 %16 %79 %143 %133
+ %115 = OpSLessThan %26 %196 %25
+ OpLoopMerge %110 %133 None
+ OpBranchConditional %115 %109 %110
+ %109 = OpLabel
+ OpBranch %117
+ %117 = OpLabel
+ %209 = OpPhi %7 %197 %109 %181 %118
+ %204 = OpPhi %13 %16 %109 %129 %118
+ %123 = OpSLessThan %26 %204 %45
+ OpLoopMerge %119 %118 None
+ OpBranchConditional %123 %118 %119
+ %118 = OpLabel
+ %125 = OpLoad %6 %124
+ %181 = OpCompositeInsert %7 %125 %209 3
+ %129 = OpIAdd %13 %204 %33
+ OpBranch %117
+ %119 = OpLabel
+ OpBranch %131
+ %131 = OpLabel
+ %208 = OpPhi %7 %209 %119 %183 %132
+ %205 = OpPhi %13 %16 %119 %141 %132
+ %137 = OpSLessThan %26 %205 %45
+ OpLoopMerge %133 %132 None
+ OpBranchConditional %137 %132 %133
+ %132 = OpLabel
+ %138 = OpLoad %6 %124
+ %183 = OpCompositeInsert %7 %138 %208 3
+ %141 = OpIAdd %13 %205 %33
+ OpBranch %131
+ %133 = OpLabel
+ %143 = OpIAdd %13 %196 %33
+ OpBranch %108
+ %110 = OpLabel
+ %145 = OpVectorShuffle %102 %197 %197 0 1 2
+ %147 = OpVectorShuffle %102 %100 %100 0 1 2
+ %148 = OpFAdd %102 %147 %145
+ %150 = OpVectorShuffle %7 %100 %148 4 5 6 3
+ OpBranch %152
+ %152 = OpLabel
+ %200 = OpPhi %7 %150 %110 %203 %163
+ %199 = OpPhi %13 %16 %110 %174 %163
+ %159 = OpSLessThan %26 %199 %158
+ OpLoopMerge %154 %163 None
+ OpBranchConditional %159 %153 %154
+ %153 = OpLabel
+ OpBranch %161
+ %161 = OpLabel
+ %203 = OpPhi %7 %200 %153 %170 %162
+ %201 = OpPhi %13 %16 %153 %172 %162
+ %167 = OpSLessThan %26 %201 %45
+ OpLoopMerge %163 %162 None
+ OpBranchConditional %167 %162 %163
+ %162 = OpLabel
+ %168 = OpLoad %6 %124
+ %170 = OpVectorTimesScalar %7 %203 %168
+ %172 = OpIAdd %13 %201 %33
+ OpBranch %161
+ %163 = OpLabel
+ %174 = OpIAdd %13 %199 %45
+ OpBranch %152
+ %154 = OpLabel
+ %178 = OpLoad %7 %84
+ %179 = OpFAdd %7 %200 %178
+ OpStore %176 %179
+ OpReturn
+ OpFunctionEnd
+ )";
+ std::unique_ptr<ir::IRContext> context =
+ BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, text,
+ SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
+ ir::Module* module = context->module();
+ EXPECT_NE(nullptr, module) << "Assembling failed for shader:\n"
+ << text << std::endl;
+ ir::Function* f = &*module->begin();
+ opt::LivenessAnalysis* liveness_analysis = context->GetLivenessAnalysis();
+ const opt::RegisterLiveness* register_liveness = liveness_analysis->Get(f);
+ ir::LoopDescriptor& ld = *context->GetLoopDescriptor(f);
+
+ {
+ SCOPED_TRACE("Block 5");
+ auto live_sets = register_liveness->Get(5);
+ std::unordered_set<uint32_t> live_in{
+ 11, // %11 = OpVariable %10 Input
+ 24, // %24 = OpVariable %23 Input
+ 28, // %28 = OpVariable %10 Input
+ 55, // %55 = OpVariable %54 Input
+ 124, // %124 = OpVariable %63 Input
+ 176, // %176 = OpVariable %175 Output
+ };
+ CompareSets(live_sets->live_in_, live_in);
+
+ std::unordered_set<uint32_t> live_out{
+ 11, // %11 = OpVariable %10 Input
+ 12, // %12 = OpLoad %7 %11
+ 24, // %24 = OpVariable %23 Input
+ 28, // %28 = OpVariable %10 Input
+ 55, // %55 = OpVariable %54 Input
+ 84, // %84 = OpVariable %8 Function
+ 124, // %124 = OpVariable %63 Input
+ 176, // %176 = OpVariable %175 Output
+ };
+ CompareSets(live_sets->live_out_, live_out);
+
+ EXPECT_EQ(live_sets->used_registers_, 8u);
+ }
+ {
+ SCOPED_TRACE("Block 17");
+ auto live_sets = register_liveness->Get(17);
+ std::unordered_set<uint32_t> live_in{
+ 11, // %11 = OpVariable %10 Input
+ 12, // %12 = OpLoad %7 %11
+ 24, // %24 = OpVariable %23 Input
+ 28, // %28 = OpVariable %10 Input
+ 55, // %55 = OpVariable %54 Input
+ 84, // %84 = OpVariable %8 Function
+ 124, // %124 = OpVariable %63 Input
+ 176, // %176 = OpVariable %175 Output
+ 184, // %184 = OpPhi %13 %16 %5 %34 %18
+ 191, // %191 = OpPhi %7 %12 %5 %31 %18
+ };
+ CompareSets(live_sets->live_in_, live_in);
+
+ std::unordered_set<uint32_t> live_out{
+ 11, // %11 = OpVariable %10 Input
+ 12, // %12 = OpLoad %7 %11
+ 25, // %25 = OpLoad %13 %24
+ 28, // %28 = OpVariable %10 Input
+ 55, // %55 = OpVariable %54 Input
+ 84, // %84 = OpVariable %8 Function
+ 124, // %124 = OpVariable %63 Input
+ 176, // %176 = OpVariable %175 Output
+ 184, // %184 = OpPhi %13 %16 %5 %34 %18
+ 191, // %191 = OpPhi %7 %12 %5 %31 %18
+ };
+ CompareSets(live_sets->live_out_, live_out);
+
+ EXPECT_EQ(live_sets->used_registers_, 11u);
+ }
+ {
+ SCOPED_TRACE("Block 18");
+ auto live_sets = register_liveness->Get(18);
+ std::unordered_set<uint32_t> live_in{
+ 11, // %11 = OpVariable %10 Input
+ 12, // %12 = OpLoad %7 %11
+ 24, // %24 = OpVariable %23 Input
+ 28, // %28 = OpVariable %10 Input
+ 55, // %55 = OpVariable %54 Input
+ 84, // %84 = OpVariable %8 Function
+ 124, // %124 = OpVariable %63 Input
+ 176, // %176 = OpVariable %175 Output
+ 184, // %184 = OpPhi %13 %16 %5 %34 %18
+ 191, // %191 = OpPhi %7 %12 %5 %31 %18
+ };
+ CompareSets(live_sets->live_in_, live_in);
+
+ std::unordered_set<uint32_t> live_out{
+ 11, // %11 = OpVariable %10 Input
+ 12, // %12 = OpLoad %7 %11
+ 24, // %24 = OpVariable %23 Input
+ 28, // %28 = OpVariable %10 Input
+ 31, // %31 = OpFAdd %7 %191 %29
+ 34, // %34 = OpIAdd %13 %184 %33
+ 55, // %55 = OpVariable %54 Input
+ 84, // %84 = OpVariable %8 Function
+ 124, // %124 = OpVariable %63 Input
+ 176, // %176 = OpVariable %175 Output
+ };
+ CompareSets(live_sets->live_out_, live_out);
+
+ EXPECT_EQ(live_sets->used_registers_, 12u);
+ }
+ {
+ SCOPED_TRACE("Block 19");
+ auto live_sets = register_liveness->Get(19);
+ std::unordered_set<uint32_t> live_inout{
+ 11, // %11 = OpVariable %10 Input
+ 12, // %12 = OpLoad %7 %11
+ 25, // %25 = OpLoad %13 %24
+ 55, // %55 = OpVariable %54 Input
+ 84, // %84 = OpVariable %8 Function
+ 124, // %124 = OpVariable %63 Input
+ 176, // %176 = OpVariable %175 Output
+ 191, // %191 = OpPhi %7 %12 %5 %31 %18
+ };
+ CompareSets(live_sets->live_in_, live_inout);
+ CompareSets(live_sets->live_out_, live_inout);
+
+ EXPECT_EQ(live_sets->used_registers_, 8u);
+ }
+ {
+ SCOPED_TRACE("Block 39");
+ auto live_sets = register_liveness->Get(39);
+ std::unordered_set<uint32_t> live_inout{
+ 11, // %11 = OpVariable %10 Input
+ 12, // %12 = OpLoad %7 %11
+ 25, // %25 = OpLoad %13 %24
+ 55, // %55 = OpVariable %54 Input
+ 84, // %84 = OpVariable %8 Function
+ 124, // %124 = OpVariable %63 Input
+ 176, // %176 = OpVariable %175 Output
+ 185, // %185 = OpPhi %13 %16 %19 %75 %51
+ 188, // %188 = OpPhi %6 %37 %19 %73 %51
+ 191, // %191 = OpPhi %7 %12 %5 %31 %18
+ };
+ CompareSets(live_sets->live_in_, live_inout);
+ CompareSets(live_sets->live_out_, live_inout);
+
+ EXPECT_EQ(live_sets->used_registers_, 11u);
+ }
+ {
+ SCOPED_TRACE("Block 40");
+ auto live_sets = register_liveness->Get(40);
+ std::unordered_set<uint32_t> live_inout{
+ 11, // %11 = OpVariable %10 Input
+ 12, // %12 = OpLoad %7 %11
+ 25, // %25 = OpLoad %13 %24
+ 55, // %55 = OpVariable %54 Input
+ 84, // %84 = OpVariable %8 Function
+ 124, // %124 = OpVariable %63 Input
+ 176, // %176 = OpVariable %175 Output
+ 185, // %185 = OpPhi %13 %16 %19 %75 %51
+ 188, // %188 = OpPhi %6 %37 %19 %73 %51
+ 191, // %191 = OpPhi %7 %12 %5 %31 %18
+ };
+ CompareSets(live_sets->live_in_, live_inout);
+ CompareSets(live_sets->live_out_, live_inout);
+
+ EXPECT_EQ(live_sets->used_registers_, 11u);
+ }
+ {
+ SCOPED_TRACE("Block 50");
+ auto live_sets = register_liveness->Get(50);
+ std::unordered_set<uint32_t> live_in{
+ 11, // %11 = OpVariable %10 Input
+ 12, // %12 = OpLoad %7 %11
+ 25, // %25 = OpLoad %13 %24
+ 55, // %55 = OpVariable %54 Input
+ 84, // %84 = OpVariable %8 Function
+ 124, // %124 = OpVariable %63 Input
+ 176, // %176 = OpVariable %175 Output
+ 185, // %185 = OpPhi %13 %16 %19 %75 %51
+ 188, // %188 = OpPhi %6 %37 %19 %73 %51
+ 191, // %191 = OpPhi %7 %12 %5 %31 %18
+ };
+ CompareSets(live_sets->live_in_, live_in);
+
+ std::unordered_set<uint32_t> live_out{
+ 11, // %11 = OpVariable %10 Input
+ 12, // %12 = OpLoad %7 %11
+ 25, // %25 = OpLoad %13 %24
+ 55, // %55 = OpVariable %54 Input
+ 60, // %60 = OpConvertUToF %6 %59
+ 84, // %84 = OpVariable %8 Function
+ 124, // %124 = OpVariable %63 Input
+ 176, // %176 = OpVariable %175 Output
+ 185, // %185 = OpPhi %13 %16 %19 %75 %51
+ 188, // %188 = OpPhi %6 %37 %19 %73 %51
+ 191, // %191 = OpPhi %7 %12 %5 %31 %18
+ };
+ CompareSets(live_sets->live_out_, live_out);
+
+ EXPECT_EQ(live_sets->used_registers_, 12u);
+ }
+ {
+ SCOPED_TRACE("Block 61");
+ auto live_sets = register_liveness->Get(61);
+ std::unordered_set<uint32_t> live_in{
+ 11, // %11 = OpVariable %10 Input
+ 12, // %12 = OpLoad %7 %11
+ 25, // %25 = OpLoad %13 %24
+ 55, // %55 = OpVariable %54 Input
+ 84, // %84 = OpVariable %8 Function
+ 124, // %124 = OpVariable %63 Input
+ 176, // %176 = OpVariable %175 Output
+ 185, // %185 = OpPhi %13 %16 %19 %75 %51
+ 188, // %188 = OpPhi %6 %37 %19 %73 %51
+ 191, // %191 = OpPhi %7 %12 %5 %31 %18
+ };
+ CompareSets(live_sets->live_in_, live_in);
+
+ std::unordered_set<uint32_t> live_out{
+ 11, // %11 = OpVariable %10 Input
+ 12, // %12 = OpLoad %7 %11
+ 25, // %25 = OpLoad %13 %24
+ 55, // %55 = OpVariable %54 Input
+ 65, // %65 = OpLoad %6 %64
+ 84, // %84 = OpVariable %8 Function
+ 124, // %124 = OpVariable %63 Input
+ 176, // %176 = OpVariable %175 Output
+ 185, // %185 = OpPhi %13 %16 %19 %75 %51
+ 188, // %188 = OpPhi %6 %37 %19 %73 %51
+ 191, // %191 = OpPhi %7 %12 %5 %31 %18
+ };
+ CompareSets(live_sets->live_out_, live_out);
+
+ EXPECT_EQ(live_sets->used_registers_, 12u);
+ }
+ {
+ SCOPED_TRACE("Block 51");
+ auto live_sets = register_liveness->Get(51);
+ std::unordered_set<uint32_t> live_in{
+ 11, // %11 = OpVariable %10 Input
+ 12, // %12 = OpLoad %7 %11
+ 25, // %25 = OpLoad %13 %24
+ 55, // %55 = OpVariable %54 Input
+ 84, // %84 = OpVariable %8 Function
+ 124, // %124 = OpVariable %63 Input
+ 176, // %176 = OpVariable %175 Output
+ 185, // %185 = OpPhi %13 %16 %19 %75 %51
+ 188, // %188 = OpPhi %6 %37 %19 %73 %51
+ 191, // %191 = OpPhi %7 %12 %5 %31 %18
+ 210, // %210 = OpPhi %6 %60 %50 %65 %61
+ };
+ CompareSets(live_sets->live_in_, live_in);
+
+ std::unordered_set<uint32_t> live_out{
+ 11, // %11 = OpVariable %10 Input
+ 12, // %12 = OpLoad %7 %11
+ 25, // %25 = OpLoad %13 %24
+ 55, // %55 = OpVariable %54 Input
+ 73, // %73 = OpFAdd %6 %188 %71
+ 75, // %75 = OpIAdd %13 %185 %33
+ 84, // %84 = OpVariable %8 Function
+ 124, // %124 = OpVariable %63 Input
+ 176, // %176 = OpVariable %175 Output
+ 191, // %191 = OpPhi %7 %12 %5 %31 %18
+ };
+ CompareSets(live_sets->live_out_, live_out);
+
+ EXPECT_EQ(live_sets->used_registers_, 13u);
+ }
+ {
+ SCOPED_TRACE("Block 41");
+ auto live_sets = register_liveness->Get(41);
+ std::unordered_set<uint32_t> live_inout{
+ 12, // %12 = OpLoad %7 %11
+ 25, // %25 = OpLoad %13 %24
+ 55, // %55 = OpVariable %54 Input
+ 84, // %84 = OpVariable %8 Function
+ 124, // %124 = OpVariable %63 Input
+ 176, // %176 = OpVariable %175 Output
+ 188, // %188 = OpPhi %6 %37 %19 %73 %51
+ 191, // %191 = OpPhi %7 %12 %5 %31 %18
+ };
+ CompareSets(live_sets->live_in_, live_inout);
+ CompareSets(live_sets->live_out_, live_inout);
+
+ EXPECT_EQ(live_sets->used_registers_, 8u);
+ }
+ {
+ SCOPED_TRACE("Block 77");
+ auto live_sets = register_liveness->Get(77);
+ std::unordered_set<uint32_t> live_inout{
+ 12, // %12 = OpLoad %7 %11
+ 25, // %25 = OpLoad %13 %24
+ 55, // %55 = OpVariable %54 Input
+ 84, // %84 = OpVariable %8 Function
+ 124, // %124 = OpVariable %63 Input
+ 176, // %176 = OpVariable %175 Output
+ 186, // %186 = OpPhi %13 %16 %41 %94 %78
+ 188, // %188 = OpPhi %6 %37 %19 %73 %51
+ 191, // %191 = OpPhi %7 %12 %5 %31 %18
+ };
+ CompareSets(live_sets->live_in_, live_inout);
+ CompareSets(live_sets->live_out_, live_inout);
+
+ EXPECT_EQ(live_sets->used_registers_, 10u);
+ }
+ {
+ SCOPED_TRACE("Block 78");
+ auto live_sets = register_liveness->Get(78);
+ std::unordered_set<uint32_t> live_in{
+ 12, // %12 = OpLoad %7 %11
+ 25, // %25 = OpLoad %13 %24
+ 55, // %55 = OpVariable %54 Input
+ 84, // %84 = OpVariable %8 Function
+ 124, // %124 = OpVariable %63 Input
+ 176, // %176 = OpVariable %175 Output
+ 186, // %186 = OpPhi %13 %16 %41 %94 %78
+ 188, // %188 = OpPhi %6 %37 %19 %73 %51
+ 191, // %191 = OpPhi %7 %12 %5 %31 %18
+ };
+ CompareSets(live_sets->live_in_, live_in);
+
+ std::unordered_set<uint32_t> live_out{
+ 12, // %12 = OpLoad %7 %11
+ 25, // %25 = OpLoad %13 %24
+ 55, // %55 = OpVariable %54 Input
+ 84, // %84 = OpVariable %8 Function
+ 94, // %94 = OpIAdd %13 %186 %33
+ 124, // %124 = OpVariable %63 Input
+ 176, // %176 = OpVariable %175 Output
+ 188, // %188 = OpPhi %6 %37 %19 %73 %51
+ 191, // %191 = OpPhi %7 %12 %5 %31 %18
+ };
+ CompareSets(live_sets->live_out_, live_out);
+
+ EXPECT_EQ(live_sets->used_registers_, 11u);
+ }
+ {
+ SCOPED_TRACE("Block 79");
+ auto live_sets = register_liveness->Get(79);
+ std::unordered_set<uint32_t> live_in{
+ 12, // %12 = OpLoad %7 %11
+ 25, // %25 = OpLoad %13 %24
+ 84, // %84 = OpVariable %8 Function
+ 124, // %124 = OpVariable %63 Input
+ 176, // %176 = OpVariable %175 Output
+ 188, // %188 = OpPhi %6 %37 %19 %73 %51
+ 191, // %191 = OpPhi %7 %12 %5 %31 %18
+ };
+ CompareSets(live_sets->live_in_, live_in);
+
+ std::unordered_set<uint32_t> live_out{
+ 25, // %25 = OpLoad %13 %24
+ 84, // %84 = OpVariable %8 Function
+ 100, // %100 = OpFAdd %7 %191 %98
+ 106, // %106 = OpVectorShuffle %7 %195 %104 4 5 6 3
+ 124, // %124 = OpVariable %63 Input
+ 176, // %176 = OpVariable %175 Output
+ };
+ CompareSets(live_sets->live_out_, live_out);
+
+ EXPECT_EQ(live_sets->used_registers_, 9u);
+ }
+ {
+ SCOPED_TRACE("Block 108");
+ auto live_sets = register_liveness->Get(108);
+ std::unordered_set<uint32_t> live_in{
+ 25, // %25 = OpLoad %13 %24
+ 84, // %84 = OpVariable %8 Function
+ 100, // %100 = OpFAdd %7 %191 %98
+ 124, // %124 = OpVariable %63 Input
+ 176, // %176 = OpVariable %175 Output
+ 196, // %196 = OpPhi %13 %16 %79 %143 %133
+ 197, // %197 = OpPhi %7 %106 %79 %208 %133
+ };
+ CompareSets(live_sets->live_in_, live_in);
+
+ std::unordered_set<uint32_t> live_out{
+ 84, // %84 = OpVariable %8 Function
+ 100, // %100 = OpFAdd %7 %191 %98
+ 124, // %124 = OpVariable %63 Input
+ 176, // %176 = OpVariable %175 Output
+ 196, // %196 = OpPhi %13 %16 %79 %143 %133
+ 197, // %197 = OpPhi %7 %106 %79 %208 %133
+ };
+ CompareSets(live_sets->live_out_, live_out);
+
+ EXPECT_EQ(live_sets->used_registers_, 8u);
+ }
+ {
+ SCOPED_TRACE("Block 109");
+ auto live_sets = register_liveness->Get(109);
+ std::unordered_set<uint32_t> live_inout{
+ 25, // %25 = OpLoad %13 %24
+ 84, // %84 = OpVariable %8 Function
+ 100, // %100 = OpFAdd %7 %191 %98
+ 124, // %124 = OpVariable %63 Input
+ 176, // %176 = OpVariable %175 Output
+ 196, // %196 = OpPhi %13 %16 %79 %143 %133
+ 197, // %197 = OpPhi %7 %106 %79 %208 %133
+ };
+ CompareSets(live_sets->live_in_, live_inout);
+ CompareSets(live_sets->live_out_, live_inout);
+
+ EXPECT_EQ(live_sets->used_registers_, 7u);
+ }
+ {
+ SCOPED_TRACE("Block 117");
+ auto live_sets = register_liveness->Get(117);
+ std::unordered_set<uint32_t> live_inout{
+ 25, // %25 = OpLoad %13 %24
+ 84, // %84 = OpVariable %8 Function
+ 100, // %100 = OpFAdd %7 %191 %98
+ 124, // %124 = OpVariable %63 Input
+ 176, // %176 = OpVariable %175 Output
+ 196, // %196 = OpPhi %13 %16 %79 %143 %133
+ 204, // %204 = OpPhi %13 %16 %109 %129 %118
+ 209, // %209 = OpPhi %7 %197 %109 %181 %118
+ };
+ CompareSets(live_sets->live_in_, live_inout);
+ CompareSets(live_sets->live_out_, live_inout);
+
+ EXPECT_EQ(live_sets->used_registers_, 9u);
+ }
+ {
+ SCOPED_TRACE("Block 118");
+ auto live_sets = register_liveness->Get(118);
+ std::unordered_set<uint32_t> live_in{
+ 25, // %25 = OpLoad %13 %24
+ 84, // %84 = OpVariable %8 Function
+ 100, // %100 = OpFAdd %7 %191 %98
+ 124, // %124 = OpVariable %63 Input
+ 176, // %176 = OpVariable %175 Output
+ 196, // %196 = OpPhi %13 %16 %79 %143 %133
+ 204, // %204 = OpPhi %13 %16 %109 %129 %118
+ 209, // %209 = OpPhi %7 %197 %109 %181 %118
+ };
+ CompareSets(live_sets->live_in_, live_in);
+
+ std::unordered_set<uint32_t> live_out{
+ 25, // %25 = OpLoad %13 %24
+ 84, // %84 = OpVariable %8 Function
+ 100, // %100 = OpFAdd %7 %191 %98
+ 124, // %124 = OpVariable %63 Input
+ 129, // %129 = OpIAdd %13 %204 %33
+ 176, // %176 = OpVariable %175 Output
+ 181, // %181 = OpCompositeInsert %7 %125 %209 3
+ 196, // %196 = OpPhi %13 %16 %79 %143 %133
+ };
+ CompareSets(live_sets->live_out_, live_out);
+
+ EXPECT_EQ(live_sets->used_registers_, 10u);
+ }
+ {
+ SCOPED_TRACE("Block 119");
+ auto live_sets = register_liveness->Get(119);
+ std::unordered_set<uint32_t> live_inout{
+ 25, // %25 = OpLoad %13 %24
+ 84, // %84 = OpVariable %8 Function
+ 100, // %100 = OpFAdd %7 %191 %98
+ 124, // %124 = OpVariable %63 Input
+ 176, // %176 = OpVariable %175 Output
+ 196, // %196 = OpPhi %13 %16 %79 %143 %133
+ 209, // %209 = OpPhi %7 %197 %109 %181 %118
+ };
+ CompareSets(live_sets->live_in_, live_inout);
+ CompareSets(live_sets->live_out_, live_inout);
+
+ EXPECT_EQ(live_sets->used_registers_, 7u);
+ }
+ {
+ SCOPED_TRACE("Block 131");
+ auto live_sets = register_liveness->Get(131);
+ std::unordered_set<uint32_t> live_inout{
+ 25, // %25 = OpLoad %13 %24
+ 84, // %84 = OpVariable %8 Function
+ 100, // %100 = OpFAdd %7 %191 %98
+ 124, // %124 = OpVariable %63 Input
+ 176, // %176 = OpVariable %175 Output
+ 196, // %196 = OpPhi %13 %16 %79 %143 %133
+ 205, // %205 = OpPhi %13 %16 %119 %141 %132
+ 208, // %208 = OpPhi %7 %209 %119 %183 %132
+ };
+ CompareSets(live_sets->live_in_, live_inout);
+ CompareSets(live_sets->live_out_, live_inout);
+
+ EXPECT_EQ(live_sets->used_registers_, 9u);
+ }
+ {
+ SCOPED_TRACE("Block 132");
+ auto live_sets = register_liveness->Get(132);
+ std::unordered_set<uint32_t> live_in{
+ 25, // %25 = OpLoad %13 %24
+ 84, // %84 = OpVariable %8 Function
+ 100, // %100 = OpFAdd %7 %191 %98
+ 124, // %124 = OpVariable %63 Input
+ 176, // %176 = OpVariable %175 Output
+ 196, // %196 = OpPhi %13 %16 %79 %143 %133
+ 205, // %205 = OpPhi %13 %16 %119 %141 %132
+ 208, // %208 = OpPhi %7 %209 %119 %183 %132
+ };
+ CompareSets(live_sets->live_in_, live_in);
+
+ std::unordered_set<uint32_t> live_out{
+ 25, // %25 = OpLoad %13 %24
+ 84, // %84 = OpVariable %8 Function
+ 100, // %100 = OpFAdd %7 %191 %98
+ 124, // %124 = OpVariable %63 Input
+ 141, // %141 = OpIAdd %13 %205 %33
+ 176, // %176 = OpVariable %175 Output
+ 183, // %183 = OpCompositeInsert %7 %138 %208 3
+ 196, // %196 = OpPhi %13 %16 %79 %143 %133
+ };
+ CompareSets(live_sets->live_out_, live_out);
+
+ EXPECT_EQ(live_sets->used_registers_, 10u);
+ }
+ {
+ SCOPED_TRACE("Block 133");
+ auto live_sets = register_liveness->Get(133);
+ std::unordered_set<uint32_t> live_in{
+ 25, // %25 = OpLoad %13 %24
+ 84, // %84 = OpVariable %8 Function
+ 100, // %100 = OpFAdd %7 %191 %98
+ 124, // %124 = OpVariable %63 Input
+ 176, // %176 = OpVariable %175 Output
+ 196, // %196 = OpPhi %13 %16 %79 %143 %133
+ 208, // %208 = OpPhi %7 %209 %119 %183 %132
+ };
+ CompareSets(live_sets->live_in_, live_in);
+
+ std::unordered_set<uint32_t> live_out{
+ 25, // %25 = OpLoad %13 %24
+ 84, // %84 = OpVariable %8 Function
+ 100, // %100 = OpFAdd %7 %191 %98
+ 124, // %124 = OpVariable %63 Input
+ 143, // %143 = OpIAdd %13 %196 %33
+ 176, // %176 = OpVariable %175 Output
+ 208, // %208 = OpPhi %7 %209 %119 %183 %132
+ };
+ CompareSets(live_sets->live_out_, live_out);
+
+ EXPECT_EQ(live_sets->used_registers_, 8u);
+ }
+ {
+ SCOPED_TRACE("Block 110");
+ auto live_sets = register_liveness->Get(110);
+ std::unordered_set<uint32_t> live_in{
+ 84, // %84 = OpVariable %8 Function
+ 100, // %100 = OpFAdd %7 %191 %98
+ 124, // %124 = OpVariable %63 Input
+ 176, // %176 = OpVariable %175 Output
+ 197, // %197 = OpPhi %7 %106 %79 %208 %133
+ };
+ CompareSets(live_sets->live_in_, live_in);
+
+ std::unordered_set<uint32_t> live_out{
+ 84, // %84 = OpVariable %8 Function
+ 124, // %124 = OpVariable %63 Input
+ 150, // %150 = OpVectorShuffle %7 %100 %148 4 5 6 3
+ 176, // %176 = OpVariable %175 Output
+ };
+ CompareSets(live_sets->live_out_, live_out);
+
+ EXPECT_EQ(live_sets->used_registers_, 7u);
+ }
+ {
+ SCOPED_TRACE("Block 152");
+ auto live_sets = register_liveness->Get(152);
+ std::unordered_set<uint32_t> live_inout{
+ 84, // %84 = OpVariable %8 Function
+ 124, // %124 = OpVariable %63 Input
+ 176, // %176 = OpVariable %175 Output
+ 199, // %199 = OpPhi %13 %16 %110 %174 %163
+ 200, // %200 = OpPhi %7 %150 %110 %203 %163
+ };
+ CompareSets(live_sets->live_in_, live_inout);
+ CompareSets(live_sets->live_out_, live_inout);
+
+ EXPECT_EQ(live_sets->used_registers_, 6u);
+ }
+ {
+ SCOPED_TRACE("Block 153");
+ auto live_sets = register_liveness->Get(153);
+ std::unordered_set<uint32_t> live_inout{
+ 84, // %84 = OpVariable %8 Function
+ 124, // %124 = OpVariable %63 Input
+ 176, // %176 = OpVariable %175 Output
+ 199, // %199 = OpPhi %13 %16 %110 %174 %163
+ 200, // %200 = OpPhi %7 %150 %110 %203 %163
+ };
+ CompareSets(live_sets->live_in_, live_inout);
+ CompareSets(live_sets->live_out_, live_inout);
+
+ EXPECT_EQ(live_sets->used_registers_, 5u);
+ }
+ {
+ SCOPED_TRACE("Block 161");
+ auto live_sets = register_liveness->Get(161);
+ std::unordered_set<uint32_t> live_inout{
+ 84, // %84 = OpVariable %8 Function
+ 124, // %124 = OpVariable %63 Input
+ 176, // %176 = OpVariable %175 Output
+ 199, // %199 = OpPhi %13 %16 %110 %174 %163
+ 201, // %201 = OpPhi %13 %16 %153 %172 %162
+ 203, // %203 = OpPhi %7 %200 %153 %170 %162
+ };
+ CompareSets(live_sets->live_in_, live_inout);
+ CompareSets(live_sets->live_out_, live_inout);
+
+ EXPECT_EQ(live_sets->used_registers_, 7u);
+ }
+ {
+ SCOPED_TRACE("Block 162");
+ auto live_sets = register_liveness->Get(162);
+ std::unordered_set<uint32_t> live_in{
+ 84, // %84 = OpVariable %8 Function
+ 124, // %124 = OpVariable %63 Input
+ 176, // %176 = OpVariable %175 Output
+ 199, // %199 = OpPhi %13 %16 %110 %174 %163
+ 201, // %201 = OpPhi %13 %16 %153 %172 %162
+ 203, // %203 = OpPhi %7 %200 %153 %170 %162
+ };
+ CompareSets(live_sets->live_in_, live_in);
+
+ std::unordered_set<uint32_t> live_out{
+ 84, // %84 = OpVariable %8 Function
+ 124, // %124 = OpVariable %63 Input
+ 170, // %170 = OpVectorTimesScalar %7 %203 %168
+ 172, // %172 = OpIAdd %13 %201 %33
+ 176, // %176 = OpVariable %175 Output
+ 199, // %199 = OpPhi %13 %16 %110 %174 %163
+ };
+ CompareSets(live_sets->live_out_, live_out);
+
+ EXPECT_EQ(live_sets->used_registers_, 8u);
+ }
+ {
+ SCOPED_TRACE("Block 163");
+ auto live_sets = register_liveness->Get(163);
+ std::unordered_set<uint32_t> live_in{
+ 84, // %84 = OpVariable %8 Function
+ 124, // %124 = OpVariable %63 Input
+ 176, // %176 = OpVariable %175 Output
+ 199, // %199 = OpPhi %13 %16 %110 %174 %163
+ 203, // %203 = OpPhi %7 %200 %153 %170 %162
+ };
+ CompareSets(live_sets->live_in_, live_in);
+
+ std::unordered_set<uint32_t> live_out{
+ 84, // %84 = OpVariable %8 Function
+ 124, // %124 = OpVariable %63 Input
+ 174, // %174 = OpIAdd %13 %199 %45
+ 176, // %176 = OpVariable %175 Output
+ 203, // %203 = OpPhi %7 %200 %153 %170 %162
+ };
+ CompareSets(live_sets->live_out_, live_out);
+
+ EXPECT_EQ(live_sets->used_registers_, 6u);
+ }
+ {
+ SCOPED_TRACE("Block 154");
+ auto live_sets = register_liveness->Get(154);
+ std::unordered_set<uint32_t> live_in{
+ 84, // %84 = OpVariable %8 Function
+ 176, // %176 = OpVariable %175 Output
+ 200, // %200 = OpPhi %7 %150 %110 %203 %163
+ };
+ CompareSets(live_sets->live_in_, live_in);
+
+ std::unordered_set<uint32_t> live_out{};
+ CompareSets(live_sets->live_out_, live_out);
+
+ EXPECT_EQ(live_sets->used_registers_, 4u);
+ }
+
+ {
+ SCOPED_TRACE("Compute loop pressure");
+ opt::RegisterLiveness::RegionRegisterLiveness loop_reg_pressure;
+ register_liveness->ComputeLoopRegisterPressure(*ld[39], &loop_reg_pressure);
+ // Generate(*context->cfg()->block(39), &loop_reg_pressure);
+ std::unordered_set<uint32_t> live_in{
+ 11, // %11 = OpVariable %10 Input
+ 12, // %12 = OpLoad %7 %11
+ 25, // %25 = OpLoad %13 %24
+ 55, // %55 = OpVariable %54 Input
+ 84, // %84 = OpVariable %8 Function
+ 124, // %124 = OpVariable %63 Input
+ 176, // %176 = OpVariable %175 Output
+ 185, // %185 = OpPhi %13 %16 %19 %75 %51
+ 188, // %188 = OpPhi %6 %37 %19 %73 %51
+ 191, // %191 = OpPhi %7 %12 %5 %31 %18
+ };
+ CompareSets(loop_reg_pressure.live_in_, live_in);
+
+ std::unordered_set<uint32_t> live_out{
+ 12, // %12 = OpLoad %7 %11
+ 25, // %25 = OpLoad %13 %24
+ 55, // %55 = OpVariable %54 Input
+ 84, // %84 = OpVariable %8 Function
+ 124, // %124 = OpVariable %63 Input
+ 176, // %176 = OpVariable %175 Output
+ 188, // %188 = OpPhi %6 %37 %19 %73 %51
+ 191, // %191 = OpPhi %7 %12 %5 %31 %18
+ };
+ CompareSets(loop_reg_pressure.live_out_, live_out);
+
+ EXPECT_EQ(loop_reg_pressure.used_registers_, 13u);
+ }
+
+ {
+ SCOPED_TRACE("Loop Fusion simulation");
+ opt::RegisterLiveness::RegionRegisterLiveness simulation_resut;
+ register_liveness->SimulateFusion(*ld[17], *ld[39], &simulation_resut);
+
+ std::unordered_set<uint32_t> live_in{
+ 11, // %11 = OpVariable %10 Input
+ 12, // %12 = OpLoad %7 %11
+ 24, // %24 = OpVariable %23 Input
+ 25, // %25 = OpLoad %13 %24
+ 28, // %28 = OpVariable %10 Input
+ 55, // %55 = OpVariable %54 Input
+ 84, // %84 = OpVariable %8 Function
+ 124, // %124 = OpVariable %63 Input
+ 176, // %176 = OpVariable %175 Output
+ 184, // %184 = OpPhi %13 %16 %5 %34 %18
+ 185, // %185 = OpPhi %13 %16 %19 %75 %51
+ 188, // %188 = OpPhi %6 %37 %19 %73 %51
+ 191, // %191 = OpPhi %7 %12 %5 %31 %18
+ };
+ CompareSets(simulation_resut.live_in_, live_in);
+
+ std::unordered_set<uint32_t> live_out{
+ 12, // %12 = OpLoad %7 %11
+ 25, // %25 = OpLoad %13 %24
+ 55, // %55 = OpVariable %54 Input
+ 84, // %84 = OpVariable %8 Function
+ 124, // %124 = OpVariable %63 Input
+ 176, // %176 = OpVariable %175 Output
+ 188, // %188 = OpPhi %6 %37 %19 %73 %51
+ 191, // %191 = OpPhi %7 %12 %5 %31 %18
+ };
+ CompareSets(simulation_resut.live_out_, live_out);
+
+ EXPECT_EQ(simulation_resut.used_registers_, 17u);
+ }
+}
+
+TEST_F(PassClassTest, FissionSimulation) {
+ const std::string source = R"(
+ OpCapability Shader
+ %1 = OpExtInstImport "GLSL.std.450"
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint Fragment %2 "main"
+ OpExecutionMode %2 OriginUpperLeft
+ OpSource GLSL 430
+ OpName %2 "main"
+ OpName %3 "i"
+ OpName %4 "A"
+ OpName %5 "B"
+ %6 = OpTypeVoid
+ %7 = OpTypeFunction %6
+ %8 = OpTypeInt 32 1
+ %9 = OpTypePointer Function %8
+ %10 = OpConstant %8 0
+ %11 = OpConstant %8 10
+ %12 = OpTypeBool
+ %13 = OpTypeFloat 32
+ %14 = OpTypeInt 32 0
+ %15 = OpConstant %14 10
+ %16 = OpTypeArray %13 %15
+ %17 = OpTypePointer Function %16
+ %18 = OpTypePointer Function %13
+ %19 = OpConstant %8 1
+ %2 = OpFunction %6 None %7
+ %20 = OpLabel
+ %3 = OpVariable %9 Function
+ %4 = OpVariable %17 Function
+ %5 = OpVariable %17 Function
+ OpBranch %21
+ %21 = OpLabel
+ %22 = OpPhi %8 %10 %20 %23 %24
+ OpLoopMerge %25 %24 None
+ OpBranch %26
+ %26 = OpLabel
+ %27 = OpSLessThan %12 %22 %11
+ OpBranchConditional %27 %28 %25
+ %28 = OpLabel
+ %29 = OpAccessChain %18 %5 %22
+ %30 = OpLoad %13 %29
+ %31 = OpAccessChain %18 %4 %22
+ OpStore %31 %30
+ %32 = OpAccessChain %18 %4 %22
+ %33 = OpLoad %13 %32
+ %34 = OpAccessChain %18 %5 %22
+ OpStore %34 %33
+ OpBranch %24
+ %24 = OpLabel
+ %23 = OpIAdd %8 %22 %19
+ OpBranch %21
+ %25 = OpLabel
+ OpStore %3 %22
+ OpReturn
+ OpFunctionEnd
+ )";
+ std::unique_ptr<ir::IRContext> context =
+ BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, source,
+ SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
+ ir::Module* module = context->module();
+ EXPECT_NE(nullptr, module) << "Assembling failed for shader:\n"
+ << source << std::endl;
+ ir::Function* f = &*module->begin();
+ opt::LivenessAnalysis* liveness_analysis = context->GetLivenessAnalysis();
+ const opt::RegisterLiveness* register_liveness = liveness_analysis->Get(f);
+ ir::LoopDescriptor& ld = *context->GetLoopDescriptor(f);
+ opt::analysis::DefUseManager& def_use_mgr = *context->get_def_use_mgr();
+
+ {
+ opt::RegisterLiveness::RegionRegisterLiveness l1_sim_resut;
+ opt::RegisterLiveness::RegionRegisterLiveness l2_sim_resut;
+ std::unordered_set<ir::Instruction*> moved_instructions{
+ def_use_mgr.GetDef(29), def_use_mgr.GetDef(30), def_use_mgr.GetDef(31),
+ def_use_mgr.GetDef(31)->NextNode()};
+ std::unordered_set<ir::Instruction*> copied_instructions{
+ def_use_mgr.GetDef(22), def_use_mgr.GetDef(27),
+ def_use_mgr.GetDef(27)->NextNode(), def_use_mgr.GetDef(23)};
+
+ register_liveness->SimulateFission(*ld[21], moved_instructions,
+ copied_instructions, &l1_sim_resut,
+ &l2_sim_resut);
+ {
+ SCOPED_TRACE("L1 simulation");
+ std::unordered_set<uint32_t> live_in{
+ 3, // %3 = OpVariable %9 Function
+ 4, // %4 = OpVariable %17 Function
+ 5, // %5 = OpVariable %17 Function
+ 22, // %22 = OpPhi %8 %10 %20 %23 %24
+ };
+ CompareSets(l1_sim_resut.live_in_, live_in);
+
+ std::unordered_set<uint32_t> live_out{
+ 3, // %3 = OpVariable %9 Function
+ 4, // %4 = OpVariable %17 Function
+ 5, // %5 = OpVariable %17 Function
+ 22, // %22 = OpPhi %8 %10 %20 %23 %24
+ };
+ CompareSets(l1_sim_resut.live_out_, live_out);
+
+ EXPECT_EQ(l1_sim_resut.used_registers_, 6u);
+ }
+ {
+ SCOPED_TRACE("L2 simulation");
+ std::unordered_set<uint32_t> live_in{
+ 3, // %3 = OpVariable %9 Function
+ 4, // %4 = OpVariable %17 Function
+ 5, // %5 = OpVariable %17 Function
+ 22, // %22 = OpPhi %8 %10 %20 %23 %24
+ };
+ CompareSets(l2_sim_resut.live_in_, live_in);
+
+ std::unordered_set<uint32_t> live_out{
+ 3, // %3 = OpVariable %9 Function
+ 22, // %22 = OpPhi %8 %10 %20 %23 %24
+ };
+ CompareSets(l2_sim_resut.live_out_, live_out);
+
+ EXPECT_EQ(l2_sim_resut.used_registers_, 6u);
+ }
+ }
+}
+} // namespace
