contrib/llvm-project/llvm/lib/Target/PowerPC/PPCBoolRetToInt.cpp

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