संकलन। 8: अनुकूलन

सुखद प्रवास के बाद, हम अपनी जे-स्क्रिप्ट के लिए एक कंपाइलर लिखना जारी रखते हैं।
पिछली पोस्ट में, हमने रजिस्टर असाइनमेंट के लिए सीलिंग से लिया गया एक अनुमान लगाया और उसी समय कोड को ऑप्टिमाइज़ करना शुरू किया। और इससे पहले, पाठकों ने असाइनमेंट के कार्यान्वयन में एक बग पाया ।

पोस्ट में आगे:

1. एक बग को ठीक करना
2. सफाई की प्रतियां
3. क्या हुआ था?
4. तह लगातार
5. कार्यान्वयन

एक बग को ठीक करना

तथ्य यह है कि हमने धोखा देने का फैसला किया है, और जब पहली बार वैरिएबल को मान प्रदान करते हैं, तो वास्तव में कॉपी नहीं करते हैं, लेकिन बस मध्यवर्ती मान के साथ रजिस्टर को वेरिएबल के लिए भंडारण स्थान के रूप में घोषित करते हैं:
ID '=' EXPR { $$ = $3 ;
if (vars[ $1 ])
emit(command::add, vars[ $1 ], $3 , 0 );
else
vars[ $1 ] = $3 ; // new var
}

फिर, जब टाइप a=2; संचालन को संकलित किया जाता है a=2; हम एक MOV R1, 2 कमांड MOV R1, 2 (कनवल्शन 2 से) प्राप्त करते हैं और vars["a"]=R1 (असाइनमेंट कनवल्शन से) याद करते हैं।
सब कुछ सत्य, सरल और स्वाभाविक है।

समस्या तब पैदा हुई, जब असाइनमेंट के दाईं ओर, एक मध्यवर्ती मूल्य का उपयोग नहीं किया गया था, लेकिन कुछ लंबे समय तक रहने वाले: उदाहरण के लिए, एक और चर।

 a = 2;
 बी = ए;

असाइनमेंट के दूसरे कनवल्शन में, कोई नया कोड उत्पन्न नहीं होता है - बस याद रखें vars["b"]=R1
दोनों चर एक ही रजिस्टर में थे, और जब उनमें से एक बदल जाएगा, तो दूसरा बदल जाएगा।

समाधान सतह पर स्थित है: प्रत्येक नए चर के लिए हम एक नया रजिस्टर शुरू करते हैं।
ID '=' EXPR { $$ = $3 ;
if (!vars[ $1 ]) vars[ $1 ] = newreg();
emit(command::add, vars[ $1 ], $3 , 0 );
}

फिर a=2; टीमों के एक जोड़े को मिलता है

 MOV R1, 2
 ADD R2, R1, 0

और vars["a"]=R2 याद रखें vars["a"]=R2
यदि b = a; द्वारा पीछा किया जाता b = a; - फिर MOV R3, R2, 0 और vars["b"]=R3 को कोड में जोड़ा जाएगा

दूसरे शब्दों में, अब उत्पन्न कोड में रजिस्टर से रजिस्टर करने के लिए बहुत सारी अतिरिक्त प्रतियां होंगी, और रजिस्टरों का उद्देश्य भी धीमी गति से काम करेगा - इस तथ्य के कारण कि प्रयुक्त रजिस्टरों की संख्या बढ़ रही है।
हम उन मामलों को खोजने की कोशिश करेंगे जहां नकल अनावश्यक है (उदाहरण के लिए, यदि असाइनमेंट के दाईं ओर से चर भविष्य में नहीं बदलता है), और प्रतिलिपि का उपयोग करने वाले आदेशों को ठीक करें ताकि वे मूल का उपयोग करें।

सफाई की प्रतियां

