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 "ppc-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.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 278 private: 279 const PPCSubtarget *ST; 280 }; 281 282 } // end anonymous namespace 283 284 char PPCBoolRetToInt::ID = 0; 285 INITIALIZE_PASS(PPCBoolRetToInt, "ppc-bool-ret-to-int", 286 "Convert i1 constants to i32/i64 if they are returned", false, 287 false) 288 289 FunctionPass *llvm::createPPCBoolRetToIntPass() { return new PPCBoolRetToInt(); } 290