Open64: osprey/be/cg/cg_swp_emit.cxx Source File

00001 /*
00002  * Copyright 2003, 2004, 2005, 2006 PathScale, Inc.  All Rights Reserved.
00003  */
00004 
00005 /*
00006 
00007   Copyright (C) 2000, 2001 Silicon Graphics, Inc.  All Rights Reserved.
00008 
00009   This program is free software; you can redistribute it and/or modify it
00010   under the terms of version 2 of the GNU General Public License as
00011   published by the Free Software Foundation.
00012 
00013   This program is distributed in the hope that it would be useful, but
00014   WITHOUT ANY WARRANTY; without even the implied warranty of
00015   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  
00016 
00017   Further, this software is distributed without any warranty that it is
00018   free of the rightful claim of any third person regarding infringement 
00019   or the like.  Any license provided herein, whether implied or 
00020   otherwise, applies only to this software file.  Patent licenses, if 
00021   any, provided herein do not apply to combinations of this program with 
00022   other software, or any other product whatsoever.  
00023 
00024   You should have received a copy of the GNU General Public License along
00025   with this program; if not, write the Free Software Foundation, Inc., 59
00026   Temple Place - Suite 330, Boston MA 02111-1307, USA.
00027 
00028   Contact information:  Silicon Graphics, Inc., 1600 Amphitheatre Pky,
00029   Mountain View, CA 94043, or:
00030 
00031   http://www.sgi.com
00032 
00033   For further information regarding this notice, see:
00034 
00035   http://oss.sgi.com/projects/GenInfo/NoticeExplan
00036 
00037 */
00038 
00039 
00040 /* =======================================================================
00041  * =======================================================================
00042  *
00043  *  Module: cg_swp_emit.cxx
00044  *  $Revision: 1.1.1.1 $
00045  *  $Date: 2005/10/21 19:00:00 $
00046  *  $Author: marcel $
00047  *  $Source: /proj/osprey/CVS/open64/osprey1.0/be/cg/cg_swp_emit.cxx,v $
00048  *
00049  *  Description:
00050  *  ============
00051  *
00052  *  Code generation phase after modulo scheduling and register allocation.
00053  *
00054  * =======================================================================
00055  * ======================================================================= */
00056 
00057 // ************************************************************************
00058 //
00059 // This file implements the translation of modulo-scheduled and rotating-
00060 // register-allocated code into the CGIR recognized by the rest of CG.
00061 // The following lists of the constraints and possible interactions with
00062 // downstream CG components.
00063 // 
00064 //
00065 // Generation of SWP region:
00066 // 
00067 //  - SWP produces a region of type RID_TYPE_swp. (See be/region/region_util.h)
00068 //  - The region contains a set of BBs that have been scheduled and
00069 //    register allocated.
00070 //  - There is one prolog/epilog block for each entry/exit of the region.
00071 //  - A backpatch in the prolog/epilog blocks is converted into a TN copy.
00072 //  - The TN copies are called the glue code.
00073 //    They are marked OP_glue(). 
00074 //    In the prolog, the result has already been assigned a register.
00075 //    In the epilog, the operand has already been assigned a register.
00076 //    Predicate copy is expanded into a sequence of operations.
00077 //  - The SWP region is considered a black-box.  BBs in the region
00078 //    are not processed by any subsequent optimizations, except
00079 //    bundling in cgemit.cxx.
00080 //  - The prolog/epilog blocks needs further optimizations,
00081 //    but the glue code imposes some restrictions.
00082 //
00083 // GRA interactions:
00084 //
00085 //  - The TNs used in the SWP region are used in the
00086 //    SWP region, used as results in prolog glue copies, or used 
00087 //    as operands in the epilog copies.  Those TNs are not used elsewhere.
00088 //    This is to relieve GRA from worrying about live ranges that span the 
00089 //    boundary of a SWP region.  A consequence is that any invariants
00090 //    must be assigned a new TN inside the SWP loop, and a glue
00091 //    copy is introduced to copy the value of old TN into the new one.
00092 //    Similar requirements for other live-in, live-out TNs are enforced
00093 //    by the conversion of backpatches into glue copies.
00094 //
00095 // HB_SCHED/LRA interactions:
00096 //
00097 //  - The prolog/epilog are allowed to have a mix of glue and non-glue
00098 //    operations, i.e., instructions are partially register allocated.
00099 //    For example, the initialization of predicate registers,
00100 //    the initialization of the loop-counter and epilog-counter are
00101 //    inserted to the prolog block.
00102 //
00103 // EBO interactions:
00104 //
00105 //  - In general glue copies cannot be optimized away, except by GRA preferencing.
00106 //  - EBO may combine a glue copy with other operations, but must preserve
00107 //    the register assignment.
00108 //
00109 // CFLOW interactions:
00110 //
00111 //  - cflow may merge prolog/epilog blocks with their predecessors/successors,
00112 //  - cflow may reorder the prolog/epilog blocks with the restriction that
00113 //    the fall-through epilog block from the SWP region remains in the
00114 //    fall-through path.
00115 //  - cflow should not reorder blocks in the SWP region.
00116 //
00117 // REG_LIVE interaction:
00118 //
00119 //  - REG_LIVE information are needed by postpass GCM, and EBO after scheduling.
00120 //  - If registers do not rotate, REG_LIVE (see reg_live.cxx) can figure out 
00121 //    the register live-in and kill set by examining the SWP-scheduled basic
00122 //    blocks.
00123 //  - If registers rotate, a use of Rx refers to Ry defined in a previous 
00124 //    iteration, it is impossible to determine the register live-in and kill
00125 //    set without annotations.   
00126 //  - We will add a new BB annotation kind:  ANNOT_ROTATING_KERNEL.
00127 //    The info stored in ANNOT_ROTATING_KERNEL are the live-in, kill 
00128 //    REGSET.
00129 //  - We will also a BB_flag: BB_ROTATING_KERNEL to indicate the
00130 //    existence of REGSET annotations.   The flag can be tested
00131 //    using BB_rotating_kernel(bb).
00132 //  - If GRA decides to rename any logical registers in the SWP kernel,
00133 //    GRA must also to update the REGSETs in ANNOT_ROTATING_KERNEL.
00134 //
00135 // ************************************************************************
00136 
00137 
00138 #define USE_STANDARD_TYPES
00139 
00140 #include "defs.h"
00141 #include "cg.h"
00142 #include "cg_swp.h"
00143 #include "cg_swp_options.h"
00144 #include "tracing.h"
00145 #include "op.h"
00146 #include "op_list.h"
00147 #include "bb.h"
00148 #include "cgexp.h"
00149 #include "tn.h"
00150 #include "tn_set.h"
00151 #include "cg_loop.h"
00152 #include "register.h"
00153 #include "cg_swp_target.h"
00154 #include "annotations.h"
00155 #include "ti_res_res.h"
00156 #include "ti_res_count.h"
00157 
00158 
00159 // The function object returns TRUE when the schedule slot of OP[i] 
00160 // is smaller than that of OP[j].  With bundling no two ops should
00161 // have the same slot number; without bundling all ops with the same
00162 // slot number (== modulo cycle number) will be sorted into
00163 // arbitrary order.
00164 //
00165 struct Order_Op_State_by_Modulo_Cycles {
00166   const SWP_OP_vector& state;
00167   bool operator()(INT i, INT j) { 
00168     return state[i].slot < state[j].slot; 
00169   }
00170   Order_Op_State_by_Modulo_Cycles(const SWP_OP_vector& op_state):state(op_state) {}
00171 };
00172 
00173 
00174 // Rearrange the OPs according to the SWP schedule.
00175 //   - first remove all OPs from the loop body
00176 //   - then insert the OPs based on <modulo-cycle, slot> ordering
00177 //   - also modify their controlling predicate
00178 //  
00179 static void 
00180 SWP_Reorder_OPs(const SWP_OP_vector& op_state,
00181     const SWP_REG_ASSIGNMENT& reg_assign,
00182     BB *body, bool trace)
00183 {
00184   BB_Remove_All(body);  // remove all OPs
00185 
00186   INT         i;
00187   std::vector<INT> sorted_op;
00188   for (i = 0; i < op_state.size(); i++) {
00189     if (op_state[i].op) 
00190       sorted_op.push_back(i);
00191   }
00192   std::sort(sorted_op.begin(), sorted_op.end(), Order_Op_State_by_Modulo_Cycles(op_state));
00193 
00194   INT ii = op_state.ii;
00195   for (i = 0; i < sorted_op.size(); i++) {
00196     OP *op =  op_state[sorted_op[i]].op;
00197     bool is_noop = op_state[sorted_op[i]].is_noop;
00198     OP_scycle(op) = op_state[sorted_op[i]].cycle;
00199     if (OP_has_predicate(op) &&
00200   TN_is_true_pred(OP_opnd(op, OP_PREDICATE_OPND)) &&
00201   !is_noop) {
00202       INT stage = op_state[sorted_op[i]].cycle / ii;
00203       Set_OP_opnd(op, OP_PREDICATE_OPND, reg_assign.Get_Control_Predicate(stage));
00204     }
00205     BB_Append_Op(body, op);
00206   }
00207 
00208   if (trace) {
00209     for (i = 0; i < sorted_op.size(); i++) {
00210       OP *op =  op_state[sorted_op[i]].op;
00211       fprintf(TFile, "%d: OP %d cycle=%d\n", i, sorted_op[i], op_state[sorted_op[i]].cycle);
00212     }
00213   }
00214 }
00215 
00216 
00217 // Lookup the assigned register TN from the CLASS_REG_PAIR
00218 //
00219 static TN *
00220 Lookup_Register_TN(SWP_REG_ASSIGNMENT::REG2TN_MAP& reg2tn_map, 
00221        CLASS_REG_PAIR                  rp,
00222        TN                             *tn,
00223        bool                            trace)
00224 {
00225   Is_True(CLASS_REG_PAIR_rclass(rp) >= ISA_REGISTER_CLASS_MIN &&
00226     CLASS_REG_PAIR_rclass(rp) <= ISA_REGISTER_CLASS_MAX,
00227     ("Lookup_Register_TN: invalid register class %d\n", CLASS_REG_PAIR_rclass(rp)));
00228     
00229   TN *rtn;
00230   if (reg2tn_map.find(rp) == reg2tn_map.end()) {
00231     // Register TN not allocated --> Generate a new one
00232     rtn = Dup_TN(tn);
00233     Set_TN_class_reg(rtn, rp);
00234     // Set TN is dedicated.  Otherwise GRA will assign registers again.
00235 #ifndef TARG_IA64
00236     Set_TN_is_dedicated(rtn);
00237 #endif
00238     reg2tn_map[rp] = rtn;
00239     if (trace) {
00240       fPrint_TN(TFile, "SWP Allocator: Reference to %s", tn);
00241       fPrint_TN(TFile, " renamed as %s\n", rtn);
00242     }
00243   } else
00244     rtn = reg2tn_map[rp];
00245   return rtn;
00246 }
00247 
00248 
00249 // Determine the rotating register assigned for 'tn', assuming unbounded
00250 // rotating register banks.
00251 // The 'adjustment' is the offset in register numbering, when converting 
00252 // from a physical pseudo-register location of the current reference to
00253 // the corresponding (unbounded) rotating register number.
00254 // 
00255 TN *SWP_REG_ASSIGNMENT::Get_Register_TN(TN *tn, INT adjustment) 
00256 {
00257   Is_True(adjustment >= 0,
00258     ("SWP_REG_ASSIGNMENT: Unexpected negative register-number offset."));
00259 #ifdef TARG_IA64
00260   Is_True(reg_allocation.find(tn) != reg_allocation.end(),
00261     ("SWP_REG_ASSIGNMENT: can't locate TN%d.", TN_number(tn)));
00262 #endif
00263   CLASS_REG_PAIR rp = reg_allocation[tn];
00264   REGISTER r = CLASS_REG_PAIR_reg(rp);
00265   ISA_REGISTER_CLASS c = CLASS_REG_PAIR_rclass(rp);
00266 #ifndef TARG_IA64
00267   c = ISA_REGISTER_CLASS_integer;
00268 #endif
00269     
00270   // Assuming a rotating logical register is numbered the same as the
00271   // corresponding physical pseudo-register location at stage 0, add in
00272   // the offset to get the logical register number:
00273   //
00274   // The correct register computation should be
00275   //   r = ((r + adjustment) % rotating_reg_avail[c]) + rotating_reg_base[c];
00276   // The issue is that we don't know the size of the rotating register file
00277   // at this time, since it is determined based on all loops in a PU, so 
00278   // delay the modulo computation to a postpass (see SWP_Fixup).
00279   //
00280   r = r + adjustment + rotating_reg_base[c];
00281 
00282   // workaround g++ bug:  Set_CLASS_REG_PAIR_reg(rp, r);
00283   Set_CLASS_REG_PAIR(rp, c, r);
00284 
00285   return Lookup_Register_TN(reg2tn_map, rp, tn, Trace());
00286 }
00287 
00288 
00289 TN *SWP_REG_ASSIGNMENT::Get_Control_Predicate(INT stage) const
00290 {
00291   TN *tn = NULL;
00292 #ifdef HAS_ROTATING_REGISTERS
00293   tn = Gen_Predicate_TN();
00294   REGISTER r = 
00295     (REGISTER)(rotating_reg_base[ISA_REGISTER_CLASS_predicate] + 
00296          control_predicate_loc + 
00297          stage);
00298   Set_TN_register(tn, r);
00299   // Set TN is dedicated.  Otherwise GRA will assign registers again.
00300   Set_TN_is_dedicated(tn);
00301   if (Trace()) {
00302     fPrint_TN(TFile, 
00303         "SWP Allocator: Control predicate is %s", tn);
00304     fprintf(TFile, " in stage %d\n", stage);
00305   }
00306 #endif
00307   return tn;
00308 }
00309 
00310 // Determine the register TN assigned for an invariant TN.
00311 //
00312 TN *SWP_REG_ASSIGNMENT::Get_Non_Rotating_Register_TN(TN *tn)
00313 {
00314   CLASS_REG_PAIR rp;
00315   if (reg_allocation.find(tn) != reg_allocation.end())
00316     rp = reg_allocation[tn];
00317   else {
00318     ISA_REGISTER_CLASS rc = TN_register_class(tn);
00319     REGISTER r;
00320   /* Try to get one that doesn't need to be saved. */
00321     r = REGISTER_SET_Choose_Intersection(non_rotating_reg[rc],
00322                                          REGISTER_CLASS_caller_saves(rc));
00323     if (r == REGISTER_UNDEFINED ) r = REGISTER_SET_Choose(non_rotating_reg[rc]);
00324     Is_True(r != REGISTER_UNDEFINED,
00325       ("SWP_REG_ASSIGNMENT: run out of non-rotating registers."));
00326     non_rotating_reg[rc] =  REGISTER_SET_Difference1(non_rotating_reg[rc], r);
00327     Set_CLASS_REG_PAIR(rp, rc, r);  
00328     reg_allocation[tn] = rp;
00329   }
00330     
00331   return Lookup_Register_TN(reg2tn_map, rp, tn, Trace());
00332 }
00333   
00334 
00335 // Return TRUE if all loop invariants can be assigned registers
00336 //
00337 bool SWP_REG_ASSIGNMENT::Enough_Non_Rotating_Registers(TN_SET *non_rotating) const
00338 {
00339   INT reg_needed[ISA_REGISTER_CLASS_MAX+1];
00340   ISA_REGISTER_CLASS i;
00341   FOR_ALL_ISA_REGISTER_CLASS(i) {
00342     reg_needed[i] = 0;
00343   }
00344 
00345   for (TN *tn = TN_SET_Choose(non_rotating);
00346        tn != TN_SET_CHOOSE_FAILURE;
00347        tn = TN_SET_Choose_Next(non_rotating,tn)) {
00348     ISA_REGISTER_CLASS rc = TN_register_class(tn);
00349     if (REGISTER_Has_Rotating_Registers(rc)) 
00350       reg_needed[rc]++;
00351   }
00352 
00353   FOR_ALL_ISA_REGISTER_CLASS(i) {
00354     if (REGISTER_SET_Size(non_rotating_reg[i]) < reg_needed[i])
00355       return false;
00356   }
00357   
00358   return true;
00359 }
00360 
00361   
00362 // Update SWP BB annotation 
00363 //  - the livein and kill REGSET
00364 void SWP_REG_ASSIGNMENT::Update_Annotation(ROTATING_KERNEL_INFO *info)
00365 {
00366   ISA_REGISTER_CLASS i;
00367   FOR_ALL_ISA_REGISTER_CLASS(i) {
00368     // The processing of int register are processed in the fixup
00369     //
00370     REGISTER_SET tmp = REGISTER_CLASS_allocatable(i);
00371     tmp = REGISTER_SET_Difference(tmp, non_rotating_reg[i]);
00372 #ifdef TARG_IA64
00373 //#ifndef KEY
00374     if (i != ISA_REGISTER_CLASS_integer) {
00375       // assume all rotating registers are killed 
00376       // for some reason, rotating reg are not in REGISTER_CLASS_allocatable()?
00377       tmp = REGISTER_SET_Union(tmp,
00378              REGISTER_SET_Range(rotating_reg_base[i],
00379               rotating_reg_base[i] + rotating_reg_avail[i] - 1));
00380     }
00381 #endif
00382 
00383     ROTATING_KERNEL_INFO_live_in(info)[i] = tmp;
00384     ROTATING_KERNEL_INFO_kill(info)[i] = tmp;
00385   }
00386 }
00387 
00388 
00389 // Initialization of SWP_REG_ASSIGNMENT
00390 //
00391 SWP_REG_ASSIGNMENT::SWP_REG_ASSIGNMENT()
00392 {
00393   ISA_REGISTER_CLASS i;
00394   FOR_ALL_ISA_REGISTER_CLASS(i) {
00395 
00396 #ifdef HAS_ROTATING_REGISTERS
00397     rotating_reg_base[i] = REGISTER_First_Rotating_Registers(i);
00398     rotating_reg_avail[i] = REGISTER_Last_Rotating_Registers(i) - 
00399       REGISTER_First_Rotating_Registers(i) + 1;
00400     
00401     // mask out rotating register from non-rotating allocatable set.
00402     non_rotating_reg[i] =
00403       REGISTER_SET_Difference_Range(REGISTER_CLASS_allocatable(i),
00404             rotating_reg_base[i],
00405             rotating_reg_base[i] + rotating_reg_avail[i] - 1);
00406 
00407 #else
00408     non_rotating_reg[i] = REGISTER_CLASS_allocatable(i);
00409 #endif
00410   }
00411 }
00412 
00413 
00414 // Generate a glue copy
00415 //
00416 static void
00417 SWP_Add_Glue(TN *result, TN *opnd, BB *bb, bool append)
00418 {
00419   OPS ops = OPS_EMPTY;
00420   SWP_Exp_COPY(result, opnd, &ops); 
00421   OP *op;
00422   FOR_ALL_OPS_OPs(&ops, op) {
00423     Set_OP_glue(op);
00424   }
00425   if (append)
00426     BB_Append_Ops(bb, &ops);
00427   else
00428     BB_Prepend_Ops(bb, &ops);
00429 }
00430 
00431 
00432 // Replace the TN in the SWP loop by register-assigned TNs.
00433 //  - A TN in SWP are used in different stages, hence have
00434 //    different register allocated.   Since one TN only has
00435 //    one assignment, it is impossible to keep the same TN.
00436 //    
00437 static void
00438 SWP_Rename_TNs(const SWP_OP_vector& op_state, 
00439          SWP_REG_ASSIGNMENT& reg_assign,
00440          BB *head, BB *tail)
00441 {
00442   INT     ii = op_state.ii;
00443   INT     sc = op_state.sc;
00444   TN_SET *non_rotating = op_state.tn_non_rotating;
00445   TN_SET *invariants = op_state.tn_invariants;
00446 
00447   if (SWP_REG_ASSIGNMENT::Trace()) {
00448     fprintf(TFile, "\nSWP Allocator: TN Renaming\n");
00449     fprintf(TFile, "--------------------------\n");
00450   }
00451 
00452   {
00453     for (TN *tn = TN_SET_Choose(invariants);
00454    tn != TN_SET_CHOOSE_FAILURE;
00455    tn = TN_SET_Choose_Next(invariants,tn)) {
00456       if (!TN_is_dedicated(tn)) {
00457   TN *rtn = reg_assign.Get_Non_Rotating_Register_TN(tn);
00458   SWP_Add_Glue(rtn, tn, head, true/*append*/ );
00459       }
00460     }
00461   }
00462 
00463   // Rename SWP body; note that we will not rename the special control
00464   // registers created by SWP_REG_ASSIGNMENT::Get_Control_Predicate, since
00465   // these are marked as "dedicated".
00466   //
00467   for (INT i = 0; i < op_state.size(); i++) {
00468     OP *op = op_state[i].op;
00469     if (op) {
00470       for (INT j = 0; j < OP_opnds(op); j++) {
00471   TN *tn = OP_opnd(op, j);
00472   if (TN_is_register(tn) &&
00473       !TN_is_dedicated(tn)) {
00474     TN *newtn;
00475 #ifdef TARG_IA64
00476     if (!TN_SET_MemberP(non_rotating, tn)) {
00477       INT ofst = reg_assign.Get_Register_Offset(op_state[i].cycle, ii, OP_omega(op,j));
00478       newtn = reg_assign.Get_Register_TN(tn, ofst);
00479     } else 
00480       newtn = reg_assign.Get_Non_Rotating_Register_TN(tn);
00481 #else
00482     if (TN_SET_MemberP(non_rotating, tn)) {
00483       newtn = reg_assign.Get_Non_Rotating_Register_TN(tn);
00484     } else { 
00485       INT ofst = reg_assign.Get_Register_Offset(op_state[i].cycle, ii, OP_omega(op,j));
00486       if (SWP_REG_ASSIGNMENT::Trace()) {
00487         fprintf(TFile, "op %d: reg ofst for operand tn %d = %d (cycle %d, omega %d)\n", i, TN_number(tn), ofst, op_state[i].cycle, OP_omega(op,j));
00488       }
00489       newtn = reg_assign.Get_Register_TN(tn, ofst);
00490     }
00491 #endif
00492     Set_OP_opnd(op, j, newtn);
00493   }
00494       }
00495       for (INT k = 0; k < OP_results(op); k++) {
00496   TN *tn = OP_result(op, k);
00497   if (TN_is_register(tn) &&
00498       !TN_is_dedicated(tn)) {
00499     Is_True(!TN_SET_MemberP(invariants, tn),
00500       ("SWP_Rename_Body: result TN%d cannot be an invariant.", TN_number(tn)));
00501     TN *newtn;
00502 #ifdef TARG_IA64
00503     if (!TN_SET_MemberP(non_rotating, tn)) {
00504       INT ofst = reg_assign.Get_Register_Offset(op_state[i].cycle, ii, 0);
00505       newtn = reg_assign.Get_Register_TN(tn, ofst);
00506     } else
00507       newtn = reg_assign.Get_Non_Rotating_Register_TN(tn);
00508 #else
00509     if (TN_SET_MemberP(non_rotating, tn)) {
00510       newtn = reg_assign.Get_Non_Rotating_Register_TN(tn);
00511     } else {
00512       INT ofst = reg_assign.Get_Register_Offset(op_state[i].cycle, ii, 0);
00513       if (SWP_REG_ASSIGNMENT::Trace()) {
00514         fprintf(TFile, "op %d: reg ofst for result tn %d = %d (cycle %d)\n", i, TN_number(tn), ofst, op_state[i].cycle);
00515       }
00516       newtn = reg_assign.Get_Register_TN(tn, ofst);
00517     }
00518 #endif // TARG_IA64
00519     Set_OP_result(op, k, newtn);
00520   }
00521       }
00522     }
00523   }
00524 
00525   CG_LOOP_BACKPATCH *bp;
00526   // Generate copies for prolog-backpatches.
00527   for (bp = CG_LOOP_Backpatch_First(head, NULL); bp; bp = CG_LOOP_Backpatch_Next(bp)) {
00528     TN *body_tn = CG_LOOP_BACKPATCH_body_tn(bp);
00529     TN *tn = CG_LOOP_BACKPATCH_non_body_tn(bp);
00530     TN *newtn;
00531     if (!TN_is_dedicated(body_tn)) {
00532       if (!TN_SET_MemberP(non_rotating, body_tn)) {
00533   INT omega = CG_LOOP_BACKPATCH_omega(bp);
00534   INT ofst = reg_assign.Get_Livein_Register_Offset(omega);
00535   newtn = reg_assign.Get_Register_TN(body_tn, ofst);
00536       } else
00537   newtn = reg_assign.Get_Non_Rotating_Register_TN(body_tn);
00538       SWP_Add_Glue(newtn, tn, head, true/*append*/);
00539     }
00540   }
00541 
00542   // Generate copies for epilog-backpatches.
00543   for (bp = CG_LOOP_Backpatch_First(tail, NULL); bp; bp = CG_LOOP_Backpatch_Next(bp)) {
00544     TN *body_tn = CG_LOOP_BACKPATCH_body_tn(bp);
00545     TN *tn = CG_LOOP_BACKPATCH_non_body_tn(bp); 
00546     TN *newtn;
00547     if (!TN_is_dedicated(body_tn)) {
00548       if (!TN_SET_MemberP(non_rotating, body_tn)) {
00549   INT omega = CG_LOOP_BACKPATCH_omega(bp);
00550   INT ofst = reg_assign.Get_Liveout_Register_Offset(sc, omega);
00551 #ifndef TARG_IA64
00552   if (SWP_REG_ASSIGNMENT::Trace()) {
00553     fprintf(TFile, "reg ofst for epilog tn %d = %d\n", TN_number(body_tn), ofst);
00554   }
00555 #endif
00556   newtn = reg_assign.Get_Register_TN(body_tn, ofst);
00557       } else
00558   newtn = reg_assign.Get_Non_Rotating_Register_TN(body_tn);
00559       SWP_Add_Glue(tn, newtn, tail, false/*prepend*/);
00560     }
00561   }
00562 } // SWP_Rename_TNs
00563 
00564 
00565 static TN*
00566 Fixup_Rotating_Register_TN(TN *tn, const SWP_FIXUP &fixup, bool trace)
00567 {
00568   TN *rtn = tn;
00569 
00570 #ifdef HAS_ROTATING_REGISTERS
00571   // The allocation of rotating registers thus far has been unbounded and
00572   // based at the appropriate rotating_reg_base.  Now we know how many 
00573   // registers are assigned to each rotating register bank, and we can
00574   // adjust all registers such that they are in-sequence within the
00575   // rotating register bank.  We also adjust predicate registers such 
00576   // that the special control predicate is located in the n first logical
00577   // registers (n==stages).
00578   //
00579   const ISA_REGISTER_CLASS rc = TN_register_class(tn);
00580 
00581   REGISTER       r = TN_register(tn);
00582 
00583   const REGISTER old_r = r;
00584   if (REGISTER_Has_Rotating_Registers(rc)) {
00585 
00586     // Invariants will have been allocated at register numbers smaller than
00587     // the rotating register bank.  The following ignores such registers in
00588     // the fixup algorithm.
00589     //
00590     // WARNING:  REGISTER is an unsigned type. Some of the arithmetic
00591     // below (in the predicate case) may produce negative intermediate
00592     // results.  Testing them successfully requires explicit
00593     // conversions to (int).
00594     //
00595     if (r >= REGISTER_First_Rotating_Registers(rc)) {
00596       if (rc == ISA_REGISTER_CLASS_predicate) {
00597 #ifdef TARG_IA64        
00598         //Bug fix:
00599         //The order of calculate must be guarded!
00600         
00601         if ( ((int)(r - fixup.control_loc)) < 0 ) {
00602           r += REGISTER_Last_Rotating_Registers(rc) - 
00603             REGISTER_First_Rotating_Registers(rc) + 1;
00604           r -= fixup.control_loc;
00605         } else {
00606     r -= fixup.control_loc;  // Control lifetime uses first rotating regs
00607     if (r < REGISTER_First_Rotating_Registers(rc))
00608       r += REGISTER_Last_Rotating_Registers(rc) - 
00609               REGISTER_First_Rotating_Registers(rc) + 1;
00610     else if (r > REGISTER_Last_Rotating_Registers(rc))
00611       r -= REGISTER_Last_Rotating_Registers(rc) - 
00612               REGISTER_First_Rotating_Registers(rc) + 1;
00613         }
00614 #else
00615   r -= fixup.control_loc;  // Control lifetime uses first rotating regs
00616   if ((int)r < (int)REGISTER_First_Rotating_Registers(rc))
00617     r += REGISTER_Last_Rotating_Registers(rc) - 
00618       REGISTER_First_Rotating_Registers(rc) + 1;
00619   else if ((int)r > (int)REGISTER_Last_Rotating_Registers(rc))
00620     r -= REGISTER_Last_Rotating_Registers(rc) - 
00621       REGISTER_First_Rotating_Registers(rc) + 1;
00622       }
00623       else if (rc == ISA_REGISTER_CLASS_integer) {
00624   if (r >= REGISTER_First_Rotating_Registers(rc) +
00625       REGISTER_Number_Stacked_Rotating(rc)) {
00626     r -= REGISTER_Number_Stacked_Rotating(rc);
00627   }
00628 #endif // TARG_IA64
00629       }
00630       else if (rc == ISA_REGISTER_CLASS_integer) {
00631   if (r >= REGISTER_First_Rotating_Registers(rc) +
00632       REGISTER_Number_Stacked_Rotating(rc)) {
00633     r -= REGISTER_Number_Stacked_Rotating(rc);
00634   }
00635       }
00636       else if (r > REGISTER_Last_Rotating_Registers(rc)) {
00637   r -= REGISTER_Last_Rotating_Registers(rc) - 
00638     REGISTER_First_Rotating_Registers(rc) + 1;
00639       }
00640 
00641 #ifdef TARG_IA64
00642       Is_True(r <= REGISTER_Last_Rotating_Registers(rc) &&
00643         r >= REGISTER_First_Rotating_Registers(rc),
00644         ("cannot wrap around twice."));
00645 #else
00646       Is_True(r <= REGISTER_Last_Rotating_Registers(rc) &&
00647         r >= REGISTER_First_Rotating_Registers(rc),
00648       ("%d (class %d:%d:%d:%d) => %d: cannot wrap around twice.",
00649        old_r, rc,
00650        REGISTER_First_Rotating_Registers(rc),
00651        REGISTER_Last_Rotating_Registers(rc),
00652        fixup.control_loc,
00653        r));
00654 #endif
00655     }
00656   }
00657   if (old_r != r) 
00658     Set_TN_register(tn, r);
00659 
00660   if (trace && old_r != r) {
00661     fprintf (TFile, "Rotated register %s;", REGISTER_name(rc, old_r));
00662     fPrint_TN(TFile, " result is %s\n", tn);
00663   }
00664 #endif // TARG_IA64
00665   return rtn;
00666 } // Fixup_Rotating_Register_TN
00667 
00668 
00669 static void 
00670 SWP_Fixup_Rotating_Registers(BB              *head, 
00671            BB              *body, 
00672            BB              *tail,
00673            const SWP_FIXUP &fixup,
00674            bool             trace)
00675 {
00676   CXX_MEM_POOL local_pool("fixup local pool", FALSE);
00677   TN_SET *fixed_tn = TN_SET_Create_Empty(Last_TN + 1, local_pool());
00678 
00679   OP *op;
00680   FOR_ALL_BB_OPs(body, op) {
00681     for (INT j = 0; j < OP_opnds(op); j++) {
00682       TN *tn = OP_opnd(op, j);
00683       if (TN_is_register(tn) && !TN_SET_MemberP(fixed_tn, tn)) {
00684   TN *new_tn = Fixup_Rotating_Register_TN(tn, fixup, trace);
00685   Set_OP_opnd(op,j, new_tn);
00686   fixed_tn = TN_SET_Union1D(fixed_tn, new_tn, local_pool());
00687       }
00688     }
00689     for (INT k = 0; k < OP_results(op); k++) {
00690       TN *tn = OP_result(op, k);
00691       if (TN_is_register(tn) && !TN_SET_MemberP(fixed_tn, tn)) {
00692   TN *new_tn = Fixup_Rotating_Register_TN(tn, fixup, trace);
00693   Set_OP_result(op, k, new_tn);
00694   fixed_tn = TN_SET_Union1D(fixed_tn, new_tn, local_pool());
00695       }
00696     }
00697   }
00698   FOR_ALL_BB_OPs(head, op) {
00699     if (OP_glue(op)) {
00700       for (INT k = 0; k < OP_results(op); k++) {
00701   TN *tn = OP_result(op, k);
00702   if (TN_is_register(tn) && !TN_SET_MemberP(fixed_tn, tn)) {
00703     TN *new_tn = Fixup_Rotating_Register_TN(tn, fixup, trace);  
00704     Set_OP_result(op, k, new_tn);
00705     fixed_tn = TN_SET_Union1D(fixed_tn, new_tn, local_pool());
00706   }
00707       }
00708     }
00709   }
00710   FOR_ALL_BB_OPs(tail, op) {
00711     if (OP_glue(op)) {
00712       for (INT j = 0; j < OP_opnds(op); j++) {
00713   TN *tn = OP_opnd(op, j);
00714   if (TN_is_register(tn) && !TN_SET_MemberP(fixed_tn, tn)) {
00715     TN *new_tn = Fixup_Rotating_Register_TN(tn, fixup, trace);
00716     Set_OP_opnd(op, j, new_tn);
00717     fixed_tn = TN_SET_Union1D(fixed_tn, new_tn, local_pool());
00718   }
00719       }
00720     }
00721   }
00722 } // SWP_Fixup_Rotating_Registers
00723 
00724 
00725 void 
00726 SWP_Emit(SWP_OP_vector& op_state,
00727    SWP_REG_ASSIGNMENT& reg_assign,
00728    TN *trip_count_tn,
00729    BB *head, BB *body, BB *tail, 
00730    bool is_doloop, bool trace)
00731 {
00732   if (trace) {
00733     CG_LOOP_Backpatch_Trace(head, NULL);
00734     CG_LOOP_Backpatch_Trace(tail, NULL);
00735   }
00736 
00737   // Create a SWP REGION
00738   RID *r = RID_Create(New_Region_Id(), 0, NULL);
00739   RID_has_reg_alloc_Set(r);
00740   RID_level(r) = RL_CG;
00741   RID_type(r) = RID_TYPE_swp;
00742   RID_bounds_exist(r) = REGION_BOUND_UNKNOWN;
00743   RID_has_return(r) = REGION_NO_RETURN;
00744   RID_num_exits(r) = 1;
00745   RID_is_glue_code(r) = FALSE;        
00746   RID *parent = BB_rid(body);
00747   RID_parent(r) = parent;
00748   RID_cginfo(r) = NULL; /* ?? this should have a value */
00749   if ( parent ) RID_Add_kid(r, parent);
00750 
00751   BB_rid(body) = r;
00752   Set_BB_reg_alloc(body);
00753   Set_BB_scheduled(body);
00754   
00755   // Rearrange OPs in modulo order
00756   SWP_Reorder_OPs(op_state, reg_assign, body, trace);
00757 
00758   // Generate br.ctop
00759   OPS prolog_ops = OPS_EMPTY;
00760   OPS body_ops = OPS_EMPTY;
00761   OPS epilog_ops = OPS_EMPTY;
00762 
00763   INT32 prolog_epilog_count = op_state.sc;
00764   if (!is_doloop && op_state.loop_one_more_time)
00765     prolog_epilog_count--;
00766 
00767   SWP_Loop_Init_Fini(is_doloop, prolog_epilog_count, &prolog_ops, &body_ops, &epilog_ops);
00768 
00769   BB_Append_Ops(head, &prolog_ops);
00770   BB_Append_Ops(body, &body_ops);  
00771   BB_Append_Ops(tail, &epilog_ops);
00772 
00773   Set_BB_mod_pred_rotating_registers(head);
00774   Set_BB_mod_rotating_registers(tail);
00775 
00776   // Rename body, backpatches and
00777   // generate glue copies for invariants
00778   SWP_Rename_TNs(op_state, reg_assign, head, tail);
00779 
00780   {
00781     // Generate SWP ROTATING KERNEL Annotation
00782     ROTATING_KERNEL_INFO *info = TYPE_PU_ALLOC(ROTATING_KERNEL_INFO);
00783     bzero(info, sizeof(ROTATING_KERNEL_INFO));
00784     reg_assign.Update_Annotation(info);
00785     
00786   // Regenerate SWP resource statistics
00787     TI_RES_COUNT *res_counts = TI_RES_COUNT_Alloc(MEM_pu_pool_ptr);
00788     // Sum resources from each OP's resource usage.
00789     OP *op;
00790     for (INT i = 0; i < op_state.size(); i++) {
00791       OP *op = op_state[i].op;
00792       if (op && !op_state[i].is_noop)
00793   TI_RES_COUNT_Add_Op_Resources(res_counts, OP_code(op));
00794     }
00795 
00796     // Save SWP statistics
00797     ROTATING_KERNEL_INFO_succeeded(info) = TRUE;
00798     ROTATING_KERNEL_INFO_ii(info) = op_state.ii;
00799     ROTATING_KERNEL_INFO_stage_count(info) = op_state.sc;
00800     ROTATING_KERNEL_INFO_min_ii(info) = op_state.min_ii;    
00801     ROTATING_KERNEL_INFO_res_min_ii(info) = op_state.res_min_ii;
00802     ROTATING_KERNEL_INFO_rec_min_ii(info) = op_state.rec_min_ii;
00803     ROTATING_KERNEL_INFO_sched_len(info) = op_state.sl;
00804     ROTATING_KERNEL_INFO_min_sched_len(info) = op_state.min_sl;
00805     ROTATING_KERNEL_INFO_res_counts(info) = res_counts;
00806 
00807     FOR_ALL_BB_OPs(head, op) {
00808       if (OP_glue(op)) {
00809   for (INT k = 0; k < OP_results(op); k++) {
00810     TN *tn = OP_result(op, k);
00811     if (!TN_is_const_reg(tn))
00812       ROTATING_KERNEL_INFO_copyin(info).push_back(tn);
00813   }
00814       }
00815     }
00816     FOR_ALL_BB_OPs(tail, op) {
00817       if (OP_glue(op)) {
00818   for (INT j = 0; j < OP_opnds(op); j++) {
00819     TN *tn = OP_opnd(op, j);
00820     if (!TN_is_const_reg(tn))
00821       ROTATING_KERNEL_INFO_copyout(info).push_back(tn);
00822   }
00823       }
00824     }
00825 #ifdef TARG_IA64
00826     REGISTER_SET all_non_rotating[ISA_REGISTER_CLASS_MAX+1];
00827     ISA_REGISTER_CLASS i;
00828     FOR_ALL_ISA_REGISTER_CLASS(i) {
00829       all_non_rotating[i] = REGISTER_SET_Difference_Range(REGISTER_CLASS_allocatable(i),
00830                                                           REGISTER_First_Rotating_Registers(i),
00831                                                           REGISTER_Last_Rotating_Registers(i));
00832     }
00833     FOR_ALL_BB_OPs(body, op) {
00834       for (INT k = 0; k < OP_results(op); k++) {
00835         TN *tn = OP_result(op, k);
00836         if (!TN_is_const_reg(tn) && TN_register(tn) != REGISTER_UNDEFINED){
00837           ISA_REGISTER_CLASS rc = TN_register_class(tn);      
00838           REGISTER r = TN_register(tn);
00839           if(r <= REGISTER_MAX //OSP_43
00840               && REGISTER_SET_MemberP(all_non_rotating[rc],r)){
00841             ROTATING_KERNEL_INFO_localdef(info).push_back(tn);
00842           }
00843         }
00844       }
00845     }
00846 #endif
00847     BB_Add_Annotation(body, ANNOT_ROTATING_KERNEL, (void *)info);
00848   }
00849 
00850   if (trace) {
00851     Print_BB(head);
00852     Print_BB(body);
00853     Print_BB(tail);
00854   }
00855 
00856   if (SWP_Options.Enable_BRP) Gen_SWP_Branch_Predict(body, head, tail);
00857 }
00858 
00859 
00860 // Postpass SWP Fixup 
00861 //  - it is run after all SWP loop has been processed.
00862 //  - called from Perform_Loop_Optimization
00863 //
00864 void SWP_Fixup(SWP_FIXUP& fixup)
00865 {
00866   BB *prolog = fixup.prolog;
00867   BB *body = fixup.body;
00868   BB *epilog = fixup.epilog;
00869 
00870   SWP_Fixup_Rotating_Registers(prolog, body, epilog, fixup, 
00871              SWP_REG_ASSIGNMENT::Trace());
00872 
00873 #ifdef HAS_ROTATING_REGISTERS
00874   // Update the requirement of the configurable int rotating registers
00875   ANNOTATION *annot = ANNOT_Get(BB_annotations(body), ANNOT_ROTATING_KERNEL);
00876   ROTATING_KERNEL_INFO *info = ANNOT_rotating_kernel(annot);
00877   ISA_REGISTER_CLASS rc = ISA_REGISTER_CLASS_integer;
00878   const REGISTER first_rotating_reg =  REGISTER_First_Rotating_Registers(rc);
00879   const REGISTER num_rotating_reg = REGISTER_Number_Stacked_Rotating(rc);
00880 
00881   BOOL trace = Get_Trace(TP_SWPIPE, 2);
00882 
00883   for (INT i = 0; i < num_rotating_reg; i++) {
00884     REGISTER reg = i + first_rotating_reg;
00885     ROTATING_KERNEL_INFO_live_in(info)[rc] =
00886       REGISTER_SET_Union1(ROTATING_KERNEL_INFO_live_in(info)[rc], reg);
00887     ROTATING_KERNEL_INFO_kill(info)[rc] = 
00888       REGISTER_SET_Union1(ROTATING_KERNEL_INFO_kill(info)[rc], reg);
00889   }
00890 
00891   if (trace) {
00892     fprintf(TFile, "Reminder: REGISTER SET number differs from real register by 1.\n");
00893     FOR_ALL_ISA_REGISTER_CLASS(rc) {
00894       fprintf(TFile, "SWP annotation: register class %d", rc);
00895       fprintf(TFile, "\nlivein: ");
00896       REGISTER_SET_Print(ROTATING_KERNEL_INFO_live_in(info)[rc], TFile);
00897       fprintf(TFile, "\nkill:   ");
00898       REGISTER_SET_Print(ROTATING_KERNEL_INFO_kill(info)[rc], TFile);
00899       fprintf(TFile,"\n");
00900     }
00901   }
00902 
00903 #ifdef Is_True_On
00904   // Verify that p63 is not modified in the last cycle
00905   {
00906     OP *op;
00907     INT ii = ROTATING_KERNEL_INFO_ii(info);
00908     OP *br = BB_branch_op(body);
00909     INT br_cycle = OP_scycle(br) % ii;
00910     FOR_ALL_BB_OPs(body, op) {
00911       if (OP_scycle(op) % ii == br_cycle) {
00912   for (INT k = 0; k < OP_results(op); k++) {
00913     TN *tn = OP_result(op, k);
00914     if (TN_is_register(tn)) {
00915       if (TN_register_class(tn) == ISA_REGISTER_CLASS_predicate &&
00916     TN_register(tn) == 64) {
00917         Is_True(FALSE, ("SWP_Fixup: p63 is modified."));
00918       }
00919     }
00920   }
00921       }
00922     }
00923   }
00924 #endif
00925 
00926 #endif
00927 }
00928