If conversion to conditional select for -Oz or -Os unprofitable for single operation blocks

[ramred01]

Summary

When we are compiling for -Os or -Oz, performing if conversion to conditional select when the two branches of the if have exactly one instruction in them tends to generate more code.

We prevent it at three stages. The first is in early if conversion. We count the number of instructions in each block and if it is less than two we return without changes.

The next is in the tail duplicator. If there are no select or GEP instructions in the layout predecessor of the tail duplicated block, then we do not splice the tail duplicated block into the layout predecessor. This prevents generation of some unnecessary branches.

The third is in simplify CFG. If the if statement results in a two entry PHI node at the beginning of a basic block, then we try to fold it into a SELECT. In case the incoming edges to the PHI node are from basic blocks having exactly one instruction, we prevent the generation of this SELECT.

[vsk]

Thanks for working on this. I’d suggest splitting this into a sequence of three patches (with tests and accompanying code size numbers), so its effects can be understood better.

lib/CodeGen/EarlyIfConversion.cpp

 /// replacePHIInstrs - Completely replace PHI instructions with selects.
 /// This is possible when the only Tail predecessors are the if-converted
 /// blocks.
 void SSAIfConv::replacePHIInstrs() {
   assert(Tail->pred_size() == 2 && "Cannot replace PHIs");
   MachineBasicBlock::iterator FirstTerm = Head->getFirstTerminator();
   assert(FirstTerm != Head->end() && "No terminators");
   DebugLoc HeadDL = FirstTerm->getDebugLoc();
   
   // Convert all PHIs to select instructions inserted before FirstTerm.
   for (unsigned i = 0, e = PHIs.size(); i != e; ++i) {
     PHIInfo &PI = PHIs[i];
     LLVM_DEBUG(dbgs() << "If-converting " << *PI.PHI);
     unsigned DstReg = PI.PHI->getOperand(0).getReg();
     TII->insertSelect(*Head, FirstTerm, HeadDL, DstReg, Cond, PI.TReg, PI.FReg);
     LLVM_DEBUG(dbgs() << "          --> " << *std::prev(FirstTerm));
     PI.PHI->eraseFromParent();

 
 /// convertIf - Execute the if conversion after canConvertIf has determined the
 /// feasibility.
 ///
 /// Any basic blocks erased will be added to RemovedBlocks.
 ///
 void SSAIfConv::convertIf(SmallVectorImpl<MachineBasicBlock*> &RemovedBlocks) {
   assert(Head && Tail && TBB && FBB && "Call canConvertIf first.");
  
   // Update statistics.
   if (isTriangle())
     ++NumTrianglesConv;
   else
     ++NumDiamondsConv;
 
   // Move all instructions into Head, except for the terminators.
   if (TBB != Tail)
bool EarlyIfConverter::shouldConvertIf() {
   }
   return true;
 }
 
 /// Attempt repeated if-conversion on MBB, return true if successful.
 ///
 bool EarlyIfConverter::tryConvertIf(MachineBasicBlock *MBB) {
   bool Changed = false;
+  const BasicBlock *BB = MBB->getBasicBlock();
+  unsigned PhiInst = 0;
+  const PHINode *PN;
+  // iterate through Basic Block for PHI nodes.
+  for (BasicBlock::const_iterator I = BB->begin(), E = BB->end(); 
+      I != E; ++I) {
+    if (dyn_cast<PHINode>(I)) {
+      PN = dyn_cast<PHINode>(I);
+      PhiInst++;
+    }
+  }
+  unsigned IfBlock1Inst = 0;
+  unsigned IfBlock2Inst = 0;
+  if (PhiInst == 1 && PN) {
+    BasicBlock *IfBlock1 = PN->getIncomingBlock(0);
+    BasicBlock *IfBlock2 = PN->getIncomingBlock(1);
+    // iterate through if block instructions 
+    for (BasicBlock::iterator I = IfBlock1->begin(); !I->isTerminator(); ++I) {
+      if(!dyn_cast<BranchInst>(I))
+        IfBlock1Inst++;
+    }
+    for (BasicBlock::iterator I = IfBlock2->begin(); !I->isTerminator(); ++I) {
+      if(!dyn_cast<BranchInst>(I))
+        IfBlock2Inst++;
+    }
+  }
+  // if optimization options is either -Oz or -Os and if have less than 
+  // two instrutions in if or else basic block return false.
+  if (BB->getParent()->optForSize() && IfBlock1Inst < 2 && IfBlock2Inst < 2)
+    return false;
+
   while (IfConv.canConvertIf(MBB) && shouldConvertIf()) {
     // If-convert MBB and update analyses.
     invalidateTraces();
     SmallVector<MachineBasicBlock*, 4> RemovedBlocks;
     IfConv.convertIf(RemovedBlocks);
     Changed = true;
     updateDomTree(RemovedBlocks);
     updateLoops(RemovedBlocks);

lib/CodeGen/TailDuplication.cpp

 
 INITIALIZE_PASS(TailDuplicate, DEBUG_TYPE, "Tail Duplication", false, false)
 INITIALIZE_PASS(EarlyTailDuplicate, "early-tailduplication",
                 "Early Tail Duplication", false, false)
 
 bool TailDuplicateBase::runOnMachineFunction(MachineFunction &MF) {
   if (skipFunction(MF.getFunction()))
     return false;
   
   auto MBPI = &getAnalysis<MachineBranchProbabilityInfo>();
   Duplicator.initMF(MF, PreRegAlloc, MBPI, /*LayoutMode=*/false);
 
   bool MadeChange = false;
   while (Duplicator.tailDuplicateBlocks())
     MadeChange = true;
 
   return MadeChange;
 }

lib/CodeGen/TailDuplicator.cpp

if (PreRegAlloc) {
         // uses with PHI source register or the new registers.
         MachineInstr *MI = &*I++;
         assert(!MI->isBundle() && "Not expecting bundles before regalloc!");
         duplicateInstruction(MI, TailBB, PrevBB, LocalVRMap, UsedByPhi);
         MI->eraseFromParent();
       }
       appendCopies(PrevBB, CopyInfos, Copies);
     } else {
-      TII->removeBranch(*PrevBB);
       // No PHIs to worry about, just splice the instructions over.
+      const BasicBlock *BBM = PrevBB->getBasicBlock();
+      unsigned SelGEPInst = 0;
+      // if BBM is not null then iterate through basicblock and 
+      // get the count of select and getElementPtr instructions.
+      if (BBM) {
+        for (BasicBlock::const_iterator I = BBM->begin(), E = BBM->end();
+            I != E; ++I) {
+          if (isa<SelectInst>(I) || isa<GetElementPtrInst>(I))
+            SelGEPInst++;            
+        }
+      }
+      // if do not have any select or getelementptr instructions in 
+      // current basic block and optimization level is -Os or -Oz then 
+      // skip the splice of the basic block.
+      if (!BBM || SelGEPInst != 0 || !BBM->getParent()->optForSize()) {
+         TII->removeBranch(*PrevBB);
          PrevBB->splice(PrevBB->end(), TailBB, TailBB->begin(), TailBB->end());
       }
+    }
     PrevBB->removeSuccessor(PrevBB->succ_begin());
     assert(PrevBB->succ_empty());
     PrevBB->transferSuccessors(TailBB);
     TDBBs.push_back(PrevBB);
     Changed = true;
   }
 
   // If this is after register allocation, there are no phis to fix.

lib/Transforms/Utils/SimplifyCFG.cpp

static bool FoldTwoEntryPHINode(PHINode *PN, const TargetTransformInfo &TTI,
                                 const DataLayout &DL) {
   // Ok, this is a two entry PHI node.  Check to see if this is a simple "if
   // statement", which has a very simple dominance structure.  Basically, we
   // are trying to find the condition that is being branched on, which
   // subsequently causes this merge to happen.  We really want control
   // dependence information for this check, but simplifycfg can't keep it up
   // to date, and this catches most of the cases we care about anyway.
   BasicBlock *BB = PN->getParent();
+  int IfBlock1Inst = 0;
+  int IfBlock2Inst = 0;
+  BasicBlock *IfBlock1 = PN->getIncomingBlock(0);
+  BasicBlock *IfBlock2 = PN->getIncomingBlock(1);
+
+  for (BasicBlock::iterator I = IfBlock1->begin(); !I->isTerminator(); ++I) {
+    if(!dyn_cast<BranchInst>(I))
+      IfBlock1Inst++;
+  }
+  for (BasicBlock::iterator I = IfBlock2->begin(); !I->isTerminator(); ++I) {
+    if(!dyn_cast<BranchInst>(I))
+      IfBlock2Inst++;
+  }
+
   const Function *Fn = BB->getParent();
+  // if optimization options is either -Oz or -Os and if have 
+  // less than two instrutions in if or else basic block return false.
+  if (Fn->optForSize() && IfBlock1Inst < 2 && IfBlock2Inst < 2)
+    return false;
+
   if (Fn && Fn->hasFnAttribute(Attribute::OptForFuzzing))
     return false;
 
   BasicBlock *IfTrue, *IfFalse;
   Value *IfCond = GetIfCondition(BB, IfTrue, IfFalse);
   if (!IfCond ||
       // Don't bother if the branch will be constant folded trivially.
       isa<ConstantInt>(IfCond))
if (PN->getType()->isIntegerTy(1) &&
        isa<BinaryOperator>(IfCond)))
     return false;
 
   // If all PHI nodes are promotable, check to make sure that all instructions
   // in the predecessor blocks can be promoted as well. If not, we won't be able
   // to get rid of the control flow, so it's not worth promoting to select
   // instructions.
   BasicBlock *DomBlock = nullptr;
-  BasicBlock *IfBlock1 = PN->getIncomingBlock(0);
-  BasicBlock *IfBlock2 = PN->getIncomingBlock(1);
   if (cast<BranchInst>(IfBlock1->getTerminator())->isConditional()) {
     IfBlock1 = nullptr;
   } else {
     DomBlock = *pred_begin(IfBlock1);
     for (BasicBlock::iterator I = IfBlock1->begin(); !I->isTerminator(); ++I)
       if (!AggressiveInsts.count(&*I) && !isa<DbgInfoIntrinsic>(I)) {
         // This is not an aggressive instruction that we can promote.
         // Because of this, we won't be able to get rid of the control flow, so
if (IfBlock1)
     hoistAllInstructionsInto(DomBlock, InsertPt, IfBlock1);
   if (IfBlock2)
     hoistAllInstructionsInto(DomBlock, InsertPt, IfBlock2);
 
   while (PHINode *PN = dyn_cast<PHINode>(BB->begin())) {
     // Change the PHI node into a select instruction.
     Value *TrueVal = PN->getIncomingValue(PN->getIncomingBlock(0) == IfFalse);
     Value *FalseVal = PN->getIncomingValue(PN->getIncomingBlock(0) == IfTrue);
     
     Value *Sel = Builder.CreateSelect(IfCond, TrueVal, FalseVal, "", InsertPt);
     PN->replaceAllUsesWith(Sel);
     Sel->takeName(PN);
     PN->eraseFromParent();
   }
   
   // At this point, IfBlock1 and IfBlock2 are both empty, so our if statement
   // has been flattened.  Change DomBlock to jump directly to our new block to
   // avoid other simplifycfg's kicking in on the diamond.
   Instruction *OldTI = DomBlock->getTerminator();
   Builder.SetInsertPoint(OldTI);
   Builder.CreateBr(BB);
   OldTI->eraseFromParent();
   return true;

test/CodeGen/AArch64/branches_are_betterthan_csels.ll

+;RUN: llc %s -o - -verify-machineinstrs | FileCheck %s
+
+target datalayout = "e-m:e-i8:8:32-i16:16:32-i64:64-i128:128-n32:64-S128"
+target triple = "aarch64-arm-none-eabi"
+
+; Function Attrs: minsize norecurse nounwind optsize readnone
+;CHECK-LABEL: @test
+;CHECK: cbz
+;CHECK: orr
+;CHECK-NEXT: ret
+;CHECK: and
+;CHECK-NOT: cmp
+;CHECK-NOT: csel
+define dso_local i32 @test(i32, i32) local_unnamed_addr #0 {
+  %3 = icmp eq i32 %1, 0
+  br i1 %3, label %6, label %4
+
+; <label>:4:                                      ; preds = %2
+  %5 = or i32 %0, 16
+  br label %8
+
+; <label>:6:                                      ; preds = %2
+  %7 = and i32 %0, -17
+  br label %8
+
+; <label>:8:                                      ; preds = %6, %4
+  %9 = phi i32 [ %5, %4 ], [ %7, %6 ]
+  ret i32 %9
+}
+
+attributes #0 = { minsize norecurse nounwind optsize readnone "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "less-precise-fpmad"="false" "min-legal-vector-width"="0" "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"="cortex-a53" "target-features"="+aes,+crc,+crypto,+fp-armv8,+neon,+sha2" "unsafe-fp-math"="false" "use-soft-float"="false" }
+
+!llvm.module.flags = !{!0}
+!llvm.ident = !{!1}
+
+!0 = !{i32 1, !"wchar_size", i32 4}
+!1 = !{!"clang version 9.0.0 (https://git.llvm.org/git/clang.git/ 2e53b8068e17d5347f6fc63e68faa2bf8531fb28) (https://git.llvm.org/git/llvm.git/ 4c1861d5b115a9ef6385f650b1ac70d75a7a29e5)"}