[OpenMP][OMPIRBuilder][BugFix] Handle Unreachable Finalization blocks in `parallel` generation

[fghanim]

Summary

In some situations (e.g. while(1); ) the body block(s) will not contain a branch to the finalization block.
In this patch, CreateParallel has been modified to check if the PRegPreFiniBB is reachable before
generating finalization code. If not, will remove all unreachable blocks.

[fghanim]

• Cleaning up some leftover code.

[fghanim]

Adding a new unittest for the this fix. Thanks to JDoerfert for Writing and providing me with this patch.

[fghanim]

Adding lit test to clang for testing the fix

[fghanim]

• Squashing all the commits

[jdoerfert]

llvm/lib/Frontend/OpenMP/OMPIRBuilder.cpp

689

Why do we need all of this? Can't we just *not do it* instead? This is code complexity that we should avoid.

[fghanim]

llvm/lib/Frontend/OpenMP/OMPIRBuilder.cpp

689

Depends.
If we want to conform with the way things are done in clang; namely, not have unreachable blocks, then yes we need to do this. If not, then no, nothing needs to change. An optimization pass will be executed at some point later that should clean all that up.

However, we should be careful, for example, The lit test for critical checks that no basic blocks were generated from the rest of the body that comes after the infinite loop. So if the choice is to not conform with clang, then we should keep an eye on these lit tests, and disable such checks for the OMPBuilder.

[jdoerfert]

llvm/lib/Frontend/OpenMP/OMPIRBuilder.cpp

689

If we want to conform with the way things are done in clang;

It's not like we introduce much extra code, break anything, or make the final result different.

If not, then no, nothing needs to change. An optimization pass will be executed at some point later that should clean all that up.

Let's go with that solution and keep this code here simple, less error prone, and easier to manage.

However, we should be careful, for example, The lit test for critical checks that no basic blocks were generated from the rest of the body that comes after the infinite loop. So if the choice is to not conform with clang, then we should keep an eye on these lit tests, and disable such checks for the OMPBuilder.

We already do things different and that will only become more evident (TRegions!). For example, to simplify this code we do *not* cache runtime calls (anymore). That is we emit a new get_thread_id call every time. (We know the OpenMPOpt pass will clean it up eventually.) I get that the tests change and for a while we will have clang and OMPBuilder check lines. Though, once the clang CG is gone there is arguably no difference anymore because the OMPBuilder behavior is then the default. As soon as we have the privatization parts properly hooked up we can even start running the OMPBuilder by default and soon after removing clang CG parts. If anything, we should modernize the clang tests as they are a constant critique point that hinders outside involvement. We could start using the llvm/utils/update_XXXX_checks scripts for example. We could also minimize the check lines and focus on the most important bits only. (I prefer the update scripts with the pending extensions, e.g., D69701)

[fghanim]

llvm/lib/Frontend/OpenMP/OMPIRBuilder.cpp

689

In that case, This revision is not necessary. The only fix needed is the branch erasure/creation change in the body CallBack (a bit more on this later), all the rest including the tests is not necessary. The only tests needed are already being done by the llvm verifier, which already reports if a BB is used by an orphan branch sticking around, or if a BB contains more than one terminator.

Regarding the issue of the branch, given that our finalization and body callbacks are very similar across different directives (Parallel, master, critical), the plan as we discussed on D72304 , is to write helper functions/class that we could use instead. So whoever, ends up writing that should make sure to include the branch changes, which makes them here redundant.

So, in the interest of everyone's time, my suggestion is to abandon this revision entirely for now, and just make sure that the implementation of these helper functions takes care of this everywhere.

[fghanim]

The bug this revision attempted to fix has been resolved as part of patch D74562

clang/lib/CodeGen/CGStmtOpenMP.cpp

