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