Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/Target/Hexagon/HexagonBranchRelaxation.cpp
Line
Count
Source (jump to first uncovered line)
1
//===--- HexagonBranchRelaxation.cpp - Identify and relax long jumps ------===//
2
//
3
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4
// See https://llvm.org/LICENSE.txt for license information.
5
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6
//
7
//===----------------------------------------------------------------------===//
8
9
#define DEBUG_TYPE "hexagon-brelax"
10
11
#include "Hexagon.h"
12
#include "HexagonInstrInfo.h"
13
#include "HexagonSubtarget.h"
14
#include "llvm/ADT/DenseMap.h"
15
#include "llvm/ADT/SmallVector.h"
16
#include "llvm/ADT/StringRef.h"
17
#include "llvm/CodeGen/MachineBasicBlock.h"
18
#include "llvm/CodeGen/MachineFunction.h"
19
#include "llvm/CodeGen/MachineFunctionPass.h"
20
#include "llvm/CodeGen/MachineInstr.h"
21
#include "llvm/CodeGen/MachineOperand.h"
22
#include "llvm/CodeGen/Passes.h"
23
#include "llvm/Pass.h"
24
#include "llvm/Support/CommandLine.h"
25
#include "llvm/Support/Debug.h"
26
#include "llvm/Support/raw_ostream.h"
27
#include <cassert>
28
#include <cstdint>
29
#include <cstdlib>
30
#include <iterator>
31
32
using namespace llvm;
33
34
// Since we have no exact knowledge of code layout, allow some safety buffer
35
// for jump target. This is measured in bytes.
36
static cl::opt<uint32_t> BranchRelaxSafetyBuffer("branch-relax-safety-buffer",
37
  cl::init(200), cl::Hidden, cl::ZeroOrMore, cl::desc("safety buffer size"));
38
39
namespace llvm {
40
41
  FunctionPass *createHexagonBranchRelaxation();
42
  void initializeHexagonBranchRelaxationPass(PassRegistry&);
43
44
} // end namespace llvm
45
46
namespace {
47
48
  struct HexagonBranchRelaxation : public MachineFunctionPass {
49
  public:
50
    static char ID;
51
52
919
    HexagonBranchRelaxation() : MachineFunctionPass(ID) {
53
919
      initializeHexagonBranchRelaxationPass(*PassRegistry::getPassRegistry());
54
919
    }
55
56
    bool runOnMachineFunction(MachineFunction &MF) override;
57
58
5.88k
    StringRef getPassName() const override {
59
5.88k
      return "Hexagon Branch Relaxation";
60
5.88k
    }
61
62
915
    void getAnalysisUsage(AnalysisUsage &AU) const override {
63
915
      AU.setPreservesCFG();
64
915
      MachineFunctionPass::getAnalysisUsage(AU);
65
915
    }
66
67
  private:
68
    const HexagonInstrInfo *HII;
69
    const HexagonRegisterInfo *HRI;
70
71
    bool relaxBranches(MachineFunction &MF);
72
    void computeOffset(MachineFunction &MF,
73
          DenseMap<MachineBasicBlock*, unsigned> &BlockToInstOffset);
74
    bool reGenerateBranch(MachineFunction &MF,
75
          DenseMap<MachineBasicBlock*, unsigned> &BlockToInstOffset);
76
    bool isJumpOutOfRange(MachineInstr &MI,
77
          DenseMap<MachineBasicBlock*, unsigned> &BlockToInstOffset);
78
  };
79
80
  char HexagonBranchRelaxation::ID = 0;
81
82
} // end anonymous namespace
83
84
INITIALIZE_PASS(HexagonBranchRelaxation, "hexagon-brelax",
85
                "Hexagon Branch Relaxation", false, false)