प्रतिलिपि उन्मूलन सरल अनुकूलन में से एक है जिसे मैंने श्रृंखला के पहले पद से वादा किया था । रजिस्टर असाइनमेंट के दौरान किए गए अनुकूलन के साथ, डेटा-प्रवाह विश्लेषण सफाई के लिए सुविधाजनक है। डीएफए के दो पिछले अनुप्रयोगों से एक महत्वपूर्ण अंतर (जीवित रजिस्टरों का पता लगाने के लिए वापस जाना, सहेजे गए रजिस्टरों को खोजने के लिए आगे बढ़ना) यह होगा कि प्रत्येक बिंदु पर हम रजिस्टरों के एक सेट को स्टोर नहीं करते हैं, लेकिन सभी रजिस्टरों को एक ही के सेट में विभाजित करते हैं। आप इसे पहले से चर्चा किए गए दो की तुलना में डीएफए के अधिक सामान्य मामले के रूप में देख सकते हैं। (इससे पहले, रजिस्टरों को हमेशा दो सेटों में विभाजित किया गया था - "शामिल" और "बाहर रखा गया।")

हम रजिस्टरों को कैसे विभाजित करेंगे?

• ADD RA, RB, 0 कमांड ADD RA, RB, 0 RA को RB के सेट पर स्थानांतरित करता है;
• किसी भी अन्य मामले को बदलने की कमान इसे एक सिंगलटन सेट पर ले जाती है;
• RA और RB टीम सी में एक साथ होंगे यदि वे सभी टीमों में एक साथ हैं जहां से आप सी (सीधे या कूद कर) जा सकते हैं।

अंतिम विभाजन प्राप्त करने के बाद, यह देखा जाएगा कि प्रतिलिपि के बजाय मूल का उपयोग कहां किया जा सकता है: RA बजाय RA आप RB उपयोग कर सकते हैं यदि वे सभी टीमों में एक साथ हैं जहां RA उपयोग किया जाता है।

और एक और सूक्ष्मता: जब से हम टीम से टीम में जाते हैं तो हम सेट का निर्माण नहीं करते हैं, लेकिन ट्रंकट (सभी आवक सेटों को काटते हैं), डीएफए शुरू करने से पहले, आपको सेट को खाली नहीं करने की आवश्यकता है, लेकिन व्यापक रूप में - और जैसा कि एल्गोरिथ्म काम करता है, सेट को छोटा कर दिया जाता है, जैसा कि आवश्यक। पैसा खर्च न करने और वास्तव में हर टीम में सभी मौजूदा रजिस्टरों के सेट को रखने के लिए, हम इस तरह के एक व्यापक सेट की ओर इशारा करते हुए "लापता पुनरावृत्ति" पर विचार करने के लिए सहमत होंगे।

सुविधा के लिए, हम उन तीन परिचालनों को प्रारूपित करते हैं जिनकी हमें एक वर्ग में विभाजन पर आवश्यकता होती है। विभाजन में, हम उन सेटों की सूची को संग्रहीत करते हैं जिनमें रजिस्टरों को विभाजित किया जाता है ("वैश्विक" सेट को छोड़कर, जिसमें रजिस्टरों को शुरू में एक साथ रखा जाता है), और प्रत्येक रजिस्टर के लिए ("वैश्विक" सेट में उन लोगों को छोड़कर), सेट का एक इटेटर जिसमें यह स्थित है ।

मुझे ट्री std::set साथ कुछ अजीब समस्याएं थीं, इसलिए मैंने खुद को bit::set लिखा bit::set कंटेनर को एक समान इंटरफ़ेस के साथ, लेकिन std::bitset साथ std::bitset अंदर। टेम्प्लेट पैरामीटर द्वारा, यह सेट में अधिकतम महत्वपूर्ण मान लेता है।
उसी समय, bit::set में सेट ( &= , |= ) पर मानक संचालन होते हैं।

typedef bit::set<regnum, 255 > regset;

