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