From 167668f8c82fb49949a058c867ddabb0c1ec48fe Mon Sep 17 00:00:00 2001
From: Peter Collingbourne <peter@pcc.me.uk>
Date: Thu, 23 Apr 2015 20:31:35 +0000
Subject: [PATCH] Thumb2: When applying branch optimizations, visit branches in
 reverse order.

The order in which branches appear in ImmBranches is approximately their
order within the function body. By visiting later branches first, we reduce
the distance between earlier forward branches and their targets, making it
more likely that the cbn?z optimization, which can only apply to forward
branches, will succeed for those earlier branches.

Differential Revision: http://reviews.llvm.org/D9185

llvm-svn: 235640
---
 llvm/lib/Target/ARM/ARMConstantIslandPass.cpp |  9 ++++-
 llvm/test/CodeGen/Thumb2/cbnz.ll              | 54 +++++++++++++++++++++++++++
 2 files changed, 61 insertions(+), 2 deletions(-)
 create mode 100644 llvm/test/CodeGen/Thumb2/cbnz.ll

diff --git a/llvm/lib/Target/ARM/ARMConstantIslandPass.cpp b/llvm/lib/Target/ARM/ARMConstantIslandPass.cpp
index 00c92fc..e6d4b14 100644
--- a/llvm/lib/Target/ARM/ARMConstantIslandPass.cpp
+++ b/llvm/lib/Target/ARM/ARMConstantIslandPass.cpp
@@ -1745,8 +1745,13 @@ bool ARMConstantIslands::optimizeThumb2Instructions() {
 bool ARMConstantIslands::optimizeThumb2Branches() {
   bool MadeChange = false;
 
-  for (unsigned i = 0, e = ImmBranches.size(); i != e; ++i) {
-    ImmBranch &Br = ImmBranches[i];
+  // The order in which branches appear in ImmBranches is approximately their
+  // order within the function body. By visiting later branches first, we reduce
+  // the distance between earlier forward branches and their targets, making it
+  // more likely that the cbn?z optimization, which can only apply to forward
+  // branches, will succeed.
+  for (unsigned i = ImmBranches.size(); i != 0; --i) {
+    ImmBranch &Br = ImmBranches[i-1];
     unsigned Opcode = Br.MI->getOpcode();
     unsigned NewOpc = 0;
     unsigned Scale = 1;
diff --git a/llvm/test/CodeGen/Thumb2/cbnz.ll b/llvm/test/CodeGen/Thumb2/cbnz.ll
new file mode 100644
index 0000000..5c0bb5b
--- /dev/null
+++ b/llvm/test/CodeGen/Thumb2/cbnz.ll
@@ -0,0 +1,54 @@
+; RUN: llc -mtriple thumbv7-unknown-linux -o - %s | FileCheck %s
+
+declare void @x()
+declare void @y()
+
+define void @f(i32 %x, i32 %y) {
+  ; CHECK-LABEL: f:
+  ; CHECK: cbnz
+  %p = icmp eq i32 %x, 0
+  br i1 %p, label %t, label %f
+
+t:
+  call void @x()
+  call void @x()
+  call void @x()
+  call void @x()
+  call void @x()
+  call void @x()
+  call void @x()
+  call void @x()
+  call void @x()
+  call void @x()
+  call void @x()
+  call void @x()
+  call void @x()
+  call void @x()
+  call void @x()
+  call void @x()
+  ; CHECK: cbnz
+  %q = icmp eq i32 %y, 0
+  br i1 %q, label %t2, label %f
+
+t2:
+  call void @x()
+  call void @x()
+  call void @x()
+  call void @x()
+  call void @x()
+  call void @x()
+  call void @x()
+  call void @x()
+  call void @x()
+  call void @x()
+  call void @x()
+  call void @x()
+  call void @x()
+  call void @x()
+  call void @x()
+  br label %f
+
+f:
+  call void @y()
+  ret void
+}
-- 
2.7.4