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
58using namespace llvm;
59
60namespace {
61
62#define DEBUG_TYPE "ppc-bool-ret-to-int"
63
64STATISTIC(NumBoolRetPromotion,
65          "Number of times a bool feeding a RetInst was promoted to an int");
66STATISTIC(NumBoolCallPromotion,
67          "Number of times a bool feeding a CallInst was promoted to an int");
68STATISTIC(NumBoolToIntPromotion,
69          "Total number of times a bool was promoted to an int");
70
71class PPCBoolRetToInt : public FunctionPass {
72  static SmallPtrSet<Value *, 8> findAllDefs(Value *V) {
73    SmallPtrSet<Value *, 8> Defs;
74    SmallVector<Value *, 8> WorkList;
75    WorkList.push_back(V);
76    Defs.insert(V);
77    while (!WorkList.empty()) {
78      Value *Curr = WorkList.pop_back_val();
79      auto *CurrUser = dyn_cast<User>(Curr);
80      // Operands of CallInst/Constant are skipped because they may not be Bool
81      // type. For CallInst, their positions are defined by ABI.
82      if (CurrUser && !isa<CallInst>(Curr) && !isa<Constant>(Curr))
83        for (auto &Op : CurrUser->operands())
84          if (Defs.insert(Op).second)
85            WorkList.push_back(Op);
86    }
87    return Defs;
88  }
89
90  // Translate a i1 value to an equivalent i32/i64 value:
91  Value *translate(Value *V) {
92    assert(V->getType() == Type::getInt1Ty(V->getContext()) &&
93           "Expect an i1 value");
94
95    Type *IntTy = ST->isPPC64() ? Type::getInt64Ty(V->getContext())
96                                : Type::getInt32Ty(V->getContext());
97
98    if (auto *C = dyn_cast<Constant>(V))
99      return ConstantExpr::getZExt(C, IntTy);
100    if (auto *P = dyn_cast<PHINode>(V)) {
101      // Temporarily set the operands to 0. We'll fix this later in
102      // runOnUse.
103      Value *Zero = Constant::getNullValue(IntTy);
104      PHINode *Q =
105        PHINode::Create(IntTy, P->getNumIncomingValues(), P->getName(), P);
106      for (unsigned i = 0; i < P->getNumOperands(); ++i)
107        Q->addIncoming(Zero, P->getIncomingBlock(i));
108      return Q;
109    }
110
111    auto *A = dyn_cast<Argument>(V);
112    auto *I = dyn_cast<Instruction>(V);
113    assert((A || I) && "Unknown value type");
114
115    auto InstPt =
116      A ? &*A->getParent()->getEntryBlock().begin() : I->getNextNode();
117    return new ZExtInst(V, IntTy, "", InstPt);
118  }
119
120  typedef SmallPtrSet<const PHINode *, 8> PHINodeSet;
121
122  // A PHINode is Promotable if:
123  // 1. Its type is i1 AND
124  // 2. All of its uses are ReturnInt, CallInst, PHINode, or DbgInfoIntrinsic
125  // AND
126  // 3. All of its operands are Constant or Argument or
127  //    CallInst or PHINode AND
128  // 4. All of its PHINode uses are Promotable AND
129  // 5. All of its PHINode operands are Promotable
130  static PHINodeSet getPromotablePHINodes(const Function &F) {
131    PHINodeSet Promotable;
132    // Condition 1
133    for (auto &BB : F)
134      for (auto &I : BB)
135        if (const auto *P = dyn_cast<PHINode>(&I))
136          if (P->getType()->isIntegerTy(1))
137            Promotable.insert(P);
138
139    SmallVector<const PHINode *, 8> ToRemove;
140    for (const PHINode *P : Promotable) {
141      // Condition 2 and 3
142      auto IsValidUser = [] (const Value *V) -> bool {
143        return isa<ReturnInst>(V) || isa<CallInst>(V) || isa<PHINode>(V) ||
144        isa<DbgInfoIntrinsic>(V);
145      };
146      auto IsValidOperand = [] (const Value *V) -> bool {
147        return isa<Constant>(V) || isa<Argument>(V) || isa<CallInst>(V) ||
148        isa<PHINode>(V);
149      };
150      const auto &Users = P->users();
151      const auto &Operands = P->operands();
152      if (!llvm::all_of(Users, IsValidUser) ||
153          !llvm::all_of(Operands, IsValidOperand))
154        ToRemove.push_back(P);
155    }
156
157    // Iterate to convergence
158    auto IsPromotable = [&Promotable] (const Value *V) -> bool {
159      const auto *Phi = dyn_cast<PHINode>(V);
160      return !Phi || Promotable.count(Phi);
161    };
162    while (!ToRemove.empty()) {
163      for (auto &User : ToRemove)
164        Promotable.erase(User);
165      ToRemove.clear();
166
167      for (const PHINode *P : Promotable) {
168        // Condition 4 and 5
169        const auto &Users = P->users();
170        const auto &Operands = P->operands();
171        if (!llvm::all_of(Users, IsPromotable) ||
172            !llvm::all_of(Operands, IsPromotable))
173          ToRemove.push_back(P);
174      }
175    }
176
177    return Promotable;
178  }
179
180  typedef DenseMap<Value *, Value *> B2IMap;
181
182 public:
183  static char ID;
184
185  PPCBoolRetToInt() : FunctionPass(ID) {
186    initializePPCBoolRetToIntPass(*PassRegistry::getPassRegistry());
187  }
188
189  bool runOnFunction(Function &F) override {
190    if (skipFunction(F))
191      return false;
192
193    auto *TPC = getAnalysisIfAvailable<TargetPassConfig>();
194    if (!TPC)
195      return false;
196
197    auto &TM = TPC->getTM<PPCTargetMachine>();
198    ST = TM.getSubtargetImpl(F);
199
200    PHINodeSet PromotablePHINodes = getPromotablePHINodes(F);
201    B2IMap Bool2IntMap;
202    bool Changed = false;
203    for (auto &BB : F) {
204      for (auto &I : BB) {
205        if (auto *R = dyn_cast<ReturnInst>(&I))
206          if (F.getReturnType()->isIntegerTy(1))
207            Changed |=
208              runOnUse(R->getOperandUse(0), PromotablePHINodes, Bool2IntMap);
209
210        if (auto *CI = dyn_cast<CallInst>(&I))
211          for (auto &U : CI->operands())
212            if (U->getType()->isIntegerTy(1))
213              Changed |= runOnUse(U, PromotablePHINodes, Bool2IntMap);
214      }
215    }
216
217    return Changed;
218  }
219
220  bool runOnUse(Use &U, const PHINodeSet &PromotablePHINodes,
221                       B2IMap &BoolToIntMap) {
222    auto Defs = findAllDefs(U);
223
224    // If the values are all Constants or Arguments, don't bother
225    if (llvm::none_of(Defs, [](Value *V) { return isa<Instruction>(V); }))
226      return false;
227
228    // Presently, we only know how to handle PHINode, Constant, Arguments and
229    // CallInst. Potentially, bitwise operations (AND, OR, XOR, NOT) and sign
230    // extension could also be handled in the future.
231    for (Value *V : Defs)
232      if (!isa<PHINode>(V) && !isa<Constant>(V) &&
233          !isa<Argument>(V) && !isa<CallInst>(V))
234        return false;
235
236    for (Value *V : Defs)
237      if (const auto *P = dyn_cast<PHINode>(V))
238        if (!PromotablePHINodes.count(P))
239          return false;
240
241    if (isa<ReturnInst>(U.getUser()))
242      ++NumBoolRetPromotion;
243    if (isa<CallInst>(U.getUser()))
244      ++NumBoolCallPromotion;
245    ++NumBoolToIntPromotion;
246
247    for (Value *V : Defs)
248      if (!BoolToIntMap.count(V))
249        BoolToIntMap[V] = translate(V);
250
251    // Replace the operands of the translated instructions. They were set to
252    // zero in the translate function.
253    for (auto &Pair : BoolToIntMap) {
254      auto *First = dyn_cast<User>(Pair.first);
255      auto *Second = dyn_cast<User>(Pair.second);
256      assert((!First || Second) && "translated from user to non-user!?");
257      // Operands of CallInst/Constant are skipped because they may not be Bool
258      // type. For CallInst, their positions are defined by ABI.
259      if (First && !isa<CallInst>(First) && !isa<Constant>(First))
260        for (unsigned i = 0; i < First->getNumOperands(); ++i)
261          Second->setOperand(i, BoolToIntMap[First->getOperand(i)]);
262    }
263
264    Value *IntRetVal = BoolToIntMap[U];
265    Type *Int1Ty = Type::getInt1Ty(U->getContext());
266    auto *I = cast<Instruction>(U.getUser());
267    Value *BackToBool = new TruncInst(IntRetVal, Int1Ty, "backToBool", I);
268    U.set(BackToBool);
269
270    return true;
271  }
272
273  void getAnalysisUsage(AnalysisUsage &AU) const override {
274    AU.addPreserved<DominatorTreeWrapperPass>();
275    FunctionPass::getAnalysisUsage(AU);
276  }
277
278private:
279  const PPCSubtarget *ST;
280};
281
282} // end anonymous namespace
283
284char PPCBoolRetToInt::ID = 0;
285INITIALIZE_PASS(PPCBoolRetToInt, "ppc-bool-ret-to-int",
286                "Convert i1 constants to i32/i64 if they are returned", false,
287                false)
288
289FunctionPass *llvm::createPPCBoolRetToIntPass() { return new PPCBoolRetToInt(); }
290