================ @@ -0,0 +1,48 @@ +//===- EntityIdTable.cpp ----------------------------------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#include "clang/Analysis/Scalable/Model/EntityIdTable.h" +#include <algorithm> +#include <cassert> + +namespace clang { +namespace ssaf { + +EntityId EntityIdTable::createEntityId(const EntityName &Name) { + auto [It, Inserted] = Entities.insert(Name); + + if (Inserted) { + IdToEntity.push_back(&(*It)); + return EntityId(IdToEntity.size() - 1); + } + + const EntityName *EntityPtr = &(*It); + auto IdIt = std::find(IdToEntity.begin(), IdToEntity.end(), EntityPtr); ---------------- aviralg wrote:
We are doing a linear scan here which is problematic from a scalability point of view. A translation unit can have tens of thousands of entities. Instead of a set, we should use a map to associate names to ids. That will result in a `O(lg N)` lookup time. There is another obvious optimization - creating a small cache of last few lookups. We can explore that in the future if lookups contribute significantly in our benchmarks. https://github.com/llvm/llvm-project/pull/171660 _______________________________________________ cfe-commits mailing list [email protected] https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
