ARM: align loops to 4 bytes on Cortex-M3 and Cortex-M4.

[t.p.northover]

Summary

The Technical Reference Manuals for these two CPUs state that branching to an unaligned 32-bit instruction incurs an extra pipeline reload penalty. That's bad.

I also enable the optimization at -Os for just these two CPUs. My impression has been that it's a bit of a gamble with the bigger cores, and it also wastes more space. But for these two we're getting 1 cycle per iteration in return for 1 byte per loop (on average); that seems like it definitely fits into LLVM's quirky definition of -Os.

I'm open to extending it to other processors, but my research indicates Cortex-M0 is too simple to benefit (it claims conditional branches are always 3 cycles if taken), and Cortex-M7 has no performance documentation.

[dmgreen]

Good stuff. The downstream version of this we have uses Subtarget->isMClass() && Subtarget->hasThumb2(). (Dont ask me why it's downstream, I'm not sure. It's from before my time). I think you are right about the M7 though, the results there are just different, not necessarily better.

We should also be aligning functions?

And we should include the M33 and its derivatives (but like you said, not M0+/M23)

llvm/lib/CodeGen/MachineBlockPlacement.cpp

2500–2501

This seems like an odd change to make at Os. It, by definition, increases code size.

Like you said, this might be an llvm quirk though. Do you have a link to llvm's definition of -Os?

llvm/lib/Target/ARM/ARM.td

950

What do you think of using FeatureAlignBranchTargets or something like it?

llvm/lib/Target/ARM/ARMISelLowering.cpp

1204

Here with this gubbins may be a better place for setting the loop alignment.

[t.p.northover]

We should also be aligning functions?

Interesting question. There are a couple of reasons to think the tradeoffs are different there. First, I'd probably (based purely on intuition rather than data) expect a loop to be executed more times than most functions. Second, when r7 is the FP, a function is almost guaranteed to start with a 16-bit instruction (push {..., r7, lr}).

I do have a captive embedded developer who cares very much about individual cycles at the moment though, so I'll ask him to benchmark it.

Anyway, thanks for commenting. I'll get started on the obvious changes.

llvm/lib/CodeGen/MachineBlockPlacement.cpp

2500–2501

It's mostly in old threads, since our manuals are not great and a bit generic:

http://clang-developers.42468.n3.nabble.com/RFC-Codifying-but-not-formalizing-the-optimization-levels-in-LLVM-and-Clang-tt4029685.html#a4029741
http://clang-developers.42468.n3.nabble.com/Meaning-of-LLVM-optimization-levels-td4032493.html#a4032496

The first, particularly, is the understanding I've got.

llvm/lib/Target/ARM/ARM.td

950

An excellent idea.

llvm/lib/Target/ARM/ARMISelLowering.cpp

1204

Yep.

[dmgreen]

Interesting question. There are a couple of reasons to think the tradeoffs are different there. First, I'd probably (based purely on intuition rather than data) expect a loop to be executed more times than most functions. Second, when r7 is the FP, a function is almost guaranteed to start with a 16-bit instruction (push {..., r7, lr}).

The counter argument would be that in the case of function alignment, you don't need to execute the added NOP. For loops, there's always the small chance that you could be running an outer loop more than the inner one, leading to a executed nops that each take a cycle (unless it's the M33 and you get lucky with it's dual issue). If you don't care about the codesize, I think function alignment it will always be a win because the extra padding is just in unused space.

But let us know how the benchmarks look.

[t.p.northover]

I think I've implemented the suggested changes, except for the function alignment one.

The benchmarks came back as about a 0.2% difference in cycle count, and (crucially) there's no way when deciding function alignment to check for OptSize so we'd inevitably pessimize some cases.

[dmgreen]

The benchmarks came back as about a 0.2% difference in cycle count, and (crucially) there's no way when deciding function alignment to check for OptSize so we'd inevitably pessimize some cases.

I think this what getPrefAlignment is for? As opposed to MinFunctionAlignment? I agree that that's a different issue though, and doesn't need to be done with this.

Although I personally think the definition of Os is a bit odd, and this is increasing codesize, everyone else I've talked to agreed with you that this is fine. Like you said, in (almost) all cases we get a performance win for the bytes we spend.

So LGTM!

[t.p.northover]

Thanks. Committed as r342127.

llvm/include/llvm/CodeGen/TargetLowering.h

unsigned getPrefFunctionAlignment() const {
     return PrefFunctionAlignment;
   }
 
   /// Return the preferred loop alignment.
   virtual unsigned getPrefLoopAlignment(MachineLoop *ML = nullptr) const {
     return PrefLoopAlignment;
   }
 
+  /// Should loops be aligned even when the function is marked OptSize (but not
+  /// MinSize).
+  virtual bool alignLoopsWithOptSize() const {
+    return false;
+  }
+
   /// If the target has a standard location for the stack protector guard,
   /// returns the address of that location. Otherwise, returns nullptr.
   /// DEPRECATED: please override useLoadStackGuardNode and customize
   ///             LOAD_STACK_GUARD, or customize \@llvm.stackguard().
   virtual Value *getIRStackGuard(IRBuilder<> &IRB) const;
 
   /// Inserts necessary declarations for SSP (stack protection) purpose.
   /// Should be used only when getIRStackGuard returns nullptr.

llvm/lib/CodeGen/MachineBlockPlacement.cpp

 }
 
 void MachineBlockPlacement::alignBlocks() {
   // Walk through the backedges of the function now that we have fully laid out
   // the basic blocks and align the destination of each backedge. We don't rely
   // exclusively on the loop info here so that we can align backedges in
   // unnatural CFGs and backedges that were introduced purely because of the
   // loop rotations done during this layout pass.
-  if (F->getFunction().optForSize())
+  if (F->getFunction().optForMinSize() ||
+      (F->getFunction().optForSize() && !TLI->alignLoopsWithOptSize()))
     return;
   BlockChain &FunctionChain = *BlockToChain[&F->front()];
   if (FunctionChain.begin() == FunctionChain.end())
     return; // Empty chain.
 
   const BranchProbability ColdProb(1, 5); // 20%
   BlockFrequency EntryFreq = MBFI->getBlockFreq(&F->front());
   BlockFrequency WeightedEntryFreq = EntryFreq * ColdProb;

llvm/lib/Target/ARM/ARM.td

 def FeatureVMLxForwarding : SubtargetFeature<"vmlx-forwarding",
                                              "HasVMLxForwarding", "true",
                                              "Has multiplier accumulator forwarding">;
 
 // Disable 32-bit to 16-bit narrowing for experimentation.
 def FeaturePref32BitThumb : SubtargetFeature<"32bit", "Pref32BitThumb", "true",
                                              "Prefer 32-bit Thumb instrs">;
 
+def FeaturePrefLoopAlign32 : SubtargetFeature<"loop-align", "PrefLoopAlignment","2",
+                                              "Prefer 32-bit alignment for loops">;
+
 /// Some instructions update CPSR partially, which can add false dependency for
 /// out-of-order implementation, e.g. Cortex-A9, unless each individual bit is
 /// mapped to a separate physical register. Avoid partial CPSR update for these
 /// processors.
 def FeatureAvoidPartialCPSR : SubtargetFeature<"avoid-partial-cpsr",
                                                "AvoidCPSRPartialUpdate", "true",
                                  "Avoid CPSR partial update for OOO execution">;
 
def : ProcessorModel<"cortex-r8",   CortexA8Model,      [ARMv7r,
                                                          FeatureMP,
                                                          FeatureSlowFPBrcc,
                                                          FeatureHWDivARM,
                                                          FeatureHasSlowFPVMLx,
                                                          FeatureAvoidPartialCPSR]>;
 
 def : ProcessorModel<"cortex-m3", CortexM3Model,        [ARMv7m,
                                                          ProcM3,
+                                                         FeaturePrefLoopAlign32,
                                                          FeatureHasNoBranchPredictor]>;
 
 def : ProcessorModel<"sc300",     CortexM3Model,        [ARMv7m,
                                                          ProcM3,
                                                          FeatureHasNoBranchPredictor]>;
 
 def : ProcessorModel<"cortex-m4", CortexM3Model,        [ARMv7em,
                                                          FeatureVFP4,
                                                          FeatureVFPOnlySP,
                                                          FeatureD16,
+                                                         FeaturePrefLoopAlign32,
                                                          FeatureHasNoBranchPredictor]>;
 
 def : ProcNoItin<"cortex-m7",                           [ARMv7em,
                                                          FeatureFPARMv8,
                                                          FeatureD16]>;
 
 def : ProcNoItin<"cortex-m23",                          [ARMv8mBaseline,
                                                          FeatureNoMovt]>;
 
 def : ProcessorModel<"cortex-m33", CortexM3Model,       [ARMv8mMainline,
                                                          FeatureDSP,
                                                          FeatureFPARMv8,
                                                          FeatureD16,
                                                          FeatureVFPOnlySP,
+                                                         FeaturePrefLoopAlign32,
                                                          FeatureHasNoBranchPredictor]>;
 
 def : ProcNoItin<"cortex-a32",                           [ARMv8a,
                                                          FeatureHWDivThumb,
                                                          FeatureHWDivARM,
                                                          FeatureCrypto,
                                                          FeatureCRC]>;
 

llvm/lib/Target/ARM/ARMISelLowering.h

public:
     CCAssignFn *CCAssignFnForReturn(CallingConv::ID CC, bool isVarArg) const;
 
     /// Returns true if \p VecTy is a legal interleaved access type. This
     /// function checks the vector element type and the overall width of the
     /// vector.
     bool isLegalInterleavedAccessType(VectorType *VecTy,
                                       const DataLayout &DL) const;
 
+    bool alignLoopsWithOptSize() const override;
+
     /// Returns the number of interleaved accesses that will be generated when
     /// lowering accesses of the given type.
     unsigned getNumInterleavedAccesses(VectorType *VecTy,
                                        const DataLayout &DL) const;
 
     void finalizeLowering(MachineFunction &MF) const override;
 
     /// Return the correct alignment for the current calling convention.

llvm/lib/Target/ARM/ARMISelLowering.cpp

ARMTargetLowering::ARMTargetLowering(const TargetMachine &TM,
 
   // On ARM arguments smaller than 4 bytes are extended, so all arguments
   // are at least 4 bytes aligned.
   setMinStackArgumentAlignment(4);
 
   // Prefer likely predicted branches to selects on out-of-order cores.
   PredictableSelectIsExpensive = Subtarget->getSchedModel().isOutOfOrder();
 
+  setPrefLoopAlignment(Subtarget->getPrefLoopAlignment());
+
   setMinFunctionAlignment(Subtarget->isThumb() ? 1 : 2);
 }
 
 bool ARMTargetLowering::useSoftFloat() const {
   return Subtarget->useSoftFloat();
 }
 
 // FIXME: It might make sense to define the representative register class as the
 // nearest super-register that has a non-null superset. For example, DPR_VFP2 is
Value *ARMTargetLowering::emitStoreConditional(IRBuilder<> &Builder, Value *Val,
   Function *Strex = Intrinsic::getDeclaration(M, Int, Tys);
 
   return Builder.CreateCall(
       Strex, {Builder.CreateZExtOrBitCast(
                   Val, Strex->getFunctionType()->getParamType(0)),
               Addr});
 }
 
+
+bool ARMTargetLowering::alignLoopsWithOptSize() const {
+  return Subtarget->isMClass();
+}
+
 /// A helper function for determining the number of interleaved accesses we
 /// will generate when lowering accesses of the given type.
 unsigned
 ARMTargetLowering::getNumInterleavedAccesses(VectorType *VecTy,
                                              const DataLayout &DL) const {
   return (DL.getTypeSizeInBits(VecTy) + 127) / 128;
 }
 

llvm/lib/Target/ARM/ARMSubtarget.h

protected:
   /// What kind of timing do load multiple/store multiple have (double issue,
   /// single issue etc).
   ARMLdStMultipleTiming LdStMultipleTiming = SingleIssue;
 
   /// The adjustment that we need to apply to get the operand latency from the
   /// operand cycle returned by the itinerary data for pre-ISel operands.
   int PreISelOperandLatencyAdjustment = 2;
 
+  /// What alignment is preferred for loop bodies, in log2(bytes).
+  unsigned PrefLoopAlignment = 0;
+
   /// IsLittle - The target is Little Endian
   bool IsLittle;
 
   /// TargetTriple - What processor and OS we're targeting.
   Triple TargetTriple;
 
   /// SchedModel - Processor specific instruction costs.
   MCSchedModel SchedModel;
public:
   }
 
   /// Allow movt+movw for PIC global address calculation.
   /// ELF does not have GOT relocations for movt+movw.
   /// ROPI does not use GOT.
   bool allowPositionIndependentMovt() const {
     return isROPI() || !isTargetELF();
   }
