CompleteLiveness.C

Go to the documentation of this file.

#include "CompleteLiveness.H"

//#define _LIVE_VAR_DEBUG_

struct UseDefOprd {
        int OprdRegNum;
        int OprdFileType;
        struct UseDefOprd *next;
};

legoHash <int, iavector *, legoHash_lt_int> *LiveNess;

static legoHash <int, struct UseDefOprd *, legoHash_lt_int> *Use;
static legoHash <int, struct UseDefOprd *, legoHash_lt_int> *Def;
static legoHash <int, struct UseDefOprd *, legoHash_lt_int> *L_Out;

static int MaxGregNum = 0;
static int MaxFregNum = 0;
static int MaxPregNum = 0;
static int MaxBregNum = 0;

static void
SetUsesAndDefs_Op(legoOp *op) {
  legoOprd *dest, *src;
  struct UseDefOprd *use, *def;
  
  //(a). This step is for the defs
  
  //HZ: in the case of the predicate, we take a conservative approach by saying
  // that the predicate guarded insn will only use regs but not kill (define)
  // regs. (p0 is always 1)
 if(op->GetPredOprdPtr() != NULL && op->GetPredOprdPtr()->GetOprdType() ==
         OT_REG && op->GetPredOprdPtr()->GetOprdFileType() == FT_PR && 
         op->GetPredOprdPtr()->GetOprdRegNum() != 0)
 {
     ;
 }
 else
 {
  for(dest = op->GetDestOprdPtr();
        dest != NULL; dest = dest->GetNextOprdPtr()) {
        if(dest->GetOprdType() != OT_REG)
        continue;
        def = Def->Lookup(op->GetOpId());
        if(Def->NotFound()) {
          // Thus the op has no element present in the 
          // Def table
          def = new struct UseDefOprd;
          def->OprdRegNum = dest->GetOprdRegNum();
          def->OprdFileType = dest->GetOprdFileType();
          def->next = NULL;
          
          Def->Set (op->GetOpId(), def);  
        } // end if
        else {
          // If we are here, there is some previous def
          // present
          while(def->next != NULL)
            def = def->next;
            
            // Now allocate memory for the next
            def->next = new struct UseDefOprd;
            def->next->OprdRegNum =  dest->GetOprdRegNum();
            def->next->OprdFileType = dest->GetOprdFileType();
            def->next->next = NULL;
        } // end else
  } // end for(dest....
 }//end of if (predicated ...)
 
  //(b). This step is for the Use
  for(src = op->GetSrcOprdPtr();
        src != NULL; src = src->GetNextOprdPtr()) {
        if(src->GetOprdType() != OT_REG)
        continue;
        use = Use->Lookup(op->GetOpId());
        if(Use->NotFound()) {
          // Thus the op has no element present in the 
          // Def table
          use = new struct UseDefOprd;
          use->OprdRegNum = src->GetOprdRegNum();
          use->OprdFileType = src->GetOprdFileType();
          use->next = NULL;
          
          Use->Set (op->GetOpId(), use);  
        } // end if
        else {
          // If we are here, there is some previous def
          // present
          while(use->next != NULL)
            use = use->next;
            
            // Now allocate memory for the next
            use->next = new struct UseDefOprd;
            use->next->OprdRegNum =  src->GetOprdRegNum();
            use->next->OprdFileType = src->GetOprdFileType();
            use->next->next = NULL;
        } // end else
  } // end for(src....
  
  //HZ: bug here, we should set the indirect uses e.g., the parameters of
  // br.call
  
  //(c). Don't forget about the Pred
  // These can be the uses for the ops
  for(src = op->GetPredOprdPtr();
        src != NULL; src = src->GetNextOprdPtr()) {
        if(src->GetOprdType() != OT_REG)
        continue;
        use = Use->Lookup(op->GetOpId());
        if(Use->NotFound()) {
          // Thus the op has no element present in the 
          // Def table
          use = new struct UseDefOprd;
          use->OprdRegNum = src->GetOprdRegNum();
          use->OprdFileType = src->GetOprdFileType();
          use->next = NULL;
          
          Use->Set (op->GetOpId(), use);  
        } // end if
        else {
          // If we are here, there is some previous def
          // present
          while(use->next != NULL)
            use = use->next;
            
            // Now allocate memory for the next
            use->next = new struct UseDefOprd;
            use->next->OprdRegNum =  src->GetOprdRegNum();
            use->next->OprdFileType = src->GetOprdFileType();
            use->next->next = NULL;
        } // end else
  } // end for(src....
  
}

