[PIR] A sequentialization pass for parallel regions

[jdoerfert]

Summary

This pass will lower all parallel regions to sequential IR. It replaces
PIR instruction by unconditional branch instructions as follows:

• fork is replaced with a branch to the forked block.
• halt is replaced with a branch to the sibling continuation block.
• join is replaced with a branch to its destination block.

This approach:

1. Does not need to scan the function if there are no parallel regions.
2. Emits llvm.mem.parallel_loop_access metadata for parallel loops that have been sequentialized.
3. Preserves the DominatorTree, LoopInfo and ParallelRegionInfo.
   
   This commit also includes general infrastructure needed for PIR passes as well as a library (libPIR) for the passes to live in.

[jdoerfert]

Update to match new D29250

[jdoerfert]

lib/Transforms/PIR/SequentializePIR.cpp

40

TODO: We can use the parallel region info pass to avoid a linear walk of the function here.

[jdoerfert]

Utilize the ParallelRegionInfo pass and emit parallel loop metadata

include/llvm/InitializePasses.h

 void initializeCodeGen(PassRegistry&);
 
 /// Initialize all passes linked into the GlobalISel library.
 void initializeGlobalISel(PassRegistry &Registry);
 
 /// Initialize all passes linked into the CodeGen library.
 void initializeTarget(PassRegistry&);
 
+/// Initialize all passes linked into the PIR library.
+void initializePIROpts(PassRegistry&);
+
 void initializeAAEvalLegacyPassPass(PassRegistry&);
 void initializeAAResultsWrapperPassPass(PassRegistry &);
 void initializeADCELegacyPassPass(PassRegistry&);
 void initializeAddDiscriminatorsLegacyPassPass(PassRegistry&);
 void initializeAddressSanitizerModulePass(PassRegistry&);
 void initializeAddressSanitizerPass(PassRegistry&);
 void initializeAliasSetPrinterPass(PassRegistry&);
 void initializeAlignmentFromAssumptionsPass(PassRegistry&);

 void initializeSROALegacyPassPass(PassRegistry&);
 void initializeSafeStackPass(PassRegistry&);
 void initializeSampleProfileLoaderLegacyPassPass(PassRegistry&);
 void initializeSanitizerCoverageModulePass(PassRegistry&);
 void initializeScalarEvolutionWrapperPassPass(PassRegistry&);
 void initializeScalarizerPass(PassRegistry&);
 void initializeScopedNoAliasAAWrapperPassPass(PassRegistry&);
 void initializeSeparateConstOffsetFromGEPPass(PassRegistry &);
+void initializeSequentializePIRPass(PassRegistry&);
 void initializeShadowStackGCLoweringPass(PassRegistry&);
 void initializeShrinkWrapPass(PassRegistry &);
 void initializeSimpleInlinerPass(PassRegistry&);
 void initializeSingleLoopExtractorPass(PassRegistry&);
 void initializeSinkingLegacyPassPass(PassRegistry&);
 void initializeSjLjEHPreparePass(PassRegistry&);
 void initializeSlotIndexesPass(PassRegistry&);
 void initializeSpeculativeExecutionLegacyPassPass(PassRegistry&);

lib/Passes/LLVMBuild.txt

 ;   http://llvm.org/docs/LLVMBuild.html
 ;
 ;===------------------------------------------------------------------------===;
 
 [component_0]
 type = Library
 name = Passes
 parent = Libraries
-required_libraries = Analysis CodeGen Core IPO InstCombine Scalar Support TransformUtils Vectorize Instrumentation
+required_libraries = Analysis CodeGen Core IPO InstCombine Scalar Support TransformUtils Vectorize Instrumentation PIR

lib/Transforms/CMakeLists.txt

 add_subdirectory(Utils)
 add_subdirectory(Instrumentation)
 add_subdirectory(InstCombine)
 add_subdirectory(Scalar)
 add_subdirectory(IPO)
 add_subdirectory(Vectorize)
 add_subdirectory(Hello)
