[Hexagon] Handle non-aligned offsets in globals in extender optimization

Instructions like memd(r0+##global+1) are legal as long as the entire
address is properly aligned. Assuming that "global" is aligned at an
8-byte boundary, the expression "global+1" appears to be misaligned.
Handle such cases in HexagonConstExtenders, and make sure that any non-
extended offsets generated are still aligned accordingly.

llvm-svn: 323799

1 files changed, 52 insertions, 18 deletions

diff --git a/llvm/lib/Target/Hexagon/HexagonConstExtenders.cpp b/llvm/lib/Target/Hexagon/HexagonConstExtenders.cpp
index dd759fe9ce5..88b5e808271 100644
--- a/llvm/lib/Target/Hexagon/HexagonConstExtenders.cpp
+++ b/llvm/lib/Target/Hexagon/HexagonConstExtenders.cpp
@@ -39,18 +39,43 @@ namespace llvm {
   FunctionPass *createHexagonConstExtenders();
 }
 
+static int32_t adjustUp(int32_t V, uint8_t A, uint8_t O) {
+  assert(isPowerOf2_32(A));
+  int32_t U = (V & -A) + O;
+  return U >= V ? U : U+A;
+}
+
+static int32_t adjustDown(int32_t V, uint8_t A, uint8_t O) {
+  assert(isPowerOf2_32(A));
+  int32_t U = (V & -A) + O;
+  return U <= V ? U : U-A;
+}
+
 namespace {
   struct OffsetRange {
+    // The range of values between Min and Max that are of form Align*N+Offset,
+    // for some integer N. Min and Max are required to be of that form as well,
+    // except in the case of an empty range.
     int32_t Min = INT_MIN, Max = INT_MAX;
     uint8_t Align = 1;
+    uint8_t Offset = 0;
 
     OffsetRange() = default;
-    OffsetRange(int32_t L, int32_t H, uint8_t A)
-      : Min(L), Max(H), Align(A) {}
+    OffsetRange(int32_t L, int32_t H, uint8_t A, uint8_t O = 0)
+      : Min(L), Max(H), Align(A), Offset(O) {}
     OffsetRange &intersect(OffsetRange A) {
-      Align = std::max(Align, A.Align);
-      Min = std::max(Min, A.Min);
-      Max = std::min(Max, A.Max);
+      if (Align < A.Align)
+        std::swap(*this, A);
+
+      // Align >= A.Align.
+      if (Offset >= A.Offset && (Offset - A.Offset) % A.Align == 0) {
+        Min = adjustUp(std::max(Min, A.Min), Align, Offset);
+        Max = adjustDown(std::min(Max, A.Max), Align, Offset);
+      } else {
+        // Make an empty range.
+        Min = 0;
+        Max = -1;
+      }
       // Canonicalize empty ranges.
       if (Min > Max)
         std::tie(Min, Max, Align) = std::make_tuple(0, -1, 1);
@@ -59,10 +84,12 @@ namespace {
     OffsetRange &shift(int32_t S) {
       Min += S;
       Max += S;
+      Offset = (Offset+S) % Align;
       return *this;
     }
     OffsetRange &extendBy(int32_t D) {
       // If D < 0, extend Min, otherwise extend Max.
+      assert(D % Align == 0);
       if (D < 0)
         Min = (INT_MIN-D < Min) ? Min+D : INT_MIN;
       else
@@ -73,7 +100,7 @@ namespace {
       return Min > Max;
     }
     bool contains(int32_t V) const {
-      return Min <= V && V <= Max && (V % Align) == 0;
+      return Min <= V && V <= Max && (V-Offset) % Align == 0;
     }
     bool operator==(const OffsetRange &R) const {
       return Min == R.Min && Max == R.Max && Align == R.Align;
@@ -407,7 +434,8 @@ namespace {
   raw_ostream &operator<< (raw_ostream &OS, const OffsetRange &OR) {
     if (OR.Min > OR.Max)
       OS << '!';
-    OS << '[' << OR.Min << ',' << OR.Max << "]a" << unsigned(OR.Align);
+    OS << '[' << OR.Min << ',' << OR.Max << "]a" << unsigned(OR.Align)
+       << '+' << unsigned(OR.Offset);
     return OS;
   }
 
@@ -1283,11 +1311,17 @@ void HCE::assignInits(const ExtRoot &ER, unsigned Begin, unsigned End,
   SmallVector<RangeTree::Node*,8> Nodes;
   Tree.order(Nodes);
 
-  auto MaxAlign = [](const SmallVectorImpl<RangeTree::Node*> &Nodes) {
-    uint8_t Align = 1;
-    for (RangeTree::Node *N : Nodes)
-      Align = std::max(Align, N->Range.Align);
-    return Align;
+  auto MaxAlign = [](const SmallVectorImpl<RangeTree::Node*> &Nodes,
+                     uint8_t Align, uint8_t Offset) {
+    for (RangeTree::Node *N : Nodes) {
+      if (N->Range.Align <= Align || N->Range.Offset < Offset)
+        continue;
+      if ((N->Range.Offset - Offset) % Align != 0)
+        continue;
+      Align = N->Range.Align;
+      Offset = N->Range.Offset;
+    }
+    return std::make_pair(Align, Offset);
   };
 
   // Construct the set of all potential definition points from the endpoints
@@ -1297,14 +1331,14 @@ void HCE::assignInits(const ExtRoot &ER, unsigned Begin, unsigned End,
   std::set<int32_t> CandSet;
   for (RangeTree::Node *N : Nodes) {
     const OffsetRange &R = N->Range;
-    uint8_t A0 = MaxAlign(Tree.nodesWith(R.Min, false));
+    auto P0 = MaxAlign(Tree.nodesWith(R.Min, false), R.Align, R.Offset);
     CandSet.insert(R.Min);
-    if (R.Align < A0)
-      CandSet.insert(R.Min < 0 ? -alignDown(-R.Min, A0) : alignTo(R.Min, A0));
-    uint8_t A1 = MaxAlign(Tree.nodesWith(R.Max, false));
+    if (R.Align < P0.first)
+      CandSet.insert(adjustUp(R.Min, P0.first, P0.second));
+    auto P1 = MaxAlign(Tree.nodesWith(R.Max, false), R.Align, R.Offset);
     CandSet.insert(R.Max);
-    if (R.Align < A1)
-      CandSet.insert(R.Max < 0 ? -alignTo(-R.Max, A1) : alignDown(R.Max, A1));
+    if (R.Align < P1.first)
+      CandSet.insert(adjustDown(R.Max, P1.first, P1.second));
   }
 
   // Build the assignment map: candidate C -> { list of extender indexes }.