Resubmit of rL345008 "Split MachinePipeliner code into header and cpp files"

[lsaba]

Summary

I would like to try to resubmit this patch which was approved in https://reviews.llvm.org/D53477
The patch was reverted since it broke the build in http://green.lab.llvm.org/green//job/lldb-cmake/
Unfortunately the logs were already expired by the time I saw the comment. I tried to locally reproduce but was unable to see an error.
I will revert the commit if the error appears, this will allow me to view the error log for that run.
Alternatively, If someone can help with re-running this patch on http://green.lab.llvm.org/green//job/lldb-cmake/ that would be appreciated!

[aleksandr.urakov]

I have no objections against the such approach, but I'm not sure if this acceptable by the LLVM development rules... Let's ask about it a more experienced participant?

[lsaba]

Ping

[lsaba]

Ping2
@craig.topper is this okay with you?

[craig.topper]

LGTM

[sgraenitz]

Hello lsaba, sorry for having to revert this after it broke http://green.lab.llvm.org/green/job/lldb-cmake/ again.
I tried to find the root cause, but so far didn't succeed. I will continue tomorrow and keep you in the loop so you can land this as soon as possible.

[sgraenitz]

@aprantl Found a workaround for the lldb-cmake bot: https://reviews.llvm.org/rL350346

I tested it locally with your patch reapplied and the error is fixed. Sorry again for the hassle. Please submit your patch. Thanks

[lsaba]

In D56084#1346142, @sgraenitz wrote:

@aprantl Found a workaround for the lldb-cmake bot: https://reviews.llvm.org/rL350346

I tested it locally with your patch reapplied and the error is fixed. Sorry again for the hassle. Please submit your patch. Thanks

Thanks for the help! I will try to resubmit

[lsaba]

In D56084#1346142, @sgraenitz wrote:

@aprantl Found a workaround for the lldb-cmake bot: https://reviews.llvm.org/rL350346

I tested it locally with your patch reapplied and the error is fixed. Sorry again for the hassle. Please submit your patch. Thanks

@aprantl , @sgraenitz , I tried to resbumit the patch in https://reviews.llvm.org/rL350493 but unfortunately issues with the modules still appear: http://lab.llvm.org:8011/builders/lldb-x64-windows-ninja/builds/314/steps/test/logs/stdio

it is now able to build but the lit test SymbolFile/PDB/class-layout.test is failing:

$ ":" "RUN: at line 4"
$ "E:\build_slave\lldb-x64-windows-ninja\build\bin\lldb-test.EXE" "symbols" "E:\build_slave\lldb-x64-windows-ninja\build\tools\lldb\lit\SymbolFile\PDB\Output/ClassLayoutTest.cpp.exe"

command stderr:

error: Module has no symbol vendor.

error: command failed with exit status: 1
$ "E:\build_slave\lldb-x64-windows-ninja\build\bin\FileCheck.EXE" "E:\build_slave\lldb-x64-windows-ninja\llvm\tools\lldb\lit\SymbolFile\PDB\class-layout.test"

command stderr:

E:\build_slave\lldb-x64-windows-ninja\llvm\tools\lldb\lit\SymbolFile\PDB\class-layout.test:15:8: error: CHECK: expected string not found in input
CHECK: Module [[MOD:.*]]

^

<stdin>:1:1: note: scanning from here
Module: E:\build_slave\lldb-x64-windows-ninja\build\tools\lldb\lit\SymbolFile\PDB\Output/ClassLayoutTest.cpp.exe

I have reverted the patch again for now as I am unable to reproduce the issue locally, your help will be much apprecicated

[aprantl]

In D56084#1347564, @lsaba wrote:

In D56084#1346142, @sgraenitz wrote:

@aprantl Found a workaround for the lldb-cmake bot: https://reviews.llvm.org/rL350346

I tested it locally with your patch reapplied and the error is fixed. Sorry again for the hassle. Please submit your patch. Thanks

@aprantl , @sgraenitz , I tried to resbumit the patch in https://reviews.llvm.org/rL350493 but unfortunately issues with the modules still appear: http://lab.llvm.org:8011/builders/lldb-x64-windows-ninja/builds/314/steps/test/logs/stdio

it is now able to build but the lit test SymbolFile/PDB/class-layout.test is failing:

$ ":" "RUN: at line 4"
$ "E:\build_slave\lldb-x64-windows-ninja\build\bin\lldb-test.EXE" "symbols" "E:\build_slave\lldb-x64-windows-ninja\build\tools\lldb\lit\SymbolFile\PDB\Output/ClassLayoutTest.cpp.exe"

command stderr:

error: Module has no symbol vendor.

error: command failed with exit status: 1
$ "E:\build_slave\lldb-x64-windows-ninja\build\bin\FileCheck.EXE" "E:\build_slave\lldb-x64-windows-ninja\llvm\tools\lldb\lit\SymbolFile\PDB\class-layout.test"

command stderr:

E:\build_slave\lldb-x64-windows-ninja\llvm\tools\lldb\lit\SymbolFile\PDB\class-layout.test:15:8: error: CHECK: expected string not found in input
CHECK: Module [[MOD:.*]]

^

<stdin>:1:1: note: scanning from here
Module: E:\build_slave\lldb-x64-windows-ninja\build\tools\lldb\lit\SymbolFile\PDB\Output/ClassLayoutTest.cpp.exe

I have reverted the patch again for now as I am unable to reproduce the issue locally, your help will be much apprecicated

Even though this error also has Module in the name, this is a completely unrelated issue. Unfortunately Module is a terribly overloaded term. Are you sure that this was actually caused by your commit? It sounds unlikely.

[lsaba]

In D56084#1348493, @aprantl wrote:

In D56084#1347564, @lsaba wrote:

In D56084#1346142, @sgraenitz wrote:

@aprantl Found a workaround for the lldb-cmake bot: https://reviews.llvm.org/rL350346

I tested it locally with your patch reapplied and the error is fixed. Sorry again for the hassle. Please submit your patch. Thanks

@aprantl , @sgraenitz , I tried to resbumit the patch in https://reviews.llvm.org/rL350493 but unfortunately issues with the modules still appear: http://lab.llvm.org:8011/builders/lldb-x64-windows-ninja/builds/314/steps/test/logs/stdio

it is now able to build but the lit test SymbolFile/PDB/class-layout.test is failing:

$ ":" "RUN: at line 4"
$ "E:\build_slave\lldb-x64-windows-ninja\build\bin\lldb-test.EXE" "symbols" "E:\build_slave\lldb-x64-windows-ninja\build\tools\lldb\lit\SymbolFile\PDB\Output/ClassLayoutTest.cpp.exe"

command stderr:

error: Module has no symbol vendor.

error: command failed with exit status: 1
$ "E:\build_slave\lldb-x64-windows-ninja\build\bin\FileCheck.EXE" "E:\build_slave\lldb-x64-windows-ninja\llvm\tools\lldb\lit\SymbolFile\PDB\class-layout.test"

command stderr:

E:\build_slave\lldb-x64-windows-ninja\llvm\tools\lldb\lit\SymbolFile\PDB\class-layout.test:15:8: error: CHECK: expected string not found in input
CHECK: Module [[MOD:.*]]

^

<stdin>:1:1: note: scanning from here
Module: E:\build_slave\lldb-x64-windows-ninja\build\tools\lldb\lit\SymbolFile\PDB\Output/ClassLayoutTest.cpp.exe

I have reverted the patch again for now as I am unable to reproduce the issue locally, your help will be much apprecicated

Even though this error also has Module in the name, this is a completely unrelated issue. Unfortunately Module is a terribly overloaded term. Are you sure that this was actually caused by your commit? It sounds unlikely.

My commit was the only one in this build which made me suspect it...
I had other failures reported later on, are those also unrelated to said modules ?
in second stage compile in http://lab.llvm.org:8011/builders/clang-x86_64-linux-selfhost-modules/builds/21662/steps/compile.llvm.stage2/logs/stdio

