1 /*****************************************************************************/
5 /* Optimizer subroutines */
9 /* (C) 2001 Ullrich von Bassewitz */
11 /* D-70597 Stuttgart */
12 /* EMail: uz@cc65.org */
15 /* This software is provided 'as-is', without any expressed or implied */
16 /* warranty. In no event will the authors be held liable for any damages */
17 /* arising from the use of this software. */
19 /* Permission is granted to anyone to use this software for any purpose, */
20 /* including commercial applications, and to alter it and redistribute it */
21 /* freely, subject to the following restrictions: */
23 /* 1. The origin of this software must not be misrepresented; you must not */
24 /* claim that you wrote the original software. If you use this software */
25 /* in a product, an acknowledgment in the product documentation would be */
26 /* appreciated but is not required. */
27 /* 2. Altered source versions must be plainly marked as such, and must not */
28 /* be misrepresented as being the original software. */
29 /* 3. This notice may not be removed or altered from any source */
32 /*****************************************************************************/
53 /*****************************************************************************/
55 /*****************************************************************************/
59 /* Defines for the conditions in a compare */
74 /* Table with the compare suffixes */
75 static const char CmpSuffixTab [][4] = {
76 "eq", "ne", "gt", "ge", "lt", "le", "ugt", "uge", "ult", "ule"
79 /* Table used to invert a condition, indexed by condition */
80 static const unsigned char CmpInvertTab [] = {
82 CMP_LE, CMP_LT, CMP_GE, CMP_GT,
83 CMP_ULE, CMP_ULT, CMP_UGE, CMP_UGT
86 /* Table to show which compares are signed (use the N flag) */
87 static const char CmpSignedTab [] = {
88 0, 0, 1, 1, 1, 1, 0, 0, 0, 0
93 /*****************************************************************************/
94 /* Helper functions */
95 /*****************************************************************************/
99 static cmp_t FindCmpCond (const char* Suffix)
100 /* Map a condition suffix to a code. Return the code or CMP_INV on failure */
105 for (I = 0; I < sizeof (CmpSuffixTab) / sizeof (CmpSuffixTab [0]); ++I) {
106 if (strcmp (Suffix, CmpSuffixTab [I]) == 0) {
118 /*****************************************************************************/
119 /* Remove calls to the bool transformer subroutines */
120 /*****************************************************************************/
124 static unsigned OptBoolTransforms (CodeSeg* S)
125 /* Try to remove the call to boolean transformer routines where the call is
129 unsigned Changes = 0;
132 /* Get the number of entries, bail out if we have not enough */
133 unsigned Count = GetCodeEntryCount (S);
138 /* Walk over the entries */
140 while (I < Count-1) {
143 CodeEntry* E = GetCodeEntry (S, I);
145 /* Check for a boolean transformer */
146 if (E->OPC == OPC_JSR && strncmp (E->Arg, "bool", 4) == 0) {
150 /* Get the next entry */
151 CodeEntry* N = GetCodeEntry (S, I+1);
153 /* Check if this is a conditional branch */
154 if ((N->Info & OF_CBRA) == 0) {
155 /* No conditional branch, bail out */
159 /* Make the boolean transformer unnecessary by changing the
160 * the conditional jump to evaluate the condition flags that
161 * are set after the compare directly. Note: jeq jumps if
162 * the condition is not met, jne jumps if the condition is met.
164 Cond = FindCmpCond (E->Arg + 4);
165 if (Cond == CMP_INV) {
166 /* Unknown function */
170 /* Invert the code if we jump on condition not met. */
171 if (GetBranchCond (N->OPC) == BC_EQ) {
172 /* Jumps if condition false, invert condition */
173 Cond = CmpInvertTab [Cond];
176 /* Check if we can replace the code by something better */
180 ReplaceOPC (N, OPC_JEQ);
184 ReplaceOPC (N, OPC_JNE);
192 ReplaceOPC (N, OPC_JPL);
196 ReplaceOPC (N, OPC_JMI);
208 ReplaceOPC (N, OPC_JCS);
212 ReplaceOPC (N, OPC_JCC);
220 Internal ("Unknown jump condition: %d", Cond);
224 /* Remove the call to the bool transformer */
228 /* Remember, we had changes */
239 /* Return the number of changes made */
245 /*****************************************************************************/
247 /*****************************************************************************/
251 /* Table with all the optimization functions */
252 typedef struct OptFunc OptFunc;
254 unsigned (*Func) (CodeSeg*);/* Optimizer function */
255 const char* Name; /* Name of optimizer step */
256 char Disabled; /* True if pass disabled */
261 /* Table with optimizer steps - are called in this order */
262 static OptFunc OptFuncs [] = {
263 /* Optimize jump cascades */
264 { OptJumpCascades, "OptJumpCascades", 0 },
265 /* Remove dead jumps */
266 { OptDeadJumps, "OptDeadJumps", 0 },
267 /* Change jsr/rts to jmp */
268 { OptRTS, "OptRTS", 0 },
269 /* Remove dead code */
270 { OptDeadCode, "OptDeadCode", 0 },
271 /* Optimize jump targets */
272 { OptJumpTarget, "OptJumpTarget", 0 },
273 /* Optimize conditional branches */
274 { OptCondBranches, "OptCondBranches", 0 },
275 /* Remove calls to the bool transformer subroutines */
276 { OptBoolTransforms, "OptBoolTransforms", 0 },
277 /* Remove unused loads */
278 { OptUnusedLoads, "OptUnusedLoads", 0 },
283 static OptFunc* FindOptStep (const char* Name)
284 /* Find an optimizer step by name in the table and return a pointer. Print an
285 * error and call AbEnd if not found.
290 /* Run all optimization steps */
291 for (I = 0; I < sizeof(OptFuncs)/sizeof(OptFuncs[0]); ++I) {
292 if (strcmp (OptFuncs[I].Name, Name) == 0) {
299 AbEnd ("Optimization step `%s' not found", Name);
305 void DisableOpt (const char* Name)
306 /* Disable the optimization with the given name */
308 OptFunc* F = FindOptStep (Name);
314 void EnableOpt (const char* Name)
315 /* Enable the optimization with the given name */
317 OptFunc* F = FindOptStep (Name);
323 void RunOpt (CodeSeg* S)
324 /* Run the optimizer */
330 /* If we shouldn't run the optimizer, bail out */
335 /* Print the name of the function we are working on */
337 Print (stdout, 1, "Running optimizer for function `%s'\n", S->Func->Name);
339 Print (stdout, 1, "Running optimizer for global code segment\n");
342 /* Repeat all steps until there are no more changes */
344 /* Reset the number of changes */
347 /* Keep the user hapy */
348 Print (stdout, 1, " Optimizer pass %u:\n", ++Pass);
350 /* Run all optimization steps */
351 for (I = 0; I < sizeof(OptFuncs)/sizeof(OptFuncs[0]); ++I) {
353 /* Print the name of the following optimizer step */
354 Print (stdout, 1, " %s:%*s", OptFuncs[I].Name,
355 (int) (30-strlen(OptFuncs[I].Name)), "");
357 /* Check if the step is disabled */
358 if (OptFuncs[I].Disabled) {
359 Print (stdout, 1, "Disabled\n");
361 unsigned Changes = OptFuncs[I].Func (S);
362 OptChanges += Changes;
363 Print (stdout, 1, "%u Changes\n", Changes);
367 } while (OptChanges > 0);