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 /*****************************************************************************/
47 /*****************************************************************************/
49 /*****************************************************************************/
53 /* Counter for the number of changes in one run. The optimizer process is
54 * repeated until there are no more changes.
56 static unsigned OptChanges;
60 /*****************************************************************************/
61 /* Remove dead jumps */
62 /*****************************************************************************/
66 static void OptDeadJumps (CodeSeg* S)
67 /* Remove dead jumps (jumps to the next instruction) */
72 /* Get the number of entries, bail out if we have less than two entries */
73 unsigned Count = CollCount (&S->Entries);
78 /* Walk over all entries minus the last one */
82 /* Get the next entry */
83 E = CollAt (&S->Entries, I);
85 /* Check if it's a branch, if it has a local target, and if the target
86 * is the next instruction.
88 if (E->AM == AM_BRA && E->JumpTo && E->JumpTo->Owner == CollAt (&S->Entries, I+1)) {
90 /* Delete the dead jump */
93 /* Keep the number of entries updated */
96 /* Remember, we had changes */
110 /*****************************************************************************/
111 /* Remove dead code */
112 /*****************************************************************************/
116 static void OptDeadCode (CodeSeg* S)
117 /* Remove dead code (code that follows an unconditional jump or an rts/rti
123 /* Get the number of entries, bail out if we have less than two entries */
124 unsigned Count = CollCount (&S->Entries);
129 /* Walk over all entries minus the last one */
131 while (I < Count-1) {
134 CodeEntry* E = CollAt (&S->Entries, I);
136 /* Check if it's an unconditional branch, and if the next entry has
139 if ((E->OPC == OPC_JMP || E->OPC == OPC_BRA || E->OPC == OPC_RTS || E->OPC == OPC_RTI) &&
140 !CodeEntryHasLabel (CollAt (&S->Entries, I+1))) {
142 /* Delete the next entry */
143 DelCodeEntry (S, I+1);
145 /* Keep the number of entries updated */
148 /* Remember, we had changes */
162 /*****************************************************************************/
163 /* Optimize jump cascades */
164 /*****************************************************************************/
168 static void OptJumpCascades (CodeSeg* S)
169 /* Optimize jump cascades (jumps to jumps). In such a case, the jump is
170 * replaced by a jump to the final location. This will in some cases produce
171 * worse code, because some jump targets are no longer reachable by short
172 * branches, but this is quite rare, so there are more advantages than
178 /* Get the number of entries, bail out if we have no entries */
179 unsigned Count = CollCount (&S->Entries);
184 /* Walk over all entries */
192 CodeEntry* E = CollAt (&S->Entries, I);
194 /* Check if it's a branch, if it has a label attached, and if the
195 * instruction at this label is also a branch.
197 if (E->AM == AM_BRA &&
198 (OldLabel = E->JumpTo) != 0 &&
199 OldLabel->Owner->AM == AM_BRA &&
200 (NewLabel = OldLabel->Owner->JumpTo) != 0) {
202 /* Get the instruction that has the new label attached */
203 CodeEntry* N = OldLabel->Owner;
205 /* Remove the reference to our label and delete it if this was
206 * the last reference.
208 if (RemoveLabelRef (OldLabel, E) == 0) {
210 DelCodeLabel (S, OldLabel);
213 /* Use the usage information from the new instruction */
217 /* Use the new label */
218 AddLabelRef (NewLabel, E);
220 /* Remember ,we had changes */
233 /*****************************************************************************/
235 /*****************************************************************************/
239 void RunOpt (CodeSeg* S)
240 /* Run the optimizer */
242 typedef void (*OptFunc) (CodeSeg*);
244 /* Table with optimizer steps - are called in this order */
245 static const OptFunc OptFuncs [] = {
246 OptJumpCascades, /* Optimize jump cascades */
247 OptDeadJumps, /* Remove dead jumps */
248 OptDeadCode, /* Remove dead code */
251 /* Repeat all steps until there are no more changes */
257 /* Reset the number of changes */
260 /* Run all optimization steps */
262 for (I = 0; I < sizeof(OptFuncs)/sizeof(OptFuncs[0]); ++I) {
263 if ((OptDisable & Flags) == 0) {
265 } else if (Verbosity > 0 || Debug) {
266 printf ("Optimizer pass %u skipped\n", I);
271 } while (OptChanges > 0);