0. /home/buildbot/modules-slave-1/clang-x86_64-linux-selfhost-modules/llvm.src/tools/clang/include/clang/Frontend/Utils.h:24:2: current parser token 'include'
#0 0x0000000003fd06e9 llvm::sys::PrintStackTrace(llvm::raw_ostream&) (/home/buildbot/modules-slave-1/clang-x86_64-linux-selfhost-modules/llvm.obj/bin/clang-7+0x3fd06e9)
#1 0x0000000003fd0919 PrintStackTraceSignalHandler(void*) (/home/buildbot/modules-slave-1/clang-x86_64-linux-selfhost-modules/llvm.obj/bin/clang-7+0x3fd0919)
#2 0x0000000003fcce42 llvm::sys::RunSignalHandlers() (/home/buildbot/modules-slave-1/clang-x86_64-linux-selfhost-modules/llvm.obj/bin/clang-7+0x3fcce42)
#3 0x0000000003fd32c8 SignalHandler(int) (/home/buildbot/modules-slave-1/clang-x86_64-linux-selfhost-modules/llvm.obj/bin/clang-7+0x3fd32c8)
#4 0x00007fe359bf5890 restore_rt (/lib/x86_64-linux-gnu/libpthread.so.0+0x12890)
#5 0x0000000003f00355 llvm::MemoryBuffer::init(char const*, char const*, bool) (/home/buildbot/modules-slave-1/clang-x86_64-linux-selfhost-modules/llvm.obj/bin/clang-7+0x3f00355)
#6 0x0000000003f05107 (anonymous namespace)::MemoryBufferMMapFile<llvm::MemoryBuffer>::MemoryBufferMMapFile(bool, int, unsigned long, unsigned long, std::1::error_code&) (/home/buildbot/modules-slave-1/clang-x86_64-linux-selfhost-modules/llvm.obj/bin/clang-7+0x3f05107)
#7 0x0000000003f0233d llvm::ErrorOr<std::1::unique_ptr<llvm::MemoryBuffer, std::1::default_delete<llvm::MemoryBuffer> > > getOpenFileImpl<llvm::MemoryBuffer>(int, llvm::Twine const&, unsigned long, unsigned long, long, bool, bool) (/home/buildbot/modules-slave-1/clang-x86_64-linux-selfhost-modules/llvm.obj/bin/clang-7+0x3f0233d)
#8 0x0000000003f02063 llvm::MemoryBuffer::getOpenFile(int, llvm::Twine const&, unsigned long, bool, bool) (/home/buildbot/modules-slave-1/clang-x86_64-linux-selfhost-modules/llvm.obj/bin/clang-7+0x3f02063)
#9 0x00000000091b7551 (anonymous namespace)::RealFile::getBuffer(llvm::Twine const&, long, bool, bool) (/home/buildbot/modules-slave-1/clang-x86_64-linux-selfhost-modules/llvm.obj/bin/clang-7+0x91b7551)
#10 0x00000000042b88bb clang::FileManager::getBufferForFile(clang::FileEntry const*, bool, bool) (/home/buildbot/modules-slave-1/clang-x86_64-linux-selfhost-modules/llvm.obj/bin/clang-7+0x42b88bb)
#11 0x0000000005313291 clang::serialization::ModuleManager::addModule(llvm::StringRef, clang::serialization::ModuleKind, clang::SourceLocation, clang::serialization::ModuleFile*, unsigned int, long, long, clang::ASTFileSignature, clang::ASTFileSignature (*)(llvm::StringRef), clang::serialization::ModuleFile*&, std::1::basic_string<char, std::1::char_traits<char>, std::1::allocator<char> >&) (/home/buildbot/modules-slave-1/clang-x86_64-linux-selfhost-modules/llvm.obj/bin/clang-7+0x5313291)
#12 0x00000000050ac8b6 clang::ASTReader::ReadASTCore(llvm::StringRef, clang::serialization::ModuleKind, clang::SourceLocation, clang::serialization::ModuleFile*, llvm::SmallVectorImpl<clang::ASTReader::ImportedModule>&, long, long, clang::ASTFileSignature, unsigned int) (/home/buildbot/modules-slave-1/clang-x86_64-linux-selfhost-modules/llvm.obj/bin/clang-7+0x50ac8b6)
#13 0x00000000050c5cba clang::ASTReader::ReadAST(llvm::StringRef, clang::serialization::ModuleKind, clang::SourceLocation, unsigned int, llvm::SmallVectorImpl<clang::ASTReader::ImportedSubmodule>*) (/home/buildbot/modules-slave-1/clang-x86_64-linux-selfhost-modules/llvm.obj/bin/clang-7+0x50c5cba)
#14 0x0000000004daeb2e compileAndLoadModule(clang::CompilerInstance&, clang::SourceLocation, clang::SourceLocation, clang::Module*, llvm::StringRef) (/home/buildbot/modules-slave-1/clang-x86_64-linux-selfhost-modules/llvm.obj/bin/clang-7+0x4daeb2e)
#15 0x0000000004daa533 clang::CompilerInstance::loadModule(clang::SourceLocation, llvm::ArrayRef<std::1::pair<clang::IdentifierInfo*, clang::SourceLocation> >, clang::Module::NameVisibilityKind, bool) (/home/buildbot/modules-slave-1/clang-x86_64-linux-selfhost-modules/llvm.obj/bin/clang-7+0x4daa533)
#16 0x0000000008d9f6f4 clang::Preprocessor::HandleIncludeDirective(clang::SourceLocation, clang::Token&, clang::DirectoryLookup const*, clang::FileEntry const*, bool) (/home/buildbot/modules-slave-1/clang-x86_64-linux-selfhost-modules/llvm.obj/bin/clang-7+0x8d9f6f4)
#17 0x0000000008da1d25 clang::Preprocessor::HandleDirective(clang::Token&) (/home/buildbot/modules-slave-1/clang-x86_64-linux-selfhost-modules/llvm.obj/bin/clang-7+0x8da1d25)
#18 0x0000000008d236bc clang::Lexer::LexTokenInternal(clang::Token&, bool) (/home/buildbot/modules-slave-1/clang-x86_64-linux-selfhost-modules/llvm.obj/bin/clang-7+0x8d236bc)
#19 0x0000000008d1f0c8 clang::Lexer::Lex(clang::Token&) (/home/buildbot/modules-slave-1/clang-x86_64-linux-selfhost-modules/llvm.obj/bin/clang-7+0x8d1f0c8)
#20 0x0000000008e3205b clang::Preprocessor::Lex(clang::Token&) (/home/buildbot/modules-slave-1/clang-x86_64-linux-selfhost-modules/llvm.obj/bin/clang-7+0x8e3205b)
#21 0x00000000074bdf76 clang::Parser::ConsumeAnnotationToken() (/home/buildbot/modules-slave-1/clang-x86_64-linux-selfhost-modules/llvm.obj/bin/clang-7+0x74bdf76)
#22 0x00000000074bd86a clang::Parser::ParseTopLevelDecl(clang::OpaquePtr<clang::DeclGroupRef>&) (/home/buildbot/modules-slave-1/clang-x86_64-linux-selfhost-modules/llvm.obj/bin/clang-7+0x74bd86a)
#23 0x00000000074b41c0 clang::ParseAST(clang::Sema&, bool, bool) (/home/buildbot/modules-slave-1/clang-x86_64-linux-selfhost-modules/llvm.obj/bin/clang-7+0x74b41c0)
#24 0x0000000004e786e9 clang::ASTFrontendAction::ExecuteAction() (/home/buildbot/modules-slave-1/clang-x86_64-linux-selfhost-modules/llvm.obj/bin/clang-7+0x4e786e9)
#25 0x0000000004e77460 clang::FrontendAction::Execute() (/home/buildbot/modules-slave-1/clang-x86_64-linux-selfhost-modules/llvm.obj/bin/clang-7+0x4e77460)
#26 0x0000000004da16ae clang::CompilerInstance::ExecuteAction(clang::FrontendAction&) (/home/buildbot/modules-slave-1/clang-x86_64-linux-selfhost-modules/llvm.obj/bin/clang-7+0x4da16ae)
#27 0x0000000004dd1923 compileModuleImpl(clang::CompilerInstance&, clang::SourceLocation, llvm::StringRef, clang::FrontendInputFile, llvm::StringRef, llvm::StringRef, llvm::function_ref<void (clang::CompilerInstance&)>, llvm::function_ref<void (clang::CompilerInstance&)>)::$_3::operator()() const (/home/buildbot/modules-slave-1/clang-x86_64-linux-selfhost-modules/llvm.obj/bin/clang-7+0x4dd1923)
#28 0x0000000004dd18e5 void llvm::function_ref<void ()>::callback_fn<compileModuleImpl(clang::CompilerInstance&, clang::SourceLocation, llvm::StringRef, clang::FrontendInputFile, llvm::StringRef, llvm::StringRef, llvm::function_ref<void (clang::CompilerInstance&)>, llvm::function_ref<void (clang::CompilerInstance&)>)::$_3>(long) (/home/buildbot/modules-slave-1/clang-x86_64-linux-selfhost-modules/llvm.obj/bin/clang-7+0x4dd18e5)
#29 0x00000000074ff299 llvm::function_ref<void ()>::operator()() const (/home/buildbot/modules-slave-1/clang-x86_64-linux-selfhost-modules/llvm.obj/bin/clang-7+0x74ff299)
#30 0x000000000913419b llvm::CrashRecoveryContext::RunSafely(llvm::function_ref<void ()>) (/home/buildbot/modules-slave-1/clang-x86_64-linux-selfhost-modules/llvm.obj/bin/clang-7+0x913419b)
#31 0x000000000913446f RunSafelyOnThread_Dispatch(void*) (/home/buildbot/modules-slave-1/clang-x86_64-linux-selfhost-modules/llvm.obj/bin/clang-7+0x913446f)
#32 0x0000000003fd8b50 ExecuteOnThread_Dispatch(void*) (/home/buildbot/modules-slave-1/clang-x86_64-linux-selfhost-modules/llvm.obj/bin/clang-7+0x3fd8b50)
#33 0x00007fe359bea6db start_thread (/lib/x86_64-linux-gnu/libpthread.so.0+0x76db)
#34 0x00007fe35883488f clone (/lib/x86_64-linux-gnu/libc.so.6+0x12188f)
clang-7: error: unable to execute command: Bus error (core dumped)
clang-7: error: clang frontend command failed due to signal (use -v to see invocation)
clang version 8.0.0 (trunk 350498)
Target: x86_64-pc-linux-gnu
Thread model: posix
InstalledDir: /home/buildbot/modules-slave-1/clang-x86_64-linux-selfhost-modules/llvm.obj/bin
clang-7: note: diagnostic msg: PLEASE submit a bug report to https://bugs.llvm.org/ and include the crash backtrace, preprocessed source, and associated run script.

and a test failure in http://green.lab.llvm.org/green/job/lldb-cmake/16358/consoleFull>

FAIL: lldb-Suite :: macosx/queues/TestQueues.py (687 of 1432)

• TEST 'lldb-Suite :: macosx/queues/TestQueues.py' FAILED ****

