Coverage Report

Created: 2017-10-03 07:32

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