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