lldb version 8.0.99
LLDB library dir: /Users/buildslave/jenkins/workspace/lldb-cmake/lldb-build/bin
LLDB import library dir: /Users/buildslave/jenkins/workspace/lldb-cmake/lldb-build/bin
libstdcxx tests will not be run because: Don't know how to build with libstdcxx on macosx
Skipping following debug info categories: ['dwo']
Session logs for test failures/errors/unexpected successes will go into directory '/Users/buildslave/jenkins/workspace/lldb-cmake/test/logs'
Command invoked: /Users/buildslave/jenkins/workspace/lldb-cmake/llvm/tools/lldb/test/dotest.py -q --arch=x86_64 -s /Users/buildslave/jenkins/workspace/lldb-cmake/lldb-build/lldb-test-traces --build-dir /Users/buildslave/jenkins/workspace/lldb-cmake/lldb-build/lldb-test-build.noindex -S nm -u CXXFLAGS -u CFLAGS --executable /Users/buildslave/jenkins/workspace/lldb-cmake/lldb-build/./bin/lldb --dsymutil /Users/buildslave/jenkins/workspace/lldb-cmake/lldb-build/./bin/dsymutil --filecheck /Users/buildslave/jenkins/workspace/lldb-cmake/lldb-build/./bin/FileCheck -C /Users/buildslave/jenkins/workspace/lldb-cmake/lldb-build/bin/clang --codesign-identity lldb_codesign --server /Users/buildslave/jenkins/workspace/lldb-cmake/lldb-build/./bin/debugserver --arch x86_64 --build-dir /Users/buildslave/jenkins/workspace/lldb-cmake/lldb-build/lldb-test-build.noindex --session-file-format fm -s=/Users/buildslave/jenkins/workspace/lldb-cmake/test/logs -t --env TERM=vt100 /Users/buildslave/jenkins/workspace/lldb-cmake/llvm/tools/lldb/packages/Python/lldbsuite/test/macosx/queues -p TestQueues.py
Change dir to: /Users/buildslave/jenkins/workspace/lldb-cmake/llvm/tools/lldb/packages/Python/lldbsuite/test/macosx/queues
runCmd: settings set symbols.clang-modules-cache-path "/Users/buildslave/jenkins/workspace/lldb-cmake/lldb-build/lldb-test-build.noindex/module-cache-lldb"
output: None
runCmd: settings set symbols.enable-external-lookup false
output: None
os command: make VPATH=/Users/buildslave/jenkins/workspace/lldb-cmake/llvm/tools/lldb/packages/Python/lldbsuite/test/macosx/queues -C /Users/buildslave/jenkins/workspace/lldb-cmake/lldb-build/lldb-test-build.noindex/macosx/queues/TestQueues.test_with_python_api_dsym -I /Users/buildslave/jenkins/workspace/lldb-cmake/llvm/tools/lldb/packages/Python/lldbsuite/test/macosx/queues -f /Users/buildslave/jenkins/workspace/lldb-cmake/llvm/tools/lldb/packages/Python/lldbsuite/test/macosx/queues/Makefile MAKE_DSYM=YES ARCH=x86_64 CC="/Users/buildslave/jenkins/workspace/lldb-cmake/lldb-build/bin/clang-8" all
with pid: 58169
stdout: /Users/buildslave/jenkins/workspace/lldb-cmake/lldb-build/bin/clang-8 -g -O0 -fno-builtin -arch x86_64 -I/Users/buildslave/jenkins/workspace/lldb-cmake/llvm/tools/lldb/packages/Python/lldbsuite/test/macosx/queues/../../make/../../../../../include -I/Users/buildslave/jenkins/workspace/lldb-cmake/llvm/tools/lldb/packages/Python/lldbsuite/test/macosx/queues/ -include /Users/buildslave/jenkins/workspace/lldb-cmake/llvm/tools/lldb/packages/Python/lldbsuite/test/macosx/queues/../../make/test_common.h -I/Users/buildslave/jenkins/workspace/lldb-cmake/llvm/tools/lldb/packages/Python/lldbsuite/test/macosx/queues/../../make/ -fno-limit-debug-info -c -o main.o /Users/buildslave/jenkins/workspace/lldb-cmake/llvm/tools/lldb/packages/Python/lldbsuite/test/macosx/queues/main.c
/Users/buildslave/jenkins/workspace/lldb-cmake/lldb-build/bin/clang-8 main.o -g -O0 -fno-builtin -arch x86_64 -I/Users/buildslave/jenkins/workspace/lldb-cmake/llvm/tools/lldb/packages/Python/lldbsuite/test/macosx/queues/../../make/../../../../../include -I/Users/buildslave/jenkins/workspace/lldb-cmake/llvm/tools/lldb/packages/Python/lldbsuite/test/macosx/queues/ -include /Users/buildslave/jenkins/workspace/lldb-cmake/llvm/tools/lldb/packages/Python/lldbsuite/test/macosx/queues/../../make/test_common.h -I/Users/buildslave/jenkins/workspace/lldb-cmake/llvm/tools/lldb/packages/Python/lldbsuite/test/macosx/queues/../../make/ -fno-limit-debug-info --driver-mode=g++ -o "a.out"
"/Users/buildslave/jenkins/workspace/lldb-cmake/lldb-build/./bin/dsymutil" -o "a.out.dSYM" "a.out"
stderr:
retcode: 0
<bound method SBProcess.Kill of <lldb.SBProcess; proxy of <Swig Object of type 'lldb::SBProcess *' at 0x10b519d50> >>: success
<bound method SBProcess.Kill of <lldb.SBProcess; proxy of <Swig Object of type 'lldb::SBProcess *' at 0x10b4155d0> >>: success
PASS: LLDB (/Users/buildslave/jenkins/workspace/lldb-cmake/lldb-build/bin/clang-8-x86_64) :: test_with_python_api_dsym (TestQueues.TestQueues)
runCmd: settings set symbols.clang-modules-cache-path "/Users/buildslave/jenkins/workspace/lldb-cmake/lldb-build/lldb-test-build.noindex/module-cache-lldb"
output: None
runCmd: settings set symbols.enable-external-lookup false
output: None
os command: make VPATH=/Users/buildslave/jenkins/workspace/lldb-cmake/llvm/tools/lldb/packages/Python/lldbsuite/test/macosx/queues -C /Users/buildslave/jenkins/workspace/lldb-cmake/lldb-build/lldb-test-build.noindex/macosx/queues/TestQueues.test_with_python_api_dwarf -I /Users/buildslave/jenkins/workspace/lldb-cmake/llvm/tools/lldb/packages/Python/lldbsuite/test/macosx/queues -f /Users/buildslave/jenkins/workspace/lldb-cmake/llvm/tools/lldb/packages/Python/lldbsuite/test/macosx/queues/Makefile MAKE_DSYM=NO ARCH=x86_64 CC="/Users/buildslave/jenkins/workspace/lldb-cmake/lldb-build/bin/clang-8"
with pid: 59833
stdout: /Users/buildslave/jenkins/workspace/lldb-cmake/lldb-build/bin/clang-8 -g -O0 -fno-builtin -arch x86_64 -I/Users/buildslave/jenkins/workspace/lldb-cmake/llvm/tools/lldb/packages/Python/lldbsuite/test/macosx/queues/../../make/../../../../../include -I/Users/buildslave/jenkins/workspace/lldb-cmake/llvm/tools/lldb/packages/Python/lldbsuite/test/macosx/queues/ -include /Users/buildslave/jenkins/workspace/lldb-cmake/llvm/tools/lldb/packages/Python/lldbsuite/test/macosx/queues/../../make/test_common.h -I/Users/buildslave/jenkins/workspace/lldb-cmake/llvm/tools/lldb/packages/Python/lldbsuite/test/macosx/queues/../../make/ -fno-limit-debug-info -c -o main.o /Users/buildslave/jenkins/workspace/lldb-cmake/llvm/tools/lldb/packages/Python/lldbsuite/test/macosx/queues/main.c
/Users/buildslave/jenkins/workspace/lldb-cmake/lldb-build/bin/clang-8 main.o -g -O0 -fno-builtin -arch x86_64 -I/Users/buildslave/jenkins/workspace/lldb-cmake/llvm/tools/lldb/packages/Python/lldbsuite/test/macosx/queues/../../make/../../../../../include -I/Users/buildslave/jenkins/workspace/lldb-cmake/llvm/tools/lldb/packages/Python/lldbsuite/test/macosx/queues/ -include /Users/buildslave/jenkins/workspace/lldb-cmake/llvm/tools/lldb/packages/Python/lldbsuite/test/macosx/queues/../../make/test_common.h -I/Users/buildslave/jenkins/workspace/lldb-cmake/llvm/tools/lldb/packages/Python/lldbsuite/test/macosx/queues/../../make/ -fno-limit-debug-info --driver-mode=g++ -o "a.out"
stderr:
retcode: 0
<bound method SBProcess.Kill of <lldb.SBProcess; proxy of <Swig Object of type 'lldb::SBProcess *' at 0x10b2d55a0> >>: success
<bound method SBProcess.Kill of <lldb.SBProcess; proxy of <Swig Object of type 'lldb::SBProcess *' at 0x10b415d50> >>: success

Sorry for copying the entire errors from the bots, but I am unable to reproduce locally

[aprantl]

Looks like these are unrelated failures. TestQueues started acting up last week because of a concurrency issue. I would recommend you attempt to re-land your commit again and see if any new failures show up. If you are unsure, feel free to ask here or on #llvm on IRC.

[lsaba]

In D56084#1348719, @aprantl wrote:

Looks like these are unrelated failures. TestQueues started acting up last week because of a concurrency issue. I would recommend you attempt to re-land your commit again and see if any new failures show up. If you are unsure, feel free to ask here or on #llvm on IRC.

Thanks, the failures do seem to appear in other unrelated commits. I will try to resubmit

[fhahn]

I am seeing lldb-cmake failing again, with the same error as with this patch earlier: http://green.lab.llvm.org/green/job/lldb-cmake/16557/

Did you try your patch with a bootstrap build as suggested in https://reviews.llvm.org/rL350290#304451?

[aprantl]

I committed a rather horrible workaround in r350650, but it would be great to revert that again.

What you need to test particularly is building with -DLLVM_ENABLE_MODULES=1.

[aprantl]

Hmmm.. my fix didn't go far enough. I reverted this patch once again, so we can sort this out without pressure. As long as you make sure that compiling with -DLLVM_ENABLE_MODULES=1 works, feel free to recommit at any time!

[lsaba]

In D56084#1350118, @aprantl wrote:

I committed a rather horrible workaround in r350650, but it would be great to revert that again.

What you need to test particularly is building with -DLLVM_ENABLE_MODULES=1.

@fhahn , @aprantl is this a Mac specific issue? because I tried the suggested bootstrap build with -DLLVM_ENABLE_MODULES=1 on linux and it worked fine. I don't have a Mac machine available to test this..
I am not sure I understand what you mean with making sure it worked with DLLVM_ENABLE_MODULES=1

[aprantl]

It should not be mac-specific, but it is possible that Linux uses a different default for LLVM_ENABLE_LOCAL_SUBMODULE_VISIBILITY. Can you try again with -DLLVM_ENABLE_LOCAL_SUBMODULE_VISIBILITY=0 -DLLVM_ENABLE_MODULES=1 ?

llvm/trunk/include/llvm/CodeGen/MachinePipeliner.h

10

This would be nice as a \file Doxygen comment?

[lsaba]

In D56084#1350146, @aprantl wrote:

Hmmm.. my fix didn't go far enough. I reverted this patch once again, so we can sort this out without pressure. As long as you make sure that compiling with -DLLVM_ENABLE_MODULES=1 works, feel free to recommit at any

In D56084#1350528, @aprantl wrote:

It should not be mac-specific, but it is possible that Linux uses a different default for LLVM_ENABLE_LOCAL_SUBMODULE_VISIBILITY. Can you try again with -DLLVM_ENABLE_LOCAL_SUBMODULE_VISIBILITY=0 -DLLVM_ENABLE_MODULES=1 ?

I tried to build with the suggested flags but I got unrelated errors on top of trunk without my commits.
The way i'm compiling and building is this:

first build: cmake '-G' 'Ninja' ../../llvm '-DLLVM_ENABLE_ASSERTIONS:BOOL=TRUE' '-DCMAKE_BUILD_TYPE=Release'
(This uses GNU 5.4 compiler to build)

second build: cmake '-G' 'Ninja' ../../llvm '-DLLVM_ENABLE_ASSERTIONS:BOOL=TRUE' '-DCMAKE_BUILD_TYPE=Release' '-DLLVM_VERSION_PATCH=99' '-DLLVM_ENABLE_MODULES=1' -DCMAKE_C_COMPILER=/firstbuild/bin/clang -DCMAKE_CXX_COMPILER=/firstbuild/bin/clang++ -DLLVM_ENABLE_LOCAL_SUBMODULE_VISIBILITY=0

without the second flag -DLLVM_ENABLE_LOCAL_SUBMODULE_VISIBILITY=0 I don't get errors when building with my patch.. Am i missing something with the compilation flags?

Is there an open bugzilla for this issue? or should I open one?

[aprantl]

You have to use clang in order to compile with clang module support enabled. If your host compiler is GCC, you will have to build clang first and then use that clang to compile clang again using all the MODULE cmake options.

[lsaba]

In D56084#1351317, @aprantl wrote:

You have to use clang in order to compile with clang module support enabled. If your host compiler is GCC, you will have to build clang first and then use that clang to compile clang again using all the MODULE cmake options.

this is what i did with my second build stated above, or is that also not enough?

[lsaba]

In D56084#1351317, @aprantl wrote:

You have to use clang in order to compile with clang module support enabled. If your host compiler is GCC, you will have to build clang first and then use that clang to compile clang again using all the MODULE cmake options.

I tried your suggestions and i still have no luck with reproducing this locally..
@aprantl , @sgraenitz @fhahn is anyone actively working on a fix for the issue? who can I assign a Bugzilla to?

[aprantl]

I *think* I fixed it for good in in r351077.

[lsaba]

In D56084#1356329, @aprantl wrote:

I *think* I fixed it for good in in r351077.

That's great news! thank you very much! do you happen to know why the dump function was causing issues in linking?

[aprantl]

Roughly: the implementation of print used code (MachineInstr operator<<) that lives in the CodeGen library, and various tools that don't link against CodeGen include header files from the CodeGen Clang module). Without local submodule visibility, this pulls in all headers of the CodeGen Clang module, thus causing code to be generated for the dump function, which then causes the linker error.

llvm/trunk/include/llvm/CodeGen/MachinePipeliner.h

