[Assignment Tracking] Elide a map copy in some cases

[Orlando]

Summary

Restructure AssignmentTrackingLowering::join to avoid a map copy in the case where BB has more than one pred.

We only need to perform a copy of a pred LiveOut if there's exactly one already-visited pred (Result = PredLiveOut). With more than one pred the result is built by calling Result = join(std::move(Result), PredLiveOut) for each subsequent pred, where join parameters are const &. i.e. with more than 1 pred we can avoid copying by referencing the first two pred LiveOuts in the first join and then using a move + reference for the rest.

This gives marginal gains in compile time for CTMark LTO-g builds (geomean reduction of 0.05% instructions retired).

[StephenTozer]

Broadly looks good, just a couple questions and a nit comment.

llvm/lib/CodeGen/AssignmentTrackingAnalysis.cpp

1777

visted->visited

1788

Tiny question - does using LiveIn[&BB] = ... here mean that an empty map will first be constructed in the &BB bucket before we assign to it? If that is the case it might be better to just use insert or try_emplace instead; don't think this is high impact either way.

1823–1824

I see that above for the single-visited-pred case you've split this if into two separate checks, so that you can use the found iterator CurrentLiveInEntry if it's valid. Since we're doing essentially the same thing here, would it make sense to use the same logic in both places, or is there a reason for the difference?

[jmorse]

Could you add the context for review; also, are there any clear winners in CTMark that justify this change? 0.05% is close to noise, and the function complexity increases substantially.

[Orlando]

Could you add the context for review

Will do, sorry about that.

Are there any clear winners in CTMark that justify this change? 0.05% is close to noise, and the function complexity increases substantially.

Good question, -0.22% for tramp3d-v4 and -0.11% for mafft in that suite. However, it's probably worth me checking if the improvement is worth it after D145558.

llvm/lib/CodeGen/AssignmentTrackingAnalysis.cpp

1823–1824

Originally for line count / simplicity, but at this point it doesn't really make a difference. Changed.

[Orlando]

It actually looks like this is now more important with D145558 applied (around 0.24% difference). Here is the impact when this patch is reverted: http://llvm-compile-time-tracker.com/compare.php?from=baec5155d5e0c5d8cc0a2f51bd7fa14f785a0093&to=68d93a1c2d58990d7cd96f0b826b944fcc7d86f3&stat=instructions

+ Use ArrayRef.drop_front to get the preds vector "tail"
+ Reduce clutter of insertion code
+ Address nits

[jmorse]

LGTM with a question; this does introduce knarlyness, so we should revisit this if we manage to make the pass faster.

llvm/lib/CodeGen/AssignmentTrackingAnalysis.cpp

1779–1780

To confirm my understanding: with no predecessors visited, there's no information in BlockInfo, and this attempts to place it in the live-in maps. If this block has already been visited then there can _only_ be an empty BlockInfo there already, so it's safe to use "try_emplace" and allow it to fail. Failure means the same BlockInfo is in the map, but we don't need to explore any further because there's been no change.

