选择性存取不同指令缓冲阶层的装置及方法

摘要

一种分支控制装置,适用于一微处理器,此分支控制装置包括:一指令缓冲器,具有数个阶层,用以暂存自指令快取区接收的指令字节的快取线。一多任务器,是在指令缓冲器中的三个阶层中选取一底层阶层,以提供至指令格式化逻辑,其中此多任务器所选取的阶层,是依据一分支指针、一指令涵盖指针及一进位指针而进行选取,其中分支指针是用以指示微处理器目前是否分支至分支目标地址快取区所提供的目标地址,而分支指针及目标地址目前是储存于相关联的阶层中,其中此阶层是包含因目标地址而被快取的分支指令。涵盖指针是指出目前被格式化的指令是否涵盖横跨两个快取线,而进位指针则是指出目前被格式化指令是否占据目前被格式化的指令缓冲器阶层的最后字节位置。

说明书

技术领域

本发明是有关于一种分支目标地址在管线微处理器进行快取的领域，且特别是有关于一种在微处理器因分支目标地址快取命中而进行分支(branch)后，将正确的指令格式提供至指令格式化逻辑的装置及方法。

背景技术

管线微处理器(pipelined microprocessor)包括多重的管路阶层，在程序指令执行中，每一个阶层会展现一个不同的函数需求。典型的管线阶层函数是指令撷取(fetch)、指令译码、指令执行、内存存取以及结果写回(result write-back)。

其中，指令撷取阶层是在目前的执行程序中撷取下一个指令，而此下一个指令基本上是下一个循序内存地址的指令，然而，在发生分支(taken branch)指令的情况下，下一个指令是由分支指令所指定的内存地址中的指令，一般称此内存地址为分支目标地址(branch targetaddress)。指令撷取阶层从指令快取区中撷取的指令，目前如果不在此指令快取区中，则会自机器的阶层式内存(memory hierarchy)中较高层次的指令高速缓存中撷取，例如从较高阶层高速缓存或是从系统内存中撷取得到，而指令撷取阶层撷取到的指令会提供给下一个阶层的指令译码阶层处理。

指令译码阶层包括指令译码逻辑，用以对从指令撷取阶层接收的指令字节进行译码。在处理器支持不同指令长度的情况下，例如x86结构处理器，一个指令译码阶层的功能，会分割指令字节流以格式化指令，其中格式化指令流(a stream of instructions)包括决定每一个指令的长度，比方说，指令格式化逻辑从指令撷取阶层接收尚未辨识的指令字节流，进而对此指令字节流进行格式化，或分析为个别的字节群组，其中每一个位群组是一个指令，而这些指令所组成的程序即是可使处理器进行执行的指令。另外，指令译码阶层也包含转换宏指令，例如x86指令，为由剩余的管线(pipeline)进行执行的微指令(micro-instruction)。

指令执行阶层包括执行逻辑，是执行从指令译码阶层接收的已格式化及译码的指令，其中执行逻辑是操作从处理器的缓存器组及/或内存回收的数据。而写回阶层，是将执行逻辑所产生的结果储存至处理器的缓存器组。

管线处理器的一个重要观念，是使每一个阶层的处理器忙碌于函数被设计时的工作，假设指令译码阶层已准备要译码下一个指令，但指令撷取阶层尚未提供其所需的指令字节时，则处理器在效能上就会变糟。而为了防止指令译码阶层的饥饿(starvation)，普遍性的解决方法是：在指令快取区及指令格式化逻辑之间，放置一个指令缓冲器。指令撷取阶层会尝试在指令缓冲器中保持数个指令的字节，以使指令译码阶层有指令字节可进行译码，不至有饥饿情形发生。

一般来说，指令快取区一次会提供一个指令字节的快取线(cacheline)，通常为16或32字节，而指令撷取阶层会自指令快取区中撷取一个或多个快取线，进而将快取线储存至指令缓冲器中。当指令译码阶层准备译码一个指令时，会自指令缓冲器中存取指令字节，而不是在指令快取区中等待。

此指令快取区提供一个指令字节用的快取线，可由撷取地址(fetchaddress)进行选取，其中撷取地址是由指令撷取阶层将的提供给指令快取区。在正常的程序运作中，由于在预期的情况下会循序性地执行程序指令，因此撷取地址会单因快取线的大小而增加，且增加后的撷取地址会被指作为下一个循序撷取地址。然而，如果有一个分支指令(branch instruction)被指令译码逻辑译码，且此分支指令发生(或预期发生)，则撷取地址会更新为分支指令的目标地址(以快取线大小计算下)，而不是被更新为下一个循序撷取地址。

然而，在撷取地址被更新至分支目标地址的时候，指令缓冲器可能在分支指令后，随着下一个循序指令的指令字节而移位。因为当分支情况发生时，在分支指令后的指令不会被译码及执行。而程序本身在执行时，是需要对在分支目标地址上的指令进行执行，而不是对在分支指令后的下一个循序指令进行执行，因此在程序的循序指令流为典型的预期情况时，指令缓冲器中的指令字节错误的预先撷取(ppre-fetch)。而为了补救这个错误，处理器必须在分支指令后，清除(flush)掉所有的指令字节，包括在指令缓冲器中的指令字节。

但在发生分支指令后，立即清除指令缓冲器会产生极高的代价，因为指令译码阶层会持续饥饿，直到指令缓冲器从指令快取区中重新移植过。而一个可解决此问题的方法是：在译码分支指令前先进行分支。此可以由使用一个分支目标地址快取区(branch target addresscache；简称BTAC)来实现，此BTAC快取(cache)包含先前已执行分支指令的指令快取线的撷取地址，以及与其相关的目标地址。

此指令快取区撷取地址是应用于BTAC，本质上相似于撷取地址对于指令快取区的应用。在包含分支指令快取线的指令快取区撷取地址情况中，快取线是提供给指令缓冲器。此外，如果撷取地址命中(hit)BTAC，BTAC会提供一个相关的分支目标地址，如果分支指令命中BTAC是预期发生的，则指令快取撷取地址会被更新为由BTAC提供的目标地址。