+//===- MachinePipeliner.h - Machine Software Pipeliner Pass -------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// An implementation of the Swing Modulo Scheduling (SMS) software pipeliner.
+//
+// Software pipelining (SWP) is an instruction scheduling technique for loops
+// that overlap loop iterations and exploits ILP via a compiler transformation.
+//
+// Swing Modulo Scheduling is an implementation of software pipelining
+// that generates schedules that are near optimal in terms of initiation
+// interval, register requirements, and stage count. See the papers:
+//
+// "Swing Modulo Scheduling: A Lifetime-Sensitive Approach", by J. Llosa,
+// A. Gonzalez, E. Ayguade, and M. Valero. In PACT '96 Proceedings of the 1996
+// Conference on Parallel Architectures and Compilation Techiniques.
+//
+// "Lifetime-Sensitive Modulo Scheduling in a Production Environment", by J.
+// Llosa, E. Ayguade, A. Gonzalez, M. Valero, and J. Eckhardt. In IEEE
+// Transactions on Computers, Vol. 50, No. 3, 2001.
+//
+// "An Implementation of Swing Modulo Scheduling With Extensions for
+// Superblocks", by T. Lattner, Master's Thesis, University of Illinois at
+// Urbana-Chambpain, 2005.
+//
+//
+// The SMS algorithm consists of three main steps after computing the minimal
+// initiation interval (MII).
+// 1) Analyze the dependence graph and compute information about each
+//    instruction in the graph.
+// 2) Order the nodes (instructions) by priority based upon the heuristics
+//    described in the algorithm.
+// 3) Attempt to schedule the nodes in the specified order using the MII.
+//
+//===----------------------------------------------------------------------===//
+#ifndef LLVM_LIB_CODEGEN_MACHINEPIPELINER_H
+#define LLVM_LIB_CODEGEN_MACHINEPIPELINER_H
+
+#include "llvm/CodeGen/RegisterClassInfo.h"
+#include "llvm/CodeGen/ScheduleDAGInstrs.h"
+#include "llvm/CodeGen/TargetInstrInfo.h"
+
+namespace llvm {
+
+class NodeSet;
+class SMSchedule;
+
+extern cl::opt<bool> SwpEnableCopyToPhi;
+
+/// The main class in the implementation of the target independent
+/// software pipeliner pass.
+class MachinePipeliner : public MachineFunctionPass {
+public:
+  MachineFunction *MF = nullptr;
+  const MachineLoopInfo *MLI = nullptr;
+  const MachineDominatorTree *MDT = nullptr;
+  const InstrItineraryData *InstrItins;
+  const TargetInstrInfo *TII = nullptr;
+  RegisterClassInfo RegClassInfo;
+
+#ifndef NDEBUG
+  static int NumTries;
+#endif
+
+  /// Cache the target analysis information about the loop.
+  struct LoopInfo {
+    MachineBasicBlock *TBB = nullptr;
+    MachineBasicBlock *FBB = nullptr;
+    SmallVector<MachineOperand, 4> BrCond;
+    MachineInstr *LoopInductionVar = nullptr;
+    MachineInstr *LoopCompare = nullptr;
+  };
+  LoopInfo LI;
+
+  static char ID;
+
+  MachinePipeliner() : MachineFunctionPass(ID) {
+    initializeMachinePipelinerPass(*PassRegistry::getPassRegistry());
+  }
+
+  bool runOnMachineFunction(MachineFunction &MF) override;
+
+  void getAnalysisUsage(AnalysisUsage &AU) const override {
+    AU.addRequired<AAResultsWrapperPass>();
+    AU.addPreserved<AAResultsWrapperPass>();
+    AU.addRequired<MachineLoopInfo>();
+    AU.addRequired<MachineDominatorTree>();
+    AU.addRequired<LiveIntervals>();
+    MachineFunctionPass::getAnalysisUsage(AU);
+  }
+
+private:
+  void preprocessPhiNodes(MachineBasicBlock &B);
+  bool canPipelineLoop(MachineLoop &L);
+  bool scheduleLoop(MachineLoop &L);
+  bool swingModuloScheduler(MachineLoop &L);
+};
+
+/// This class builds the dependence graph for the instructions in a loop,
+/// and attempts to schedule the instructions using the SMS algorithm.
+class SwingSchedulerDAG : public ScheduleDAGInstrs {
+  MachinePipeliner &Pass;
+  /// The minimum initiation interval between iterations for this schedule.
+  unsigned MII = 0;
+  /// Set to true if a valid pipelined schedule is found for the loop.
+  bool Scheduled = false;
+  MachineLoop &Loop;
+  LiveIntervals &LIS;
+  const RegisterClassInfo &RegClassInfo;
+
+  /// A toplogical ordering of the SUnits, which is needed for changing
+  /// dependences and iterating over the SUnits.
+  ScheduleDAGTopologicalSort Topo;
+
+  struct NodeInfo {
+    int ASAP = 0;
+    int ALAP = 0;
+    int ZeroLatencyDepth = 0;
+    int ZeroLatencyHeight = 0;
+
+    NodeInfo() = default;
+  };
+  /// Computed properties for each node in the graph.
+  std::vector<NodeInfo> ScheduleInfo;
+
+  enum OrderKind { BottomUp = 0, TopDown = 1 };
+  /// Computed node ordering for scheduling.
+  SetVector<SUnit *> NodeOrder;
+
+  using NodeSetType = SmallVector<NodeSet, 8>;
+  using ValueMapTy = DenseMap<unsigned, unsigned>;
+  using MBBVectorTy = SmallVectorImpl<MachineBasicBlock *>;
+  using InstrMapTy = DenseMap<MachineInstr *, MachineInstr *>;
+
+  /// Instructions to change when emitting the final schedule.
+  DenseMap<SUnit *, std::pair<unsigned, int64_t>> InstrChanges;
+
+  /// We may create a new instruction, so remember it because it
+  /// must be deleted when the pass is finished.
+  SmallPtrSet<MachineInstr *, 4> NewMIs;
+
+  /// Ordered list of DAG postprocessing steps.
+  std::vector<std::unique_ptr<ScheduleDAGMutation>> Mutations;
+
+  /// Helper class to implement Johnson's circuit finding algorithm.
+  class Circuits {
+    std::vector<SUnit> &SUnits;
+    SetVector<SUnit *> Stack;
+    BitVector Blocked;
+    SmallVector<SmallPtrSet<SUnit *, 4>, 10> B;
+    SmallVector<SmallVector<int, 4>, 16> AdjK;
+    // Node to Index from ScheduleDAGTopologicalSort
+    std::vector<int> *Node2Idx;
+    unsigned NumPaths;
+    static unsigned MaxPaths;
+
+  public:
+    Circuits(std::vector<SUnit> &SUs, ScheduleDAGTopologicalSort &Topo)
+        : SUnits(SUs), Blocked(SUs.size()), B(SUs.size()), AdjK(SUs.size()) {
+      Node2Idx = new std::vector<int>(SUs.size());
+      unsigned Idx = 0;
+      for (const auto &NodeNum : Topo)
+        Node2Idx->at(NodeNum) = Idx++;
+    }
+
+    ~Circuits() { delete Node2Idx; }
+
+    /// Reset the data structures used in the circuit algorithm.
+    void reset() {
+      Stack.clear();
+      Blocked.reset();
+      B.assign(SUnits.size(), SmallPtrSet<SUnit *, 4>());
+      NumPaths = 0;
+    }
+
+    void createAdjacencyStructure(SwingSchedulerDAG *DAG);
+    bool circuit(int V, int S, NodeSetType &NodeSets, bool HasBackedge = false);
+    void unblock(int U);
+  };
+
+  struct CopyToPhiMutation : public ScheduleDAGMutation {
+    void apply(ScheduleDAGInstrs *DAG) override;
+  };
+
+public:
+  SwingSchedulerDAG(MachinePipeliner &P, MachineLoop &L, LiveIntervals &lis,
+                    const RegisterClassInfo &rci)
+      : ScheduleDAGInstrs(*P.MF, P.MLI, false), Pass(P), Loop(L), LIS(lis),
+        RegClassInfo(rci), Topo(SUnits, &ExitSU) {
+    P.MF->getSubtarget().getSMSMutations(Mutations);
+    if (SwpEnableCopyToPhi)
+      Mutations.push_back(llvm::make_unique<CopyToPhiMutation>());
+  }
+
+  void schedule() override;
+  void finishBlock() override;
+
+  /// Return true if the loop kernel has been scheduled.
+  bool hasNewSchedule() { return Scheduled; }
+
+  /// Return the earliest time an instruction may be scheduled.
+  int getASAP(SUnit *Node) { return ScheduleInfo[Node->NodeNum].ASAP; }
+
+  /// Return the latest time an instruction my be scheduled.
+  int getALAP(SUnit *Node) { return ScheduleInfo[Node->NodeNum].ALAP; }
+
+  /// The mobility function, which the number of slots in which
+  /// an instruction may be scheduled.
+  int getMOV(SUnit *Node) { return getALAP(Node) - getASAP(Node); }
+
+  /// The depth, in the dependence graph, for a node.
+  unsigned getDepth(SUnit *Node) { return Node->getDepth(); }
+
+  /// The maximum unweighted length of a path from an arbitrary node to the
+  /// given node in which each edge has latency 0
+  int getZeroLatencyDepth(SUnit *Node) {
+    return ScheduleInfo[Node->NodeNum].ZeroLatencyDepth;
+  }
+
+  /// The height, in the dependence graph, for a node.
+  unsigned getHeight(SUnit *Node) { return Node->getHeight(); }
+
+  /// The maximum unweighted length of a path from the given node to an
+  /// arbitrary node in which each edge has latency 0
+  int getZeroLatencyHeight(SUnit *Node) {
+    return ScheduleInfo[Node->NodeNum].ZeroLatencyHeight;
+  }
+
+  /// Return true if the dependence is a back-edge in the data dependence graph.
+  /// Since the DAG doesn't contain cycles, we represent a cycle in the graph
+  /// using an anti dependence from a Phi to an instruction.
+  bool isBackedge(SUnit *Source, const SDep &Dep) {
+    if (Dep.getKind() != SDep::Anti)
+      return false;
+    return Source->getInstr()->isPHI() || Dep.getSUnit()->getInstr()->isPHI();
+  }
+
+  bool isLoopCarriedDep(SUnit *Source, const SDep &Dep, bool isSucc = true);
+
+  /// The distance function, which indicates that operation V of iteration I
+  /// depends on operations U of iteration I-distance.
+  unsigned getDistance(SUnit *U, SUnit *V, const SDep &Dep) {
+    // Instructions that feed a Phi have a distance of 1. Computing larger
+    // values for arrays requires data dependence information.
+    if (V->getInstr()->isPHI() && Dep.getKind() == SDep::Anti)
+      return 1;
+    return 0;
+  }
+
+  /// Set the Minimum Initiation Interval for this schedule attempt.
+  void setMII(unsigned mii) { MII = mii; }
+
+  void applyInstrChange(MachineInstr *MI, SMSchedule &Schedule);
+
+  void fixupRegisterOverlaps(std::deque<SUnit *> &Instrs);
+
+  /// Return the new base register that was stored away for the changed
+  /// instruction.
+  unsigned getInstrBaseReg(SUnit *SU) {
+    DenseMap<SUnit *, std::pair<unsigned, int64_t>>::iterator It =
+        InstrChanges.find(SU);
+    if (It != InstrChanges.end())
+      return It->second.first;
+    return 0;
+  }
+
+  void addMutation(std::unique_ptr<ScheduleDAGMutation> Mutation) {
+    Mutations.push_back(std::move(Mutation));
+  }
+
+  static bool classof(const ScheduleDAGInstrs *DAG) { return true; }
+
+private:
+  void addLoopCarriedDependences(AliasAnalysis *AA);
+  void updatePhiDependences();
+  void changeDependences();
+  unsigned calculateResMII();
+  unsigned calculateRecMII(NodeSetType &RecNodeSets);
+  void findCircuits(NodeSetType &NodeSets);
+  void fuseRecs(NodeSetType &NodeSets);
+  void removeDuplicateNodes(NodeSetType &NodeSets);
+  void computeNodeFunctions(NodeSetType &NodeSets);
+  void registerPressureFilter(NodeSetType &NodeSets);
+  void colocateNodeSets(NodeSetType &NodeSets);
+  void checkNodeSets(NodeSetType &NodeSets);
+  void groupRemainingNodes(NodeSetType &NodeSets);
+  void addConnectedNodes(SUnit *SU, NodeSet &NewSet,
+                         SetVector<SUnit *> &NodesAdded);
+  void computeNodeOrder(NodeSetType &NodeSets);
+  void checkValidNodeOrder(const NodeSetType &Circuits) const;
+  bool schedulePipeline(SMSchedule &Schedule);
+  void generatePipelinedLoop(SMSchedule &Schedule);
+  void generateProlog(SMSchedule &Schedule, unsigned LastStage,
+                      MachineBasicBlock *KernelBB, ValueMapTy *VRMap,
+                      MBBVectorTy &PrologBBs);
+  void generateEpilog(SMSchedule &Schedule, unsigned LastStage,
+                      MachineBasicBlock *KernelBB, ValueMapTy *VRMap,
+                      MBBVectorTy &EpilogBBs, MBBVectorTy &PrologBBs);
+  void generateExistingPhis(MachineBasicBlock *NewBB, MachineBasicBlock *BB1,
+                            MachineBasicBlock *BB2, MachineBasicBlock *KernelBB,
+                            SMSchedule &Schedule, ValueMapTy *VRMap,
+                            InstrMapTy &InstrMap, unsigned LastStageNum,
+                            unsigned CurStageNum, bool IsLast);
+  void generatePhis(MachineBasicBlock *NewBB, MachineBasicBlock *BB1,
+                    MachineBasicBlock *BB2, MachineBasicBlock *KernelBB,
+                    SMSchedule &Schedule, ValueMapTy *VRMap,
+                    InstrMapTy &InstrMap, unsigned LastStageNum,
+                    unsigned CurStageNum, bool IsLast);
+  void removeDeadInstructions(MachineBasicBlock *KernelBB,
+                              MBBVectorTy &EpilogBBs);
+  void splitLifetimes(MachineBasicBlock *KernelBB, MBBVectorTy &EpilogBBs,
+                      SMSchedule &Schedule);
+  void addBranches(MBBVectorTy &PrologBBs, MachineBasicBlock *KernelBB,
+                   MBBVectorTy &EpilogBBs, SMSchedule &Schedule,
+                   ValueMapTy *VRMap);
+  bool computeDelta(MachineInstr &MI, unsigned &Delta);
+  void updateMemOperands(MachineInstr &NewMI, MachineInstr &OldMI,
+                         unsigned Num);
+  MachineInstr *cloneInstr(MachineInstr *OldMI, unsigned CurStageNum,
+                           unsigned InstStageNum);
+  MachineInstr *cloneAndChangeInstr(MachineInstr *OldMI, unsigned CurStageNum,
+                                    unsigned InstStageNum,
+                                    SMSchedule &Schedule);
+  void updateInstruction(MachineInstr *NewMI, bool LastDef,
+                         unsigned CurStageNum, unsigned InstrStageNum,
+                         SMSchedule &Schedule, ValueMapTy *VRMap);
+  MachineInstr *findDefInLoop(unsigned Reg);
+  unsigned getPrevMapVal(unsigned StageNum, unsigned PhiStage, unsigned LoopVal,
+                         unsigned LoopStage, ValueMapTy *VRMap,
+                         MachineBasicBlock *BB);
+  void rewritePhiValues(MachineBasicBlock *NewBB, unsigned StageNum,
+                        SMSchedule &Schedule, ValueMapTy *VRMap,
+                        InstrMapTy &InstrMap);
+  void rewriteScheduledInstr(MachineBasicBlock *BB, SMSchedule &Schedule,
+                             InstrMapTy &InstrMap, unsigned CurStageNum,
+                             unsigned PhiNum, MachineInstr *Phi,
+                             unsigned OldReg, unsigned NewReg,
+                             unsigned PrevReg = 0);
+  bool canUseLastOffsetValue(MachineInstr *MI, unsigned &BasePos,
+                             unsigned &OffsetPos, unsigned &NewBase,
+                             int64_t &NewOffset);
+  void postprocessDAG();
+};
+
+/// A NodeSet contains a set of SUnit DAG nodes with additional information
+/// that assigns a priority to the set.
+class NodeSet {
+  SetVector<SUnit *> Nodes;
+  bool HasRecurrence = false;
+  unsigned RecMII = 0;
+  int MaxMOV = 0;
+  unsigned MaxDepth = 0;
+  unsigned Colocate = 0;
+  SUnit *ExceedPressure = nullptr;
+  unsigned Latency = 0;
+
+public:
+  using iterator = SetVector<SUnit *>::const_iterator;
+
+  NodeSet() = default;
+  NodeSet(iterator S, iterator E) : Nodes(S, E), HasRecurrence(true) {
+    Latency = 0;
+    for (unsigned i = 0, e = Nodes.size(); i < e; ++i)
+      for (const SDep &Succ : Nodes[i]->Succs)
+        if (Nodes.count(Succ.getSUnit()))
+          Latency += Succ.getLatency();
+  }
+
+  bool insert(SUnit *SU) { return Nodes.insert(SU); }
+
+  void insert(iterator S, iterator E) { Nodes.insert(S, E); }
+
+  template <typename UnaryPredicate> bool remove_if(UnaryPredicate P) {
+    return Nodes.remove_if(P);
+  }
+
+  unsigned count(SUnit *SU) const { return Nodes.count(SU); }
+
+  bool hasRecurrence() { return HasRecurrence; };
+
+  unsigned size() const { return Nodes.size(); }
+
+  bool empty() const { return Nodes.empty(); }
+
+  SUnit *getNode(unsigned i) const { return Nodes[i]; };
+
+  void setRecMII(unsigned mii) { RecMII = mii; };
+
+  void setColocate(unsigned c) { Colocate = c; };
+
+  void setExceedPressure(SUnit *SU) { ExceedPressure = SU; }
+
+  bool isExceedSU(SUnit *SU) { return ExceedPressure == SU; }
+
+  int compareRecMII(NodeSet &RHS) { return RecMII - RHS.RecMII; }
+
+  int getRecMII() { return RecMII; }
+
+  /// Summarize node functions for the entire node set.
+  void computeNodeSetInfo(SwingSchedulerDAG *SSD) {
+    for (SUnit *SU : *this) {
+      MaxMOV = std::max(MaxMOV, SSD->getMOV(SU));
+      MaxDepth = std::max(MaxDepth, SSD->getDepth(SU));
+    }
+  }
+
+  unsigned getLatency() { return Latency; }
+
+  unsigned getMaxDepth() { return MaxDepth; }
+
+  void clear() {
+    Nodes.clear();
+    RecMII = 0;
+    HasRecurrence = false;
+    MaxMOV = 0;
+    MaxDepth = 0;
+    Colocate = 0;
+    ExceedPressure = nullptr;
+  }
+
+  operator SetVector<SUnit *> &() { return Nodes; }
+
+  /// Sort the node sets by importance. First, rank them by recurrence MII,
+  /// then by mobility (least mobile done first), and finally by depth.
+  /// Each node set may contain a colocate value which is used as the first
+  /// tie breaker, if it's set.
+  bool operator>(const NodeSet &RHS) const {
+    if (RecMII == RHS.RecMII) {
+      if (Colocate != 0 && RHS.Colocate != 0 && Colocate != RHS.Colocate)
+        return Colocate < RHS.Colocate;
+      if (MaxMOV == RHS.MaxMOV)
+        return MaxDepth > RHS.MaxDepth;
+      return MaxMOV < RHS.MaxMOV;
+    }
+    return RecMII > RHS.RecMII;
+  }
+
+  bool operator==(const NodeSet &RHS) const {
+    return RecMII == RHS.RecMII && MaxMOV == RHS.MaxMOV &&
+           MaxDepth == RHS.MaxDepth;
+  }
+
+  bool operator!=(const NodeSet &RHS) const { return !operator==(RHS); }
+
+  iterator begin() { return Nodes.begin(); }
+  iterator end() { return Nodes.end(); }
+
+  void print(raw_ostream &os) const {
+    os << "Num nodes " << size() << " rec " << RecMII << " mov " << MaxMOV
+       << " depth " << MaxDepth << " col " << Colocate << "\n";
+    for (const auto &I : Nodes)
+      os << "   SU(" << I->NodeNum << ") " << *(I->getInstr());
+    os << "\n";
+  }
+
+#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
+  LLVM_DUMP_METHOD void dump() const { print(dbgs()); }
+#endif
+};
+
+/// This class represents the scheduled code.  The main data structure is a
+/// map from scheduled cycle to instructions.  During scheduling, the
+/// data structure explicitly represents all stages/iterations.   When
+/// the algorithm finshes, the schedule is collapsed into a single stage,
+/// which represents instructions from different loop iterations.
+///
+/// The SMS algorithm allows negative values for cycles, so the first cycle
+/// in the schedule is the smallest cycle value.
+class SMSchedule {
+private:
+  /// Map from execution cycle to instructions.
+  DenseMap<int, std::deque<SUnit *>> ScheduledInstrs;
+
+  /// Map from instruction to execution cycle.
+  std::map<SUnit *, int> InstrToCycle;
+
+  /// Map for each register and the max difference between its uses and def.
+  /// The first element in the pair is the max difference in stages. The
+  /// second is true if the register defines a Phi value and loop value is
+  /// scheduled before the Phi.
+  std::map<unsigned, std::pair<unsigned, bool>> RegToStageDiff;
+
+  /// Keep track of the first cycle value in the schedule.  It starts
+  /// as zero, but the algorithm allows negative values.
+  int FirstCycle = 0;
+
+  /// Keep track of the last cycle value in the schedule.
+  int LastCycle = 0;
+
+  /// The initiation interval (II) for the schedule.
+  int InitiationInterval = 0;
+
+  /// Target machine information.
+  const TargetSubtargetInfo &ST;
+
+  /// Virtual register information.
+  MachineRegisterInfo &MRI;
+
+  std::unique_ptr<DFAPacketizer> Resources;
+
+public:
+  SMSchedule(MachineFunction *mf)
+      : ST(mf->getSubtarget()), MRI(mf->getRegInfo()),
+        Resources(ST.getInstrInfo()->CreateTargetScheduleState(ST)) {}
+
+  void reset() {
+    ScheduledInstrs.clear();
+    InstrToCycle.clear();
+    RegToStageDiff.clear();
+    FirstCycle = 0;
+    LastCycle = 0;
+    InitiationInterval = 0;
+  }
+
+  /// Set the initiation interval for this schedule.
+  void setInitiationInterval(int ii) { InitiationInterval = ii; }
+
+  /// Return the first cycle in the completed schedule.  This
+  /// can be a negative value.
+  int getFirstCycle() const { return FirstCycle; }
+
+  /// Return the last cycle in the finalized schedule.
+  int getFinalCycle() const { return FirstCycle + InitiationInterval - 1; }
+
+  /// Return the cycle of the earliest scheduled instruction in the dependence
+  /// chain.
+  int earliestCycleInChain(const SDep &Dep);
+
+  /// Return the cycle of the latest scheduled instruction in the dependence
+  /// chain.
+  int latestCycleInChain(const SDep &Dep);
+
+  void computeStart(SUnit *SU, int *MaxEarlyStart, int *MinLateStart,
+                    int *MinEnd, int *MaxStart, int II, SwingSchedulerDAG *DAG);
+  bool insert(SUnit *SU, int StartCycle, int EndCycle, int II);
+
+  /// Iterators for the cycle to instruction map.
+  using sched_iterator = DenseMap<int, std::deque<SUnit *>>::iterator;
+  using const_sched_iterator =
+      DenseMap<int, std::deque<SUnit *>>::const_iterator;
+
+  /// Return true if the instruction is scheduled at the specified stage.
+  bool isScheduledAtStage(SUnit *SU, unsigned StageNum) {
+    return (stageScheduled(SU) == (int)StageNum);
+  }
+
+  /// Return the stage for a scheduled instruction.  Return -1 if
+  /// the instruction has not been scheduled.
+  int stageScheduled(SUnit *SU) const {
+    std::map<SUnit *, int>::const_iterator it = InstrToCycle.find(SU);
+    if (it == InstrToCycle.end())
+      return -1;
+    return (it->second - FirstCycle) / InitiationInterval;
+  }
+
+  /// Return the cycle for a scheduled instruction. This function normalizes
+  /// the first cycle to be 0.
+  unsigned cycleScheduled(SUnit *SU) const {
+    std::map<SUnit *, int>::const_iterator it = InstrToCycle.find(SU);
+    assert(it != InstrToCycle.end() && "Instruction hasn't been scheduled.");
+    return (it->second - FirstCycle) % InitiationInterval;
+  }
+
+  /// Return the maximum stage count needed for this schedule.
+  unsigned getMaxStageCount() {
+    return (LastCycle - FirstCycle) / InitiationInterval;
+  }
+
+  /// Return the max. number of stages/iterations that can occur between a
+  /// register definition and its uses.
+  unsigned getStagesForReg(int Reg, unsigned CurStage) {
+    std::pair<unsigned, bool> Stages = RegToStageDiff[Reg];
+    if (CurStage > getMaxStageCount() && Stages.first == 0 && Stages.second)
+      return 1;
+    return Stages.first;
+  }
+
+  /// The number of stages for a Phi is a little different than other
+  /// instructions. The minimum value computed in RegToStageDiff is 1
+  /// because we assume the Phi is needed for at least 1 iteration.
+  /// This is not the case if the loop value is scheduled prior to the
+  /// Phi in the same stage.  This function returns the number of stages
+  /// or iterations needed between the Phi definition and any uses.
+  unsigned getStagesForPhi(int Reg) {
+    std::pair<unsigned, bool> Stages = RegToStageDiff[Reg];
+    if (Stages.second)
+      return Stages.first;
+    return Stages.first - 1;
+  }
+
+  /// Return the instructions that are scheduled at the specified cycle.
+  std::deque<SUnit *> &getInstructions(int cycle) {
+    return ScheduledInstrs[cycle];
+  }
+
+  bool isValidSchedule(SwingSchedulerDAG *SSD);
+  void finalizeSchedule(SwingSchedulerDAG *SSD);
+  void orderDependence(SwingSchedulerDAG *SSD, SUnit *SU,
+                       std::deque<SUnit *> &Insts);
+  bool isLoopCarried(SwingSchedulerDAG *SSD, MachineInstr &Phi);
+  bool isLoopCarriedDefOfUse(SwingSchedulerDAG *SSD, MachineInstr *Def,
+                             MachineOperand &MO);
+  void print(raw_ostream &os) const;
+  void dump() const;
+};
+
+} // end namespace llvm
+
+#endif // LLVM_LIB_CODEGEN_MACHINEPIPELINER_H