+
+  unsigned getPrefLoopAlignment() const {
+    return PrefLoopAlignment;
+  }
 };
 
 } // end namespace llvm
 
 #endif  // LLVM_LIB_TARGET_ARM_ARMSUBTARGET_H

llvm/test/CodeGen/ARM/loop-align-cortex-m.ll

+; RUN: llc -mtriple=thumbv7m-none-eabi %s -mcpu=cortex-m3 -o - | FileCheck %s
+; RUN: llc -mtriple=thumbv7m-none-eabi %s -mcpu=cortex-m4 -o - | FileCheck %s
+; RUN: llc -mtriple=thumbv7m-none-eabi %s -mcpu=cortex-m33 -o - | FileCheck %s
+
+define void @test_loop_alignment(i32* %in, i32*  %out) optsize {
+; CHECK-LABEL: test_loop_alignment:
+; CHECK: movs {{r[0-9]+}}, #0
+; CHECK: .p2align 2
+
+entry:
+  br label %loop
+
+loop:
+  %i = phi i32 [ 0, %entry ], [ %i.next, %loop ]
+  %in.addr = getelementptr inbounds i32, i32* %in, i32 %i
+  %lhs = load i32, i32* %in.addr, align 4
+  %res = mul nsw i32 %lhs, 5
+  %out.addr = getelementptr inbounds i32, i32* %out, i32 %i
+  store i32 %res, i32* %out.addr, align 4
+  %i.next = add i32 %i, 1
+  %done = icmp eq i32 %i.next, 1024
+  br i1 %done, label %end, label %loop
+
+end:
+  ret void
+}
+
+define void @test_loop_alignment_minsize(i32* %in, i32*  %out) minsize {
+; CHECK-LABEL: test_loop_alignment_minsize:
+; CHECK: movs {{r[0-9]+}}, #0
+; CHECK-NOT: .p2align
+
+entry:
+  br label %loop
+
+loop:
+  %i = phi i32 [ 0, %entry ], [ %i.next, %loop ]
+  %in.addr = getelementptr inbounds i32, i32* %in, i32 %i
+  %lhs = load i32, i32* %in.addr, align 4
+  %res = mul nsw i32 %lhs, 5
+  %out.addr = getelementptr inbounds i32, i32* %out, i32 %i
+  store i32 %res, i32* %out.addr, align 4
+  %i.next = add i32 %i, 1
+  %done = icmp eq i32 %i.next, 1024
+  br i1 %done, label %end, label %loop
+
+end:
+  ret void
+}