Coverage Report

Created: 2019-07-24 05:18

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