lib/CodeGen/IntrinsicLowering.cpp

   1 //===-- IntrinsicLowering.cpp - Intrinsic Lowering default implementation -===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by the LLVM research group and is distributed under
   6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file implements the IntrinsicLowering class.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "llvm/Constants.h"
  15 #include "llvm/DerivedTypes.h"
  16 #include "llvm/Module.h"
  17 #include "llvm/Instructions.h"
  18 #include "llvm/Type.h"
  19 #include "llvm/CodeGen/IntrinsicLowering.h"
  20 #include "llvm/Support/Streams.h"
  21 #include "llvm/Target/TargetData.h"
  22 #include "llvm/ADT/SmallVector.h"
  23 using namespace llvm;
  24
  25 template <class ArgIt>
  26 static void EnsureFunctionExists(Module &M, const char *Name,
  27                                  ArgIt ArgBegin, ArgIt ArgEnd,
  28                                  const Type *RetTy) {
  29   // Insert a correctly-typed definition now.
  30   std::vector<const Type *> ParamTys;
  31   for (ArgIt I = ArgBegin; I != ArgEnd; ++I)
  32     ParamTys.push_back(I->getType());
  33   M.getOrInsertFunction(Name, FunctionType::get(RetTy, ParamTys, false));
  34 }
  35
  36 /// ReplaceCallWith - This function is used when we want to lower an intrinsic
  37 /// call to a call of an external function.  This handles hard cases such as
  38 /// when there was already a prototype for the external function, and if that
  39 /// prototype doesn't match the arguments we expect to pass in.
  40 template <class ArgIt>
  41 static CallInst *ReplaceCallWith(const char *NewFn, CallInst *CI,
  42                                  ArgIt ArgBegin, ArgIt ArgEnd,
  43                                  const Type *RetTy, Constant *&FCache) {
  44   if (!FCache) {
  45     // If we haven't already looked up this function, check to see if the
  46     // program already contains a function with this name.
  47     Module *M = CI->getParent()->getParent()->getParent();
  48     // Get or insert the definition now.
  49     std::vector<const Type *> ParamTys;
  50     for (ArgIt I = ArgBegin; I != ArgEnd; ++I)
  51       ParamTys.push_back((*I)->getType());
  52     FCache = M->getOrInsertFunction(NewFn,
  53                                     FunctionType::get(RetTy, ParamTys, false));
  54   }
  55
  56   SmallVector<Value*, 8> Operands(ArgBegin, ArgEnd);
  57   CallInst *NewCI = new CallInst(FCache, &Operands[0], Operands.size(),
  58                                  CI->getName(), CI);
  59   if (!CI->use_empty())
  60     CI->replaceAllUsesWith(NewCI);
  61   return NewCI;
  62 }
  63
  64 void IntrinsicLowering::AddPrototypes(Module &M) {
  65   for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I)
  66     if (I->isDeclaration() && !I->use_empty())
  67       switch (I->getIntrinsicID()) {
  68       default: break;
  69       case Intrinsic::setjmp:
  70         EnsureFunctionExists(M, "setjmp", I->arg_begin(), I->arg_end(),
  71                              Type::Int32Ty);
  72         break;
  73       case Intrinsic::longjmp:
  74         EnsureFunctionExists(M, "longjmp", I->arg_begin(), I->arg_end(),
  75                              Type::VoidTy);
  76         break;
  77       case Intrinsic::siglongjmp:
  78         EnsureFunctionExists(M, "abort", I->arg_end(), I->arg_end(),
  79                              Type::VoidTy);
  80         break;
  81       case Intrinsic::memcpy_i32:
  82       case Intrinsic::memcpy_i64:
  83         M.getOrInsertFunction("memcpy", PointerType::get(Type::Int8Ty),
  84                               PointerType::get(Type::Int8Ty),
  85                               PointerType::get(Type::Int8Ty),
  86                               TD.getIntPtrType(), (Type *)0);
  87         break;
  88       case Intrinsic::memmove_i32:
  89       case Intrinsic::memmove_i64:
  90         M.getOrInsertFunction("memmove", PointerType::get(Type::Int8Ty),
  91                               PointerType::get(Type::Int8Ty),
  92                               PointerType::get(Type::Int8Ty),
  93                               TD.getIntPtrType(), (Type *)0);
  94         break;
  95       case Intrinsic::memset_i32:
  96       case Intrinsic::memset_i64:
  97         M.getOrInsertFunction("memset", PointerType::get(Type::Int8Ty),
  98                               PointerType::get(Type::Int8Ty), Type::Int32Ty,
  99                               TD.getIntPtrType(), (Type *)0);
 100         break;
 101       case Intrinsic::sqrt_f32:
 102       case Intrinsic::sqrt_f64:
 103         if(I->arg_begin()->getType() == Type::FloatTy)
 104           EnsureFunctionExists(M, "sqrtf", I->arg_begin(), I->arg_end(),
 105                                Type::FloatTy);
 106         else
 107           EnsureFunctionExists(M, "sqrt", I->arg_begin(), I->arg_end(),
 108                                Type::DoubleTy);
 109         break;
 110       }
 111 }
 112
 113 /// LowerBSWAP - Emit the code to lower bswap of V before the specified
 114 /// instruction IP.
 115 static Value *LowerBSWAP(Value *V, Instruction *IP) {
 116   assert(V->getType()->isInteger() && "Can't bswap a non-integer type!");
 117
 118   unsigned BitSize = V->getType()->getPrimitiveSizeInBits();
 119
 120   switch(BitSize) {
 121   default: assert(0 && "Unhandled type size of value to byteswap!");
 122   case 16: {
 123     Value *Tmp1 = BinaryOperator::createShl(V,
 124                                 ConstantInt::get(V->getType(),8),"bswap.2",IP);
 125     Value *Tmp2 = BinaryOperator::createLShr(V,
 126                                 ConstantInt::get(V->getType(),8),"bswap.1",IP);
 127     V = BinaryOperator::createOr(Tmp1, Tmp2, "bswap.i16", IP);
 128     break;
 129   }
 130   case 32: {
 131     Value *Tmp4 = BinaryOperator::createShl(V,
 132                               ConstantInt::get(V->getType(),24),"bswap.4", IP);
 133     Value *Tmp3 = BinaryOperator::createShl(V,
 134                               ConstantInt::get(V->getType(),8),"bswap.3",IP);
 135     Value *Tmp2 = BinaryOperator::createLShr(V,
 136                               ConstantInt::get(V->getType(),8),"bswap.2",IP);
 137     Value *Tmp1 = BinaryOperator::createLShr(V,
 138                               ConstantInt::get(V->getType(),24),"bswap.1", IP);
 139     Tmp3 = BinaryOperator::createAnd(Tmp3,
 140                                      ConstantInt::get(Type::Int32Ty, 0xFF0000),
 141                                      "bswap.and3", IP);
 142     Tmp2 = BinaryOperator::createAnd(Tmp2,
 143                                      ConstantInt::get(Type::Int32Ty, 0xFF00),
 144                                      "bswap.and2", IP);
 145     Tmp4 = BinaryOperator::createOr(Tmp4, Tmp3, "bswap.or1", IP);
 146     Tmp2 = BinaryOperator::createOr(Tmp2, Tmp1, "bswap.or2", IP);
 147     V = BinaryOperator::createOr(Tmp4, Tmp3, "bswap.i32", IP);
 148     break;
 149   }
 150   case 64: {
 151     Value *Tmp8 = BinaryOperator::createShl(V,
 152                               ConstantInt::get(V->getType(),56),"bswap.8", IP);
 153     Value *Tmp7 = BinaryOperator::createShl(V,
 154                               ConstantInt::get(V->getType(),40),"bswap.7", IP);
 155     Value *Tmp6 = BinaryOperator::createShl(V,
 156                               ConstantInt::get(V->getType(),24),"bswap.6", IP);
 157     Value *Tmp5 = BinaryOperator::createShl(V,
 158                               ConstantInt::get(V->getType(),8),"bswap.5", IP);
 159     Value* Tmp4 = BinaryOperator::createLShr(V,
 160                               ConstantInt::get(V->getType(),8),"bswap.4", IP);
 161     Value* Tmp3 = BinaryOperator::createLShr(V,
 162                               ConstantInt::get(V->getType(),24),"bswap.3", IP);
 163     Value* Tmp2 = BinaryOperator::createLShr(V,
 164                               ConstantInt::get(V->getType(),40),"bswap.2", IP);
 165     Value* Tmp1 = BinaryOperator::createLShr(V,
 166                               ConstantInt::get(V->getType(),56),"bswap.1", IP);
 167     Tmp7 = BinaryOperator::createAnd(Tmp7,
 168                              ConstantInt::get(Type::Int64Ty,
 169                                0xFF000000000000ULL),
 170                              "bswap.and7", IP);
 171     Tmp6 = BinaryOperator::createAnd(Tmp6,
 172                              ConstantInt::get(Type::Int64Ty, 0xFF0000000000ULL),
 173                              "bswap.and6", IP);
 174     Tmp5 = BinaryOperator::createAnd(Tmp5,
 175                              ConstantInt::get(Type::Int64Ty, 0xFF00000000ULL),
 176                              "bswap.and5", IP);
 177     Tmp4 = BinaryOperator::createAnd(Tmp4,
 178                              ConstantInt::get(Type::Int64Ty, 0xFF000000ULL),
 179                              "bswap.and4", IP);
 180     Tmp3 = BinaryOperator::createAnd(Tmp3,
 181                              ConstantInt::get(Type::Int64Ty, 0xFF0000ULL),
 182                              "bswap.and3", IP);
 183     Tmp2 = BinaryOperator::createAnd(Tmp2,
 184                              ConstantInt::get(Type::Int64Ty, 0xFF00ULL),
 185                              "bswap.and2", IP);
 186     Tmp8 = BinaryOperator::createOr(Tmp8, Tmp7, "bswap.or1", IP);
 187     Tmp6 = BinaryOperator::createOr(Tmp6, Tmp5, "bswap.or2", IP);
 188     Tmp4 = BinaryOperator::createOr(Tmp4, Tmp3, "bswap.or3", IP);
 189     Tmp2 = BinaryOperator::createOr(Tmp2, Tmp1, "bswap.or4", IP);
 190     Tmp8 = BinaryOperator::createOr(Tmp8, Tmp6, "bswap.or5", IP);
 191     Tmp4 = BinaryOperator::createOr(Tmp4, Tmp2, "bswap.or6", IP);
 192     V = BinaryOperator::createOr(Tmp8, Tmp4, "bswap.i64", IP);
 193     break;
 194   }
 195   }
 196   return V;
 197 }
 198
 199 /// LowerCTPOP - Emit the code to lower ctpop of V before the specified
 200 /// instruction IP.
 201 static Value *LowerCTPOP(Value *V, Instruction *IP) {
 202   assert(V->getType()->isInteger() && "Can't ctpop a non-integer type!");
 203
 204   static const uint64_t MaskValues[6] = {
 205     0x5555555555555555ULL, 0x3333333333333333ULL,
 206     0x0F0F0F0F0F0F0F0FULL, 0x00FF00FF00FF00FFULL,
 207     0x0000FFFF0000FFFFULL, 0x00000000FFFFFFFFULL
 208   };
 209
 210   unsigned BitSize = V->getType()->getPrimitiveSizeInBits();
 211
 212   for (unsigned i = 1, ct = 0; i != BitSize; i <<= 1, ++ct) {
 213     Value *MaskCst = ConstantInt::get(V->getType(), MaskValues[ct]);
 214     Value *LHS = BinaryOperator::createAnd(V, MaskCst, "cppop.and1", IP);
 215     Value *VShift = BinaryOperator::createLShr(V,
 216                       ConstantInt::get(V->getType(), i), "ctpop.sh", IP);
 217     Value *RHS = BinaryOperator::createAnd(VShift, MaskCst, "cppop.and2", IP);
 218     V = BinaryOperator::createAdd(LHS, RHS, "ctpop.step", IP);
 219   }
 220
 221   return CastInst::createIntegerCast(V, Type::Int32Ty, false, "ctpop", IP);
 222 }
 223
 224 /// LowerCTLZ - Emit the code to lower ctlz of V before the specified
 225 /// instruction IP.
 226 static Value *LowerCTLZ(Value *V, Instruction *IP) {
 227
 228   unsigned BitSize = V->getType()->getPrimitiveSizeInBits();
 229   for (unsigned i = 1; i != BitSize; i <<= 1) {
 230     Value *ShVal = ConstantInt::get(V->getType(), i);
 231     ShVal = BinaryOperator::createLShr(V, ShVal, "ctlz.sh", IP);
 232     V = BinaryOperator::createOr(V, ShVal, "ctlz.step", IP);
 233   }
 234
 235   V = BinaryOperator::createNot(V, "", IP);
 236   return LowerCTPOP(V, IP);
 237 }
 238
 239 /// Convert the llvm.part.select.iX.iY intrinsic. This intrinsic takes
 240 /// three integer arguments. The first argument is the Value from which the
 241 /// bits will be selected. It may be of any bit width. The second and third
 242 /// arguments specify a range of bits to select with the second argument
 243 /// specifying the low bit and the third argument specifying the high bit. Both
 244 /// must be type i32. The result is the corresponding selected bits from the
 245 /// Value in the same width as the Value (first argument). If the low bit index
 246 /// is higher than the high bit index then the inverse selection is done and
 247 /// the bits are returned in inverse order.
 248 /// @brief Lowering of llvm.part.select intrinsic.
 249 static Instruction *LowerPartSelect(CallInst *CI) {
 250   // Make sure we're dealing with a part select intrinsic here
 251   Function *F = CI->getCalledFunction();
 252   const FunctionType *FT = F->getFunctionType();
 253   if (!F->isDeclaration() || !FT->getReturnType()->isInteger() ||
 254       FT->getNumParams() != 3 || !FT->getParamType(0)->isInteger() ||
 255       !FT->getParamType(1)->isInteger() || !FT->getParamType(2)->isInteger())
 256     return CI;
 257
 258   // Get the intrinsic implementation function by converting all the . to _
 259   // in the intrinsic's function name and then reconstructing the function
 260   // declaration.
 261   std::string Name(F->getName());
 262   for (unsigned i = 4; i < Name.length(); ++i)
 263     if (Name[i] == '.')
 264       Name[i] = '_';
 265   Module* M = F->getParent();
 266   F = cast<Function>(M->getOrInsertFunction(Name, FT));
 267   F->setLinkage(GlobalValue::WeakLinkage);
 268
 269   // If we haven't defined the impl function yet, do so now
 270   if (F->isDeclaration()) {
 271
 272     // Get the arguments to the function
 273     Function::arg_iterator args = F->arg_begin();
 274     Value* Val = args++; Val->setName("Val");
 275     Value* Lo = args++; Lo->setName("Lo");
 276     Value* Hi  = args++; Hi->setName("High");
 277
 278     // We want to select a range of bits here such that [Hi, Lo] is shifted
 279     // down to the low bits. However, it is quite possible that Hi is smaller
 280     // than Lo in which case the bits have to be reversed.
 281
 282     // Create the blocks we will need for the two cases (forward, reverse)
 283     BasicBlock* CurBB   = new BasicBlock("entry", F);
 284     BasicBlock *RevSize = new BasicBlock("revsize", CurBB->getParent());
 285     BasicBlock *FwdSize = new BasicBlock("fwdsize", CurBB->getParent());
 286     BasicBlock *Compute = new BasicBlock("compute", CurBB->getParent());
 287     BasicBlock *Reverse = new BasicBlock("reverse", CurBB->getParent());
 288     BasicBlock *RsltBlk = new BasicBlock("result",  CurBB->getParent());
 289
 290     // Cast Hi and Lo to the size of Val so the widths are all the same
 291     if (Hi->getType() != Val->getType())
 292       Hi = CastInst::createIntegerCast(Hi, Val->getType(), false,
 293                                          "tmp", CurBB);
 294     if (Lo->getType() != Val->getType())
 295       Lo = CastInst::createIntegerCast(Lo, Val->getType(), false,
 296                                           "tmp", CurBB);
 297
 298     // Compute a few things that both cases will need, up front.
 299     Constant* Zero = ConstantInt::get(Val->getType(), 0);
 300     Constant* One = ConstantInt::get(Val->getType(), 1);
 301     Constant* AllOnes = ConstantInt::getAllOnesValue(Val->getType());
 302
 303     // Compare the Hi and Lo bit positions. This is used to determine
 304     // which case we have (forward or reverse)
 305     ICmpInst *Cmp = new ICmpInst(ICmpInst::ICMP_ULT, Hi, Lo, "less",CurBB);
 306     new BranchInst(RevSize, FwdSize, Cmp, CurBB);
 307
 308     // First, copmute the number of bits in the forward case.
 309     Instruction* FBitSize =
 310       BinaryOperator::createSub(Hi, Lo,"fbits", FwdSize);
 311     new BranchInst(Compute, FwdSize);
 312
 313     // Second, compute the number of bits in the reverse case.
 314     Instruction* RBitSize =
 315       BinaryOperator::createSub(Lo, Hi, "rbits", RevSize);
 316     new BranchInst(Compute, RevSize);
 317
 318     // Now, compute the bit range. Start by getting the bitsize and the shift
 319     // amount (either Hi or Lo) from PHI nodes. Then we compute a mask for
 320     // the number of bits we want in the range. We shift the bits down to the
 321     // least significant bits, apply the mask to zero out unwanted high bits,
 322     // and we have computed the "forward" result. It may still need to be
 323     // reversed.
 324
 325     // Get the BitSize from one of the two subtractions
 326     PHINode *BitSize = new PHINode(Val->getType(), "bits", Compute);
 327     BitSize->reserveOperandSpace(2);
 328     BitSize->addIncoming(FBitSize, FwdSize);
 329     BitSize->addIncoming(RBitSize, RevSize);
 330
 331     // Get the ShiftAmount as the smaller of Hi/Lo
 332     PHINode *ShiftAmt = new PHINode(Val->getType(), "shiftamt", Compute);
 333     ShiftAmt->reserveOperandSpace(2);
 334     ShiftAmt->addIncoming(Lo, FwdSize);
 335     ShiftAmt->addIncoming(Hi, RevSize);
 336
 337     // Increment the bit size
 338     Instruction *BitSizePlusOne =
 339       BinaryOperator::createAdd(BitSize, One, "bits", Compute);
 340
 341     // Create a Mask to zero out the high order bits.
 342     Instruction* Mask =
 343       BinaryOperator::createShl(AllOnes, BitSizePlusOne, "mask", Compute);
 344     Mask = BinaryOperator::createNot(Mask, "mask", Compute);
 345
 346     // Shift the bits down and apply the mask
 347     Instruction* FRes =
 348       BinaryOperator::createLShr(Val, ShiftAmt, "fres", Compute);
 349     FRes = BinaryOperator::createAnd(FRes, Mask, "fres", Compute);
 350     new BranchInst(Reverse, RsltBlk, Cmp, Compute);
 351
 352     // In the Reverse block we have the mask already in FRes but we must reverse
 353     // it by shifting FRes bits right and putting them in RRes by shifting them
 354     // in from left.
 355
 356     // First set up our loop counters
 357     PHINode *Count = new PHINode(Val->getType(), "count", Reverse);
 358     Count->reserveOperandSpace(2);
 359     Count->addIncoming(BitSizePlusOne, Compute);
 360
 361     // Next, get the value that we are shifting.
 362     PHINode *BitsToShift   = new PHINode(Val->getType(), "val", Reverse);
 363     BitsToShift->reserveOperandSpace(2);
 364     BitsToShift->addIncoming(FRes, Compute);
 365
 366     // Finally, get the result of the last computation
 367     PHINode *RRes  = new PHINode(Val->getType(), "rres", Reverse);
 368     RRes->reserveOperandSpace(2);
 369     RRes->addIncoming(Zero, Compute);
 370
 371     // Decrement the counter
 372     Instruction *Decr = BinaryOperator::createSub(Count, One, "decr", Reverse);
 373     Count->addIncoming(Decr, Reverse);
 374
 375     // Compute the Bit that we want to move
 376     Instruction *Bit =
 377       BinaryOperator::createAnd(BitsToShift, One, "bit", Reverse);
 378
 379     // Compute the new value for next iteration.
 380     Instruction *NewVal =
 381       BinaryOperator::createLShr(BitsToShift, One, "rshift", Reverse);
 382     BitsToShift->addIncoming(NewVal, Reverse);
 383
 384     // Shift the bit into the low bits of the result.
 385     Instruction *NewRes =
 386       BinaryOperator::createShl(RRes, One, "lshift", Reverse);
 387     NewRes = BinaryOperator::createOr(NewRes, Bit, "addbit", Reverse);
 388     RRes->addIncoming(NewRes, Reverse);
 389
 390     // Terminate loop if we've moved all the bits.
 391     ICmpInst *Cond =
 392       new ICmpInst(ICmpInst::ICMP_EQ, Decr, Zero, "cond", Reverse);
 393     new BranchInst(RsltBlk, Reverse, Cond, Reverse);
 394
 395     // Finally, in the result block, select one of the two results with a PHI
 396     // node and return the result;
 397     CurBB = RsltBlk;
 398     PHINode *BitSelect = new PHINode(Val->getType(), "part_select", CurBB);
 399     BitSelect->reserveOperandSpace(2);
 400     BitSelect->addIncoming(FRes, Compute);
 401     BitSelect->addIncoming(NewRes, Reverse);
 402     new ReturnInst(BitSelect, CurBB);
 403   }
 404
 405   // Return a call to the implementation function
 406   Value *Args[3];
 407   Args[0] = CI->getOperand(1);
 408   Args[1] = CI->getOperand(2);
 409   Args[2] = CI->getOperand(3);
 410   return new CallInst(F, Args, 3, CI->getName(), CI);
 411 }
 412
 413 /// Convert the llvm.part.set.iX.iY.iZ intrinsic. This intrinsic takes
 414 /// four integer arguments (iAny %Value, iAny %Replacement, i32 %Low, i32 %High)
 415 /// The first two arguments can be any bit width. The result is the same width
 416 /// as %Value. The operation replaces bits between %Low and %High with the value
 417 /// in %Replacement. If %Replacement is not the same width, it is truncated or
 418 /// zero extended as appropriate to fit the bits being replaced. If %Low is
 419 /// greater than %High then the inverse set of bits are replaced.
 420 /// @brief Lowering of llvm.bit.part.set intrinsic.
 421 static Instruction *LowerPartSet(CallInst *CI) {
 422   // Make sure we're dealing with a part select intrinsic here
 423   Function *F = CI->getCalledFunction();
 424   const FunctionType *FT = F->getFunctionType();
 425   if (!F->isDeclaration() || !FT->getReturnType()->isInteger() ||
 426       FT->getNumParams() != 4 || !FT->getParamType(0)->isInteger() ||
 427       !FT->getParamType(1)->isInteger() || !FT->getParamType(2)->isInteger() ||
 428       !FT->getParamType(3)->isInteger())
 429     return CI;
 430
 431   // Get the intrinsic implementation function by converting all the . to _
 432   // in the intrinsic's function name and then reconstructing the function
 433   // declaration.
 434   std::string Name(F->getName());
 435   for (unsigned i = 4; i < Name.length(); ++i)
 436     if (Name[i] == '.')
 437       Name[i] = '_';
 438   Module* M = F->getParent();
 439   F = cast<Function>(M->getOrInsertFunction(Name, FT));
 440   F->setLinkage(GlobalValue::WeakLinkage);
 441
 442   // If we haven't defined the impl function yet, do so now
 443   if (F->isDeclaration()) {
 444     // Note: the following code is based on code generated by llvm2cpp with
 445     // the following input. This is just *one* example of a generated function.
 446     // The functions vary by bit width of result and first two arguments.
 447     // The generated code has been changed to deal with any bit width not just
 448     // the 32/64 bitwidths used in the above sample.
 449     //
 450     // define i64 @part_set(i64 %Val, i32 %Rep, i32 %Lo, i32 %Hi) {
 451     // entry:
 452     //   %is_forward = icmp ult i32 %Lo, %Hi
 453     //   %Lo.pn = select i1 %is_forward, i32 %Hi, i32 %Lo
 454     //   %Hi.pn = select i1 %is_forward, i32 %Lo, i32 %Hi
 455     //   %iftmp.16.0 = sub i32 %Lo.pn, %Hi.pn
 456     //   icmp ult i32 %iftmp.16.0, 32
 457     //   br i1 %1, label %cond_true11, label %cond_next19
 458     // cond_true11:
 459     //   %tmp13 = sub i32 32, %iftmp.16.0
 460     //   %tmp14 = lshr i32 -1, %tmp13
 461     //   %tmp16 = and i32 %tmp14, %Rep
 462     //   br label %cond_next19
 463     // cond_next19:
 464     //   %iftmp.17.0 = phi i32 [ %tmp16, %cond_true11 ], [ %Rep, %entry ]
 465     //   %tmp2021 = zext i32 %iftmp.17.0 to i64
 466     //   icmp ugt i32 %Lo, %Hi
 467     //   br i1 %2, label %cond_next60, label %cond_true24
 468     // cond_true24:
 469     //   %tmp25.cast = zext i32 %Hi to i64
 470     //   %tmp26 = lshr i64 -1, %tmp25.cast
 471     //   %tmp27.cast = zext i32 %Lo to i64
 472     //   %tmp28 = shl i64 %tmp26, %tmp27.cast
 473     //   %tmp28not = xor i64 %tmp28, -1
 474     //   %tmp31 = shl i64 %tmp2021, %tmp27.cast
 475     //   %tmp34 = and i64 %tmp28not, %Val
 476     //   %Val_addr.064 = or i64 %tmp31, %tmp34
 477     //   ret i64 %Val_addr.064
 478     // cond_next60:
 479     //   %tmp39.cast = zext i32 %Lo to i64
 480     //   %tmp40 = shl i64 -1, %tmp39.cast
 481     //   %tmp41.cast = zext i32 %Hi to i64
 482     //   %tmp42 = shl i64 -1, %tmp41.cast
 483     //   %tmp45.demorgan = or i64 %tmp42, %tmp40
 484     //   %tmp45 = xor i64 %tmp45.demorgan, -1
 485     //   %tmp47 = and i64 %tmp45, %Val
 486     //   %tmp50 = shl i64 %tmp2021, %tmp39.cast
 487     //   %tmp52 = sub i32 32, %Hi
 488     //   %tmp52.cast = zext i32 %tmp52 to i64
 489     //   %tmp54 = lshr i64 %tmp2021, %tmp52.cast
 490     //   %tmp57 = or i64 %tmp50, %tmp47
 491     //   %Val_addr.0 = or i64 %tmp57, %tmp54
 492     //   ret i64 %Val_addr.0
 493     // }
 494
 495     // Get the arguments for the function.
 496     Function::arg_iterator args = F->arg_begin();
 497     Value* Val = args++; Val->setName("Val");
 498     Value* Rep = args++; Rep->setName("Rep");
 499     Value* Lo  = args++; Lo->setName("Lo");
 500     Value* Hi  = args++; Hi->setName("Hi");
 501
 502     // Get some types we need
 503     const IntegerType* ValTy = cast<IntegerType>(Val->getType());
 504     const IntegerType* RepTy = cast<IntegerType>(Rep->getType());
 505     uint32_t ValBits = ValTy->getBitWidth();
 506     uint32_t RepBits = RepTy->getBitWidth();
 507
 508     // Constant Definitions
 509     ConstantInt* RepBitWidth = ConstantInt::get(Type::Int32Ty, RepBits);
 510     ConstantInt* RepMask = ConstantInt::getAllOnesValue(RepTy);
 511     ConstantInt* ValMask = ConstantInt::getAllOnesValue(ValTy);
 512
 513     BasicBlock* entry = new BasicBlock("entry",F,0);
 514     BasicBlock* large = new BasicBlock("large",F,0);
 515     BasicBlock* small = new BasicBlock("small",F,0);
 516     BasicBlock* forward = new BasicBlock("forward",F,0);
 517     BasicBlock* reverse = new BasicBlock("reverse",F,0);
 518
 519     // Block entry (entry)
 520     // First, get the number of bits that we're placing as an i32
 521     ICmpInst* is_forward =
 522       new ICmpInst(ICmpInst::ICMP_ULT, Lo, Hi, "", entry);
 523     SelectInst* Lo_pn = new SelectInst(is_forward, Hi, Lo, "", entry);
 524     SelectInst* Hi_pn = new SelectInst(is_forward, Lo, Hi, "", entry);
 525     BinaryOperator* NumBits = BinaryOperator::createSub(Lo_pn, Hi_pn, "",entry);
 526     // Now, convert Lo and Hi to ValTy bit width
 527     if (ValBits > 32) {
 528       Hi = new ZExtInst(Hi, ValTy, "", entry);
 529       Lo = new ZExtInst(Lo, ValTy, "", entry);
 530     } else if (ValBits < 32) {
 531       Hi = new TruncInst(Hi, ValTy, "", entry);
 532       Lo = new TruncInst(Lo, ValTy, "", entry);
 533     }
 534     // Determine if the replacement bits are larger than the number of bits we
 535     // are replacing and deal with it.
 536     ICmpInst* is_large =
 537       new ICmpInst(ICmpInst::ICMP_ULT, NumBits, RepBitWidth, "", entry);
 538     new BranchInst(large, small, is_large, entry);
 539
 540     // Block "large"
 541     Instruction* MaskBits =
 542       BinaryOperator::createSub(RepBitWidth, NumBits, "", large);
 543     MaskBits = CastInst::createIntegerCast(MaskBits, RepMask->getType(),
 544                                            false, "", large);
 545     BinaryOperator* Mask1 =
 546       BinaryOperator::createLShr(RepMask, MaskBits, "", large);
 547     BinaryOperator* Rep2 = BinaryOperator::createAnd(Mask1, Rep, "", large);
 548     new BranchInst(small, large);
 549
 550     // Block "small"
 551     PHINode* Rep3 = new PHINode(RepTy, "", small);
 552     Rep3->reserveOperandSpace(2);
 553     Rep3->addIncoming(Rep2, large);
 554     Rep3->addIncoming(Rep, entry);
 555     Value* Rep4 = Rep3;
 556     if (ValBits > RepBits)
 557       Rep4 = new ZExtInst(Rep3, ValTy, "", small);
 558     else if (ValBits < RepBits)
 559       Rep4 = new TruncInst(Rep3, ValTy, "", small);
 560     ICmpInst* is_reverse =
 561       new ICmpInst(ICmpInst::ICMP_UGT, Lo, Hi, "", small);
 562     new BranchInst(reverse, forward, is_reverse, small);
 563
 564     // Block "forward"
 565     Value* t1    = BinaryOperator::createLShr(ValMask, Hi, "", forward);
 566     Value* t2    = BinaryOperator::createShl(t1, Lo, "", forward);
 567     Value* nott2 = BinaryOperator::createXor(t2, ValMask, "", forward);
 568     Value* t3    = BinaryOperator::createShl(Rep4, Lo, "", forward);
 569     Value* t4    = BinaryOperator::createAnd(nott2, Val, "", forward);
 570     Value* FRslt = BinaryOperator::createOr(t3, t4, "", forward);
 571     new ReturnInst(FRslt, forward);
 572
 573     // Block "reverse"
 574     Value* t5    = BinaryOperator::createShl(ValMask, Lo, "", reverse);
 575     Value* t6    = BinaryOperator::createShl(ValMask, Hi, "", reverse);
 576     Value* t7    = BinaryOperator::createOr(t6, t5, "", reverse);
 577     Value* t8    = BinaryOperator::createXor(t7, ValMask, "", reverse);
 578     Value* t9    = BinaryOperator::createAnd(t8, Val, "", reverse);
 579     Value* t10   = BinaryOperator::createShl(Rep4, Lo, "", reverse);
 580     if (32 < ValBits)
 581       RepBitWidth =
 582         cast<ConstantInt>(ConstantExpr::getZExt(RepBitWidth, ValTy));
 583     else if (32 > ValBits)
 584       RepBitWidth =
 585         cast<ConstantInt>(ConstantExpr::getTrunc(RepBitWidth, ValTy));
 586     Value* t11   = BinaryOperator::createSub(RepBitWidth, Hi, "", reverse);
 587     Value* t13   = BinaryOperator::createLShr(Rep4, t11, "",reverse);
 588     Value* t14   = BinaryOperator::createOr(t10, t9, "", reverse);
 589     Value* RRslt = BinaryOperator::createOr(t14, t13, "", reverse);
 590     new ReturnInst(RRslt, reverse);
 591   }
 592
 593   // Return a call to the implementation function
 594   Value *Args[3];
 595   Args[0] = CI->getOperand(1);
 596   Args[1] = CI->getOperand(2);
 597   Args[2] = CI->getOperand(3);
 598   Args[3] = CI->getOperand(4);
 599   return new CallInst(F, Args, 4, CI->getName(), CI);
 600 }
 601
 602
 603 void IntrinsicLowering::LowerIntrinsicCall(CallInst *CI) {
 604   Function *Callee = CI->getCalledFunction();
 605   assert(Callee && "Cannot lower an indirect call!");
 606
 607   switch (Callee->getIntrinsicID()) {
 608   case Intrinsic::not_intrinsic:
 609     cerr << "Cannot lower a call to a non-intrinsic function '"
 610          << Callee->getName() << "'!\n";
 611     abort();
 612   default:
 613     cerr << "Error: Code generator does not support intrinsic function '"
 614          << Callee->getName() << "'!\n";
 615     abort();
 616
 617     // The setjmp/longjmp intrinsics should only exist in the code if it was
 618     // never optimized (ie, right out of the CFE), or if it has been hacked on
 619     // by the lowerinvoke pass.  In both cases, the right thing to do is to
 620     // convert the call to an explicit setjmp or longjmp call.
 621   case Intrinsic::setjmp: {
 622     static Constant *SetjmpFCache = 0;
 623     Value *V = ReplaceCallWith("setjmp", CI, CI->op_begin()+1, CI->op_end(),
 624                                Type::Int32Ty, SetjmpFCache);
 625     if (CI->getType() != Type::VoidTy)
 626       CI->replaceAllUsesWith(V);
 627     break;
 628   }
 629   case Intrinsic::sigsetjmp:
 630      if (CI->getType() != Type::VoidTy)
 631        CI->replaceAllUsesWith(Constant::getNullValue(CI->getType()));
 632      break;
 633
 634   case Intrinsic::longjmp: {
 635     static Constant *LongjmpFCache = 0;
 636     ReplaceCallWith("longjmp", CI, CI->op_begin()+1, CI->op_end(),
 637                     Type::VoidTy, LongjmpFCache);
 638     break;
 639   }
 640
 641   case Intrinsic::siglongjmp: {
 642     // Insert the call to abort
 643     static Constant *AbortFCache = 0;
 644     ReplaceCallWith("abort", CI, CI->op_end(), CI->op_end(),
 645                     Type::VoidTy, AbortFCache);
 646     break;
 647   }
 648   case Intrinsic::ctpop:
 649     CI->replaceAllUsesWith(LowerCTPOP(CI->getOperand(1), CI));
 650     break;
 651
 652   case Intrinsic::bswap:
 653     CI->replaceAllUsesWith(LowerBSWAP(CI->getOperand(1), CI));
 654     break;
 655
 656   case Intrinsic::ctlz:
 657     CI->replaceAllUsesWith(LowerCTLZ(CI->getOperand(1), CI));
 658     break;
 659
 660   case Intrinsic::cttz: {
 661     // cttz(x) -> ctpop(~X & (X-1))
 662     Value *Src = CI->getOperand(1);
 663     Value *NotSrc = BinaryOperator::createNot(Src, Src->getName()+".not", CI);
 664     Value *SrcM1  = ConstantInt::get(Src->getType(), 1);
 665     SrcM1 = BinaryOperator::createSub(Src, SrcM1, "", CI);
 666     Src = LowerCTPOP(BinaryOperator::createAnd(NotSrc, SrcM1, "", CI), CI);
 667     CI->replaceAllUsesWith(Src);
 668     break;
 669   }
 670
 671   case Intrinsic::part_select:
 672     CI->replaceAllUsesWith(LowerPartSelect(CI));
 673     break;
 674
 675   case Intrinsic::part_set:
 676     CI->replaceAllUsesWith(LowerPartSet(CI));
 677     break;
 678
 679   case Intrinsic::stacksave:
 680   case Intrinsic::stackrestore: {
 681     static bool Warned = false;
 682     if (!Warned)
 683       cerr << "WARNING: this target does not support the llvm.stack"
 684            << (Callee->getIntrinsicID() == Intrinsic::stacksave ?
 685                "save" : "restore") << " intrinsic.\n";
 686     Warned = true;
 687     if (Callee->getIntrinsicID() == Intrinsic::stacksave)
 688       CI->replaceAllUsesWith(Constant::getNullValue(CI->getType()));
 689     break;
 690   }
 691
 692   case Intrinsic::returnaddress:
 693   case Intrinsic::frameaddress:
 694     cerr << "WARNING: this target does not support the llvm."
 695          << (Callee->getIntrinsicID() == Intrinsic::returnaddress ?
 696              "return" : "frame") << "address intrinsic.\n";
 697     CI->replaceAllUsesWith(ConstantPointerNull::get(
 698                                             cast<PointerType>(CI->getType())));
 699     break;
 700
 701   case Intrinsic::prefetch:
 702     break;    // Simply strip out prefetches on unsupported architectures
 703
 704   case Intrinsic::pcmarker:
 705     break;    // Simply strip out pcmarker on unsupported architectures
 706   case Intrinsic::readcyclecounter: {
 707     cerr << "WARNING: this target does not support the llvm.readcyclecoun"
 708          << "ter intrinsic.  It is being lowered to a constant 0\n";
 709     CI->replaceAllUsesWith(ConstantInt::get(Type::Int64Ty, 0));
 710     break;
 711   }
 712
 713   case Intrinsic::dbg_stoppoint:
 714   case Intrinsic::dbg_region_start:
 715   case Intrinsic::dbg_region_end:
 716   case Intrinsic::dbg_func_start:
 717   case Intrinsic::dbg_declare:
 718   case Intrinsic::eh_exception:
 719   case Intrinsic::eh_selector:
 720   case Intrinsic::eh_filter:
 721     break;    // Simply strip out debugging and eh intrinsics
 722
 723   case Intrinsic::memcpy_i32:
 724   case Intrinsic::memcpy_i64: {
 725     static Constant *MemcpyFCache = 0;
 726     Value *Size = CI->getOperand(3);
 727     const Type *IntPtr = TD.getIntPtrType();
 728     if (Size->getType()->getPrimitiveSizeInBits() <
 729         IntPtr->getPrimitiveSizeInBits())
 730       Size = new ZExtInst(Size, IntPtr, "", CI);
 731     else if (Size->getType()->getPrimitiveSizeInBits() >
 732              IntPtr->getPrimitiveSizeInBits())
 733       Size = new TruncInst(Size, IntPtr, "", CI);
 734     Value *Ops[3];
 735     Ops[0] = CI->getOperand(1);
 736     Ops[1] = CI->getOperand(2);
 737     Ops[2] = Size;
 738     ReplaceCallWith("memcpy", CI, Ops, Ops+3, CI->getOperand(1)->getType(),
 739                     MemcpyFCache);
 740     break;
 741   }
 742   case Intrinsic::memmove_i32:
 743   case Intrinsic::memmove_i64: {
 744     static Constant *MemmoveFCache = 0;
 745     Value *Size = CI->getOperand(3);
 746     const Type *IntPtr = TD.getIntPtrType();
 747     if (Size->getType()->getPrimitiveSizeInBits() <
 748         IntPtr->getPrimitiveSizeInBits())
 749       Size = new ZExtInst(Size, IntPtr, "", CI);
 750     else if (Size->getType()->getPrimitiveSizeInBits() >
 751              IntPtr->getPrimitiveSizeInBits())
 752       Size = new TruncInst(Size, IntPtr, "", CI);
 753     Value *Ops[3];
 754     Ops[0] = CI->getOperand(1);
 755     Ops[1] = CI->getOperand(2);
 756     Ops[2] = Size;
 757     ReplaceCallWith("memmove", CI, Ops, Ops+3, CI->getOperand(1)->getType(),
 758                     MemmoveFCache);
 759     break;
 760   }
 761   case Intrinsic::memset_i32:
 762   case Intrinsic::memset_i64: {
 763     static Constant *MemsetFCache = 0;
 764     Value *Size = CI->getOperand(3);
 765     const Type *IntPtr = TD.getIntPtrType();
 766     if (Size->getType()->getPrimitiveSizeInBits() <
 767         IntPtr->getPrimitiveSizeInBits())
 768       Size = new ZExtInst(Size, IntPtr, "", CI);
 769     else if (Size->getType()->getPrimitiveSizeInBits() >
 770              IntPtr->getPrimitiveSizeInBits())
 771       Size = new TruncInst(Size, IntPtr, "", CI);
 772     Value *Ops[3];
 773     Ops[0] = CI->getOperand(1);
 774     // Extend the amount to i32.
 775     Ops[1] = new ZExtInst(CI->getOperand(2), Type::Int32Ty, "", CI);
 776     Ops[2] = Size;
 777     ReplaceCallWith("memset", CI, Ops, Ops+3, CI->getOperand(1)->getType(),
 778                     MemsetFCache);
 779     break;
 780   }
 781   case Intrinsic::sqrt_f32: {
 782     static Constant *sqrtfFCache = 0;
 783     ReplaceCallWith("sqrtf", CI, CI->op_begin()+1, CI->op_end(),
 784                     Type::FloatTy, sqrtfFCache);
 785     break;
 786   }
 787   case Intrinsic::sqrt_f64: {
 788     static Constant *sqrtFCache = 0;
 789     ReplaceCallWith("sqrt", CI, CI->op_begin()+1, CI->op_end(),
 790                     Type::DoubleTy, sqrtFCache);
 791     break;
 792   }
 793   }
 794
 795   assert(CI->use_empty() &&
 796          "Lowering should have eliminated any uses of the intrinsic call!");
 797   CI->eraseFromParent();
 798 }