blob: 582c8d0acbd9997415b0a87cf95788a25ede7cf7 [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
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
#ifndef SOURCE_OPT_LOOP_DEPENDENCE_H_
#define SOURCE_OPT_LOOP_DEPENDENCE_H_
#include <algorithm>
#include <cstdint>
#include <list>
#include <map>
#include <memory>
#include <ostream>
#include <set>
#include <string>
#include <utility>
#include <vector>
#include "source/opt/instruction.h"
#include "source/opt/ir_context.h"
#include "source/opt/loop_descriptor.h"
#include "source/opt/scalar_analysis.h"
namespace spvtools {
namespace opt {
// Stores information about dependence between a load and a store wrt a single
// loop in a loop nest.
// DependenceInformation
// * UNKNOWN if no dependence information can be gathered or is gathered
// for it.
// * DIRECTION if a dependence direction could be found, but not a
// distance.
// * DISTANCE if a dependence distance could be found.
// * PEEL if peeling either the first or last iteration will break
// dependence between the given load and store.
// * IRRELEVANT if it has no effect on the dependence between the given
// load and store.
//
// If peel_first == true, the analysis has found that peeling the first
// iteration of this loop will break dependence.
//
// If peel_last == true, the analysis has found that peeling the last iteration
// of this loop will break dependence.
class DistanceEntry {
public:
enum DependenceInformation {
UNKNOWN = 0,
DIRECTION = 1,
DISTANCE = 2,
PEEL = 3,
IRRELEVANT = 4,
POINT = 5
};
enum Directions {
NONE = 0,
LT = 1,
EQ = 2,
LE = 3,
GT = 4,
NE = 5,
GE = 6,
ALL = 7
};
DependenceInformation dependence_information;
Directions direction;
int64_t distance;
bool peel_first;
bool peel_last;
int64_t point_x;
int64_t point_y;
DistanceEntry()
: dependence_information(DependenceInformation::UNKNOWN),
direction(Directions::ALL),
distance(0),
peel_first(false),
peel_last(false),
point_x(0),
point_y(0) {}
explicit DistanceEntry(Directions direction_)
: dependence_information(DependenceInformation::DIRECTION),
direction(direction_),
distance(0),
peel_first(false),
peel_last(false),
point_x(0),
point_y(0) {}
DistanceEntry(Directions direction_, int64_t distance_)
: dependence_information(DependenceInformation::DISTANCE),
direction(direction_),
distance(distance_),
peel_first(false),
peel_last(false),
point_x(0),
point_y(0) {}
DistanceEntry(int64_t x, int64_t y)
: dependence_information(DependenceInformation::POINT),
direction(Directions::ALL),
distance(0),
peel_first(false),
peel_last(false),
point_x(x),
point_y(y) {}
bool operator==(const DistanceEntry& rhs) const {
return direction == rhs.direction && peel_first == rhs.peel_first &&
peel_last == rhs.peel_last && distance == rhs.distance &&
point_x == rhs.point_x && point_y == rhs.point_y;
}
bool operator!=(const DistanceEntry& rhs) const { return !(*this == rhs); }
};
// Stores a vector of DistanceEntrys, one per loop in the analysis.
// A DistanceVector holds all of the information gathered in a dependence
// analysis wrt the loops stored in the LoopDependenceAnalysis performing the
// analysis.
class DistanceVector {
public:
explicit DistanceVector(size_t size) : entries(size, DistanceEntry{}) {}
explicit DistanceVector(std::vector<DistanceEntry> entries_)
: entries(entries_) {}
DistanceEntry& GetEntry(size_t index) { return entries[index]; }
const DistanceEntry& GetEntry(size_t index) const { return entries[index]; }
std::vector<DistanceEntry>& GetEntries() { return entries; }
const std::vector<DistanceEntry>& GetEntries() const { return entries; }
bool operator==(const DistanceVector& rhs) const {
if (entries.size() != rhs.entries.size()) {
return false;
}
for (size_t i = 0; i < entries.size(); ++i) {
if (entries[i] != rhs.entries[i]) {
return false;
}
}
return true;
}
bool operator!=(const DistanceVector& rhs) const { return !(*this == rhs); }
private:
std::vector<DistanceEntry> entries;
};
class DependenceLine;
class DependenceDistance;
class DependencePoint;
class DependenceNone;
class DependenceEmpty;
class Constraint {
public:
explicit Constraint(const Loop* loop) : loop_(loop) {}
enum ConstraintType { Line, Distance, Point, None, Empty };
virtual ConstraintType GetType() const = 0;
virtual ~Constraint() {}
// Get the loop this constraint belongs to.
const Loop* GetLoop() const { return loop_; }
bool operator==(const Constraint& other) const;
bool operator!=(const Constraint& other) const;
#define DeclareCastMethod(target) \
virtual target* As##target() { return nullptr; } \
virtual const target* As##target() const { return nullptr; }
DeclareCastMethod(DependenceLine);
DeclareCastMethod(DependenceDistance);
DeclareCastMethod(DependencePoint);
DeclareCastMethod(DependenceNone);
DeclareCastMethod(DependenceEmpty);
#undef DeclareCastMethod
protected:
const Loop* loop_;
};
class DependenceLine : public Constraint {
public:
DependenceLine(SENode* a, SENode* b, SENode* c, const Loop* loop)
: Constraint(loop), a_(a), b_(b), c_(c) {}
ConstraintType GetType() const final { return Line; }
DependenceLine* AsDependenceLine() final { return this; }
const DependenceLine* AsDependenceLine() const final { return this; }
SENode* GetA() const { return a_; }
SENode* GetB() const { return b_; }
SENode* GetC() const { return c_; }
private:
SENode* a_;
SENode* b_;
SENode* c_;
};
class DependenceDistance : public Constraint {
public:
DependenceDistance(SENode* distance, const Loop* loop)
: Constraint(loop), distance_(distance) {}
ConstraintType GetType() const final { return Distance; }
DependenceDistance* AsDependenceDistance() final { return this; }
const DependenceDistance* AsDependenceDistance() const final { return this; }
SENode* GetDistance() const { return distance_; }
private:
SENode* distance_;
};
class DependencePoint : public Constraint {
public:
DependencePoint(SENode* source, SENode* destination, const Loop* loop)
: Constraint(loop), source_(source), destination_(destination) {}
ConstraintType GetType() const final { return Point; }
DependencePoint* AsDependencePoint() final { return this; }
const DependencePoint* AsDependencePoint() const final { return this; }
SENode* GetSource() const { return source_; }
SENode* GetDestination() const { return destination_; }
private:
SENode* source_;
SENode* destination_;
};
class DependenceNone : public Constraint {
public:
DependenceNone() : Constraint(nullptr) {}
ConstraintType GetType() const final { return None; }
DependenceNone* AsDependenceNone() final { return this; }
const DependenceNone* AsDependenceNone() const final { return this; }
};
class DependenceEmpty : public Constraint {
public:
DependenceEmpty() : Constraint(nullptr) {}
ConstraintType GetType() const final { return Empty; }
DependenceEmpty* AsDependenceEmpty() final { return this; }
const DependenceEmpty* AsDependenceEmpty() const final { return this; }
};
// Provides dependence information between a store instruction and a load
// instruction inside the same loop in a loop nest.
//
// The analysis can only check dependence between stores and loads with regard
// to the loop nest it is created with.
//
// The analysis can output debugging information to a stream. The output
// describes the control flow of the analysis and what information it can deduce
// at each step.
// SetDebugStream and ClearDebugStream are provided for this functionality.
//
// The dependency algorithm is based on the 1990 Paper
// Practical Dependence Testing
// Gina Goff, Ken Kennedy, Chau-Wen Tseng
//
// The algorithm first identifies subscript pairs between the load and store.
// Each pair is tested until all have been tested or independence is found.
// The number of induction variables in a pair determines which test to perform
// on it;
// Zero Index Variable (ZIV) is used when no induction variables are present
// in the pair.
// Single Index Variable (SIV) is used when only one induction variable is
// present, but may occur multiple times in the pair.
// Multiple Index Variable (MIV) is used when more than one induction variable
// is present in the pair.
class LoopDependenceAnalysis {
public:
LoopDependenceAnalysis(IRContext* context, std::vector<const Loop*> loops)
: context_(context),
loops_(loops),
scalar_evolution_(context),
debug_stream_(nullptr),
constraints_{} {}
// Finds the dependence between |source| and |destination|.
// |source| should be an OpLoad.
// |destination| should be an OpStore.
// Any direction and distance information found will be stored in
// |distance_vector|.
// Returns true if independence is found, false otherwise.
bool GetDependence(const Instruction* source, const Instruction* destination,
DistanceVector* distance_vector);
// Returns true if |subscript_pair| represents a Zero Index Variable pair
// (ZIV)
bool IsZIV(const std::pair<SENode*, SENode*>& subscript_pair);
// Returns true if |subscript_pair| represents a Single Index Variable
// (SIV) pair
bool IsSIV(const std::pair<SENode*, SENode*>& subscript_pair);
// Returns true if |subscript_pair| represents a Multiple Index Variable
// (MIV) pair
bool IsMIV(const std::pair<SENode*, SENode*>& subscript_pair);
// Finds the lower bound of |loop| as an SENode* and returns the result.
// The lower bound is the starting value of the loops induction variable
SENode* GetLowerBound(const Loop* loop);
// Finds the upper bound of |loop| as an SENode* and returns the result.
// The upper bound is the last value before the loop exit condition is met.
SENode* GetUpperBound(const Loop* loop);
// Returns true if |value| is between |bound_one| and |bound_two| (inclusive).
bool IsWithinBounds(int64_t value, int64_t bound_one, int64_t bound_two);
// Finds the bounds of |loop| as upper_bound - lower_bound and returns the
// resulting SENode.
// If the operations can not be completed a nullptr is returned.
SENode* GetTripCount(const Loop* loop);
// Returns the SENode* produced by building an SENode from the result of
// calling GetInductionInitValue on |loop|.
// If the operation can not be completed a nullptr is returned.
SENode* GetFirstTripInductionNode(const Loop* loop);
// Returns the SENode* produced by building an SENode from the result of
// GetFirstTripInductionNode + (GetTripCount - 1) * induction_coefficient.
// If the operation can not be completed a nullptr is returned.
SENode* GetFinalTripInductionNode(const Loop* loop,
SENode* induction_coefficient);
// Returns all the distinct loops that appear in |nodes|.
std::set<const Loop*> CollectLoops(
const std::vector<SERecurrentNode*>& nodes);
// Returns all the distinct loops that appear in |source| and |destination|.
std::set<const Loop*> CollectLoops(SENode* source, SENode* destination);
// Returns true if |distance| is provably outside the loop bounds.
// |coefficient| must be an SENode representing the coefficient of the
// induction variable of |loop|.
// This method is able to handle some symbolic cases which IsWithinBounds
// can't handle.
bool IsProvablyOutsideOfLoopBounds(const Loop* loop, SENode* distance,
SENode* coefficient);
// Sets the ostream for debug information for the analysis.
void SetDebugStream(std::ostream& debug_stream) {
debug_stream_ = &debug_stream;
}
// Clears the stored ostream to stop debug information printing.
void ClearDebugStream() { debug_stream_ = nullptr; }
// Returns the ScalarEvolutionAnalysis used by this analysis.
ScalarEvolutionAnalysis* GetScalarEvolution() { return &scalar_evolution_; }
// Creates a new constraint of type |T| and returns the pointer to it.
template <typename T, typename... Args>
Constraint* make_constraint(Args&&... args) {
constraints_.push_back(
std::unique_ptr<Constraint>(new T(std::forward<Args>(args)...)));
return constraints_.back().get();
}
// Subscript partitioning as described in Figure 1 of 'Practical Dependence
// Testing' by Gina Goff, Ken Kennedy, and Chau-Wen Tseng from PLDI '91.
// Partitions the subscripts into independent subscripts and minimally coupled
// sets of subscripts.
// Returns the partitioning of subscript pairs. Sets of size 1 indicates an
// independent subscript-pair and others indicate coupled sets.
using PartitionedSubscripts =
std::vector<std::set<std::pair<Instruction*, Instruction*>>>;
PartitionedSubscripts PartitionSubscripts(
const std::vector<Instruction*>& source_subscripts,
const std::vector<Instruction*>& destination_subscripts);
// Returns the Loop* matching the loop for |subscript_pair|.
// |subscript_pair| must be an SIV pair.
const Loop* GetLoopForSubscriptPair(
const std::pair<SENode*, SENode*>& subscript_pair);
// Returns the DistanceEntry matching the loop for |subscript_pair|.
// |subscript_pair| must be an SIV pair.
DistanceEntry* GetDistanceEntryForSubscriptPair(
const std::pair<SENode*, SENode*>& subscript_pair,
DistanceVector* distance_vector);
// Returns the DistanceEntry matching |loop|.
DistanceEntry* GetDistanceEntryForLoop(const Loop* loop,
DistanceVector* distance_vector);
// Returns a vector of Instruction* which form the subscripts of the array
// access defined by the access chain |instruction|.
std::vector<Instruction*> GetSubscripts(const Instruction* instruction);
// Delta test as described in Figure 3 of 'Practical Dependence
// Testing' by Gina Goff, Ken Kennedy, and Chau-Wen Tseng from PLDI '91.
bool DeltaTest(
const std::vector<std::pair<SENode*, SENode*>>& coupled_subscripts,
DistanceVector* dv_entry);
// Constraint propagation as described in Figure 5 of 'Practical Dependence
// Testing' by Gina Goff, Ken Kennedy, and Chau-Wen Tseng from PLDI '91.
std::pair<SENode*, SENode*> PropagateConstraints(
const std::pair<SENode*, SENode*>& subscript_pair,
const std::vector<Constraint*>& constraints);
// Constraint intersection as described in Figure 4 of 'Practical Dependence
// Testing' by Gina Goff, Ken Kennedy, and Chau-Wen Tseng from PLDI '91.
Constraint* IntersectConstraints(Constraint* constraint_0,
Constraint* constraint_1,
const SENode* lower_bound,
const SENode* upper_bound);
// Returns true if each loop in |loops| is in a form supported by this
// analysis.
// A loop is supported if it has a single induction variable and that
// induction variable has a step of +1 or -1 per loop iteration.
bool CheckSupportedLoops(std::vector<const Loop*> loops);
// Returns true if |loop| is in a form supported by this analysis.
// A loop is supported if it has a single induction variable and that
// induction variable has a step of +1 or -1 per loop iteration.
bool IsSupportedLoop(const Loop* loop);
private:
IRContext* context_;
// The loop nest we are analysing the dependence of.
std::vector<const Loop*> loops_;
// The ScalarEvolutionAnalysis used by this analysis to store and perform much
// of its logic.
ScalarEvolutionAnalysis scalar_evolution_;
// The ostream debug information for the analysis to print to.
std::ostream* debug_stream_;
// Stores all the constraints created by the analysis.
std::list<std::unique_ptr<Constraint>> constraints_;
// Returns true if independence can be proven and false if it can't be proven.
bool ZIVTest(const std::pair<SENode*, SENode*>& subscript_pair);
// Analyzes the subscript pair to find an applicable SIV test.
// Returns true if independence can be proven and false if it can't be proven.
bool SIVTest(const std::pair<SENode*, SENode*>& subscript_pair,
DistanceVector* distance_vector);
// Takes the form a*i + c1, a*i + c2
// When c1 and c2 are loop invariant and a is constant
// distance = (c1 - c2)/a
// < if distance > 0
// direction = = if distance = 0
// > if distance < 0
// Returns true if independence is proven and false if it can't be proven.
bool StrongSIVTest(SENode* source, SENode* destination, SENode* coeff,
DistanceEntry* distance_entry);
// Takes for form a*i + c1, a*i + c2
// where c1 and c2 are loop invariant and a is constant.
// c1 and/or c2 contain one or more SEValueUnknown nodes.
bool SymbolicStrongSIVTest(SENode* source, SENode* destination,
SENode* coefficient,
DistanceEntry* distance_entry);
// Takes the form a1*i + c1, a2*i + c2
// where a1 = 0
// distance = (c1 - c2) / a2
// Returns true if independence is proven and false if it can't be proven.
bool WeakZeroSourceSIVTest(SENode* source, SERecurrentNode* destination,
SENode* coefficient,
DistanceEntry* distance_entry);
// Takes the form a1*i + c1, a2*i + c2
// where a2 = 0
// distance = (c2 - c1) / a1
// Returns true if independence is proven and false if it can't be proven.
bool WeakZeroDestinationSIVTest(SERecurrentNode* source, SENode* destination,
SENode* coefficient,
DistanceEntry* distance_entry);
// Takes the form a1*i + c1, a2*i + c2
// where a1 = -a2
// distance = (c2 - c1) / 2*a1
// Returns true if independence is proven and false if it can't be proven.
bool WeakCrossingSIVTest(SENode* source, SENode* destination,
SENode* coefficient, DistanceEntry* distance_entry);
// Uses the def_use_mgr to get the instruction referenced by
// SingleWordInOperand(|id|) when called on |instruction|.
Instruction* GetOperandDefinition(const Instruction* instruction, int id);
// Perform the GCD test if both, the source and the destination nodes, are in
// the form a0*i0 + a1*i1 + ... an*in + c.
bool GCDMIVTest(const std::pair<SENode*, SENode*>& subscript_pair);
// Finds the number of induction variables in |node|.
// Returns -1 on failure.
int64_t CountInductionVariables(SENode* node);
// Finds the number of induction variables shared between |source| and
// |destination|.
// Returns -1 on failure.
int64_t CountInductionVariables(SENode* source, SENode* destination);
// Takes the offset from the induction variable and subtracts the lower bound
// from it to get the constant term added to the induction.
// Returns the resuting constant term, or nullptr if it could not be produced.
SENode* GetConstantTerm(const Loop* loop, SERecurrentNode* induction);
// Marks all the distance entries in |distance_vector| that were relate to
// loops in |loops_| but were not used in any subscripts as irrelevant to the
// to the dependence test.
void MarkUnsusedDistanceEntriesAsIrrelevant(const Instruction* source,
const Instruction* destination,
DistanceVector* distance_vector);
// Converts |value| to a std::string and returns the result.
// This is required because Android does not compile std::to_string.
template <typename valueT>
std::string ToString(valueT value) {
std::ostringstream string_stream;
string_stream << value;
return string_stream.str();
}
// Prints |debug_msg| and "\n" to the ostream pointed to by |debug_stream_|.
// Won't print anything if |debug_stream_| is nullptr.
void PrintDebug(std::string debug_msg);
};
} // namespace opt
} // namespace spvtools
#endif // SOURCE_OPT_LOOP_DEPENDENCE_H_