8#ifndef FRONTENDS_P4_DEF_USE_H_
9#define FRONTENDS_P4_DEF_USE_H_
11#include "absl/container/flat_hash_set.h"
12#include "absl/container/inlined_vector.h"
13#include "absl/container/node_hash_set.h"
14#include "frontends/common/resolveReferences/referenceMap.h"
16#include "lib/alloc_trace.h"
17#include "lib/flat_map.h"
19#include "lib/hvec_map.h"
20#include "lib/ordered_set.h"
35 mutable std::size_t computedHash = 0;
36 bool operator==(
const loc_t &a)
const {
37 if (node != a.node)
return false;
38 if (parent == a.parent)
return true;
39 if (!parent || !a.parent)
return false;
40 return *parent == *a.parent;
42 std::size_t hash()
const;
49#ifdef DEBUG_LOCATION_IDS
50 static unsigned crtid;
55 virtual ~StorageLocation() {}
58 StorageLocation(
const IR::Type *type,
cstring name)
60#ifdef DEBUG_LOCATION_IDS
67 void dbprint(std::ostream &out)
const override {
68#ifdef DEBUG_LOCATION_IDS
69 out <<
id <<
" " << name;
71 out << dbp(type) <<
" " << name;
74 cstring toString()
const {
return name; }
75 virtual const char *locClass()
const = 0;
79 virtual void addValidBits(
LocationSet *result)
const = 0;
85 virtual void addLastIndexField(
LocationSet *result)
const = 0;
87 DECLARE_TYPEINFO(StorageLocation);
92class BaseLocation :
public StorageLocation {
94 BaseLocation(
const IR::Type *type,
cstring name) : StorageLocation(type, name) {
95 if (
auto tt = type->to<IR::Type_Tuple>())
96 BUG_CHECK(tt->getSize() == 0,
"%1%: tuples with fields are not base locations", tt);
97 else if (
auto ts = type->to<IR::Type_StructLike>())
98 BUG_CHECK(ts->fields.size() == 0,
"%1%: structs with fields are not base locations",
101 BUG_CHECK(type->is<IR::Type_Bits>() || type->is<IR::Type_Enum>() ||
102 type->is<IR::Type_Boolean>() || type->is<IR::Type_Var>() ||
103 type->is<IR::Type_Error>() || type->is<IR::Type_Varbits>() ||
104 type->is<IR::Type_Newtype>() || type->is<IR::Type_SerEnum>() ||
105 type->is<IR::Type_List>(),
106 "%1%: unexpected type", type);
109 void addLastIndexField(
LocationSet *)
const override {}
111 const char *locClass()
const override {
return "Base"; }
113 DECLARE_TYPEINFO(BaseLocation, StorageLocation);
117class WithFieldsLocation :
public StorageLocation {
119 absl::InlinedVector<std::pair<cstring, const StorageLocation *>, 4>>
122 void createField(
cstring name, StorageLocation *field) {
123 fieldLocations.emplace(name, field);
126 void replaceField(
cstring field, StorageLocation *replacement) {
127 fieldLocations[field] = replacement;
130 friend class StorageFactory;
133 WithFieldsLocation(
const IR::Type *type,
cstring name) : StorageLocation(type, name) {}
138 auto fields()
const {
return Values(fieldLocations); }
139 const char *locClass()
const override {
return "WithFields"; }
140 void dbprint(std::ostream &out)
const override {
141 out <<
"<" << locClass() <<
">{";
142 const char *sep =
"";
143 for (
auto f : fieldLocations) {
144 out << sep << *f.second;
150 DECLARE_TYPEINFO(WithFieldsLocation, StorageLocation);
154class StructLocation :
public WithFieldsLocation {
156 StructLocation(
const IR::Type *type,
cstring name) : WithFieldsLocation(type, name) {
157 BUG_CHECK(type->is<IR::Type_StructLike>(),
"%1%: unexpected type", type);
159 friend class StorageFactory;
162 void addValidBits(
LocationSet *result)
const override;
163 void addLastIndexField(
LocationSet *result)
const override;
164 bool isHeader()
const {
return type->is<IR::Type_Header>(); }
165 bool isHeaderUnion()
const {
return type->is<IR::Type_HeaderUnion>(); }
166 bool isStruct()
const {
return type->is<IR::Type_Struct>(); }
167 const char *locClass()
const override {
return "Struct"; }
169 DECLARE_TYPEINFO(StructLocation, WithFieldsLocation);
173class IndexedLocation :
public StorageLocation {
174 absl::InlinedVector<const StorageLocation *, 8> elements;
177 void createElement(
unsigned index, StorageLocation *element) {
178 elements[index] = element;
182 IndexedLocation(
const IR::Type *type,
cstring name) : StorageLocation(type, name) {
184 const auto *it = type->to<IR::Type_Indexed>();
185 BUG_CHECK(it !=
nullptr,
"%1%: unexpected type", type);
186 elements.resize(it->getSize());
189 friend class StorageFactory;
192 void addElement(
unsigned index,
LocationSet *result)
const;
193 auto begin()
const {
return elements.cbegin(); }
194 auto end()
const {
return elements.cend(); }
195 const char *locClass()
const override {
return "Indexed"; }
196 void dbprint(std::ostream &out)
const override {
197 out <<
"<" << locClass() <<
">[";
198 const char *sep =
"";
199 for (
unsigned i = 0; i < elements.size(); i++) {
200 out << sep << *elements.at(i);
205 size_t getSize()
const {
return elements.size(); }
208 DECLARE_TYPEINFO(IndexedLocation, StorageLocation);
212class TupleLocation :
public IndexedLocation {
214 TupleLocation(
const IR::Type *type,
cstring name) : IndexedLocation(type, name) {}
215 friend class StorageFactory;
219 void addLastIndexField(
LocationSet *)
const override {}
220 const char *locClass()
const override {
return "Tuple"; }
222 DECLARE_TYPEINFO(TupleLocation, IndexedLocation);
225class ArrayLocation :
public IndexedLocation {
228 void setLastIndexField(
const StorageLocation *location) { lastIndexField = location; }
231 ArrayLocation(
const IR::Type *type,
cstring name) : IndexedLocation(type, name) {}
232 friend class StorageFactory;
235 const StorageLocation *getLastIndexField()
const {
return lastIndexField; }
237 void addValidBits(
LocationSet *result)
const override;
239 void addLastIndexField(
LocationSet *result)
const override;
240 const char *locClass()
const override {
return "Array"; }
242 DECLARE_TYPEINFO(ArrayLocation, IndexedLocation);
247 mutable std::vector<std::unique_ptr<StorageLocation>> storageLocations;
250 T *construct(
const IR::Type *type,
cstring name)
const;
252 static constexpr std::string_view indexFieldName =
"$last_index";
257 static const cstring validFieldName;
264 LocationsStorage locations;
266 class canonical_iterator {
267 absl::InlinedVector<const StorageLocation *, 8> workList;
270 if (workList.empty())
return;
272 const auto *location = workList.back();
278 workList.push_back(f);
290 BUG(
"unexpected location");
294 using iterator_category = std::forward_iterator_tag;
296 using difference_type = ptrdiff_t;
297 using pointer = value_type;
298 using reference = value_type;
300 canonical_iterator() =
default;
302 explicit canonical_iterator(
const LocationsStorage &locations) {
304 workList.push_back(loc);
307 canonical_iterator &operator++() {
312 canonical_iterator operator++(
int) {
317 bool operator==(
const canonical_iterator &i)
const {
return workList == i.workList; }
318 bool operator!=(
const canonical_iterator &i)
const {
return workList != i.workList; }
319 reference operator*()
const {
return workList.back(); }
320 pointer operator->()
const {
return workList.back(); }
324 LocationSet() =
default;
327 CHECK_NULL(location);
328 locations.emplace(location);
330 static const LocationSet *empty;
332 const LocationSet *getField(
cstring field)
const;
333 const LocationSet *getValidField()
const;
334 const LocationSet *getIndex(
unsigned index)
const;
335 const LocationSet *allElements()
const;
336 const LocationSet *getArrayLastIndex()
const;
339 CHECK_NULL(location);
340 locations.emplace(location);
342 const LocationSet *join(
const LocationSet *other)
const;
347 auto begin()
const {
return locations.cbegin(); }
348 auto end()
const {
return locations.cend(); }
349 auto canon_begin()
const {
return canonical_iterator(locations); }
350 auto canon_end()
const {
return canonical_iterator(); }
353 void dbprint(std::ostream &out)
const override {
354 if (locations.empty()) out <<
"LocationSet::empty";
355 for (
auto l : locations) {
361 bool overlaps(
const LocationSet *other)
const;
362 bool operator==(
const LocationSet &other)
const;
363 bool isEmpty()
const {
return locations.empty(); }
382 auto type = typeMap->getType(decl->getNode(),
true);
383 auto loc = factory.create(type, decl->
getName() +
"/" + decl->externalName());
384 if (loc !=
nullptr) storage.emplace(decl, loc);
388 const auto *s = getStorage(decl);
389 if (s !=
nullptr)
return s;
394 auto result = ::P4::get(storage, decl);
397 void dbprint(std::ostream &out)
const override {
398 for (
auto &it : storage) out << it.first <<
": " << it.second << Log::endl;
411 absl::InlinedVector<const IR::Node *, 8> stack;
414 ProgramPoint() =
default;
415 ProgramPoint(
const ProgramPoint &other) : stack(other.stack) {}
416 explicit ProgramPoint(
const IR::Node *node) {
420 ProgramPoint(
const ProgramPoint &context,
const IR::Node *node);
424 ProgramPoint
after() {
return ProgramPoint(*
this,
nullptr); }
426 std::size_t hash()
const;
427 void dbprint(std::ostream &out)
const override {
428 if (isBeforeStart()) {
429 out <<
"<BeforeStart>";
432 for (
auto n : stack) {
433 if (!first) out <<
"//";
440 auto l = stack.back();
442 (l->is<IR::BaseAssignmentStatement>() || l->is<IR::MethodCallStatement>()))
443 out <<
"[[" << l <<
"]]";
446 void assign(
const ProgramPoint &context,
const IR::Node *node);
447 void assign(
const IR::Node *node) { stack.assign({node}); }
448 void clear() { stack.clear(); }
449 const IR::Node *last()
const {
return stack.empty() ? nullptr : stack.back(); }
450 bool isBeforeStart()
const {
return stack.empty(); }
451 auto begin()
const {
return stack.begin(); }
452 auto end()
const {
return stack.end(); }
453 ProgramPoint &operator=(
const ProgramPoint &) =
default;
454 ProgramPoint &operator=(ProgramPoint &&) =
default;
461struct hash<
P4::ProgramPoint> {
462 std::size_t operator()(
const P4::ProgramPoint &s)
const {
return s.hash(); }
466struct hash<
P4::loc_t> {
467 std::size_t operator()(
const P4::loc_t &loc)
const {
return loc.hash(); }
480 size_t operator()(
const P4::loc_t &loc)
const {
return loc.hash(); }
486 typedef absl::flat_hash_set<ProgramPoint, Util::Hash> Points;
488 explicit ProgramPoints(
const Points &points) : points(points) {}
491 ProgramPoints() =
default;
492 explicit ProgramPoints(
ProgramPoint point) { points.emplace(point); }
493 void add(
const ProgramPoints *from);
494 const ProgramPoints *merge(
const ProgramPoints *with)
const;
495 bool operator==(
const ProgramPoints &other)
const;
496 void dbprint(std::ostream &out)
const override {
498 for (
auto p : points) out << p <<
" ";
501 size_t size()
const {
return points.size(); }
502 bool containsBeforeStart()
const {
505 Points::const_iterator begin()
const {
return points.cbegin(); }
506 Points::const_iterator end()
const {
return points.cend(); }
515 bool unreachable =
false;
518 Definitions() =
default;
519 Definitions(
const Definitions &other)
520 : definitions(other.definitions), unreachable(other.unreachable) {}
521 Definitions *joinDefinitions(
const Definitions *other)
const;
527 definitions[loc] = point;
531 Definitions *setUnreachable() {
535 bool isUnreachable()
const {
return unreachable; }
537 return definitions.find(location) != definitions.end();
540 auto r = ::P4::get(definitions, location);
541 BUG_CHECK(r !=
nullptr,
"no definitions found for %1%", location);
545 bool operator==(
const Definitions &other)
const;
546 void dbprint(std::ostream &out)
const override {
548 out <<
" Unreachable" << Log::endl;
550 if (definitions.empty()) out <<
" Empty definitions";
552 for (
auto d : definitions) {
553 if (!first) out << Log::endl;
554 out <<
" " << *d.first <<
"=>" << *d.second;
558 Definitions *cloneDefinitions()
const {
return new Definitions(*
this); }
560 bool empty()
const {
return definitions.empty(); }
561 size_t size()
const {
return definitions.size(); }
576 auto it = atPoint.find(point);
577 if (it == atPoint.end()) {
578 if (emptyIfNotFound) {
580 setDefinitionsAt(point, defs,
false);
583 BUG(
"Unknown point %1% for definitions", &point);
589 auto it = atPoint.find(point);
590 if (it != atPoint.end()) {
591 LOG2(
"Overwriting definitions at " << point <<
": " << it->second <<
" with "
593 BUG_CHECK(
false,
"Overwriting definitions at %1%", point);
596 atPoint[point] = defs;
600 return storageMap.getStorage(decl);
604 return storageMap.getOrAdd(decl);
607 void dbprint(std::ostream &out)
const override {
608 for (
auto e : atPoint) out << e.first <<
" => " << e.second << Log::endl;
625 using CachedLocs = absl::node_hash_set<loc_t, Util::Hash>;
631 allDefinitions(allDefinitions),
636 virtualMethod(
false),
637 cached_locs(
new CachedLocs) {
638 CHECK_NULL(allDefinitions);
641 visitDagOnce =
false;
645 bool preorder(
const IR::Literal *expression)
override;
646 bool preorder(
const IR::AbstractSlice *expression)
override;
647 bool preorder(
const IR::TypeNameExpression *expression)
override;
648 bool preorder(
const IR::PathExpression *expression)
override;
649 bool preorder(
const IR::Member *expression)
override;
650 bool preorder(
const IR::ArrayIndex *expression)
override;
651 bool preorder(
const IR::Operation_Binary *expression)
override;
652 bool preorder(
const IR::Mux *expression)
override;
653 bool preorder(
const IR::SelectExpression *expression)
override;
654 bool preorder(
const IR::ListExpression *expression)
override;
655 bool preorder(
const IR::Operation_Unary *expression)
override;
656 bool preorder(
const IR::MethodCallExpression *expression)
override;
657 bool preorder(
const IR::DefaultExpression *expression)
override;
658 bool preorder(
const IR::Expression *expression)
override;
659 bool preorder(
const IR::InvalidHeader *expression)
override;
660 bool preorder(
const IR::InvalidHeaderUnion *expression)
override;
661 bool preorder(
const IR::P4ListExpression *expression)
override;
662 bool preorder(
const IR::ArrayExpression *expression)
override;
663 bool preorder(
const IR::StructExpression *expression)
override;
665 bool preorder(
const IR::P4Parser *parser)
override;
666 bool preorder(
const IR::P4Control *control)
override;
667 bool preorder(
const IR::P4Action *action)
override;
668 bool preorder(
const IR::P4Table *table)
override;
669 bool preorder(
const IR::Function *function)
override;
670 bool preorder(
const IR::BaseAssignmentStatement *statement)
override;
671 bool preorder(
const IR::ReturnStatement *statement)
override;
672 bool preorder(
const IR::ExitStatement *statement)
override;
673 bool preorder(
const IR::BreakStatement *statement)
override;
674 bool handleJump(
const char *tok,
Definitions *&defs);
675 bool preorder(
const IR::ContinueStatement *statement)
override;
676 bool preorder(
const IR::IfStatement *statement)
override;
677 bool preorder(
const IR::ForStatement *statement)
override;
678 bool preorder(
const IR::ForInStatement *statement)
override;
679 bool preorder(
const IR::BlockStatement *statement)
override;
680 bool preorder(
const IR::SwitchStatement *statement)
override;
681 bool preorder(
const IR::EmptyStatement *statement)
override;
682 bool preorder(
const IR::MethodCallStatement *statement)
override;
684 const LocationSet *writtenLocations(
const IR::Expression *expression) {
685 expression->apply(*
this);
686 return getWrites(expression);
706 static int nest_count;
711 std::shared_ptr<CachedLocs> cached_locs)
712 : refMap(source->refMap),
713 typeMap(source->typeMap),
715 allDefinitions(source->allDefinitions),
723 virtualMethod(false),
724 cached_locs(cached_locs) {
725 visitDagOnce =
false;
729 const loc_t *getLoc(
const Visitor::Context *ctxt);
730 const loc_t *getLoc(
const IR::Node *n,
const Visitor::Context *ctxt);
731 void enterScope(
const IR::ParameterList *parameters,
734 void exitScope(
const IR::ParameterList *parameters,
736 Definitions *getDefinitionsAfter(
const IR::ParserState *state);
737 bool setDefinitions(
Definitions *defs,
const IR::Node *who =
nullptr,
bool overwrite =
false);
740 const LocationSet *getWrites(
const IR::Expression *expression) {
741 const loc_t &exprLoc = *getLoc(expression, getChildContext());
742 auto result = ::P4::get(
writes, exprLoc);
743 BUG_CHECK(result !=
nullptr,
"No location set known for %1%", expression);
748 const LocationSet *getWrites(
const IR::Expression *expression,
const loc_t *parentLoc) {
749 const loc_t &exprLoc = *getLoc(expression, parentLoc);
750 auto result = ::P4::get(
writes, exprLoc);
751 BUG_CHECK(result !=
nullptr,
"No location set known for %1%", expression);
755 void expressionWrites(
const IR::Expression *expression,
const LocationSet *loc) {
756 CHECK_NULL(expression);
758 LOG3(expression << dbp(expression) <<
" writes " << loc);
759 const Context *ctx = getChildContext();
760 BUG_CHECK(ctx->node == expression,
"Expected ctx->node == expression.");
761 const loc_t &exprLoc = *getLoc(ctx);
762 if (
auto it =
writes.find(exprLoc); it !=
writes.end()) {
763 BUG_CHECK(*it->second == *loc || expression->is<IR::Literal>(),
764 "Expression %1% write set already set", expression);
766 writes.emplace(exprLoc, loc);
769 void dbprint(std::ostream &out)
const override {
770 if (
writes.empty()) out <<
"No writes";
771 for (
auto &it :
writes) out << it.first.node <<
" writes " << it.second << Log::endl;
773 profile_t init_apply(
const IR::Node *root)
override {
774 auto rv = Inspector::init_apply(root);
775 LOG1(
"starting ComputWriteSet" << Log::indent);
776 if (nest_count++ == 0 && LOGGING(2)) {
778 nested_trace =
memuse.start();
782 void end_apply()
override {
783 LOG1(
"finished CWS" << Log::unindent);
784 if (--nest_count == 0 && LOGGING(2)) {
785 memuse.stop(nested_trace);
791 std::shared_ptr<CachedLocs> cached_locs;
Definition frontends/p4/def_use.h:564
Definition alloc_trace.h:20
Definition frontends/p4/def_use.h:92
Definition frontends/p4/def_use.h:623
bool lhs
if true we are processing an expression on the lhs of an assignment
Definition frontends/p4/def_use.h:700
AllocTrace memuse
True if we are analyzing a virtual method.
Definition frontends/p4/def_use.h:704
Definitions * breakDefinitions
Definitions after exit statements.
Definition frontends/p4/def_use.h:696
Definitions * returnedDefinitions
Before statement currently processed.
Definition frontends/p4/def_use.h:694
ComputeWriteSet(const ComputeWriteSet *source, ProgramPoint context, Definitions *definitions, std::shared_ptr< CachedLocs > cached_locs)
Definition frontends/p4/def_use.h:710
void visitVirtualMethods(const IR::IndexedVector< IR::Declaration > &locals)
Statements and other control structures.
Definition frontends/p4/def_use.cpp:760
Definitions * exitDefinitions
Definitions after return statements.
Definition frontends/p4/def_use.h:695
Definitions * currentDefinitions
Result computed by this pass.
Definition frontends/p4/def_use.h:693
Definitions * continueDefinitions
Definitions at break statements.
Definition frontends/p4/def_use.h:697
ProgramPoint callingContext
Definitions at continue statements.
Definition frontends/p4/def_use.h:698
hvec_map< loc_t, const LocationSet * > writes
For each program location the location set it writes.
Definition frontends/p4/def_use.h:702
List of definers for each base storage (at a specific program point).
Definition frontends/p4/def_use.h:510
Definitions * writes(ProgramPoint point, const LocationSet &locations) const
Point writes the specified LocationSet.
Definition frontends/p4/def_use.cpp:369
Definition stringify.h:24
The Declaration interface, representing objects with names.
Definition declaration.h:17
virtual ID getName() const =0
Definition indexed_vector.h:31
Interface for locations that support an index operation.
Definition frontends/p4/def_use.h:173
Definition frontends/p4/def_use.h:262
const LocationSet * canonicalize() const
Definition frontends/p4/def_use.cpp:232
Indicates a statement in the program.
Definition frontends/p4/def_use.h:403
static ProgramPoint beforeStart
A point logically before the function/control/action start.
Definition frontends/p4/def_use.h:422
ProgramPoint after()
We use a nullptr to indicate a point after the previous context.
Definition frontends/p4/def_use.h:424
Definition frontends/p4/def_use.h:485
Class used to encode maps from paths to declarations.
Definition referenceMap.h:58
Definition frontends/p4/def_use.h:245
Abstraction for something that is has a left value (variable, parameter)
Definition frontends/p4/def_use.h:48
LocationSet getValidBits() const
Definition frontends/p4/def_use.cpp:154
LocationSet removeHeaders() const
Definition frontends/p4/def_use.cpp:106
LocationSet getLastIndexField() const
Definition frontends/p4/def_use.cpp:160
Maps a declaration to its associated storage.
Definition frontends/p4/def_use.h:367
Definition iterator_range.h:44
Base class for location sets that contain fields.
Definition frontends/p4/def_use.h:117
Definition ordered_set.h:23
TODO: this is not really specific to BMV2, it should reside somewhere else.
Definition applyOptionsPragmas.cpp:13
Definition frontends/p4/def_use.h:32