| //===- PPCBoolRetToInt.cpp ------------------------------------------------===// |
| // |
| // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
| // See https://llvm.org/LICENSE.txt for license information. |
| // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
| // |
| //===----------------------------------------------------------------------===// |
| // |
| // This file implements converting i1 values to i32/i64 if they could be more |
| // profitably allocated as GPRs rather than CRs. This pass will become totally |
| // unnecessary if Register Bank Allocation and Global Instruction Selection ever |
| // go upstream. |
| // |
| // Presently, the pass converts i1 Constants, and Arguments to i32/i64 if the |
| // transitive closure of their uses includes only PHINodes, CallInsts, and |
| // ReturnInsts. The rational is that arguments are generally passed and returned |
| // in GPRs rather than CRs, so casting them to i32/i64 at the LLVM IR level will |
| // actually save casts at the Machine Instruction level. |
| // |
| // It might be useful to expand this pass to add bit-wise operations to the list |
| // of safe transitive closure types. Also, we miss some opportunities when LLVM |
| // represents logical AND and OR operations with control flow rather than data |
| // flow. For example by lowering the expression: return (A && B && C) |
| // |
| // as: return A ? true : B && C. |
| // |
| // There's code in SimplifyCFG that code be used to turn control flow in data |
| // flow using SelectInsts. Selects are slow on some architectures (P7/P8), so |
| // this probably isn't good in general, but for the special case of i1, the |
| // Selects could be further lowered to bit operations that are fast everywhere. |
| // |
| //===----------------------------------------------------------------------===// |
| |
| #include "PPC.h" |
| #include "PPCTargetMachine.h" |
| #include "llvm/ADT/DenseMap.h" |
| #include "llvm/ADT/STLExtras.h" |
| #include "llvm/ADT/SmallPtrSet.h" |
| #include "llvm/ADT/SmallVector.h" |
| #include "llvm/ADT/Statistic.h" |
| #include "llvm/IR/Argument.h" |
| #include "llvm/IR/Constants.h" |
| #include "llvm/IR/Dominators.h" |
| #include "llvm/IR/Function.h" |
| #include "llvm/IR/Instruction.h" |
| #include "llvm/IR/Instructions.h" |
| #include "llvm/IR/IntrinsicInst.h" |
| #include "llvm/IR/OperandTraits.h" |
| #include "llvm/IR/Type.h" |
| #include "llvm/IR/Use.h" |
| #include "llvm/IR/User.h" |
| #include "llvm/IR/Value.h" |
| #include "llvm/Pass.h" |
| #include "llvm/CodeGen/TargetPassConfig.h" |
| #include "llvm/Support/Casting.h" |
| #include <cassert> |
| |
| using namespace llvm; |
| |
| namespace { |
| |
| #define DEBUG_TYPE "ppc-bool-ret-to-int" |
| |
| STATISTIC(NumBoolRetPromotion, |
| "Number of times a bool feeding a RetInst was promoted to an int"); |
| STATISTIC(NumBoolCallPromotion, |
| "Number of times a bool feeding a CallInst was promoted to an int"); |
| STATISTIC(NumBoolToIntPromotion, |
| "Total number of times a bool was promoted to an int"); |
| |
| class PPCBoolRetToInt : public FunctionPass { |
| static SmallPtrSet<Value *, 8> findAllDefs(Value *V) { |
| SmallPtrSet<Value *, 8> Defs; |
| SmallVector<Value *, 8> WorkList; |
| WorkList.push_back(V); |
| Defs.insert(V); |
| while (!WorkList.empty()) { |
| Value *Curr = WorkList.pop_back_val(); |
| auto *CurrUser = dyn_cast<User>(Curr); |
| // Operands of CallInst/Constant are skipped because they may not be Bool |
| // type. For CallInst, their positions are defined by ABI. |
| if (CurrUser && !isa<CallInst>(Curr) && !isa<Constant>(Curr)) |
| for (auto &Op : CurrUser->operands()) |
| if (Defs.insert(Op).second) |
| WorkList.push_back(Op); |
| } |
| return Defs; |
| } |
| |
| // Translate a i1 value to an equivalent i32/i64 value: |
| Value *translate(Value *V) { |
| assert(V->getType() == Type::getInt1Ty(V->getContext()) && |
| "Expect an i1 value"); |
| |
| Type *IntTy = ST->isPPC64() ? Type::getInt64Ty(V->getContext()) |
| : Type::getInt32Ty(V->getContext()); |
| |
| if (auto *C = dyn_cast<Constant>(V)) |
| return ConstantExpr::getZExt(C, IntTy); |
| if (auto *P = dyn_cast<PHINode>(V)) { |
| // Temporarily set the operands to 0. We'll fix this later in |
| // runOnUse. |
| Value *Zero = Constant::getNullValue(IntTy); |
| PHINode *Q = |
| PHINode::Create(IntTy, P->getNumIncomingValues(), P->getName(), P); |
| for (unsigned i = 0; i < P->getNumOperands(); ++i) |
| Q->addIncoming(Zero, P->getIncomingBlock(i)); |
| return Q; |
| } |
| |
| auto *A = dyn_cast<Argument>(V); |
| auto *I = dyn_cast<Instruction>(V); |
| assert((A || I) && "Unknown value type"); |
| |
| auto InstPt = |
| A ? &*A->getParent()->getEntryBlock().begin() : I->getNextNode(); |
| return new ZExtInst(V, IntTy, "", InstPt); |
| } |
| |
| typedef SmallPtrSet<const PHINode *, 8> PHINodeSet; |
| |
| // A PHINode is Promotable if: |
| // 1. Its type is i1 AND |
| // 2. All of its uses are ReturnInt, CallInst, PHINode, or DbgInfoIntrinsic |
| // AND |
| // 3. All of its operands are Constant or Argument or |
| // CallInst or PHINode AND |
| // 4. All of its PHINode uses are Promotable AND |
| // 5. All of its PHINode operands are Promotable |
| static PHINodeSet getPromotablePHINodes(const Function &F) { |
| PHINodeSet Promotable; |
| // Condition 1 |
| for (auto &BB : F) |
| for (auto &I : BB) |
| if (const auto *P = dyn_cast<PHINode>(&I)) |
| if (P->getType()->isIntegerTy(1)) |
| Promotable.insert(P); |
| |
| SmallVector<const PHINode *, 8> ToRemove; |
| for (const PHINode *P : Promotable) { |
| // Condition 2 and 3 |
| auto IsValidUser = [] (const Value *V) -> bool { |
| return isa<ReturnInst>(V) || isa<CallInst>(V) || isa<PHINode>(V) || |
| isa<DbgInfoIntrinsic>(V); |
| }; |
| auto IsValidOperand = [] (const Value *V) -> bool { |
| return isa<Constant>(V) || isa<Argument>(V) || isa<CallInst>(V) || |
| isa<PHINode>(V); |
| }; |
| const auto &Users = P->users(); |
| const auto &Operands = P->operands(); |
| if (!llvm::all_of(Users, IsValidUser) || |
| !llvm::all_of(Operands, IsValidOperand)) |
| ToRemove.push_back(P); |
| } |
| |
| // Iterate to convergence |
| auto IsPromotable = [&Promotable] (const Value *V) -> bool { |
| const auto *Phi = dyn_cast<PHINode>(V); |
| return !Phi || Promotable.count(Phi); |
| }; |
| while (!ToRemove.empty()) { |
| for (auto &User : ToRemove) |
| Promotable.erase(User); |
| ToRemove.clear(); |
| |
| for (const PHINode *P : Promotable) { |
| // Condition 4 and 5 |
| const auto &Users = P->users(); |
| const auto &Operands = P->operands(); |
| if (!llvm::all_of(Users, IsPromotable) || |
| !llvm::all_of(Operands, IsPromotable)) |
| ToRemove.push_back(P); |
| } |
| } |
| |
| return Promotable; |
| } |
| |
| typedef DenseMap<Value *, Value *> B2IMap; |
| |
| public: |
| static char ID; |
| |
| PPCBoolRetToInt() : FunctionPass(ID) { |
| initializePPCBoolRetToIntPass(*PassRegistry::getPassRegistry()); |
| } |
| |
| bool runOnFunction(Function &F) override { |
| if (skipFunction(F)) |
| return false; |
| |
| auto *TPC = getAnalysisIfAvailable<TargetPassConfig>(); |
| if (!TPC) |
| return false; |
| |
| auto &TM = TPC->getTM<PPCTargetMachine>(); |
| ST = TM.getSubtargetImpl(F); |
| |
| PHINodeSet PromotablePHINodes = getPromotablePHINodes(F); |
| B2IMap Bool2IntMap; |
| bool Changed = false; |
| for (auto &BB : F) { |
| for (auto &I : BB) { |
| if (auto *R = dyn_cast<ReturnInst>(&I)) |
| if (F.getReturnType()->isIntegerTy(1)) |
| Changed |= |
| runOnUse(R->getOperandUse(0), PromotablePHINodes, Bool2IntMap); |
| |
| if (auto *CI = dyn_cast<CallInst>(&I)) |
| for (auto &U : CI->operands()) |
| if (U->getType()->isIntegerTy(1)) |
| Changed |= runOnUse(U, PromotablePHINodes, Bool2IntMap); |
| } |
| } |
| |
| return Changed; |
| } |
| |
| bool runOnUse(Use &U, const PHINodeSet &PromotablePHINodes, |
| B2IMap &BoolToIntMap) { |
| auto Defs = findAllDefs(U); |
| |
| // If the values are all Constants or Arguments, don't bother |
| if (llvm::none_of(Defs, [](Value *V) { return isa<Instruction>(V); })) |
| return false; |
| |
| // Presently, we only know how to handle PHINode, Constant, Arguments and |
| // CallInst. Potentially, bitwise operations (AND, OR, XOR, NOT) and sign |
| // extension could also be handled in the future. |
| for (Value *V : Defs) |
| if (!isa<PHINode>(V) && !isa<Constant>(V) && |
| !isa<Argument>(V) && !isa<CallInst>(V)) |
| return false; |
| |
| for (Value *V : Defs) |
| if (const auto *P = dyn_cast<PHINode>(V)) |
| if (!PromotablePHINodes.count(P)) |
| return false; |
| |
| if (isa<ReturnInst>(U.getUser())) |
| ++NumBoolRetPromotion; |
| if (isa<CallInst>(U.getUser())) |
| ++NumBoolCallPromotion; |
| ++NumBoolToIntPromotion; |
| |
| for (Value *V : Defs) |
| if (!BoolToIntMap.count(V)) |
| BoolToIntMap[V] = translate(V); |
| |
| // Replace the operands of the translated instructions. They were set to |
| // zero in the translate function. |
| for (auto &Pair : BoolToIntMap) { |
| auto *First = dyn_cast<User>(Pair.first); |
| auto *Second = dyn_cast<User>(Pair.second); |
| assert((!First || Second) && "translated from user to non-user!?"); |
| // Operands of CallInst/Constant are skipped because they may not be Bool |
| // type. For CallInst, their positions are defined by ABI. |
| if (First && !isa<CallInst>(First) && !isa<Constant>(First)) |
| for (unsigned i = 0; i < First->getNumOperands(); ++i) |
| Second->setOperand(i, BoolToIntMap[First->getOperand(i)]); |
| } |
| |
| Value *IntRetVal = BoolToIntMap[U]; |
| Type *Int1Ty = Type::getInt1Ty(U->getContext()); |
| auto *I = cast<Instruction>(U.getUser()); |
| Value *BackToBool = new TruncInst(IntRetVal, Int1Ty, "backToBool", I); |
| U.set(BackToBool); |
| |
| return true; |
| } |
| |
| void getAnalysisUsage(AnalysisUsage &AU) const override { |
| AU.addPreserved<DominatorTreeWrapperPass>(); |
| FunctionPass::getAnalysisUsage(AU); |
| } |
| |
| private: |
| const PPCSubtarget *ST; |
| }; |
| |
| } // end anonymous namespace |
| |
| char PPCBoolRetToInt::ID = 0; |
| INITIALIZE_PASS(PPCBoolRetToInt, "ppc-bool-ret-to-int", |
| "Convert i1 constants to i32/i64 if they are returned", false, |
| false) |
| |
| FunctionPass *llvm::createPPCBoolRetToIntPass() { return new PPCBoolRetToInt(); } |