llvm/trunk/lib/CodeGen/MachinePipeliner.cpp

 //===- MachinePipeliner.cpp - Machine Software Pipeliner Pass -------------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // An implementation of the Swing Modulo Scheduling (SMS) software pipeliner.
 //
-// Software pipelining (SWP) is an instruction scheduling technique for loops
-// that overlap loop iterations and exploits ILP via a compiler transformation.
-//
-// Swing Modulo Scheduling is an implementation of software pipelining
-// that generates schedules that are near optimal in terms of initiation
-// interval, register requirements, and stage count. See the papers:
-//
-// "Swing Modulo Scheduling: A Lifetime-Sensitive Approach", by J. Llosa,
-// A. Gonzalez, E. Ayguade, and M. Valero. In PACT '96 Proceedings of the 1996
-// Conference on Parallel Architectures and Compilation Techiniques.
-//
-// "Lifetime-Sensitive Modulo Scheduling in a Production Environment", by J.
-// Llosa, E. Ayguade, A. Gonzalez, M. Valero, and J. Eckhardt. In IEEE
-// Transactions on Computers, Vol. 50, No. 3, 2001.
-//
-// "An Implementation of Swing Modulo Scheduling With Extensions for
-// Superblocks", by T. Lattner, Master's Thesis, University of Illinois at
-// Urbana-Chambpain, 2005.
-//
-//
-// The SMS algorithm consists of three main steps after computing the minimal
-// initiation interval (MII).
-// 1) Analyze the dependence graph and compute information about each
-//    instruction in the graph.
-// 2) Order the nodes (instructions) by priority based upon the heuristics
-//    described in the algorithm.
-// 3) Attempt to schedule the nodes in the specified order using the MII.
-//
 // This SMS implementation is a target-independent back-end pass. When enabled,
 // the pass runs just prior to the register allocation pass, while the machine
 // IR is in SSA form. If software pipelining is successful, then the original
 // loop is replaced by the optimized loop. The optimized loop contains one or
 // more prolog blocks, the pipelined kernel, and one or more epilog blocks. If
 // the instructions cannot be scheduled in a given MII, we increase the MII by
 // one and try again.
 //

 #include "llvm/CodeGen/MachineDominators.h"
 #include "llvm/CodeGen/MachineFunction.h"
 #include "llvm/CodeGen/MachineFunctionPass.h"
 #include "llvm/CodeGen/MachineInstr.h"
 #include "llvm/CodeGen/MachineInstrBuilder.h"
 #include "llvm/CodeGen/MachineLoopInfo.h"
 #include "llvm/CodeGen/MachineMemOperand.h"
 #include "llvm/CodeGen/MachineOperand.h"
