blob: d61d6783c862e0f1bbbaaa45f8e76206af0cc1ac [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 <map>
#include <set>
#include <utility>
#include <vector>
#include "source/opt/ir_context.h"
#include "source/opt/loop_descriptor.h"
#include "source/opt/loop_utils.h"
#include "source/opt/scalar_analysis.h"
namespace spvtools {
namespace opt {
class LoopFusion {
LoopFusion(IRContext* context, Loop* loop_0, Loop* loop_1)
: context_(context),
containing_function_(loop_0->GetHeaderBlock()->GetParent()) {}
// Checks if the |loop_0| and |loop_1| are compatible for fusion.
// That means:
// * they both have one induction variable
// * they have the same upper and lower bounds
// - same inital value
// - same condition
// * they have the same update step
// * they are adjacent, with |loop_0| appearing before |loop_1|
// * there are no break/continue in either of them
// * they both have pre-header blocks (required for ScalarEvolutionAnalysis
// and dependence checking).
bool AreCompatible();
// Checks if compatible |loop_0| and |loop_1| are legal to fuse.
// * fused loops do not have any dependencies with dependence distance greater
// than 0 that did not exist in the original loops.
// * there are no function calls in the loops (could have side-effects)
bool IsLegal();
// Perform the actual fusion of |loop_0_| and |loop_1_|. The loops have to be
// compatible and the fusion has to be legal.
void Fuse();
// Check that the initial values are the same.
bool CheckInit();
// Check that the conditions are the same.
bool CheckCondition();
// Check that the steps are the same.
bool CheckStep();
// Returns |true| if |instruction| is used in the continue or condition block
// of |loop|.
bool UsedInContinueOrConditionBlock(Instruction* instruction, Loop* loop);
// Remove entries in |instructions| that are not used in the continue or
// condition block of |loop|.
void RemoveIfNotUsedContinueOrConditionBlock(
std::vector<Instruction*>* instructions, Loop* loop);
// Returns |true| if |instruction| is used in |loop|.
bool IsUsedInLoop(Instruction* instruction, Loop* loop);
// Returns |true| if |loop| has at least one barrier or function call.
bool ContainsBarriersOrFunctionCalls(Loop* loop);
// Get all instructions in the |loop| (except in the latch block) that have
// the opcode |opcode|.
std::pair<std::vector<Instruction*>, std::vector<Instruction*>>
GetLoadsAndStoresInLoop(Loop* loop);
// Given a vector of memory operations (OpLoad/OpStore), constructs a map from
// variables to the loads/stores that those variables.
std::map<Instruction*, std::vector<Instruction*>> LocationToMemOps(
const std::vector<Instruction*>& mem_ops);
IRContext* context_;
// The original loops to be fused.
Loop* loop_0_;
Loop* loop_1_;
// The function that contains |loop_0_| and |loop_1_|.
Function* containing_function_ = nullptr;
// The induction variables for |loop_0_| and |loop_1_|.
Instruction* induction_0_ = nullptr;
Instruction* induction_1_ = nullptr;
} // namespace opt
} // namespace spvtools