[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/Analysis/ParallelRegionInfo.h

public:
   ///
   ///{
   iterator begin() { return TopLevelParallelRegions.begin(); }
   iterator end() { return TopLevelParallelRegions.end(); }
   const_iterator begin() const { return TopLevelParallelRegions.begin(); }
   const_iterator end() const { return TopLevelParallelRegions.end(); }
   ///}
 
+  /// Fill @p Container with all parallel regions (not only top level).
+  void getAllParallelRegions(ParallelRegionVectorTy &Container) const;
+
   /// Return the parallel region that makes @p L a parallel loop, if any.
   ///
   /// A parallel loop is a loop that does fork (parts of) its body to a new
   /// task which are joined only after the loop. It is also ensured that
   /// everything that is not forked but part of the loop does not cause
   /// side-effects. These instructions usually compute the exit condition
   /// and the new values for the induction variable(s).
   ///

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/Analysis/ParallelRegionInfo.cpp

for (ParallelRegion *PR : TopLevelParallelRegions) {
     bool Success = PR->visit(Visitor, true);
     (void)Success;
     assert(Success && "Expeded walk over parallel region to visit all blocks!");
   }
 
   return BB2PTMap;
 }
 
+void ParallelRegionInfo::getAllParallelRegions(
+    ParallelRegionVectorTy &Container) const {
+
+  Container.append(begin(), end());
+  for (unsigned i = 0; i < Container.size(); i++) {
+    ParallelRegion *PR = Container[i];
+
+    for (const auto &It : PR->getSubRegions())
+      Container.push_back(It.getSecond());
+  }
+}
+
 ParallelRegion *ParallelRegionInfo::getParallelLoopRegion(const Loop &L,
                                         const DominatorTree &DT) const {
   if (empty())
     return nullptr;
 
   SmallVector<ParallelRegion *, 8> ParallelRegions;
   ParallelRegions.append(begin(), end());
 

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/Analysis/ParallelRegionInfo.h"
+#include "llvm/Analysis/LoopInfo.h"
+#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.
+///
+/// If a parallel loop is encountered we annotate it as parallel using metadata.
+struct SequentializePIR : public FunctionPass {
+  static char ID;
+
+  SequentializePIR() : FunctionPass(ID) {
+    initializeSequentializePIRPass(*PassRegistry::getPassRegistry());
+  }
+
+  void getAnalysisUsage(AnalysisUsage &AU) const override {
+    AU.addRequired<DominatorTreeWrapperPass>();
+    AU.addRequired<ParallelRegionInfoPass>();
+    AU.addRequired<LoopInfoWrapperPass>();
+
+    AU.addPreserved<DominatorTreeWrapperPass>();
+    AU.addPreserved<ParallelRegionInfoPass>();
+    AU.addPreserved<LoopInfoWrapperPass>();
+    AU.setPreservesCFG();
+  }
+
+  ParallelTask::VisitorTy createParallelTaskAnnotator(MDNode *LoopID) {
+    assert(LoopID);
+
+    // Helper function that annotates all read/write instructions in a basic
+    // block with parallel memory metadata referring to LoopID.
+    ParallelTask::VisitorTy Annotator = [LoopID](BasicBlock &BB,
+                                                 const ParallelTask &) {
+      for (Instruction &I : BB) {
+        if (!I.mayReadOrWriteMemory())
+          continue;
+
+        MDNode *LoopIdMD =
+            I.getMetadata(LLVMContext::MD_mem_parallel_loop_access);
+        if (!LoopIdMD)
+          LoopIdMD = MDNode::get(I.getContext(), {LoopID});
+        else
+          LoopIdMD = MDNode::concatenate(LoopIdMD, LoopID);
+        I.setMetadata(LLVMContext::MD_mem_parallel_loop_access, LoopIdMD);
+      }
+
+      return true;
+    };
+
+    return Annotator;
+  }
+
+  bool runOnFunction(Function &F) override {
+    ParallelRegionInfo &PRI =
+        getAnalysis<ParallelRegionInfoPass>().getParallelRegionInfo();
+
+    // Exit early if there is nothing to do.
+    if (PRI.empty())
+      return false;
+
+    LoopInfo &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
+    const DominatorTree &DT =
+        getAnalysis<DominatorTreeWrapperPass>().getDomTree();
+
+    ParallelRegionInfo::ParallelRegionVectorTy ParallelRegions;
+    PRI.getAllParallelRegions(ParallelRegions);
+
+    for (ParallelRegion *PR : ParallelRegions) {
+      Loop *L = LI.getLoopFor(PR->getFork().getParent());
+      bool AnnotateAsParallel =
+          (L && !L->isAnnotatedParallel() && PR->isParallelLoopRegion(*L, DT));
+
+      // Replace the fork, join and halt instructions by branches. Note that
+      // this does not change the dominator tree or loop info.
+      ForkInst &Fork = PR->getFork();
+      BranchInst::Create(Fork.getForkedBB(), &Fork);
+      Fork.eraseFromParent();
+
+      ParallelTask &ForkedTask = PR->getForkedTask();
+      for (TerminatorInst *TI : ForkedTask.getHaltsOrJoints()) {
+        assert(isa<HaltInst>(TI) && "Forked task was not terminated by a halt!");
+        BranchInst::Create(TI->getSuccessor(0), TI);
+        TI->eraseFromParent();
+      }
+
+      ParallelTask &ContinuationTask = PR->getContinuationTask();
+      for (TerminatorInst *TI : ContinuationTask.getHaltsOrJoints()) {
+        assert(isa<JoinInst>(TI) &&
+               "Continuation task was not terminated by a join!");
+        BranchInst::Create(TI->getSuccessor(0), TI);
+        TI->eraseFromParent();
+      }
+
+      if (!AnnotateAsParallel)
+        continue;
+
+      // Get or create a loop id for the current loop.
+      MDNode *LoopID = L->getLoopID();
+      if (!LoopID) {
+        LoopID = MDNode::get(F.getContext(), {nullptr});
+        LoopID->replaceOperandWith(0, LoopID);
+        L->setLoopID(LoopID);
+      }
+
+      // Annotate all blocks in the forked task with
+      // llvm.mem.parallel_loop_access metadata. Note that no other side-effects
+      // are allowed in the loop outside the forked task.
+      ParallelTask::VisitorTy Annotator = createParallelTaskAnnotator(LoopID);
+      ForkedTask.visit(Annotator);
+
+      // Verify that (for simplified loops) the annotation is recognized.
+      assert(!L->isLoopSimplifyForm() || L->isAnnotatedParallel());
+    }
+
+    // Update the parallel region info.
+    PRI.clear();
+    assert(PRI.empty());
+
+    return true;
+  }
+};
+}
+
+char SequentializePIR::ID = 0;
+
+INITIALIZE_PASS_BEGIN(SequentializePIR, "sequentialize-pir",
+                      "Lower parallel regions to sequential IR", false, false)
+INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
+INITIALIZE_PASS_DEPENDENCY(ParallelRegionInfoPass)
+INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
+INITIALIZE_PASS_END(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, %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, %cont.outer
+; CHECK:      entry
+; CHECK-NEXT: br label %forked.outer
+
+forked.outer:
+  call void @foo()
+  fork label %forked.inner, %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
+}