class regPartition {
typedef std::list<regset> regsets;
regsets sets;
std::map<regnum, regsets::iterator> byreg;
// : ""

public :
// :
bool add(regnum copy, regnum orig) {
if (byreg.count(copy)) {
if (byreg[copy]==byreg[orig]) //
return false ;
byreg[copy]->erase(copy);
// ?
if (!byreg[copy]->size())
sets.erase(byreg[copy]);
}
assert(byreg.count(orig));
byreg[copy] = byreg[orig];
byreg[copy]->insert(copy);
return true ;
}

void remove(regnum r) {
if (byreg.count(‌r)) {
if (byreg[r]->size()== 1 ) return ; //
byreg[r]->erase(‌r);
}
byreg[r] = sets.insert(sets.end(), regset());
byreg[r]->insert(‌r);
}

// :
bool isect( /* const */ regPartition& p, const command& self) {
bool changed = false ;
// , p
foreach(i, byreg) {
regnum r = i->first;
// split by p.byreg[r]
regsets::iterator withR = i->second,
withoutR = sets.insert(sets.end(), regset());
foreach2(j, (*withR), next)
// , -- mov :
//
if (!(self.opcode==command::add && !self.src2 &&
((self.src1==r && self.dest==*j)||(self.dest==r && self.src1==*j)))
&&((!p.byreg.count(‌r) && p.byreg.count(*j)) || // R in global, J isn't
(p.byreg.count(‌r) && !p.byreg[r]->count(*j)))) { // R not in global
withR->erase(*j);
withoutR->insert(*j);
byreg[*j] = withoutR;
}
if (!withoutR->size()) //
sets.erase(withoutR);
else //
changed = true ;
}
// , this, p
foreach(i, p.sets) {
regset inP;
foreach(j, (*i))
if (!byreg.count(*j)) inP.insert(*j);
if (inP.size()) {
regsets::iterator newSet = sets.insert(sets.end(), inP);
foreach(j, inP) byreg[*j] = newSet;
changed = true ;
}
}
return changed;
}

// : r ( )
void apply(regnum r, regset& global) {
if (!r) return ; // may not be replaced
assert(byreg.count(‌r));
if (!global.size()) // uninitialized set
global = *byreg[r];
else // initialized; intersect
global &= *byreg[r];
}
}

struct commandn एक नया फ़ील्ड regPartition copies; जोड़ें regPartition copies;
अब हम डीएफए को सामान्य तरीके से लागू करते हैं, तैयार किए गए कार्यों का उपयोग करते हुए:
void copies() {
// )
bool changed = false ;
foreach(i, pcode) {
i->copies = regPartition();
// rule 2
if (writesdest(i)) {
i->copies.remove(i->cmd.dest);
changed = true ;
}
}
while (changed) {
changed = false ;
foreach2(i, pcode, next) {
// rule 1
if (i->cmd.opcode==command::add && !i->cmd.src2)
changed |= i->copies.add(i->cmd.dest, i->cmd.src1);
// rule 3 (next command)
if (hasnext(i))
changed |= next->copies.isect(i->copies, next->cmd);
// rule 3 (jmp target)
if (i->cmd.opcode==command::jz)
changed |= i->tgt->copies.isect(i->copies, i->tgt->cmd);
}
}
// )
std::vector<regset> copies(lastreg+ 1 );
foreach(i, pcode) {
if (readsdest(i))
i->copies.apply(i->cmd.dest, copies[i->cmd.dest]);
if (has2src(i)) {
i->copies.apply(i->cmd.src1, copies[i->cmd.src1]);
i->copies.apply(i->cmd.src2, copies[i->cmd.src2]);
}
}
// )
for (regnum r= 1 ; r<=lastreg; r++) {
copies[r].erase(‌r);
if (copies[r].size()) { // ?
regnum s = *(copies[r].begin()); // r s
foreach(i, pcode) { //
if (i->cmd.dest==r)
i->cmd.dest = s;
if (has2src(i)) {
if (i->cmd.src1==r) i->cmd.src1 = s;
if (i->cmd.src2==r) i->cmd.src2 = s;
}
if (i->cmd.opcode==command::add && i->cmd.src1==i->cmd.dest && !i->cmd.src2) // self-mov
nopOut(i);
}
foreach(c, copies) //
if (c->count(‌r)) {
c->erase(‌r);
c->insert(s);
}
}
}
}
कॉल copies(); आजीविका की जांच करने से पहले, अनुकूलन चक्र की शुरुआत में डालें।

