[PIR] Add fork, join and halt instructions

[jdoerfert]

Summary

With this commit, low-level fork-join parallelism can be natively
expressed in LLVM IR. To this end, three new terminators are added:
fork, join, and halt.

A brief description of the syntax and semantics of the each terminator
follows:

(1) fork label %task.block, label %continuation.block
A fork terminator marks the beginning of a (possibly nested) parallel
region. Conceptually the %task.block and the %continuation.block
represent the two tasks to be executed in parallel. We denote the two
successors of a fork instruction as siblings.

(2) halt label %continuation.block
A halt marks the end of a forked task. The sibling continuation block of
the tasks starting block is the operand of the halt terminator.

(3) join label %sequential.block
A join specifies a synchronization point, or barrier, for a parallel
region. Once a join terminator is reached by a thread, execution stops
in that thread until all tasks spawned by this thread finish their work,
thus reach their respective halt instruction.

For more details, please refer to the following resources:
[0] PIR Wiki: https://github.com/Parallel-IR/llvm-pir/wiki.

Here, you will find the RFC document for the first stage of our proposal.

[1] Tapir: http://wsmoses.com/tapir.pdf.
[2] PIR (white paper): http://compilers.cs.uni-saarland.de/people/doerfert/parallelcfg.pdf

Disclaimer:

This patch, the PIR RFC, the PIR wiki, etc. are a joint effort by Tao B.
Schardl (MIT), Charles E. Leiserson (MIT), Kareem Ergawy (Saarland
University), Simon Moll (Saarland University) and Johannes Doerfert
(Saarland University). However, we are grateful for all the ideas and
feedback that came from various people in the community.

[deadalnix]

I'm not sure who's the proper person to review that, but that wouldn't be me. Did you discussed adding these instruction with someone ? If so, who is that ? maybe you want to add these people as reviewer.

[jdoerfert]

In D29250#659678, @deadalnix wrote:

I'm not sure who's the proper person to review that, but that wouldn't be me. Did you discussed adding these instruction with someone ? If so, who is that ? maybe you want to add these people as reviewer.

A herald rule added you automatically, sorry for that. I was not going to add any specific reviewer for the time beeing but just let people that read the RFC take a look (and comment if they like).

[majnemer]

Is there another patch which updates the langref? The semantics are most important of all.
Also, how do you discover where a region begins and ends?

[jdoerfert]

In D29250#659722, @majnemer wrote:

Is there another patch which updates the langref? The semantics are most important of all.

Good points, thanks. So far there is no lang ref patch but we'll work on it now. However, the RFC email does define a semantics and how the regions have to look like.

Also, how do you discover where a region begins and ends?

At this point a parallel region starts with a fork and spreads till all paths from there end in a join. Detecting the regions can be therefor done in a single sweep that looks for the fork (, halt) and join instructions.

[jdoerfert]

Fix smaller issues and minor renaming

[jdoerfert]

In D29250#659722, @majnemer wrote:

Is there another patch which updates the langref? The semantics are most important of all.

Please see https://reviews.llvm.org/D30353 for a draft documentation and semantics.

Also, how do you discover where a region begins and ends?

Please see https://reviews.llvm.org/D30354 for a draft parallel region info implementation that discovers and maintains parallel region information.

include/llvm-c/Core.h