因为指令快取区会一次提供一条指令集的快取线提供至指令缓冲器，因此在分支指令后，快取线中可能仍会有指令字节存在。而在分支指令后的这些指令字节不应被执行。然而，指令缓冲器不会一次全被清除掉(如上所述，在没有BTAC的处理器中会被清除掉)，因为可能直到现在尚未被译码的指令缓冲器中，仍有有效指令存在。特别是，分支指令本身(即任何在快取线中优先于分支指令的指令字节)必须被译码及执行。

可是，在分支指令仍在指令缓冲器中且尚未被格式化的情况下，在指令缓冲器中接续于分支指令的指令的位置也不得而知，这是因为分支指令在快取线中的长度及位置在分支指令被格式化前无法得知，因此在指令缓冲器中的分支指令的位置未知。据此，在分支指令后的指令的位置也无法得知。

此外，也可能在分支指令译码前，包含分支的目标指令的快取线会被储存至指令缓冲器中，而在快取线中，处于目标指令前的指令字节不会被执行，更复杂点的，分支指令可能会由多字节(multiple bytes)组成，而造成分支指令会涵盖横跨多个快取线。

一般说来，在管线微处理器的设计中，去设计指令格式逻辑，使的在处理器的循环周期中进行指令格式函数，是很困难的事，因此，尽可能在格式化指令字节上提供更多的循环周期，会比将指令字节自指令缓冲器中位移，更有助益。而如果是利用一个指令缓冲器使的尽可能提供时间，也是相当有助益的事，因为可让指令格式化逻辑格式化由指令缓冲器提供的指令字节。此外，利用微处理器中一个具有较大储存空间的指令缓冲器，以减少指令译码阶层饥饿的可能性，也很有帮助。特别是关于这一点在当微处理器管线处理指令的速度增加时会特别重要。这在与内存的存取时间，或是与撷取阶层在发生分支情况下，自指令快取区中撷取指令所需的时间有关的速度增加上尤其正确。

因此，在管线处理器中的分支控制装置是必须的，使得基于BTAC的指令快取撷取地址在利用上，可以与一个具有较大储存空间的指令缓冲器结合，而此具有较大储存空间的指令缓冲器可以提供有效的处理时间特性及适当的程序执行。

发明内容

本发明在管线处理器中提出一种分支控制装置，使得预先译码(pre-decode)BTAC的利用，可以与多字节宽度结合，而多重阶层指令缓冲器则提供指令译码逻辑，以增加格式化指令的时间。依据上述欲达成的目的，本发明的特征在于提供一微处理器，而此微处理器包括一个指令缓冲器，具有数个阶层，用以暂存自指令快取区接收的指令字节。此微处理器也包括一个分支指针，是关联于数个储存指针用的阶层，用以检测微处理器是否有分支到暂存于关联阶层中的分支指令的目标地址。微处理器也包含一个多任务器(multiplexer)，耦接于指令缓冲器，依据与分支指针相关联的阶层，选择其中的一个阶层。

本发明另在微处理器中也提供一种预先译码阶层，此预先译码阶层包括一个指令缓冲器，至少具有阶层A、B以及C，用以暂存指令字节。此预先译码阶层也包括一个多任务器，耦接于指令缓冲器，用以选择阶层A、B及C其中的一个阶层以提供至指令格式化逻辑。预先译码阶层也包含一分支指针，耦接于多任务器，依据呈现于阶层A的分支指令以指示微处理器是否发生分支。预先译码阶层也包含一涵盖指针(wrap indicator)，耦接于多任务器，指出被指令格式化逻辑格式化的指令是否涵盖横跨阶层A及B，以进一步格式化指令。其中，多任务器依据分支指针及涵盖指针，从阶层A、B及C中选择其中的一个阶层以提供给指令格式化逻辑。

本发明又提供一种分支控制装置，适用于微处理器。此分支控制装置包括指令缓冲器，具有第一、第二及第三阶层，用以暂存自指令快取区接收的第一、第二及第三快取线，其中，第一及第二快取线各自包含分支指令的一部份，而第三快取线则是包含分支指令的目标指令。分支控制装置也包括一分支目标地址快取区(branch target addresscache；简称BTAC)，耦接于指令缓冲器，输出一个指针，以显示第三快取线是由BTAC所提供的分支指令的目标地址自指令快取区中选取得到。分支控制装置也包括一多任务器，耦接指令缓冲器与指令格式化逻辑，用以选取第一、第二及第三阶层中的一个阶层，以提供至指令格式化逻辑，其中，多任务器会在选取第一及第二阶层后，依据BTAC输出的指针及指令格式化逻辑判断的分支指令长度，选取第三阶层。

本发明又再提出一种暂存指令字节以提供至指令格式化逻辑的方法，适用于一微处理器。此方法包括储存一分支指针，以判断处理器是否有分支于相对应于指令缓冲器的第一快取线，接着，产生第一快取线的第一指令长度，然后，依据第一指令的长度，判断第一指令是否涵盖超过第一快取线，此方法也包括依据分支指针及上述的判断步骤，选取储存于指令缓冲器的第二快取线以格式化第二指令。

本发明具有的一个优点是使多重字节宽度的指令缓冲器在连接预先译码BTAC时，可以在多数情况中，达到零分支代价，因为本发明是在将指令缓冲器中的阶层提供给指令格式化逻辑后，才进行阶层位移(shift)，而不是先位移指令缓冲器的已格式化阶层，再提供最底层的阶层予指令格式化逻辑。而由位移阶层的减少，本发明可以将有效的周期时间数量，增加于指令格式化逻辑在格式化目前的指令上。

附图说明

图1是依据本发明的包含一分支控制装置的一管线微处理器的一方框图；

图2是本发明依据图1关于位移指令缓冲器的一流程图；

图3是本发明依据图1关于指令缓冲器在阶层选择上的一流程图；以及

图4A-4F是本发明依据图1及图3关于选取指令缓冲器阶层为例的一数据表。

附图标记说明：

100：微处理器

102：指令快取区

104、174：缓存器

106：阶层置换多任务器

108：字节智能型排列多任务器(byte-wise alignment mux)

112：指令缓冲器

