code size reduction using ext-tsp block placement

[spupyrev]

Summary

[this is an experimental diff, not yet ready for review]

Building the binary of clang (revision_10) with -DCMAKE_BUILD_TYPE=MinSizeRel

-enable-ext-tsp-block-placement=0 (default)
binary size: 746405864

-enable-ext-tsp-block-placement=1 (OLD)
binary size: 754066000 (+1.03%)

-enable-ext-tsp-block-placement=1 (NEW)
binary size: 745735520 (-0.1%)

llvm/lib/CodeGen/MachineBlockPlacement.cpp

void MachineBlockPlacement::applyExtTsp() {
   std::vector<const MachineBasicBlock *> CurrentBlockOrder;
   CurrentBlockOrder.reserve(F->size());
   size_t NumBlocks = 0;
   for (const MachineBasicBlock &MBB : *F) {
     BlockIndex[&MBB] = NumBlocks++;
     CurrentBlockOrder.push_back(&MBB);
   }
 
+  bool OptForSize = F->getFunction().hasOptSize() ||
+                    llvm::shouldOptimizeForSize(F, PSI, &MBFI->getMBFI());
+
   auto BlockSizes = std::vector<uint64_t>(F->size());
   auto BlockCounts = std::vector<uint64_t>(F->size());
   DenseMap<std::pair<uint64_t, uint64_t>, uint64_t> JumpCounts;
   for (MachineBasicBlock &MBB : *F) {
     // Getting the block frequency.
     BlockFrequency BlockFreq = MBFI->getBlockFreq(&MBB);
+    if (!OptForSize)
       BlockCounts[BlockIndex[&MBB]] = BlockFreq.getFrequency();
+    else
+      BlockCounts[BlockIndex[&MBB]] = MBB.pred_size();
     // Getting the block size:
     // - approximate the size of an instruction by 4 bytes, and
     // - ignore debug instructions.
     // Note: getting the exact size of each block is target-dependent and can be
     // done by extending the interface of MCCodeEmitter. Experimentally we do
     // not see a perf improvement with the exact block sizes.
     auto NonDbgInsts =
         instructionsWithoutDebug(MBB.instr_begin(), MBB.instr_end());
     int NumInsts = std::distance(NonDbgInsts.begin(), NonDbgInsts.end());
     BlockSizes[BlockIndex[&MBB]] = 4 * NumInsts;
     // Getting jump frequencies.
     for (MachineBasicBlock *Succ : MBB.successors()) {
       auto EP = MBPI->getEdgeProbability(&MBB, Succ);
       BlockFrequency EdgeFreq = BlockFreq * EP;
       auto Edge = std::make_pair(BlockIndex[&MBB], BlockIndex[Succ]);
+      if (!OptForSize)
         JumpCounts[Edge] = EdgeFreq.getFrequency();
+      else
+        JumpCounts[Edge] = MBB.succ_size() == 1 ? 100 : 1;
     }
   }
 
   LLVM_DEBUG(dbgs() << "Applying ext-tsp layout for |V| = " << F->size()
                     << " with profile = " << F->getFunction().hasProfileData()
                     << " (" << F->getName().str() << ")"
                     << "\n");
   LLVM_DEBUG(