blob: a4e61900bc7bd5c4311e7cada35f30982b7170d3 [file] [log] [blame]
// Copyright (c) 2018 Google LLC.
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
// 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 <list>
#include <memory>
#include <unordered_map>
#include <vector>
#include "source/opt/ir_context.h"
#include "source/opt/loop_descriptor.h"
namespace spvtools {
namespace opt {
// Class to gather some metrics about a Region Of Interest (ROI).
// So far it counts the number of instructions in a ROI (excluding debug
// and label instructions) per basic block and in total.
struct CodeMetrics {
void Analyze(const Loop& loop);
// The number of instructions per basic block in the ROI.
std::unordered_map<uint32_t, size_t> block_sizes_;
// Number of instruction in the ROI.
size_t roi_size_;
// LoopUtils is used to encapsulte loop optimizations and from the passes which
// use them. Any pass which needs a loop optimization should do it through this
// or through a pass which is using this.
class LoopUtils {
// Holds a auxiliary results of the loop cloning procedure.
struct LoopCloningResult {
using ValueMapTy = std::unordered_map<uint32_t, uint32_t>;
using BlockMapTy = std::unordered_map<uint32_t, BasicBlock*>;
using PtrMap = std::unordered_map<Instruction*, Instruction*>;
PtrMap ptr_map_;
// Mapping between the original loop ids and the new one.
ValueMapTy value_map_;
// Mapping between original loop blocks to the cloned one.
BlockMapTy old_to_new_bb_;
// Mapping between the cloned loop blocks to original one.
BlockMapTy new_to_old_bb_;
// List of cloned basic block.
std::vector<std::unique_ptr<BasicBlock>> cloned_bb_;
LoopUtils(IRContext* context, Loop* loop)
: context_(context),
function_(*loop_->GetHeaderBlock()->GetParent()) {}
// The converts the current loop to loop closed SSA form.
// In the loop closed SSA, all loop exiting values go through a dedicated Phi
// instruction. For instance:
// for (...) {
// A1 = ...
// if (...)
// A2 = ...
// A = phi A1, A2
// }
// ... = op A ...
// Becomes
// for (...) {
// A1 = ...
// if (...)
// A2 = ...
// A = phi A1, A2
// }
// C = phi A
// ... = op C ...
// This makes some loop transformations (such as loop unswitch) simpler
// (removes the needs to take care of exiting variables).
void MakeLoopClosedSSA();
// Create dedicate exit basic block. This ensure all exit basic blocks has the
// loop as sole predecessors.
// By construction, structured control flow already has a dedicated exit
// block.
// Preserves: CFG, def/use and instruction to block mapping.
void CreateLoopDedicatedExits();
// Clone |loop_| and remap its instructions. Newly created blocks
// will be added to the |cloning_result.cloned_bb_| list, correctly ordered to
// be inserted into a function.
// It is assumed that |ordered_loop_blocks| is compatible with the result of
// |Loop::ComputeLoopStructuredOrder|. If the preheader and merge block are in
// the list they will also be cloned. If not, the resulting loop will share
// them with the original loop.
// The function preserves the def/use, cfg and instr to block analyses.
// The cloned loop nest will be added to the loop descriptor and will have
// ownership.
Loop* CloneLoop(LoopCloningResult* cloning_result,
const std::vector<BasicBlock*>& ordered_loop_blocks) const;
// Clone |loop_| and remap its instructions, as above. Overload to compute
// loop block ordering within method rather than taking in as parameter.
Loop* CloneLoop(LoopCloningResult* cloning_result) const;
// Clone the |loop_| and make the new loop branch to the second loop on exit.
Loop* CloneAndAttachLoopToHeader(LoopCloningResult* cloning_result);
// Perfom a partial unroll of |loop| by given |factor|. This will copy the
// body of the loop |factor| times. So a |factor| of one would give a new loop
// with the original body plus one unrolled copy body.
bool PartiallyUnroll(size_t factor);
// Fully unroll |loop|.
bool FullyUnroll();
// This function validates that |loop| meets the assumptions made by the
// implementation of the loop unroller. As the implementation accommodates
// more types of loops this function can reduce its checks.
// The conditions checked to ensure the loop can be unrolled are as follows:
// 1. That the loop is in structured order.
// 2. That the continue block is a branch to the header.
// 3. That the only phi used in the loop is the induction variable.
// TODO( This is a temporary mesure, after the loop is
// converted into LCSAA form and has a single entry and exit we can rewrite
// the other phis.
// 4. That this is an inner most loop, or that loops contained within this
// loop have already been fully unrolled.
// 5. That each instruction in the loop is only used within the loop.
// (Related to the above phi condition).
bool CanPerformUnroll();
// Maintains the loop descriptor object after the unroll functions have been
// called, otherwise the analysis should be invalidated.
void Finalize();
// Returns the context associate to |loop_|.
IRContext* GetContext() { return context_; }
// Returns the loop descriptor owning |loop_|.
LoopDescriptor* GetLoopDescriptor() { return loop_desc_; }
// Returns the loop on which the object operates on.
Loop* GetLoop() const { return loop_; }
// Returns the function that |loop_| belong to.
Function* GetFunction() const { return &function_; }
IRContext* context_;
LoopDescriptor* loop_desc_;
Loop* loop_;
Function& function_;
// Populates the loop nest of |new_loop| according to |loop_| nest.
void PopulateLoopNest(Loop* new_loop,
const LoopCloningResult& cloning_result) const;
// Populates |new_loop| descriptor according to |old_loop|'s one.
void PopulateLoopDesc(Loop* new_loop, Loop* old_loop,
const LoopCloningResult& cloning_result) const;
} // namespace opt
} // namespace spvtools