114：指令格式化逻辑

116：分支目标地址快取区(BTAC)

118、128：多任务器

122：控制逻辑

124：增加器

126：阶层

132、138：目标地址

134：命中讯号(HIT signal)

136：理论性分支信息(SBI signal)

142、144、146、148、166：数据总线

152：撷取地址

154、156、168：控制讯号

158：现行指针

162：次一循序撷取地址

164：分解目标地址

172：指令长度

176：与门

178：比较器

184：现行指针缓存器

186：BWRAP讯号

188：移位讯号

192、193：BTAC分支指针

194：涵盖讯号(fwrap signal)

196：进位讯号

198：和(sum)

步骤202至步骤228为本发明一实施例的一实施步骤

步骤302至步骤326为本发明另一实施的一实施步骤

具体实施方式

请参照图1，其是依照本发明一实施例的一种包含分支控制装置的管线微处理器100的一部分方框图。在本实施例中，微处理器100包括一x86结构处理器，而在本实施例中，微处理器100包含一13-阶层管线，包括指令撷取阶层、多重指令快取存取阶层、指令格式化阶层、指令译码或转换阶层、缓存器存取阶层、地址计算阶层、多重数据快取存取阶层、多重执行阶层、储存阶层及写回阶层。

微处理器100包括指令快取区102，用以快取指令字节，经由数据总线166自内存中接收这些指令字节，而指令快取区102包括储存指令字节用的快取线矩阵，此快取线矩阵是由撷取地址152来进行索引，即撷取地址152是在矩阵中选择其中一条快取线，而指令快取区102会经由数据总线142输出被选取的指令字节的快取线。

在本实施例中，指令快取区102包含一个64KB的4-way集合关系型快取，具有每道(way)32-字节的快取线，在本实施例中，指令快取区102一次会提供已选取的指令字节的一半快取线，例如，在每两个间隔周期中，会提供16个字节。在本实施例中，指令快取区102是类似于美国专利案号09/849,736，名称为非实际的分支目标地址快取(SPECULATIVE BRANCH TARGET ADDRESS CACHE)(文件编号CNTR：2021)中所描述的指令快取区，其中此申请案与本发明具有共同的申请人(assignee)，在此也将其申请标的并入本发明作参考。

微处理器100也包含分支目标地址快取区(branch target addresscache；以下简称BTAC)116，此BTAC 116接收指令快取区102的撷取地址152，BTAC 116包括储存元素的矩阵，用以快取目前已执行的分支指令及其相关分支目标地址的撷取地址，而储存的元素也包括其它关于分支指令的理论性分支信息，作为快取的目标地址，特别是，所储存的元素包括多重字节分支指令是否涵盖横跨两个指令快取线的指针。撷取地址152会指向位于BTAC 116中储存元素的矩阵，以选择其中的一个储存元素。

BTAC 116会由撷取地址152，从被选取的储存元素中，输出一个目标地址132及理论性分支信息(speculative branch information；以下简称SBI)136。在本实施例中，SBI 136包括分支指令长度，位于快取线中的分支指令位置，分支指令为呼叫(call)或返回(return)指令，以及分支指令预期发生与否，这些皆在美国专利案号09/849,736，名称为非实际的分支目标地址快取(SPECULATIVE BRANCH TARGETADDRESS CACHE)中有所描述，在此将其申请标的也并入本发明的参考。

BTAC 116也输出一个命中讯号(HIT signal)134，用以指示撷取地址152是否命中BTAC 116，在本实施例中，BTAC 116是类似于上述参考的美国专利案中描述的BTAC，其中，BTAC 116是一个非实际的BTAC，因为微处理器100在指令快取区102提供的指令快取线被译码前，会分支连结到BTAC 116所提供的目标地址132，不论目前在撷取地址选取的快取线中的分支指令是否为已知状态，因此，理论上，微处理器100会分支连结到BTAC 116所提供的目标地址132，即使目前分支指令可能不存在于撷取地址选取以作为命中BTAC 116的快取线中。

BTAC 116也输出一个BWRAP讯号186，用以确认分支指令是否涵盖横跨两个快取线，其中，BWRAP讯号186的值是BTAC 116在分支指令执行后，随着分支指令目标地址而快取得到的，但BWRAP讯号186的值在仅显示上次分支指令是否涵盖横跨快取线的情况下，是非实际的值。然而，如在上述参考的美国专利案中所描述的，在本实施例中，在上次所执行的分支指令或快取线的撷取地址152是虚拟别名的状况中，快取线会被进行修正。

微处理器100也包括控制逻辑122，上述的HIT讯号134、SBI 136以及BWRAP讯号186皆是当作输入讯号输入至控制逻辑122，以下会对控制逻辑122的操作进行更详细的描述。

微处理器100也包括一个多任务器118，此多任务器118在其输入端至少接收三个地址，且会选取其中一个输入地址作为输出至指令快取区102的撷取地址152，以响应从控制逻辑122传送的控制讯号168。多任务器118会自BTAC 116接收目标地址132，也会接收次一循序撷取地址162，此次一循序撷取地址162，为依循指令快取区102的快取线大小而增加，且会由增加器124所接收的撷取地址152以提供至多任务器118。

多任务器118也接收一个分解目标地址(resolved target address)164，由微处理器100中的执行逻辑所提供，此执行逻辑依据分支指令的完整译码来计算分解目标地址164。如果微处理器100在分支连结到BTAC 116提供的目标地址132后，经判断发觉其所分支连结到的地址是错误的，则微处理器100会进行错误修正，由清除(flush)管线以及分支连结至分解目标地址164或是快取线的撷取地址，包括接续于分支指令的指令地址，来进行修正。在本实施例中，如果微处理器100推测判断出在目前的快取线142中没有分支指令，则微处理器100会由清除管线以及分支连结至包括分支指令本身指令地址的快取线撷取地址，来修正错误，此错误修正描述于美国专利案号09/849,658，名称为侦测及修正错误的非实际分支目标地址快取分支的装置、系统及方法(APPARATUS，SYSTEM AND METHOD FOR DETECTING ANDCORRECTING ERRONEOUS SPECULATIVE BRANCH TARGETADDRESS CACHE BRANCHES)(文件编号CNTR：2022)，此案与本发明具有相同的申请人，在此将其申请标的并入本案作参考。

