I think you have a pretty good understanding of the algorithm. I could be missing something, but your proposal makes sense. If you write a patch, please add comments explaining your reasoning. And of course make sure the test suite passes with -enable-aa-sched-mi.
Here is a patch that implements the change in iterations over previously added memory dependencies, according to our discussion. Make check passed with -enable-aa-sched-mi.
[PATCH] New method SDep::isMemory() in ScheduleDAGInstrs.cpp.
Used to iterate over previously added memory dependencies in
adjustChainDeps() and iterateChainSucc().
SDep::isCtrl() was previously used in these places, that also gave
anti and output edges. The code may be worse if these are followed,
because MisNeedChainEdge() will conservatively return true since a
non-memory instruction has no memory operands, and a false chain dep
will be added. It is also unnecessary since all memory accesses of
interest will be reached by memory dependencies, and there is a budget
limit for the number of edges traversed.
This problem was found on an out-of-tree target with enabled alias
analysis. No test case for an in-tree target has been found.