Coverage Report

Created: 2017-10-03 07:32

/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/lib/Target/PowerPC/PPCBoolRetToInt.cpp
Line
Count
Source (jump to first uncovered line)
1
//===- PPCBoolRetToInt.cpp ------------------------------------------------===//
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
// This file implements converting i1 values to i32/i64 if they could be more
11
// profitably allocated as GPRs rather than CRs. This pass will become totally
12
// unnecessary if Register Bank Allocation and Global Instruction Selection ever
13
// go upstream.
14
//
15
// Presently, the pass converts i1 Constants, and Arguments to i32/i64 if the
16
// transitive closure of their uses includes only PHINodes, CallInsts, and
17
// ReturnInsts. The rational is that arguments are generally passed and returned
18
// in GPRs rather than CRs, so casting them to i32/i64 at the LLVM IR level will
19
// actually save casts at the Machine Instruction level.
20
//
21
// It might be useful to expand this pass to add bit-wise operations to the list
22
// of safe transitive closure types. Also, we miss some opportunities when LLVM
23
// represents logical AND and OR operations with control flow rather than data
24
// flow. For example by lowering the expression: return (A && B && C)
25
//
26
// as: return A ? true : B && C.
27
//
28
// There's code in SimplifyCFG that code be used to turn control flow in data
29
// flow using SelectInsts. Selects are slow on some architectures (P7/P8), so
30
// this probably isn't good in general, but for the special case of i1, the
31
// Selects could be further lowered to bit operations that are fast everywhere.
32
//
33
//===----------------------------------------------------------------------===//
34
35
#include "PPC.h"
36
#include "PPCTargetMachine.h"
37
#include "llvm/ADT/DenseMap.h"
38
#include "llvm/ADT/STLExtras.h"
39
#include "llvm/ADT/SmallPtrSet.h"
40
#include "llvm/ADT/SmallVector.h"
41
#include "llvm/ADT/Statistic.h"
42
#include "llvm/IR/Argument.h"
43
#include "llvm/IR/Constants.h"
44
#include "llvm/IR/Dominators.h"
45
#include "llvm/IR/Function.h"
46
#include "llvm/IR/Instruction.h"
47
#include "llvm/IR/Instructions.h"
48
#include "llvm/IR/IntrinsicInst.h"
49
#include "llvm/IR/OperandTraits.h"
50
#include "llvm/IR/Type.h"
51
#include "llvm/IR/Use.h"
52
#include "llvm/IR/User.h"
53
#include "llvm/IR/Value.h"
54
#include "llvm/Pass.h"
55
#include "llvm/CodeGen/TargetPassConfig.h"
56
#include "llvm/Support/Casting.h"
57
#include <cassert>
58
59
using namespace llvm;
60
61
namespace {
62
63
#define DEBUG_TYPE "bool-ret-to-int"
64
65
STATISTIC(NumBoolRetPromotion,
66
          "Number of times a bool feeding a RetInst was promoted to an int");
67
STATISTIC(NumBoolCallPromotion,
68
          "Number of times a bool feeding a CallInst was promoted to an int");
69
STATISTIC(NumBoolToIntPromotion,
70
          "Total number of times a bool was promoted to an int");
71
72
class PPCBoolRetToInt : public FunctionPass {
73
140
  static SmallPtrSet<Value *, 8> findAllDefs(Value *V) {
74
140
    SmallPtrSet<Value *, 8> Defs;
75
140
    SmallVector<Value *, 8> WorkList;
76
140
    WorkList.push_back(V);
77
140
    Defs.insert(V);
78
533
    while (
!WorkList.empty()533
) {
79
393
      Value *Curr = WorkList.back();
80
393
      WorkList.pop_back();
81
393
      auto *CurrUser = dyn_cast<User>(Curr);
82
393
      // Operands of CallInst are skipped because they may not be Bool type,
83
393
      // and their positions are defined by ABI.
84
393
      if (
CurrUser && 393
!isa<CallInst>(Curr)306
)
85
297
        for (auto &Op : CurrUser->operands())
86
285
          
if (285
Defs.insert(Op).second285
)
87
253
            WorkList.push_back(Op);
88
393
    }
89
140
    return Defs;
90
140
  }
91
92
  // Translate a i1 value to an equivalent i32/i64 value:
93
23
  Value *translate(Value *V) {
94
23
    Type *IntTy = ST->isPPC64() ? Type::getInt64Ty(V->getContext())
95
0
                                : Type::getInt32Ty(V->getContext());
96
23
97
23
    if (auto *C = dyn_cast<Constant>(V))
98
10
      return ConstantExpr::getZExt(C, IntTy);
99
13
    
if (auto *13
P13
= dyn_cast<PHINode>(V)) {
100
10
      // Temporarily set the operands to 0. We'll fix this later in
101
10
      // runOnUse.
102
10
      Value *Zero = Constant::getNullValue(IntTy);
103
10
      PHINode *Q =
104
10
        PHINode::Create(IntTy, P->getNumIncomingValues(), P->getName(), P);
105
29
      for (unsigned i = 0; 
i < P->getNumOperands()29
;
++i19
)
106
19
        Q->addIncoming(Zero, P->getIncomingBlock(i));
107
10
      return Q;
108
10
    }
109
3
110
3
    auto *A = dyn_cast<Argument>(V);
111
3
    auto *I = dyn_cast<Instruction>(V);
112
3
    assert((A || I) && "Unknown value type");
113
3
114
3
    auto InstPt =
115
3
      A ? 
&*A->getParent()->getEntryBlock().begin()2
:
I->getNextNode()1
;
116
23
    return new ZExtInst(V, IntTy, "", InstPt);
117
23
  }
118
119
  typedef SmallPtrSet<const PHINode *, 8> PHINodeSet;
120
121
  // A PHINode is Promotable if:
122
  // 1. Its type is i1 AND
123
  // 2. All of its uses are ReturnInt, CallInst, PHINode, or DbgInfoIntrinsic
124
  // AND
125
  // 3. All of its operands are Constant or Argument or
126
  //    CallInst or PHINode AND
127
  // 4. All of its PHINode uses are Promotable AND
128
  // 5. All of its PHINode operands are Promotable
129
6.90k
  static PHINodeSet getPromotablePHINodes(const Function &F) {
130
6.90k
    PHINodeSet Promotable;
131
6.90k
    // Condition 1
132
6.90k
    for (auto &BB : F)
133
9.88k
      for (auto &I : BB)
134
36.8k
        
if (const auto *36.8k
P36.8k
= dyn_cast<PHINode>(&I))
135
668
          
if (668
P->getType()->isIntegerTy(1)668
)
136
16
            Promotable.insert(P);
137
6.90k
138
6.90k
    SmallVector<const PHINode *, 8> ToRemove;
139
16
    for (const PHINode *P : Promotable) {
140
16
      // Condition 2 and 3
141
19
      auto IsValidUser = [] (const Value *V) -> bool {
142
19
        return isa<ReturnInst>(V) || 
isa<CallInst>(V)12
||
isa<PHINode>(V)10
||
143
5
        isa<DbgInfoIntrinsic>(V);
144
19
      };
145
21
      auto IsValidOperand = [] (const Value *V) -> bool {
146
21
        return isa<Constant>(V) || 
isa<Argument>(V)7
||
isa<CallInst>(V)5
||
147
5
        isa<PHINode>(V);
148
21
      };
149
16
      const auto &Users = P->users();
150
16
      const auto &Operands = P->operands();
151
16
      if (!llvm::all_of(Users, IsValidUser) ||
152
11
          !llvm::all_of(Operands, IsValidOperand))
153
5
        ToRemove.push_back(P);
154
16
    }
155
6.90k
156
6.90k
    // Iterate to convergence
157
3
    auto IsPromotable = [&Promotable] (const Value *V) -> bool {
158
3
      const auto *Phi = dyn_cast<PHINode>(V);
159
1
      return !Phi || Promotable.count(Phi);
160
3
    };
161
6.90k
    while (
!ToRemove.empty()6.90k
) {
162
6
      for (auto &User : ToRemove)
163
6
        Promotable.erase(User);
164
6
      ToRemove.clear();
165
6
166
1
      for (const PHINode *P : Promotable) {
167
1
        // Condition 4 and 5
168
1
        const auto &Users = P->users();
169
1
        const auto &Operands = P->operands();
170
1
        if (!llvm::all_of(Users, IsPromotable) ||
171
1
            !llvm::all_of(Operands, IsPromotable))
172
1
          ToRemove.push_back(P);
173
1
      }
174
6
    }
175
6.90k
176
6.90k
    return Promotable;
177
6.90k
  }
178
179
  typedef DenseMap<Value *, Value *> B2IMap;
180
181
 public:
182
  static char ID;
183
184
1.23k
  PPCBoolRetToInt() : FunctionPass(ID) {
185
1.23k
    initializePPCBoolRetToIntPass(*PassRegistry::getPassRegistry());
186
1.23k
  }
187
188
6.90k
  bool runOnFunction(Function &F) override {
189
6.90k
    if (skipFunction(F))
190
1
      return false;
191
6.90k
192
6.90k
    auto *TPC = getAnalysisIfAvailable<TargetPassConfig>();
193
6.90k
    if (!TPC)
194
0
      return false;
195
6.90k
196
6.90k
    auto &TM = TPC->getTM<PPCTargetMachine>();
197
6.90k
    ST = TM.getSubtargetImpl(F);
198
6.90k
199
6.90k
    PHINodeSet PromotablePHINodes = getPromotablePHINodes(F);
200
6.90k
    B2IMap Bool2IntMap;
201
6.90k
    bool Changed = false;
202
9.88k
    for (auto &BB : F) {
203
36.8k
      for (auto &I : BB) {
204
36.8k
        if (auto *R = dyn_cast<ReturnInst>(&I))
205
6.97k
          
if (6.97k
F.getReturnType()->isIntegerTy(1)6.97k
)
206
60
            Changed |=
207
60
              runOnUse(R->getOperandUse(0), PromotablePHINodes, Bool2IntMap);
208
36.8k
209
36.8k
        if (auto *CI = dyn_cast<CallInst>(&I))
210
2.42k
          for (auto &U : CI->operands())
211
7.67k
            
if (7.67k
U->getType()->isIntegerTy(1)7.67k
)
212
80
              Changed |= runOnUse(U, PromotablePHINodes, Bool2IntMap);
213
36.8k
      }
214
9.88k
    }
215
6.90k
216
6.90k
    return Changed;
217
6.90k
  }
218
219
  bool runOnUse(Use &U, const PHINodeSet &PromotablePHINodes,
220
140
                       B2IMap &BoolToIntMap) {
221
140
    auto Defs = findAllDefs(U);
222
140
223
140
    // If the values are all Constants or Arguments, don't bother
224
140
    if (llvm::none_of(Defs, isa<Instruction, Value *>))
225
81
      return false;
226
59
227
59
    // Presently, we only know how to handle PHINode, Constant, Arguments and
228
59
    // CallInst. Potentially, bitwise operations (AND, OR, XOR, NOT) and sign
229
59
    // extension could also be handled in the future.
230
59
    for (Value *V : Defs)
231
86
      
if (86
!isa<PHINode>(V) && 86
!isa<Constant>(V)71
&&
232
86
          
!isa<Argument>(V)54
&&
!isa<CallInst>(V)50
)
233
49
        return false;
234
10
235
10
    for (Value *V : Defs)
236
29
      
if (const auto *29
P29
= dyn_cast<PHINode>(V))
237
14
        
if (14
!PromotablePHINodes.count(P)14
)
238
2
          return false;
239
8
240
8
    
if (8
isa<ReturnInst>(U.getUser())8
)
241
6
      ++NumBoolRetPromotion;
242
8
    if (isa<CallInst>(U.getUser()))
243
2
      ++NumBoolCallPromotion;
244
8
    ++NumBoolToIntPromotion;
245
8
246
8
    for (Value *V : Defs)
247
27
      
if (27
!BoolToIntMap.count(V)27
)
248
23
        BoolToIntMap[V] = translate(V);
249
8
250
8
    // Replace the operands of the translated instructions. They were set to
251
8
    // zero in the translate function.
252
27
    for (auto &Pair : BoolToIntMap) {
253
27
      auto *First = dyn_cast<User>(Pair.first);
254
27
      auto *Second = dyn_cast<User>(Pair.second);
255
27
      assert((!First || Second) && "translated from user to non-user!?");
256
27
      // Operands of CallInst are skipped because they may not be Bool type,
257
27
      // and their positions are defined by ABI.
258
27
      if (
First && 27
!isa<CallInst>(First)25
)
259
47
        
for (unsigned i = 0; 24
i < First->getNumOperands()47
;
++i23
)
260
23
          Second->setOperand(i, BoolToIntMap[First->getOperand(i)]);
261
27
    }
262
140
263
140
    Value *IntRetVal = BoolToIntMap[U];
264
140
    Type *Int1Ty = Type::getInt1Ty(U->getContext());
265
140
    auto *I = cast<Instruction>(U.getUser());
266
140
    Value *BackToBool = new TruncInst(IntRetVal, Int1Ty, "backToBool", I);
267
140
    U.set(BackToBool);
268
140
269
140
    return true;
270
140
  }
271
272
1.23k
  void getAnalysisUsage(AnalysisUsage &AU) const override {
273
1.23k
    AU.addPreserved<DominatorTreeWrapperPass>();
274
1.23k
    FunctionPass::getAnalysisUsage(AU);
275
1.23k
  }
276
277
private:
278
  const PPCSubtarget *ST;
279
};
280
281
} // end anonymous namespace
282
283
char PPCBoolRetToInt::ID = 0;
284
INITIALIZE_PASS(PPCBoolRetToInt, "bool-ret-to-int",
285
                "Convert i1 constants to i32/i64 if they are returned",
286
                false, false)
287
288
1.23k
FunctionPass *llvm::createPPCBoolRetToIntPass() { return new PPCBoolRetToInt(); }