在本实施例中，多任务器118也接收其它来自于分支预测元素预测的目标地址，例如一个呼叫/返回堆栈以及一个分支目标缓冲器(branch target buffer；简称BTB)，其中BTB是依据分支指令指针，快取间接分支指令的目标地址。多任务器118会选择性地使BTAC 116提供的目标地址因呼叫/返回堆栈及BTB提供的目标地址而无效，此在美国专利案号09/849,799，名称为依据分支指令型态由第二预测器使非实际的分支目标地址快取选择性无效(SPECULATIVE BRANCHTARGET ADDRESS VACHE WITH SELECTIVE OVERRIDE BYSECONDARY PREDICTOR BASED ON BRANCH INTRUCTIONTYPE)(文件编号CNTR：2052)，此案与本发明具有相同的申请人，在此将申请标的并入本案作参考。

微处理器100也包括一指令缓冲器112，此指令缓冲器112包括数个阶层、或缓存器，会集体或个别地称为阶层126，以储存自指令快取区102经数据总线142传送的指令字节。在本实施例中，指令缓冲器112会自指令快取区102中一次接收16-字节的快取线，在本实施例中，指令缓冲器112的阶层126是16-字节宽，在本实施例中，指令缓冲器112包含一个由8阶层所组成的128-字节缓冲空间，每个阶层用以储存16个指令字节。图1仅显示指令缓冲器112的较低4层阶层，最底层阶层记为阶层A 126A，下一个阶层是在阶层A 126A的上的阶层B126B，再下一个阶层是在阶层B 126B的上的阶层C 126C，再下下一个阶层是在阶层C 126C的上的阶层D 126D。

指令缓冲器112是由一个具有顶层及底层的先进先出(first-in-first-out)移位缓存器所组成，会自指令快取区102接收指令字节储存于顶层，然后将阶层126移出底层。指令缓冲器112可以一次自底层移出一个或两个阶层126，也就是说，指令缓冲器112可以在一个时脉周期中移出阶层A 126A，或是在一个时脉周期中将阶层A126A及阶层B 126B一起移出。控制逻辑122会提供一个移位讯号，即是用以判断移出指令缓冲器112的阶层126数目，以下将会详述。当指令快取区102提供一个快取限制指令缓冲器112，则快取线会被置入最接近指令缓冲器112底层的未使用阶层126。

微处理器100也包括数个缓存器174，每一个缓存器174储存自BTAC 116传送的目标地址132，每一个缓存器174连接于相对应于指令缓冲器112中的阶层126。图1中即显示连结于阶层126A～D的4个缓存器174A～D，储存于缓存器174的目标地址是被BTAC 116用来预测储存在相连的阶层126中的分支指令。

微处理器100也包括数个缓存器104，每一个缓存器104用以储存自控制逻辑122传送的BTAC分支指针192，每一个缓存器104是对应连接于数个指令缓冲器112的阶层126以及目标地址缓存器174，图1即绘示4个缓存器104A～D对应连接阶层126A～D及目标地址缓存器174A～D，其中，储存于缓存器104的BTAC分支指针192，用以确认微处理器100是否会如推测般，分支连结到自BTAC 116传送且储存于相对应缓存器174的目标地址，进而推测目前相对应阶层126中的分支指令。如果BTAC 116在确认拥有HIT讯号且预期分支指令发生的情况下，微处理器100会分支连结至BTAC 116所提供的目标地址132，在本实施例中，BTAC 116会在SBI 136中提供一个预期讯号，无论分支指令是否会发生，其中一个存在于缓存器104的BTAC分支指针会被提供以作为输出至控制逻辑122的输出讯号193。

在本实施例中，控制讯号122会输出一个16-位值的BTAC分支指针，以储存于缓存器104且会被作为输出讯号193提供至控制逻辑122，这16位(bits)相对应于阶层126的16字节(bytes)，其中具有真值(true value)的位会指出在阶层126中相对应的字节，作为分支指令的第一字节，用以使微处理器100可分支连结至BTAC 116所提供的目标地址132。

微处理器100也包括一个具有3-输入端的阶层置换多任务器106，此阶层置换多任务器106是经由数据总线144A～C，接收自指令缓冲器112分别传送的关于指令字节的三个阶层126A～C。阶层置换多任务器106会依据控制逻辑122产生的控制讯号154，自三个阶层126A～C选择其中一个阶层，关于阶层置换多任务器106的操作将会详述于下。

在本实施例中，每一个数据总线144A～C都是26-字节宽，数据总线144A～C会分别提供阶层126A～C 16个字节，另外，会提供上一个阶层前10个字节做映像(shadow)。以数据总线144A为例，数据总线144A会提供阶层A 126A 16个字节[0∶15]，此外，阶层A 126A的16个字节[0∶15]中的前10个字节[0∶9]会提供给阶层B 126B。

在x86处理器中的指令长度是可变动的，且可能会变为11个字节长，因此，一个11-字节的指令在其第一字节的是阶层A 126A最后一个字节位置的情况下，指令的最后10个字节会是在阶层B 126B的前10个字节位置。进一步地说，由所提供的16-字节及上一个阶层的10-字节映像，阶层置换多任务器106会提供足够的指令字节，以确保目前至少有一个完整的x86指令会被数据总线144A～C其中的一所选取，不管在26-字节的数据总线144中的下一个指令是从何处开始。

微处理器100也包括一个字节智能型排列多任务器(byte-wisealignment mux)108，此字节智能型排列多任务器108所接收的指令字节，是阶层置换多任务器106经由数据总线146自其中的一个总线144A～C选取得到。在本实施例中，字节智能型排列多任务器108包括一组多任务器，用以排列自阶层置换多任务器106接收的指令字节，使得下一个字节被格式化，例如，下一个被格式化指令的第一个字节，会被输出在11-字节的数据总线148的第一字节线上。字节智能型排列多任务器108依据控制逻辑122产生的控制讯号156来排列字节，控制逻辑122则是依据现行指针(current pointer)讯号158来产生控制讯号156，其中现行指针讯号158会指向下一个被格式化指令的第一字节。

