Coverage Report

Created: 2017-10-03 07:32

/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/lib/Target/Hexagon/HexagonCFGOptimizer.cpp
Line
Count
Source (jump to first uncovered line)
1
//===-- HexagonCFGOptimizer.cpp - CFG optimizations -----------------------===//
2
//                     The LLVM Compiler Infrastructure
3
//
4
// This file is distributed under the University of Illinois Open Source
5
// License. See LICENSE.TXT for details.
6
//
7
//===----------------------------------------------------------------------===//
8
9
#include "Hexagon.h"
10
#include "HexagonMachineFunctionInfo.h"
11
#include "HexagonSubtarget.h"
12
#include "HexagonTargetMachine.h"
13
#include "llvm/CodeGen/MachineDominators.h"
14
#include "llvm/CodeGen/MachineFunctionPass.h"
15
#include "llvm/CodeGen/MachineInstrBuilder.h"
16
#include "llvm/CodeGen/MachineLoopInfo.h"
17
#include "llvm/CodeGen/MachineRegisterInfo.h"
18
#include "llvm/CodeGen/Passes.h"
19
#include "llvm/Support/Debug.h"
20
#include "llvm/Support/MathExtras.h"
21
#include "llvm/Target/TargetInstrInfo.h"
22
#include "llvm/Target/TargetMachine.h"
23
#include "llvm/Target/TargetRegisterInfo.h"
24
25
using namespace llvm;
26
27
#define DEBUG_TYPE "hexagon_cfg"
28
29
namespace llvm {
30
  FunctionPass *createHexagonCFGOptimizer();
31
  void initializeHexagonCFGOptimizerPass(PassRegistry&);
32
}
33
34
35
namespace {
36
37
class HexagonCFGOptimizer : public MachineFunctionPass {
38
39
private:
40
  void InvertAndChangeJumpTarget(MachineInstr &, MachineBasicBlock *);
41
  bool isOnFallThroughPath(MachineBasicBlock *MBB);
42
43
public:
44
  static char ID;
45
405
  HexagonCFGOptimizer() : MachineFunctionPass(ID) {
46
405
    initializeHexagonCFGOptimizerPass(*PassRegistry::getPassRegistry());
47
405
  }
48
49
401
  StringRef getPassName() const override { return "Hexagon CFG Optimizer"; }
50
  bool runOnMachineFunction(MachineFunction &Fn) override;
51
401
  MachineFunctionProperties getRequiredProperties() const override {
52
401
    return MachineFunctionProperties().set(
53
401
        MachineFunctionProperties::Property::NoVRegs);
54
401
  }
55
};
56
57
58
char HexagonCFGOptimizer::ID = 0;
59
60
1.64k
static bool IsConditionalBranch(int Opc) {
61
1.64k
  switch (Opc) {
62
421
    case Hexagon::J2_jumpt:
63
421
    case Hexagon::J2_jumptpt:
64
421
    case Hexagon::J2_jumpf:
65
421
    case Hexagon::J2_jumpfpt:
66
421
    case Hexagon::J2_jumptnew:
67
421
    case Hexagon::J2_jumpfnew:
68
421
    case Hexagon::J2_jumptnewpt:
69
421
    case Hexagon::J2_jumpfnewpt:
70
421
      return true;
71
1.22k
  }
72
1.22k
  return false;
73
1.22k
}
74
75
76
63
static bool IsUnconditionalJump(int Opc) {
77
63
  return (Opc == Hexagon::J2_jump);
78
63
}
79
80
void HexagonCFGOptimizer::InvertAndChangeJumpTarget(
81
29
    MachineInstr &MI, MachineBasicBlock *NewTarget) {
82
29
  const TargetInstrInfo *TII =
83
29
      MI.getParent()->getParent()->getSubtarget().getInstrInfo();
84
29
  int NewOpcode = 0;
85
29
  switch (MI.getOpcode()) {
86
15
  case Hexagon::J2_jumpt:
87
15
    NewOpcode = Hexagon::J2_jumpf;
88
15
    break;
89
29
90
14
  case Hexagon::J2_jumpf:
91
14
    NewOpcode = Hexagon::J2_jumpt;
92
14
    break;
93
29
94
0
  case Hexagon::J2_jumptnewpt:
95
0
    NewOpcode = Hexagon::J2_jumpfnewpt;
96
0
    break;
97
29
98
0
  case Hexagon::J2_jumpfnewpt:
99
0
    NewOpcode = Hexagon::J2_jumptnewpt;
100
0
    break;
101
29
102
0
  default:
103
0
    llvm_unreachable("Cannot handle this case");
104
29
  }
105
29
106
29
  MI.setDesc(TII->get(NewOpcode));
107
29
  MI.getOperand(1).setMBB(NewTarget);
108
29
}
109
110
0
bool HexagonCFGOptimizer::isOnFallThroughPath(MachineBasicBlock *MBB) {
111
0
  if (MBB->canFallThrough())
112
0
    return true;
113
0
  for (MachineBasicBlock *PB : MBB->predecessors())
114
0
    
if (0
PB->isLayoutSuccessor(MBB) && 0
PB->canFallThrough()0
)
115
0
      return true;
116
0
  return false;
117
0
}
118
119
860
bool HexagonCFGOptimizer::runOnMachineFunction(MachineFunction &Fn) {
120
860
  if (skipFunction(*Fn.getFunction()))
121
0
    return false;
122
860
123
860
  // Loop over all of the basic blocks.
124
860
  for (MachineFunction::iterator MBBb = Fn.begin(), MBBe = Fn.end();
125
2.92k
       
MBBb != MBBe2.92k
;
++MBBb2.06k
) {
126
2.06k
    MachineBasicBlock *MBB = &*MBBb;
127
2.06k
128
2.06k
    // Traverse the basic block.
129
2.06k
    MachineBasicBlock::iterator MII = MBB->getFirstTerminator();
130
2.06k
    if (
MII != MBB->end()2.06k
) {
131
1.64k
      MachineInstr &MI = *MII;
132
1.64k
      int Opc = MI.getOpcode();
133
1.64k
      if (
IsConditionalBranch(Opc)1.64k
) {
134
421
135
421
        //
136
421
        // (Case 1) Transform the code if the following condition occurs:
137
421
        //   BB1: if (p0) jump BB3
138
421
        //   ...falls-through to BB2 ...
139
421
        //   BB2: jump BB4
140
421
        //   ...next block in layout is BB3...
141
421
        //   BB3: ...
142
421
        //
143
421
        //  Transform this to:
144
421
        //  BB1: if (!p0) jump BB4
145
421
        //  Remove BB2
146
421
        //  BB3: ...
147
421
        //
148
421
        // (Case 2) A variation occurs when BB3 contains a JMP to BB4:
149
421
        //   BB1: if (p0) jump BB3
150
421
        //   ...falls-through to BB2 ...
151
421
        //   BB2: jump BB4
152
421
        //   ...other basic blocks ...
153
421
        //   BB4:
154
421
        //   ...not a fall-thru
155
421
        //   BB3: ...
156
421
        //     jump BB4
157
421
        //
158
421
        // Transform this to:
159
421
        //   BB1: if (!p0) jump BB4
160
421
        //   Remove BB2
161
421
        //   BB3: ...
162
421
        //   BB4: ...
163
421
        //
164
421
        unsigned NumSuccs = MBB->succ_size();
165
421
        MachineBasicBlock::succ_iterator SI = MBB->succ_begin();
166
421
        MachineBasicBlock* FirstSucc = *SI;
167
421
        MachineBasicBlock* SecondSucc = *(++SI);
168
421
        MachineBasicBlock* LayoutSucc = nullptr;
169
421
        MachineBasicBlock* JumpAroundTarget = nullptr;
170
421
171
421
        if (
MBB->isLayoutSuccessor(FirstSucc)421
) {
172
267
          LayoutSucc = FirstSucc;
173
267
          JumpAroundTarget = SecondSucc;
174
421
        } else 
if (154
MBB->isLayoutSuccessor(SecondSucc)154
) {
175
145
          LayoutSucc = SecondSucc;
176
145
          JumpAroundTarget = FirstSucc;
177
154
        } else {
178
9
          // Odd case...cannot handle.
179
9
        }
180
421
181
421
        // The target of the unconditional branch must be JumpAroundTarget.
182
421
        // TODO: If not, we should not invert the unconditional branch.
183
421
        MachineBasicBlock* CondBranchTarget = nullptr;
184
421
        if (MI.getOpcode() == Hexagon::J2_jumpt ||
185
421
            
MI.getOpcode() == Hexagon::J2_jumpf188
) {
186
421
          CondBranchTarget = MI.getOperand(1).getMBB();
187
421
        }
188
421
189
421
        if (
!LayoutSucc || 421
(CondBranchTarget != JumpAroundTarget)412
) {
190
11
          continue;
191
11
        }
192
410
193
410
        
if (410
(NumSuccs == 2) && 410
LayoutSucc410
&&
(LayoutSucc->pred_size() == 1)410
) {
194
379
          // Ensure that BB2 has one instruction -- an unconditional jump.
195
379
          if ((LayoutSucc->size() == 1) &&
196
379
              
IsUnconditionalJump(LayoutSucc->front().getOpcode())57
) {
197
30
            assert(JumpAroundTarget && "jump target is needed to process second basic block");
198
30
            MachineBasicBlock* UncondTarget =
199
30
              LayoutSucc->front().getOperand(0).getMBB();
200
30
            // Check if the layout successor of BB2 is BB3.
201
30
            bool case1 = LayoutSucc->isLayoutSuccessor(JumpAroundTarget);
202
30
            bool case2 = JumpAroundTarget->isSuccessor(UncondTarget) &&
203
6
              JumpAroundTarget->size() >= 1 &&
204
6
              IsUnconditionalJump(JumpAroundTarget->back().getOpcode()) &&
205
3
              JumpAroundTarget->pred_size() == 1 &&
206
3
              JumpAroundTarget->succ_size() == 1;
207
30
208
30
            if (
case1 || 30
case21
) {
209
29
              InvertAndChangeJumpTarget(MI, UncondTarget);
210
29
              MBB->replaceSuccessor(JumpAroundTarget, UncondTarget);
211
29
212
29
              // Remove the unconditional branch in LayoutSucc.
213
29
              LayoutSucc->erase(LayoutSucc->begin());
214
29
              LayoutSucc->replaceSuccessor(UncondTarget, JumpAroundTarget);
215
29
216
29
              // This code performs the conversion for case 2, which moves
217
29
              // the block to the fall-thru case (BB3 in the code above).
218
29
              if (
case2 && 29
!case12
) {
219
0
                JumpAroundTarget->moveAfter(LayoutSucc);
220
0
                // only move a block if it doesn't have a fall-thru. otherwise
221
0
                // the CFG will be incorrect.
222
0
                if (!isOnFallThroughPath(UncondTarget))
223
0
                  UncondTarget->moveAfter(JumpAroundTarget);
224
0
              }
225
29
226
29
              //
227
29
              // Correct live-in information. Is used by post-RA scheduler
228
29
              // The live-in to LayoutSucc is now all values live-in to
229
29
              // JumpAroundTarget.
230
29
              //
231
29
              std::vector<MachineBasicBlock::RegisterMaskPair> OrigLiveIn(
232
29
                  LayoutSucc->livein_begin(), LayoutSucc->livein_end());
233
29
              std::vector<MachineBasicBlock::RegisterMaskPair> NewLiveIn(
234
29
                  JumpAroundTarget->livein_begin(),
235
29
                  JumpAroundTarget->livein_end());
236
29
              for (const auto &OrigLI : OrigLiveIn)
237
172
                LayoutSucc->removeLiveIn(OrigLI.PhysReg);
238
29
              for (const auto &NewLI : NewLiveIn)
239
205
                LayoutSucc->addLiveIn(NewLI);
240
29
            }
241
30
          }
242
379
        }
243
421
      }
244
1.64k
    }
245
2.06k
  }
246
860
  return true;
247
860
}
248
}
249
250
251
//===----------------------------------------------------------------------===//
252
//                         Public Constructor Functions
253
//===----------------------------------------------------------------------===//
254
255
INITIALIZE_PASS(HexagonCFGOptimizer, "hexagon-cfg", "Hexagon CFG Optimizer",
256
                false, false)
257
258
405
FunctionPass *llvm::createHexagonCFGOptimizer() {
259
405
  return new HexagonCFGOptimizer();
260
405
}