test/PIR/parallel_loops.ll

+; RUN: opt -sequentialize-pir -S < %s | FileCheck %s
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+; void f0(int *A, int N) {
+;   int i = 0;
+;   #pragma parallel
+;   do {
+;     A[i] += 1;
+;   } while (i++ < N);
+; }
+;
+; Function Attrs: noinline nounwind uwtable
+define void @f0(i32* %A, i32 %N) #0 {
+entry:
+  %tmp = sext i32 %N to i64
+  br label %do.body
+
+do.body:                                          ; preds = %do.cond, %entry
+  %indvars.iv = phi i64 [ %indvars.iv.next, %do.cond ], [ 0, %entry ]
+  br label %pr.begin
+
+pr.begin:
+  fork label %forked, %do.cond
+
+forked:
+  %arrayidx = getelementptr inbounds i32, i32* %A, i64 %indvars.iv
+  %tmp1 = load i32, i32* %arrayidx, align 4
+  %add = add nsw i32 %tmp1, 1
+  store i32 %add, i32* %arrayidx, align 4
+  halt label %do.cond
+
+; CHECK: forked:
+; CHECK:   %tmp1 = load i32, i32* %arrayidx, align 4, !llvm.mem.parallel_loop_access ![[PID0:[0-9]*]]
+; CHECK:   store i32 %add, i32* %arrayidx, align 4, !llvm.mem.parallel_loop_access ![[PID0]]
+; CHECK:   br label %do.cond
+
+do.cond:                                          ; preds = %do.body
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  %cmp = icmp slt i64 %indvars.iv, %tmp
+  br i1 %cmp, label %do.body, label %do.end
+
+; CHECK: do.cond:
+; CHECK:  br i1 %cmp, label %do.body, label %do.end, !llvm.loop ![[L0:[0-9]*]]
+
+do.end:                                           ; preds = %do.cond
+  join label %return
+
+return:
+  ret void
+}
+
+; void f1(int *A, int N) {
+;   int i = N;
+;   #pragma parallel
+;   do {
+;     A[i] += 1;
+;   } while (i-- >= 0);
+; }
+;
+; Function Attrs: noinline nounwind uwtable
+define void @f1(i32* %A, i32 %N) #0 {
+entry:
+  %tmp = sext i32 %N to i64
+  br label %do.body
+
+do.body:                                          ; preds = %do.cond, %entry
+  %indvars.iv = phi i64 [ %indvars.iv.next, %do.cond ], [ %tmp, %entry ]
+  br label %pr.begin
+
+pr.begin:
+  fork label %forked, %do.cond
+
+forked:
+  %arrayidx = getelementptr inbounds i32, i32* %A, i64 %indvars.iv
+  %tmp1 = load i32, i32* %arrayidx, align 4
+  %add = add nsw i32 %tmp1, 1
+  store i32 %add, i32* %arrayidx, align 4
+  halt label %do.cond
+
+; CHECK: forked:
+; CHECK:   %tmp1 = load i32, i32* %arrayidx, align 4, !llvm.mem.parallel_loop_access ![[PID1:[0-9]*]]
+; CHECK:   store i32 %add, i32* %arrayidx, align 4, !llvm.mem.parallel_loop_access ![[PID1]]
+; CHECK:   br label %do.cond
+
+do.cond:                                          ; preds = %do.body
+  %indvars.iv.next = add nsw i64 %indvars.iv, -1
+  %cmp = icmp sgt i64 %indvars.iv, -1
+
+; CHECK: do.cond:
+; CHECK:  br i1 %cmp, label %do.body, label %do.end, !llvm.loop ![[L1:[0-9]*]]
+
+ br i1 %cmp, label %do.body, label %do.end
+
+do.end:                                           ; preds = %do.cond
+  join label %return
+
+return:
+  ret void
+}
+
+; void f2(int *A, int N) {
+;   int i = 0;
+;   #pragma parallel
+;   do {
+;     A[i] += 1;
+;   } while (i++ < N);
+; }
+;
+; Function Attrs: noinline nounwind uwtable
+define void @f2(i32* %A, i32 %N) #0 {
+entry:
+  %tmp = sext i32 %N to i64
+  br label %do.body
+
+do.body:                                          ; preds = %do.cond, %entry
+  %indvars.iv = phi i64 [ %indvars.iv.next, %do.cond ], [ 0, %entry ]
+  br label %pr.begin
+
+pr.begin:                                         ; preds = %do.body
+  fork label %forked, %do.cond
+
+forked:                                           ; preds = %pr.begin
+  %arrayidx = getelementptr inbounds i32, i32* %A, i64 %indvars.iv
+  %tmp1 = load i32, i32* %arrayidx, align 4, !llvm.mem.parallel_loop_access !0
+  %add = add nsw i32 %tmp1, 1
+  store i32 %add, i32* %arrayidx, align 4, !llvm.mem.parallel_loop_access !0
+  halt label %do.cond
+
+; CHECK: forked:
+; CHECK:   %tmp1 = load i32, i32* %arrayidx, align 4, !llvm.mem.parallel_loop_access ![[PID2:[0-9]*]]
+; CHECK:   store i32 %add, i32* %arrayidx, align 4, !llvm.mem.parallel_loop_access ![[PID2]]
+; CHECK:   br label %do.cond
+
+do.cond:                                          ; preds = %forked
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  %cmp = icmp slt i64 %indvars.iv, %tmp
+  br i1 %cmp, label %do.body, label %do.end, !llvm.loop !1
+
+; CHECK: do.cond:
+; CHECK:  br i1 %cmp, label %do.body, label %do.end, !llvm.loop ![[L2:[0-9]*]]
+
+do.end:                                           ; preds = %do.cond
+  join label %return
+
+return:                                           ; preds = %do.end
+  ret void
+}
+
+; void f3(int *A, int N) {
+;   int i = N;
+;   #pragma parallel
+;   do {
+;     A[i] += 1;
+;   } while (i-- >= 0);
+; }
+;
+; CHECK: @f3
+;
+; Function Attrs: noinline nounwind uwtable
+define void @f3(i32* %A, i32 %N) #0 {
+entry:
+  %tmp = sext i32 %N to i64
+  br label %do.body
+
+do.body:                                          ; preds = %do.cond, %entry
+  %indvars.iv = phi i64 [ %indvars.iv.next, %do.cond ], [ %tmp, %entry ]
+  br label %pr.begin
+
+pr.begin:                                         ; preds = %do.body
+  fork label %forked, %do.cond
+
+; CHECK:      pr.begin:
+; CHECK-NEXT:   br label %forked
+
+forked:                                           ; preds = %pr.begin
+  %arrayidx = getelementptr inbounds i32, i32* %A, i64 %indvars.iv
+  %tmp1 = load i32, i32* %arrayidx, align 4, !llvm.mem.parallel_loop_access !2
+  %add = add nsw i32 %tmp1, 1
+  store i32 %add, i32* %arrayidx, align 4, !llvm.mem.parallel_loop_access !2
+  halt label %do.cond
+
+; CHECK: forked:
+; CHECK:   %tmp1 = load i32, i32* %arrayidx, align 4, !llvm.mem.parallel_loop_access ![[PID3:[0-9]*]]
+; CHECK:   store i32 %add, i32* %arrayidx, align 4, !llvm.mem.parallel_loop_access ![[PID3]]
+; CHECK:   br label %do.cond
+
+do.cond:                                          ; preds = %forked
+  %indvars.iv.next = add nsw i64 %indvars.iv, -1
+  %cmp = icmp sgt i64 %indvars.iv, -1
+  br i1 %cmp, label %do.body, label %do.end, !llvm.loop !3
+
+; CHECK: do.cond:
+; CHECK:  br i1 %cmp, label %do.body, label %do.end, !llvm.loop ![[L3:[0-9]*]]
+
+do.end:                                           ; preds = %do.cond
+  join label %return
+
+return:                                           ; preds = %do.end
+  ret void
+}
+
+; void f4(int *A, int N) {
+;   int i = N;
+;   do {
+;     #pragma parallel
+;     do {
+;       A[i] += 1;
+;     } while (i-- >= 0);
+;   } while (0);
+; }
+;
+; Function Attrs: noinline nounwind uwtable
+;
+; CHECK: @f4
+define void @f4(i32* %A, i32 %N) #0 {
+entry:
+  %tmp = sext i32 %N to i64
+  br label %outer.do.body
+
+outer.do.body:
+  br label %do.body
+
+do.body:                                          ; preds = %do.cond, %entry
+  %indvars.iv = phi i64 [ %indvars.iv.next, %do.cond ], [ %tmp, %outer.do.body ]
+  br label %pr.begin
+
+pr.begin:                                         ; preds = %do.body
+  fork label %forked, %do.cond
+
+forked:                                           ; preds = %pr.begin
+  %arrayidx = getelementptr inbounds i32, i32* %A, i64 %indvars.iv
+  %tmp1 = load i32, i32* %arrayidx, align 4, !llvm.mem.parallel_loop_access !4
+  %add = add nsw i32 %tmp1, 1
+  store i32 %add, i32* %arrayidx, align 4, !llvm.mem.parallel_loop_access !4
+  halt label %do.cond
+
+; CHECK:  %tmp1 = load i32, i32* %arrayidx, align 4, !llvm.mem.parallel_loop_access ![[PID4:[0-9]*]]
+; CHECK:  store i32 %add, i32* %arrayidx, align 4, !llvm.mem.parallel_loop_access ![[PID4]]
+
+do.cond:                                          ; preds = %forked
+  %indvars.iv.next = add nsw i64 %indvars.iv, -1
+  %cmp = icmp sgt i64 %indvars.iv, -1
+  br i1 %cmp, label %do.body, label %do.end
+
+; CHECK: do.cond
+; CHECK:   br i1 %cmp, label %do.body, label %do.end, !llvm.loop ![[LInner4:[0-9]*]]
+
+do.end:                                           ; preds = %do.cond
+  join label %outer.do.cond
+
+outer.do.cond:
+  br i1 false, label %outer.do.body, label %outer.do.end, !llvm.loop !5
+
+; CHECK: outer.do.cond
+; CHECK:  br i1 false, label %outer.do.body, label %outer.do.end, !llvm.loop ![[LOuter4:[0-9]*]]
+
+outer.do.end:
+  br label %return
+
+return:                                           ; preds = %do.end
+  ret void
+}
+
+!0 = !{!1}
+!1 = distinct !{!1}
+!2 = !{!3}
+!3 = distinct !{!3}
+!4 = !{!5}
+!5 = distinct !{!5}
+
+; CHECK:  ![[PID0]] = !{![[L0]]}
+; CHECK:  ![[L0]] = distinct !{![[L0]]}
+
+; CHECK:  ![[PID1]] = !{![[L1]]}
+; CHECK:  ![[L1]] = distinct !{![[L1]]}
+
+; CHECK:  ![[PID2]] = !{![[L2]]}
+; CHECK:  ![[L2]] = distinct !{![[L2]]}
+
+; CHECK:  ![[PID3]] = !{![[L3]]}
+; CHECK:  ![[L3]] = distinct !{![[L3]]}
+
+; CHECK:  ![[PID4]] = !{![[LOuter4]], ![[LInner4]]}
+; CHECK:  ![[LOuter4]] = distinct !{![[LOuter4]]}
+; CHECK:  ![[LInner4]] = distinct !{![[LInner4]]}
+
+attributes #0 = { noinline nounwind uwtable "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "less-precise-fpmad"="false" "no-frame-pointer-elim"="true" "no-frame-pointer-elim-non-leaf" "no-infs-fp-math"="false" "no-jump-tables"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+fxsr,+mmx,+sse,+sse2,+x87" "unsafe-fp-math"="false" "use-soft-float"="false" }

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);