+#include "llvm/CodeGen/MachinePipeliner.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
-#include "llvm/CodeGen/RegisterClassInfo.h"
 #include "llvm/CodeGen/RegisterPressure.h"
 #include "llvm/CodeGen/ScheduleDAG.h"
-#include "llvm/CodeGen/ScheduleDAGInstrs.h"
 #include "llvm/CodeGen/ScheduleDAGMutation.h"
-#include "llvm/CodeGen/TargetInstrInfo.h"
 #include "llvm/CodeGen/TargetOpcodes.h"
 #include "llvm/CodeGen/TargetRegisterInfo.h"
 #include "llvm/CodeGen/TargetSubtargetInfo.h"
 #include "llvm/Config/llvm-config.h"
 #include "llvm/IR/Attributes.h"
 #include "llvm/IR/DebugLoc.h"
 #include "llvm/IR/Function.h"
 #include "llvm/MC/LaneBitmask.h"

 #ifndef NDEBUG
 static cl::opt<int> SwpLoopLimit("pipeliner-max", cl::Hidden, cl::init(-1));
 #endif
 
 static cl::opt<bool> SwpIgnoreRecMII("pipeliner-ignore-recmii",
                                      cl::ReallyHidden, cl::init(false),
                                      cl::ZeroOrMore, cl::desc("Ignore RecMII"));
 
