591 lines
13 KiB
C++
591 lines
13 KiB
C++
// OpenSTA, Static Timing Analyzer
|
|
// Copyright (c) 2024, Parallax Software, Inc.
|
|
//
|
|
// This program is free software: you can redistribute it and/or modify
|
|
// it under the terms of the GNU General Public License as published by
|
|
// the Free Software Foundation, either version 3 of the License, or
|
|
// (at your option) any later version.
|
|
//
|
|
// This program is distributed in the hope that it will be useful,
|
|
// but WITHOUT ANY WARRANTY; without even the implied warranty of
|
|
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
|
// GNU General Public License for more details.
|
|
//
|
|
// You should have received a copy of the GNU General Public License
|
|
// along with this program. If not, see <https://www.gnu.org/licenses/>.
|
|
|
|
#include "PathVertex.hh"
|
|
|
|
#include <cmath>
|
|
|
|
#include "Fuzzy.hh"
|
|
#include "Graph.hh"
|
|
#include "ExceptionPath.hh"
|
|
#include "Sdc.hh"
|
|
#include "GraphDelayCalc.hh"
|
|
#include "Corner.hh"
|
|
#include "Tag.hh"
|
|
#include "TagGroup.hh"
|
|
#include "PathAnalysisPt.hh"
|
|
#include "PathRef.hh"
|
|
#include "PathVertexRep.hh"
|
|
#include "Search.hh"
|
|
|
|
namespace sta {
|
|
|
|
PathVertex::PathVertex() :
|
|
vertex_(nullptr),
|
|
tag_(nullptr),
|
|
arrival_index_(0)
|
|
{
|
|
}
|
|
|
|
PathVertex::PathVertex(const PathVertex &path) :
|
|
vertex_(path.vertex_),
|
|
tag_(path.tag_),
|
|
arrival_index_(path.arrival_index_)
|
|
{
|
|
}
|
|
|
|
PathVertex::PathVertex(const PathVertex *path) :
|
|
vertex_(nullptr),
|
|
tag_(nullptr),
|
|
arrival_index_(0)
|
|
{
|
|
if (path) {
|
|
vertex_ = path->vertex_;
|
|
tag_ = path->tag_;
|
|
arrival_index_ = path->arrival_index_;
|
|
}
|
|
}
|
|
|
|
PathVertex::PathVertex(Vertex *vertex,
|
|
Tag *tag,
|
|
const StaState *sta)
|
|
{
|
|
init(vertex, tag, sta);
|
|
}
|
|
|
|
PathVertex::PathVertex(Vertex *vertex,
|
|
Tag *tag,
|
|
int arrival_index) :
|
|
vertex_(vertex),
|
|
tag_(tag),
|
|
arrival_index_(arrival_index)
|
|
{
|
|
}
|
|
|
|
PathVertex::PathVertex(const PathVertexRep *path,
|
|
const StaState *sta)
|
|
{
|
|
if (path)
|
|
init(path->vertex(sta), path->tag(sta), sta);
|
|
else
|
|
init();
|
|
}
|
|
|
|
PathVertex::PathVertex(const PathVertexRep &path,
|
|
const StaState *sta)
|
|
{
|
|
if (path.isNull())
|
|
init();
|
|
else
|
|
init(path.vertex(sta), path.tag(sta), sta);
|
|
}
|
|
|
|
void
|
|
PathVertex::init()
|
|
{
|
|
vertex_ = nullptr;
|
|
tag_ = nullptr;
|
|
arrival_index_ = 0;
|
|
}
|
|
|
|
void
|
|
PathVertex::init(Vertex *vertex,
|
|
Tag *tag,
|
|
const StaState *sta)
|
|
{
|
|
vertex_ = nullptr;
|
|
tag_ = nullptr;
|
|
arrival_index_ = 0;
|
|
const Search *search = sta->search();
|
|
TagGroup *tag_group = search->tagGroup(vertex);
|
|
if (tag_group) {
|
|
bool arrival_exists;
|
|
tag_group->arrivalIndex(tag, arrival_index_, arrival_exists);
|
|
if (arrival_exists) {
|
|
vertex_ = vertex;
|
|
tag_ = tag;
|
|
}
|
|
}
|
|
}
|
|
|
|
void
|
|
PathVertex::init(Vertex *vertex,
|
|
Tag *tag,
|
|
int arrival_index)
|
|
{
|
|
vertex_ = vertex;
|
|
tag_ = tag;
|
|
arrival_index_ = arrival_index;
|
|
}
|
|
|
|
void
|
|
PathVertex::init(const PathVertexRep *path,
|
|
const StaState *sta)
|
|
{
|
|
if (path)
|
|
init(path->vertex(sta), path->tag(sta), sta);
|
|
else
|
|
init();
|
|
}
|
|
|
|
void
|
|
PathVertex::init(const PathVertexRep &path,
|
|
const StaState *sta)
|
|
{
|
|
if (!path.isNull())
|
|
init(path.vertex(sta), path.tag(sta), sta);
|
|
else
|
|
init();
|
|
}
|
|
|
|
void
|
|
PathVertex::operator=(const PathVertex &path)
|
|
{
|
|
vertex_ = path.vertex_;
|
|
tag_ = path.tag_;
|
|
arrival_index_ = path.arrival_index_;
|
|
}
|
|
|
|
bool
|
|
PathVertex::isNull() const
|
|
{
|
|
return tag_ == nullptr;
|
|
}
|
|
|
|
void
|
|
PathVertex::setRef(PathRef *ref) const
|
|
{
|
|
ref->init(vertex_, tag_, arrival_index_);
|
|
}
|
|
|
|
VertexId
|
|
PathVertex::vertexId(const StaState *sta) const
|
|
{
|
|
const Graph *graph = sta->graph();
|
|
return graph->id(vertex_);
|
|
}
|
|
|
|
TagIndex
|
|
PathVertex::tagIndex(const StaState *) const
|
|
{
|
|
return tag_->index();
|
|
}
|
|
|
|
const RiseFall *
|
|
PathVertex::transition(const StaState *) const
|
|
{
|
|
return tag_->transition();
|
|
}
|
|
|
|
int
|
|
PathVertex::rfIndex(const StaState *) const
|
|
{
|
|
return tag_->rfIndex();
|
|
}
|
|
|
|
PathAnalysisPt *
|
|
PathVertex::pathAnalysisPt(const StaState *sta) const
|
|
{
|
|
return tag_->pathAnalysisPt(sta);
|
|
}
|
|
|
|
PathAPIndex
|
|
PathVertex::pathAnalysisPtIndex(const StaState *) const
|
|
{
|
|
return tag_->pathAPIndex();
|
|
}
|
|
|
|
void
|
|
PathVertex::arrivalIndex(int &arrival_index,
|
|
bool &arrival_exists) const
|
|
{
|
|
if (tag_) {
|
|
arrival_index = arrival_index_;
|
|
arrival_exists = true;
|
|
}
|
|
else
|
|
arrival_exists = false;
|
|
}
|
|
|
|
void
|
|
PathVertex::setArrivalIndex(int arrival_index)
|
|
{
|
|
arrival_index_ = arrival_index;
|
|
}
|
|
|
|
Arrival
|
|
PathVertex::arrival(const StaState *sta) const
|
|
{
|
|
Arrival *arrivals = sta->graph()->arrivals(vertex_);
|
|
if (arrivals)
|
|
return arrivals[arrival_index_];
|
|
else {
|
|
sta->report()->error(1400, "missing arrivals.");
|
|
return 0.0;
|
|
}
|
|
}
|
|
|
|
void
|
|
PathVertex::setArrival(Arrival arrival,
|
|
const StaState *sta)
|
|
{
|
|
if (tag_) {
|
|
Arrival *arrivals = sta->graph()->arrivals(vertex_);
|
|
if (arrivals)
|
|
arrivals[arrival_index_] = arrival;
|
|
else
|
|
sta->report()->error(1401, "missing arrivals.");
|
|
}
|
|
}
|
|
|
|
const Required &
|
|
PathVertex::required(const StaState *sta) const
|
|
{
|
|
if (tag_) {
|
|
Required *requireds = sta->graph()->requireds(vertex_);
|
|
if (requireds)
|
|
return requireds[arrival_index_];
|
|
}
|
|
return delayInitValue(minMax(sta)->opposite());
|
|
}
|
|
|
|
void
|
|
PathVertex::setRequired(const Required &required,
|
|
const StaState *sta)
|
|
{
|
|
Graph *graph = sta->graph();
|
|
Required *requireds = graph->requireds(vertex_);
|
|
if (requireds == nullptr) {
|
|
const Search *search = sta->search();
|
|
TagGroup *tag_group = search->tagGroup(vertex_);
|
|
if (tag_group) {
|
|
int arrival_count = tag_group->arrivalCount();
|
|
requireds = graph->makeRequireds(vertex_, arrival_count);
|
|
}
|
|
else
|
|
sta->report()->error(1402, "missing requireds.");
|
|
}
|
|
requireds[arrival_index_] = required;
|
|
}
|
|
|
|
bool
|
|
PathVertex::equal(const PathVertex *path1,
|
|
const PathVertex *path2)
|
|
{
|
|
return path1->vertex_ == path2->vertex_
|
|
&& path1->tag_ == path2->tag_;
|
|
}
|
|
|
|
////////////////////////////////////////////////////////////////
|
|
|
|
// EvalPred but search to clk source pin.
|
|
class PrevPred2 : public SearchPred0
|
|
{
|
|
public:
|
|
explicit PrevPred2(const StaState *sta);
|
|
virtual bool searchThru(Edge *edge);
|
|
};
|
|
|
|
PrevPred2::PrevPred2(const StaState *sta) :
|
|
SearchPred0(const_cast<StaState*>(sta))
|
|
{
|
|
}
|
|
|
|
bool
|
|
PrevPred2::searchThru(Edge *edge)
|
|
{
|
|
const Sdc *sdc = sta_->sdc();
|
|
TimingRole *role = edge->role();
|
|
return SearchPred0::searchThru(edge)
|
|
&& (sdc->dynamicLoopBreaking()
|
|
|| !edge->isDisabledLoop())
|
|
&& !role->isTimingCheck();
|
|
}
|
|
|
|
class PrevPathVisitor : public PathVisitor
|
|
{
|
|
public:
|
|
PrevPathVisitor(const Path *path,
|
|
SearchPred *pred,
|
|
const StaState *sta);
|
|
virtual VertexVisitor *copy() const;
|
|
virtual void visit(Vertex *) {}
|
|
virtual bool visitFromToPath(const Pin *from_pin,
|
|
Vertex *from_vertex,
|
|
const RiseFall *from_rf,
|
|
Tag *from_tag,
|
|
PathVertex *from_path,
|
|
const Arrival &from_arrival,
|
|
Edge *edge,
|
|
TimingArc *arc,
|
|
ArcDelay arc_delay,
|
|
Vertex *to_vertex,
|
|
const RiseFall *to_rf,
|
|
Tag *to_tag,
|
|
Arrival &to_arrival,
|
|
const MinMax *min_max,
|
|
const PathAnalysisPt *path_ap);
|
|
PathVertex &prevPath() { return prev_path_; }
|
|
TimingArc *prevArc() const { return prev_arc_; }
|
|
|
|
protected:
|
|
Tag *unfilteredTag(const Tag *tag) const;
|
|
|
|
const Path *path_;
|
|
Arrival path_arrival_;
|
|
Tag *path_tag_;
|
|
int path_rf_index_;
|
|
PathAPIndex path_ap_index_;
|
|
PathVertex prev_path_;
|
|
TimingArc *prev_arc_;
|
|
float dcalc_tol_;
|
|
};
|
|
|
|
PrevPathVisitor::PrevPathVisitor(const Path *path,
|
|
SearchPred *pred,
|
|
const StaState *sta) :
|
|
PathVisitor(pred, sta),
|
|
path_(path),
|
|
path_arrival_(path->arrival(sta)),
|
|
path_tag_(path->tag(sta)),
|
|
path_rf_index_(path->rfIndex(sta)),
|
|
path_ap_index_(path->pathAnalysisPtIndex(sta)),
|
|
prev_path_(),
|
|
prev_arc_(nullptr),
|
|
dcalc_tol_(sta->graphDelayCalc()->incrementalDelayTolerance())
|
|
{
|
|
}
|
|
|
|
VertexVisitor *
|
|
PrevPathVisitor::copy() const
|
|
{
|
|
return new PrevPathVisitor(path_, pred_, this);
|
|
}
|
|
|
|
bool
|
|
PrevPathVisitor::visitFromToPath(const Pin *,
|
|
Vertex *,
|
|
const RiseFall *,
|
|
Tag *from_tag,
|
|
PathVertex *from_path,
|
|
const Arrival &,
|
|
Edge *,
|
|
TimingArc *arc,
|
|
ArcDelay,
|
|
Vertex *,
|
|
const RiseFall *to_rf,
|
|
Tag *to_tag,
|
|
Arrival &to_arrival,
|
|
const MinMax *,
|
|
const PathAnalysisPt *path_ap)
|
|
{
|
|
PathAPIndex path_ap_index = path_ap->index();
|
|
if (to_rf->index() == path_rf_index_
|
|
&& path_ap_index == path_ap_index_
|
|
&& delayEqual(to_arrival, path_arrival_)
|
|
&& (tagMatch(to_tag, path_tag_, this)
|
|
// If the filter exception became active searching from
|
|
// from_path to to_path the tag includes the filter, but
|
|
// to_vertex still has paths from previous searches that do
|
|
// not have the filter.
|
|
|| (!from_tag->isFilter()
|
|
&& to_tag->isFilter()
|
|
&& tagMatch(unfilteredTag(to_tag), path_tag_, this)))) {
|
|
int arrival_index;
|
|
bool arrival_exists;
|
|
from_path->arrivalIndex(arrival_index, arrival_exists);
|
|
if (arrival_exists) {
|
|
prev_path_ = from_path;
|
|
prev_arc_ = arc;
|
|
// Stop looking for the previous path/arc.
|
|
return false;
|
|
}
|
|
}
|
|
return true;
|
|
}
|
|
|
|
Tag *
|
|
PrevPathVisitor::unfilteredTag(const Tag *tag) const
|
|
{
|
|
ExceptionStateSet *unfiltered_states = nullptr;
|
|
const ExceptionStateSet *states = tag->states();
|
|
ExceptionStateSet::ConstIterator state_iter(states);
|
|
while (state_iter.hasNext()) {
|
|
ExceptionState *state = state_iter.next();
|
|
ExceptionPath *except = state->exception();
|
|
if (!except->isFilter()) {
|
|
if (unfiltered_states == nullptr)
|
|
unfiltered_states = new ExceptionStateSet();
|
|
unfiltered_states->insert(state);
|
|
}
|
|
}
|
|
return search_->findTag(tag->transition(),
|
|
corners_->findPathAnalysisPt(tag->pathAPIndex()),
|
|
tag->clkInfo(),
|
|
tag->isClock(),
|
|
tag->inputDelay(),
|
|
tag->isSegmentStart(),
|
|
unfiltered_states, true);
|
|
}
|
|
|
|
////////////////////////////////////////////////////////////////
|
|
|
|
void
|
|
PathVertex::prevPath(const StaState *sta,
|
|
// Return values.
|
|
PathVertex &prev_path,
|
|
TimingArc *&prev_arc) const
|
|
{
|
|
PrevPred2 pred(sta);
|
|
PrevPathVisitor visitor(this, &pred, sta);
|
|
visitor.visitFaninPaths(vertex(sta));
|
|
prev_path = visitor.prevPath();
|
|
prev_arc = visitor.prevArc();
|
|
}
|
|
|
|
void
|
|
PathVertex::prevPath(const StaState *sta,
|
|
// Return values.
|
|
PathVertex &prev_path) const
|
|
{
|
|
PrevPred2 pred(sta);
|
|
PrevPathVisitor visitor(this, &pred, sta);
|
|
visitor.visitFaninPaths(vertex(sta));
|
|
prev_path = visitor.prevPath();
|
|
}
|
|
|
|
void
|
|
PathVertex::prevPath(const StaState *sta,
|
|
// Return values.
|
|
PathRef &prev_path,
|
|
TimingArc *&prev_arc) const
|
|
{
|
|
PathVertex prev;
|
|
prevPath(sta, prev, prev_arc);
|
|
prev.setRef(prev_path);
|
|
}
|
|
|
|
////////////////////////////////////////////////////////////////
|
|
|
|
VertexPathIterator::VertexPathIterator(Vertex *vertex,
|
|
const StaState *sta) :
|
|
search_(sta->search()),
|
|
vertex_(vertex),
|
|
rf_(nullptr),
|
|
path_ap_(nullptr),
|
|
min_max_(nullptr)
|
|
{
|
|
TagGroup *tag_group = search_->tagGroup(vertex);
|
|
if (tag_group) {
|
|
arrival_iter_.init(tag_group->arrivalMap());
|
|
findNext();
|
|
}
|
|
}
|
|
|
|
// Iterate over vertex paths with the same transition and
|
|
// analysis pt but different but different tags.
|
|
VertexPathIterator::VertexPathIterator(Vertex *vertex,
|
|
const RiseFall *rf,
|
|
const PathAnalysisPt *path_ap,
|
|
const StaState *sta) :
|
|
search_(sta->search()),
|
|
vertex_(vertex),
|
|
rf_(rf),
|
|
path_ap_(path_ap),
|
|
min_max_(nullptr)
|
|
{
|
|
TagGroup *tag_group = search_->tagGroup(vertex);
|
|
if (tag_group) {
|
|
arrival_iter_.init(tag_group->arrivalMap());
|
|
findNext();
|
|
}
|
|
}
|
|
|
|
VertexPathIterator::VertexPathIterator(Vertex *vertex,
|
|
const RiseFall *rf,
|
|
const MinMax *min_max,
|
|
const StaState *sta) :
|
|
search_(sta->search()),
|
|
vertex_(vertex),
|
|
rf_(rf),
|
|
path_ap_(nullptr),
|
|
min_max_(min_max)
|
|
{
|
|
TagGroup *tag_group = search_->tagGroup(vertex);
|
|
if (tag_group) {
|
|
arrival_iter_.init(tag_group->arrivalMap());
|
|
findNext();
|
|
}
|
|
}
|
|
|
|
VertexPathIterator::VertexPathIterator(Vertex *vertex,
|
|
const RiseFall *rf,
|
|
const PathAnalysisPt *path_ap,
|
|
const MinMax *min_max,
|
|
const StaState *sta) :
|
|
search_(sta->search()),
|
|
vertex_(vertex),
|
|
rf_(rf),
|
|
path_ap_(path_ap),
|
|
min_max_(min_max)
|
|
{
|
|
TagGroup *tag_group = search_->tagGroup(vertex);
|
|
if (tag_group) {
|
|
arrival_iter_.init(tag_group->arrivalMap());
|
|
findNext();
|
|
}
|
|
}
|
|
|
|
VertexPathIterator::~VertexPathIterator()
|
|
{
|
|
}
|
|
|
|
bool
|
|
VertexPathIterator::hasNext()
|
|
{
|
|
return !next_.isNull();
|
|
}
|
|
|
|
void
|
|
VertexPathIterator::findNext()
|
|
{
|
|
while (arrival_iter_.hasNext()) {
|
|
Tag *tag;
|
|
int arrival_index;
|
|
arrival_iter_.next(tag, arrival_index);
|
|
if ((rf_ == nullptr
|
|
|| tag->rfIndex() == rf_->index())
|
|
&& (path_ap_ == nullptr
|
|
|| tag->pathAPIndex() == path_ap_->index())
|
|
&& (min_max_ == nullptr
|
|
|| tag->pathAnalysisPt(search_)->pathMinMax() == min_max_)) {
|
|
next_.init(vertex_, tag, arrival_index);
|
|
return;
|
|
}
|
|
}
|
|
next_.init();
|
|
}
|
|
|
|
PathVertex *
|
|
VertexPathIterator::next()
|
|
{
|
|
path_ = next_;
|
|
findNext();
|
|
return &path_;
|
|
}
|
|
|
|
} // namespace
|