1292915Sdim//===- PPCBoolRetToInt.cpp - Convert bool literals to i32 if they are returned ==// 2292915Sdim// 3292915Sdim// The LLVM Compiler Infrastructure 4292915Sdim// 5292915Sdim// This file is distributed under the University of Illinois Open Source 6292915Sdim// License. See LICENSE.TXT for details. 7292915Sdim// 8292915Sdim//===----------------------------------------------------------------------===// 9292915Sdim// 10292915Sdim// This file implements converting i1 values to i32 if they could be more 11292915Sdim// profitably allocated as GPRs rather than CRs. This pass will become totally 12292915Sdim// unnecessary if Register Bank Allocation and Global Instruction Selection ever 13292915Sdim// go upstream. 14292915Sdim// 15292915Sdim// Presently, the pass converts i1 Constants, and Arguments to i32 if the 16292915Sdim// transitive closure of their uses includes only PHINodes, CallInsts, and 17292915Sdim// ReturnInsts. The rational is that arguments are generally passed and returned 18292915Sdim// in GPRs rather than CRs, so casting them to i32 at the LLVM IR level will 19292915Sdim// actually save casts at the Machine Instruction level. 20292915Sdim// 21292915Sdim// It might be useful to expand this pass to add bit-wise operations to the list 22292915Sdim// of safe transitive closure types. Also, we miss some opportunities when LLVM 23292915Sdim// represents logical AND and OR operations with control flow rather than data 24292915Sdim// flow. For example by lowering the expression: return (A && B && C) 25292915Sdim// 26292915Sdim// as: return A ? true : B && C. 27292915Sdim// 28292915Sdim// There's code in SimplifyCFG that code be used to turn control flow in data 29292915Sdim// flow using SelectInsts. Selects are slow on some architectures (P7/P8), so 30292915Sdim// this probably isn't good in general, but for the special case of i1, the 31292915Sdim// Selects could be further lowered to bit operations that are fast everywhere. 32292915Sdim// 33292915Sdim//===----------------------------------------------------------------------===// 34292915Sdim 35292915Sdim#include "PPC.h" 36292915Sdim#include "llvm/Transforms/Scalar.h" 37292915Sdim#include "llvm/ADT/SmallPtrSet.h" 38292915Sdim#include "llvm/ADT/Statistic.h" 39292915Sdim#include "llvm/IR/Constants.h" 40292915Sdim#include "llvm/IR/Dominators.h" 41292915Sdim#include "llvm/IR/Instructions.h" 42292915Sdim#include "llvm/IR/IntrinsicInst.h" 43292915Sdim#include "llvm/Support/raw_ostream.h" 44292915Sdim#include "llvm/Pass.h" 45292915Sdim 46292915Sdimusing namespace llvm; 47292915Sdim 48292915Sdimnamespace { 49292915Sdim 50292915Sdim#define DEBUG_TYPE "bool-ret-to-int" 51292915Sdim 52292915SdimSTATISTIC(NumBoolRetPromotion, 53292915Sdim "Number of times a bool feeding a RetInst was promoted to an int"); 54292915SdimSTATISTIC(NumBoolCallPromotion, 55292915Sdim "Number of times a bool feeding a CallInst was promoted to an int"); 56292915SdimSTATISTIC(NumBoolToIntPromotion, 57292915Sdim "Total number of times a bool was promoted to an int"); 58292915Sdim 59292915Sdimclass PPCBoolRetToInt : public FunctionPass { 60292915Sdim 61292915Sdim static SmallPtrSet<Value *, 8> findAllDefs(Value *V) { 62292915Sdim SmallPtrSet<Value *, 8> Defs; 63292915Sdim SmallVector<Value *, 8> WorkList; 64292915Sdim WorkList.push_back(V); 65292915Sdim Defs.insert(V); 66292915Sdim while (!WorkList.empty()) { 67292915Sdim Value *Curr = WorkList.back(); 68292915Sdim WorkList.pop_back(); 69292915Sdim if (User *CurrUser = dyn_cast<User>(Curr)) 70292915Sdim for (auto &Op : CurrUser->operands()) 71292915Sdim if (Defs.insert(Op).second) 72292915Sdim WorkList.push_back(Op); 73292915Sdim } 74292915Sdim return Defs; 75292915Sdim } 76292915Sdim 77292915Sdim // Translate a i1 value to an equivalent i32 value: 78292915Sdim static Value *translate(Value *V) { 79292915Sdim Type *Int32Ty = Type::getInt32Ty(V->getContext()); 80292915Sdim if (Constant *C = dyn_cast<Constant>(V)) 81292915Sdim return ConstantExpr::getZExt(C, Int32Ty); 82292915Sdim if (PHINode *P = dyn_cast<PHINode>(V)) { 83292915Sdim // Temporarily set the operands to 0. We'll fix this later in 84292915Sdim // runOnUse. 85292915Sdim Value *Zero = Constant::getNullValue(Int32Ty); 86292915Sdim PHINode *Q = 87292915Sdim PHINode::Create(Int32Ty, P->getNumIncomingValues(), P->getName(), P); 88292915Sdim for (unsigned i = 0; i < P->getNumOperands(); ++i) 89292915Sdim Q->addIncoming(Zero, P->getIncomingBlock(i)); 90292915Sdim return Q; 91292915Sdim } 92292915Sdim 93292915Sdim Argument *A = dyn_cast<Argument>(V); 94292915Sdim Instruction *I = dyn_cast<Instruction>(V); 95292915Sdim assert((A || I) && "Unknown value type"); 96292915Sdim 97292915Sdim auto InstPt = 98292915Sdim A ? &*A->getParent()->getEntryBlock().begin() : I->getNextNode(); 99292915Sdim return new ZExtInst(V, Int32Ty, "", InstPt); 100292915Sdim } 101292915Sdim 102292915Sdim typedef SmallPtrSet<const PHINode *, 8> PHINodeSet; 103292915Sdim 104292915Sdim // A PHINode is Promotable if: 105292915Sdim // 1. Its type is i1 AND 106292915Sdim // 2. All of its uses are ReturnInt, CallInst, PHINode, or DbgInfoIntrinsic 107292915Sdim // AND 108292915Sdim // 3. All of its operands are Constant or Argument or 109292915Sdim // CallInst or PHINode AND 110292915Sdim // 4. All of its PHINode uses are Promotable AND 111292915Sdim // 5. All of its PHINode operands are Promotable 112292915Sdim static PHINodeSet getPromotablePHINodes(const Function &F) { 113292915Sdim PHINodeSet Promotable; 114292915Sdim // Condition 1 115292915Sdim for (auto &BB : F) 116292915Sdim for (auto &I : BB) 117292915Sdim if (const PHINode *P = dyn_cast<PHINode>(&I)) 118292915Sdim if (P->getType()->isIntegerTy(1)) 119292915Sdim Promotable.insert(P); 120292915Sdim 121292915Sdim SmallVector<const PHINode *, 8> ToRemove; 122292915Sdim for (const auto &P : Promotable) { 123292915Sdim // Condition 2 and 3 124292915Sdim auto IsValidUser = [] (const Value *V) -> bool { 125292915Sdim return isa<ReturnInst>(V) || isa<CallInst>(V) || isa<PHINode>(V) || 126292915Sdim isa<DbgInfoIntrinsic>(V); 127292915Sdim }; 128292915Sdim auto IsValidOperand = [] (const Value *V) -> bool { 129292915Sdim return isa<Constant>(V) || isa<Argument>(V) || isa<CallInst>(V) || 130292915Sdim isa<PHINode>(V); 131292915Sdim }; 132292915Sdim const auto &Users = P->users(); 133292915Sdim const auto &Operands = P->operands(); 134292915Sdim if (!std::all_of(Users.begin(), Users.end(), IsValidUser) || 135292915Sdim !std::all_of(Operands.begin(), Operands.end(), IsValidOperand)) 136292915Sdim ToRemove.push_back(P); 137292915Sdim } 138292915Sdim 139292915Sdim // Iterate to convergence 140292915Sdim auto IsPromotable = [&Promotable] (const Value *V) -> bool { 141292915Sdim const PHINode *Phi = dyn_cast<PHINode>(V); 142292915Sdim return !Phi || Promotable.count(Phi); 143292915Sdim }; 144292915Sdim while (!ToRemove.empty()) { 145292915Sdim for (auto &User : ToRemove) 146292915Sdim Promotable.erase(User); 147292915Sdim ToRemove.clear(); 148292915Sdim 149292915Sdim for (const auto &P : Promotable) { 150292915Sdim // Condition 4 and 5 151292915Sdim const auto &Users = P->users(); 152292915Sdim const auto &Operands = P->operands(); 153292915Sdim if (!std::all_of(Users.begin(), Users.end(), IsPromotable) || 154292915Sdim !std::all_of(Operands.begin(), Operands.end(), IsPromotable)) 155292915Sdim ToRemove.push_back(P); 156292915Sdim } 157292915Sdim } 158292915Sdim 159292915Sdim return Promotable; 160292915Sdim } 161292915Sdim 162292915Sdim typedef DenseMap<Value *, Value *> B2IMap; 163292915Sdim 164292915Sdim public: 165292915Sdim static char ID; 166292915Sdim PPCBoolRetToInt() : FunctionPass(ID) { 167292915Sdim initializePPCBoolRetToIntPass(*PassRegistry::getPassRegistry()); 168292915Sdim } 169292915Sdim 170292915Sdim bool runOnFunction(Function &F) { 171292915Sdim PHINodeSet PromotablePHINodes = getPromotablePHINodes(F); 172292915Sdim B2IMap Bool2IntMap; 173292915Sdim bool Changed = false; 174292915Sdim for (auto &BB : F) { 175292915Sdim for (auto &I : BB) { 176292915Sdim if (ReturnInst *R = dyn_cast<ReturnInst>(&I)) 177292915Sdim if (F.getReturnType()->isIntegerTy(1)) 178292915Sdim Changed |= 179292915Sdim runOnUse(R->getOperandUse(0), PromotablePHINodes, Bool2IntMap); 180292915Sdim 181292915Sdim if (CallInst *CI = dyn_cast<CallInst>(&I)) 182292915Sdim for (auto &U : CI->operands()) 183292915Sdim if (U->getType()->isIntegerTy(1)) 184292915Sdim Changed |= runOnUse(U, PromotablePHINodes, Bool2IntMap); 185292915Sdim } 186292915Sdim } 187292915Sdim 188292915Sdim return Changed; 189292915Sdim } 190292915Sdim 191292915Sdim static bool runOnUse(Use &U, const PHINodeSet &PromotablePHINodes, 192292915Sdim B2IMap &BoolToIntMap) { 193292915Sdim auto Defs = findAllDefs(U); 194292915Sdim 195292915Sdim // If the values are all Constants or Arguments, don't bother 196292915Sdim if (!std::any_of(Defs.begin(), Defs.end(), isa<Instruction, Value *>)) 197292915Sdim return false; 198292915Sdim 199292915Sdim // Presently, we only know how to handle PHINode, Constant, and Arguments. 200292915Sdim // Potentially, bitwise operations (AND, OR, XOR, NOT) and sign extension 201292915Sdim // could also be handled in the future. 202292915Sdim for (const auto &V : Defs) 203292915Sdim if (!isa<PHINode>(V) && !isa<Constant>(V) && !isa<Argument>(V)) 204292915Sdim return false; 205292915Sdim 206292915Sdim for (const auto &V : Defs) 207292915Sdim if (const PHINode *P = dyn_cast<PHINode>(V)) 208292915Sdim if (!PromotablePHINodes.count(P)) 209292915Sdim return false; 210292915Sdim 211292915Sdim if (isa<ReturnInst>(U.getUser())) 212292915Sdim ++NumBoolRetPromotion; 213292915Sdim if (isa<CallInst>(U.getUser())) 214292915Sdim ++NumBoolCallPromotion; 215292915Sdim ++NumBoolToIntPromotion; 216292915Sdim 217292915Sdim for (const auto &V : Defs) 218292915Sdim if (!BoolToIntMap.count(V)) 219292915Sdim BoolToIntMap[V] = translate(V); 220292915Sdim 221292915Sdim // Replace the operands of the translated instructions. There were set to 222292915Sdim // zero in the translate function. 223292915Sdim for (auto &Pair : BoolToIntMap) { 224292915Sdim User *First = dyn_cast<User>(Pair.first); 225292915Sdim User *Second = dyn_cast<User>(Pair.second); 226292915Sdim assert((!First || Second) && "translated from user to non-user!?"); 227292915Sdim if (First) 228292915Sdim for (unsigned i = 0; i < First->getNumOperands(); ++i) 229292915Sdim Second->setOperand(i, BoolToIntMap[First->getOperand(i)]); 230292915Sdim } 231292915Sdim 232292915Sdim Value *IntRetVal = BoolToIntMap[U]; 233292915Sdim Type *Int1Ty = Type::getInt1Ty(U->getContext()); 234292915Sdim Instruction *I = cast<Instruction>(U.getUser()); 235292915Sdim Value *BackToBool = new TruncInst(IntRetVal, Int1Ty, "backToBool", I); 236292915Sdim U.set(BackToBool); 237292915Sdim 238292915Sdim return true; 239292915Sdim } 240292915Sdim 241292915Sdim void getAnalysisUsage(AnalysisUsage &AU) const { 242292915Sdim AU.addPreserved<DominatorTreeWrapperPass>(); 243292915Sdim FunctionPass::getAnalysisUsage(AU); 244292915Sdim } 245292915Sdim}; 246292915Sdim} 247292915Sdim 248292915Sdimchar PPCBoolRetToInt::ID = 0; 249292915SdimINITIALIZE_PASS(PPCBoolRetToInt, "bool-ret-to-int", 250292915Sdim "Convert i1 constants to i32 if they are returned", 251292915Sdim false, false) 252292915Sdim 253292915SdimFunctionPass *llvm::createPPCBoolRetToIntPass() { return new PPCBoolRetToInt(); } 254