shithub: rgbds

Download patch

ref: 1b05c43b979f8cc8c9bd571a7c96f13614724111
parent: e4cbf773f69913a36519e71f7ad159913c382ce7
author: Ben10do <[email protected]>
date: Sun Feb 19 17:43:45 EST 2017 

Implement byte alignment in section assingment

Yay, more refactoring of the section assignment… This version of the linker will allocate sections by their alignment, and then by their size (largest first, in both cases).

In future, this may be improved by using dense packing (as suggested by #83).


--- a/src/link/assign.c
+++ b/src/link/assign.c
@@ -46,7 +46,7 @@
 	case SECT_WRAMX: DOMAXWBANK(y); break; \
 	case SECT_SRAM: DOMAXSBANK(y); break; \
 	case SECT_VRAM: DOMAXVBANK(y); break; \
-	default: errx(1, "DOMAXBANK used with invalid parameters"); break; }}
+	default: break; }}
 #define DOMAXRBANK(x)	{if( (x)>MaxBankUsed ) MaxBankUsed=(x);}
 #define DOMAXWBANK(x)	{if( (x)>MaxWBankUsed ) MaxWBankUsed=(x);}
 #define DOMAXSBANK(x)	{if( (x)>MaxSBankUsed ) MaxSBankUsed=(x);}
@@ -78,45 +78,51 @@
 }
 
 SLONG
