[BOLT] Remove removeConditionalTailCalls

[yota9]

Summary

We can treat conditional tail call both as call and false branch without CFG violations. Initially the BB containing CTC would always end with CTC instruction (as it is treated as tail call at this stage). The fall through FBB would also be added for this BB during CFG construction. The analyzeBranch would stop execution on finding isTailCall and initially would return nullptr for both CondBranch and UncondBranch. After BB reordering unconditional jump to FBB might be added by fixBranches (BB is treated normally as BB with one successor).

[rafauler]

FYI if you just want to test, I think you can publish this as "draft" using "arc diff --draft"

[yota9]

@rafaelauler Thanks, I've decided to add proper description since currently I don't really see any examples when removeConditionalTailCalls would be necessary. We can discuss it in discord if it will be comfortable for you or @maksfb .

bolt/include/bolt/Core/BinaryFunction.h

   ///
   /// Assumes the CFG has been built and edge frequency for taken branches
   /// has been filled with LBR data.
   void inferFallThroughCounts();
 
   /// Clear execution profile of the function.
   void clearProfile();
 
-  /// Converts conditional tail calls to unconditional tail calls. We do this to
-  /// handle conditional tail calls correctly and to give a chance to the
-  /// simplify conditional tail call pass to decide whether to re-optimize them
-  /// using profile information.
-  void removeConditionalTailCalls();
-
   // Convert COUNT_NO_PROFILE to 0
   void removeTagsFromProfile();
 
   /// Computes a function hotness score: the sum of the products of BB frequency
   /// and size.
   uint64_t getFunctionScore() const;
 
   /// Return true if the layout has been changed by basic block reordering,

bolt/lib/Core/BinaryFunction.cpp

bool BinaryFunction::buildCFG(MCPlusBuilder::AllocatorIdTy AllocatorId) {
   clearList(ExternallyReferencedOffsets);
   clearList(UnknownIndirectBranchOffsets);
 
   return true;
 }
 
 void BinaryFunction::postProcessCFG() {
   if (isSimple() && !BasicBlocks.empty()) {
-    // Convert conditional tail call branches to conditional branches that jump
-    // to a tail call.
-    removeConditionalTailCalls();
-
     postProcessProfile();
 
     // Eliminate inconsistencies between branch instructions and CFG.
     postProcessBranches();
   }
 
   calculateMacroOpFusionStats();
 
for (BinaryBasicBlock::BinaryBranchInfo &BI : BB->branch_info()) {
           BI.MispredictedCount != BinaryBasicBlock::COUNT_NO_PROFILE)
         continue;
       BI.Count = 0;
       BI.MispredictedCount = 0;
     }
   }
 }
 
