LLVM API Documentation

LowerPacked.cpp

Go to the documentation of this file.
00001 //===- LowerPacked.cpp -  Implementation of LowerPacked Transform ---------===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file was developed by Brad Jones and is distributed under
00006 // the University of Illinois Open Source License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This file implements lowering Packed datatypes into more primitive
00011 // Packed datatypes, and finally to scalar operations.
00012 //
00013 //===----------------------------------------------------------------------===//
00014 
00015 #include "llvm/Transforms/Scalar.h"
00016 #include "llvm/Argument.h"
00017 #include "llvm/Constants.h"
00018 #include "llvm/DerivedTypes.h"
00019 #include "llvm/Function.h"
00020 #include "llvm/Instructions.h"
00021 #include "llvm/Pass.h"
00022 #include "llvm/Support/InstVisitor.h"
00023 #include "llvm/ADT/StringExtras.h"
00024 #include <algorithm>
00025 #include <map>
00026 #include <iostream>
00027 #include <functional>
00028 
00029 using namespace llvm;
00030 
00031 namespace {
00032 
00033 /// This pass converts packed operators to an
00034 /// equivalent operations on smaller packed data, to possibly
00035 /// scalar operations.  Currently it supports lowering
00036 /// to scalar operations.
00037 ///
00038 /// @brief Transforms packed instructions to simpler instructions.
00039 ///
00040 class LowerPacked : public FunctionPass, public InstVisitor<LowerPacked> {
00041 public:
00042    /// @brief Lowers packed operations to scalar operations.
00043    /// @param F The fuction to process
00044    virtual bool runOnFunction(Function &F);
00045 
00046    /// @brief Lowers packed load instructions.
00047    /// @param LI the load instruction to convert
00048    void visitLoadInst(LoadInst& LI);
00049 
00050    /// @brief Lowers packed store instructions.
00051    /// @param SI the store instruction to convert
00052    void visitStoreInst(StoreInst& SI);
00053 
00054    /// @brief Lowers packed binary operations.
00055    /// @param BO the binary operator to convert
00056    void visitBinaryOperator(BinaryOperator& BO);
00057 
00058    /// @brief Lowers packed select instructions.
00059    /// @param SELI the select operator to convert
00060    void visitSelectInst(SelectInst& SELI);
00061 
00062    /// @brief Lowers packed extractelement instructions.
00063    /// @param EI the extractelement operator to convert
00064    void visitExtractElementInst(ExtractElementInst& EE);
00065 
00066    /// @brief Lowers packed insertelement instructions.
00067    /// @param EI the insertelement operator to convert
00068    void visitInsertElementInst(InsertElementInst& IE);
00069 
00070    /// This function asserts if the instruction is a PackedType but
00071    /// is handled by another function.
00072    ///
00073    /// @brief Asserts if PackedType instruction is not handled elsewhere.
00074    /// @param I the unhandled instruction
00075    void visitInstruction(Instruction &I)
00076    {
00077       if(isa<PackedType>(I.getType())) {
00078          std::cerr << "Unhandled Instruction with Packed ReturnType: " <<
00079                       I << '\n';
00080       }
00081    }
00082 private:
00083    /// @brief Retrieves lowered values for a packed value.
00084    /// @param val the packed value
00085    /// @return the lowered values
00086    std::vector<Value*>& getValues(Value* val);
00087 
00088    /// @brief Sets lowered values for a packed value.
00089    /// @param val the packed value
00090    /// @param values the corresponding lowered values
00091    void setValues(Value* val,const std::vector<Value*>& values);
00092 
00093    // Data Members
00094    /// @brief whether we changed the function or not
00095    bool Changed;
00096 
00097    /// @brief a map from old packed values to new smaller packed values
00098    std::map<Value*,std::vector<Value*> > packedToScalarMap;
00099 
00100    /// Instructions in the source program to get rid of
00101    /// after we do a pass (the old packed instructions)
00102    std::vector<Instruction*> instrsToRemove;
00103 };
00104 
00105 RegisterOpt<LowerPacked>
00106 X("lower-packed",
00107   "lowers packed operations to operations on smaller packed datatypes");
00108 
00109 } // end namespace
00110 
00111 FunctionPass *llvm::createLowerPackedPass() { return new LowerPacked(); }
00112 
00113 
00114 // This function sets lowered values for a corresponding
00115 // packed value.  Note, in the case of a forward reference
00116 // getValues(Value*) will have already been called for
00117 // the packed parameter.  This function will then replace
00118 // all references in the in the function of the "dummy"
00119 // value the previous getValues(Value*) call
00120 // returned with actual references.
00121 void LowerPacked::setValues(Value* value,const std::vector<Value*>& values)
00122 {
00123    std::map<Value*,std::vector<Value*> >::iterator it =
00124          packedToScalarMap.lower_bound(value);
00125    if (it == packedToScalarMap.end() || it->first != value) {
00126        // there was not a forward reference to this element
00127        packedToScalarMap.insert(it,std::make_pair(value,values));
00128    }
00129    else {
00130       // replace forward declarations with actual definitions
00131       assert(it->second.size() == values.size() &&
00132              "Error forward refences and actual definition differ in size");
00133       for (unsigned i = 0, e = values.size(); i != e; ++i) {
00134            // replace and get rid of old forward references
00135            it->second[i]->replaceAllUsesWith(values[i]);
00136            delete it->second[i];
00137            it->second[i] = values[i];
00138       }
00139    }
00140 }
00141 
00142 // This function will examine the packed value parameter
00143 // and if it is a packed constant or a forward reference
00144 // properly create the lowered values needed.  Otherwise
00145 // it will simply retreive values from a
00146 // setValues(Value*,const std::vector<Value*>&)
00147 // call.  Failing both of these cases, it will abort
00148 // the program.
00149 std::vector<Value*>& LowerPacked::getValues(Value* value)
00150 {
00151    assert(isa<PackedType>(value->getType()) &&
00152           "Value must be PackedType");
00153 
00154    // reject further processing if this one has
00155    // already been handled
00156    std::map<Value*,std::vector<Value*> >::iterator it =
00157       packedToScalarMap.lower_bound(value);
00158    if (it != packedToScalarMap.end() && it->first == value) {
00159        return it->second;
00160    }
00161 
00162    if (ConstantPacked* CP = dyn_cast<ConstantPacked>(value)) {
00163        // non-zero constant case
00164        std::vector<Value*> results;
00165        results.reserve(CP->getNumOperands());
00166        for (unsigned i = 0, e = CP->getNumOperands(); i != e; ++i) {
00167           results.push_back(CP->getOperand(i));
00168        }
00169        return packedToScalarMap.insert(it,
00170                                        std::make_pair(value,results))->second;
00171    }
00172    else if (ConstantAggregateZero* CAZ =
00173             dyn_cast<ConstantAggregateZero>(value)) {
00174        // zero constant
00175        const PackedType* PKT = cast<PackedType>(CAZ->getType());
00176        std::vector<Value*> results;
00177        results.reserve(PKT->getNumElements());
00178 
00179        Constant* C = Constant::getNullValue(PKT->getElementType());
00180        for (unsigned i = 0, e = PKT->getNumElements(); i != e; ++i) {
00181             results.push_back(C);
00182        }
00183        return packedToScalarMap.insert(it,
00184                                        std::make_pair(value,results))->second;
00185    }
00186    else if (isa<Instruction>(value)) {
00187        // foward reference
00188        const PackedType* PKT = cast<PackedType>(value->getType());
00189        std::vector<Value*> results;
00190        results.reserve(PKT->getNumElements());
00191 
00192       for (unsigned i = 0, e = PKT->getNumElements(); i != e; ++i) {
00193            results.push_back(new Argument(PKT->getElementType()));
00194       }
00195       return packedToScalarMap.insert(it,
00196                                       std::make_pair(value,results))->second;
00197    }
00198    else {
00199        // we don't know what it is, and we are trying to retrieve
00200        // a value for it
00201        assert(false && "Unhandled PackedType value");
00202        abort();
00203    }
00204 }
00205 
00206 void LowerPacked::visitLoadInst(LoadInst& LI)
00207 {
00208    // Make sure what we are dealing with is a packed type
00209    if (const PackedType* PKT = dyn_cast<PackedType>(LI.getType())) {
00210        // Initialization, Idx is needed for getelementptr needed later
00211        std::vector<Value*> Idx(2);
00212        Idx[0] = ConstantUInt::get(Type::UIntTy,0);
00213 
00214        ArrayType* AT = ArrayType::get(PKT->getContainedType(0),
00215                                       PKT->getNumElements());
00216        PointerType* APT = PointerType::get(AT);
00217 
00218        // Cast the packed type to an array
00219        Value* array = new CastInst(LI.getPointerOperand(),
00220                                    APT,
00221                                    LI.getName() + ".a",
00222                                    &LI);
00223 
00224        // Convert this load into num elements number of loads
00225        std::vector<Value*> values;
00226        values.reserve(PKT->getNumElements());
00227 
00228        for (unsigned i = 0, e = PKT->getNumElements(); i != e; ++i) {
00229             // Calculate the second index we will need
00230             Idx[1] = ConstantUInt::get(Type::UIntTy,i);
00231 
00232             // Get the pointer
00233             Value* val = new GetElementPtrInst(array,
00234                                                Idx,
00235                                                LI.getName() +
00236                                                ".ge." + utostr(i),
00237                                                &LI);
00238 
00239             // generate the new load and save the result in packedToScalar map
00240             values.push_back(new LoadInst(val,
00241                              LI.getName()+"."+utostr(i),
00242                              LI.isVolatile(),
00243                              &LI));
00244        }
00245 
00246        setValues(&LI,values);
00247        Changed = true;
00248        instrsToRemove.push_back(&LI);
00249    }
00250 }
00251 
00252 void LowerPacked::visitBinaryOperator(BinaryOperator& BO)
00253 {
00254    // Make sure both operands are PackedTypes
00255    if (isa<PackedType>(BO.getOperand(0)->getType())) {
00256        std::vector<Value*>& op0Vals = getValues(BO.getOperand(0));
00257        std::vector<Value*>& op1Vals = getValues(BO.getOperand(1));
00258        std::vector<Value*> result;
00259        assert((op0Vals.size() == op1Vals.size()) &&
00260               "The two packed operand to scalar maps must be equal in size.");
00261 
00262        result.reserve(op0Vals.size());
00263 
00264        // generate the new binary op and save the result
00265        for (unsigned i = 0; i != op0Vals.size(); ++i) {
00266             result.push_back(BinaryOperator::create(BO.getOpcode(),
00267                                                     op0Vals[i],
00268                                                     op1Vals[i],
00269                                                     BO.getName() +
00270                                                     "." + utostr(i),
00271                                                     &BO));
00272        }
00273 
00274        setValues(&BO,result);
00275        Changed = true;
00276        instrsToRemove.push_back(&BO);
00277    }
00278 }
00279 
00280 void LowerPacked::visitStoreInst(StoreInst& SI)
00281 {
00282    if (const PackedType* PKT =
00283        dyn_cast<PackedType>(SI.getOperand(0)->getType())) {
00284        // We will need this for getelementptr
00285        std::vector<Value*> Idx(2);
00286        Idx[0] = ConstantUInt::get(Type::UIntTy,0);
00287 
00288        ArrayType* AT = ArrayType::get(PKT->getContainedType(0),
00289                                       PKT->getNumElements());
00290        PointerType* APT = PointerType::get(AT);
00291 
00292        // cast the packed to an array type
00293        Value* array = new CastInst(SI.getPointerOperand(),
00294                                    APT,
00295                                    "store.ge.a.",
00296                                    &SI);
00297        std::vector<Value*>& values = getValues(SI.getOperand(0));
00298 
00299        assert((values.size() == PKT->getNumElements()) &&
00300               "Scalar must have the same number of elements as Packed Type");
00301 
00302        for (unsigned i = 0, e = PKT->getNumElements(); i != e; ++i) {
00303             // Generate the indices for getelementptr
00304             Idx[1] = ConstantUInt::get(Type::UIntTy,i);
00305             Value* val = new GetElementPtrInst(array,
00306                                                Idx,
00307                                                "store.ge." +
00308                                                utostr(i) + ".",
00309                                                &SI);
00310             new StoreInst(values[i], val, SI.isVolatile(),&SI);
00311        }
00312 
00313        Changed = true;
00314        instrsToRemove.push_back(&SI);
00315    }
00316 }
00317 
00318 void LowerPacked::visitSelectInst(SelectInst& SELI)
00319 {
00320    // Make sure both operands are PackedTypes
00321    if (isa<PackedType>(SELI.getType())) {
00322        std::vector<Value*>& op0Vals = getValues(SELI.getTrueValue());
00323        std::vector<Value*>& op1Vals = getValues(SELI.getFalseValue());
00324        std::vector<Value*> result;
00325 
00326       assert((op0Vals.size() == op1Vals.size()) &&
00327              "The two packed operand to scalar maps must be equal in size.");
00328 
00329       for (unsigned i = 0; i != op0Vals.size(); ++i) {
00330            result.push_back(new SelectInst(SELI.getCondition(),
00331                                            op0Vals[i],
00332                                            op1Vals[i],
00333                                            SELI.getName()+ "." + utostr(i),
00334                                            &SELI));
00335       }
00336 
00337       setValues(&SELI,result);
00338       Changed = true;
00339       instrsToRemove.push_back(&SELI);
00340    }
00341 }
00342 
00343 void LowerPacked::visitExtractElementInst(ExtractElementInst& EI)
00344 {
00345   std::vector<Value*>& op0Vals = getValues(EI.getOperand(0));
00346   const PackedType *PTy = cast<PackedType>(EI.getOperand(0)->getType());
00347   Value *op1 = EI.getOperand(1);
00348 
00349   if (ConstantUInt *C = dyn_cast<ConstantUInt>(op1)) {
00350     EI.replaceAllUsesWith(op0Vals[C->getValue()]);
00351   } else {
00352     AllocaInst *alloca = 
00353       new AllocaInst(PTy->getElementType(),
00354                      ConstantUInt::get(Type::UIntTy, PTy->getNumElements()),
00355                      EI.getName() + ".alloca", 
00356          EI.getParent()->getParent()->getEntryBlock().begin());
00357     for (unsigned i = 0; i < PTy->getNumElements(); ++i) {
00358       GetElementPtrInst *GEP = 
00359         new GetElementPtrInst(alloca, ConstantUInt::get(Type::UIntTy, i),
00360                               "store.ge", &EI);
00361       new StoreInst(op0Vals[i], GEP, &EI);
00362     }
00363     GetElementPtrInst *GEP = 
00364       new GetElementPtrInst(alloca, op1, EI.getName() + ".ge", &EI);
00365     LoadInst *load = new LoadInst(GEP, EI.getName() + ".load", &EI);
00366     EI.replaceAllUsesWith(load);
00367   }
00368 
00369   Changed = true;
00370   instrsToRemove.push_back(&EI);
00371 }
00372 
00373 void LowerPacked::visitInsertElementInst(InsertElementInst& IE)
00374 {
00375   std::vector<Value*>& Vals = getValues(IE.getOperand(0));
00376   Value *Elt = IE.getOperand(1);
00377   Value *Idx = IE.getOperand(2);
00378   std::vector<Value*> result;
00379   result.reserve(Vals.size());
00380 
00381   if (ConstantUInt *C = dyn_cast<ConstantUInt>(Idx)) {
00382     unsigned idxVal = C->getValue();
00383     for (unsigned i = 0; i != Vals.size(); ++i) {
00384       result.push_back(i == idxVal ? Elt : Vals[i]);
00385     }
00386   } else {
00387     for (unsigned i = 0; i != Vals.size(); ++i) {
00388       SetCondInst *setcc =
00389         new SetCondInst(Instruction::SetEQ, Idx, 
00390                         ConstantUInt::get(Type::UIntTy, i),
00391                         "setcc", &IE);
00392       SelectInst *select =
00393         new SelectInst(setcc, Elt, Vals[i], "select", &IE);
00394       result.push_back(select);
00395     }
00396   }
00397 
00398   setValues(&IE, result);
00399   Changed = true;
00400   instrsToRemove.push_back(&IE);
00401 }
00402 
00403 bool LowerPacked::runOnFunction(Function& F)
00404 {
00405    // initialize
00406    Changed = false;
00407 
00408    // Does three passes:
00409    // Pass 1) Converts Packed Operations to
00410    //         new Packed Operations on smaller
00411    //         datatypes
00412    visit(F);
00413 
00414    // Pass 2) Drop all references
00415    std::for_each(instrsToRemove.begin(),
00416                  instrsToRemove.end(),
00417                  std::mem_fun(&Instruction::dropAllReferences));
00418 
00419    // Pass 3) Delete the Instructions to remove aka packed instructions
00420    for (std::vector<Instruction*>::iterator i = instrsToRemove.begin(),
00421                                             e = instrsToRemove.end();
00422         i != e; ++i) {
00423         (*i)->getParent()->getInstList().erase(*i);
00424    }
00425 
00426    // clean-up
00427    packedToScalarMap.clear();
00428    instrsToRemove.clear();
00429 
00430    return Changed;
00431 }
00432