举例来说，假设最后一个被格式化指令的最后一个字节是在数据总线146的字节3中，则下一个被格式化指令的第一字节会是在数据总线146的字节4中。字节智能型排列多任务器108会从数据总线146排列字节，使得数据总线146的字节4会被提供于数据总线148的字节0上，数据总线146的字节5会被提供于数据总线148的字节1上，直至四次上升排列，使得字节14被提供于数据总线148的字节10为止。

微处理器100也包括指令格式化逻辑114，是接收指令缓冲器112经由数据总线148传送的指令字节，此指令格式化逻辑114会检查，或审视，指令缓冲器112的阶层126以及相关的映像内容，这些内容是由阶层置换多任务器106所选取，以及由字节智能型排列多任务器108进行排列。指令格式化逻辑114会将接收到的指令字节进行格式化，或分析，为指令，特别是，指令格式化逻辑114会决定指令的字节大小。指令格式化逻辑114会提供已格式化指令给剩余的微处理器100管线，用以更进一步的译码及执行，而指令缓冲器112为了减少指令格式化逻辑114饥饿的可能性，会暂存指令字节。

指令格式化逻辑114会经由控制讯号172，提供目前已格式化的指令长度。在本实施例中，指令长度172包括4个位，会由控制逻辑172(改为122)产生的控制讯号188，来控制指令缓冲器112的移位，即，控制讯号188会为指令缓冲器112供应如移位计数的服务，而控制逻辑122也会利用移位计数188来控制指令字节至指令缓冲器112的加载。

在本实施例中，指令格式化逻辑114可以在每个处理器100的时脉周期中格式化多重指令，而指令长度讯号172会显示多重格式化指令的指令长度和(sum)。在本实施例中，指令长度讯号172上所显示的最大和(sum)是15字节。

也就是，阶层置换多任务器106会提供一个装置，让指令格式化逻辑114可以得到最适的指令字节阶层126，用以格式化而不需指令缓冲器112位移已格式化的阶层126。然后，自指令缓冲器112位移一个阶层126的时间，就会从提供阶层126至指令格式化逻辑114所减少的时间而来，而这对微处理器在时脉的时间上是相当有助益的。

微处理器100也包括缓存器184，用以储存及输出现行指针158，此现行指针158用以确认在指令缓冲器112阶层126中的位置，是目前被指令格式化逻辑114格式化的指令，也即现行指针158会指向被指令格式化逻辑114格式化指令的第一字节。另，现行指针158也会被提供给控制逻辑122，而控制逻辑122会利用现行指针158产生控制讯号154、156及188。在本实施例中，现行指针158包括4个位，用以确认任一16字节是在其中的一指令缓冲器112的阶层126中。

微处理器100也包括加法器182，用以接收指令长度172及现行指针158，以及产生它们的和(sum)198。如果下一个指令是循序的，例如目前被格式化指令不是一个发生的分支指令，则指令长度172及现行指针158的和198即是次一指针198，或是指向下一个被格式化指令的指针。

次一指针198是提供给多任务器128，而此多任务器128也接收储存于其中一个缓存器174的目标地址的较低4个位，且缓存器174是关联于阶层置换多任务器106所选取的阶层126。如果BTAC分支指针193显示目前格式化指令并非一发生分支指令，则控制逻辑122会控制多任务器128去选取次一指针198，但如果BTAC分支指针193显示目前格式化指令是一发生分支指令，则控制逻辑122会控制多任务器128选择自缓存器174传送的目标地址138，即分支指令会使微处理器100分支连结到BTAC116所提供的目标地址132。其中，多任务器128的输出会储存于现行指针缓存器184中。

加法器182也会产生进位讯号(carry signal)196，而进位讯号196在现行指针158及指令长度172的和为真时会产生一个进位，特别是，进位讯号196会显示目前格式化指令的一个字节是否有占据现阶层126的最后一个字节。举例来说，假设目前格式化指令是开始于选取阶层126的字节13，例：现行指针158是0xD，然后假设指令格式化逻辑114决定目前格式化指令有一个3字节的指令长度172，例：此指令占据阶层126的字节13、14及15是阶层126的最后3个字节，而在本例中，现行指针158及指令长度172的和为0x10，因此，加法器182产生的次一指针198即会是0x0，且进位196会是1，或真值。

相比之下，假设目前格式化指令是开始于字节12，即指令会占据阶层126字节位置12、13及14，但不是字节位置15。在这个情况中，和是0xF，因此，次一指针198是0xF，而进位196的值是0，或伪值。进位讯号196是提供至控制逻辑122，而控制逻辑122会利用进位讯号196产生控制讯号154、156及188。

微处理器100也包括比较器(comparator)178，用以接收次一指针198及将次一指针198与0进行比较，如果次一指针198不等于0，则比较器178会输出真值(true value)，但如果次一指针198等于0，则比较器178会输出伪值(false value)。

比较器178输出的值会提供给与门(AND gate)176，且与门176也会接收进位讯号196。另，与门176输出的讯号是一个涵盖讯号(fwrapsignal)194，用以显示目前格式化指令所涵盖的阶层126是否如指令格式化逻辑114所决定的。举例来说，假设目前被格式化指令是开始于所选取阶层126的字节13，例现行指针158是0xD，然后假设指令格式化逻辑114决定目前格式化指令有一个3字节的指令长度172，假设此指令占据阶层126的字节13、14及15是阶层126的最后3个字节。在此例中，现行指针158及指令长度172的和为0x10，因此，加法器182产生的次一指针198即会是0x0，进位196是1，或真值。而由于次一指针198等于0(非不等于0)，则比较器178的输出值为伪值(false value)，接下来，由于与门176的其中一个输入讯号(即比较器178的输出讯号)为伪值，因此涵盖讯号194会是伪值。