+namespace llvm {
+
 // A command line option to enable the CopyToPhi DAG mutation.
-static cl::opt<bool>
+cl::opt<bool>
     SwpEnableCopyToPhi("pipeliner-enable-copytophi", cl::ReallyHidden,
                        cl::init(true), cl::ZeroOrMore,
                        cl::desc("Enable CopyToPhi DAG Mutation"));
 
-namespace {
-
-class NodeSet;
-class SMSchedule;
-
-/// The main class in the implementation of the target independent
-/// software pipeliner pass.
-class MachinePipeliner : public MachineFunctionPass {
-public:
-  MachineFunction *MF = nullptr;
-  const MachineLoopInfo *MLI = nullptr;
-  const MachineDominatorTree *MDT = nullptr;
-  const InstrItineraryData *InstrItins;
-  const TargetInstrInfo *TII = nullptr;
-  RegisterClassInfo RegClassInfo;
-
-#ifndef NDEBUG
-  static int NumTries;
-#endif
-
-  /// Cache the target analysis information about the loop.
-  struct LoopInfo {
-    MachineBasicBlock *TBB = nullptr;
-    MachineBasicBlock *FBB = nullptr;
-    SmallVector<MachineOperand, 4> BrCond;
-    MachineInstr *LoopInductionVar = nullptr;
-    MachineInstr *LoopCompare = nullptr;
-  };
-  LoopInfo LI;
-
-  static char ID;
-
-  MachinePipeliner() : MachineFunctionPass(ID) {
-    initializeMachinePipelinerPass(*PassRegistry::getPassRegistry());
-  }
-
-  bool runOnMachineFunction(MachineFunction &MF) override;
-
-  void getAnalysisUsage(AnalysisUsage &AU) const override {
-    AU.addRequired<AAResultsWrapperPass>();
-    AU.addPreserved<AAResultsWrapperPass>();
-    AU.addRequired<MachineLoopInfo>();
-    AU.addRequired<MachineDominatorTree>();
-    AU.addRequired<LiveIntervals>();
-    MachineFunctionPass::getAnalysisUsage(AU);
-  }
-
-private:
-  void preprocessPhiNodes(MachineBasicBlock &B);
-  bool canPipelineLoop(MachineLoop &L);
-  bool scheduleLoop(MachineLoop &L);
-  bool swingModuloScheduler(MachineLoop &L);
-};
-
-/// This class builds the dependence graph for the instructions in a loop,
-/// and attempts to schedule the instructions using the SMS algorithm.
-class SwingSchedulerDAG : public ScheduleDAGInstrs {
-  MachinePipeliner &Pass;
-  /// The minimum initiation interval between iterations for this schedule.
-  unsigned MII = 0;
-  /// Set to true if a valid pipelined schedule is found for the loop.
-  bool Scheduled = false;
-  MachineLoop &Loop;
-  LiveIntervals &LIS;
-  const RegisterClassInfo &RegClassInfo;
-
-  /// A toplogical ordering of the SUnits, which is needed for changing
-  /// dependences and iterating over the SUnits.
-  ScheduleDAGTopologicalSort Topo;
-
-  struct NodeInfo {
-    int ASAP = 0;
-    int ALAP = 0;
-    int ZeroLatencyDepth = 0;
-    int ZeroLatencyHeight = 0;
-
-    NodeInfo() = default;
-  };
-  /// Computed properties for each node in the graph.
-  std::vector<NodeInfo> ScheduleInfo;
-
-  enum OrderKind { BottomUp = 0, TopDown = 1 };
-  /// Computed node ordering for scheduling.
-  SetVector<SUnit *> NodeOrder;
-
-  using NodeSetType = SmallVector<NodeSet, 8>;
-  using ValueMapTy = DenseMap<unsigned, unsigned>;
-  using MBBVectorTy = SmallVectorImpl<MachineBasicBlock *>;
-  using InstrMapTy = DenseMap<MachineInstr *, MachineInstr *>;
-
-  /// Instructions to change when emitting the final schedule.
-  DenseMap<SUnit *, std::pair<unsigned, int64_t>> InstrChanges;
-
-  /// We may create a new instruction, so remember it because it
-  /// must be deleted when the pass is finished.
-  SmallPtrSet<MachineInstr *, 4> NewMIs;
-
-  /// Ordered list of DAG postprocessing steps.
-  std::vector<std::unique_ptr<ScheduleDAGMutation>> Mutations;
-
-  /// Helper class to implement Johnson's circuit finding algorithm.
-  class Circuits {
-    std::vector<SUnit> &SUnits;
-    SetVector<SUnit *> Stack;
-    BitVector Blocked;
-    SmallVector<SmallPtrSet<SUnit *, 4>, 10> B;
-    SmallVector<SmallVector<int, 4>, 16> AdjK;
-    // Node to Index from ScheduleDAGTopologicalSort
-    std::vector<int> *Node2Idx;
-    unsigned NumPaths;
-    static unsigned MaxPaths;
-
-  public:
-    Circuits(std::vector<SUnit> &SUs, ScheduleDAGTopologicalSort &Topo)
-        : SUnits(SUs), Blocked(SUs.size()), B(SUs.size()), AdjK(SUs.size()) {
-      Node2Idx = new std::vector<int>(SUs.size());
-      unsigned Idx = 0;
-      for (const auto &NodeNum : Topo)
-        Node2Idx->at(NodeNum) = Idx++;
-    }
-
-    ~Circuits() { delete Node2Idx; }
-
-    /// Reset the data structures used in the circuit algorithm.
-    void reset() {
-      Stack.clear();
-      Blocked.reset();
-      B.assign(SUnits.size(), SmallPtrSet<SUnit *, 4>());
-      NumPaths = 0;
-    }
-
-    void createAdjacencyStructure(SwingSchedulerDAG *DAG);
-    bool circuit(int V, int S, NodeSetType &NodeSets, bool HasBackedge = false);
-    void unblock(int U);
-  };
-
-  struct CopyToPhiMutation : public ScheduleDAGMutation {
-    void apply(ScheduleDAGInstrs *DAG) override;
-  };
-
-public:
-  SwingSchedulerDAG(MachinePipeliner &P, MachineLoop &L, LiveIntervals &lis,
-                    const RegisterClassInfo &rci)
-      : ScheduleDAGInstrs(*P.MF, P.MLI, false), Pass(P), Loop(L), LIS(lis),
-        RegClassInfo(rci), Topo(SUnits, &ExitSU) {
-    P.MF->getSubtarget().getSMSMutations(Mutations);
-    if (SwpEnableCopyToPhi)
-      Mutations.push_back(llvm::make_unique<CopyToPhiMutation>());
-  }
-
-  void schedule() override;
-  void finishBlock() override;
-
-  /// Return true if the loop kernel has been scheduled.
-  bool hasNewSchedule() { return Scheduled; }
-
-  /// Return the earliest time an instruction may be scheduled.
-  int getASAP(SUnit *Node) { return ScheduleInfo[Node->NodeNum].ASAP; }
-
-  /// Return the latest time an instruction my be scheduled.
-  int getALAP(SUnit *Node) { return ScheduleInfo[Node->NodeNum].ALAP; }
-
-  /// The mobility function, which the number of slots in which
-  /// an instruction may be scheduled.
-  int getMOV(SUnit *Node) { return getALAP(Node) - getASAP(Node); }
-
-  /// The depth, in the dependence graph, for a node.
-  unsigned getDepth(SUnit *Node) { return Node->getDepth(); }
-
-  /// The maximum unweighted length of a path from an arbitrary node to the
-  /// given node in which each edge has latency 0
-  int getZeroLatencyDepth(SUnit *Node) {
-    return ScheduleInfo[Node->NodeNum].ZeroLatencyDepth;
-  }
-
-  /// The height, in the dependence graph, for a node.
-  unsigned getHeight(SUnit *Node) { return Node->getHeight(); }
-
-  /// The maximum unweighted length of a path from the given node to an
-  /// arbitrary node in which each edge has latency 0
-  int getZeroLatencyHeight(SUnit *Node) {
-    return ScheduleInfo[Node->NodeNum].ZeroLatencyHeight;
-  }
-
-  /// Return true if the dependence is a back-edge in the data dependence graph.
-  /// Since the DAG doesn't contain cycles, we represent a cycle in the graph
-  /// using an anti dependence from a Phi to an instruction.
-  bool isBackedge(SUnit *Source, const SDep &Dep) {
-    if (Dep.getKind() != SDep::Anti)
-      return false;
-    return Source->getInstr()->isPHI() || Dep.getSUnit()->getInstr()->isPHI();
-  }
-
-  bool isLoopCarriedDep(SUnit *Source, const SDep &Dep, bool isSucc = true);
-
-  /// The distance function, which indicates that operation V of iteration I
-  /// depends on operations U of iteration I-distance.
-  unsigned getDistance(SUnit *U, SUnit *V, const SDep &Dep) {
-    // Instructions that feed a Phi have a distance of 1. Computing larger
-    // values for arrays requires data dependence information.
-    if (V->getInstr()->isPHI() && Dep.getKind() == SDep::Anti)
-      return 1;
-    return 0;
-  }
-
-  /// Set the Minimum Initiation Interval for this schedule attempt.
-  void setMII(unsigned mii) { MII = mii; }
-
-  void applyInstrChange(MachineInstr *MI, SMSchedule &Schedule);
-
-  void fixupRegisterOverlaps(std::deque<SUnit *> &Instrs);
-
-  /// Return the new base register that was stored away for the changed
-  /// instruction.
-  unsigned getInstrBaseReg(SUnit *SU) {
-    DenseMap<SUnit *, std::pair<unsigned, int64_t>>::iterator It =
-        InstrChanges.find(SU);
-    if (It != InstrChanges.end())
-      return It->second.first;
-    return 0;
-  }
-
-  void addMutation(std::unique_ptr<ScheduleDAGMutation> Mutation) {
-    Mutations.push_back(std::move(Mutation));
-  }
-
-  static bool classof(const ScheduleDAGInstrs *DAG) { return true; }
-
-private:
-  void addLoopCarriedDependences(AliasAnalysis *AA);
-  void updatePhiDependences();
-  void changeDependences();
-  unsigned calculateResMII();
-  unsigned calculateRecMII(NodeSetType &RecNodeSets);
-  void findCircuits(NodeSetType &NodeSets);
-  void fuseRecs(NodeSetType &NodeSets);
-  void removeDuplicateNodes(NodeSetType &NodeSets);
-  void computeNodeFunctions(NodeSetType &NodeSets);
-  void registerPressureFilter(NodeSetType &NodeSets);
-  void colocateNodeSets(NodeSetType &NodeSets);
-  void checkNodeSets(NodeSetType &NodeSets);
-  void groupRemainingNodes(NodeSetType &NodeSets);
-  void addConnectedNodes(SUnit *SU, NodeSet &NewSet,
-                         SetVector<SUnit *> &NodesAdded);
-  void computeNodeOrder(NodeSetType &NodeSets);
-  void checkValidNodeOrder(const NodeSetType &Circuits) const;
-  bool schedulePipeline(SMSchedule &Schedule);
-  void generatePipelinedLoop(SMSchedule &Schedule);
-  void generateProlog(SMSchedule &Schedule, unsigned LastStage,
-                      MachineBasicBlock *KernelBB, ValueMapTy *VRMap,
-                      MBBVectorTy &PrologBBs);
-  void generateEpilog(SMSchedule &Schedule, unsigned LastStage,
-                      MachineBasicBlock *KernelBB, ValueMapTy *VRMap,
-                      MBBVectorTy &EpilogBBs, MBBVectorTy &PrologBBs);
-  void generateExistingPhis(MachineBasicBlock *NewBB, MachineBasicBlock *BB1,
-                            MachineBasicBlock *BB2, MachineBasicBlock *KernelBB,
-                            SMSchedule &Schedule, ValueMapTy *VRMap,
-                            InstrMapTy &InstrMap, unsigned LastStageNum,
-                            unsigned CurStageNum, bool IsLast);
-  void generatePhis(MachineBasicBlock *NewBB, MachineBasicBlock *BB1,
-                    MachineBasicBlock *BB2, MachineBasicBlock *KernelBB,
-                    SMSchedule &Schedule, ValueMapTy *VRMap,
-                    InstrMapTy &InstrMap, unsigned LastStageNum,
-                    unsigned CurStageNum, bool IsLast);
-  void removeDeadInstructions(MachineBasicBlock *KernelBB,
-                              MBBVectorTy &EpilogBBs);
-  void splitLifetimes(MachineBasicBlock *KernelBB, MBBVectorTy &EpilogBBs,
-                      SMSchedule &Schedule);
-  void addBranches(MBBVectorTy &PrologBBs, MachineBasicBlock *KernelBB,
-                   MBBVectorTy &EpilogBBs, SMSchedule &Schedule,
-                   ValueMapTy *VRMap);
-  bool computeDelta(MachineInstr &MI, unsigned &Delta);
-  void updateMemOperands(MachineInstr &NewMI, MachineInstr &OldMI,
-                         unsigned Num);
-  MachineInstr *cloneInstr(MachineInstr *OldMI, unsigned CurStageNum,
-                           unsigned InstStageNum);
-  MachineInstr *cloneAndChangeInstr(MachineInstr *OldMI, unsigned CurStageNum,
-                                    unsigned InstStageNum,
-                                    SMSchedule &Schedule);
-  void updateInstruction(MachineInstr *NewMI, bool LastDef,
-                         unsigned CurStageNum, unsigned InstrStageNum,
-                         SMSchedule &Schedule, ValueMapTy *VRMap);
-  MachineInstr *findDefInLoop(unsigned Reg);
-  unsigned getPrevMapVal(unsigned StageNum, unsigned PhiStage, unsigned LoopVal,
-                         unsigned LoopStage, ValueMapTy *VRMap,
-                         MachineBasicBlock *BB);
-  void rewritePhiValues(MachineBasicBlock *NewBB, unsigned StageNum,
-                        SMSchedule &Schedule, ValueMapTy *VRMap,
-                        InstrMapTy &InstrMap);
-  void rewriteScheduledInstr(MachineBasicBlock *BB, SMSchedule &Schedule,
-                             InstrMapTy &InstrMap, unsigned CurStageNum,
-                             unsigned PhiNum, MachineInstr *Phi,
-                             unsigned OldReg, unsigned NewReg,
-                             unsigned PrevReg = 0);
-  bool canUseLastOffsetValue(MachineInstr *MI, unsigned &BasePos,
-                             unsigned &OffsetPos, unsigned &NewBase,
-                             int64_t &NewOffset);
-  void postprocessDAG();
-};
-
-/// A NodeSet contains a set of SUnit DAG nodes with additional information
-/// that assigns a priority to the set.
-class NodeSet {
-  SetVector<SUnit *> Nodes;
-  bool HasRecurrence = false;
-  unsigned RecMII = 0;
-  int MaxMOV = 0;
-  unsigned MaxDepth = 0;
-  unsigned Colocate = 0;
-  SUnit *ExceedPressure = nullptr;
-  unsigned Latency = 0;
-
-public:
-  using iterator = SetVector<SUnit *>::const_iterator;
-
-  NodeSet() = default;
-  NodeSet(iterator S, iterator E) : Nodes(S, E), HasRecurrence(true) {
-    Latency = 0;
-    for (unsigned i = 0, e = Nodes.size(); i < e; ++i)
-      for (const SDep &Succ : Nodes[i]->Succs)
-        if (Nodes.count(Succ.getSUnit()))
-          Latency += Succ.getLatency();
-  }
-
-  bool insert(SUnit *SU) { return Nodes.insert(SU); }
-
-  void insert(iterator S, iterator E) { Nodes.insert(S, E); }
-
-  template <typename UnaryPredicate> bool remove_if(UnaryPredicate P) {
-    return Nodes.remove_if(P);
-  }
-
-  unsigned count(SUnit *SU) const { return Nodes.count(SU); }
-
-  bool hasRecurrence() { return HasRecurrence; };
-
-  unsigned size() const { return Nodes.size(); }
-
-  bool empty() const { return Nodes.empty(); }
-
-  SUnit *getNode(unsigned i) const { return Nodes[i]; };
-
-  void setRecMII(unsigned mii) { RecMII = mii; };
-
-  void setColocate(unsigned c) { Colocate = c; };
-
-  void setExceedPressure(SUnit *SU) { ExceedPressure = SU; }
-
-  bool isExceedSU(SUnit *SU) { return ExceedPressure == SU; }
-
-  int compareRecMII(NodeSet &RHS) { return RecMII - RHS.RecMII; }
-
-  int getRecMII() { return RecMII; }
-
-  /// Summarize node functions for the entire node set.
-  void computeNodeSetInfo(SwingSchedulerDAG *SSD) {
-    for (SUnit *SU : *this) {
-      MaxMOV = std::max(MaxMOV, SSD->getMOV(SU));
-      MaxDepth = std::max(MaxDepth, SSD->getDepth(SU));
-    }
-  }
-
-  unsigned getLatency() { return Latency; }
-
-  unsigned getMaxDepth() { return MaxDepth; }
-
-  void clear() {
-    Nodes.clear();
-    RecMII = 0;
-    HasRecurrence = false;
-    MaxMOV = 0;
-    MaxDepth = 0;
-    Colocate = 0;
-    ExceedPressure = nullptr;
-  }
-
-  operator SetVector<SUnit *> &() { return Nodes; }
-
-  /// Sort the node sets by importance. First, rank them by recurrence MII,
-  /// then by mobility (least mobile done first), and finally by depth.
-  /// Each node set may contain a colocate value which is used as the first
-  /// tie breaker, if it's set.
-  bool operator>(const NodeSet &RHS) const {
-    if (RecMII == RHS.RecMII) {
-      if (Colocate != 0 && RHS.Colocate != 0 && Colocate != RHS.Colocate)
-        return Colocate < RHS.Colocate;
-      if (MaxMOV == RHS.MaxMOV)
-        return MaxDepth > RHS.MaxDepth;
-      return MaxMOV < RHS.MaxMOV;
-    }
-    return RecMII > RHS.RecMII;
-  }
-
-  bool operator==(const NodeSet &RHS) const {
-    return RecMII == RHS.RecMII && MaxMOV == RHS.MaxMOV &&
-           MaxDepth == RHS.MaxDepth;
-  }
-
-  bool operator!=(const NodeSet &RHS) const { return !operator==(RHS); }
-
-  iterator begin() { return Nodes.begin(); }
-  iterator end() { return Nodes.end(); }
-
-  void print(raw_ostream &os) const {
-    os << "Num nodes " << size() << " rec " << RecMII << " mov " << MaxMOV
-       << " depth " << MaxDepth << " col " << Colocate << "\n";
-    for (const auto &I : Nodes)
-      os << "   SU(" << I->NodeNum << ") " << *(I->getInstr());
-    os << "\n";
-  }
-
-#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
-  LLVM_DUMP_METHOD void dump() const { print(dbgs()); }
-#endif
-};
-
-/// This class represents the scheduled code.  The main data structure is a
-/// map from scheduled cycle to instructions.  During scheduling, the
-/// data structure explicitly represents all stages/iterations.   When
-/// the algorithm finshes, the schedule is collapsed into a single stage,
-/// which represents instructions from different loop iterations.
-///
-/// The SMS algorithm allows negative values for cycles, so the first cycle
-/// in the schedule is the smallest cycle value.
-class SMSchedule {
-private:
-  /// Map from execution cycle to instructions.
-  DenseMap<int, std::deque<SUnit *>> ScheduledInstrs;
-
-  /// Map from instruction to execution cycle.
-  std::map<SUnit *, int> InstrToCycle;
-
-  /// Map for each register and the max difference between its uses and def.
-  /// The first element in the pair is the max difference in stages. The
-  /// second is true if the register defines a Phi value and loop value is
-  /// scheduled before the Phi.
-  std::map<unsigned, std::pair<unsigned, bool>> RegToStageDiff;
-
-  /// Keep track of the first cycle value in the schedule.  It starts
-  /// as zero, but the algorithm allows negative values.
-  int FirstCycle = 0;
-
-  /// Keep track of the last cycle value in the schedule.
-  int LastCycle = 0;
-
-  /// The initiation interval (II) for the schedule.
-  int InitiationInterval = 0;
-
-  /// Target machine information.
-  const TargetSubtargetInfo &ST;
-
-  /// Virtual register information.
-  MachineRegisterInfo &MRI;
-
-  std::unique_ptr<DFAPacketizer> Resources;
-
-public:
-  SMSchedule(MachineFunction *mf)
-      : ST(mf->getSubtarget()), MRI(mf->getRegInfo()),
-        Resources(ST.getInstrInfo()->CreateTargetScheduleState(ST)) {}
-
-  void reset() {
-    ScheduledInstrs.clear();
-    InstrToCycle.clear();
-    RegToStageDiff.clear();
-    FirstCycle = 0;
-    LastCycle = 0;
-    InitiationInterval = 0;
-  }
-
-  /// Set the initiation interval for this schedule.
-  void setInitiationInterval(int ii) { InitiationInterval = ii; }
-
-  /// Return the first cycle in the completed schedule.  This
-  /// can be a negative value.
-  int getFirstCycle() const { return FirstCycle; }
-
-  /// Return the last cycle in the finalized schedule.
-  int getFinalCycle() const { return FirstCycle + InitiationInterval - 1; }
-
-  /// Return the cycle of the earliest scheduled instruction in the dependence
-  /// chain.
-  int earliestCycleInChain(const SDep &Dep);
-
-  /// Return the cycle of the latest scheduled instruction in the dependence
-  /// chain.
-  int latestCycleInChain(const SDep &Dep);
-
-  void computeStart(SUnit *SU, int *MaxEarlyStart, int *MinLateStart,
-                    int *MinEnd, int *MaxStart, int II, SwingSchedulerDAG *DAG);
-  bool insert(SUnit *SU, int StartCycle, int EndCycle, int II);
-
-  /// Iterators for the cycle to instruction map.
-  using sched_iterator = DenseMap<int, std::deque<SUnit *>>::iterator;
-  using const_sched_iterator =
-      DenseMap<int, std::deque<SUnit *>>::const_iterator;
-
-  /// Return true if the instruction is scheduled at the specified stage.
-  bool isScheduledAtStage(SUnit *SU, unsigned StageNum) {
-    return (stageScheduled(SU) == (int)StageNum);
-  }
-
-  /// Return the stage for a scheduled instruction.  Return -1 if
-  /// the instruction has not been scheduled.
-  int stageScheduled(SUnit *SU) const {
-    std::map<SUnit *, int>::const_iterator it = InstrToCycle.find(SU);
-    if (it == InstrToCycle.end())
-      return -1;
-    return (it->second - FirstCycle) / InitiationInterval;
-  }
-
-  /// Return the cycle for a scheduled instruction. This function normalizes
-  /// the first cycle to be 0.
-  unsigned cycleScheduled(SUnit *SU) const {
-    std::map<SUnit *, int>::const_iterator it = InstrToCycle.find(SU);
-    assert(it != InstrToCycle.end() && "Instruction hasn't been scheduled.");
-    return (it->second - FirstCycle) % InitiationInterval;
-  }
-
-  /// Return the maximum stage count needed for this schedule.
-  unsigned getMaxStageCount() {
-    return (LastCycle - FirstCycle) / InitiationInterval;
-  }
-
-  /// Return the max. number of stages/iterations that can occur between a
-  /// register definition and its uses.
-  unsigned getStagesForReg(int Reg, unsigned CurStage) {
-    std::pair<unsigned, bool> Stages = RegToStageDiff[Reg];
-    if (CurStage > getMaxStageCount() && Stages.first == 0 && Stages.second)
-      return 1;
-    return Stages.first;
-  }
-
-  /// The number of stages for a Phi is a little different than other
-  /// instructions. The minimum value computed in RegToStageDiff is 1
-  /// because we assume the Phi is needed for at least 1 iteration.
-  /// This is not the case if the loop value is scheduled prior to the
-  /// Phi in the same stage.  This function returns the number of stages
-  /// or iterations needed between the Phi definition and any uses.
-  unsigned getStagesForPhi(int Reg) {
-    std::pair<unsigned, bool> Stages = RegToStageDiff[Reg];
-    if (Stages.second)
-      return Stages.first;
-    return Stages.first - 1;
-  }
-
-  /// Return the instructions that are scheduled at the specified cycle.
-  std::deque<SUnit *> &getInstructions(int cycle) {
-    return ScheduledInstrs[cycle];
-  }
-
-  bool isValidSchedule(SwingSchedulerDAG *SSD);
-  void finalizeSchedule(SwingSchedulerDAG *SSD);
-  void orderDependence(SwingSchedulerDAG *SSD, SUnit *SU,
-                       std::deque<SUnit *> &Insts);
-  bool isLoopCarried(SwingSchedulerDAG *SSD, MachineInstr &Phi);
-  bool isLoopCarriedDefOfUse(SwingSchedulerDAG *SSD, MachineInstr *Def,
-                             MachineOperand &MO);
-  void print(raw_ostream &os) const;
-  void dump() const;
-};
-
-} // end anonymous namespace
+} // end namespace llvm
 
 unsigned SwingSchedulerDAG::Circuits::MaxPaths = 5;
 char MachinePipeliner::ID = 0;
 #ifndef NDEBUG
 int MachinePipeliner::NumTries = 0;
 #endif
 char &llvm::MachinePipelinerID = MachinePipeliner::ID;