क्या हुआ था?

पिछली बार की तुलना में, कोड को कुछ और कमांड द्वारा कम किया गया था:

 00 mov r01,0
 01 Mov r02, 0x3e8
 02 इको 0x126
 ०३ इको आर ०१
 04 गूंज 0xa0
 ०५ इको आर ०२
 06 इको 0xa7
 07 ले r03, r01, r02
 08 jz r03, + 0x1d (= 0x26)
 09 जोड़ें r03, r01, r02
 ० ए मू र ०४, २
 0b div r03, r03, r04
 0c इको 0x162
 0d इको r03
 0 इको 0xcc
 0f इनपुट r04
 10 स्टोर r01, 1
 11 मूव r01, 1
 12 eq r01, r04, r01
 13 jz r01, +4 (= 0x18)
 14 लोड r01, 1
 15 मूव r02, 1
 16 उप r02, r03, r02
 17 jz 0, -0x11 (= 0x7)
 18 मूव r01, 2
 19 eq r01, r04, r01
 1a jz r01, +3 (= 0x1e)
 1 बी मूव आर 01, 1
 1 सी जोड़ें r01, r03, r01
 1d jz 0, -0x17 (= 0x7)
 1e लोड r01, 1
 1 एफ Mov r03, 3
 20 eq r03, r04, r03
 21 jz r03, +2 (= 0x24)
 22 प्रतिध्वनि 0x146
 23 घंटे
 24 गूंज 0x16a
 25 jz 0, -0x1f (= 7)
 26 प्रतिध्वनि 0xff
 27 घंटे

ऐसा प्रतीत हो सकता है कि गायब कमांड के बारे में ( add r01, r01, 0 add r02, r02, 0 और add r02, r02, 0 ), यह तुरंत स्पष्ट था कि वे अर्थहीन थे। वास्तव में, इन आदेशों ने भौतिक रजिस्टरों की नियुक्ति के बाद ही एक अर्थहीन रूप ले लिया, अर्थात। समाप्त पी-कोड आउटपुट करने से पहले बहुत अंतिम चरण में। तब तक, ऑपरेंड्स के एन-रजिस्टरों की संख्या अलग थी; केवल विश्लेषण जो हमने अभी-अभी किया है, उन्होंने उन्हें संयोजित करना और उस नकल को हटाना संभव बना दिया है, जो संवेदनहीन बना है - यह सब शारीरिक रजिस्टरों की नियुक्ति से बहुत पहले।

तह लगातार

एक अन्य मानक अनुकूलन, जो पिछले वाले की तरह, डीएफए का उपयोग करके कार्यान्वित किया जाता है, निरंतर तह है । सिद्धांत बहुत सरल है: यदि ऑपरेंड्स के मूल्यों को जाना जाता है, तो संकलन पर तुरंत ऑपरेशन किया जा सकता है। उदाहरण के लिए, कोड के बजाय

 MOV R1, 2
 MOV R2, 3
 एडीडी आर 3, आर 1, आर 2

हम तुरंत उत्पन्न कर सकते हैं

  MOV R3.5 

स्थिरांक पर संचालन जरूरी एक प्रोग्रामर की लापरवाही को इंगित नहीं करता है जो पहले ज्ञात परिणाम की गणना करने के लिए बहुत आलसी था: उदाहरण के लिए, pixels=1024*768; pixels=786432; तुलना में पढ़ने और बनाए रखने में आसान pixels=786432;

इस बार, प्रत्येक कमांड में हम रजिस्टरों के सेटों को संग्रहीत करते हैं, जिसके लिए मूल्यों को जाना जाता है, एक साथ मूल्यों के साथ: फॉर्म std::map<regnum,int>
हमेशा की तरह, हम सेट की गणना के लिए तीन नियम बनाते हैं:

• MOV R, X कमांड में MOV R, X R का मान ज्ञात है, और यह X है ;
• किसी भी अन्य कमांड में जो R का मान सेट करता है, यह मान अज्ञात है;
• टीम C में, R का मान ज्ञात किया जाता है यदि यह ज्ञात है और सभी टीमों में समान है , जहां से आप C (सीधे या बिना जंप) जा सकते हैं।

हम फिर से देखते हैं: मार्ग की दिशा आगे है (अगले में इसका मूल्य पिछले कमांड में रजिस्टर के मूल्य पर निर्भर करता है); नोड्स में ऑपरेशन - अज्ञात रजिस्टरों का एक संघ।

जब सेट स्थिर हो जाते हैं, तो हम प्रत्येक ऑपरेशन को बदल सकते हैं, दोनों ऑपरेंड जिनमें से ज्ञात हैं, एमओवी के साथ।

एक ही डेटा हमें एक और अनुकूलन करने की अनुमति देगा - निरंतर प्रसार (एक रजिस्टर संदर्भ के बजाय एक ज्ञात मूल्य का प्रतिस्थापन)। यह अनुकूलन हमारे द्वारा चुने गए पी-कोड प्रारूप के साथ संभव नहीं है, क्योंकि इसमें रजिस्टर पर कोई संचालन नहीं होता है और इसमें स्थिर होता है; इस तरह के संचालन, हालांकि, कई वास्तविक प्रोसेसर में मौजूद हैं, इसलिए निष्पादन योग्य कोड उत्पन्न करते समय पूर्ण-निरंतर "निरंतर प्रतिस्थापन" करना संभव होगा। अब हम खुद को R0 के साथ शून्य मान को बदलने के लिए प्रतिबंधित करते हैं।

उदाहरण के लिए, एक निर्माण जैसे if (1>2) { echo("unreachable"); } if (1>2) { echo("unreachable"); } जो संकलन करता है

 एमओवी आर 1, 1
 MOV R2, 2
 जीटी आर 3, आर 1, आर 2
 JZ R3, लेबल
 ECHO "अगम्य"
 लेबल:

में तह स्थिरांक के चरण को चालू करेगा

 एमओवी आर 1, 1
 MOV R2, 2
 MOV R3, 0
 JZ R3, लेबल
 ECHO "अगम्य"
 लेबल:

और पिछली बार हमारे द्वारा पहले से लागू किए गए "गैर-जीवित कोड का विनाश" अनुकूलन पहले दो MOV आदेशों को हटा देगा।
यदि उसी समय हम शून्य मान को R0 से प्रतिस्थापित करते हैं:

 MOV R3, 0
 JZ R0, लेबल
 ECHO "अगम्य"
 लेबल:

फिर, गैर-जीवित कोड के साथ, अंतिम MOV हटा दिया जाएगा, और "अगम्य कोड का विनाश" भी ECHO हटा देगा, JZ को NOP में बदल देगा।

इसी तरह, आप एक ज्ञात गैर-शून्य मान वाले JZ कोड से निकाल सकते हैं। दूसरा लागू किया गया "विशेष मामला" ADD RX, (0), RY का प्रतिस्थापन है ADD RX, (0), RY ADD RX, RY, R0 साथ ADD RX, (0), RY ADD RX, RY, R0 , ताकि कॉपी क्लीनिंग एल्गोरिथ्म इस कमांड में रजिस्टर करने के लिए रजिस्टर से कॉपी की पहचान करे।

तह स्थिरांक का एक और लाभ यह है कि नकारात्मक मूल्य अब हमारे आदेशों में उपयोग किए जा सकते हैं। इस तथ्य के कारण कि लेक्सर में हमने NUM टोकन को regexp [0-9]+ , "-123" प्रकार के स्ट्रिंग्स को एक शून्य ऋण के रूप में व्याख्या की गई और फिर 123 का शाब्दिक अर्थ; इसलिए उन्होंने पी-कोड में संकलित किया

 एमओवी आर 1, 123
 SUB R2, R0, R1

