| //===- ExpandLargeIntegers.cpp - Expand illegal integers for PNaCl ABI ----===// |
| // |
| // The LLVM Compiler Infrastructure |
| // |
| // This file is distributed under the University of Illinois Open Source |
| // License. See LICENSE.TXT for details. |
| // |
| // A limited set of transformations to expand illegal-sized int types. |
| // |
| //===----------------------------------------------------------------------===// |
| // |
| // Legal sizes for the purposes of expansion are anything 64 bits or less. |
| // Operations on large integers are split into operations on smaller-sized |
| // integers. The low parts should always be powers of 2, but the high parts may |
| // not be. A subsequent pass can promote those. For now this pass only intends |
| // to support the uses generated by clang, which is basically just for large |
| // bitfields. |
| // |
| // Limitations: |
| // 1) It can't change function signatures or global variables. |
| // 3) Doesn't support mul, div/rem, switch. |
| // 4) Doesn't handle arrays or structs (or GEPs) with illegal types. |
| // 5) Doesn't handle constant expressions (it also doesn't produce them, so it |
| // can run after ExpandConstantExpr). |
| // |
| //===----------------------------------------------------------------------===// |
| |
| #include "llvm/ADT/DenseMap.h" |
| #include "llvm/ADT/PostOrderIterator.h" |
| #include "llvm/ADT/STLExtras.h" |
| #include "llvm/ADT/SmallVector.h" |
| #include "llvm/IR/CFG.h" |
| #include "llvm/IR/DataLayout.h" |
| #include "llvm/IR/DerivedTypes.h" |
| #include "llvm/IR/Function.h" |
| #include "llvm/IR/IRBuilder.h" |
| #include "llvm/IR/Instructions.h" |
| #include "llvm/Pass.h" |
| #include "llvm/Support/Debug.h" |
| #include "llvm/Support/MathExtras.h" |
| #include "llvm/Support/raw_ostream.h" |
| #include "llvm/Transforms/NaCl.h" |
| |
| using namespace llvm; |
| |
| #define DEBUG_TYPE "nacl-expand-ints" |
| |
| // Break instructions up into no larger than 64-bit chunks. |
| static const unsigned kChunkBits = 64; |
| static const unsigned kChunkBytes = kChunkBits / CHAR_BIT; |
| |
| namespace { |
| class ExpandLargeIntegers : public FunctionPass { |
| public: |
| static char ID; |
| ExpandLargeIntegers() : FunctionPass(ID) { |
| initializeExpandLargeIntegersPass(*PassRegistry::getPassRegistry()); |
| } |
| bool runOnFunction(Function &F) override; |
| }; |
| |
| template <typename T> struct LoHiPair { |
| T Lo, Hi; |
| LoHiPair() : Lo(), Hi() {} |
| LoHiPair(T Lo, T Hi) : Lo(Lo), Hi(Hi) {} |
| }; |
| template <typename T> struct LoHiBitTriple { |
| T Lo, Hi, Bit; |
| LoHiBitTriple() : Lo(), Hi(), Bit() {} |
| LoHiBitTriple(T Lo, T Hi, T Bit) : Lo(Lo), Hi(Hi), Bit(Bit) {} |
| }; |
| typedef LoHiPair<IntegerType *> TypePair; |
| typedef LoHiPair<Value *> ValuePair; |
| typedef LoHiPair<unsigned> AlignPair; |
| typedef LoHiBitTriple<Value *> ValueTriple; |
| |
| // Information needed to patch a phi node which forward-references a value. |
| struct ForwardPHI { |
| Value *Val; |
| PHINode *Lo, *Hi; |
| unsigned ValueNumber; |
| ForwardPHI(Value *Val, PHINode *Lo, PHINode *Hi, unsigned ValueNumber) |
| : Val(Val), Lo(Lo), Hi(Hi), ValueNumber(ValueNumber) {} |
| }; |
| } |
| |
| char ExpandLargeIntegers::ID = 0; |
| INITIALIZE_PASS(ExpandLargeIntegers, "nacl-expand-ints", |
| "Expand integer types that are illegal in PNaCl", false, false) |
| |
| #define DIE_IF(COND, VAL, MSG) \ |
| do { \ |
| if (COND) { \ |
| errs() << "Unsupported: " << *(VAL) << '\n'; \ |
| report_fatal_error( \ |
| MSG " not yet supported for integer types larger than 64 bits"); \ |
| } \ |
| } while (0) |
| |
| static bool isLegalBitSize(unsigned Bits) { |
| assert(Bits && "Can't have zero-size integers"); |
| return Bits <= kChunkBits; |
| } |
| |
| static TypePair getExpandedIntTypes(const Type *Ty) { |
| unsigned BitWidth = Ty->getIntegerBitWidth(); |
| assert(!isLegalBitSize(BitWidth)); |
| return {IntegerType::get(Ty->getContext(), kChunkBits), |
| IntegerType::get(Ty->getContext(), BitWidth - kChunkBits)}; |
| } |
| |
| static bool shouldConvert(const Type *Ty) { |
| if (const IntegerType *ITy = dyn_cast<IntegerType>(Ty)) |
| return !isLegalBitSize(ITy->getBitWidth()); |
| return false; |
| } |
| // Return true if Val is an int which should be converted. |
| static bool shouldConvert(const Value *Val) { |
| return shouldConvert(Val->getType()); |
| } |
| |
| // Return a pair of constants expanded from C. |
| static ValuePair expandConstant(Constant *C) { |
| assert(shouldConvert(C)); |
| TypePair ExpandedTypes = getExpandedIntTypes(C->getType()); |
| if (isa<UndefValue>(C)) { |
| return {UndefValue::get(ExpandedTypes.Lo), |
| UndefValue::get(ExpandedTypes.Hi)}; |
| } else if (ConstantInt *CInt = dyn_cast<ConstantInt>(C)) { |
| Constant *ShiftAmt = ConstantInt::get( |
| CInt->getType(), ExpandedTypes.Lo->getBitWidth(), false); |
| return {ConstantExpr::getTrunc(CInt, ExpandedTypes.Lo), |
| ConstantExpr::getTrunc(ConstantExpr::getLShr(CInt, ShiftAmt), |
| ExpandedTypes.Hi)}; |
| } |
| DIE_IF(true, C, "Constant value"); |
| } |
| |
| template <typename T> |
| static AlignPair getAlign(const DataLayout &DL, T *I, Type *PrefAlignTy) { |
| unsigned LoAlign = I->getAlignment(); |
| if (LoAlign == 0) |
| LoAlign = DL.getPrefTypeAlignment(PrefAlignTy); |
| unsigned HiAlign = MinAlign(LoAlign, kChunkBytes); |
| return {LoAlign, HiAlign}; |
| } |
| |
| static ValuePair createBit(IRBuilder<> *IRB, const BinaryOperator *Binop, |
| const ValuePair &Lhs, const ValuePair &Rhs, |
| const TypePair &Tys, const StringRef &Name) { |
| auto Op = Binop->getOpcode(); |
| Value *Lo = IRB->CreateBinOp(Op, Lhs.Lo, Rhs.Lo, Twine(Name, ".lo")); |
| Value *Hi = IRB->CreateBinOp(Op, Lhs.Hi, Rhs.Hi, Twine(Name, ".hi")); |
| return {Lo, Hi}; |
| } |
| |
| static ValuePair createShl(IRBuilder<> *IRB, const BinaryOperator *Binop, |
| const ValuePair &Lhs, const ValuePair &Rhs, |
| const TypePair &Tys, const StringRef &Name) { |
| ConstantInt *ShlAmount = dyn_cast<ConstantInt>(Rhs.Lo); |
| // TODO(dschuff): Expansion of variable-sized shifts isn't supported |
| // because the behavior depends on whether the shift amount is less than |
| // the size of the low part of the expanded type, and I haven't yet |
| // figured out a way to do it for variable-sized shifts without splitting |
| // the basic block. I don't believe it's actually necessary for |
| // bitfields. Likewise for LShr below. |
| DIE_IF(!ShlAmount, Binop, "Expansion of variable-sized shifts"); |
| unsigned ShiftAmount = ShlAmount->getZExtValue(); |
| if (ShiftAmount >= Binop->getType()->getIntegerBitWidth()) |
| ShiftAmount = 0; // Undefined behavior. |
| unsigned HiBits = Tys.Hi->getIntegerBitWidth(); |
| // |<------------Hi---------->|<-------Lo------>| |
| // | | | |
| // +--------+--------+--------+--------+--------+ |
| // |abcdefghijklmnopqrstuvwxyz|ABCDEFGHIJKLMNOPQ| |
| // +--------+--------+--------+--------+--------+ |
| // Possible shifts: |
| // |efghijklmnopqrstuvwxyzABCD|EFGHIJKLMNOPQ0000| Some Lo into Hi. |
| // |vwxyzABCDEFGHIJKLMNOPQ0000|00000000000000000| Lo is 0, keep some Hi. |
| // |DEFGHIJKLMNOPQ000000000000|00000000000000000| Lo is 0, no Hi left. |
| Value *Lo, *Hi; |
| if (ShiftAmount < kChunkBits) { |
| Lo = IRB->CreateShl(Lhs.Lo, ShiftAmount, Twine(Name, ".lo")); |
| Hi = |
| IRB->CreateZExtOrTrunc(IRB->CreateLShr(Lhs.Lo, kChunkBits - ShiftAmount, |
| Twine(Name, ".lo.shr")), |
| Tys.Hi, Twine(Name, ".lo.ext")); |
| } else { |
| Lo = ConstantInt::get(Tys.Lo, 0); |
| Hi = IRB->CreateShl( |
| IRB->CreateZExtOrTrunc(Lhs.Lo, Tys.Hi, Twine(Name, ".lo.ext")), |
| ShiftAmount - kChunkBits, Twine(Name, ".lo.shl")); |
| } |
| if (ShiftAmount < HiBits) |
| Hi = IRB->CreateOr( |
| Hi, IRB->CreateShl(Lhs.Hi, ShiftAmount, Twine(Name, ".hi.shl")), |
| Twine(Name, ".or")); |
| return {Lo, Hi}; |
| } |
| |
| static ValuePair createShr(IRBuilder<> *IRB, const BinaryOperator *Binop, |
| const ValuePair &Lhs, const ValuePair &Rhs, |
| const TypePair &Tys, const StringRef &Name) { |
| auto Op = Binop->getOpcode(); |
| ConstantInt *ShrAmount = dyn_cast<ConstantInt>(Rhs.Lo); |
| // TODO(dschuff): Expansion of variable-sized shifts isn't supported |
| // because the behavior depends on whether the shift amount is less than |
| // the size of the low part of the expanded type, and I haven't yet |
| // figured out a way to do it for variable-sized shifts without splitting |
| // the basic block. I don't believe it's actually necessary for bitfields. |
| DIE_IF(!ShrAmount, Binop, "Expansion of variable-sized shifts"); |
| bool IsArith = Op == Instruction::AShr; |
| unsigned ShiftAmount = ShrAmount->getZExtValue(); |
| if (ShiftAmount >= Binop->getType()->getIntegerBitWidth()) |
| ShiftAmount = 0; // Undefined behavior. |
| unsigned HiBitWidth = Tys.Hi->getIntegerBitWidth(); |
| // |<--Hi-->|<-------Lo------>| |
| // | | | |
| // +--------+--------+--------+ |
| // |abcdefgh|ABCDEFGHIJKLMNOPQ| |
| // +--------+--------+--------+ |
| // Possible shifts (0 is sign when doing AShr): |
| // |0000abcd|defgABCDEFGHIJKLM| Some Hi into Lo. |
| // |00000000|00abcdefgABCDEFGH| Hi is 0, keep some Lo. |
| // |00000000|000000000000abcde| Hi is 0, no Lo left. |
| Value *Lo, *Hi; |
| if (ShiftAmount < kChunkBits) { |
| Lo = IRB->CreateShl( |
| IsArith |
| ? IRB->CreateSExtOrTrunc(Lhs.Hi, Tys.Lo, Twine(Name, ".hi.ext")) |
| : IRB->CreateZExtOrTrunc(Lhs.Hi, Tys.Lo, Twine(Name, ".hi.ext")), |
| kChunkBits - ShiftAmount, Twine(Name, ".hi.shl")); |
| Lo = IRB->CreateOr( |
| Lo, IRB->CreateLShr(Lhs.Lo, ShiftAmount, Twine(Name, ".lo.shr")), |
| Twine(Name, ".lo")); |
| } else { |
| Lo = IRB->CreateBinOp(Op, Lhs.Hi, |
| ConstantInt::get(Tys.Hi, ShiftAmount - kChunkBits), |
| Twine(Name, ".hi.shr")); |
| Lo = IsArith ? IRB->CreateSExtOrTrunc(Lo, Tys.Lo, Twine(Name, ".lo.ext")) |
| : IRB->CreateZExtOrTrunc(Lo, Tys.Lo, Twine(Name, ".lo.ext")); |
| } |
| if (ShiftAmount < HiBitWidth) { |
| Hi = IRB->CreateBinOp(Op, Lhs.Hi, ConstantInt::get(Tys.Hi, ShiftAmount), |
| Twine(Name, ".hi")); |
| } else { |
| Hi = IsArith ? IRB->CreateAShr(Lhs.Hi, HiBitWidth - 1, Twine(Name, ".hi")) |
| : ConstantInt::get(Tys.Hi, 0); |
| } |
| return {Lo, Hi}; |
| } |
| |
| static Value *createCarry(IRBuilder<> *IRB, Value *Lhs, Value *Rhs, |
| Value *Added, Type *Ty, const StringRef &Name) { |
| return IRB->CreateZExt( |
| IRB->CreateICmpULT( |
| Added, |
| IRB->CreateSelect(IRB->CreateICmpULT(Lhs, Rhs, Twine(Name, ".cmp")), |
| Rhs, Lhs, Twine(Name, ".limit")), |
| Twine(Name, ".overflowed")), |
| Ty, Twine(Name, ".carry")); |
| } |
| |
| static ValueTriple createAdd(IRBuilder<> *IRB, const ValuePair &Lhs, |
| const ValuePair &Rhs, const TypePair &Tys, |
| const StringRef &Name, Type *HiCarryTy) { |
| auto Op = Instruction::Add; |
| // Don't propagate NUW/NSW to the lo operation: it can overflow. |
| Value *Lo = IRB->CreateBinOp(Op, Lhs.Lo, Rhs.Lo, Twine(Name, ".lo")); |
| Value *LoCarry = createCarry(IRB, Lhs.Lo, Rhs.Lo, Lo, Tys.Hi, Name); |
| // TODO(jfb) The hi operation could be tagged with NUW/NSW. |
| Value *HiAdd = IRB->CreateBinOp(Op, Lhs.Hi, Rhs.Hi, Twine(Name, ".hi")); |
| Value *Hi = IRB->CreateBinOp(Op, HiAdd, LoCarry, Twine(Name, ".carried")); |
| Value *HiCarry = HiCarryTy |
| ? createCarry(IRB, Lhs.Hi, Rhs.Hi, Hi, HiCarryTy, Name) |
| : nullptr; |
| return {Lo, Hi, HiCarry}; |
| } |
| |
| static ValuePair createSub(IRBuilder<> *IRB, const ValuePair &Lhs, |
| const ValuePair &Rhs, const TypePair &Tys, |
| const StringRef &Name) { |
| auto Op = Instruction::Sub; |
| Value *Borrowed = IRB->CreateSExt( |
| IRB->CreateICmpULT(Lhs.Lo, Rhs.Lo, Twine(Name, ".borrow")), Tys.Hi, |
| Twine(Name, ".borrowing")); |
| Value *Lo = IRB->CreateBinOp(Op, Lhs.Lo, Rhs.Lo, Twine(Name, ".lo")); |
| Value *Hi = |
| IRB->CreateBinOp(Instruction::Add, |
| IRB->CreateBinOp(Op, Lhs.Hi, Rhs.Hi, Twine(Name, ".hi")), |
| Borrowed, Twine(Name, ".borrowed")); |
| return {Lo, Hi}; |
| } |
| |
| static Value *createICmpEquality(IRBuilder<> *IRB, CmpInst::Predicate Pred, |
| const ValuePair &Lhs, const ValuePair &Rhs, |
| const StringRef &Name) { |
| assert(Pred == CmpInst::ICMP_EQ || Pred == CmpInst::ICMP_NE); |
| Value *Lo = IRB->CreateICmp(Pred, Lhs.Lo, Rhs.Lo, Twine(Name, ".lo")); |
| Value *Hi = IRB->CreateICmp(Pred, Lhs.Hi, Rhs.Hi, Twine(Name, ".hi")); |
| return IRB->CreateBinOp( |
| Instruction::And, Lo, Hi, |
| Twine(Name, Pred == CmpInst::ICMP_EQ ? ".eq" : ".ne")); |
| } |
| |
| static Value *createICmp(IRBuilder<> *IRB, const ICmpInst *ICmp, |
| const ValuePair &Lhs, const ValuePair &Rhs, |
| const TypePair &Tys, const StringRef &Name) { |
| auto Pred = ICmp->getPredicate(); |
| switch (Pred) { |
| case CmpInst::ICMP_EQ: |
| case CmpInst::ICMP_NE: |
| return createICmpEquality(IRB, ICmp->getPredicate(), Lhs, Rhs, Name); |
| |
| case CmpInst::ICMP_UGT: // C == 1 and Z == 0 |
| case CmpInst::ICMP_UGE: // C == 1 |
| case CmpInst::ICMP_ULT: // C == 0 and Z == 0 |
| case CmpInst::ICMP_ULE: // C == 0 |
| { |
| Value *Carry = createAdd(IRB, Lhs, Rhs, Tys, Name, ICmp->getType()).Bit; |
| if (Pred == CmpInst::ICMP_ULT || Pred == CmpInst::ICMP_ULE) |
| Carry = IRB->CreateNot(Carry, Name); |
| if (Pred == CmpInst::ICMP_UGT || Pred == CmpInst::ICMP_ULT) |
| Carry = IRB->CreateBinOp( |
| Instruction::And, Carry, |
| createICmpEquality(IRB, CmpInst::ICMP_EQ, Lhs, Rhs, Name), Name); |
| return Carry; |
| } |
| |
| case CmpInst::ICMP_SGT: // N == V and Z == 0 |
| case CmpInst::ICMP_SGE: // N == V |
| case CmpInst::ICMP_SLT: // N != V |
| case CmpInst::ICMP_SLE: // N != V or Z == 1 |
| DIE_IF(true, ICmp, "Signed comparisons"); |
| default: |
| llvm_unreachable("Invalid integer comparison"); |
| } |
| } |
| |
| static ValuePair createLoad(IRBuilder<> *IRB, const DataLayout &DL, |
| LoadInst *Load) { |
| DIE_IF(!Load->isSimple(), Load, "Volatile and atomic loads"); |
| Value *Op = Load->getPointerOperand(); |
| TypePair Tys = getExpandedIntTypes(Load->getType()); |
| AlignPair Align = getAlign(DL, Load, Load->getType()); |
| Value *Loty = IRB->CreateBitCast(Op, Tys.Lo->getPointerTo(), |
| Twine(Op->getName(), ".loty")); |
| Value *Lo = |
| IRB->CreateAlignedLoad(Loty, Align.Lo, Twine(Load->getName(), ".lo")); |
| Value *HiAddr = |
| IRB->CreateConstGEP1_32(Loty, 1, Twine(Op->getName(), ".hi.gep")); |
| Value *HiTy = IRB->CreateBitCast(HiAddr, Tys.Hi->getPointerTo(), |
| Twine(Op->getName(), ".hity")); |
| Value *Hi = |
| IRB->CreateAlignedLoad(HiTy, Align.Hi, Twine(Load->getName(), ".hi")); |
| return {Lo, Hi}; |
| } |
| |
| static ValuePair createStore(IRBuilder<> *IRB, const DataLayout &DL, |
| StoreInst *Store, const ValuePair &StoreVals) { |
| DIE_IF(!Store->isSimple(), Store, "Volatile and atomic stores"); |
| Value *Ptr = Store->getPointerOperand(); |
| TypePair Tys = getExpandedIntTypes(Store->getValueOperand()->getType()); |
| AlignPair Align = getAlign(DL, Store, Store->getValueOperand()->getType()); |
| Value *Loty = IRB->CreateBitCast(Ptr, Tys.Lo->getPointerTo(), |
| Twine(Ptr->getName(), ".loty")); |
| Value *Lo = IRB->CreateAlignedStore(StoreVals.Lo, Loty, Align.Lo); |
| Value *HiAddr = |
| IRB->CreateConstGEP1_32(Loty, 1, Twine(Ptr->getName(), ".hi.gep")); |
| Value *HiTy = IRB->CreateBitCast(HiAddr, Tys.Hi->getPointerTo(), |
| Twine(Ptr->getName(), ".hity")); |
| Value *Hi = IRB->CreateAlignedStore(StoreVals.Hi, HiTy, Align.Hi); |
| return {Lo, Hi}; |
| } |
| |
| namespace { |
| // Holds the state for converting/replacing values. We visit instructions in |
| // reverse post-order, phis are therefore the only instructions which can be |
| // visited before the value they use. |
| class ConversionState { |
| public: |
| // Return the expanded values for Val. |
| ValuePair getConverted(Value *Val) { |
| assert(shouldConvert(Val)); |
| // Directly convert constants. |
| if (Constant *C = dyn_cast<Constant>(Val)) |
| return expandConstant(C); |
| if (RewrittenIllegals.count(Val)) { |
| ValuePair Found = RewrittenIllegals[Val]; |
| if (RewrittenLegals.count(Found.Lo)) |
| Found.Lo = RewrittenLegals[Found.Lo]; |
| if (RewrittenLegals.count(Found.Hi)) |
| Found.Hi = RewrittenLegals[Found.Hi]; |
| return Found; |
| } |
| errs() << "Value: " << *Val << "\n"; |
| report_fatal_error("Expanded value not found in map"); |
| } |
| |
| // Returns whether a converted value has been recorded. This is only useful |
| // for phi instructions: they can be encountered before the incoming |
| // instruction, whereas RPO order guarantees that other instructions always |
| // use converted values. |
| bool hasConverted(Value *Val) { |
| assert(shouldConvert(Val)); |
| return dyn_cast<Constant>(Val) || RewrittenIllegals.count(Val); |
| } |
| |
| // Record a forward phi, temporarily setting it to use Undef. This will be |
| // patched up at the end of RPO. |
| ValuePair recordForwardPHI(Value *Val, PHINode *Lo, PHINode *Hi, |
| unsigned ValueNumber) { |
| DEBUG(dbgs() << "\tRecording as forward PHI\n"); |
| ForwardPHIs.push_back(ForwardPHI(Val, Lo, Hi, ValueNumber)); |
| return {UndefValue::get(Lo->getType()), UndefValue::get(Hi->getType())}; |
| } |
| |
| void recordConverted(Instruction *From, const ValuePair &To) { |
| DEBUG(dbgs() << "\tTo: " << *To.Lo << "\n"); |
| DEBUG(dbgs() << "\tAnd: " << *To.Hi << "\n"); |
| ToErase.push_back(From); |
| RewrittenIllegals[From] = To; |
| } |
| |
| // Replace the uses of From with To, give From's name to To, and mark To for |
| // deletion. |
| void recordConverted(Instruction *From, Value *To) { |
| assert(!shouldConvert(From)); |
| DEBUG(dbgs() << "\tTo: " << *To << "\n"); |
| ToErase.push_back(From); |
| // From does not produce an illegal value, update its users in place. |
| From->replaceAllUsesWith(To); |
| To->takeName(From); |
| RewrittenLegals[From] = To; |
| } |
| |
| void patchForwardPHIs() { |
| DEBUG(if (!ForwardPHIs.empty()) dbgs() << "Patching forward PHIs:\n"); |
| for (ForwardPHI &F : ForwardPHIs) { |
| ValuePair Ops = getConverted(F.Val); |
| F.Lo->setIncomingValue(F.ValueNumber, Ops.Lo); |
| F.Hi->setIncomingValue(F.ValueNumber, Ops.Hi); |
| DEBUG(dbgs() << "\t" << *F.Lo << "\n\t" << *F.Hi << "\n"); |
| } |
| } |
| |
| void eraseReplacedInstructions() { |
| for (Instruction *I : ToErase) |
| I->dropAllReferences(); |
| for (Instruction *I : ToErase) |
| I->eraseFromParent(); |
| } |
| |
| private: |
| // Maps illegal values to their new converted lo/hi values. |
| DenseMap<Value *, ValuePair> RewrittenIllegals; |
| // Maps legal values to their new converted value. |
| DenseMap<Value *, Value *> RewrittenLegals; |
| // Illegal values which have already been converted, will be erased. |
| SmallVector<Instruction *, 32> ToErase; |
| // PHIs which were encountered but had forward references. They need to get |
| // patched up after RPO traversal. |
| SmallVector<ForwardPHI, 32> ForwardPHIs; |
| }; |
| } // Anonymous namespace |
| |
| static void convertInstruction(Instruction *Inst, ConversionState &State, |
| const DataLayout &DL) { |
| DEBUG(dbgs() << "Expanding Large Integer: " << *Inst << "\n"); |
| // Set the insert point *after* Inst, so that any instructions inserted here |
| // will be visited again. That allows iterative expansion of types > i128. |
| BasicBlock::iterator InsertPos(Inst); |
| IRBuilder<> IRB(++InsertPos); |
| StringRef Name = Inst->getName(); |
| |
| if (PHINode *Phi = dyn_cast<PHINode>(Inst)) { |
| unsigned N = Phi->getNumIncomingValues(); |
| TypePair OpTys = getExpandedIntTypes(Phi->getIncomingValue(0)->getType()); |
| PHINode *Lo = IRB.CreatePHI(OpTys.Lo, N, Twine(Name + ".lo")); |
| PHINode *Hi = IRB.CreatePHI(OpTys.Hi, N, Twine(Name + ".hi")); |
| for (unsigned I = 0; I != N; ++I) { |
| Value *InVal = Phi->getIncomingValue(I); |
| BasicBlock *InBB = Phi->getIncomingBlock(I); |
| // If the value hasn't already been converted then this is a |
| // forward-reference PHI which needs to be patched up after RPO traversal. |
| ValuePair Ops = State.hasConverted(InVal) |
| ? State.getConverted(InVal) |
| : State.recordForwardPHI(InVal, Lo, Hi, I); |
| Lo->addIncoming(Ops.Lo, InBB); |
| Hi->addIncoming(Ops.Hi, InBB); |
| } |
| State.recordConverted(Phi, {Lo, Hi}); |
| |
| } else if (ZExtInst *ZExt = dyn_cast<ZExtInst>(Inst)) { |
| Value *Operand = ZExt->getOperand(0); |
| Type *OpTy = Operand->getType(); |
| TypePair Tys = getExpandedIntTypes(Inst->getType()); |
| Value *Lo, *Hi; |
| if (OpTy->getIntegerBitWidth() <= kChunkBits) { |
| Lo = IRB.CreateZExt(Operand, Tys.Lo, Twine(Name, ".lo")); |
| Hi = ConstantInt::get(Tys.Hi, 0); |
| } else { |
| ValuePair Ops = State.getConverted(Operand); |
| Lo = Ops.Lo; |
| Hi = IRB.CreateZExt(Ops.Hi, Tys.Hi, Twine(Name, ".hi")); |
| } |
| State.recordConverted(ZExt, {Lo, Hi}); |
| |
| } else if (TruncInst *Trunc = dyn_cast<TruncInst>(Inst)) { |
| Value *Operand = Trunc->getOperand(0); |
| assert(shouldConvert(Operand) && "TruncInst is expandable but not its op"); |
| ValuePair Ops = State.getConverted(Operand); |
| if (!shouldConvert(Inst)) { |
| Value *NewInst = IRB.CreateTrunc(Ops.Lo, Trunc->getType(), Name); |
| State.recordConverted(Trunc, NewInst); |
| } else { |
| TypePair Tys = getExpandedIntTypes(Trunc->getType()); |
| assert(Tys.Lo == getExpandedIntTypes(Operand->getType()).Lo); |
| Value *Lo = Ops.Lo; |
| Value *Hi = IRB.CreateTrunc(Ops.Hi, Tys.Hi, Twine(Name, ".hi")); |
| State.recordConverted(Trunc, {Lo, Hi}); |
| } |
| |
| } else if (BinaryOperator *Binop = dyn_cast<BinaryOperator>(Inst)) { |
| ValuePair Lhs = State.getConverted(Binop->getOperand(0)); |
| ValuePair Rhs = State.getConverted(Binop->getOperand(1)); |
| TypePair Tys = getExpandedIntTypes(Binop->getType()); |
| ValuePair Conv; |
| switch (Binop->getOpcode()) { |
| case Instruction::And: |
| case Instruction::Or: |
| case Instruction::Xor: |
| Conv = createBit(&IRB, Binop, Lhs, Rhs, Tys, Name); |
| break; |
| case Instruction::Shl: |
| Conv = createShl(&IRB, Binop, Lhs, Rhs, Tys, Name); |
| break; |
| case Instruction::AShr: |
| case Instruction::LShr: |
| Conv = createShr(&IRB, Binop, Lhs, Rhs, Tys, Name); |
| break; |
| case Instruction::Add: { |
| ValueTriple VT = |
| createAdd(&IRB, Lhs, Rhs, Tys, Name, /*HiCarryTy=*/nullptr); |
| Conv = {VT.Lo, VT.Hi}; // Ignore Hi carry. |
| } break; |
| case Instruction::Sub: |
| Conv = createSub(&IRB, Lhs, Rhs, Tys, Name); |
| break; |
| default: |
| DIE_IF(true, Binop, "Binary operator type"); |
| } |
| State.recordConverted(Binop, Conv); |
| |
| } else if (ICmpInst *ICmp = dyn_cast<ICmpInst>(Inst)) { |
| ValuePair Lhs = State.getConverted(ICmp->getOperand(0)); |
| ValuePair Rhs = State.getConverted(ICmp->getOperand(1)); |
| TypePair Tys = getExpandedIntTypes(ICmp->getOperand(0)->getType()); |
| State.recordConverted(ICmp, createICmp(&IRB, ICmp, Lhs, Rhs, Tys, Name)); |
| |
| } else if (LoadInst *Load = dyn_cast<LoadInst>(Inst)) { |
| State.recordConverted(Load, createLoad(&IRB, DL, Load)); |
| |
| } else if (StoreInst *Store = dyn_cast<StoreInst>(Inst)) { |
| ValuePair StoreVals = State.getConverted(Store->getValueOperand()); |
| State.recordConverted(Store, createStore(&IRB, DL, Store, StoreVals)); |
| |
| } else if (SelectInst *Select = dyn_cast<SelectInst>(Inst)) { |
| Value *Cond = Select->getCondition(); |
| ValuePair True = State.getConverted(Select->getTrueValue()); |
| ValuePair False = State.getConverted(Select->getFalseValue()); |
| Value *Lo = IRB.CreateSelect(Cond, True.Lo, False.Lo, Twine(Name, ".lo")); |
| Value *Hi = IRB.CreateSelect(Cond, True.Hi, False.Hi, Twine(Name, ".hi")); |
| State.recordConverted(Select, {Lo, Hi}); |
| |
| } else { |
| DIE_IF(true, Inst, "Instruction"); |
| } |
| } |
| |
| bool ExpandLargeIntegers::runOnFunction(Function &F) { |
| // Don't support changing the function arguments. Illegal function arguments |
| // should not be generated by clang. |
| for (const Argument &Arg : F.args()) |
| if (shouldConvert(&Arg)) |
| report_fatal_error("Function " + F.getName() + |
| " has illegal integer argument"); |
| |
| if (shouldConvert(F.getReturnType())) { |
| report_fatal_error("Function " + F.getName() + |
| " has illegal integer return"); |
| } |
| |
| // TODO(jfb) This should loop to handle nested forward PHIs. |
| |
| ConversionState State; |
| DataLayout DL(F.getParent()); |
| bool Modified = false; |
| ReversePostOrderTraversal<Function *> RPOT(&F); |
| for (ReversePostOrderTraversal<Function *>::rpo_iterator FI = RPOT.begin(), |
| FE = RPOT.end(); |
| FI != FE; ++FI) { |
| BasicBlock *BB = *FI; |
| for (Instruction &I : *BB) { |
| // Only attempt to convert an instruction if its result or any of its |
| // operands are illegal. |
| bool ShouldConvert = shouldConvert(&I); |
| for (Value *Op : I.operands()) |
| ShouldConvert |= shouldConvert(Op); |
| if (ShouldConvert) { |
| convertInstruction(&I, State, DL); |
| Modified = true; |
| } |
| } |
| } |
| State.patchForwardPHIs(); |
| State.eraseReplacedInstructions(); |
| return Modified; |
| } |
| |
| FunctionPass *llvm::createExpandLargeIntegersPass() { |
| return new ExpandLargeIntegers(); |
| } |
