Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/Target/X86/X86PadShortFunction.cpp
Line
Count
Source (jump to first uncovered line)
1
//===-------- X86PadShortFunction.cpp - pad short functions -----------===//
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
// This file defines the pass which will pad short functions to prevent
10
// a stall if a function returns before the return address is ready. This
11
// is needed for some Intel Atom processors.
12
//
13
//===----------------------------------------------------------------------===//
14
15
16
#include "X86.h"
17
#include "X86InstrInfo.h"
18
#include "X86Subtarget.h"
19
#include "llvm/ADT/Statistic.h"
20
#include "llvm/CodeGen/MachineFunctionPass.h"
21
#include "llvm/CodeGen/MachineInstrBuilder.h"
22
#include "llvm/CodeGen/Passes.h"
23
#include "llvm/CodeGen/TargetSchedule.h"
24
#include "llvm/IR/Function.h"
25
#include "llvm/Support/Debug.h"
26
#include "llvm/Support/raw_ostream.h"
27
28
using namespace llvm;
29
30
#define DEBUG_TYPE "x86-pad-short-functions"
31
32
STATISTIC(NumBBsPadded, "Number of basic blocks padded");
33
34
namespace {
35
  struct VisitedBBInfo {
36
    // HasReturn - Whether the BB contains a return instruction
37
    bool HasReturn;
38
39
    // Cycles - Number of cycles until return if HasReturn is true, otherwise
40
    // number of cycles until end of the BB
41
    unsigned int Cycles;
42
43
100
    VisitedBBInfo() : HasReturn(false), Cycles(0) {}
44
    VisitedBBInfo(bool HasReturn, unsigned int Cycles)
45
100
      : HasReturn(HasReturn), Cycles(Cycles) {}
46
  };
47
48
  struct PadShortFunc : public MachineFunctionPass {
49
    static char ID;
50
    PadShortFunc() : MachineFunctionPass(ID)
51
11.4k
                   , Threshold(4) {}
52
53
    bool runOnMachineFunction(MachineFunction &MF) override;
54
55
11.3k
    MachineFunctionProperties getRequiredProperties() const override {
56
11.3k
      return MachineFunctionProperties().set(
57
11.3k
          MachineFunctionProperties::Property::NoVRegs);
58
11.3k
    }
59
60
146k
    StringRef getPassName() const override {
61
146k
      return "X86 Atom pad short functions";
62
146k
    }
63
64
  private:
65
    void findReturns(MachineBasicBlock *MBB,
66
                     unsigned int Cycles = 0);
67
68
    bool cyclesUntilReturn(MachineBasicBlock *MBB,
69
                           unsigned int &Cycles);
70
71
    void addPadding(MachineBasicBlock *MBB,
72
                    MachineBasicBlock::iterator &MBBI,
73
                    unsigned int NOOPsToAdd);
74
75
    const unsigned int Threshold;
76
77
    // ReturnBBs - Maps basic blocks that return to the minimum number of
78
    // cycles until the return, starting from the entry block.
79
    DenseMap<MachineBasicBlock*, unsigned int> ReturnBBs;
80
81
    // VisitedBBs - Cache of previously visited BBs.
82
    DenseMap<MachineBasicBlock*, VisitedBBInfo> VisitedBBs;
83
84
    TargetSchedModel TSM;
85
  };
86
87
  char PadShortFunc::ID = 0;
88
}
89
90
11.3k
FunctionPass *llvm::createX86PadShortFunctions() {
91
11.3k
  return new PadShortFunc();
92
11.3k
}
93
94
/// runOnMachineFunction - Loop over all of the basic blocks, inserting
95
/// NOOP instructions before early exits.
96
135k
bool PadShortFunc::runOnMachineFunction(MachineFunction &MF) {
97
135k
  if (skipFunction(MF.getFunction()))
98
196
    return false;
99
135k
100
135k
  if (MF.getFunction().hasOptSize())
101
1.91k
    return false;
102
133k
103
133k
  if (!MF.getSubtarget<X86Subtarget>().padShortFunctions())
104
133k
    return false;
105
84
106
84
  TSM.init(&MF.getSubtarget());
107
84
108
84
  // Search through basic blocks and mark the ones that have early returns
109
84
  ReturnBBs.clear();
110
84
  VisitedBBs.clear();
111
84
  findReturns(&MF.front());
112
84
113
84
  bool MadeChange = false;
114
84
115
84
  // Pad the identified basic blocks with NOOPs
116
84
  for (DenseMap<MachineBasicBlock*, unsigned int>::iterator I = ReturnBBs.begin();
117
108
       I != ReturnBBs.end(); 
++I24
) {
118
24
    MachineBasicBlock *MBB = I->first;
119
24
    unsigned Cycles = I->second;
120
24
121
24
    if (Cycles < Threshold) {
122
24
      // BB ends in a return. Skip over any DBG_VALUE instructions
123
24
      // trailing the terminator.
124
24
      assert(MBB->size() > 0 &&
125
24
             "Basic block should contain at least a RET but is empty");
126
24
      MachineBasicBlock::iterator ReturnLoc = --MBB->end();
127
24
128
24
      while (ReturnLoc->isDebugInstr())
129
0
        --ReturnLoc;
130
24
      assert(ReturnLoc->isReturn() && !ReturnLoc->isCall() &&
131
24
             "Basic block does not end with RET");
132
24
133
24
      addPadding(MBB, ReturnLoc, Threshold - Cycles);
134
24
      NumBBsPadded++;
135
24
      MadeChange = true;
136
24
    }
137
24
  }
138
84
139
84
  return MadeChange;
140
84
}
141
142
/// findReturn - Starting at MBB, follow control flow and add all
143
/// basic blocks that contain a return to ReturnBBs.
144
101
void PadShortFunc::findReturns(MachineBasicBlock *MBB, unsigned int Cycles) {
145
101
  // If this BB has a return, note how many cycles it takes to get there.
146
101
  bool hasReturn = cyclesUntilReturn(MBB, Cycles);
147
101
  if (Cycles >= Threshold)
148
63
    return;
149
38
150
38
  if (hasReturn) {
151
24
    ReturnBBs[MBB] = std::max(ReturnBBs[MBB], Cycles);
152
24
    return;
153
24
  }
154
14
155
14
  // Follow branches in BB and look for returns
156
14
  for (MachineBasicBlock::succ_iterator I = MBB->succ_begin();
157
36
       I != MBB->succ_end(); 
++I22
) {
158
22
    if (*I == MBB)
159
1
      continue;
160
21
    findReturns(*I, Cycles);
161
21
  }
162
14
}
163
164
/// cyclesUntilReturn - return true if the MBB has a return instruction,
165
/// and return false otherwise.
166
/// Cycles will be incremented by the number of cycles taken to reach the
167
/// return or the end of the BB, whichever occurs first.
168
bool PadShortFunc::cyclesUntilReturn(MachineBasicBlock *MBB,
169
101
                                     unsigned int &Cycles) {
170
101
  // Return cached result if BB was previously visited
171
101
  DenseMap<MachineBasicBlock*, VisitedBBInfo>::iterator it
172
101
    = VisitedBBs.find(MBB);
173
101
  if (it != VisitedBBs.end()) {
174
1
    VisitedBBInfo BBInfo = it->second;
175
1
    Cycles += BBInfo.Cycles;
176
1
    return BBInfo.HasReturn;
177
1
  }
178
100
179
100
  unsigned int CyclesToEnd = 0;
180
100
181
598
  for (MachineInstr &MI : *MBB) {
182
598
    // Mark basic blocks with a return instruction. Calls to other
183
598
    // functions do not count because the called function will be padded,
184
598
    // if necessary.
185
598
    if (MI.isReturn() && 
!MI.isCall()67
) {
186
66
      VisitedBBs[MBB] = VisitedBBInfo(true, CyclesToEnd);
187
66
      Cycles += CyclesToEnd;
188
66
      return true;
189
66
    }
190
532
191
532
    CyclesToEnd += TSM.computeInstrLatency(&MI);
192
532
  }
193
100
194
100
  VisitedBBs[MBB] = VisitedBBInfo(false, CyclesToEnd);
195
34
  Cycles += CyclesToEnd;
196
34
  return false;
197
100
}
198
199
/// addPadding - Add the given number of NOOP instructions to the function
200
/// just prior to the return at MBBI
201
void PadShortFunc::addPadding(MachineBasicBlock *MBB,
202
                              MachineBasicBlock::iterator &MBBI,
203
24
                              unsigned int NOOPsToAdd) {
204
24
  DebugLoc DL = MBBI->getDebugLoc();
205
24
  unsigned IssueWidth = TSM.getIssueWidth();
206
24
207
128
  for (unsigned i = 0, e = IssueWidth * NOOPsToAdd; i != e; 
++i104
)
208
104
    BuildMI(*MBB, MBBI, DL, TSM.getInstrInfo()->get(X86::NOOP));
209
24
}