Page MenuHomePhabricator

[MemCpyOpt] Port to MemorySSA. Disabled by default.
Needs ReviewPublic

Authored by bryant on Nov 16 2016, 3:27 AM.

Details

Summary

This creates a MemorySSA-backed analogue of MemCpyOpt that is disabled by
default. It can be enabled by passing to opt either its pass-specific flag
(-memcpyopt-mssa) or a force flag (e.g., -O3 -mco-mssa).

In order to facilitate code review and correctness checking, the changes have
been made to resemble as closely as possible the pattern matching and
transformation logic of the legacy pass. In particular, non-local results from
MemorySSAWalker::getClobberingMemoryAccess/getCMA are ignored since the
MemDep version can only see patterns within a single block. The idea is to land
this patch first before adding back non-locality and other more sophisticated
matchers.

Diff Detail

Repository
rL LLVM

Event Timeline

bryant updated this revision to Diff 78157.Nov 16 2016, 3:27 AM
bryant retitled this revision from to [MemCpyOpt] Port to MemorySSA. Disabled by default..
bryant updated this object.
bryant added reviewers: dberlin, hfinkel.
bryant set the repository for this revision to rL LLVM.
bryant added a subscriber: llvm-commits.

FileCheck output of both versions (should, and do) closely match each other.
This can be verified by first applying the patch and then:

bash
# refresh the FileCheck results for pertinent .ll tests
$ for chk in `grep -r -l MCO-MSSA test/`; do python util/update_test_check.py --tool=opt $chk; done

# verify that results are identical
$ for chk in `grep -r -l MCO-MSSA test/`; do python verifier.py $chk; done

# the verifier
$ cat verifier.py
"""
Checks if FileChecks of both labels are identical.
"""

from re import sub
from itertools import ifilter, groupby, izip_longest

def collect_outputs(lines):
    mco, mssa = [], []
    check_lines = ifilter(lambda s: "; CHECK" in s or "; MCO-MSSA" in s, lines)
    for mcoty, line in groupby(check_lines, lambda s: "; CHECK" in s):
        if mcoty:
            mco.append(map(lambda s: sub("^; CHECK\S+\s+", "", s), line))
        else:
            mssa.append(map(lambda s: sub("^; MCO-MSSA\S+\s+", "", s), line))
    return mco, mssa

if __name__ == "__main__":
    from sys import stdin, argv
    from difflib import ndiff

    lines = stdin.readlines() if len(argv) < 2 else open(argv[1]).readlines()
    mco, mssa = collect_outputs(lines)
    for a, b in izip_longest(mco, mssa):
        try:
            assert a == b
        except AssertionError:
            print "Problem in", ("stdin" if len(argv) == 0 else argv[1])
            a_ = [" " * 4 + l.strip() for l in (a or [])]
            b_ = [" " * 4 + l.strip() for l in (b or [])]
            print "\n".join(ndiff(a_, b_))
            continue
bryant added a comment.EditedNov 16 2016, 3:55 AM

Forgot to mention that this depends on:

  • The upward AccessList splice defined in D26661 and used by moveUp,
  • D26631 (NFC), which sets up the FileChecks for the legacy MemCpyOpt, and
  • the instructionClobbersQuery patch at D26659 in order to get the right clobbers for either source of dest memcpy locs.

EDIT: Clickables.

davide added a subscriber: davide.Dec 26 2016, 6:14 AM

Holding off on this until I can get non-local DSE running, since non-local MCO is useless without that.

mati865 added a subscriber: mati865.Mar 3 2019, 6:03 AM
Herald added a project: Restricted Project. · View Herald TranscriptMar 3 2019, 6:03 AM
jfb added a comment.Mar 3 2019, 1:51 PM

(random drive-by)

include/llvm/Transforms/Scalar.h
354

bool = false? enum class FTW.

lib/Transforms/Scalar/MemCpyOptimizer.cpp
127

Oxygen comments usually have triple slash at the beginning.

167

Drop StartPtrUser - (even if it matches the surrounding style).

331

Use the enum class here too.