相比之下，假设目前格式化指令是开始于字节14，即假设指令的前两个字节占据阶层中的后两个字节位置，而指令的最后一个字节会占据下一个阶层上的第一字节位置。在这种情况中，和是0x11，因此，次一指针198是0x1，而进位196的值为真，由于次一指针198不等于0，即非并不等于0，因此比较器178的输出值为真值(true value)，接下来，由于比较器178的输出讯号为真且进位讯号196也为真，因此涵盖讯号194也为真。

涵盖讯号(fwrap signal)194会提供至控制逻辑122，而控制逻辑122会利用涵盖讯号194产生控制讯号154、156及188。由于涵盖讯号194是依据指令字节在阶层126中译码而来，因此涵盖讯号194会提供一个真实指示于格式化指令是否有涵盖横跨于两个指令缓冲器112阶层126，相比之下，BWRAP讯号186是在指令译码前产生出来，因此BWRAP讯号186会提供一个非实际指示于分支指令是否有涵盖横跨两个快取线。

请参考图2，是本发明依据图1关于指令缓冲器112动作的流程图，此流程开始于步骤202。

在步骤202中，图1中的次一循序撷取地址162是由图1的多任务器118选取，作为图1的撷取地址152，以提供给图1的指令快取区102及图1的BTAC 116。接着，流程程序自步骤202至步骤204。

在步骤204中，指令快取区102会输出快取线于图1的数据总线142，此快取线是由步骤202提供的撷取地址所选取。接着，流程程序自步骤204至步骤206。

在步骤206中，经由步骤204的指令快取区所输出的已选取快取线，会被储存于指令缓冲器112，且此快取线是储存在接近指令缓冲器112底层的第一未使用阶层126。此已选取快取线包括一个分支指令，为BTAC 116快取的目标地址。接着，流程程序自步骤206至步骤208。

在判断步骤208中，控制逻辑122会判断BTAC 116的分支是否发生，即，控制逻辑122会检测BTAC HIT讯号134，以判断撷取地址152对在步骤202的BTAC 116是否发生命中情形，以及与BTAC 116输出的目标地址132有关联的分支指令，是否有预期性的发生。如果没有，则流程会返回步骤202以撷取下一个循序快取线，否则流程会进行至步骤212。

在步骤212中，目标地址132会由BTAC 116输出以储存在其中一个缓存器174，此缓存器174是与步骤206分支指令所储存的阶层126有关联。另外，控制逻辑122会输出一个具有真值的BTAC分支指针192，此BTAC分支指针192是储存在其中一个缓存器104，而此缓存器104是与步骤206分支指令储存的阶层126有关联。在本实施例中，BTAC分支指针192中的位与阶层126分支指令的第一字节有关联，此位值为真，表示微处理器100会分支连结到将在步骤224中发生且由BTAC 116所提供的目标地址132。接着，流程从步骤212至判断步骤214继续进行。

在判断步骤214中，控制逻辑122会判断BTAC 116是否预期分支指令会涵盖横跨快取线，也就是，图1的控制逻辑122会判断图1的BWRAP讯号是否为真，如果是，则流程会进入步骤216，否则流程会进入步骤224。

在步骤216中，次一循序撷取地址162会提供至指令快取区102。如果流程进到步骤216，而目前只有分支指令的第一部份储存在步骤206的指令缓冲器112的快取线中，则此情形会由步骤214中的BWRAP讯号186来表示，也就是说，这个分支指令字节的第二部份还没有被指令快取区102输出以储存至指令缓冲器112内。因此，有必要在分支指令的第二部分被指令快取区102输出以储存在指令缓冲器112后，才可将BTAC 116所提供的目标地址132应用于指令缓冲区102中。流程自步骤216至步骤218继续进行。

在步骤218中，指令快取区102输出由步骤216提供的次一循序撷取地址162所选取的快取线，所输出的快取线包括非实际BWRAP讯号186所指示的分支指令第二部份。流程自步骤218至步骤222继续进行。

在步骤222中，包含分支指令第二部分的快取线，是储存于指令缓冲器112中，其中，包含分支指令第二部分的快取线储存于指令缓冲器112的阶层126中，而紧连的上一层阶层126中，则是包含分支指令的第一部分。流程自步骤222至步骤224继续进行。

在步骤224中，多任务器118选取BTAC 116提供的目标地址132。作为下一个指令快取区102的撷取地址152，在此，整个分支指令已储存于指令缓冲器112中。如果，流程是从判断步骤214至步骤224，则分支指令是包含在指令缓冲器112中的一个阶层126，如果，流程是从步骤222至步骤224，则分支指令是包含在指令缓冲器112中两个紧邻的阶层126。流程自步骤224至步骤226继续进行。

在步骤226中，指令快取区102输出的快取线，是由目标地址132因应步骤224的指令快取区102而选取，所选取的快取线，包括分支指令的目标指令，或指令集。流程自步骤226至步骤228继续进行。

在步骤228中，包含目标指令的快取线是储存于指令缓冲器112中，其中，包含目标指令的快取线会储存于指令缓冲器112的阶层126中，而紧接在上一层的阶层126是包含整个分支指令或是分支指令的第二部分，则是依据分支指令是否涵盖横跨多重快取线而定。流程自步骤228返回至步骤202进行。

请参考图3，是本发明依据图1的指令缓冲器112的阶层126的选择的一流程图。流程开始于步骤302。

在步骤302中，图1的指令格式化逻辑114，格式化图1指令缓冲器112的阶层A 126A中的指令，而指令格式化逻辑114是对图1的现行指针158指向的指令进行格式化，且会产生指令在图1的指令长度172。流程自步骤302至步骤304进行。

在步骤304中，图1的加法器182会将指令长度172加向现行指针158，以产生图1的次一指针198及图1的进位讯号196，且与门176会产生图1的涵盖讯号(fwrap signal)194。另外，储存于缓存器104A的BTAC分支指针会被输出在图1的BTAC分支指针讯号193上。流程自步骤304至步骤306进行。

在判断步骤306中，控制逻辑122会判断步骤302的格式化指令，是否为图2步骤224微处理器100分支连结的分支指令，即，控制逻辑122会判断步骤304的BTAC分支指针193是否为真。在本实施例中，控制逻辑122会判断在BTAC分支指针193中，与现行指针158相对应的位是否为真，如果不是，则流程会进到判断步骤308，否则流程会进行到判断步骤316。

