MarkStep uses logic like this in a few places:

if (reason.Kind == DependencyKind.AlreadyMarked) {
	Debug.Assert (Annotations.IsMarked (member));
} else {
	Annotations.Mark (member, reason);
}
// possibly do extra work
if (CheckProcessed (member))
	return;
// do main work for the member

The AlreadyMarked check is to avoid calling Annotations.Mark twice when a different step marks a member through Annotations, and the CheckProcessed call ensures that most of the work is done only once per marked member. Sometimes there is logic in-between which can get called once for each time the member is marked.

We could avoid the AlreadyMarked check by splitting up the MarkStep.Mark* methods into variants that do/don't call Annotations.Mark, or by moving the check into Annotations.Mark.

In cases where there is no "extra work" done between Mark and CheckProcessed, we could then combine the Mark/CheckProcessed calls (assuming it is ok to remove the CheckProcessed extensibility point for derived classes).
With the extra tracking introduced by #1768, this would avoid an extra hashset lookup in a few cases.

See #1768 (comment)