(I worry that try_emplace failing would cause exploration to cease too early, but if the above is true, then it's sound).

[Orlando]

Thanks!

llvm/lib/CodeGen/AssignmentTrackingAnalysis.cpp

1779–1780

That's exactly right, yeah.

llvm/lib/CodeGen/AssignmentTrackingAnalysis.cpp

 AssignmentTrackingLowering::BlockInfo
 AssignmentTrackingLowering::joinBlockInfo(const BlockInfo &A,
                                           const BlockInfo &B) {
   return BlockInfo::join(A, B, TrackedVariablesVectorSize);
 }
 
 bool AssignmentTrackingLowering::join(
     const BasicBlock &BB, const SmallPtrSet<BasicBlock *, 16> &Visited) {
-  BlockInfo BBLiveIn;
-  bool FirstJoin = true;
-  // LiveIn locs for BB is the join of the already-processed preds' LiveOut
-  // locs.
-  for (auto I = pred_begin(&BB), E = pred_end(&BB); I != E; I++) {
-    // Ignore backedges if we have not visited the predecessor yet. As the
-    // predecessor hasn't yet had locations propagated into it, most locations
-    // will not yet be valid, so treat them as all being uninitialized and
-    // potentially valid. If a location guessed to be correct here is
-    // invalidated later, we will remove it when we revisit this block. This
-    // is essentially the same as initialising all LocKinds and Assignments to
-    // an implicit ⊥ value which is the identity value for the join operation.
+
+  SmallVector<const BasicBlock *> VisitedPreds;
+  for (auto I = pred_begin(&BB), E = pred_end(&BB); I != E; I++) {
     const BasicBlock *Pred = *I;
-    if (!Visited.count(Pred))
-      continue;
+    if (Visited.count(Pred))
+      VisitedPreds.push_back(Pred);
+  }
 
-    auto PredLiveOut = LiveOut.find(Pred);
-    // Pred must have been processed already. See comment at start of this loop.
-    assert(PredLiveOut != LiveOut.end());
+  // No preds visited yet.
+  if (VisitedPreds.empty()) {
+    auto It = LiveIn.try_emplace(&BB, BlockInfo());
+    bool DidInsert = It.second;
+    if (DidInsert)
+      It.first->second.init(TrackedVariablesVectorSize);
+    return /*Changed*/ DidInsert;
+  }
+
+  // Exactly one visited pred. Copy the LiveOut from that pred into BB LiveIn.
+  if (VisitedPreds.size() == 1) {
+    const BlockInfo &PredLiveOut = LiveOut.find(VisitedPreds[0])->second;
+    auto CurrentLiveInEntry = LiveIn.find(&BB);
 
-    // Perform the join of BBLiveIn (current live-in info) and PrevLiveOut.
-    if (FirstJoin)
-      BBLiveIn = PredLiveOut->second;
+    // Check if there isn't an entry, or there is but the LiveIn set has
+    // changed (expensive check).
+    if (CurrentLiveInEntry == LiveIn.end())
+      LiveIn.insert(std::make_pair(&BB, PredLiveOut));
+    else if (PredLiveOut != CurrentLiveInEntry->second)
+      CurrentLiveInEntry->second = PredLiveOut;
     else
-      BBLiveIn = joinBlockInfo(std::move(BBLiveIn), PredLiveOut->second);
-    FirstJoin = false;
+      return /*Changed*/ false;
+    return /*Changed*/ true;
   }
 
-  if (FirstJoin)
-    BBLiveIn.init(TrackedVariablesVectorSize);
+  // More than one pred. Join LiveOuts of blocks 1 and 2.
+  assert(VisitedPreds.size() > 1);
+  const BlockInfo &PredLiveOut0 = LiveOut.find(VisitedPreds[0])->second;
+  const BlockInfo &PredLiveOut1 = LiveOut.find(VisitedPreds[1])->second;
+  BlockInfo BBLiveIn = joinBlockInfo(PredLiveOut0, PredLiveOut1);
+
+  // Join the LiveOuts of subsequent blocks.
+  ArrayRef Tail = ArrayRef(VisitedPreds).drop_front(2);
+  for (const BasicBlock *Pred : Tail) {
+    const auto &PredLiveOut = LiveOut.find(Pred);
+    assert(PredLiveOut != LiveOut.end() &&
+           "block should have been processed already");
+    BBLiveIn = joinBlockInfo(std::move(BBLiveIn), PredLiveOut->second);
+  }
 
+  // Save the joined result for BB.
   auto CurrentLiveInEntry = LiveIn.find(&BB);
   // Check if there isn't an entry, or there is but the LiveIn set has changed
   // (expensive check).
-  if (CurrentLiveInEntry == LiveIn.end() ||
-      BBLiveIn != CurrentLiveInEntry->second) {
-    LiveIn[&BB] = std::move(BBLiveIn);
-    // A change has occured.
-    return true;
-  }
-  // No change.
-  return false;
+  if (CurrentLiveInEntry == LiveIn.end())
+    LiveIn.try_emplace(&BB, std::move(BBLiveIn));
+  else if (BBLiveIn != CurrentLiveInEntry->second)
+    CurrentLiveInEntry->second = std::move(BBLiveIn);
+  else
+    return /*Changed*/ false;
+  return /*Changed*/ true;
 }
 
 /// Return true if A fully contains B.
 static bool fullyContains(DIExpression::FragmentInfo A,
                           DIExpression::FragmentInfo B) {
   auto ALeft = A.OffsetInBits;
   auto BLeft = B.OffsetInBits;
   if (BLeft < ALeft)