typedef enum {
 
   /* Exception Handling Operators */
   LLVMResume         = 58,
   LLVMLandingPad     = 59,
   LLVMCleanupRet     = 61,
   LLVMCatchRet       = 62,
   LLVMCatchPad       = 63,
   LLVMCleanupPad     = 64,
-  LLVMCatchSwitch    = 65
+  LLVMCatchSwitch    = 65,
+
+  /* Parallel fork-join operators */
+  LLVMFork           = 66,
+  LLVMHalt           = 67,
+  LLVMJoin           = 68
 } LLVMOpcode;
 
 typedef enum {
   LLVMVoidTypeKind,        /**< type with no size */
   LLVMHalfTypeKind,        /**< 16 bit floating point type */
   LLVMFloatTypeKind,       /**< 32 bit floating point type */
   LLVMDoubleTypeKind,      /**< 64 bit floating point type */
   LLVMX86_FP80TypeKind,    /**< 80 bit floating point type (X87) */

include/llvm/Bitcode/LLVMBitCodes.h

enum FunctionCodes {
   FUNC_CODE_INST_CATCHRET = 49,    // CATCHRET: [val,bb#]
   FUNC_CODE_INST_CATCHPAD = 50,    // CATCHPAD: [bb#,bb#,num,args...]
   FUNC_CODE_INST_CLEANUPPAD = 51,  // CLEANUPPAD: [num,args...]
   FUNC_CODE_INST_CATCHSWITCH =
       52, // CATCHSWITCH: [num,args...] or [num,args...,bb]
   // 53 is unused.
   // 54 is unused.
   FUNC_CODE_OPERAND_BUNDLE = 55, // OPERAND_BUNDLE: [tag#, value...]
+
+  FUNC_CODE_INST_FORK = 56, // FORK: [bb#, bb#]
+  FUNC_CODE_INST_HALT = 57, // HALT: [bb#]
+  FUNC_CODE_INST_JOIN = 58  // JOIN: [bb#]
 };
 
 enum UseListCodes {
   USELIST_CODE_DEFAULT = 1, // DEFAULT: [index..., value-id]
   USELIST_CODE_BB = 2       // BB: [index..., bb-id]
 };
 
 enum AttributeKindCodes {

include/llvm/CodeGen/GlobalISel/IRTranslator.h

bool translateCleanupRet(const User &U, MachineIRBuilder &MIRBuilder) {
     return false;
   }
   bool translateCatchRet(const User &U, MachineIRBuilder &MIRBuilder) {
     return false;
   }
   bool translateCatchSwitch(const User &U, MachineIRBuilder &MIRBuilder) {
     return false;
   }
+  bool translateFork(const User &U, MachineIRBuilder &MIRBuilder) {
+    return false;
+  }
+  bool translateJoin(const User &U, MachineIRBuilder &MIRBuilder) {
+    return false;
+  }
+  bool translateHalt(const User &U, MachineIRBuilder &MIRBuilder) {
+    return false;
+  }
   bool translateFence(const User &U, MachineIRBuilder &MIRBuilder) {
     return false;
   }
   bool translateAtomicCmpXchg(const User &U, MachineIRBuilder &MIRBuilder) {
     return false;
   }
   bool translateAtomicRMW(const User &U, MachineIRBuilder &MIRBuilder) {
     return false;

include/llvm/IR/InstVisitor.h

#include "llvm/IR/Instruction.def"
   RetTy visitBranchInst(BranchInst &I)            { DELEGATE(TerminatorInst);}
   RetTy visitSwitchInst(SwitchInst &I)            { DELEGATE(TerminatorInst);}
   RetTy visitIndirectBrInst(IndirectBrInst &I)    { DELEGATE(TerminatorInst);}
   RetTy visitResumeInst(ResumeInst &I)            { DELEGATE(TerminatorInst);}
   RetTy visitUnreachableInst(UnreachableInst &I)  { DELEGATE(TerminatorInst);}
   RetTy visitCleanupReturnInst(CleanupReturnInst &I) { DELEGATE(TerminatorInst);}
   RetTy visitCatchReturnInst(CatchReturnInst &I)  { DELEGATE(TerminatorInst); }
   RetTy visitCatchSwitchInst(CatchSwitchInst &I)  { DELEGATE(TerminatorInst);}
+  RetTy visitForkInst(ForkInst &I)                { DELEGATE(TerminatorInst); }
+  RetTy visitHaltInst(HaltInst &I)                { DELEGATE(TerminatorInst); }
+  RetTy visitJoinInst(JoinInst &I)                { DELEGATE(TerminatorInst); }
   RetTy visitICmpInst(ICmpInst &I)                { DELEGATE(CmpInst);}
   RetTy visitFCmpInst(FCmpInst &I)                { DELEGATE(CmpInst);}
   RetTy visitAllocaInst(AllocaInst &I)            { DELEGATE(UnaryInstruction);}
   RetTy visitLoadInst(LoadInst     &I)            { DELEGATE(UnaryInstruction);}
   RetTy visitStoreInst(StoreInst   &I)            { DELEGATE(Instruction);}
   RetTy visitAtomicCmpXchgInst(AtomicCmpXchgInst &I) { DELEGATE(Instruction);}
   RetTy visitAtomicRMWInst(AtomicRMWInst &I)      { DELEGATE(Instruction);}
   RetTy visitFenceInst(FenceInst   &I)            { DELEGATE(Instruction);}

include/llvm/IR/Instruction.def

 HANDLE_TERM_INST  ( 3, Switch        , SwitchInst)
 HANDLE_TERM_INST  ( 4, IndirectBr    , IndirectBrInst)
 HANDLE_TERM_INST  ( 5, Invoke        , InvokeInst)
 HANDLE_TERM_INST  ( 6, Resume        , ResumeInst)
 HANDLE_TERM_INST  ( 7, Unreachable   , UnreachableInst)
 HANDLE_TERM_INST  ( 8, CleanupRet    , CleanupReturnInst)
 HANDLE_TERM_INST  ( 9, CatchRet      , CatchReturnInst)
 HANDLE_TERM_INST  (10, CatchSwitch   , CatchSwitchInst)
-  LAST_TERM_INST  (10)
+HANDLE_TERM_INST  (11, Fork          , ForkInst)
+HANDLE_TERM_INST  (12, Halt          , HaltInst)
+HANDLE_TERM_INST  (13, Join          , JoinInst)
+  LAST_TERM_INST  (13)
 
 // Standard binary operators...
- FIRST_BINARY_INST(11)
-HANDLE_BINARY_INST(11, Add  , BinaryOperator)
-HANDLE_BINARY_INST(12, FAdd , BinaryOperator)
-HANDLE_BINARY_INST(13, Sub  , BinaryOperator)
-HANDLE_BINARY_INST(14, FSub , BinaryOperator)
-HANDLE_BINARY_INST(15, Mul  , BinaryOperator)
-HANDLE_BINARY_INST(16, FMul , BinaryOperator)
-HANDLE_BINARY_INST(17, UDiv , BinaryOperator)
-HANDLE_BINARY_INST(18, SDiv , BinaryOperator)
-HANDLE_BINARY_INST(19, FDiv , BinaryOperator)
-HANDLE_BINARY_INST(20, URem , BinaryOperator)
-HANDLE_BINARY_INST(21, SRem , BinaryOperator)
-HANDLE_BINARY_INST(22, FRem , BinaryOperator)
+ FIRST_BINARY_INST(14)
+HANDLE_BINARY_INST(14, Add  , BinaryOperator)
+HANDLE_BINARY_INST(15, FAdd , BinaryOperator)
+HANDLE_BINARY_INST(16, Sub  , BinaryOperator)
+HANDLE_BINARY_INST(17, FSub , BinaryOperator)
+HANDLE_BINARY_INST(18, Mul  , BinaryOperator)
+HANDLE_BINARY_INST(19, FMul , BinaryOperator)
+HANDLE_BINARY_INST(20, UDiv , BinaryOperator)
+HANDLE_BINARY_INST(21, SDiv , BinaryOperator)
+HANDLE_BINARY_INST(22, FDiv , BinaryOperator)
+HANDLE_BINARY_INST(23, URem , BinaryOperator)
+HANDLE_BINARY_INST(24, SRem , BinaryOperator)
+HANDLE_BINARY_INST(25, FRem , BinaryOperator)
 
 // Logical operators (integer operands)
-HANDLE_BINARY_INST(23, Shl  , BinaryOperator) // Shift left  (logical)
-HANDLE_BINARY_INST(24, LShr , BinaryOperator) // Shift right (logical)
-HANDLE_BINARY_INST(25, AShr , BinaryOperator) // Shift right (arithmetic)
-HANDLE_BINARY_INST(26, And  , BinaryOperator)
-HANDLE_BINARY_INST(27, Or   , BinaryOperator)
-HANDLE_BINARY_INST(28, Xor  , BinaryOperator)
-  LAST_BINARY_INST(28)
+HANDLE_BINARY_INST(26, Shl  , BinaryOperator) // Shift left  (logical)
+HANDLE_BINARY_INST(27, LShr , BinaryOperator) // Shift right (logical)
+HANDLE_BINARY_INST(28, AShr , BinaryOperator) // Shift right (arithmetic)
+HANDLE_BINARY_INST(29, And  , BinaryOperator)
+HANDLE_BINARY_INST(30, Or   , BinaryOperator)
+HANDLE_BINARY_INST(31, Xor  , BinaryOperator)
+  LAST_BINARY_INST(31)
 
 // Memory operators...
- FIRST_MEMORY_INST(29)
-HANDLE_MEMORY_INST(29, Alloca, AllocaInst)  // Stack management
-HANDLE_MEMORY_INST(30, Load  , LoadInst  )  // Memory manipulation instrs
-HANDLE_MEMORY_INST(31, Store , StoreInst )
-HANDLE_MEMORY_INST(32, GetElementPtr, GetElementPtrInst)
-HANDLE_MEMORY_INST(33, Fence , FenceInst )
-HANDLE_MEMORY_INST(34, AtomicCmpXchg , AtomicCmpXchgInst )
-HANDLE_MEMORY_INST(35, AtomicRMW , AtomicRMWInst )
-  LAST_MEMORY_INST(35)
+ FIRST_MEMORY_INST(32)
+HANDLE_MEMORY_INST(32, Alloca, AllocaInst)  // Stack management
+HANDLE_MEMORY_INST(33, Load  , LoadInst  )  // Memory manipulation instrs
+HANDLE_MEMORY_INST(34, Store , StoreInst )
+HANDLE_MEMORY_INST(35, GetElementPtr, GetElementPtrInst)
+HANDLE_MEMORY_INST(36, Fence , FenceInst )
+HANDLE_MEMORY_INST(37, AtomicCmpXchg , AtomicCmpXchgInst )
+HANDLE_MEMORY_INST(38, AtomicRMW , AtomicRMWInst )
+  LAST_MEMORY_INST(38)
 
 // Cast operators ...
 // NOTE: The order matters here because CastInst::isEliminableCastPair
 // NOTE: (see Instructions.cpp) encodes a table based on this ordering.
- FIRST_CAST_INST(36)
-HANDLE_CAST_INST(36, Trunc   , TruncInst   )  // Truncate integers
-HANDLE_CAST_INST(37, ZExt    , ZExtInst    )  // Zero extend integers
-HANDLE_CAST_INST(38, SExt    , SExtInst    )  // Sign extend integers
-HANDLE_CAST_INST(39, FPToUI  , FPToUIInst  )  // floating point -> UInt
-HANDLE_CAST_INST(40, FPToSI  , FPToSIInst  )  // floating point -> SInt
-HANDLE_CAST_INST(41, UIToFP  , UIToFPInst  )  // UInt -> floating point
-HANDLE_CAST_INST(42, SIToFP  , SIToFPInst  )  // SInt -> floating point
-HANDLE_CAST_INST(43, FPTrunc , FPTruncInst )  // Truncate floating point
-HANDLE_CAST_INST(44, FPExt   , FPExtInst   )  // Extend floating point
-HANDLE_CAST_INST(45, PtrToInt, PtrToIntInst)  // Pointer -> Integer
-HANDLE_CAST_INST(46, IntToPtr, IntToPtrInst)  // Integer -> Pointer
-HANDLE_CAST_INST(47, BitCast , BitCastInst )  // Type cast
-HANDLE_CAST_INST(48, AddrSpaceCast, AddrSpaceCastInst)  // addrspace cast
-  LAST_CAST_INST(48)
-
- FIRST_FUNCLETPAD_INST(49)
-HANDLE_FUNCLETPAD_INST(49, CleanupPad, CleanupPadInst)
-HANDLE_FUNCLETPAD_INST(50, CatchPad  , CatchPadInst)
-  LAST_FUNCLETPAD_INST(50)
+ FIRST_CAST_INST(39)
+HANDLE_CAST_INST(39, Trunc   , TruncInst   )  // Truncate integers
+HANDLE_CAST_INST(40, ZExt    , ZExtInst    )  // Zero extend integers
+HANDLE_CAST_INST(41, SExt    , SExtInst    )  // Sign extend integers
+HANDLE_CAST_INST(42, FPToUI  , FPToUIInst  )  // floating point -> UInt
+HANDLE_CAST_INST(43, FPToSI  , FPToSIInst  )  // floating point -> SInt
+HANDLE_CAST_INST(44, UIToFP  , UIToFPInst  )  // UInt -> floating point
+HANDLE_CAST_INST(45, SIToFP  , SIToFPInst  )  // SInt -> floating point
+HANDLE_CAST_INST(46, FPTrunc , FPTruncInst )  // Truncate floating point
+HANDLE_CAST_INST(47, FPExt   , FPExtInst   )  // Extend floating point
+HANDLE_CAST_INST(48, PtrToInt, PtrToIntInst)  // Pointer -> Integer
+HANDLE_CAST_INST(49, IntToPtr, IntToPtrInst)  // Integer -> Pointer
+HANDLE_CAST_INST(50, BitCast , BitCastInst )  // Type cast
+HANDLE_CAST_INST(51, AddrSpaceCast, AddrSpaceCastInst)  // addrspace cast
+  LAST_CAST_INST(51)
+
+ FIRST_FUNCLETPAD_INST(52)
+HANDLE_FUNCLETPAD_INST(52, CleanupPad, CleanupPadInst)
+HANDLE_FUNCLETPAD_INST(53, CatchPad  , CatchPadInst)
+  LAST_FUNCLETPAD_INST(53)
 
 // Other operators...
- FIRST_OTHER_INST(51)
-HANDLE_OTHER_INST(51, ICmp   , ICmpInst   )  // Integer comparison instruction
-HANDLE_OTHER_INST(52, FCmp   , FCmpInst   )  // Floating point comparison instr.
-HANDLE_OTHER_INST(53, PHI    , PHINode    )  // PHI node instruction
-HANDLE_OTHER_INST(54, Call   , CallInst   )  // Call a function
-HANDLE_OTHER_INST(55, Select , SelectInst )  // select instruction
-HANDLE_OTHER_INST(56, UserOp1, Instruction)  // May be used internally in a pass
-HANDLE_OTHER_INST(57, UserOp2, Instruction)  // Internal to passes only
-HANDLE_OTHER_INST(58, VAArg  , VAArgInst  )  // vaarg instruction
-HANDLE_OTHER_INST(59, ExtractElement, ExtractElementInst)// extract from vector
-HANDLE_OTHER_INST(60, InsertElement, InsertElementInst)  // insert into vector
-HANDLE_OTHER_INST(61, ShuffleVector, ShuffleVectorInst)  // shuffle two vectors.
-HANDLE_OTHER_INST(62, ExtractValue, ExtractValueInst)// extract from aggregate
-HANDLE_OTHER_INST(63, InsertValue, InsertValueInst)  // insert into aggregate
-HANDLE_OTHER_INST(64, LandingPad, LandingPadInst)  // Landing pad instruction.
-  LAST_OTHER_INST(64)
+ FIRST_OTHER_INST(54)
+HANDLE_OTHER_INST(54, ICmp   , ICmpInst   )  // Integer comparison instruction
+HANDLE_OTHER_INST(55, FCmp   , FCmpInst   )  // Floating point comparison instr.
+HANDLE_OTHER_INST(56, PHI    , PHINode    )  // PHI node instruction
+HANDLE_OTHER_INST(57, Call   , CallInst   )  // Call a function
+HANDLE_OTHER_INST(58, Select , SelectInst )  // select instruction
+HANDLE_OTHER_INST(59, UserOp1, Instruction)  // May be used internally in a pass
+HANDLE_OTHER_INST(60, UserOp2, Instruction)  // Internal to passes only
+HANDLE_OTHER_INST(61, VAArg  , VAArgInst  )  // vaarg instruction
+HANDLE_OTHER_INST(62, ExtractElement, ExtractElementInst)// extract from vector
+HANDLE_OTHER_INST(63, InsertElement, InsertElementInst)  // insert into vector
+HANDLE_OTHER_INST(64, ShuffleVector, ShuffleVectorInst)  // shuffle two vectors.
+HANDLE_OTHER_INST(65, ExtractValue, ExtractValueInst)// extract from aggregate
+HANDLE_OTHER_INST(66, InsertValue, InsertValueInst)  // insert into aggregate
+HANDLE_OTHER_INST(67, LandingPad, LandingPadInst)  // Landing pad instruction.
+  LAST_OTHER_INST(67)
 
 #undef  FIRST_TERM_INST
 #undef HANDLE_TERM_INST
 #undef   LAST_TERM_INST
 
 #undef  FIRST_BINARY_INST
 #undef HANDLE_BINARY_INST
 #undef   LAST_BINARY_INST

include/llvm/IR/Instructions.h

 
 private:
   BasicBlock *getSuccessorV(unsigned idx) const override;
   unsigned getNumSuccessorsV() const override;
   void setSuccessorV(unsigned idx, BasicBlock *B) override;
 };
 
 //===----------------------------------------------------------------------===//
+//                                 ForkInst Class
+//===----------------------------------------------------------------------===//
+
+//===---------------------------------------------------------------------------
+/// This class represents a fork terminator instruction
+  class ForkInst : public TerminatorInst {
+    /// Ops list - The operand are ordered: forked, continue
+    ForkInst(const ForkInst &FI);
+    void AssertOK();
+    // ForkInst constructors (where {F, C} are blocks):
+    // ForkInst(BB *F, BB *C)          - 'fork D, C'
+    // ForkInst(BB *F, BB *C, Inst *I) - 'fork D, C', insert before
+    // ForkInst(BB *F, BB *C, BB *I)   - 'fork D, C', insert at end
+    ForkInst(BasicBlock *Forked, BasicBlock *Continue,
+             Instruction *InsertBefore = nullptr);
+    ForkInst(BasicBlock *Forked, BasicBlock *Continue,
+             BasicBlock *InsertAtEnd);
+
+  protected:
+    // Note: Instruction needs to be friend here to call cloneImpl
+    friend class Instruction;
+    ForkInst *cloneImpl() const;
+
+  public:
+    static ForkInst *Create(BasicBlock *Forked, BasicBlock *Continue,
+                            Instruction *InsertBefore = nullptr) {
+      return new(2) ForkInst(Forked, Continue, InsertBefore);
+    }
+    static ForkInst *Create(BasicBlock *Forked, BasicBlock *Continue,
+                            BasicBlock *InsertAtEnd) {
+      return new(2) ForkInst(Forked, Continue, InsertAtEnd);
+    }
+
+    /// Transparently provide more efficient getOperand methods.
+    DECLARE_TRANSPARENT_OPERAND_ACCESSORS(Value);
+
+    unsigned getNumSuccessors() const { return 2; }
+
+    BasicBlock *getSuccessor(unsigned i) const {
+      assert(i < 2 && "Successor # out of range for fork!");
+      return cast_or_null<BasicBlock>((&Op<0>() + i)->get());
+    }
+
+    void setSuccessor(unsigned idx, BasicBlock *NewSucc) {
+      assert(idx < 2 && "Successor # out of range for fork!");
+      *(&Op<0>() + idx) = (Value*)NewSucc;
+    }
+
+    /// Swap the successors of this fork instruction.
+    ///
+    /// Swaps the successors of the fork instruction. This also swaps any
+    /// branch weight metadata associated with the instruction so that it
+    /// continues to map correctly to each operand.
+    void swapSuccessors();
+
+    // Methods for support type inquiry through isa, cast, and dyn_cast:
+    static inline bool classof(const Instruction *I) {
+      return (I->getOpcode() == Instruction::Fork);
+    }
+    static inline bool classof(const Value *V) {
+      return isa<Instruction>(V) && classof(cast<Instruction>(V));
+    }
+
+    inline BasicBlock* getForkedBB() const { return getSuccessor(0); }
+    inline BasicBlock* getContinuationBB() const { return getSuccessor(1); }
+  private:
+    BasicBlock *getSuccessorV(unsigned idx) const override;
+    unsigned getNumSuccessorsV() const override;
+    void setSuccessorV(unsigned idx, BasicBlock *B) override;
+  };
+
+  template <>
+  struct OperandTraits<ForkInst>
+      : public FixedNumOperandTraits<ForkInst, 2> {};
+
+  DEFINE_TRANSPARENT_OPERAND_ACCESSORS(ForkInst, Value)
+
+  //===----------------------------------------------------------------------===//
+  //                                 HaltInst Class
+  //===----------------------------------------------------------------------===//
+
+  //===---------------------------------------------------------------------------
+  /// HaltInst - Halt Instruction.
+  class HaltInst : public TerminatorInst {
+    HaltInst(const HaltInst &HI);
+    void AssertOK();
+    // HaltInst constructors (where F is a block):
+    // HaltInst(BB *F)
+    // HaltInst(BB *F, Inst *I) - insert before I
+    // HaltInst(BB *F, BB *I)   - insert at end
+    explicit HaltInst(LLVMContext &C, BasicBlock *ForkContinue,
+                      Instruction *InsertBefore = nullptr);
+    HaltInst(LLVMContext &C, BasicBlock *ForkContinue,
+             BasicBlock *InsertAtEnd);
+  protected:
+    // Note: Instruction needs to be friend here to call cloneImpl.
+    friend class Instruction;
+    HaltInst *cloneImpl() const;
+
+  public:
+    static HaltInst *Create(LLVMContext &C, BasicBlock *ForkContinue,
+                            Instruction *InsertBefore = nullptr) {
+      return new(1) HaltInst(C, ForkContinue, InsertBefore);
+    }
+    static HaltInst *Create(LLVMContext &C, BasicBlock *ForkContinue,
+                            BasicBlock *InsertAtEnd) {
+      return new(1) HaltInst(C, ForkContinue, InsertAtEnd);
+    }
+
+    /// Transparently provide more efficient getOperand methods.
+    DECLARE_TRANSPARENT_OPERAND_ACCESSORS(Value);
+
+    unsigned getNumSuccessors() const { return 1; }
+
+    BasicBlock *getSuccessor(unsigned i) const {
+      assert(i == 0 && "Successor # out of range for halt!");
+      return cast_or_null<BasicBlock>((&Op<0>())->get());
+    }
+
+    void setSuccessor(unsigned idx, BasicBlock *NewSucc) {
+      assert(idx == 0 && "Successor # out of range for halt!");
+      *(&Op<0>()) = (Value*)NewSucc;
+    }
+
+    BasicBlock *getContinuationBB() const {
+      return cast_or_null<BasicBlock>((&Op<0>())->get());
+    }
+
+    // Methods for support type inquiry through isa, cast, and dyn_cast:
+    static inline bool classof(const Instruction *I) {
+      return (I->getOpcode() == Instruction::Halt);
+    }
+    static inline bool classof(const Value *V) {
+      return isa<Instruction>(V) && classof(cast<Instruction>(V));
+    }
+
+  private:
+    BasicBlock *getSuccessorV(unsigned idx) const override;
+    unsigned getNumSuccessorsV() const override;
+    void setSuccessorV(unsigned idx, BasicBlock *B) override;
+ };
+
+  template<>
+  struct OperandTraits<HaltInst> : public FixedNumOperandTraits<HaltInst, 1> {};
+
+  DEFINE_TRANSPARENT_OPERAND_ACCESSORS(HaltInst, Value)
+
+  ///===----------------------------------------------------------------------===//
+  //                                 JoinInst Class
+  //===----------------------------------------------------------------------===//
+
+  //===---------------------------------------------------------------------------
+  /// JoinInst - Join Instruction
+  class JoinInst : public TerminatorInst {
+    /// Ops list - A join is like an unconditional branch to its continuation.
+    JoinInst(const JoinInst &SI);
+    void AssertOK();
+    // JoinInst constructor (where C is a block):
+    // JoinInst(BB *C)           - 'sync C'
+    // JoinInst(BB *C, Inst *I)  - 'sync C'    insert before I
+    // JoinInst(BB *C, BB *I)    - 'sync C'    insert at end
+    explicit JoinInst(BasicBlock *Continue, Instruction *InsertBefore = nullptr);
+    JoinInst(BasicBlock *Continue, BasicBlock *InsertAtEnd);
+  protected:
+    // Note: Instruction needs to be friend here to call cloneImpl.
+    friend class Instruction;
+    JoinInst *cloneImpl() const;
+
+  public:
+    static JoinInst *Create(BasicBlock *Continue, Instruction *InsertBefore = nullptr) {
+      return new(1) JoinInst(Continue, InsertBefore);
+    }
+    static JoinInst *Create(BasicBlock *Continue, BasicBlock *InsertAtEnd) {
+      return new(1) JoinInst(Continue, InsertAtEnd);
+    }
+
+    /// Transparently provide more efficient getOperand methods.
+    DECLARE_TRANSPARENT_OPERAND_ACCESSORS(Value);
+
+    unsigned getNumSuccessors() const { return 1; }
+
+    BasicBlock *getSuccessor(unsigned i) const {
+      assert(i == 0 && "Successor # out of range for join!");
+      return cast<BasicBlock>((&Op<0>())->get());
+    }
+
+    void setSuccessor(unsigned idx, BasicBlock *NewSucc) {
+      assert(idx == 0 && "Successor # out of range for join!");
+      *(&Op<0>()) = (Value*)NewSucc;
+    }
+
+    // Methods for support type inquiry through isa, cast, and dyn_cast:
+    static inline bool classof(const Instruction *I) {
+      return (I->getOpcode() == Instruction::Join);
+    }
+    static inline bool classof(const Value *V) {
+      return isa<Instruction>(V) && classof(cast<Instruction>(V));
+    }
+
+  private:
+    BasicBlock *getSuccessorV(unsigned idx) const override;
+    unsigned getNumSuccessorsV() const override;
+    void setSuccessorV(unsigned idx, BasicBlock *B) override;
+  };
+
+  template<>
+  struct OperandTraits<JoinInst> : public FixedNumOperandTraits<JoinInst, 1> {};
+
+  DEFINE_TRANSPARENT_OPERAND_ACCESSORS(JoinInst, Value)
+
+//===----------------------------------------------------------------------===//
 //                                 TruncInst Class
 //===----------------------------------------------------------------------===//
 
 /// This class represents a truncation of integer types.
 class TruncInst : public CastInst {
 protected:
   // Note: Instruction needs to be a friend here to call cloneImpl.
   friend class Instruction;

lib/AsmParser/LLLexer.cpp

#define INSTKEYWORD(STR, Enum)                                                 \
   INSTKEYWORD(va_arg,      VAArg);
   INSTKEYWORD(ret,         Ret);
   INSTKEYWORD(br,          Br);
   INSTKEYWORD(switch,      Switch);
   INSTKEYWORD(indirectbr,  IndirectBr);
   INSTKEYWORD(invoke,      Invoke);
   INSTKEYWORD(resume,      Resume);
   INSTKEYWORD(unreachable, Unreachable);
+  INSTKEYWORD(fork,        Fork);
+  INSTKEYWORD(halt,        Halt);
+  INSTKEYWORD(join,        Join);
 
   INSTKEYWORD(alloca,      Alloca);
   INSTKEYWORD(load,        Load);
   INSTKEYWORD(store,       Store);
   INSTKEYWORD(cmpxchg,     AtomicCmpXchg);
   INSTKEYWORD(atomicrmw,   AtomicRMW);
   INSTKEYWORD(fence,       Fence);
   INSTKEYWORD(getelementptr, GetElementPtr);

lib/AsmParser/LLParser.h

#include "llvm/IR/Metadata.def"
     // normal result, an error result, or return having eaten an extra comma.
     enum InstResult { InstNormal = 0, InstError = 1, InstExtraComma = 2 };
     int ParseInstruction(Instruction *&Inst, BasicBlock *BB,
                          PerFunctionState &PFS);
     bool ParseCmpPredicate(unsigned &Pred, unsigned Opc);
 
     bool ParseRet(Instruction *&Inst, BasicBlock *BB, PerFunctionState &PFS);
     bool ParseBr(Instruction *&Inst, PerFunctionState &PFS);
+    bool ParseFork(Instruction *&Inst, PerFunctionState &PFS);
+    bool ParseHalt(Instruction *&Inst, PerFunctionState &PFS);
+    bool ParseJoin(Instruction *&Inst, PerFunctionState &PFS);
     bool ParseSwitch(Instruction *&Inst, PerFunctionState &PFS);
     bool ParseIndirectBr(Instruction *&Inst, PerFunctionState &PFS);
     bool ParseInvoke(Instruction *&Inst, PerFunctionState &PFS);
     bool ParseResume(Instruction *&Inst, PerFunctionState &PFS);
     bool ParseCleanupRet(Instruction *&Inst, PerFunctionState &PFS);
     bool ParseCatchRet(Instruction *&Inst, PerFunctionState &PFS);
     bool ParseCatchSwitch(Instruction *&Inst, PerFunctionState &PFS);
     bool ParseCatchPad(Instruction *&Inst, PerFunctionState &PFS);

lib/AsmParser/LLParser.cpp

int LLParser::ParseInstruction(Instruction *&Inst, BasicBlock *BB,
   case lltok::kw_indirectbr:  return ParseIndirectBr(Inst, PFS);
   case lltok::kw_invoke:      return ParseInvoke(Inst, PFS);
   case lltok::kw_resume:      return ParseResume(Inst, PFS);
   case lltok::kw_cleanupret:  return ParseCleanupRet(Inst, PFS);
   case lltok::kw_catchret:    return ParseCatchRet(Inst, PFS);
   case lltok::kw_catchswitch: return ParseCatchSwitch(Inst, PFS);
   case lltok::kw_catchpad:    return ParseCatchPad(Inst, PFS);
   case lltok::kw_cleanuppad:  return ParseCleanupPad(Inst, PFS);
+  case lltok::kw_fork:        return ParseFork(Inst, PFS);
+  case lltok::kw_halt:        return ParseHalt(Inst, PFS);
+  case lltok::kw_join:        return ParseJoin(Inst, PFS);
   // Binary Operators.
   case lltok::kw_add:
   case lltok::kw_sub:
   case lltok::kw_mul:
   case lltok::kw_shl: {
     bool NUW = EatIfPresent(lltok::kw_nuw);
     bool NSW = EatIfPresent(lltok::kw_nsw);
     if (!NUW) NUW = EatIfPresent(lltok::kw_nuw);
if (ParseToken(lltok::comma, "expected ',' after branch condition") ||
       ParseToken(lltok::comma, "expected ',' after true destination") ||
       ParseTypeAndBasicBlock(Op2, Loc2, PFS))
     return true;
 
   Inst = BranchInst::Create(Op1, Op2, Op0);
   return false;
 }
 
+/// ParseFork
+///    ::= 'fork' TypeAndValue ',' Value
+bool LLParser::ParseFork(Instruction *&Inst, PerFunctionState &PFS) {
+  LocTy Loc, Loc2;
+  BasicBlock *ForkedBB;
+  Value *Op2;
+
+  if (ParseTypeAndBasicBlock(ForkedBB, Loc, PFS) ||
+      ParseToken(lltok::comma, "expected ',' after forked block") ||
+      ParseValue(ForkedBB->getType(), Op2, PFS))
+    return true;
+
+  BasicBlock *ContinuationBB = cast<BasicBlock>(Op2);
+  Inst = ForkInst::Create(ForkedBB, ContinuationBB);
+  return false;
+}
+
+/// ParseHalt
+///   ::= 'halt' TypeAndValue
+bool LLParser::ParseHalt(Instruction *&Inst, PerFunctionState &PFS) {
+  LocTy Loc;
+  BasicBlock *Op;
+
+  if (ParseTypeAndBasicBlock(Op, Loc, PFS))
+    return true;
+
+  Inst = HaltInst::Create(Context, Op);
+  return false;
+}
+
+/// ParseJoin
+///   ::= 'join' TypeAndValue
+bool LLParser::ParseJoin(Instruction *&Inst, PerFunctionState &PFS) {
+  LocTy Loc;
+  BasicBlock *Op;
+
+  if (ParseTypeAndBasicBlock(Op, Loc, PFS))
+    return true;
+
+  Inst = JoinInst::Create(Op);
+  return false;
+}
+
 /// ParseSwitch
 ///  Instruction
 ///    ::= 'switch' TypeAndValue ',' TypeAndValue '[' JumpTable ']'
 ///  JumpTable
 ///    ::= (TypeAndValue ',' TypeAndValue)*
 bool LLParser::ParseSwitch(Instruction *&Inst, PerFunctionState &PFS) {
   LocTy CondLoc, BBLoc;
   Value *Cond;

lib/AsmParser/LLToken.h

enum Kind {
 
   kw_extractelement,
   kw_insertelement,
   kw_shufflevector,
   kw_extractvalue,
   kw_insertvalue,
   kw_blockaddress,
 
+  // Parallel IR types
+  kw_fork,
+  kw_halt,
+  kw_join,
+
   // Metadata types.
   kw_distinct,
 
   // Use-list order directives.
   kw_uselistorder,
   kw_uselistorder_bb,
 
   // Unsigned Valued tokens (UIntVal).

lib/Bitcode/Reader/BitcodeReader.cpp

case bitc::FUNC_CODE_INST_RESUME: { // RESUME: [opval]
       I = ResumeInst::Create(Val);
       InstructionList.push_back(I);
       break;
     }
     case bitc::FUNC_CODE_INST_UNREACHABLE: // UNREACHABLE
       I = new UnreachableInst(Context);
       InstructionList.push_back(I);
       break;
+    case bitc::FUNC_CODE_INST_FORK: { // FORK: [bb#, bb#]
+      if (Record.size() != 2)
+        return error("Invalid record");
+      BasicBlock *Forked = getBasicBlock(Record[0]);
+      if (!Forked)
+        return error("Invalid record");
+
+      BasicBlock *Continue = getBasicBlock(Record[1]);
+      if (!Continue)
+        return error("Invalid record");
+
+      I = ForkInst::Create(Forked, Continue);
+      InstructionList.push_back(I);
+      break;
+    }
+    case bitc::FUNC_CODE_INST_HALT: { // HALT: [bb#]
+      if (Record.size() != 1)
+        return error("Invalid record");
+
+      BasicBlock *ForkContinue = getBasicBlock(Record[0]);
+      if (!ForkContinue)
+        return error("Invalid record");
+
+      I = HaltInst::Create(Context, ForkContinue);
+      InstructionList.push_back(I);
+      break;
+    }
+    case bitc::FUNC_CODE_INST_JOIN: { // JOIN: [bb#]
+      if (Record.size() != 1)
+        return error("Invalid record");
+
+      BasicBlock *Continue = getBasicBlock(Record[0]);
+      if (!Continue)
+        return error("Invalid record");
+
+      I = JoinInst::Create(Continue);
+      InstructionList.push_back(I);
+      break;
+    }
     case bitc::FUNC_CODE_INST_PHI: { // PHI: [ty, val0,bb0, ...]
       if (Record.size() < 1 || ((Record.size()-1)&1))
         return error("Invalid record");
       Type *Ty = getTypeByID(Record[0]);
       if (!Ty)
         return error("Invalid record");
 
       PHINode *PN = PHINode::Create(Ty, (Record.size()-1)/2);

lib/Bitcode/Writer/BitcodeWriter.cpp

case Instruction::CatchSwitch: {
     if (CatchSwitch.hasUnwindDest())
       Vals.push_back(VE.getValueID(CatchSwitch.getUnwindDest()));
     break;
   }
   case Instruction::Unreachable:
     Code = bitc::FUNC_CODE_INST_UNREACHABLE;
     AbbrevToUse = FUNCTION_INST_UNREACHABLE_ABBREV;
     break;
-
+  case Instruction::Fork: {
+    Code = bitc::FUNC_CODE_INST_FORK;
+    const ForkInst &FI = cast<ForkInst>(I);
+    Vals.push_back(VE.getValueID(FI.getSuccessor(0)));
+    Vals.push_back(VE.getValueID(FI.getSuccessor(1)));
+    break;
+  }
+  case Instruction::Halt: {
+    Code = bitc::FUNC_CODE_INST_HALT;
+    const HaltInst &HI = cast<HaltInst>(I);
+    Vals.push_back(VE.getValueID(HI.getSuccessor(0)));
+    break;
+  }
+  case Instruction::Join: {
+    Code = bitc::FUNC_CODE_INST_JOIN;
+    const JoinInst &JI = cast<JoinInst>(I);
+    Vals.push_back(VE.getValueID(JI.getSuccessor(0)));
+    break;
+  }
   case Instruction::PHI: {
     const PHINode &PN = cast<PHINode>(I);
     Code = bitc::FUNC_CODE_INST_PHI;
     // With the newer instruction encoding, forward references could give
     // negative valued IDs.  This is most common for PHIs, so we use
     // signed VBRs.
     SmallVector<uint64_t, 128> Vals64;
     Vals64.push_back(VE.getTypeID(PN.getType()));

lib/CodeGen/SelectionDAG/SelectionDAGBuilder.h

 class BasicBlock;
 class BitCastInst;
 class BranchInst;
 class CallInst;
 class DbgValueInst;
 class ExtractElementInst;
 class ExtractValueInst;
 class FCmpInst;
+class ForkInst;
 class FPExtInst;
 class FPToSIInst;
 class FPToUIInst;
 class FPTruncInst;
 class Function;
 class FunctionLoweringInfo;
 class GetElementPtrInst;
 class GCFunctionInfo;
+class HaltInst;
 class ICmpInst;
 class IntToPtrInst;
 class IndirectBrInst;
 class InvokeInst;
 class InsertElementInst;
 class InsertValueInst;
 class Instruction;
+class JoinInst;
 class LoadInst;
 class MachineBasicBlock;
 class MachineInstr;
 class MachineRegisterInfo;
 class MDNode;
 class MVT;
 class PHINode;
 class PtrToIntInst;
private:
   void visitSwitch(const SwitchInst &I);
   void visitIndirectBr(const IndirectBrInst &I);
   void visitUnreachable(const UnreachableInst &I);
   void visitCleanupRet(const CleanupReturnInst &I);
   void visitCatchSwitch(const CatchSwitchInst &I);
   void visitCatchRet(const CatchReturnInst &I);
   void visitCatchPad(const CatchPadInst &I);
   void visitCleanupPad(const CleanupPadInst &CPI);
+  void visitFork(const ForkInst &I);
+  void visitHalt(const HaltInst &I);
+  void visitJoin(const JoinInst &I);
 
   BranchProbability getEdgeProbability(const MachineBasicBlock *Src,
                                        const MachineBasicBlock *Dst) const;
   void addSuccessorWithProb(
       MachineBasicBlock *Src, MachineBasicBlock *Dst,
       BranchProbability Prob = BranchProbability::getUnknown());
 
 public:

lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

 }
 
 void SelectionDAGBuilder::visitUnreachable(const UnreachableInst &I) {
   if (DAG.getTarget().Options.TrapUnreachable)
     DAG.setRoot(
         DAG.getNode(ISD::TRAP, getCurSDLoc(), MVT::Other, DAG.getRoot()));
 }
 
+void SelectionDAGBuilder::visitFork(const llvm::ForkInst &I) {
+  MachineBasicBlock *ForkMBB = FuncInfo.MBB;
+
+  MachineBasicBlock *Forked = FuncInfo.MBBMap[I.getSuccessor(0)];
+
+  // Update machine-CFG edges
+  ForkMBB->addSuccessor(Forked);
+
+  // If this not a fall-trough branch or optimizations are switched off,
+  // emit the branch
+  if (Forked != NextBlock(ForkMBB) || TM.getOptLevel() == CodeGenOpt::None)
+    DAG.setRoot(DAG.getNode(ISD::BR, getCurSDLoc(),
+                            MVT::Other, getControlRoot(),
+                            DAG.getBasicBlock(Forked)));
+
+  return;
+}
+
+void SelectionDAGBuilder::visitHalt(const llvm::HaltInst &I) {
+  MachineBasicBlock *HaltMBB = FuncInfo.MBB;
+
+  MachineBasicBlock *Continue = FuncInfo.MBBMap[I.getSuccessor(0)];
+
+  // Update machine-CFG edges.
+  HaltMBB->addSuccessor(Continue);
+
+  // If this not a fall-trough branch or optimizations are switched off,
+  // emit the branch
+  if (Continue != NextBlock(HaltMBB) || TM.getOptLevel() == CodeGenOpt::None)
+    DAG.setRoot(DAG.getNode(ISD::BR, getCurSDLoc(),
+                            MVT::Other, getControlRoot(),
+                            DAG.getBasicBlock(Continue)));
+
+  return;
+}
+
+void SelectionDAGBuilder::visitJoin(const llvm::JoinInst &I) {
+  MachineBasicBlock *JoinMBB = FuncInfo.MBB;
+
+  MachineBasicBlock *Continue = FuncInfo.MBBMap[I.getSuccessor(0)];
+
+  // Update machine-CFG edges.
+  JoinMBB->addSuccessor(Continue);
+
+  // If this not a fall-trough branch or optimizations are switched off,
+  // emit the branch
+  if (Continue != NextBlock(JoinMBB) || TM.getOptLevel() == CodeGenOpt::None)
+    DAG.setRoot(DAG.getNode(ISD::BR, getCurSDLoc(),
+                            MVT::Other, getControlRoot(),
+                            DAG.getBasicBlock(Continue)));
+
+  return;
+}
+
 void SelectionDAGBuilder::visitFSub(const User &I) {
   // -0.0 - X --> fneg
   Type *Ty = I.getType();
   if (isa<Constant>(I.getOperand(0)) &&
       I.getOperand(0) == ConstantFP::getZeroValueForNegation(Ty)) {
     SDValue Op2 = getValue(I.getOperand(1));
     setValue(&I, DAG.getNode(ISD::FNEG, getCurSDLoc(),
                              Op2.getValueType(), Op2));

lib/CodeGen/TargetLoweringBase.cpp

#include "llvm/IR/Instruction.def"
   case Invoke:         return 0;
   case Resume:         return 0;
   case Unreachable:    return 0;
   case CleanupRet:     return 0;
   case CatchRet:       return 0;
   case CatchPad:       return 0;
   case CatchSwitch:    return 0;
   case CleanupPad:     return 0;
+  case Fork:           return 0;
+  case Join:           return 0;
+  case Halt:           return 0;
   case Add:            return ISD::ADD;
   case FAdd:           return ISD::FADD;
   case Sub:            return ISD::SUB;
   case FSub:           return ISD::FSUB;
   case Mul:            return ISD::MUL;
   case FMul:           return ISD::FMUL;
   case UDiv:           return ISD::UDIV;
   case SDiv:           return ISD::SDIV;

lib/IR/Instruction.cpp

const char *Instruction::getOpcodeName(unsigned OpCode) {
   case IndirectBr: return "indirectbr";
   case Invoke: return "invoke";
   case Resume: return "resume";
   case Unreachable: return "unreachable";
   case CleanupRet: return "cleanupret";
   case CatchRet: return "catchret";
   case CatchPad: return "catchpad";
   case CatchSwitch: return "catchswitch";
+  case Fork:        return "fork";
+  case Halt:        return "halt";
+  case Join:        return "join";
 
   // Standard binary operators...
   case Add: return "add";
   case FAdd: return "fadd";
   case Sub: return "sub";
   case FSub: return "fsub";
   case Mul: return "mul";
   case FMul: return "fmul";

lib/IR/Instructions.cpp

void UnreachableInst::setSuccessorV(unsigned idx, BasicBlock *NewSucc) {
   llvm_unreachable("UnreachableInst has no successors!");
 }
 
 BasicBlock *UnreachableInst::getSuccessorV(unsigned idx) const {
   llvm_unreachable("UnreachableInst has no successors!");
 }
 
 //===----------------------------------------------------------------------===//
+//                        ForkInst Implementation
+//===----------------------------------------------------------------------===//
+
+void ForkInst::AssertOK() {
+}
+
+ForkInst::ForkInst(BasicBlock *Forked, BasicBlock *Continue,
+                   Instruction *InsertBefore)
+    : TerminatorInst(Type::getVoidTy(Forked->getContext()), Instruction::Fork,
+                     OperandTraits<ForkInst>::op_end(this), 2, InsertBefore) {
+  Op<0>() = Forked;
+  Op<1>() = Continue;
+#ifndef NDEBUG
+  AssertOK();
+#endif
+}
+
+ForkInst::ForkInst(const ForkInst &FI)
+    : TerminatorInst(Type::getVoidTy(FI.getContext()), Instruction::Fork,
+                     OperandTraits<ForkInst>::op_end(this),
+                     FI.getNumOperands()) {
+  Op<0>() = FI.Op<0>();
+  Op<1>() = FI.Op<1>();
+  assert(FI.getNumOperands() == 2 && "Fork must have 2 operands!");
+  SubclassOptionalData = FI.SubclassOptionalData;
+}
+
+void ForkInst::swapSuccessors() {
+  Op<0>().swap(Op<1>());
+
+  // Update profile metadata if present and it matches our structrual
+  // expectations.
+  MDNode *ProfileData = getMetadata(LLVMContext::MD_prof);
+  if (!ProfileData || ProfileData->getNumOperands() != 2)
+    return;
+
+  // The first operand is the name. Fetch them backwards and build a new one.
+  Metadata *Ops[] = {ProfileData->getOperand(1), ProfileData->getOperand(0)};
+
+  setMetadata(LLVMContext::MD_prof, MDNode::get(ProfileData->getContext(), Ops));
+}
+
+BasicBlock *ForkInst::getSuccessorV(unsigned idx) const {
+  return getSuccessor(idx);
+}
+unsigned ForkInst::getNumSuccessorsV() const {
+  return getNumSuccessors();
+}
+void ForkInst::setSuccessorV(unsigned idx, BasicBlock *B) {
+  assert(idx <= 1);
+  setSuccessor(idx, B);
+}
+
+//===----------------------------------------------------------------------===//
+//                        HaltInst Implementation
+//===----------------------------------------------------------------------===//
+
+void HaltInst::AssertOK() {
+}
+
+HaltInst::HaltInst(LLVMContext &C, BasicBlock *ForkContinue,
+                   Instruction *InsertBefore)
+  : TerminatorInst(Type::getVoidTy(C), Instruction::Halt,
+                   OperandTraits<HaltInst>::op_end(this), 1,
+                   InsertBefore) {
+  Op<0>() = ForkContinue;
+#ifndef NDEBUG
+  AssertOK();
+#endif
+}
+HaltInst::HaltInst(LLVMContext &C, BasicBlock *ForkContinue,
+                   BasicBlock *InsertAtEnd)
+  : TerminatorInst(Type::getVoidTy(C), Instruction::Halt,
+                   OperandTraits<HaltInst>::op_end(this), 1,
+                   InsertAtEnd) {
+  Op<0>() = ForkContinue;
+#ifndef NDEBUG
+  AssertOK();
+#endif
+}
+
+HaltInst::HaltInst(const HaltInst &HI)
+  : TerminatorInst(Type::getVoidTy(HI.getContext()), Instruction::Halt,
+                   OperandTraits<HaltInst>::op_end(this) - HI.getNumOperands(),
+                   HI.getNumOperands()) {
+  Op<0>() = HI.Op<0>();
+  assert(HI.getNumOperands() == 1 && "Halt must have 1 operand!");
+  SubclassOptionalData = HI.SubclassOptionalData;
+}
+
+unsigned HaltInst::getNumSuccessorsV() const {
+  return getNumSuccessors();
+}
+
+BasicBlock *HaltInst::getSuccessorV(unsigned idx) const {
+  return getSuccessor(idx);
+}
+
+void HaltInst::setSuccessorV(unsigned idx, BasicBlock *B) {
+  assert(idx == 0);
+  setSuccessor(idx, B);
+}
+
+//===----------------------------------------------------------------------===//
+//                        JoinInst Implementation
+//===----------------------------------------------------------------------===//
+
+void JoinInst::AssertOK() {
+}
+
+JoinInst::JoinInst(BasicBlock *Continue, Instruction *InsertBefore)
+    : TerminatorInst(Type::getVoidTy(Continue->getContext()), Instruction::Join,
+                     OperandTraits<JoinInst>::op_end(this), 1, InsertBefore) {
+  Op<0>() = Continue;
+#ifndef NDEBUG
+  AssertOK();
+#endif
+}
+JoinInst::JoinInst(BasicBlock *Continue, BasicBlock *InsertAtEnd)
+    : TerminatorInst(Type::getVoidTy(Continue->getContext()), Instruction::Join,
+                     OperandTraits<JoinInst>::op_end(this), 1, InsertAtEnd) {
+  Op<0>() = Continue;
+#ifndef NDEBUG
+  AssertOK();
+#endif
+}
+
+JoinInst::JoinInst(const JoinInst &JI)
+  : TerminatorInst(Type::getVoidTy(JI.getContext()), Instruction::Join,
+                   OperandTraits<JoinInst>::op_end(this) - JI.getNumOperands(),
+                   JI.getNumOperands()) {
+  Op<0>() = JI.Op<0>();
+  assert(JI.getNumOperands() == 1 && "Join must have 1 operand!");
+  SubclassOptionalData = JI.SubclassOptionalData;
+}
+
+unsigned JoinInst::getNumSuccessorsV() const {
+  return getNumSuccessors();
+}
+
+BasicBlock *JoinInst::getSuccessorV(unsigned idx) const {
+  return getSuccessor(idx);
+}
+
+void JoinInst::setSuccessorV(unsigned idx, BasicBlock *B) {
+  assert(idx == 0);
+  setSuccessor(idx, B);
+}
+
+//===----------------------------------------------------------------------===//
 //                        BranchInst Implementation
 //===----------------------------------------------------------------------===//
 
 void BranchInst::AssertOK() {
   if (isConditional())
     assert(getCondition()->getType()->isIntegerTy(1) &&
            "May only branch on boolean predicates!");
 }

 FuncletPadInst *FuncletPadInst::cloneImpl() const {
   return new (getNumOperands()) FuncletPadInst(*this);
 }
 
 UnreachableInst *UnreachableInst::cloneImpl() const {
   LLVMContext &Context = getContext();
   return new UnreachableInst(Context);
 }
+
+ForkInst *ForkInst::cloneImpl() const {
+  return new(getNumOperands()) ForkInst(*this);
+}
+
+HaltInst *HaltInst::cloneImpl() const {
+  return new(getNumOperands()) HaltInst(*this);
+}
+
+JoinInst *JoinInst::cloneImpl() const {
+  return new(getNumOperands()) JoinInst(*this);
+}

test/PIR/invalid_fork.ll

+; RUN: not llvm-as < %s
+
+declare void @foo();
+
+define i32 @test() {
+entry:
+  fork label %forked
+
+forked:                                       ; preds = %entry
+  call void @foo()
+  halt label %cont
+
+cont:                                         ; preds = %entry, %forked
+  call void @foo()
+  join label %join
+
+join:                                         ; preds = %cont
+  ret i32 0
+}

test/PIR/reader_writer.ll

+; RUN: llvm-as < %s | llvm-dis | FileCheck %s
+; RUN: opt < %s -o - | opt -o - -S | FileCheck %s
+; RUN: opt < %s -o - | opt -o - -S | opt -o - | opt -o - -S | FileCheck %s
+
+declare void @foo();
+
+define i32 @test() {
+entry:
+  ; CHECK: fork label %forked, %cont
+  fork label %forked, %cont
+
+forked:                                       ; preds = %entry
+  call void @foo()
+  ; CHECK: halt label %cont
+  halt label %cont
+
+cont:                                         ; preds = %entry, %forked
+  call void @foo()
+  ; CHECK: join label %join
+  join label %join
+
+join:                                         ; preds = %cont
+  ret i32 0
+}

unittests/IR/InstructionsTest.cpp

TEST(InstructionsTest, BranchInst) {
   // clean up
   delete b0;
   delete b1;
 
   delete bb0;
   delete bb1;
 }
 
+  TEST(InstructionTest, ForkInst) {
+    LLVMContext C;
+
+    // create fork destinations
+    BasicBlock *Forked = BasicBlock::Create(C);
+    BasicBlock *Continue = BasicBlock::Create(C);
+
+    // create fork instruction
+    ForkInst *Fork = ForkInst::Create(Forked, Continue);
+
+    EXPECT_EQ(Forked, Fork->getSuccessor(0));
+    EXPECT_EQ(Forked, Fork->getForkedBB());
+    EXPECT_EQ(Continue, Fork->getSuccessor(1));
+    EXPECT_EQ(Continue, Fork->getContinuationBB());
+
+    // test swapping destinations
+    Fork->swapSuccessors();
+
+    EXPECT_EQ(Forked, Fork->getSuccessor(1));
+    EXPECT_EQ(Forked, Fork->getContinuationBB());
+    EXPECT_EQ(Continue, Fork->getSuccessor(0));
+    EXPECT_EQ(Continue, Fork->getForkedBB());
+
+    EXPECT_NE(Forked, Fork->getSuccessor(0));
+    EXPECT_NE(Forked, Fork->getForkedBB());
+    EXPECT_NE(Continue, Fork->getSuccessor(1));
+    EXPECT_NE(Continue, Fork->getContinuationBB());
+
+    // test instruction type
+    EXPECT_TRUE(ForkInst::classof(Fork));
+
+    // clean up
+    delete Fork;
+
+    delete Forked;
+    delete Continue;
+  }
+
 TEST(InstructionsTest, CastInst) {
   LLVMContext C;
 
   Type *Int8Ty = Type::getInt8Ty(C);
   Type *Int16Ty = Type::getInt16Ty(C);
   Type *Int32Ty = Type::getInt32Ty(C);
   Type *Int64Ty = Type::getInt64Ty(C);
   Type *V8x8Ty = VectorType::get(Int8Ty, 8);