86
87
919
FunctionPass *llvm::createHexagonBranchRelaxation() {
88
919
  return new HexagonBranchRelaxation();
89
919
}
90
91
4.97k
bool HexagonBranchRelaxation::runOnMachineFunction(MachineFunction &MF) {
92
4.97k
  LLVM_DEBUG(dbgs() << "****** Hexagon Branch Relaxation ******\n");
93
4.97k
94
4.97k
  auto &HST = MF.getSubtarget<HexagonSubtarget>();
95
4.97k
  HII = HST.getInstrInfo();
96
4.97k
  HRI = HST.getRegisterInfo();
97
4.97k
98
4.97k
  bool Changed = false;
99
4.97k
  Changed = relaxBranches(MF);
100
4.97k
  return Changed;
101
4.97k
}
102
103
void HexagonBranchRelaxation::computeOffset(MachineFunction &MF,
104
4.97k
      DenseMap<MachineBasicBlock*, unsigned> &OffsetMap) {
105
4.97k
  // offset of the current instruction from the start.
106
4.97k
  unsigned InstOffset = 0;
107
6.64k
  for (auto &B : MF) {
108
6.64k
    if (B.getAlignment()) {
109
404
      // Although we don't know the exact layout of the final code, we need
110
404
      // to account for alignment padding somehow. This heuristic pads each
111
404
      // aligned basic block according to the alignment value.
112
404
      int ByteAlign = (1u << B.getAlignment()) - 1;
113
404
      InstOffset = (InstOffset + ByteAlign) & ~(ByteAlign);
114
404
    }
115
6.64k
    OffsetMap[&B] = InstOffset;
116
33.9k
    for (auto &MI : B.instrs()) {
117
33.9k
      InstOffset += HII->getSize(MI);
118
33.9k
      // Assume that all extendable branches will be extended.
119
33.9k
      if (MI.isBranch() && 
HII->isExtendable(MI)4.29k
)
120
896
        InstOffset += HEXAGON_INSTR_SIZE;
121
33.9k
    }
122
6.64k
  }
123
4.97k
}
124
125
/// relaxBranches - For Hexagon, if the jump target/loop label is too far from
126
/// the jump/loop instruction then, we need to make sure that we have constant
127
/// extenders set for jumps and loops.
128
129
/// There are six iterations in this phase. It's self explanatory below.
130
4.97k
bool HexagonBranchRelaxation::relaxBranches(MachineFunction &MF) {
131
4.97k
  // Compute the offset of each basic block
132
4.97k
  // offset of the current instruction from the start.
133
4.97k
  // map for each instruction to the beginning of the function
134
4.97k
  DenseMap<MachineBasicBlock*, unsigned> BlockToInstOffset;
135
4.97k
  computeOffset(MF, BlockToInstOffset);
136
4.97k
137
4.97k
  return reGenerateBranch(MF, BlockToInstOffset);
138
4.97k
}
139
140
/// Check if a given instruction is:
141
/// - a jump to a distant target
142
/// - that exceeds its immediate range
143
/// If both conditions are true, it requires constant extension.
144
bool HexagonBranchRelaxation::isJumpOutOfRange(MachineInstr &MI,
145
4.29k
      DenseMap<MachineBasicBlock*, unsigned> &BlockToInstOffset) {
146
4.29k
  MachineBasicBlock &B = *MI.getParent();
147
4.29k
  auto FirstTerm = B.getFirstInstrTerminator();
148
4.29k
  if (FirstTerm == B.instr_end())
149
0
    return false;
150
4.29k
151
4.29k
  if (HII->isExtended(MI))
152
6
    return false;
153
4.29k
154
4.29k
  unsigned InstOffset = BlockToInstOffset[&B];
155
4.29k
  unsigned Distance = 0;
156
4.29k
157
4.29k
  // To save time, estimate exact position of a branch instruction
158
4.29k
  // as one at the end of the MBB.
159
4.29k
  // Number of instructions times typical instruction size.
160
4.29k
  InstOffset += HII->nonDbgBBSize(&B) * HEXAGON_INSTR_SIZE;
161
4.29k
162
4.29k
  MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
163
4.29k
  SmallVector<MachineOperand, 4> Cond;
164
4.29k
165
4.29k
  // Try to analyze this branch.
166
4.29k
  if (HII->analyzeBranch(B, TBB, FBB, Cond, false)) {
167
3.23k
    // Could not analyze it. See if this is something we can recognize.
168
3.23k
    // If it is a NVJ, it should always have its target in
169
3.23k
    // a fixed location.
170
3.23k
    if (HII->isNewValueJump(*FirstTerm))
171
0
      TBB = FirstTerm->getOperand(HII->getCExtOpNum(*FirstTerm)).getMBB();
172
3.23k
  }
173
4.29k
  if (TBB && 
&MI == &*FirstTerm1.05k
) {
174
1.00k
    Distance = std::abs((long long)InstOffset - BlockToInstOffset[TBB])
175
1.00k
                + BranchRelaxSafetyBuffer;
176
1.00k
    return !HII->isJumpWithinBranchRange(*FirstTerm, Distance);
177
1.00k
  }
178
3.28k
  if (FBB) {
179
53
    // Look for second terminator.
180
53
    auto SecondTerm = std::next(FirstTerm);
181
53
    assert(SecondTerm != B.instr_end() &&
182
53
          (SecondTerm->isBranch() || SecondTerm->isCall()) &&
183
53
          "Bad second terminator");
184
53
    if (&MI != &*SecondTerm)
185
0
      return false;
186
53
    // Analyze the second branch in the BB.
187
53
    Distance = std::abs((long long)InstOffset - BlockToInstOffset[FBB])
188
53
                + BranchRelaxSafetyBuffer;
189
53
    return !HII->isJumpWithinBranchRange(*SecondTerm, Distance);
190
53
  }
191
3.23k
  return false;
192
3.23k
}
193
194
bool HexagonBranchRelaxation::reGenerateBranch(MachineFunction &MF,
195
4.97k
      DenseMap<MachineBasicBlock*, unsigned> &BlockToInstOffset) {
196
4.97k
  bool Changed = false;
197
4.97k
198
6.64k
  for (auto &B : MF) {
199
33.9k
    for (auto &MI : B) {
200
33.9k
      if (!MI.isBranch() || 
!isJumpOutOfRange(MI, BlockToInstOffset)4.29k
)
201
33.7k
        continue;
202
231
      LLVM_DEBUG(dbgs() << "Long distance jump. isExtendable("
203
231
                        << HII->isExtendable(MI) << ") isConstExtended("
204
231
                        << HII->isConstExtended(MI) << ") " << MI);
205
231
206
231
      // Since we have not merged HW loops relaxation into
207
231
      // this code (yet), soften our approach for the moment.
208
231
      if (!HII->isExtendable(MI) && !HII->isExtended(MI)) {
209
231
        LLVM_DEBUG(dbgs() << "\tUnderimplemented relax branch instruction.\n");
210
231
      } else {
211
0
        // Find which operand is expandable.
212
0
        int ExtOpNum = HII->getCExtOpNum(MI);
213
0
        MachineOperand &MO = MI.getOperand(ExtOpNum);
214
0
        // This need to be something we understand. So far we assume all
215
0
        // branches have only MBB address as expandable field.
216
0
        // If it changes, this will need to be expanded.
217
0
        assert(MO.isMBB() && "Branch with unknown expandable field type");
218
0
        // Mark given operand as extended.
219
0
        MO.addTargetFlag(HexagonII::HMOTF_ConstExtended);
220
0
        Changed = true;
221
0
      }
222
231
    }
223
6.64k
  }
224
4.97k
  return Changed;
225
4.97k
}