在判断步骤308中，控制逻辑122会判断进位讯号196是否为真，如果不是，则流程会进到步骤312，否则流程会进行到步骤314。

在步骤312中，控制逻辑122会产生控制讯号154，以控制图1的阶层置换多任务器106选取阶层A 126A，使阶层A 126A提供于数据总线146中，进一步让指令格式化逻辑114进行格式化。另外，控制逻辑122会在移位讯号188上产生0的值。流程自步骤312至步骤324进行。

在步骤314中，控制逻辑122产生控制讯号154以控制图1的阶层置换多任务器106选取阶层B 126B，使阶层B 126B提供于数据总线146中，以进一步让指令格式化逻辑114进行格式化。另外，控制逻辑122会在移位讯号188上产生1的值。流程自步骤314至步骤324进行。

在判断步骤316中，控制逻辑122会判断图1的涵盖讯号194是否为真，如果不为真，则流程进入步骤318，否则，流程进入步骤322。

在步骤318中，控制逻辑122产生控制讯号154以控制图1的阶层置换多任务器106选取阶层B 126B，使阶层B 126B提供于数据总线146中，以进一步让指令格式化逻辑114进行格式化。另外，控制逻辑122会在移位讯号188上产生1的值。接着，流程自步骤318至步骤324进行。

在步骤322中，控制逻辑122会产生控制讯号154，以控制图1的阶层置换多任务器106选取阶层C 126C，以提供于数据总线146上，作为指令格式化逻辑114格式化的用。此外，控制逻辑122还会产生值为2的移位讯号188。接着，流程自步骤322至步骤324进行。

在步骤324中，对现行指针158进行更新，即，图1的多任务器128会选取图1的次一指针198或是目标地址138，且会储存选取的值于缓存器184中。如果流程是由步骤312或314而来，则多任务器128会选取次一指针198，否则，多任务器128会选取目标地址138。另外，指令格式化逻辑114会格式化已更新现行指针158指向的指令，其中，已更新现行指针158所在的阶层，由步骤312、314、318或322的阶层置换多任务器106选取而得。流程自步骤324至步骤326进行。

在步骤326中，指令缓冲器112会在312、314、318或322的步骤中，位移移位讯号188确认的阶层数目，使得阶层A又可再次位于指令缓冲器112的底层，且指令缓冲器112会在阶层置换多任务器106选取适当的阶层126以提供指令格式化逻辑114后，才位移确认的阶层数目。

请合并参考图4A～F，一同作为图4来参考，是本发明的图1依据图3的指令缓冲器112阶层126选取的6个数据表例子。在图4的每个数据表中包括4列，相对应于指令缓冲器112的阶层A～D 126A～D，且以这些阶层名称为卷标，每一个数据表包括16行，相对应每个阶层126的16个位位置，从左而右分别标示0至15。在数据表中的每个单位(cell)不是空白的，就是被移植关于指令字节的内容。有三个不同的指令常被用来说明：3-字节ADD(x86加法指令)、4-字节SUB(x86减法指令)及2-字节JCC(x86条件式跳跃指令、或是分支指令)，每个指令的字节会以括号圈住数字来标示相对应的指令字节。例如，“SUB[2]”表示为第3字节，是SUB指令的字节2。

这6个不同的数据表即是说明6个关于目前格式化指令的不同组合内容，包括分支/非分支、涵盖讯号194真/伪值，以及进位讯号196真/伪值。在每个情形中，现行指针158、指令长度172、BTAC分支指针193及目标地址138较低4个位的初始条件值皆为确定的值。此外，次一指针198、进位讯号196及涵盖讯号194的值，在每个状况中，由图1的控制装置从初始条件值产生而来，而由阶层置换多任务器106选取的指令缓冲器112阶层，以及由控制逻辑122产生的移位讯号值188，皆会在每个情况中，显示于响应初始条件值及所产生的值中。虽然在图4的实施例中，字节因此大印地安格式(big-endian)存放，但在其它的实施例中，微处理器100可为小印地安(little-endian)的微处理器100，在图4中会显示字节的相反编号。

图4A即是说明状况1，目前格式化指令是一个非分支指令(non-branch)，并没有涵盖横跨两个指令缓冲器112阶层，且也没有占据阶层的最后一个字节，3-字节的ADD指令是位于阶层A 126A的字节8～10，而4-字节的SUB指令是位于阶层A 126A的字节11～14。现行指针158的值为8，指向ADD指令的第一字节，且由指令格式化逻辑114在图3的步骤302中所产生的指令长度172为3，BTAC分支指针193在图3的步骤304所输出的值为伪(false)，另外，由于目前格式化指令并非分支指令，因此在步骤324输出的目标地址138是非可应用的值。

在图3的步骤304中，由加法器182产生的次一指针198的值为11，加法器182产生的进位讯号196的值为伪，且由与门176产生的涵盖讯号194也为伪值。因为目前格式化指令是一个非分支指令，并不会占据其阶层的最后字节，因此下一个被指令格式化逻辑114格式化的指令，会开始于与目前格式化指令相同的阶层。接着，控制逻辑122会控制阶层置换多任务器106选择阶层A 126A，且位移0个阶层，这个动作是对应图3的步骤312。

图4B即是说明状况2，目前格式化指令是一个非分支指令(non-branch)，并没有涵盖横跨两个指令缓冲器112阶层，但却占据阶层的最后一个字节。其中，3-字节的ADD指令是位于阶层A 126A的字节13～15，而4-字节的SUB指令是位于阶层B 126B的字节0～3。现行指针158的值为13，指向ADD指令的第一字节，且由指令格式化逻辑114在图3的步骤302中所产生的指令长度172为3，而BTAC分支指针193在步骤304所输出的值为伪(false)，另外，由于目前格式化指令并非分支指令，因此在步骤324输出的目标地址138是非可应用的值。

