TINKER LEGO DOC: many_to_one.cpp Source File

00001 //
00002 // File: many_to_one.cpp
00003 //
00004 // Purpose: This file contains the many-to-one munger algorithm for collapsing multiple ops into
00005 //          a single op.
00006 //
00007 // Author: Mark C. Toburen
00008 //
00009 // History:
00010 //    Created - 8/30/01
00011 //
00012 
00013 #include "munger_main.h"
00014 #include "scheduling_utilities.H"
00015 #include "dag.H"
00016 
00017 // Global variables
00018 extern Automaton *Patterns;
00019 extern knobs *Knobs;
00020 extern machine *Mach;
00021 extern map<string, int> opMap;
00022 static vector<legoOp *> Match;
00023 static vector<insn> Rule;
00024 static insn Macro;
00025 static legoProc *proc_copy;
00026 
00027 int MungManyToOne (legoProc *Proc, int MaxOpId) {
00028    enum regionTypes region_type, subregion_type;
00029 
00030    //cerr << "many_to_one: munging proc " << Proc->GetProcName() << " ... " << endl;
00031    //cerr << "many_to_one: proc region count is " << Proc->GetCount() << endl;
00032 
00033    proc_copy = Proc;
00034    for (int i = 0; i < Proc->GetCount(); i++) {
00035       legoRegion *Region = (legoRegion *)Proc->GetItem(i);
00036       region_type = Region->GetRegionType();
00037 
00038       // if the region is a treegion, call merge() for each of its BBs...
00039       if (region_type == RT_TREE) {
00040          //cerr << "treegion BB count is " << Region->GetCount() << endl;
00041          for (int j = 0; j < Region->GetCount(); j++) {
00042             legoRegion *Subregion = (legoRegion *)Region->GetItem(i);
00043             subregion_type = Subregion->GetRegionType();
00044             MaxOpId = MungManyToOne(Subregion, MaxOpId);
00045          }
00046       } else   // ...else just mung the original region
00047          MaxOpId = MungManyToOne(Region, MaxOpId);
00048    }
00049 
00050    //cerr << "many_to_one: done munging proc " << Proc->GetProcName() << endl;
00051 }
00052 
00053 int MungManyToOne (legoRegion *Region, int MaxOpId) {
00054    dag *DDG;
00055    TreeNode *startOp;
00056 
00057    //cerr << "many_to_one: munging region " << Region->GetRegionId() << " ... " << endl;
00058 
00059    // Build the DDG for the region
00060    BuildDagForRegion(Region, Mach, Knobs);
00061    DDG = (dag *)Region->GetDAG();
00062 
00063    BLEIter Front, Back = (DDG->GetList())->end();
00064    for (Front = (DDG->GetList())->begin(); Front != Back; Front++) {
00065       bool match = false;
00066 
00067       // Look for the DDG op in the automaton and determine if its the
00068       // start of a many-to-one rule/pattern.
00069       string name = ParseMap(Front->GetOp()->GetOpcode());
00070       if (!(startOp = Patterns->FindStartOp(name)))
00071          continue;
00072 
00073       // create two vectors:
00074       //    1) Match - holds the set of legoOps that match the rule
00075       //    2) Rule - holds the set of insns that make up the rule
00076       Match.clear();
00077       Match.push_back(Front->GetOp());
00078       Rule.clear();
00079       Rule.push_back(startOp->GetOp());
00080 
00081       // determine if there is a match for the rule(s) starting with startOp
00082       match = FindMatch(Front, startOp);
00083 
00084       // If we have a match we need to replace the ops in the DDG subgraph with the corresponding
00085       // macro insn defined by the rule.
00086       if (match) {
00087          cerr << "Found match on op " << Front->GetOp()->GetOpId() << endl;
00088 
00089          // Create a new legoOp with the appropriate operands.
00090          legoOp *op = new legoOp(*(*(Match.begin())));
00091          op->SetOpId(++MaxOpId);
00092          op->SetOpcode(opMap[Macro.GetName()]);
00093 
00094          // Create op attributes for the new op.
00095          attrs *attrtail, *atscan, *attrdictionary;
00096          attrList *atlscan;
00097 
00098          // First find the tail of the attribute dictionary.
00099          if (!(attrdictionary = ((legoProc *)proc_copy)->GetAttrDictionary()))
00100             LegoFatal("MungManyToOne", "Attribute dictionary is missing.");
00101          for (attrtail = attrdictionary; attrtail->GetNextAttrPtr() != NULL; attrtail = attrtail->GetNextAttrPtr());
00102 
00103          // Now create new attr.
00104          int eaid = FindMaxEdgeAttrId((legoProc *)proc_copy);
00105          for (atlscan = op->GetOpAttrListPtr(); atlscan != NULL; atlscan = atlscan->GetNextListPtr()) {
00106             if (atlscan->GetAttrPtr() == NULL)
00107                continue;
00108             atscan = new attrs(*(atlscan->GetAttrPtr()), op, ++eaid);
00109             atlscan->SetAttrPtr(atscan);
00110             atscan->SetAttrId(eaid);
00111             atlscan->SetAttrId(eaid);
00112             attrtail->SetNextAttrPtr(atscan);
00113             attrtail = attrtail->GetNextAttrPtr();
00114          }
00115 
00116          legoOprd *dest1 = GetOprd(Macro.GetDest1(), Rule.begin(), Rule.end());
00117          if (dest1) {
00118             dest1->SetParentOpPtr(op);
00119             op->SetDestOprdPtr(dest1);
00120          }
00121 
00122          legoOprd *dest2 = GetOprd(Macro.GetDest2(), Rule.begin(), Rule.end());
00123          if (dest2) {
00124             dest2->SetParentOpPtr(op);
00125             op->SetDestOprdPtr(dest2);
00126             op->GetDestOprdPtr()->SetNextOprdPtr(dest2);
00127          }
00128 
00129          legoOprd *src1 = GetOprd(Macro.GetSrc1(), Rule.begin(), Rule.end());
00130          if (src1) {
00131             src1->SetParentOpPtr(op);
00132             op->SetSrcOprdPtr(src1);
00133          }
00134 
00135          legoOprd *src2 = GetOprd(Macro.GetSrc2(), Rule.begin(), Rule.end());
00136          if (src2) {
00137             src2->SetParentOpPtr(op);
00138             src2->SetPrevOprdPtr(src1);
00139             op->GetSrcOprdPtr()->SetNextOprdPtr(src2);
00140          }
00141 
00142          legoOprd *src3 = GetOprd(Macro.GetSrc3(), Rule.begin(), Rule.end());
00143          if (src3) {
00144             src3->SetParentOpPtr(op);
00145             src3->SetPrevOprdPtr(src2);
00146             op->GetSrcOprdPtr()->GetNextOprdPtr()->SetNextOprdPtr(src3);
00147          }
00148 
00149          legoOprd *pred = GetOprd(Macro.GetPred(), Rule.begin(), Rule.end());
00150          if (pred) {
00151             pred->SetParentOpPtr(op);
00152             op->SetPredOprdPtr(pred);
00153          }
00154 
00155          // Replace the insn pattern with the macro op in the IR.
00156          LegoOpVecIter liter = Match.begin();
00157          legoOp *last = *(Match.end() - 1);
00158 
00159          cerr << "Adding mid op " << op->GetOpId() << " (" << &op << ")" << endl;
00160          AddMidOp(op, last);
00161          for (; liter != Match.end(); liter++) {
00162             if ((*liter)->GetNextLink() != NULL)
00163                RemoveMidOp(*liter);
00164             else
00165                RemoveLastOp(*liter);
00166          }
00167          Region->RefreshAll();
00168 
00169          // do some debug stuff here
00170 //         legoProc *proc = (legoProc *)FindParentRegionType(RT_PROC, op);
00171 //         opEdges *theedge; 
00172 //         for (theedge = proc->GetEdgeDictionary(); theedge != NULL; theedge = theedge->GetNextOpEdgePtr()) {
00173 //            if ((theedge->GetFromOpPtr() == op->GetPrevLink()) && (theedge->GetToOpPtr() == op) && (theedge->GetEdgeType() == ET_CNTL))
00174 //               cerr << "*** Found proper control edge defined after many-to-one mapping." << endl;
00175 //         }
00176 
00177 //         for (legoOp *alllist = proc->GetListOpPtr(); alllist->GetListOpPtr() != NULL; alllist = alllist->GetListOpPtr()) {
00178 //           if (alllist->GetOpcode() == op->GetOpcode())
00179 //              cerr << "*** Opcode match on list op " << alllist->GetOpId() << "(" << &op << ")" << endl;
00180 //        }
00181       }
00182    }
00183 
00184    //cerr << "many_to_one: done munging region " << Region->GetRegionId() << endl;
00185    return MaxOpId;
00186 }
00187 
00188 bool FindMatch (BLEIter dagNode, TreeNode *treeNode) {
00189    bool match = false;
00190    SuccNode *snode;
00191 
00192    for (BelongIter biter = treeNode->GetBelongTo().begin(); biter != treeNode->GetBelongTo().end(); biter++) {
00193       if ((biter->second).IsStartOp()) {
00194          if (!(snode = (biter->second).GetSuccessor())) {
00195             //cerr << ">> FindMatch: matched one-to-one rule on Lego op " << dagNode->GetOp()->GetOpId() << endl;
00196             if (!VerifyOperandRules(dagNode->GetOp(), treeNode->GetOp()))
00197                return false;
00198             Macro = (biter->second).GetMacroInsn();
00199             return true;
00200          } else {
00201             match = FindDagMatch(dagNode, biter);
00202             return match;
00203          }
00204       }
00205    }
00206 
00207    return match;
00208 }
00209 
00210 bool FindDagMatch (BLEIter dagNode, BelongIter biter) {
00211    bool match = false;
00212    SuccNode *succ = (biter->second).GetSuccessor();
00213    SLEIter Front, Back = dagNode->Successors->end();
00214 
00215    for (Front = dagNode->Successors->begin(); Front != Back; Front++) {
00216       string name = ParseMap(Front->GetOp()->GetOpcode());
00217       if (name == succ->GetOp().GetName()) {
00218          if (!VerifyOperandRules(Front->GetOp(), succ->GetOp()))
00219             return false;
00220          Macro = (biter->second).GetMacroInsn();
00221          Match.push_back(Front->GetOp());
00222          Rule.push_back(succ->GetOp());
00223          if (succ->IsLeafNode()) {
00224             return true;
00225          } else {
00226             match = FindDagMatch(Front->GetDagEntry(), succ->GetParentNode()->GetBelongTo().find(Macro.GetName()));
00227             return match;
00228          }
00229       }
00230    }
00231 
00232    return match;
00233 }
00234 
00235 legoOprd *GetOprd (oprd *oprd, InsnVecIter Front, InsnVecIter Back) {
00236    legoOprd *newoprd;
00237    oprd_type ot;
00238    int cnt, pos;
00239    bool lit = false;
00240 
00241    if (oprd->GetType() == NIL) {
00242       newoprd = NULL;
00243       return newoprd;
00244    }
00245 
00246    for (cnt = 0, pos = 0; Front != Back; Front++, cnt++) {
00247       if (*(Front->GetDest1()) == *oprd) {
00248          ot = D;
00249          pos = 1;
00250          break;
00251       } else if (*(Front->GetDest2()) == *oprd) {
00252          ot = D;
00253          pos = 2;
00254          break;
00255       } else if (*(Front->GetSrc1()) == *oprd) {
00256          ot = S;
00257          pos = 1;
00258          break;
00259       } else if (*(Front->GetSrc2()) == *oprd) {
00260          ot = S;
00261          pos = 2;
00262          break;
00263       } else if (*(Front->GetSrc3()) == *oprd) {
00264          ot = S;
00265          pos = 3;
00266          break;
00267       } else if (*(Front->GetPred()) == *oprd) {
00268          ot = PR;
00269          break;
00270       } else if ((Front->GetSrc1()->GetType() == INT_LIT && oprd->GetType() == INT_LIT) ||
00271                  (Front->GetSrc1()->GetType() == FLOAT_LIT && oprd->GetType() == FLOAT_LIT)) {
00272          ot = S;
00273          pos = 1;
00274          lit = true;
00275          break;
00276       } else if ((Front->GetSrc2()->GetType() == INT_LIT && oprd->GetType() == INT_LIT) ||
00277                  (Front->GetSrc2()->GetType() == FLOAT_LIT && oprd->GetType() == FLOAT_LIT)) {
00278          ot = S;
00279          pos = 2;
00280          lit = true;
00281          break;
00282       } else if ((Front->GetSrc3()->GetType() == INT_LIT && oprd->GetType() == INT_LIT) ||
00283                  (Front->GetSrc3()->GetType() == FLOAT_LIT && oprd->GetType() == FLOAT_LIT)) {
00284          ot = S;
00285          pos = 3;
00286          lit = true;
00287          break;
00288       }
00289    }
00290 
00291    // Set the op which has the required operand.
00292    legoOp *op;
00293    LegoOpVecIter iter = Match.begin();
00294    op = *(iter + cnt);
00295 
00296    // choose the proper operand from this op.
00297    switch (ot) {
00298       case D:
00299          switch (pos) {
00300             case 1:
00301                newoprd = new legoOprd(*(op->GetDestOprdPtr()));
00302                break;
00303             case 2:
00304                newoprd = new legoOprd(*(op->GetDestOprdPtr()->GetNextOprdPtr()));
00305                break;
00306             default:
00307                LegoFatal("GetOprd", "invalid dest operand position.");
00308          }
00309          break;
00310       case S:
00311          switch (pos) {
00312             case 1:
00313                newoprd = new legoOprd(*(op->GetSrcOprdPtr()));
00314                break;
00315             case 2:
00316                newoprd = new legoOprd(*(op->GetSrcOprdPtr()->GetNextOprdPtr()));
00317                break;
00318             case 3:
00319                newoprd = new legoOprd(*(op->GetSrcOprdPtr()->GetNextOprdPtr()->GetNextOprdPtr()));
00320                break;
00321             default:
00322                LegoFatal("GetOprd", "invalid source operand position.");
00323          }
00324          break;
00325       case PR:
00326          newoprd = new legoOprd(*(op->GetPredOprdPtr()));
00327          break;
00328       default:
00329          break;
00330    }
00331 
00332    if (lit) {
00333       switch (newoprd->GetOprdType()) {
00334          case OT_LITERAL_SH:
00335             newoprd->SetLiteralShort(oprd->GetIval());
00336             break;
00337          case OT_LITERAL_USH:
00338             newoprd->SetLiteralUShort(oprd->GetIval());
00339             break;
00340          case OT_LITERAL_I:
00341             newoprd->SetLiteralInteger(oprd->GetIval());
00342             break;
00343          case OT_LITERAL_UI:
00344             newoprd->SetLiteralUInteger(oprd->GetIval());
00345             break;
00346          case OT_LITERAL_LNG:
00347             newoprd->SetLiteralLong((long)oprd->GetIval());
00348             break;
00349          case OT_LITERAL_ULNG:
00350             newoprd->SetLiteralLong((long)oprd->GetIval());
00351             break;
00352          case OT_LITERAL_LLNG:
00353             newoprd->SetLiteralLong((long long)oprd->GetIval());
00354             break;
00355          case OT_LITERAL_ULLNG:
00356             newoprd->SetLiteralLong((long long)oprd->GetIval());
00357             break;
00358          case OT_LITERAL_LLLNG:
00359             newoprd->SetLiteralLong((long long)oprd->GetIval());
00360             break;
00361          case OT_LITERAL_ULLLNG:
00362             newoprd->SetLiteralLong((long long)oprd->GetIval());
00363             break;
00364          case OT_LITERAL_F:
00365             newoprd->SetLiteralFloat(oprd->GetFval());
00366             break;
00367          case OT_LITERAL_D:
00368             newoprd->SetLiteralDouble((double)oprd->GetFval());
00369             break;
00370          default:
00371             LegoFatal("GetOprd", "invalid lego literal type.");
00372       }
00373    }
00374 
00375    return newoprd;
00376 }