static int 
Redefine(legoOprd *def, legoOp *UseOp)
{
        int Redef;
        legoOp *op;
        legoOprd *dest;
        
        // Check the redefinition from the 
        // def reg of the UseOp to the 
        // last of the BB
        Redef = 0;
        for(op = UseOp; op != NULL; 
                op = op->GetNextLink()) {
          for(dest = op->GetDestOprdPtr(); dest != NULL;
                dest = dest->GetNextOprdPtr()) {
                if(dest->GetOprdType() != 
                        def->GetOprdType()) continue;
                if(dest->GetOprdFileType() != 
                        def->GetOprdFileType()) continue;
                if(dest->GetOprdRegNum() != 
                        def->GetOprdRegNum()) continue;
                // if we are here we have a redefinition
                
                Redef = 1;
                break;
          }// end for   
          if(Redef) break;
        } // end for
        
        return Redef;
}
static  struct UseDefOprd *
AttachOprdInfo(struct UseDefOprd *Live, 
                legoOprd *oprd) {
  struct UseDefOprd *temp;
  
  if(Live != NULL) {
  int confidence = 1;
     for(temp = Live; temp->next != NULL;
        temp = temp->next) {
        if(temp->OprdRegNum != oprd->GetOprdRegNum())
        continue;
        if(temp->OprdFileType != oprd->GetOprdFileType())
        continue;
        // The live has this oprd
        // so need to attach it again
        confidence = 0;
     } // end for (temp..)
     // check again
     if(temp->OprdRegNum == oprd->GetOprdRegNum() &&
        temp->OprdFileType == oprd->GetOprdFileType())
        confidence = 0;
     if(confidence) {
     temp->next = new struct UseDefOprd;
     temp = temp->next;
     temp->OprdRegNum = oprd->GetOprdRegNum();
     temp->OprdFileType = oprd->GetOprdFileType();
     temp->next = NULL;
     } // end if
  } // end if
  else {
        Live = new struct UseDefOprd;
        Live->OprdRegNum = oprd->GetOprdRegNum();
        Live->OprdFileType = oprd->GetOprdFileType();
        Live->next = NULL;
  }
  return Live;          
} 
static struct UseDefOprd *
GetLiveOut(legoOp *LastOp, 
        legoOp *StartOp, legoProc *Proc) {
 struct UseDefOprd *LiveOut = NULL, *LiveTemp = NULL;
 attrs *Attr;
 legoOprd *AttrOprd;
 opList *opl;
 legoOp *PredOp;
 opEdges *ControlEdge1;
 
 if(LastOp->GetOutListPtr() != NULL) {
  for(opl = LastOp->GetOutListPtr(); opl != NULL;
        opl = opl->GetNextListPtr()) {
        PredOp = (legoOp *) opl->GetOpPtr();
        // Find the control Edge 
        ControlEdge1 = FindControlEdge (LastOp, PredOp);
        if(ControlEdge1 == NULL) {
         fprintf(stderr, "There is no Ctrl edge between op %d and op %d\n",
                LastOp->GetOpId(), PredOp->GetOpId());
         exit(-1);
        } // end if
        Attr = FindLiveAttribute(ControlEdge1);
        for(AttrOprd = Attr->GetAttrOprdPtr(); AttrOprd != NULL;
                AttrOprd = AttrOprd->GetNextOprdPtr()) {
          LiveOut = AttachOprdInfo(LiveOut, AttrOprd);
        } // end for(AttrOprd....
  } // end for(opl...
 } // end if
 else {
   // This can happen if the Region or the BB
   // is the end BB of the Proc. We can say
   // in other words that this BB ends in
   // "br.ret....."
   // Now here can be two cases: -
   // (a). if there is only one BB
   // in the Proc. so the LiveIn will be NULL
   // (b) The Proc has more than one BB
   // we will have the LiveIn information
   
   // if we have the Livein information
   // we can operations and get the LiveOut
   // of the end Op
   
   // else we will assume that the only Live regs
   // are the O/p regs(regs8 to reg12) and traverse 
   // the ops to get the LiveOut
   if(Proc->GetCount() < 2) {
      // we don't have the LiveIn information
      // assume that o/p regs are live at the start
      // First of all check they are not redefined
      // in the BB.
      legoOprd *Oprd = new legoOprd;
      Oprd->SetOprdType(OT_REG);
      Oprd->SetOprdFileType(FT_GPR);
      int i;
      for(i = 8; i < 12; i++) {
         Oprd->SetOprdRegNum(i);
         if(1){
           LiveOut = AttachOprdInfo(LiveOut, Oprd);
         }
      } // end for(i....
      delete Oprd;
   } // end if
   else {
     // same principle will be applied here
     // the only change will be that 
     // we are going to take the o/p regs from the LiveIn
     for(opl = StartOp->GetInListPtr(); opl != NULL;
        opl = opl->GetNextListPtr()) { 
        PredOp = (legoOp *) opl->GetOpPtr();
        // Find the control Edge 
        ControlEdge1 = FindControlEdge (PredOp, StartOp);
        if(ControlEdge1 == NULL) {
         fprintf(stderr, "There is no Ctrl edge between op %d and op %d\n",
                PredOp->GetOpId(), StartOp->GetOpId());
         exit(-1);
        } // end if
        Attr = FindLiveAttribute(ControlEdge1);
        for(AttrOprd = Attr->GetAttrOprdPtr(); AttrOprd != NULL;
                AttrOprd = AttrOprd->GetNextOprdPtr()) {
           if(AttrOprd->GetOprdFileType() != FT_GPR)
           continue;
           if(AttrOprd->GetOprdRegNum() >= 8 &&
                AttrOprd->GetOprdRegNum() <= 11) {
             if(1) {
             LiveOut = AttachOprdInfo(LiveOut, AttrOprd);
            } //end if
           } // end if
        } // end for(AttrOprd...
   }// end for(opl...
  } // end else
 } // end else
 return LiveOut;
}
static  struct UseDefOprd *
AttachLiveOut(struct UseDefOprd *Live, 
                struct UseDefOprd *oprd) {
  struct UseDefOprd *temp;
  
  if(Live != NULL) {
     int confidence = 1;
     for(temp = Live; temp->next != NULL;
        temp = temp->next) {
        if(temp->OprdRegNum != oprd->OprdRegNum)
        continue;
        if(temp->OprdFileType != oprd->OprdFileType)
        continue;
        // The live has this oprd
        // so need to attach it again
        confidence = 0;
     } // end for (temp..)
     // check again
     if(temp->OprdRegNum == oprd->OprdRegNum &&
        temp->OprdFileType == oprd->OprdFileType)
        confidence = 0;
     if(confidence) {
     temp->next = new struct UseDefOprd;
     temp = temp->next;
     temp->OprdRegNum = oprd->OprdRegNum;
     temp->OprdFileType = oprd->OprdFileType;
     temp->next = NULL;
    }
  } // end if
  else {
        Live = new struct UseDefOprd;
        Live->OprdRegNum = oprd->OprdRegNum;
        Live->OprdFileType = oprd->OprdFileType;
        Live->next = NULL;
  }
  return Live;          
} 
static void
SetLiveOut_AllOps(struct UseDefOprd *LiveOut, 
        legoOp *LastOp) {
  legoOp *op;
  struct UseDefOprd *Out, *use, *def, *def1, *In = NULL;
  // Now here we will traverse from the last op 
  // to the first op. setting LiveOut using Eqn.
  // LiveIn = use[i] U (LiveOut[i] - def[i])
  
  // first of all set LiveOut for the Last Op
  L_Out->Set (LastOp->GetOpId(), LiveOut);
  // Now traverse Ops
  for(op = LastOp; op != NULL;
        op = op->GetPrevLink()) {
        Out = L_Out->Lookup(op->GetOpId());
        if(L_Out->NotFound()) {
         fprintf(stderr, "There is something wrong with Live\n");
         exit(-1);
        }
        // Here the main point is that the LiveIn
        // of the Op becomes the LiveOut of the Prev 
        // Op
        if(op->GetPrevLink() != NULL) {
           for(;Out != NULL; Out = Out->next) {
                def1 = Def->Lookup(op->GetOpId());
                int confidence = 1;
                if(!Def->NotFound()) {
                   for(def = def1; def != NULL; def = def->next) {
                      if(def->OprdRegNum != Out->OprdRegNum)
                      continue;
                      if(def->OprdFileType != Out->OprdFileType)
                      continue;
                      
                      confidence = 0;
                      break;
                   }// end for(def..
                }// end if
                if(!confidence)
                continue;
                In = AttachLiveOut(In, Out); 
           } // end for(Out..
           // Now add the uses
            use = Use->Lookup(op->GetOpId());
            if(!Use->NotFound()) {
                for(; use != NULL; use = use->next) {
                  In = AttachLiveOut(In, use);
                } // end for
            } // end if
            L_Out->Set (((legoOp *) op->GetPrevLink())->GetOpId(),
                        In);
            In = NULL;
        }// end if
  } // end for (op..
}