auto BodyGenCB = [ParallelRegionBodyStmt,
                             llvm::BasicBlock &ContinuationBB) {
       auto OldAllocaIP = AllocaInsertPt;
       AllocaInsertPt = &*AllocaIP.getPoint();
 
       auto OldReturnBlock = ReturnBlock;
       ReturnBlock = getJumpDestInCurrentScope(&ContinuationBB);
 
       llvm::BasicBlock *CodeGenIPBB = CodeGenIP.getBlock();
-      CodeGenIPBB->splitBasicBlock(CodeGenIP.getPoint());
+      // CodeGenIPBB->splitBasicBlock(CodeGenIP.getPoint());
       llvm::Instruction *CodeGenIPBBTI = CodeGenIPBB->getTerminator();
-      CodeGenIPBBTI->removeFromParent();
+      CodeGenIPBBTI->eraseFromParent();
 
       Builder.SetInsertPoint(CodeGenIPBB);
 
       EmitStmt(ParallelRegionBodyStmt);
 
-      Builder.Insert(CodeGenIPBBTI);
+      if (Builder.saveIP().isSet())
+        Builder.CreateBr(&ContinuationBB);
 
       AllocaInsertPt = OldAllocaIP;
       ReturnBlock = OldReturnBlock;
     };
 
     CGCapturedStmtInfo CGSI(*CS, CR_OpenMP);
     CodeGenFunction::CGCapturedStmtRAII CapInfoRAII(*this, &CGSI);
     Builder.restoreIP(OMPBuilder->CreateParallel(Builder, BodyGenCB, PrivCB,

llvm/lib/Frontend/OpenMP/OMPIRBuilder.cpp

IRBuilder<>::InsertPoint OpenMPIRBuilder::CreateParallel(
   while (!Worklist.empty()) {
     BasicBlock *BB = Worklist.pop_back_val();
     ParallelRegionBlocks.push_back(BB);
     for (BasicBlock *SuccBB : successors(BB))
       if (ParallelRegionBlockSet.insert(SuccBB).second)
         Worklist.push_back(SuccBB);
   }
 
+  // If we didn't emit a branch to FiniBB during body generation, it means
+  // FiniBB is unreachable (e.g. while(1);). stop generating all the
+  // unreachable blocks, and remove anything we are not going to use.
+  // Check to see if PRegPreFiniBB is reachable from PRegionBodyBB.
+  bool FoundPreFiniBB = false;
+  for (auto BI : ParallelRegionBlocks) {
+    if (BI == PRegPreFiniBB) {
+      FoundPreFiniBB = true;
+      break;
+    }
+  }
+
   CodeExtractorAnalysisCache CEAC(*OuterFn);
   CodeExtractor Extractor(ParallelRegionBlocks, /* DominatorTree */ nullptr,
                           /* AggregateArgs */ false,
                           /* BlockFrequencyInfo */ nullptr,
                           /* BranchProbabilityInfo */ nullptr,
                           /* AssumptionCache */ nullptr,
                           /* AllowVarArgs */ true,
                           /* AllowAlloca */ true,
if (!F->hasMetadata(llvm::LLVMContext::MD_callback)) {
       F->addMetadata(
           llvm::LLVMContext::MD_callback,
           *llvm::MDNode::get(Ctx, {MDB.createCallbackEncoding(
                                       2, {-1, -1},
                                       /* VarArgsArePassed */ true)}));
     }
   }
 
-  Builder.CreateCall(RTLFn, RealArgs);
+  Builder.GetInsertBlock()->dump();
+  CallInst *ForkCall = Builder.CreateCall(RTLFn, RealArgs);
 
   LLVM_DEBUG(dbgs() << "With fork_call placed: "
                     << *Builder.GetInsertBlock()->getParent() << "\n");
 
   InsertPointTy AfterIP(UI->getParent(), UI->getParent()->end());
   InsertPointTy ExitIP(PRegExitBB, PRegExitBB->end());
   UI->eraseFromParent();
 
   // Initialize the local TID stack location with the argument value.
   Builder.SetInsertPoint(PrivTID);
   Function::arg_iterator OutlinedAI = OutlinedFn->arg_begin();
   Builder.CreateStore(Builder.CreateLoad(OutlinedAI), PrivTIDAddr);
 
   // If no "if" clause was present we do not need the call created during
   // outlining, otherwise we reuse it in the serialized parallel region.
   if (!ElseTI) {
     CI->eraseFromParent();
   } else {
-
     // If an "if" clause was present we are now generating the serialized
     // version into the "else" branch.
     Builder.SetInsertPoint(ElseTI);
 
     // Build calls __kmpc_serialized_parallel(&Ident, GTid);
     Value *SerializedParallelCallArgs[] = {Ident, ThreadID};
     Builder.CreateCall(
         getOrCreateRuntimeFunction(OMPRTL___kmpc_serialized_parallel),
         SerializedParallelCallArgs);
 
     // OutlinedFn(&GTid, &zero, CapturedStruct);
     CI->removeFromParent();
     Builder.Insert(CI);
 
     // __kmpc_end_serialized_parallel(&Ident, GTid);
     Value *EndArgs[] = {Ident, ThreadID};
     Builder.CreateCall(
         getOrCreateRuntimeFunction(OMPRTL___kmpc_end_serialized_parallel),
         EndArgs);
 
     LLVM_DEBUG(dbgs() << "With serialized parallel region: "
                       << *Builder.GetInsertBlock()->getParent() << "\n");
   }
 
-  // Adjust the finalization stack, verify the adjustment, and call the
-  // finalize function a last time to finalize values between the pre-fini block
-  // and the exit block if we left the parallel "the normal way".
+  assert(!FinalizationStack.empty() && "Unexpected finalization stack state!");
   auto FiniInfo = FinalizationStack.pop_back_val();
-  (void)FiniInfo;
   assert(FiniInfo.DK == OMPD_parallel &&
          "Unexpected finalization stack state!");
+  if (FoundPreFiniBB) {
+    // PRegPreFiniBB is reachable. Adjust the finalization stack, verify the
+    // adjustment, and call the finalize function a last time to finalize values
+    // between the pre-fini block and the exit block if we left the parallel
+    // "the normal way".
+    (void)FiniInfo;
 
     Instruction *PreFiniTI = PRegPreFiniBB->getTerminator();
     assert(PreFiniTI->getNumSuccessors() == 1 &&
            PreFiniTI->getSuccessor(0)->size() == 1 &&
            isa<ReturnInst>(PreFiniTI->getSuccessor(0)->getTerminator()) &&
            "Unexpected CFG structure!");
 
     InsertPointTy PreFiniIP(PRegPreFiniBB, PreFiniTI->getIterator());
     FiniCB(PreFiniIP);
+  } else {
+    // PRegPreFiniBB is unreachable. remove the blocks and discard the
+    // finalization callback
+    llvm::SmallVector<BasicBlock *, 4> ToBeDeletedBB;
+    ToBeDeletedBB.push_back(PRegPreFiniBB);
+    PRegPreFiniBB->getUniquePredecessor();
+    BranchInst *BBTerminator =
+        dyn_cast_or_null<BranchInst>(PRegPreFiniBB->getTerminator());
+    while (BBTerminator) {
+      assert(!BBTerminator->isConditional() &&
+             "unexpected conditional branch in unreachable blocks");
+      BasicBlock *next = BBTerminator->getSuccessor(0);
+      ToBeDeletedBB.push_back(next);
+      BBTerminator = dyn_cast_or_null<BranchInst>(next->getTerminator());
+    }
+
+    for (auto BB : ToBeDeletedBB) {
+      BB->eraseFromParent();
+    }
+
+    BasicBlock *ForkBB = ForkCall->getParent();
+    ForkBB->getTerminator()->eraseFromParent();
+    AfterIP = InsertPointTy(ForkBB, ForkBB->end());
+  }
 
   for (Instruction *I : ToBeDeleted)
     I->eraseFromParent();
 
+  AfterIP.getBlock()->dump();
   return AfterIP;
 }
 
 OpenMPIRBuilder::InsertPointTy
 OpenMPIRBuilder::CreateMaster(const LocationDescription &Loc,
                               BodyGenCallbackTy BodyGenCB,
                               FinalizeCallbackTy FiniCB) {
 
   if (!updateToLocation(Loc))
     return Loc.IP;
 
   Directive OMPD = Directive::OMPD_master;
   Constant *SrcLocStr = getOrCreateSrcLocStr(Loc);
   Value *Ident = getOrCreateIdent(SrcLocStr);
   Value *ThreadId = getOrCreateThreadID(Ident);
   Value *Args[] = {Ident, ThreadId};
 
   Function *EntryRTLFn = getOrCreateRuntimeFunction(OMPRTL___kmpc_master);
   Instruction *EntryCall = Builder.CreateCall(EntryRTLFn, Args);
 
   Function *ExitRTLFn = getOrCreateRuntimeFunction(OMPRTL___kmpc_end_master);
   Instruction *ExitCall = Builder.CreateCall(ExitRTLFn, Args);
 
   return EmitOMPInlinedRegion(OMPD, EntryCall, ExitCall, BodyGenCB, FiniCB,
                               /*Conditional*/ true, /*hasFinalize*/ true);
 }