在图3的步骤304中，由加法器182产生的次一指针198的值为0，加法器182产生的进位讯号196的值为真，且由与门176产生的涵盖讯号194是为伪值。因为目前格式化指令是一个会占据其阶层的最后字节的非分支指令，因此下一个被指令格式化逻辑114格式化的指令会开始于目前被格式化指令的上一层阶层。接着，控制逻辑122会控制阶层置换多任务器106选择阶层B 126B，且位移1个阶层，这个动作是对应图3的步骤314。

图4C即是说明状况3，目前格式化指令是一个非分支指令(non-branch)，此非分支指令涵盖横跨两个指令缓冲器112阶层，且占据阶层的最后一个字节。其中，3-字节的ADD指令的前两个字节是位于阶层A 126A的字节14～15，而3-字节的ADD指令的第三字节是位于阶层B 126B的字节0，另，4-字节的SUB指令是位于阶层B 126B的字节1～4。现行指针158的值为14，指向ADD指令的第一字节，且由指令格式化逻辑114在图3的步骤302中所产生的指令长度172为3，而BTAC分支指针193在步骤304所输出的值为伪(false)，另外，由于目前格式化指令并非分支指令，因此在步骤324输出的目标地址138是非可应用的值。

在图3的步骤304中，由加法器182产生的次一指针198的值为1，加法器182产生的进位讯号196的值为真，与门176产生的涵盖讯号194也为真值。因为目前格式化指令是一个会占据其阶层的最后字节的非分支指令，因此下一个被指令格式化逻辑114格式化的指令会开始于目前被格式化的指令的上一层阶层。接着，控制逻辑122会控制阶层置换多任务器106选择阶层B 126B，且位移1个阶层，这个动作是对应图3的步骤314。

图4D是说明状况4，目前格式化指令是一个分支(branch)指令，并没有涵盖横跨两个指令缓冲器112阶层，且也没有占据阶层的最后一个字节，2-字节的JCC指令是位于阶层A 126A的字节7～8，而4-字节的SUB指令是分支指令的目标指令，位于阶层B 126B的字节11～14。现行指针158的值为7，指向JCC指令的第一字节，且由指令格式化逻辑114在图3的步骤302中所产生的指令长度172为2，另外，由于阶层A 126A的字节7包含JCC指令的第一字节，且此分支指令是目前BTAC 116分支的指令，因此，BTAC分支指针193的位7在图3的步骤304所输出的值为真(true)，而在步骤324输出的目标地址138是11，用以指向目标指令。

在图3的步骤304中，由加法器182产生的次一指针198的值为9，然而，由于BTAC分支指针193的值为真，因此多任务器128会选择值为11的目标地址138。而加法器182产生的进位讯号196的值为伪，且由与门176产生的涵盖讯号194也为伪值。另外，虽然目前格式化指令是一个没有涵盖横跨两个指令缓冲器112阶层的分支指令，但下一个被指令格式化逻辑114格式化的指令，即目标指令，却会开始于目前被格式化指令的上一层阶层。接着，控制逻辑122会控制阶层置换多任务器106选择阶层B 126B，且位移1个阶层，这个动作是对应图3的步骤318。

图4E是说明状况5，即目前格式化指令是一个分支指令，并没有涵盖横跨两个指令缓冲器112阶层，但却占据阶层的最后一个字节。其中，2-字节的JCC指令是位于阶层A 126A的字节14～15，而4-字节的SUB指令是分支指令的目标指令，位于阶层B 126B的字节11～14。现行指针158的值为14，指向JCC指令的第一字节，且由指令格式化逻辑114在步骤302中所产生的指令长度172为2，另外，由于阶层A126A的字节14包含JCC指令的第一字节，且此分支指令是目前BTAC116分支的指令，因此，BTAC分支指针193的位14在步骤304所输出的值为真(true)，而在步骤324输出的目标地址138是11，用以指向目标指令。

在图3的步骤304中，由加法器182产生的次一指针198的值为0，然而，由于BTAC分支指针193的值为真，因此多任务器128会选择值为11的目标地址138。而加法器182产生的进位讯号196的值为真，但由与门176产生的涵盖讯号194是为伪值。另外，虽然目前格式化指令是一个没有涵盖横跨两个指令缓冲器112阶层的分支指令，但下一个被指令格式化逻辑114格式化的指令，即目标指令，却会开始于目前被格式化指令的上一层阶层。接着，控制逻辑122会控制阶层置换多任务器106选择阶层B 126B，且位移1个阶层，这个动作是对应图3的步骤318。

图4F即是说明状况6，目前格式化指令是一个分支指令，且涵盖横跨两个指令缓冲器112阶层。其中，2-字节的JCC指令的前一个字节是位于阶层A 126A的字节15，而2-字节的JCC指令的第二字节是位于阶层B 126B的字节0，另，4-字节的SUB指令是此分支指令的目标指令，位于阶层C 126C的字节11～14。现行指针158的值为15，指向JCC指令的第一字节，且由指令格式化逻辑114在图3的步骤302中所产生的指令长度172为2，另外，由于阶层A 126A的字节15包含JCC指令的第一字节，且此分支指令是目前BTAC 116分支的指令，因此，BTAC分支指针193的位15在步骤304所输出的值为真(true)，而在步骤324输出的目标地址138是11，用以指向目标指令。

在图3的步骤304中，由加法器182产生的次一指针198的值为1，然而，由于BTAC分支指针193的值为真，因此多任务器128会选择值为11的目标地址138。而加法器182产生的进位讯号196的值为真，且由与门176产生的涵盖讯号194也为真。因为目前格式化指令是一个涵盖横跨两个指令缓冲器112阶层的分支指令，因此下一个被指令格式化逻辑114格式化的指令，即目标指令，会开始于目前格式化指令的上两层阶层。接着，控制逻辑122会控制阶层置换多任务器106选择阶层C 126C，且位移2个阶层，这个动作是对应图3的步骤322。

虽然本发明已以实施例说明如上，然其并非用以限定本发明，举例来说，指令缓冲器的宽度及储存空间是可变换的，也就是说，本发明可以使用较大宽度及储存空间的指令缓冲器进行操作。

任何熟悉此技术者，在不脱离本发明的精神和范围内，当可作各种的更动与润饰，因此本发明的保护范围当以权利要求书为准。