+add_subdirectory(PIR)
 add_subdirectory(ObjCARC)
 add_subdirectory(Coroutines)

lib/Transforms/LLVMBuild.txt

 ;
 ; For more information on the LLVMBuild system, please see:
 ;
 ;   http://llvm.org/docs/LLVMBuild.html
 ;
 ;===------------------------------------------------------------------------===;
 
 [common]
-subdirectories = Coroutines IPO InstCombine Instrumentation Scalar Utils Vectorize ObjCARC
+subdirectories = Coroutines IPO InstCombine Instrumentation Scalar Utils Vectorize ObjCARC PIR
 
 [component_0]
 type = Group
 name = Transforms
 parent = Libraries

lib/Transforms/PIR/CMakeLists.txt

+add_llvm_library(LLVMPIR
+  SequentializePIR.cpp
+  PIR.cpp
+
+  ADDITIONAL_HEADER_DIRS
+  ${LLVM_MAIN_INCLUDE_DIR}/llvm/Transforms
+
+  DEPENDS
+  intrinsics_gen
+ )

lib/Transforms/PIR/LLVMBuild.txt

-;===- ./lib/Passes/LLVMBuild.txt -------------------------------*- Conf -*--===;
+;===- ./lib/Transforms/PIR/LLVMBuild.txt -----------------------*- Conf -*--===;
 ;
 ;                     The LLVM Compiler Infrastructure
 ;
 ; This file is distributed under the University of Illinois Open Source
 ; License. See LICENSE.TXT for details.
 ;
 ;===------------------------------------------------------------------------===;
 ;
 ; This is an LLVMBuild description file for the components in this subdirectory.
 ;
 ; For more information on the LLVMBuild system, please see:
 ;
 ;   http://llvm.org/docs/LLVMBuild.html
 ;
 ;===------------------------------------------------------------------------===;
 
 [component_0]
 type = Library
-name = Passes
-parent = Libraries
-required_libraries = Analysis CodeGen Core IPO InstCombine Scalar Support TransformUtils Vectorize Instrumentation
+name = PIR
+parent = Transforms
+required_libraries = Analysis BitWriter Core InstCombine IRReader Linker Object ProfileData Scalar Support TransformUtils Vectorize Instrumentation

lib/Transforms/PIR/PIR.cpp

+//===-- PIR.cpp -----------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/InitializePasses.h"
+
+using namespace llvm;
+
+void llvm::initializePIROpts(PassRegistry &Registry) {
+  initializeSequentializePIRPass(Registry);
+}

lib/Transforms/PIR/SequentializePIR.cpp

+//===-- PIR/SequentializePIR.cpp - Sequentialize parallel regions ---------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This pass will lower all parallel regions to sequential IR.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/IR/BasicBlock.h"
+#include "llvm/IR/Function.h"
+#include "llvm/IR/Instructions.h"
+#include "llvm/Pass.h"
+#include "llvm/Support/raw_ostream.h"
+
+using namespace llvm;
+
+namespace {
+
+/// This pass will lower all parallel regions to sequential IR. It replaces
+/// PIR instruction by unconditional branch instructions as follows:
+///   - fork is replaced with a branch to the forked block.
+///   - halt is replaced with a branch to the sibling continuation block.
+///   - join is replaced with a branch to its destination block.
+struct SequentializePIR : public FunctionPass {
+  static char ID;
+
+  SequentializePIR() : FunctionPass(ID) {
+    initializeSequentializePIRPass(*PassRegistry::getPassRegistry());
+  }
+
+  bool runOnFunction(Function &F) override {
+    bool Changed = false;
+
+    for (auto BB = F.begin(); BB != F.end(); ++BB) {
+      auto I = BB->getTerminator();
+
+      if (ForkInst *FI = dyn_cast<ForkInst>(I)) {
+        BranchInst::Create(FI->getForked(), I);
+        I->eraseFromParent();
+        Changed = true;
+      } else if (HaltInst *HI = dyn_cast<HaltInst>(I)) {
+        BranchInst::Create(HI->getForkContinue(), I);
+        I->eraseFromParent();
+        Changed = true;
+      } else if (JoinInst *JI = dyn_cast<JoinInst>(I)) {
+        BranchInst::Create(JI->getContinue(), I);
+        I->eraseFromParent();
+        Changed = true;
+      }
+    }
+
+    return Changed;
+  }
+};
+}
+
+char SequentializePIR::ID = 0;
+INITIALIZE_PASS(SequentializePIR, "sequentialize-pir",
+                "Lower parallel regions to sequential IR", false, false)

