[Assignment Tracking] Initialise maps with exact required number of entries

[Orlando]

Summary

The required size is known - the Join map in both cases gets an entry for each variable from both input maps (union). This avoids the unnecessary cost of repeatedly growing the map.

This improves ReleaseLTO-g compile time for CTMark projects by an average of around 0.2%.

[Orlando]

Thanks!

I made a mistake saying the exact size is known. This is actually the lower bound of the Join map size, since it is possible that the maps _both_ contain unique variables. I'll update the summary and description before landing.

llvm/lib/CodeGen/AssignmentTrackingAnalysis.cpp

AssignmentTrackingLowering::joinLocMap(const LocMap &A, const LocMap &B) {
   // D = join(x, ⊤) for x where Var(x) is in A xor B
   // Join = U ∪ D
   //
   // This is achieved by performing a join on elements from A and B with
   // variables common to both A and B (join elements indexed by var intersect),
   // then adding LocKind::None elements for vars in A xor B. The latter part is
   // equivalent to performing join on elements with variables in A xor B with
   // LocKind::None (⊤) since join(x, ⊤) = ⊤.
-  LocMap Join;
+  LocMap Join(std::max(A.size(), B.size()));
   SmallVector<VariableID, 16> SymmetricDifference;
   // Insert the join of the elements with common vars into Join. Add the
   // remaining elements to into SymmetricDifference.
   for (const auto &[Var, Loc] : A) {
     // If this Var doesn't exist in B then add it to the symmetric difference
     // set.
     auto R = B.find(Var);
     if (R == B.end()) {
AssignmentTrackingLowering::joinAssignmentMap(const AssignmentMap &A,
   // D = join(x, ⊤) for x where Var(x) is in A xor B
   // Join = U ∪ D
   //
   // This is achieved by performing a join on elements from A and B with
   // variables common to both A and B (join elements indexed by var intersect),
   // then adding LocKind::None elements for vars in A xor B. The latter part is
   // equivalent to performing join on elements with variables in A xor B with
   // Status::NoneOrPhi (⊤) since join(x, ⊤) = ⊤.
-  AssignmentMap Join;
+  AssignmentMap Join(std::max(A.size(), B.size()));
   SmallVector<VariableID, 16> SymmetricDifference;
   // Insert the join of the elements with common vars into Join. Add the
   // remaining elements to into SymmetricDifference.
   for (const auto &[Var, AV] : A) {
     // If this Var doesn't exist in B then add it to the symmetric difference
     // set.
     auto R = B.find(Var);
     if (R == B.end()) {