lib/Transforms/Scalar/LowerPacked.cpp

   1 //===- LowerPacked.cpp -  Implementation of LowerPacked Transform ---------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by Brad Jones and is distributed under
   6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file implements lowering Packed datatypes into more primitive
  11 // Packed datatypes, and finally to scalar operations.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #include "llvm/Transforms/Scalar.h"
  16 #include "llvm/Argument.h"
  17 #include "llvm/Constants.h"
  18 #include "llvm/DerivedTypes.h"
  19 #include "llvm/Function.h"
  20 #include "llvm/Instructions.h"
  21 #include "llvm/Pass.h"
  22 #include "llvm/Support/InstVisitor.h"
  23 #include "llvm/ADT/StringExtras.h"
  24 #include <algorithm>
  25 #include <map>
  26 #include <iostream>
  27 #include <functional>
  28
  29 using namespace llvm;
  30
  31 namespace {
  32
  33 /// This pass converts packed operators to an
  34 /// equivalent operations on smaller packed data, to possibly
  35 /// scalar operations.  Currently it supports lowering
  36 /// to scalar operations.
  37 ///
  38 /// @brief Transforms packed instructions to simpler instructions.
  39 ///
  40 class LowerPacked : public FunctionPass, public InstVisitor<LowerPacked> {
  41 public:
  42    /// @brief Lowers packed operations to scalar operations.
  43    /// @param F The fuction to process
  44    virtual bool runOnFunction(Function &F);
  45
  46    /// @brief Lowers packed load instructions.
  47    /// @param LI the load instruction to convert
  48    void visitLoadInst(LoadInst& LI);
  49
  50    /// @brief Lowers packed store instructions.
  51    /// @param SI the store instruction to convert
  52    void visitStoreInst(StoreInst& SI);
  53
  54    /// @brief Lowers packed binary operations.
  55    /// @param BO the binary operator to convert
  56    void visitBinaryOperator(BinaryOperator& BO);
  57
  58    /// @brief Lowers packed select instructions.
  59    /// @param SELI the select operator to convert
  60    void visitSelectInst(SelectInst& SELI);
  61
  62    /// @brief Lowers packed extractelement instructions.
  63    /// @param EI the extractelement operator to convert
  64    void visitExtractElementInst(ExtractElementInst& EE);
  65
  66    /// @brief Lowers packed insertelement instructions.
  67    /// @param EI the insertelement operator to convert
  68    void visitInsertElementInst(InsertElementInst& IE);
  69
  70    /// This function asserts if the instruction is a PackedType but
  71    /// is handled by another function.
  72    ///
  73    /// @brief Asserts if PackedType instruction is not handled elsewhere.
  74    /// @param I the unhandled instruction
  75    void visitInstruction(Instruction &I)
  76    {
  77       if(isa<PackedType>(I.getType())) {
  78          std::cerr << "Unhandled Instruction with Packed ReturnType: " <<
  79                       I << '\n';
  80       }
  81    }
  82 private:
  83    /// @brief Retrieves lowered values for a packed value.
  84    /// @param val the packed value
  85    /// @return the lowered values
  86    std::vector<Value*>& getValues(Value* val);
  87
  88    /// @brief Sets lowered values for a packed value.
  89    /// @param val the packed value
  90    /// @param values the corresponding lowered values
  91    void setValues(Value* val,const std::vector<Value*>& values);
  92
  93    // Data Members
  94    /// @brief whether we changed the function or not
  95    bool Changed;
  96
  97    /// @brief a map from old packed values to new smaller packed values
  98    std::map<Value*,std::vector<Value*> > packedToScalarMap;
  99
 100    /// Instructions in the source program to get rid of
 101    /// after we do a pass (the old packed instructions)
 102    std::vector<Instruction*> instrsToRemove;
 103 };
 104
 105 RegisterPass<LowerPacked>
 106 X("lower-packed",
 107   "lowers packed operations to operations on smaller packed datatypes");
 108
 109 } // end namespace
 110
 111 FunctionPass *llvm::createLowerPackedPass() { return new LowerPacked(); }
 112
 113
 114 // This function sets lowered values for a corresponding
 115 // packed value.  Note, in the case of a forward reference
 116 // getValues(Value*) will have already been called for
 117 // the packed parameter.  This function will then replace
 118 // all references in the in the function of the "dummy"
 119 // value the previous getValues(Value*) call
 120 // returned with actual references.
 121 void LowerPacked::setValues(Value* value,const std::vector<Value*>& values)
 122 {
 123    std::map<Value*,std::vector<Value*> >::iterator it =
 124          packedToScalarMap.lower_bound(value);
 125    if (it == packedToScalarMap.end() || it->first != value) {
 126        // there was not a forward reference to this element
 127        packedToScalarMap.insert(it,std::make_pair(value,values));
 128    }
 129    else {
 130       // replace forward declarations with actual definitions
 131       assert(it->second.size() == values.size() &&
 132              "Error forward refences and actual definition differ in size");
 133       for (unsigned i = 0, e = values.size(); i != e; ++i) {
 134            // replace and get rid of old forward references
 135            it->second[i]->replaceAllUsesWith(values[i]);
 136            delete it->second[i];
 137            it->second[i] = values[i];
 138       }
 139    }
 140 }
 141
 142 // This function will examine the packed value parameter
 143 // and if it is a packed constant or a forward reference
 144 // properly create the lowered values needed.  Otherwise
 145 // it will simply retreive values from a
 146 // setValues(Value*,const std::vector<Value*>&)
 147 // call.  Failing both of these cases, it will abort
 148 // the program.
 149 std::vector<Value*>& LowerPacked::getValues(Value* value)
 150 {
 151    assert(isa<PackedType>(value->getType()) &&
 152           "Value must be PackedType");
 153
 154    // reject further processing if this one has
 155    // already been handled
 156    std::map<Value*,std::vector<Value*> >::iterator it =
 157       packedToScalarMap.lower_bound(value);
 158    if (it != packedToScalarMap.end() && it->first == value) {
 159        return it->second;
 160    }
 161
 162    if (ConstantPacked* CP = dyn_cast<ConstantPacked>(value)) {
 163        // non-zero constant case
 164        std::vector<Value*> results;
 165        results.reserve(CP->getNumOperands());
 166        for (unsigned i = 0, e = CP->getNumOperands(); i != e; ++i) {
 167           results.push_back(CP->getOperand(i));
 168        }
 169        return packedToScalarMap.insert(it,
 170                                        std::make_pair(value,results))->second;
 171    }
 172    else if (ConstantAggregateZero* CAZ =
 173             dyn_cast<ConstantAggregateZero>(value)) {
 174        // zero constant
 175        const PackedType* PKT = cast<PackedType>(CAZ->getType());
 176        std::vector<Value*> results;
 177        results.reserve(PKT->getNumElements());
 178
 179        Constant* C = Constant::getNullValue(PKT->getElementType());
 180        for (unsigned i = 0, e = PKT->getNumElements(); i != e; ++i) {
 181             results.push_back(C);
 182        }
 183        return packedToScalarMap.insert(it,
 184                                        std::make_pair(value,results))->second;
 185    }
 186    else if (isa<Instruction>(value)) {
 187        // foward reference
 188        const PackedType* PKT = cast<PackedType>(value->getType());
 189        std::vector<Value*> results;
 190        results.reserve(PKT->getNumElements());
 191
 192       for (unsigned i = 0, e = PKT->getNumElements(); i != e; ++i) {
 193            results.push_back(new Argument(PKT->getElementType()));
 194       }
 195       return packedToScalarMap.insert(it,
 196                                       std::make_pair(value,results))->second;
 197    }
 198    else {
 199        // we don't know what it is, and we are trying to retrieve
 200        // a value for it
 201        assert(false && "Unhandled PackedType value");
 202        abort();
 203    }
 204 }
 205
 206 void LowerPacked::visitLoadInst(LoadInst& LI)
 207 {
 208    // Make sure what we are dealing with is a packed type
 209    if (const PackedType* PKT = dyn_cast<PackedType>(LI.getType())) {
 210        // Initialization, Idx is needed for getelementptr needed later
 211        std::vector<Value*> Idx(2);
 212        Idx[0] = ConstantInt::get(Type::UIntTy,0);
 213
 214        ArrayType* AT = ArrayType::get(PKT->getContainedType(0),
 215                                       PKT->getNumElements());
 216        PointerType* APT = PointerType::get(AT);
 217
 218        // Cast the packed type to an array
 219        Value* array = new CastInst(LI.getPointerOperand(),
 220                                    APT,
 221                                    LI.getName() + ".a",
 222                                    &LI);
 223
 224        // Convert this load into num elements number of loads
 225        std::vector<Value*> values;
 226        values.reserve(PKT->getNumElements());
 227
 228        for (unsigned i = 0, e = PKT->getNumElements(); i != e; ++i) {
 229             // Calculate the second index we will need
 230             Idx[1] = ConstantInt::get(Type::UIntTy,i);
 231
 232             // Get the pointer
 233             Value* val = new GetElementPtrInst(array,
 234                                                Idx,
 235                                                LI.getName() +
 236                                                ".ge." + utostr(i),
 237                                                &LI);
 238
 239             // generate the new load and save the result in packedToScalar map
 240             values.push_back(new LoadInst(val,
 241                              LI.getName()+"."+utostr(i),
 242                              LI.isVolatile(),
 243                              &LI));
 244        }
 245
 246        setValues(&LI,values);
 247        Changed = true;
 248        instrsToRemove.push_back(&LI);
 249    }
 250 }
 251
 252 void LowerPacked::visitBinaryOperator(BinaryOperator& BO)
 253 {
 254    // Make sure both operands are PackedTypes
 255    if (isa<PackedType>(BO.getOperand(0)->getType())) {
 256        std::vector<Value*>& op0Vals = getValues(BO.getOperand(0));
 257        std::vector<Value*>& op1Vals = getValues(BO.getOperand(1));
 258        std::vector<Value*> result;
 259        assert((op0Vals.size() == op1Vals.size()) &&
 260               "The two packed operand to scalar maps must be equal in size.");
 261
 262        result.reserve(op0Vals.size());
 263
 264        // generate the new binary op and save the result
 265        for (unsigned i = 0; i != op0Vals.size(); ++i) {
 266             result.push_back(BinaryOperator::create(BO.getOpcode(),
 267                                                     op0Vals[i],
 268                                                     op1Vals[i],
 269                                                     BO.getName() +
 270                                                     "." + utostr(i),
 271                                                     &BO));
 272        }
 273
 274        setValues(&BO,result);
 275        Changed = true;
 276        instrsToRemove.push_back(&BO);
 277    }
 278 }
 279
 280 void LowerPacked::visitStoreInst(StoreInst& SI)
 281 {
 282    if (const PackedType* PKT =
 283        dyn_cast<PackedType>(SI.getOperand(0)->getType())) {
 284        // We will need this for getelementptr
 285        std::vector<Value*> Idx(2);
 286        Idx[0] = ConstantInt::get(Type::UIntTy,0);
 287
 288        ArrayType* AT = ArrayType::get(PKT->getContainedType(0),
 289                                       PKT->getNumElements());
 290        PointerType* APT = PointerType::get(AT);
 291
 292        // cast the packed to an array type
 293        Value* array = new CastInst(SI.getPointerOperand(),
 294                                    APT,
 295                                    "store.ge.a.",
 296                                    &SI);
 297        std::vector<Value*>& values = getValues(SI.getOperand(0));
 298
 299        assert((values.size() == PKT->getNumElements()) &&
 300               "Scalar must have the same number of elements as Packed Type");
 301
 302        for (unsigned i = 0, e = PKT->getNumElements(); i != e; ++i) {
 303             // Generate the indices for getelementptr
 304             Idx[1] = ConstantInt::get(Type::UIntTy,i);
 305             Value* val = new GetElementPtrInst(array,
 306                                                Idx,
 307                                                "store.ge." +
 308                                                utostr(i) + ".",
 309                                                &SI);
 310             new StoreInst(values[i], val, SI.isVolatile(),&SI);
 311        }
 312
 313        Changed = true;
 314        instrsToRemove.push_back(&SI);
 315    }
 316 }
 317
 318 void LowerPacked::visitSelectInst(SelectInst& SELI)
 319 {
 320    // Make sure both operands are PackedTypes
 321    if (isa<PackedType>(SELI.getType())) {
 322        std::vector<Value*>& op0Vals = getValues(SELI.getTrueValue());
 323        std::vector<Value*>& op1Vals = getValues(SELI.getFalseValue());
 324        std::vector<Value*> result;
 325
 326       assert((op0Vals.size() == op1Vals.size()) &&
 327              "The two packed operand to scalar maps must be equal in size.");
 328
 329       for (unsigned i = 0; i != op0Vals.size(); ++i) {
 330            result.push_back(new SelectInst(SELI.getCondition(),
 331                                            op0Vals[i],
 332                                            op1Vals[i],
 333                                            SELI.getName()+ "." + utostr(i),
 334                                            &SELI));
 335       }
 336
 337       setValues(&SELI,result);
 338       Changed = true;
 339       instrsToRemove.push_back(&SELI);
 340    }
 341 }
 342
 343 void LowerPacked::visitExtractElementInst(ExtractElementInst& EI)
 344 {
 345   std::vector<Value*>& op0Vals = getValues(EI.getOperand(0));
 346   const PackedType *PTy = cast<PackedType>(EI.getOperand(0)->getType());
 347   Value *op1 = EI.getOperand(1);
 348
 349   if (ConstantInt *C = dyn_cast<ConstantInt>(op1)) {
 350     EI.replaceAllUsesWith(op0Vals[C->getZExtValue()]);
 351   } else {
 352     AllocaInst *alloca =
 353       new AllocaInst(PTy->getElementType(),
 354                      ConstantInt::get(Type::UIntTy, PTy->getNumElements()),
 355                      EI.getName() + ".alloca",
 356                      EI.getParent()->getParent()->getEntryBlock().begin());
 357     for (unsigned i = 0; i < PTy->getNumElements(); ++i) {
 358       GetElementPtrInst *GEP =
 359         new GetElementPtrInst(alloca, ConstantInt::get(Type::UIntTy, i),
 360                               "store.ge", &EI);
 361       new StoreInst(op0Vals[i], GEP, &EI);
 362     }
 363     GetElementPtrInst *GEP =
 364       new GetElementPtrInst(alloca, op1, EI.getName() + ".ge", &EI);
 365     LoadInst *load = new LoadInst(GEP, EI.getName() + ".load", &EI);
 366     EI.replaceAllUsesWith(load);
 367   }
 368
 369   Changed = true;
 370   instrsToRemove.push_back(&EI);
 371 }
 372
 373 void LowerPacked::visitInsertElementInst(InsertElementInst& IE)
 374 {
 375   std::vector<Value*>& Vals = getValues(IE.getOperand(0));
 376   Value *Elt = IE.getOperand(1);
 377   Value *Idx = IE.getOperand(2);
 378   std::vector<Value*> result;
 379   result.reserve(Vals.size());
 380
 381   if (ConstantInt *C = dyn_cast<ConstantInt>(Idx)) {
 382     unsigned idxVal = C->getZExtValue();
 383     for (unsigned i = 0; i != Vals.size(); ++i) {
 384       result.push_back(i == idxVal ? Elt : Vals[i]);
 385     }
 386   } else {
 387     for (unsigned i = 0; i != Vals.size(); ++i) {
 388       SetCondInst *setcc =
 389         new SetCondInst(Instruction::SetEQ, Idx,
 390                         ConstantInt::get(Type::UIntTy, i),
 391                         "setcc", &IE);
 392       SelectInst *select =
 393         new SelectInst(setcc, Elt, Vals[i], "select", &IE);
 394       result.push_back(select);
 395     }
 396   }
 397
 398   setValues(&IE, result);
 399   Changed = true;
 400   instrsToRemove.push_back(&IE);
 401 }
 402
 403 bool LowerPacked::runOnFunction(Function& F)
 404 {
 405    // initialize
 406    Changed = false;
 407
 408    // Does three passes:
 409    // Pass 1) Converts Packed Operations to
 410    //         new Packed Operations on smaller
 411    //         datatypes
 412    visit(F);
 413
 414    // Pass 2) Drop all references
 415    std::for_each(instrsToRemove.begin(),
 416                  instrsToRemove.end(),
 417                  std::mem_fun(&Instruction::dropAllReferences));
 418
 419    // Pass 3) Delete the Instructions to remove aka packed instructions
 420    for (std::vector<Instruction*>::iterator i = instrsToRemove.begin(),
 421                                             e = instrsToRemove.end();
 422         i != e; ++i) {
 423         (*i)->getParent()->getInstList().erase(*i);
 424    }
 425
 426    // clean-up
 427    packedToScalarMap.clear();
 428    instrsToRemove.clear();
 429
 430    return Changed;
 431 }
 432