blob: df012274c09a980a45893ad28eab8dae6c9c5984 [file] [log] [blame]
// Copyright (c) 2017 Google Inc.
// 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
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// See the License for the specific language governing permissions and
// limitations under the License.
#include <algorithm>
#include <cstdint>
#include <map>
#include <memory>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
#include "source/opt/basic_block.h"
#include "source/opt/dominator_analysis.h"
#include "source/opt/module.h"
#include "source/opt/tree_iterator.h"
namespace spvtools {
namespace opt {
class IRContext;
class CFG;
class LoopDescriptor;
// A class to represent and manipulate a loop in structured control flow.
class Loop {
// The type used to represent nested child loops.
using ChildrenList = std::vector<Loop*>;
using iterator = ChildrenList::iterator;
using const_iterator = ChildrenList::const_iterator;
using BasicBlockListTy = std::unordered_set<uint32_t>;
explicit Loop(IRContext* context)
: context_(context),
loop_is_marked_for_removal_(false) {}
Loop(IRContext* context, DominatorAnalysis* analysis, BasicBlock* header,
BasicBlock* continue_target, BasicBlock* merge_target);
// Iterators over the immediate sub-loops.
inline iterator begin() { return nested_loops_.begin(); }
inline iterator end() { return nested_loops_.end(); }
inline const_iterator begin() const { return cbegin(); }
inline const_iterator end() const { return cend(); }
inline const_iterator cbegin() const { return nested_loops_.begin(); }
inline const_iterator cend() const { return nested_loops_.end(); }
// Returns the header (first basic block of the loop). This block contains the
// OpLoopMerge instruction.
inline BasicBlock* GetHeaderBlock() { return loop_header_; }
inline const BasicBlock* GetHeaderBlock() const { return loop_header_; }
inline void SetHeaderBlock(BasicBlock* header) { loop_header_ = header; }
// Updates the OpLoopMerge instruction to reflect the current state of the
// loop.
inline void UpdateLoopMergeInst() {
assert(GetHeaderBlock()->GetLoopMergeInst() &&
"The loop is not structured");
Instruction* merge_inst = GetHeaderBlock()->GetLoopMergeInst();
merge_inst->SetInOperand(0, {GetMergeBlock()->id()});
// Returns the continue target basic block. This is the block designated as
// the continue target by the OpLoopMerge instruction.
inline BasicBlock* GetContinueBlock() { return loop_continue_; }
inline const BasicBlock* GetContinueBlock() const { return loop_continue_; }
// Returns the latch basic block (basic block that holds the back-edge).
// These functions return nullptr if the loop is not structured (i.e. if it
// has more than one backedge).
inline BasicBlock* GetLatchBlock() { return loop_latch_; }
inline const BasicBlock* GetLatchBlock() const { return loop_latch_; }
// Sets |latch| as the loop unique block branching back to the header.
// A latch block must have the following properties:
// - |latch| must be in the loop;
// - must be the only block branching back to the header block.
void SetLatchBlock(BasicBlock* latch);
// Sets |continue_block| as the continue block of the loop. This should be the
// continue target of the OpLoopMerge and should dominate the latch block.
void SetContinueBlock(BasicBlock* continue_block);
// Returns the basic block which marks the end of the loop.
// These functions return nullptr if the loop is not structured.
inline BasicBlock* GetMergeBlock() { return loop_merge_; }
inline const BasicBlock* GetMergeBlock() const { return loop_merge_; }
// Sets |merge| as the loop merge block. A merge block must have the following
// properties:
// - |merge| must not be in the loop;
// - all its predecessors must be in the loop.
// - it must not be already used as merge block.
// If the loop has an OpLoopMerge in its header, this instruction is also
// updated.
void SetMergeBlock(BasicBlock* merge);
// Returns the loop pre-header, nullptr means that the loop predecessor does
// not qualify as a preheader.
// The preheader is the unique predecessor that:
// - Dominates the loop header;
// - Has only the loop header as successor.
inline BasicBlock* GetPreHeaderBlock() { return loop_preheader_; }
// Returns the loop pre-header.
inline const BasicBlock* GetPreHeaderBlock() const { return loop_preheader_; }
// Sets |preheader| as the loop preheader block. A preheader block must have
// the following properties:
// - |merge| must not be in the loop;
// - have an unconditional branch to the loop header.
void SetPreHeaderBlock(BasicBlock* preheader);
// Returns the loop pre-header, if there is no suitable preheader it will be
// created. Returns |nullptr| if it fails to create the preheader.
BasicBlock* GetOrCreatePreHeaderBlock();
// Returns true if this loop contains any nested loops.
inline bool HasNestedLoops() const { return nested_loops_.size() != 0; }
// Clears and fills |exit_blocks| with all basic blocks that are not in the
// loop and has at least one predecessor in the loop.
void GetExitBlocks(std::unordered_set<uint32_t>* exit_blocks) const;
// 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(std::unordered_set<uint32_t>* merging_blocks) const;
// Returns true if the loop is in a Loop Closed SSA form.
// In LCSSA form, all in-loop definitions are used in the loop or in phi
// instructions in the loop exit blocks.
bool IsLCSSA() const;
// Returns the depth of this loop in the loop nest.
// The outer-most loop has a depth of 1.
inline size_t GetDepth() const {
size_t lvl = 1;
for (const Loop* loop = GetParent(); loop; loop = loop->GetParent()) lvl++;
return lvl;
inline size_t NumImmediateChildren() const { return nested_loops_.size(); }
inline bool HasChildren() const { return !nested_loops_.empty(); }
// Adds |nested| as a nested loop of this loop. Automatically register |this|
// as the parent of |nested|.
inline void AddNestedLoop(Loop* nested) {
assert(!nested->GetParent() && "The loop has another parent.");
inline Loop* GetParent() { return parent_; }
inline const Loop* GetParent() const { return parent_; }
inline bool HasParent() const { return parent_; }
// Returns true if this loop is itself nested within another loop.
inline bool IsNested() const { return parent_ != nullptr; }
// Returns the set of all basic blocks contained within the loop. Will be all
// BasicBlocks dominated by the header which are not also dominated by the
// loop merge block.
inline const BasicBlockListTy& GetBlocks() const {
return loop_basic_blocks_;
// Returns true if the basic block |bb| is inside this loop.
inline bool IsInsideLoop(const BasicBlock* bb) const {
return IsInsideLoop(bb->id());
// Returns true if the basic block id |bb_id| is inside this loop.
inline bool IsInsideLoop(uint32_t bb_id) const {
return loop_basic_blocks_.count(bb_id);
// Returns true if the instruction |inst| is inside this loop.
bool IsInsideLoop(Instruction* inst) const;
// Adds the Basic Block |bb| to this loop and its parents.
void AddBasicBlock(const BasicBlock* bb) { AddBasicBlock(bb->id()); }
// Adds the Basic Block with |id| to this loop and its parents.
void AddBasicBlock(uint32_t id) {
for (Loop* loop = this; loop != nullptr; loop = loop->parent_) {
// Removes the Basic Block id |bb_id| from this loop and its parents.
// It the user responsibility to make sure the removed block is not a merge,
// header or continue block.
void RemoveBasicBlock(uint32_t bb_id) {
for (Loop* loop = this; loop != nullptr; loop = loop->parent_) {
// Removes all the basic blocks from the set of basic blocks within the loop.
// This does not affect any of the stored pointers to the header, preheader,
// merge, or continue blocks.
void ClearBlocks() { loop_basic_blocks_.clear(); }
// Adds the Basic Block |bb| this loop and its parents.
void AddBasicBlockToLoop(const BasicBlock* bb) {
assert(IsBasicBlockInLoopSlow(bb) &&
"Basic block does not belong to the loop");
// Returns the list of induction variables within the loop.
void GetInductionVariables(std::vector<Instruction*>& inductions) const;
// This function uses the |condition| to find the induction variable which is
// used by the loop condition within the loop. This only works if the loop is
// bound by a single condition and single induction variable.
Instruction* FindConditionVariable(const BasicBlock* condition) const;
// Returns the number of iterations within a loop when given the |induction|
// variable and the loop |condition| check. It stores the found number of
// iterations in the output parameter |iterations| and optionally, the step
// value in |step_value| and the initial value of the induction variable in
// |init_value|.
bool FindNumberOfIterations(const Instruction* induction,
const Instruction* condition, size_t* iterations,
int64_t* step_amount = nullptr,
int64_t* init_value = nullptr) const;
// Returns the value of the OpLoopMerge control operand as a bool. Loop
// control can be None(0), Unroll(1), or DontUnroll(2). This function returns
// true if it is set to Unroll.
inline bool HasUnrollLoopControl() const {
if (!loop_header_->GetLoopMergeInst()) return false;
return loop_header_->GetLoopMergeInst()->GetSingleWordOperand(2) == 1;
// Finds the conditional block with a branch to the merge and continue blocks
// within the loop body.
BasicBlock* FindConditionBlock() const;
// Remove the child loop form this loop.
inline void RemoveChildLoop(Loop* loop) {
std::find(nested_loops_.begin(), nested_loops_.end(), loop));
// Mark this loop to be removed later by a call to
// LoopDescriptor::PostModificationCleanup.
inline void MarkLoopForRemoval() { loop_is_marked_for_removal_ = true; }
// Returns whether or not this loop has been marked for removal.
inline bool IsMarkedForRemoval() const { return loop_is_marked_for_removal_; }
// Returns true if all nested loops have been marked for removal.
inline bool AreAllChildrenMarkedForRemoval() const {
for (const Loop* child : nested_loops_) {
if (!child->IsMarkedForRemoval()) {
return false;
return true;
// Checks if the loop contains any instruction that will prevent it from being
// cloned. If the loop is structured, the merge construct is also considered.
bool IsSafeToClone() const;
// Sets the parent loop of this loop, that is, a loop which contains this 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);
// Extract the initial value from the |induction| variable and store it in
// |value|. If the function couldn't find the initial value of |induction|
// return false.
bool GetInductionInitValue(const Instruction* induction,
int64_t* value) const;
// Takes in a phi instruction |induction| and the loop |header| and returns
// the step operation of the loop.
Instruction* GetInductionStepOperation(const Instruction* induction) const;
// Returns true if we can deduce the number of loop iterations in the step
// operation |step|. IsSupportedCondition must also be true for the condition
// instruction.
bool IsSupportedStepOp(SpvOp step) const;
// Returns true if we can deduce the number of loop iterations in the
// condition operation |condition|. IsSupportedStepOp must also be true for
// the step instruction.
bool IsSupportedCondition(SpvOp condition) const;
// Creates the list of the loop's basic block in structured order and store
// the result in |ordered_loop_blocks|. If |include_pre_header| is true, the
// pre-header block will also be included at the beginning of the list if it
// exist. If |include_merge| is true, the merge block will also be included at
// the end of the list if it exist.
void ComputeLoopStructuredOrder(std::vector<BasicBlock*>* ordered_loop_blocks,
bool include_pre_header = false,
bool include_merge = false) const;
// Given the loop |condition|, |initial_value|, |step_value|, the trip count
// |number_of_iterations|, and the |unroll_factor| requested, get the new
// condition value for the residual loop.
static int64_t GetResidualConditionValue(SpvOp condition,
int64_t initial_value,
int64_t step_value,
size_t number_of_iterations,
size_t unroll_factor);
// Returns the condition instruction for entry into the loop
// Returns nullptr if it can't be found.
Instruction* GetConditionInst() const;
// Returns the context associated this loop.
IRContext* GetContext() const { return context_; }
// Looks at all the blocks with a branch to the header block to find one
// which is also dominated by the loop continue block. This block is the latch
// block. The specification mandates that this block should exist, therefore
// this function will assert if it is not found.
BasicBlock* FindLatchBlock();
IRContext* context_;
// The block which marks the start of the loop.
BasicBlock* loop_header_;
// The block which begins the body of the loop.
BasicBlock* loop_continue_;
// The block which marks the end of the loop.
BasicBlock* loop_merge_;
// The block immediately before the loop header.
BasicBlock* loop_preheader_;
// The block containing the backedge to the loop header.
BasicBlock* loop_latch_;
// A parent of a loop is the loop which contains it as a nested child loop.
Loop* parent_;
// Nested child loops of this loop.
ChildrenList nested_loops_;
// A set of all the basic blocks which comprise the loop structure. Will be
// computed only when needed on demand.
BasicBlockListTy loop_basic_blocks_;
// Check that |bb| is inside the loop using domination property.
// Note: this is for assertion purposes only, IsInsideLoop should be used
// instead.
bool IsBasicBlockInLoopSlow(const BasicBlock* bb);
// Returns the loop preheader if it exists, returns nullptr otherwise.
BasicBlock* FindLoopPreheader(DominatorAnalysis* dom_analysis);
// Sets |latch| as the loop unique latch block. No checks are performed
// here.
inline void SetLatchBlockImpl(BasicBlock* latch) { loop_latch_ = latch; }
// Sets |merge| as the loop merge block. No checks are performed here.
inline void SetMergeBlockImpl(BasicBlock* merge) { loop_merge_ = merge; }
// Each different loop |condition| affects how we calculate the number of
// iterations using the |condition_value|, |init_value|, and |step_values| of
// the induction variable. This method will return the number of iterations in
// a loop with those values for a given |condition|. Returns 0 if the number
// of iterations could not be computed.
int64_t GetIterations(SpvOp condition, int64_t condition_value,
int64_t init_value, int64_t step_value) const;
// This is to allow for loops to be removed mid iteration without invalidating
// the iterators.
bool loop_is_marked_for_removal_;
// This is only to allow LoopDescriptor::placeholder_top_loop_ to add top
// level loops as child.
friend class LoopDescriptor;
friend class LoopUtils;
// Loop descriptions class for a given function.
// For a given function, the class builds loop nests information.
// The analysis expects a structured control flow.
class LoopDescriptor {
// Iterator interface (depth first postorder traversal).
using iterator = PostOrderTreeDFIterator<Loop>;
using const_iterator = PostOrderTreeDFIterator<const Loop>;
using pre_iterator = TreeDFIterator<Loop>;
using const_pre_iterator = TreeDFIterator<const Loop>;
// Creates a loop object for all loops found in |f|.
LoopDescriptor(IRContext* context, const Function* f);
// Disable copy constructor, to avoid double-free on destruction.
LoopDescriptor(const LoopDescriptor&) = delete;
// Move constructor.
LoopDescriptor(LoopDescriptor&& other) : placeholder_top_loop_(nullptr) {
// We need to take ownership of the Loop objects in the other
// LoopDescriptor, to avoid double-free.
loops_ = std::move(other.loops_);
basic_block_to_loop_ = std::move(other.basic_block_to_loop_);
placeholder_top_loop_ = std::move(other.placeholder_top_loop_);
// Destructor
// Returns the number of loops found in the function.
inline size_t NumLoops() const { return loops_.size(); }
// Returns the loop at a particular |index|. The |index| must be in bounds,
// check with NumLoops before calling.
inline Loop& GetLoopByIndex(size_t index) const {
assert(loops_.size() > index &&
"Index out of range (larger than loop count)");
return *loops_[index];
// Returns the loops in |this| in the order their headers appear in the
// binary.
std::vector<Loop*> GetLoopsInBinaryLayoutOrder();
// Returns the inner most loop that contains the basic block id |block_id|.
inline Loop* operator[](uint32_t block_id) const {
return FindLoopForBasicBlock(block_id);
// Returns the inner most loop that contains the basic block |bb|.
inline Loop* operator[](const BasicBlock* bb) const {
return (*this)[bb->id()];
// Iterators for post order depth first traversal of the loops.
// Inner most loops will be visited first.
inline iterator begin() { return iterator::begin(&placeholder_top_loop_); }
inline iterator end() { return iterator::end(&placeholder_top_loop_); }
inline const_iterator begin() const { return cbegin(); }
inline const_iterator end() const { return cend(); }
inline const_iterator cbegin() const {
return const_iterator::begin(&placeholder_top_loop_);
inline const_iterator cend() const {
return const_iterator::end(&placeholder_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(&placeholder_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(&placeholder_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;
// Mark the loop |loop_to_add| as needing to be added when the user calls
// PostModificationCleanup. |parent| may be null.
inline void AddLoop(std::unique_ptr<Loop>&& loop_to_add, Loop* parent) {
loops_to_add_.emplace_back(std::make_pair(parent, std::move(loop_to_add)));
// Checks all loops in |this| and will create pre-headers for all loops
// that don't have one. Returns |true| if any blocks were created.
bool CreatePreHeaderBlocksIfMissing();
// Should be called to preserve the LoopAnalysis after loops have been marked
// for addition with AddLoop or MarkLoopForRemoval.
void PostModificationCleanup();
// Removes the basic block id |bb_id| from the block to loop mapping.
inline void ForgetBasicBlock(uint32_t bb_id) {
// Adds the loop |new_loop| and all its nested loops to the descriptor set.
// The object takes ownership of all the loops.
Loop* AddLoopNest(std::unique_ptr<Loop> new_loop);
// Remove the loop |loop|.
void RemoveLoop(Loop* loop);
void SetAsTopLoop(Loop* loop) {
assert(std::find(placeholder_top_loop_.begin(), placeholder_top_loop_.end(),
loop) == placeholder_top_loop_.end() &&
"already registered");
Loop* GetPlaceholderRootLoop() { return &placeholder_top_loop_; }
const Loop* GetPlaceholderRootLoop() const { return &placeholder_top_loop_; }
// TODO(dneto): This should be a vector of unique_ptr. But VisualStudio 2013
// is unable to compile it.
using LoopContainerType = std::vector<Loop*>;
using LoopsToAddContainerType =
std::vector<std::pair<Loop*, std::unique_ptr<Loop>>>;
// Creates loop descriptors for the function |f|.
void PopulateList(IRContext* context, const Function* f);
// Returns the inner most loop that contains the basic block id |block_id|.
inline Loop* FindLoopForBasicBlock(uint32_t block_id) const {
std::unordered_map<uint32_t, Loop*>::const_iterator it =
return it != basic_block_to_loop_.end() ? it->second : nullptr;
// Erase all the loop information.
void ClearLoops();
// A list of all the loops in the function. This variable owns the Loop
// objects.
LoopContainerType loops_;
// Placeholder root: this "loop" is only there to help iterators creation.
Loop placeholder_top_loop_;
std::unordered_map<uint32_t, Loop*> basic_block_to_loop_;
// List of the loops marked for addition when PostModificationCleanup is
// called.
LoopsToAddContainerType loops_to_add_;
} // namespace opt
} // namespace spvtools