-area_AllocAbs(struct sFreeArea ** ppArea, SLONG org, SLONG size)
+area_doAlloc(struct sFreeArea *pArea, SLONG org, SLONG size)
 {
-	struct sFreeArea *pArea;
-
-	pArea = *ppArea;
-	while (pArea) {
-		if (org >= pArea->nOrg
-		    && (org + size - 1) <= (pArea->nOrg + pArea->nSize - 1)) {
-			if (org == pArea->nOrg) {
-				pArea->nOrg += size;
+	if (org >= pArea->nOrg && (org + size) <= (pArea->nOrg + pArea->nSize)) {
+		if (org == pArea->nOrg) {
+			pArea->nOrg += size;
+			pArea->nSize -= size;
+			return org;
+		} else {
+			if ((org + size) == (pArea->nOrg + pArea->nSize)) {
 				pArea->nSize -= size;
-				return 0;
+				return org;
 			} else {
-				if ((org + size - 1) ==
-				    (pArea->nOrg + pArea->nSize - 1)) {
-					pArea->nSize -= size;
-					return 0;
-				} else {
-					struct sFreeArea *pNewArea;
+				struct sFreeArea *pNewArea;
 
-					if ((pNewArea =
-						malloc(sizeof(struct sFreeArea)))
-					    != NULL) {
-						*pNewArea = *pArea;
-						pNewArea->pPrev = pArea;
-						pArea->pNext = pNewArea;
-						pArea->nSize =
-						    org - pArea->nOrg;
-						pNewArea->nOrg = org + size;
-						pNewArea->nSize -=
-						    size + pArea->nSize;
-
-						return 0;
-					} else {
-						err(1, NULL);
-					}
+				if ((pNewArea = malloc(sizeof(struct sFreeArea))) != NULL) {
+					*pNewArea = *pArea;
+					pNewArea->pPrev = pArea;
+					pArea->pNext = pNewArea;
+					pArea->nSize = org - pArea->nOrg;
+					pNewArea->nOrg = org + size;
+					pNewArea->nSize -= size + pArea->nSize;
+					return org;
+					
+				} else {
+					err(1, NULL);
 				}
 			}
 		}
+	}
+	
+	return -1;
+}
+
+SLONG
+area_AllocAbs(struct sFreeArea ** ppArea, SLONG org, SLONG size)
+{
+	struct sFreeArea *pArea;
+
+	pArea = *ppArea;
+	while (pArea) {
+		SLONG result = area_doAlloc(pArea, org, size);
+		if (result != -1) {
+			return result;
+		}
+		
 		ppArea = &(pArea->pNext);
 		pArea = *ppArea;
 	}
@@ -141,31 +147,35 @@
 	return -1;
 }
 
-SLONG 
-area_Alloc(struct sFreeArea ** ppArea, SLONG size)
-{
+SLONG
+area_Alloc(struct sFreeArea ** ppArea, SLONG size, SLONG alignment) {
 	struct sFreeArea *pArea;
-
+	if (alignment < 1) {
+		alignment = 1;
+	}
+	
 	pArea = *ppArea;
 	while (pArea) {
-		if (size <= pArea->nSize) {
-			SLONG r;
-
-			r = pArea->nOrg;
-			pArea->nOrg += size;
-			pArea->nSize -= size;
-
-			return (r);
+		SLONG org = pArea->nOrg;	
+		if (org % alignment) {
+			org += alignment;
 		}
+		org -= org % alignment;
+		
+		SLONG result = area_doAlloc(pArea, org, size);
+		if (result != -1) {
+			return result;
+		}
+		
 		ppArea = &(pArea->pNext);
 		pArea = *ppArea;
 	}
 
-	return (-1);
+	return -1;
 }
 
 SLONG
-area_AllocAnyBank(SLONG size, enum eSectionType type) {
+area_AllocAnyBank(SLONG size, SLONG alignment, enum eSectionType type) {
 	ensureSectionTypeIsValid(type);
 
 	SLONG startBank = SECT_ATTRIBUTES[type].bank;
@@ -172,7 +182,7 @@
 	SLONG bankCount = SECT_ATTRIBUTES[type].bankCount;
 	
 	for (int i = 0; i < bankCount; i++) {
-		SLONG org = area_Alloc(&BankFree[startBank + i], size);
+		SLONG org = area_Alloc(&BankFree[startBank + i], size, alignment);
 		if (org != -1) {
 			return ((startBank + i) << 16) | org;
 		}
@@ -182,35 +192,73 @@
 }
 
 struct sSection *
-FindLargestSection(enum eSectionType type)
+FindLargestSection(enum eSectionType type, bool bankFixed)
 {
 	struct sSection *pSection, *r = NULL;
 	SLONG nLargest = 0;
+	SLONG nLargestAlignment = 0;
 
 	pSection = pSections;
 	while (pSection) {
-		if (pSection->oAssigned == 0 && pSection->Type == type) {
-			if (pSection->nByteSize > nLargest) {
+		if (pSection->oAssigned == 0 && pSection->Type == type && (bankFixed ^ (pSection->nBank == -1))) {
+			if (pSection->nAlign > nLargestAlignment || (pSection->nAlign == nLargestAlignment && pSection->nByteSize > nLargest)) {
 				nLargest = pSection->nByteSize;
+				nLargestAlignment = pSection->nAlign;
 				r = pSection;
 			}
 		}
 		pSection = pSection->pNext;
 	}
+	
 	return r;
 }
 
+
+bool
+VerifyAndSetBank(struct sSection *pSection)
+{
+	ensureSectionTypeIsValid(pSection->Type);
+
+	if (pSection->nBank >= SECT_ATTRIBUTES[pSection->Type].minBank
+		&& pSection->nBank < SECT_ATTRIBUTES[pSection->Type].minBank + SECT_ATTRIBUTES[pSection->Type].bankCount) {
+		pSection->nBank += SECT_ATTRIBUTES[pSection->Type].bank + SECT_ATTRIBUTES[pSection->Type].offset;
+		return true;
+		
+	} else {
+		return false;
+	}
+}
+
 void
-AssignBankedSections(enum eSectionType type)
+AssignFixedBankSections(enum eSectionType type)
 {
 	ensureSectionTypeIsValid(type);
 
 	struct sSection *pSection;
 
-	while ((pSection = FindLargestSection(type))) {
+	while ((pSection = FindLargestSection(type, true))) {
+		if (VerifyAndSetBank(pSection) &&
+			(pSection->nOrg = area_Alloc(&BankFree[pSection->nBank], pSection->nByteSize, pSection->nAlign)) != -1) {
+			pSection->oAssigned = 1;
+			DOMAXBANK(pSection->Type, pSection->nBank);
+		} else {
+			errx(1, "Unable to load fixed %s section into bank $%02lX",
+				SECT_ATTRIBUTES[pSection->Type].name, pSection->nBank);
+		}
+	}
+}
+
+void
+AssignFloatingBankSections(enum eSectionType type)
+{
+	ensureSectionTypeIsValid(type);
+
+	struct sSection *pSection;
+
+	while ((pSection = FindLargestSection(type, false))) {
 		SLONG org;
 
-		if ((org = area_AllocAnyBank(pSection->nByteSize, type)) != -1) {
+		if ((org = area_AllocAnyBank(pSection->nByteSize, pSection->nAlign, type)) != -1) {
 			pSection->nOrg = org & 0xFFFF;
 			pSection->nBank = org >> 16;
 			pSection->oAssigned = 1;
@@ -219,24 +267,9 @@
 			errx(1, "Unable to place %s section anywhere",
 				 SECT_ATTRIBUTES[type].name);
 		}
-	}
+	}	
 }
 
-bool
-VerifyAndSetBank(struct sSection *pSection)
-{
-	ensureSectionTypeIsValid(pSection->Type);
-
-	if (pSection->nBank >= SECT_ATTRIBUTES[pSection->Type].minBank
-		&& pSection->nBank < SECT_ATTRIBUTES[pSection->Type].minBank + SECT_ATTRIBUTES[pSection->Type].bankCount) {
-		pSection->nBank += SECT_ATTRIBUTES[pSection->Type].bank + SECT_ATTRIBUTES[pSection->Type].offset;
-		return true;
-		
-	} else {
-		return false;
-	}
-}
-
 void
 AssignSections(void)
 {
@@ -353,35 +386,11 @@
 	}
 
 	/*
-	 * Next, let's assign all the bankfixed ONLY ROMX sections...
+	 * Next, let's assign all the bankfixed ONLY sections...
 	 *
 	 */
-
-	pSection = pSections;
-	while (pSection) {
-		if (pSection->oAssigned == 0
-			&& pSection->nOrg == -1 && pSection->nBank != -1) {
-			switch (pSection->Type) {
-			case SECT_ROMX:
-			case SECT_SRAM:
-			case SECT_VRAM:
-			case SECT_WRAMX:
-				if (VerifyAndSetBank(pSection) &&
-					(pSection->nOrg = area_Alloc(&BankFree[pSection->nBank], pSection->nByteSize)) != -1) {
-					pSection->oAssigned = 1;
-					DOMAXBANK(pSection->Type, pSection->nBank);
-				} else {
-					errx(1, "Unable to load fixed %s section into bank $%02lX",
-						 SECT_ATTRIBUTES[pSection->Type].name, pSection->nBank);
-				}
-				break;
-
-			default: // Handle other sections later
-				break;
-			}
-		}
-
-		pSection = pSection->pNext;
+	for (enum eSectionType i = SECT_MIN; i <= SECT_MAX; i++) {
+		AssignFixedBankSections(i);
 	}
 
 	/*
@@ -421,41 +430,9 @@
 	 * sections
 	 *
 	 */
-
-	pSection = pSections;
-	while (pSection) {
-		if (pSection->oAssigned == 0) {
-			switch (pSection->Type) {
-			case SECT_WRAM0:
-			case SECT_HRAM:
-			case SECT_ROM0:
-				pSection->nBank = SECT_ATTRIBUTES[pSection->Type].bank;
-				if ((pSection->nOrg =
-					area_Alloc(&BankFree[pSection->nBank],
-					    pSection->nByteSize)) == -1) {
-					errx(1, "%s section too large", SECT_ATTRIBUTES[pSection->Type].name);
-				}
-				pSection->oAssigned = 1;
-				break;
-
-			case SECT_SRAM:
-			case SECT_VRAM:
-			case SECT_WRAMX:
-			case SECT_ROMX:
-				break;
-
-			default:
-				errx(1, "(INTERNAL) Unknown section type!");
-				break;
-			}
-		}
-		pSection = pSection->pNext;
+	for (enum eSectionType i = SECT_MIN; i <= SECT_MAX; i++) {
+		AssignFloatingBankSections(i);
 	}
-
-	AssignBankedSections(SECT_ROMX);
-	AssignBankedSections(SECT_VRAM);
-	AssignBankedSections(SECT_WRAMX);
-	AssignBankedSections(SECT_SRAM);
 }
 
 void