test/PIR/lower.ll

+; RUN: opt -sequentialize-pir -S < %s | FileCheck %s
+
+declare void @foo();
+
+define void @simple() {
+entry:
+  fork label %forked, label %cont
+; CHECK:      entry
+; CHECK-NEXT: br label %forked
+
+forked:
+  call void @foo()
+  halt label %cont
+; CHECK:      forked
+; CHECK-NEXT: call void @foo
+; CHECK-NEXT: br label %cont
+
+cont:
+  call void @foo()
+  join label %join
+; CHECK:      cont
+; CHECK-NEXT: call void @foo
+; CHECK-NEXT: br label %join
+
+join:
+  ret void
+}
+
+
+define void @nested() {
+entry:
+  fork label %forked.outer, label %cont.outer
+; CHECK:      entry
+; CHECK-NEXT: br label %forked.outer
+
+forked.outer:
+  call void @foo()
+  fork label %forked.inner, label %cont.inner
+; CHECK:      forked.outer
+; CHECK-NEXT: call void @foo
+; CHECK-NEXT: br label %forked.inner
+
+forked.inner:
+  call void @foo()
+  br label %forked.inner.body
+; CHECK:      forked.inner
+; CHECK-NEXT: call void @foo
+; CHECK-NEXT: br label %forked.inner.body
+
+forked.inner.body:
+  call void @foo()
+  halt label %cont.inner
+; CHECK:      forked.inner.body
+; CHECK-NEXT: call void @foo
+; CHECK-NEXT: br label %cont.inner
+
+cont.inner:
+  call void @foo()
+  join label %forked.outer.end
+; CHECK:      cont.inner
+; CHECK-NEXT: call void @foo
+; CHECK-NEXT: br label %forked.outer.end
+
+forked.outer.end:
+  halt label %cont.outer
+; CHECK:      forked.outer.end
+; CHECK-NEXT: br label %cont.outer
+
+cont.outer:
+  call void @foo()
+  join label %join
+; CHECK:      cont
+; CHECK-NEXT: call void @foo
+; CHECK-NEXT: br label %join
+
+join:
+  ret void
+}

tools/opt/CMakeLists.txt

 set(LLVM_LINK_COMPONENTS
   ${LLVM_TARGETS_TO_BUILD}
   Analysis
   BitWriter
   CodeGen
   Core
   Coroutines
   IPO
+  PIR
   IRReader
   InstCombine
   Instrumentation
   MC
   ObjCARCOpts
   ScalarOpts
   Support
   Target

tools/opt/opt.cpp

int main(int argc, char **argv) {
   initializeObjCARCOpts(Registry);
   initializeVectorization(Registry);
   initializeIPO(Registry);
   initializeAnalysis(Registry);
   initializeTransformUtils(Registry);
   initializeInstCombine(Registry);
   initializeInstrumentation(Registry);
   initializeTarget(Registry);
+  initializePIROpts(Registry);
   // For codegen passes, only passes that do IR to IR transformation are
   // supported.
   initializeCodeGenPreparePass(Registry);
   initializeAtomicExpandPass(Registry);
   initializeRewriteSymbolsLegacyPassPass(Registry);
   initializeWinEHPreparePass(Registry);
   initializeDwarfEHPreparePass(Registry);
   initializeSafeStackPass(Registry);