static void
SetLiveInformation() {
  iavector *s;
  struct UseDefOprd *liveOprd;
  int opid;
  for(L_Out->Start(); !(L_Out->AtEnd()); L_Out->Next()){
  liveOprd = L_Out->LookupCurrent();
  opid = L_Out->GetCurrentKey(); 
  while(liveOprd != NULL) {  
     switch(liveOprd->OprdFileType)
     {
        case FT_GPR: s = LiveNess->Lookup(opid);
                     if(LiveNess->NotFound()) {
                        s = new iavector(MaxGregNum,
                                MaxFregNum, MaxPregNum, MaxBregNum);
                        // Now set the bit representing the particular
                        // "reg"
                        s->SetGreg(liveOprd->OprdRegNum);
                        
                        LiveNess->Set(opid, s);
                     } // end if
                     else
                     s->SetGreg(liveOprd->OprdRegNum);
                     break;
        case FT_FPR: s = LiveNess->Lookup(opid);
                     if(LiveNess->NotFound()) {
                        s = new iavector(MaxGregNum,
                                MaxFregNum, MaxPregNum, MaxBregNum);
                        // Now set the bit representing the particular
                        // "reg"
                        s->SetFreg(liveOprd->OprdRegNum);
                        
                        LiveNess->Set(opid, s);
                     } // end if
                     else
                     s->SetFreg(liveOprd->OprdRegNum);
                     break;
        case FT_PR: s = LiveNess->Lookup(opid);
                     if(LiveNess->NotFound()) {
                        s = new iavector(MaxGregNum,
                                MaxFregNum, MaxPregNum, MaxBregNum);
                        // Now set the bit representing the particular
                        // "reg"
                        s->SetPreg(liveOprd->OprdRegNum);
                        
                        LiveNess->Set(opid, s);
                     } // end if
                     else
                     s->SetPreg(liveOprd->OprdRegNum);
                     break;
        case FT_BTR: s = LiveNess->Lookup(opid);
                     if(LiveNess->NotFound()) {
                        s = new iavector(MaxGregNum,
                                MaxFregNum, MaxPregNum, MaxBregNum);
                        // Now set the bit representing the particular
                        // "reg"
                        s->SetBreg(liveOprd->OprdRegNum);
                        
                        LiveNess->Set(opid, s);
                     } // end if
                     else
                     s->SetBreg(liveOprd->OprdRegNum);
                     break;
     }
     liveOprd = liveOprd->next;
    } // end while
  } // end for
}