अब पी-कोड में एक ईमानदार टीम MOV R1, -123 ।

कार्यान्वयन

struct commandn को कुछ और क्षेत्रों द्वारा पूरक किया जाता है:
std::map<regnum, int > known; regset unknown;

अनुकूलन का आधार, जैसा कि पिछले मामलों में है, डीएफए है:
void constp() {
bool changed = false ;
foreach(i, pcode) {
i->known.clear(); i->unknown.clear();
if (i->cmd.opcode==command::mov) { // rule 1
i->known[i->cmd.dest] = i->cmd.imm;
changed = true ;
} else if (writesdest(i)) { // rule 2
i->unknown.insert(i->cmd.dest);
changed = true ;
}
}
while (changed) {
changed = false ;
foreach2(i, pcode, next) {
// rule 3 (next command)
if (hasnext(i))
changed |= propagate(i, next);
// rule 3 (jmp target)
if (i->cmd.opcode==command::jz)
changed |= propagate(i, i->tgt);
}
}
//
foreach(i, pcode) {
i->known[ 0 ] = 0 ; // R0
if (has2src(i) && i->known.count(i->cmd.src1) && i->known.count(i->cmd.src2))
i->cmd = command(command::mov, i->cmd.dest, ops[i->cmd.opcode](i->known[i->cmd.src1],i->known[i->cmd.src2]));
// 0
if (has2src(i)) {
if (i->known.count(i->cmd.src1) && !i->known[i->cmd.src1])
i->cmd.src1 = 0 ;
if (i->known.count(i->cmd.src2) && !i->known[i->cmd.src2])
i->cmd.src2 = 0 ;
if (i->cmd.opcode==command::add && !i->cmd.src1) { //
i->cmd.src1 = i->cmd.src2;
i->cmd.src2 = 0 ;
}
}
if (readsdest(i) && i->known.count(i->cmd.dest))
if (!i->known[i->cmd.dest])
i->cmd.dest = 0 ;
else // , 0
if (i->cmd.opcode==command::jz) nopOut(i);
}
}

propagate() प्रक्रिया अज्ञात रजिस्टरों के सेट के संघ को लागू करती है: कई ज्ञात मूल्यों वाले एक रजिस्टर को अज्ञात घोषित किया जाता है।
bool propagate(pcommandn from, pcommandn to) {
bool changed = false ; // :
//
foreach(i, from->known) {
regnum r = i->first;
if (to->known.count(‌r))
if ((to->known[r]!=i->second) // , 1
&&!((to->cmd.opcode==command::mov) && (to->cmd.dest==r))) {
to->known.erase(‌r);
to->unknown.insert(‌r);
changed = true ;
} else ; //
else if (!to->unknown.count(‌r)) { // ,
to->known[r]=i->second;
changed = true ;
}
}
//
foreach(r, from->unknown)
if (!to->unknown.count(*r)) {
to->unknown.insert(*r);
to->known.erase(*r);
changed = true ;
}
return changed;
}

अंतिम चीज को उस मूल्य की वास्तविक गणना के रूप में जाना जाता है जब ऑपरेंड ज्ञात होते हैं। उसी तरह जैसे कि j-script निष्पादक में, हम प्रत्येक opcode के लिए एक फंक्शन सेट करते हैं:
int hlt( int src1, int src2) { assert( false ); return 0 ; }
int add( int src1, int src2) { return src1+src2; }
int sub( int src1, int src2) { return src1-src2; }
...
int lt( int src1, int src2) { return src1<src2; }
int (*ops[])( int , int ) = {hlt, hlt, hlt, hlt, hlt, hlt, hlt, add, sub, mul, div, eq, ne, ge, le, gt, lt};

constp(); लिए एक कॉल डालें constp(); copies(); से पहले copies(); - और हम अनुकूलन के साथ समाप्त करेंगे।

अगली पोस्ट में - हम भौतिक रजिस्टर के साथ पी-कोड से x86 / x64 के लिए वास्तविक निष्पादन योग्य कोड सेट करते हैं।