From 1647c6783f98c7ca74f1f49a7f3eb3c60bdf95d0 Mon Sep 17 00:00:00 2001 From: cuz Date: Sun, 6 Oct 2002 19:01:16 +0000 Subject: [PATCH] New functions CS_ResetMarks, CS_ResetAllMarks and CS_IsBasicBlock. git-svn-id: svn://svn.cc65.org/cc65/trunk@1448 b7a2c559-68d2-44c3-8de9-860c34a00d81 --- src/cc65/codeseg.c | 120 +++++++++++++++++++++++++++++++++++++++++++++ src/cc65/codeseg.h | 43 ++++++++++++---- 2 files changed, 153 insertions(+), 10 deletions(-) diff --git a/src/cc65/codeseg.c b/src/cc65/codeseg.c index 530ffe205..ab500eee2 100644 --- a/src/cc65/codeseg.c +++ b/src/cc65/codeseg.c @@ -1096,6 +1096,126 @@ void CS_DelCodeAfter (CodeSeg* S, unsigned Last) +void CS_ResetMarks (CodeSeg* S, unsigned First, unsigned Last) +/* Remove all user marks from the entries in the given range */ +{ + while (First <= Last) { + CE_ResetMark (CS_GetEntry (S, First++)); + } +} + + + +int CS_IsBasicBlock (CodeSeg* S, unsigned First, unsigned Last) +/* Check if the given code segment range is a basic block. That is, check if + * First is the only entrance and Last is the only exit. This means that no + * jump/branch inside the block may jump to an insn below First or after(!) + * Last, and that no insn may jump into this block from the outside. + */ +{ + unsigned I; + + /* Don't accept invalid ranges */ + CHECK (First <= Last); + + /* First pass: Walk over the range and remove all marks from the entries */ + CS_ResetMarks (S, First, Last); + + /* Second pass: Walk over the range checking all labels. Note: There may be + * label on the first insn which is ok. + */ + I = First + 1; + while (I <= Last) { + + /* Get the next entry */ + CodeEntry* E = CS_GetEntry (S, I); + + /* Check if this entry has one or more labels, if so, check which + * entries jump to this label. + */ + unsigned LabelCount = CE_GetLabelCount (E); + unsigned LabelIndex; + for (LabelIndex = 0; LabelIndex < LabelCount; ++LabelIndex) { + + /* Get this label */ + CodeLabel* L = CE_GetLabel (E, LabelIndex); + + /* Walk over all entries that jump to this label. Check for each + * of the entries if it is out of the range. + */ + unsigned RefCount = CL_GetRefCount (L); + unsigned RefIndex; + for (RefIndex = 0; RefIndex < RefCount; ++RefIndex) { + + /* Get the code entry that jumps here */ + CodeEntry* Ref = CL_GetRef (L, RefIndex); + + /* Walk over out complete range and check if we find the + * refering entry. This is cheaper than using CS_GetEntryIndex, + * because CS_GetEntryIndex will search the complete code + * segment and not just our range. + */ + unsigned J; + for (J = First; J <= Last; ++J) { + if (Ref == CS_GetEntry (S, J)) { + break; + } + } + if (J > Last) { + /* We did not find the entry. This means that the jump to + * out code segment entry E came from outside the range, + * which in turn means that the given range is not a basic + * block. + */ + CS_ResetMarks (S, First, Last); + return 0; + } + + /* If we come here, we found the entry. Mark it, so we know + * that the branch to the label is in range. + */ + CE_SetMark (Ref); + } + } + + /* Next entry */ + ++I; + } + + /* Third pass: Walk again over the range and check all branches. If we + * find a branch that is not marked, its target is not inside the range + * (since we checked all the labels in the range before). + */ + I = First; + while (I <= Last) { + + /* Get the next entry */ + CodeEntry* E = CS_GetEntry (S, I); + + /* Check if this is a branch and if so, if it has a mark */ + if (E->Info & (OF_UBRA | OF_CBRA)) { + if (!CE_HasMark (E)) { + /* No mark means not a basic block. Before bailing out, be sure + * to remove the marks from the remaining entries. + */ + CS_ResetMarks (S, I+1, Last); + return 0; + } + + /* Remove the mark */ + CE_ResetMark (E); + } + + /* Next entry */ + ++I; + } + + /* Done - this is a basic block */ + return 1; +} + + + void CS_OutputPrologue (const CodeSeg* S, FILE* F) /* If the given code segment is a code segment for a function, output the * assembler prologue into the file. That is: Output a comment header, switch diff --git a/src/cc65/codeseg.h b/src/cc65/codeseg.h index c149a2dc7..3ddf24ada 100644 --- a/src/cc65/codeseg.h +++ b/src/cc65/codeseg.h @@ -103,6 +103,16 @@ void CS_AddVLine (CodeSeg* S, LineInfo* LI, const char* Format, va_list ap) attr void CS_AddLine (CodeSeg* S, LineInfo* LI, const char* Format, ...) attribute ((format(printf,3,4))); /* Add a line to the given code segment */ +#if defined(HAVE_INLINE) +INLINE unsigned CS_GetEntryCount (const CodeSeg* S) +/* Return the number of entries for the given code segment */ +{ + return CollCount (&S->Entries); +} +#else +# define CS_GetEntryCount(S) CollCount (&(S)->Entries) +#endif + void CS_InsertEntry (CodeSeg* S, struct CodeEntry* E, unsigned Index); /* Insert the code entry at the index given. Following code entries will be * moved to slots with higher indices. @@ -218,6 +228,29 @@ void CS_MoveLabelRef (CodeSeg* S, struct CodeEntry* E, CodeLabel* L); void CS_DelCodeAfter (CodeSeg* S, unsigned Last); /* Delete all entries including the given one */ +void CS_ResetMarks (CodeSeg* S, unsigned First, unsigned Last); +/* Remove all user marks from the entries in the given range */ + +#if defined(HAVE_INLINE) +INLINE void CS_ResetAllMarks (CodeSeg* S) +/* Remove all user marks from the code segment */ +{ + if (CS_GetEntryCount (S) > 0) { + CS_ResetMarks (S, 0, CS_GetEntryCount (S)); + } +} +#else +# define CS_ResetAllMarks(S) \ + ((CS_GetEntryCount (S) > 0)? CS_ResetMarks (S, 0, CS_GetEntryCount (S)) : (void) 0) +#endif + +int CS_IsBasicBlock (CodeSeg* S, unsigned First, unsigned Last); +/* Check if the given code segment range is a basic block. That is, check if + * First is the only entrance and Last is the only exit. This means that no + * jump/branch inside the block may jump to an insn below First or after(!) + * Last, and that no insn may jump into this block from the outside. + */ + void CS_OutputPrologue (const CodeSeg* S, FILE* F); /* If the given code segment is a code segment for a function, output the * assembler prologue into the file. That is: Output a comment header, switch @@ -233,16 +266,6 @@ void CS_OutputEpilogue (const CodeSeg* S, FILE* F); void CS_Output (const CodeSeg* S, FILE* F); /* Output the code segment data to a file */ -#if defined(HAVE_INLINE) -INLINE unsigned CS_GetEntryCount (const CodeSeg* S) -/* Return the number of entries for the given code segment */ -{ - return CollCount (&S->Entries); -} -#else -# define CS_GetEntryCount(S) CollCount (&(S)->Entries) -#endif - void CS_FreeRegInfo (CodeSeg* S); /* Free register infos for all instructions */ -- 2.39.2