static void
PrintLiveNess() {
  iavector *s;
  for(LiveNess->Start(); !(LiveNess->AtEnd());
        LiveNess->Next()) {
     printf("\nGetting the liveness information for op %d\n",
                LiveNess->GetCurrentKey());
     s = LiveNess->LookupCurrent();
     printf("\nGetting the Live Gregs\n");
     int i;
     for(i = 0; i < s->GetGregSize(); i++) {
       if(s->ReadGreg(i))
       printf("reg %d\t", i);
     } // end for
     printf("\nGetting the Live Gregs\n");
     for(i = 0; i < s->GetFregSize(); i++) {
       if(s->ReadFreg(i))
       printf("freg %d\t", i);
     } // end for
     printf("\nGetting the Live Pregs\n");
     for(i = 0; i < s->GetPregSize(); i++) {
       if(s->ReadPreg(i))
       printf("preg %d\t", i);
     } // end for
     printf("\nGetting the Live Bregs\n");
     for(i = 0; i < s->GetBregSize(); i++) {
       if(s->ReadBreg(i))
       printf("breg %d\t", i);
     } // end for
  } // end for
}

legoHash <int, iavector *, legoHash_lt_int> * 
CompleteLiveNess(legoProc *Proc) {
legoRegion *Region;
legoOp *op, *StartOp, *LastOp;
legoOprd *src, *preg;
struct UseDefOprd *LiveOut;
 LiveVariables(Proc);
 // Allocate Memory for the Hash Table
 LiveNess = new legoHash <int, iavector *, legoHash_lt_int>; 
 
 // Get the max reg Num of all the file Type
 MaxGregNum = FindMaxRegNum (Proc,FT_GPR) + 1;
 
 //HZ: should cover r8, r9, r10, r11 even the max reg num is less than 8.
 if(MaxGregNum < 32) MaxGregNum = 32;
 
 MaxFregNum = FindMaxRegNum (Proc,FT_FPR) + 1;
 MaxPregNum = FindMaxRegNum (Proc,FT_PR) + 1;
 MaxBregNum = FindMaxRegNum (Proc,FT_BTR) + 1;
 L_Out = new legoHash <int, struct UseDefOprd *, legoHash_lt_int>;
 int j;
 for(j = 0; j < Proc->GetCount(); j++) {
   Region = (legoRegion *) Proc->GetItem(j);
   StartOp = (legoOp *) (Region->GetEntryOpsPtr())->GetOpPtr();
   LastOp = (legoOp *) (Region->GetExitOpsPtr())->GetOpPtr();
           
   // Get the LiveOut of the Region
   LiveOut = GetLiveOut(LastOp, StartOp, Proc);
           
   Use = new legoHash <int, struct UseDefOprd *, legoHash_lt_int>;
   Def = new legoHash <int, struct UseDefOprd *, legoHash_lt_int>;
   int k;
   for(k = 0; k < Region->GetCount(); k++) {
    op = (legoOp *) Region->GetItem(k);
    // Get the use and the definition set of
    // each op in the Region or the BB
    // store them in the hash table
    // The key of the hash table will be the Op
    // ids as they are unique, and the list of oprdRegNum
    // and the OprdFileType will be stored as elements
    SetUsesAndDefs_Op(op);
   } // end for(k ...
   SetLiveOut_AllOps(LiveOut, LastOp);
   // De-allocate Use and Def
   for(Use->Start(); !(Use->AtEnd()); Use->Next()) {
    delete Use->LookupCurrent();
   }
   delete Use;
   Use = NULL;
   for(Def->Start(); !(Def->AtEnd()); Def->Next()) {
    delete Def->LookupCurrent();
   }
   delete Def;
   Def = NULL;
 }// end for(j...
 SetLiveInformation();
 #ifdef _LIVE_VAR_DEBUG_
  //PrintLiveNess();
 printf("Getting Live out information for the Proc %s\n",
                Proc->GetProcName());
 for(L_Out->Start(); !(L_Out->AtEnd()); L_Out->Next()) {
   struct UseDefOprd *sau =  L_Out->LookupCurrent();
   printf("LiveOut for op %d\n", 
   L_Out->GetCurrentKey());
   while(sau != NULL) {
    switch(sau->OprdFileType) {
        case FT_GPR: printf("r%d\t",
                   sau->OprdRegNum);
                   break;
        case FT_FPR: printf("f%d\t",
                   sau->OprdRegNum);
                   break;
        case FT_PR: printf("p%d\t",
                   sau->OprdRegNum);
                   break;
        case FT_BTR: printf("b%d\t",
                   sau->OprdRegNum);
                   break;
    }
    sau = sau->next;
   }
   printf("\n");
 } 
 #endif
 for(L_Out->Start(); !(L_Out->AtEnd()); L_Out->Next()) {
 delete L_Out->LookupCurrent();
 } 
 delete L_Out;
 L_Out = NULL;
 
 return LiveNess;
}

---