LLVM API Documentation

Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Namespace Members | Class Members | File Members | Related Pages

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