-void BinaryFunction::removeConditionalTailCalls() {
-  // Blocks to be appended at the end.
-  std::vector<std::unique_ptr<BinaryBasicBlock>> NewBlocks;
-
-  for (auto BBI = begin(); BBI != end(); ++BBI) {
-    BinaryBasicBlock &BB = *BBI;
-    MCInst *CTCInstr = BB.getLastNonPseudoInstr();
-    if (!CTCInstr)
-      continue;
-
-    Optional<uint64_t> TargetAddressOrNone =
-        BC.MIB->getConditionalTailCall(*CTCInstr);
-    if (!TargetAddressOrNone)
-      continue;
-
-    // Gather all necessary information about CTC instruction before
-    // annotations are destroyed.
-    const int32_t CFIStateBeforeCTC = BB.getCFIStateAtInstr(CTCInstr);
-    uint64_t CTCTakenCount = BinaryBasicBlock::COUNT_NO_PROFILE;
-    uint64_t CTCMispredCount = BinaryBasicBlock::COUNT_NO_PROFILE;
-    if (hasValidProfile()) {
-      CTCTakenCount = BC.MIB->getAnnotationWithDefault<uint64_t>(
-          *CTCInstr, "CTCTakenCount");
-      CTCMispredCount = BC.MIB->getAnnotationWithDefault<uint64_t>(
-          *CTCInstr, "CTCMispredCount");
-    }
-
-    // Assert that the tail call does not throw.
-    assert(!BC.MIB->getEHInfo(*CTCInstr) &&
-           "found tail call with associated landing pad");
-
-    // Create a basic block with an unconditional tail call instruction using
-    // the same destination.
-    const MCSymbol *CTCTargetLabel = BC.MIB->getTargetSymbol(*CTCInstr);
-    assert(CTCTargetLabel && "symbol expected for conditional tail call");
-    MCInst TailCallInstr;
-    BC.MIB->createTailCall(TailCallInstr, CTCTargetLabel, BC.Ctx.get());
-    // Link new BBs to the original input offset of the BB where the CTC
-    // is, so we can map samples recorded in new BBs back to the original BB
-    // seem in the input binary (if using BAT)
-    std::unique_ptr<BinaryBasicBlock> TailCallBB = createBasicBlock(
-        BB.getInputOffset(), BC.Ctx->createNamedTempSymbol("TC"));
-    TailCallBB->addInstruction(TailCallInstr);
-    TailCallBB->setCFIState(CFIStateBeforeCTC);
-
-    // Add CFG edge with profile info from BB to TailCallBB.
-    BB.addSuccessor(TailCallBB.get(), CTCTakenCount, CTCMispredCount);
-
-    // Add execution count for the block.
-    TailCallBB->setExecutionCount(CTCTakenCount);
-
-    BC.MIB->convertTailCallToJmp(*CTCInstr);
-
-    BC.MIB->replaceBranchTarget(*CTCInstr, TailCallBB->getLabel(),
-                                BC.Ctx.get());
-
-    // Add basic block to the list that will be added to the end.
-    NewBlocks.emplace_back(std::move(TailCallBB));
-
-    // Swap edges as the TailCallBB corresponds to the taken branch.
-    BB.swapConditionalSuccessors();
-
-    // This branch is no longer a conditional tail call.
-    BC.MIB->unsetConditionalTailCall(*CTCInstr);
-  }
-
-  insertBasicBlocks(std::prev(end()), std::move(NewBlocks),
-                    /* UpdateLayout */ true,
-                    /* UpdateCFIState */ false);
-}
-
 uint64_t BinaryFunction::getFunctionScore() const {
   if (FunctionScore != -1)
     return FunctionScore;
 
   if (!isSimple() || !hasValidProfile()) {
     FunctionScore = 0;
     return FunctionScore;
   }

 
 void BinaryFunction::postProcessBranches() {
   if (!isSimple())
     return;
   for (BinaryBasicBlock *BB : BasicBlocksLayout) {
     auto LastInstrRI = BB->getLastNonPseudo();
     if (BB->succ_size() == 1) {
       if (LastInstrRI != BB->rend() &&
-          BC.MIB->isConditionalBranch(*LastInstrRI)) {
+          BC.MIB->isConditionalBranch(*LastInstrRI) &&
+          !BC.MIB->getConditionalTailCall(*LastInstrRI)) {
         // __builtin_unreachable() could create a conditional branch that
         // falls-through into the next function - hence the block will have only
         // one valid successor. Such behaviour is undefined and thus we remove
         // the conditional branch while leaving a valid successor.
         BB->eraseInstruction(std::prev(LastInstrRI.base()));
         LLVM_DEBUG(dbgs() << "BOLT-DEBUG: erasing conditional branch in "
                           << BB->getName() << " in function " << *this << '\n');
       }

bolt/lib/Target/X86/X86MCPlusBuilder.cpp

bool analyzeBranch(InstructionIterator Begin, InstructionIterator End,
                      MCInst *&UncondBranch) const override {
     auto I = End;
 
     // Bottom-up analysis
     while (I != Begin) {
       --I;
 
       // Ignore nops and CFIs
-      if (isPseudo(*I))
+      if (isPseudo(*I) || isNoop(*I))
         continue;
 
       // Stop when we find the first non-terminator
-      if (!isTerminator(*I))
-        break;
-
-      if (!isBranch(*I))
+      if (!isTerminator(*I) || isTailCall(*I) || !isBranch(*I))
         break;
 
       // Handle unconditional branches.
       if ((I->getOpcode() == X86::JMP_1 || I->getOpcode() == X86::JMP_2 ||
-           I->getOpcode() == X86::JMP_4) &&
-          !isTailCall(*I)) {
+           I->getOpcode() == X86::JMP_4)) {
         // If any code was seen after this unconditional branch, we've seen
         // unreachable code. Ignore them.
         CondBranch = nullptr;
         UncondBranch = &*I;
         const MCSymbol *Sym = getTargetSymbol(*I);
         assert(Sym != nullptr &&
                "Couldn't extract BB symbol from jump operand");
         TBB = Sym;