00001 /* 00002 00003 Copyright (C) 2000, 2001 Silicon Graphics, Inc. All Rights Reserved. 00004 00005 This program is free software; you can redistribute it and/or modify it 00006 under the terms of version 2 of the GNU General Public License as 00007 published by the Free Software Foundation. 00008 00009 This program is distributed in the hope that it would be useful, but 00010 WITHOUT ANY WARRANTY; without even the implied warranty of 00011 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. 00012 00013 Further, this software is distributed without any warranty that it is 00014 free of the rightful claim of any third person regarding infringement 00015 or the like. Any license provided herein, whether implied or 00016 otherwise, applies only to this software file. Patent licenses, if 00017 any, provided herein do not apply to combinations of this program with 00018 other software, or any other product whatsoever. 00019 00020 You should have received a copy of the GNU General Public License along 00021 with this program; if not, write the Free Software Foundation, Inc., 59 00022 Temple Place - Suite 330, Boston MA 02111-1307, USA. 00023 00024 Contact information: Silicon Graphics, Inc., 1600 Amphitheatre Pky, 00025 Mountain View, CA 94043, or: 00026 00027 http://www.sgi.com 00028 00029 For further information regarding this notice, see: 00030 00031 http://oss.sgi.com/projects/GenInfo/NoticeExplan 00032 00033 */ 00034 00035 00036 //-*-c++-*- 00037 /* ==================================================================== 00038 * ==================================================================== 00039 * 00040 * Module: opt_alias_rule.h 00041 * $Revision$ 00042 * $Date$ 00043 * $Author$ 00044 * $Source$ 00045 * 00046 * Revision history: 00047 * 04-APR-95 lo - Split from opt_alias.h 00048 * 00049 * Description: 00050 * 00051 * ==================================================================== 00052 * ==================================================================== 00053 */ 00054 00055 #ifndef opt_alias_rule_INCLUDED 00056 #define opt_alias_rule_INCLUDED "opt_alias_rule.h" 00057 #ifdef _KEEP_RCS_ID 00058 static char *opt_alias_rulercs_id = opt_alias_rule_INCLUDED"$Revision$"; 00059 #endif /* _KEEP_RCS_ID */ 00060 00061 00062 /* ======================================================================== 00063 * 00064 * ALIAS RULE 00065 * ---------- 00066 * This package implements the rules used in alias analysis. 00067 * The set of rules used is run-time configurable by changing 00068 * the ALIAS CONTEXT. The rules are managed by the ALIAS MANAGER, 00069 * which is the interface to LNO/CG/IPA. 00070 * 00071 * Overview 00072 * -------- 00073 * The alias analysis is implemented as a rule-based system. 00074 * Each alias rule is implemented by a function that returns 00075 * TRUE or FALSE. However, in one case, a function returns 00076 * NO_READ_NO_WRITE, READ, WRITE, and READ_AND_WRITE in order 00077 * to return better information. 00078 * 00079 * The function returns FALSE if it determines that two memory 00080 * operations are not aliased. It returns TRUE if 1) the rule 00081 * determines that the memory operations are aliased; 2) the 00082 * rule cannot draw any conclusions. 00083 * 00084 * The rules examine a data structure called POINTS_TO that 00085 * sumarize the alias information about memory operations. 00086 * Each memory operation have its own POINTS_TO information. 00087 * 00088 * Given a set of rules, two memory operation are not aliased if 00089 * ANY of the rules returns FALSE. 00090 * 00091 * The set of rules used for alias analysis is determined by 00092 * the ALIAS CONTEXT. The context is encoded in a 64-bit integer. 00093 * Each rule is assigned a bit in the integer. If the rule can 00094 * be used for alias analysis, the bit corresponding to its 00095 * position is set to 1. The default ALIAS CONTEXT is 00096 * initialized in the ALIAS MANAGER constructor by examining 00097 * various command line options. e.g., -OPT:alias=typed ... 00098 * 00099 * The ALIAS CONTEXT can also be manipulated in the midst of 00100 * compilation by the use Get_context()/Set_context() interface. 00101 * This interface is particularly useful to carry out alias 00102 * analysis for inlined procedures. For example, 00103 * procedure A inlines procedure B. Procedure A is written C 00104 * and procedure B is written in Fortran. After inlining, 00105 * we still want to apply Fortran alias rules to the regions belonging 00106 * to B. During inlining, IPA would call Get_context() to 00107 * obtain the alias context of B and use a pragma to annotate 00108 * the alias context to the expanded section of B inside A. 00109 * During alias analysis, the default alias context (of B) is 00110 * used. When the module starts processing of the inlined IR, 00111 * the module should read the pragma and use Set_context() to 00112 * reconfigure the alias rule set. Therefore, the Fortran alias 00113 * rules can be applied to the inlined region. 00114 * 00115 * Similarly, if the procedure A is compiled with -OPT:alias=restrict, 00116 * and procedure B is compiled with -OPT:alias=typed. Even after inlining 00117 * B to A, B will still be optimized with the -OPT:alias=typed. 00118 * 00119 * WARNING: The alias context is bound to the control flow structure! 00120 * If a memory operation is moved out of region by code motion, then 00121 * the alias context of the complement is used. The implication is 00122 * 1) if a memory operation is moved from a region of aggressive alias rules 00123 * to a lesser one, performance may suffer. 00124 * 2) if a memory operation is moved from a region of less aggressive rules 00125 * to a more aggressive one, incorrect results may happen. 00126 * Therefore, we strongly discourage inlining routines of different 00127 * alias levels together. 00128 * 00129 * 00130 * Exported functions 00131 * ------------------ 00132 * 00133 * USE the interface defined here. DO NOT CALL the alias rules 00134 * directly because the implementation should change without notification. 00135 * 00136 * ALIAS_CONTEXT Get_context(void) 00137 * returns the current alias context. 00138 * 00139 * void Set_context(ALIAS_CONTEXT new_rule_set) 00140 * Set the current alias context to new_rule_set. 00141 * 00142 * BOOL Rule_enabled(ALIAS_CONTEXT rule) 00143 * returns TRUE if the rule specified is allowed in the current 00144 * context. 00145 * 00146 * 00147 * These following function called by the ALIAS MANAGER and the 00148 * computation of SSA form. The Aliased_Memop.... function 00149 * examines the context and applies the enabled rules. 00150 * 00151 * The rules are deliberately separated into two groups: one that 00152 * is related to user-declaration, and the other to analyses. 00153 * The user-declaration group is evaluated only once during SSA 00154 * computations. The analyses group is evalutated twice during SSA 00155 * computations. 00156 * 00157 * The flow is 00158 * 1) perform context-free alias analysis 00159 * 2) apply both declaration group and analyses group rule set. 00160 * 3) build SSA form 00161 * 4) perform context-sensitive alias analysis using the use-def 00162 * chain provided by SSA. 00163 * 5) re-apply analyses group rules because of the extra information 00164 * generated by context-sensitive analysis. 00165 * 00166 * 00167 * BOOL Aliased_Memop_By_Analysis(const POINTS_TO *, const POINTS_TO *) 00168 * Use the rules that based on flow-sensitive POINTS_TO analysis. 00169 * 00170 * BOOL Aliased_Memop_By_Declaration(cosnt POINTS_TO *, const POINTS_TO *, TY *, TY*) 00171 * Use the rules that based on language declarations. 00172 * 00173 * BOOL Aliased_Memop_By_Offset(cosnt POINTS_TO *, const POINTS_TO) 00174 * Use only the offset rule because we know the base is the same. 00175 * 00176 * BOOL Aliased_Memop(const POINTS_TO *, const POINTS_TO *) 00177 * returns TRUE if two POINTS_TO are aliased. 00178 * Invoke both Aliased_Memop_By_Analysis() and Aliased_Memop_By_Declaration(). 00179 * 00180 * BOOL Aliased_Memop(const POINTS_TO *, const POINTS_TO *, TY *, TY *) 00181 * Same as Aliased_Memop(), but use the high level type information 00182 * passed as parameter. 00183 * Invoke both Aliased_Memop_By_Analysis() and Aliased_Memop_By_Declaration(). 00184 * 00185 * BOOL Aliased_with_Call(ST *, const POINTS_TO *) 00186 * Returns TRUE if the POINTS_TO is read/modified by the procedure call. 00187 * 00188 * BOOL Aliased_with_Region( ... ) 00189 * // to be implemented 00190 * 00191 * BOOL Same_location(const WN *, const WN *, const POINTS_TO *, const POINTS_TO *) 00192 * Two memory operations points to exactly the same location. 00193 * 00194 * 00195 * ALIAS RULES 00196 * ----------- 00197 * 00198 * Rules applied to all languages. 00199 * 00200 * A.1: (Base rule) 00201 * Two memory operations are not aliased if their base is different. 00202 * See opt_alias_analysis.h for the definition of Same_base() 00203 * and Different_base(). 00204 * 00205 * A.2: (Ofst rule) 00206 * Two memory operations are not aliased if their base is the same, 00207 * and their memory ranges defined by the offset and size fields 00208 * does not overlap. 00209 * 00210 * A.3: (Nest_rule) 00211 * Implementation not finished. Supposed to deal with up-level references 00212 * and nested procedures ... 00213 * 00214 * A.4: (Indirect rule) 00215 * Indirect memory access cannot access variables that are not address 00216 * taken and saved. See opt_alias_analysis.h for the definition 00217 * of addr_taken_and_saved. 00218 * 00219 * A.5: (Call_rule) 00220 * A procedure call does not affect local variables that are not 00221 * addr_taken_and_saved. 00222 * 00223 * A.6: (Qual_rule) 00224 * Use the qualified attributes. 00225 * WARNING: The Qual is physically distributed in different subroutines. 00226 * 00227 * A.6.1: (pure funcition rule) 00228 * Pure function is not aliased to any 00229 * memory operations. (See ST_pu_is_pure() in stab.h.) 00230 * 00231 * A.6.2: (no side-effect function rule) 00232 * No side-effect does not modify the value returned by any memory 00233 * operations, but it might read the content of some memory. 00234 * (See ST_pu_no_se(st) in stab.h.) 00235 * 00236 * A.6.3: (const object) 00237 * A const object is not modified. 00238 * 00239 * A.6.4: (unique pointer) 00240 * If a indirect memory operation has the unique_pt attribute, 00241 * then the only memory operation that can alias to it is itself. 00242 * 00243 * 00244 * 00245 * C Rules 00246 * 00247 * C.1: (ANSI Rules) 00248 * 00249 * An object shall have its stored value accessed only by an lvalue that 00250 * has one of the following types: 00251 * *) the declared type of the object, 00252 * *) a qualified version of the declared type of the object, 00253 * *) a type that is signed or unsigned type corresponding to the declared type 00254 * of the object, 00255 * *) a type that is signed or unisgined type corresponding to a 00256 * qualified version of the declared type of the object, 00257 * *) an aggregrate or union type that includes one of the aforementioned types 00258 * among its members (including, recursively, a member of a subaggregate 00259 * or contained union), 00260 * *) a character type, or 00261 * *) a void type. 00262 * 00263 * Use the Ragnarok interpretation here. Objects are aliased if 00264 * their base types (MTYPES), after stripping off the qualifiers and 00265 * signed-ness, are equal. See ANSI C 3.3 and 3.2.2.3. 00266 * 00267 * C.2: (C Qualifier Rule) 00268 * 00269 * C.2.1: (restricted pointer) 00270 * If both memory operations are restricted pointer dereference, 00271 * they are not aliased if their based pointer are different. 00272 * 00273 * 00274 * C++ Rules 00275 * Not determined. 00276 * 00277 * 00278 * Fortran Rules 00279 * 00280 * F.1: (Fortran Parameter rule) 00281 * Fortran parameters are not aliased to anything except itself. 00282 * 00283 * F.2: (Fortran Call rule) 00284 * Fortran actual parameters can be modified. Fortran calls have 00285 * no side effect on address taken variables. 00286 * 00287 * F.3: (Fortran pointer rule) 00288 * // not implemented 00289 * Fortran pointer-based variable cannot itself be a pointer. 00290 * 00291 * F.4: (Fortran pointer restriction) 00292 * // not implemented 00293 * These restrictions are enforced by the frontend. 00294 * A pointer-based variable cannot be used as a dummy argument or in 00295 * COMMON, EQUIVALENCE, DATA, or NAMELIST statements. 00296 * The dimension expressions for pointer-based variables must be constant 00297 * expressions in main programs. In subroutines and functions, the same rules 00298 * apply for pointer-based variables as for dummy arguments. The expression 00299 * can contain dummy arguments and variables in COMMON statements. Any 00300 * variable in the expressions must be defined with an integer value at the 00301 * time the subroutine or function is called. 00302 * 00303 * 00304 * Old Rules 00305 * 00306 * O.1: (Ragnarok unnamed) 00307 * Direct memory operations are not aliased to indirect memory operations. 00308 * 00309 * O.2: (Ragnarok restricted) 00310 * Memory operations are not aliased if their based pointer 00311 * are different. 00312 * 00313 * 00314 * ======================================================================== 00315 */ 00316 00317 00318 00319 class OPT_STAB; 00320 class AUX_STAB_ENTRY; 00321 class POINTS_TO; 00322 class ALIAS_KIND; 00323 class WN; 00324 typedef struct bs BS; 00325 00326 #include "optimizer.h" 00327 00328 // Assign a bitpos to each rule. 00329 // _context in ALIAS_RULE control which rules can be applied 00330 // 00331 enum { 00332 // Rules common to all languages 00333 BASE_RULE = 0x1, 00334 OFST_RULE = 0x2, 00335 NEST_RULE = 0x4, 00336 INDR_RULE = 0x8, 00337 CALL_RULE = 0x10, 00338 QUAL_RULE = 0x20, 00339 ATTR_RULE = 0x40, 00340 CLAS_RULE = 0x80, 00341 IP_CLAS_RULE = 0x80000000, 00342 ALL_COMMON_RULES = 0x800000ff, 00343 DEFAULT_COMMON_RULES = 0x800000ff, 00344 00345 // C Rules 00346 C_ANSI_RULE = 0x100, 00347 C_QUAL_RULE = 0x200, 00348 C_RESTRICT_CONST_RULE = 0x400, 00349 C_STRONGLY_TYPED_RULE = 0x800, 00350 ALL_C_RULES = 0x0f00, 00351 DEFAULT_C_RULES = 0x0200, 00352 00353 // C++ Rules 00354 ALL_CXX_RULES = 0xf000, 00355 DEFAULT_CXX_RULES = 0xf000, 00356 00357 // Fortran Rules 00358 F_PARM_RULE = 0x10000, 00359 F_CALL_RULE = 0x20000, 00360 F_CRAY_POINTER_RULE = 0x40000, 00361 ALL_F_RULES = 0x0f0000, 00362 DEFAULT_F_RULES = 0x020000, 00363 00364 // F90 Rules 00365 F90_TARGET_RULE = 0x100000, 00366 ALL_F90_RULES = 0xf00000, 00367 DEFAULT_F90_RULES = 0xf00000, 00368 00369 // Analysis Rules 00370 FFA_RULE = 0x1000000, 00371 FSA_RULE = 0x2000000, 00372 ALL_ANALYSIS_RULES = 0x7000000, 00373 DEFAULT_ANALYSIS_RULES = 0x7000000, 00374 00375 // Compatiability Rules 00376 IBM_DISJOINT_RULE = 0x08000000, 00377 RAG_RESTRICTED_RULE = 0x10000000, 00378 RAG_UNNAMED_RULE = 0x20000000, 00379 RAG_PARMS_RULE = 0x40000000, 00380 ALL_COMPATIABILITY_RULES = 0x78000000, 00381 DEFAULT_COMPATIABILITY_RULES = 0, 00382 }; 00383 00384 00385 class ALIAS_RULE { 00386 00387 ALIAS_CONTEXT _context; // control which rules can be applied 00388 00389 private: 00390 00391 // Obtain the basic type from TY 00392 INT32 Get_stripped_mtype(TY_IDX ty) const; 00393 00394 // return TRUE iff 00395 // o. ty1 == ty2, or 00396 // o. ty1 is of aggregate and there exist a filed <f> of ty2 00397 // where Ty1_Include_Ty2(ty1, type-of-<f>) is satisfied. 00398 // 00399 // this is helper function of Aliased_This_Ptr_Rule (). 00400 BOOL Ty1_Include_Ty2 (TY_IDX ty1, TY_IDX ty2) const; 00401 00402 // This routine are used by alias analysis internally. 00403 // Each function implements one of the alias rules. 00404 // See doc/Mongoose/alias-analysis-design for more details. 00405 00406 BOOL Aliased_Base_Rule(const POINTS_TO *, const POINTS_TO *) const; 00407 // BOOL Aliased_Ofst_Rule(const POINTS_TO *, const POINTS_TO *); // exported 00408 BOOL Aliased_Static_Nest_Rule(const POINTS_TO *, const POINTS_TO *) const; 00409 BOOL Aliased_Classification_Rule(const POINTS_TO *, const POINTS_TO *) const; 00410 BOOL Aliased_Ip_Classification_Rule(const POINTS_TO *, const POINTS_TO *) const; 00411 BOOL Aliased_F_Param_Rule(const POINTS_TO *, const POINTS_TO *) const; 00412 BOOL Aliased_ANSI_Type_Rule(const POINTS_TO *, const POINTS_TO *, TY_IDX, TY_IDX) const; 00413 BOOL Aliased_Qualifier_Rule(const POINTS_TO *, const POINTS_TO *, TY_IDX , TY_IDX ) const; 00414 BOOL Aliased_Attribute_Rule(const POINTS_TO *, const POINTS_TO *) const; 00415 BOOL Aliased_C_Qualifier_Rule(const POINTS_TO *, const POINTS_TO *) const; 00416 BOOL Aliased_Ragnarok_Unnamed(const POINTS_TO *, const POINTS_TO *) const; 00417 BOOL Aliased_Ragnarok_Restrict(const POINTS_TO *, const POINTS_TO *) const; 00418 BOOL Aliased_Disjoint(const POINTS_TO *, const POINTS_TO *) const; 00419 ALIAS_KIND Aliased_Indirect_Rule(const POINTS_TO *, const POINTS_TO *, 00420 BOOL ignore_loop_carried) const; 00421 BOOL Aliased_F90_Target_Rule(const POINTS_TO *, const POINTS_TO *, 00422 TY_IDX , TY_IDX ) const; 00423 00424 public: 00425 00426 ALIAS_RULE(ALIAS_CONTEXT ac):_context(ac) {} 00427 00428 BOOL Aliased_Strongly_Typed_Rule(TY_IDX , TY_IDX ) const; 00429 00430 // Check if a rule is applicable 00431 BOOL Rule_enabled(ALIAS_CONTEXT rule) const { return _context & rule; } 00432 00433 // Add all call-by-reference language here!!! 00434 BOOL Call_by_reference(void) const { return Rule_enabled(F_CALL_RULE); } 00435 00436 // Get/Set alias context. 00437 void Set_context(ALIAS_CONTEXT c) { _context = c; } 00438 ALIAS_CONTEXT Get_context(void) { return _context; } 00439 00440 // Two memory operations are referencing the same location. 00441 BOOL Same_location(const WN *, const WN *, const POINTS_TO *, const POINTS_TO *) const; 00442 00443 // Offset,size of two memop overlapped. 00444 ALIAS_KIND Aliased_Ofst_Rule(const POINTS_TO *, const POINTS_TO *) const; 00445 00446 // Interface exported to the optimizer. 00447 // We provide two sets of interface functions. 00448 00449 // The first set returns whether two memops are aliased. 00450 // 00451 ALIAS_KIND Aliased_Memop(const POINTS_TO *, const POINTS_TO *, 00452 BOOL ignore_loop_carried = FALSE) const; 00453 ALIAS_KIND Aliased_Memop(const POINTS_TO *, const POINTS_TO *, TY_IDX , TY_IDX, 00454 BOOL ignore_loop_carried = FALSE) const; 00455 ALIAS_KIND Aliased_Memop_By_Analysis(const POINTS_TO *, const POINTS_TO *, 00456 BOOL ignore_loop_carried = FALSE) const; 00457 BOOL Aliased_Memop_By_Declaration(const POINTS_TO *, const POINTS_TO *, 00458 TY_IDX ll_ty1, TY_IDX ll_ty2, 00459 TY_IDX hl_ty1=(TY_IDX)0, 00460 TY_IDX hl_ty2=(TY_IDX)0) const; 00461 00462 BOOL Aliased_with_Global(const POINTS_TO *) const; 00463 BOOL Aliased_with_Indirect(const POINTS_TO *) const; 00464 00465 // The second set returns whether a scalar is aliased by a CALL 00466 // 00467 READ_WRITE Aliased_with_Call(ST *, INT32, const POINTS_TO *) const; 00468 // READ_WRITE Aliased_with_Region(REGION *, const POINTS_TO *); 00469 00470 READ_WRITE Aliased_with_Asm(const WN *, const POINTS_TO *) const; 00471 00472 // The third set returns a bitset representing the set of named 00473 // scalars that are affected by the side effect (memop to symbol 00474 // analysis). The set is a conservative estimate. 00475 // 00476 const BS *Alias_Set_Indirect(const OPT_STAB *) const; 00477 const BS *Alias_Set_Call_By_Value(const OPT_STAB *) const; 00478 const BS *Alias_Set_Call_By_Ref(const OPT_STAB *) const; 00479 const BS *Alias_Set_Return(const OPT_STAB *) const; 00480 const BS *Alias_Set_Asm(const OPT_STAB *) const; 00481 }; 00482 00483 typedef UINT32 LMV_ALIAS_GROUP; 00484 inline LMV_ALIAS_GROUP Gen_LMV_alias_group(INT loop, INT grp) 00485 { return (UINT(loop & 0xffff) << 16) | UINT(grp & 0xffff) ; } 00486 00487 #endif
1.5.6