[PowerPC][Future] Branch Distance Estimation For Prefixed Instructions

[stefanp]

Summary

By adding the prefixed instructions the branch distances are no longer computed correctly. Since prefixed instructions cannot cross a 64 byte boundary we have to assume that a prefixed instruction may have a nop prepended to it. This patch tries to take that nop into consideration when computing the size of basic blocks.

[stefanp]

Added full context.

[nemanjai]

Aside from a couple of minor nits, LGTM.

llvm/lib/Target/PowerPC/PPCBranchSelector.cpp

161

s/You cannot have/It is not possible for

llvm/test/CodeGen/PowerPC/alignlongjumptest.mir

2

Minor nit: since you are splitting the run directives across multiple lines, might as well keep them to 80 columns. It appears that this is a bit wider.

[stefanp]

Addressed review comments.

[amyk]

llvm/lib/Target/PowerPC/PPCBranchSelector.cpp

151

s/iteself/itself

llvm/lib/Target/PowerPC/PPCBranchSelector.cpp

 #include "llvm/Support/MathExtras.h"
 #include "llvm/Target/TargetMachine.h"
 #include <algorithm>
 using namespace llvm;
 
 #define DEBUG_TYPE "ppc-branch-select"
 
 STATISTIC(NumExpanded, "Number of branches expanded to long format");
+STATISTIC(NumPrefixed, "Number of prefixed instructions");
+STATISTIC(NumPrefixedAligned,
+          "Number of prefixed instructions that have been aligned");
 
 namespace {
   struct PPCBSel : public MachineFunctionPass {
     static char ID;
     PPCBSel() : MachineFunctionPass(ID) {
       initializePPCBSelPass(*PassRegistry::getPassRegistry());
     }
 
if (MBB->getNumber() > 0) {
       auto &BS = BlockSizes[MBB->getNumber()-1];
       BS.first += AlignExtra;
       BS.second = AlignExtra;
 
       FuncSize += AlignExtra;
     }
 
     unsigned BlockSize = 0;
+    unsigned UnalignedBytesRemaining = 0;
     for (MachineInstr &MI : *MBB) {
-      BlockSize += TII->getInstSizeInBytes(MI);
+      unsigned MINumBytes = TII->getInstSizeInBytes(MI);
       if (MI.isInlineAsm() && (FirstImpreciseBlock < 0))
         FirstImpreciseBlock = MBB->getNumber();
+      if (TII->isPrefixed(MI.getOpcode())) {
+        NumPrefixed++;
+
+        // All 8 byte instructions may require alignment. Each 8 byte
+        // instruction may be aligned by another 4 bytes.
+        // This means that an 8 byte instruction may require 12 bytes
+        // (8 for the instruction iteself and 4 for the alignment nop).
+        // This will happen if an 8 byte instruction can be aligned to 64 bytes
+        // by only adding a 4 byte nop.
+        // We don't know the alignment at this point in the code so we have to
+        // adopt a more pessimistic approach. If an instruction may need
+        // alignment we assume that it does need alignment and add 4 bytes to
+        // it. As a result we may end up with more long branches than before
+        // but we are in the safe position where if we need a long branch we
+        // have one.
+        // The if statement checks to make sure that two 8 byte instructions
+        // are at least 64 bytes away from each other. You cannot have two
+        // instructions that both need alignment that are within 64 bytes of
+        // each other.
+        if (!UnalignedBytesRemaining) {
+          BlockSize += 4;
+          UnalignedBytesRemaining = 60;
+          NumPrefixedAligned++;
+        }
+      }
+      UnalignedBytesRemaining -= std::min(UnalignedBytesRemaining, MINumBytes);
+      BlockSize += MINumBytes;
     }
 
     BlockSizes[MBB->getNumber()].first = BlockSize;
     FuncSize += BlockSize;
   }
 
   return FuncSize;
 }

llvm/test/CodeGen/PowerPC/alignlongjumptest.mir

+# RUN: llc -mcpu=future -mtriple=powerpc64le-unknown-unknown %s \
+# RUN:   -start-before=ppc-branch-select -verify-machineinstrs -filetype=obj -o - | \
+# RUN:   llvm-objdump -mcpu=future -d -r - | FileCheck --check-prefix=CHECK-LE %s
+# RUN: llc -mcpu=future -mtriple=powerpc64-unknown-unknown %s \
+# RUN:   -start-before=ppc-branch-select -verify-machineinstrs -filetype=obj -o - | \
+# RUN:   llvm-objdump -mcpu=future -d -r - | FileCheck --check-prefix=CHECK-BE %s
+
+# The purpose of this test is to check that long branches are selected correctly
+# when we have prefixed instructions that may require alignment. Prefixed
+# instructions may require alignment and so an additional 4 bytes may be added.
+# If those 4 bytes put the target of the branch past the range of a short branch
+# then we should use a long branch like in this test.
+
+---
+name:            longbranchtest
+alignment:       16
+exposesReturnsTwice: false
+legalized:       false
+regBankSelected: false
+selected:        false
+failedISel:      false
+tracksRegLiveness: true
+hasWinCFI:       false
+registers:       []
+liveins:
+  - { reg: '$x3', virtual-reg: '' }
+frameInfo:
+  isFrameAddressTaken: false
+  isReturnAddressTaken: false
+  hasStackMap:     false
+  hasPatchPoint:   false
+  stackSize:       0
+  offsetAdjustment: 0
+  maxAlignment:    1
+  adjustsStack:    false
+  hasCalls:        false
+  stackProtector:  ''
+  maxCallFrameSize: 0
+  cvBytesOfCalleeSavedRegisters: 0
+  hasOpaqueSPAdjustment: false
+  hasVAStart:      false
+  hasMustTailInVarArgFunc: false
+  localFrameSize:  0
+  savePoint:       ''
+  restorePoint:    ''
+fixedStack:      []
+stack:           []
+callSites:       []
+constants:       []
+machineFunctionInfo: {}
+body:             |
+  bb.0.entry:
+    successors: %bb.1(0x30000000), %bb.2(0x50000000)
+    liveins: $x3
+    renamable $cr0 = CMPLWI killed renamable $r3, 0, implicit $x3
+    BCC 76, killed renamable $cr0, %bb.1
+  bb.2:
+    renamable $x3 = LI8 2
+    INLINEASM &".space 32744", 1
+    renamable $x3 = PADDI8 $x3, 13
+    BLR8 implicit $lr8, implicit $rm, implicit killed $x3
+  bb.1:
+    renamable $x3 = LI8 1
+    INLINEASM &".space 32744", 1
+    renamable $x3 = PADDI8 $x3, 21
+    BLR8 implicit $lr8, implicit $rm, implicit killed $x3
+
+...
+
+# Check for the long branch.
+# CHECK-LE:         08 00 82 4{{[01]}}   b{{[tf]}}  2, .+8
+# CHECK-LE-NEXT:    fc 7f 00 48   b .+32764
+# CHECK-LE-DAG:     paddi 3, 3, 13, 0
+# CHECK-LE-DAG:     paddi 3, 3, 21, 0
+# CHECK-LE:         blr
+# CHECK-BE:         4{{[01]}} 82 00 08   b{{[tf]}}  2, .+8
+# CHECK-BE-NEXT:    48 00 7f fc   b .+32764
+# CHECK-BE-DAG:     paddi 3, 3, 13, 0
+# CHECK-BE-DAG:     paddi 3, 3, 21, 0
+# CHECK-BE:         blr
+
+