Prinsip-prinsip dasar
Ini adalah proses pengumpulan informasi tentang cara variabel yang digunakan, didefinisikan dalam program ini. Analisis aliran data upaya untuk memperoleh informasi tertentu pada setiap titik dalam prosedur. Biasanya, itu sudah cukup untuk memperoleh informasi ini pada batas blok dasar, sejak dari bahwa adalah mudah untuk menghitung informasi pada poin di blok dasar. Dalam analisis arus maju, negara keluar dari blok adalah fungsi negara masuk blok. Fungsi ini adalah komposisi efek dari pernyataan di blok. Keadaan masuknya blok adalah fungsi dari negara-negara keluar dari pendahulunya. Ini menghasilkan satu set data-aliran persamaan:
Untuk setiap blok b:
outb = transb (inb)
in_b = join_ {p \ di pred_b} (out_p)
Dalam hal ini, transb adalah fungsi transfer blok b. Ia bekerja pada negara inb masuk, yang menghasilkan outb negara keluar. Operasi bergabung bergabung menggabungkan menyatakan keluar dari pendahulu p \ di pred_b b, menghasilkan negara masuknya b.
Setelah menyelesaikan set persamaan, negara masuk dan / atau keluar dari blok dapat digunakan untuk mendapatkan properti dari program pada batas blok. Fungsi transfer setiap pernyataan secara terpisah dapat diterapkan untuk mendapatkan informasi pada suatu titik di dalam blok dasar.
Setiap jenis tertentu dari data-aliran analisis telah mentransfer sendiri fungsi dan bergabung dengan operasi. Beberapa data-aliran masalah, analisis arus mundur. Ini mengikuti rencana yang sama, kecuali bahwa fungsi transfer diterapkan kepada negara keluar menghasilkan negara masuk, dan operasi bergabung bekerja pada masuknya negara penerus untuk menghasilkan negara keluar.
Titik masuk (aliran ke depan) memainkan peran penting: Karena tidak memiliki pendahulu, masuknya negara didefinisikan dengan baik pada awal analisis. Misalnya, himpunan variabel lokal dengan nilai-nilai diketahui kosong. Jika grafik aliran kontrol tidak mengandung siklus (tidak ada loop eksplisit atau implisit dalam prosedur) memecahkan persamaan secara langsung. Grafik aliran kontrol kemudian dapat topologi diurutkan, berjalan dalam urutan seperti ini, negara-negara entri dapat dihitung pada awal setiap blok, karena semua pendahulu dari blok yang telah diproses, sehingga mereka menyatakan keluar tersedia. Jika grafik aliran kontrol tidak mengandung siklus, sebuah algoritma yang lebih canggih diperlukan.[Sunting] Sebuah algoritma iteratif
Cara yang paling umum untuk memecahkan persamaan aliran data adalah dengan menggunakan algoritma iteratif. Ini dimulai dengan perkiraan negara di-blok masing-masing. Out-negara tersebut kemudian dihitung dengan menerapkan fungsi transfer pada di negara-negara. Dari ini, di-negara yang diperbarui dengan menerapkan operasi bergabung. Dua terakhir langkah ini diulang sampai kita mencapai fixpoint disebut: situasi di mana di negara-negara (dan keluar-negara bagian di konsekuensi) tidak berubah.
Sebuah algoritma dasar untuk memecahkan persamaan aliran data adalah round-robin algoritma iteratif:
untuk i ← 1 sampai N
menginisialisasi node i
sementara (set masih berubah)
untuk i ← 1 sampai N
recompute set pada node i
[Sunting] Konvergensi
Untuk digunakan, pendekatan iteratif harus benar-benar mencapai suatu fixpoint. Hal ini dapat dijamin oleh memaksakan kendala pada kombinasi dari domain nilai negara, fungsi transfer dan operasi join.
Nilai domain harus urutan parsial dengan ketinggian yang terbatas (yaitu, tidak ada rantai ascending terbatas x1 <x2 <...). Kombinasi dari fungsi transfer dan operasi harus bergabung monoton sehubungan dengan urutan parsial. Kemonotonan memastikan bahwa pada setiap iterasi nilai baik akan tetap sama atau akan tumbuh lebih besar, sementara tingginya terbatas memastikan bahwa hal itu tidak bisa tumbuh tanpa batas. Dengan demikian kita akhirnya akan mencapai situasi di mana T (x) = x untuk semua x, yang fixpoint tersebut.[Sunting] Pendekatan daftar pekerjaan
Sangat mudah untuk memperbaiki algoritma di atas dengan memperhatikan bahwa di negara-blok tidak akan berubah jika keluar-negara pendahulunya tidak berubah. Oleh karena itu, kami memperkenalkan sebuah daftar kerja: daftar blok yang masih harus diproses. Setiap kali keluar-negara perubahan blok, kita menambahkan penerus ke daftar kerja. Dalam setiap iterasi, blok dihapus dari daftar pekerjaan. Its keluar-negara dihitung. Jika out-negara berubah, penerus blok tersebut ditambahkan ke daftar kerja. Untuk efisiensi, blok tidak boleh dalam daftar bekerja lebih dari sekali.
Algoritma ini dimulai dengan menempatkan titik masuk dalam daftar pekerjaan. Ini berakhir ketika daftar pekerjaan kosong.[Sunting] Perintah penting
Efisiensi iteratif memecahkan persamaan aliran data dipengaruhi oleh urutan di mana node lokal dikunjungi. Selain itu, tergantung, apakah data-aliran persamaan yang digunakan untuk maju atau mundur aliran data analisis atas CFG tersebut. Intuitif, dalam masalah aliran ke depan, akan tercepat jika semua pendahulu dari blok telah diproses sebelum blok itu sendiri, sejak saat iterasi akan menggunakan informasi terbaru. Dengan tidak adanya loop adalah mungkin untuk memesan blok sedemikian rupa sehingga benar keluar-negara dihitung dengan memproses setiap blok hanya sekali.
Dalam berikut, pesanan beberapa iterasi untuk menyelesaikan persamaan aliran data yang dibahas (sebuah konsep yang berhubungan untuk memesan iterasi dari CFG adalah pohon traversal dari pohon).
Urutan acak - Ini pesanan iterasi tidak menyadari apakah data-aliran persamaan memecahkan masalah data aliran maju atau mundur. Oleh karena itu, kinerja yang relatif miskin dibandingkan dengan perintah iterasi khusus.
Postorder - Ini adalah perintah iterasi khas untuk mundur data masalah arus. Dalam iterasi postorder, node dikunjungi setelah semua node penggantinya telah dikunjungi. Biasanya, iterasi postorder diimplementasikan dengan strategi depth-first.
Sebaliknya postorder - Ini adalah perintah iterasi khas untuk meneruskan data-masalah arus. Dalam reverse-postorder iterasi, node dikunjungi sebelum semua node penggantinya telah dikunjungi, kecuali bila penggantinya adalah dicapai oleh ujung belakang. (Catatan bahwa ini tidak sama dengan preorder.)
[Sunting] Inisialisasi
Nilai awal di-negara adalah penting untuk mendapatkan hasil yang benar dan akurat. Jika hasilnya digunakan untuk optimasi compiler, mereka harus memberikan informasi yang konservatif, yaitu ketika menerapkan informasi, program tidak harus mengubah semantik. Iterasi dari algoritma fixpoint akan mengambil nilai-nilai dalam arah elemen maksimum. Menginisialisasi semua blok dengan elemen maksimum karena itu tidak berguna. Setidaknya satu blok dimulai di negara dengan nilai kurang maksimal. Rincian tergantung pada masalah data-aliran. Jika elemen minimal merupakan informasi benar-benar konservatif, hasilnya dapat digunakan dengan aman bahkan selama iterasi data aliran. Jika itu merupakan informasi yang paling akurat, fixpoint harus dicapai sebelum hasil dapat diterapkan.[Sunting] Contoh
Berikut ini adalah contoh dari sifat-sifat dari program komputer yang dapat dihitung dengan data-aliran analisis. Perhatikan bahwa sifat dihitung dengan analisis aliran data biasanya hanya perkiraan sifat nyata. Hal ini karena data-flow analisis beroperasi pada struktur sintaksis CFG tanpa simulasi aliran kontrol yang tepat dari program. Namun, untuk menjadi masih berguna dalam praktek, algoritma analisis data flow biasanya dirancang untuk menghitung masing-masing pendekatan bawah atas sifat program nyata.[Sunting] Analisis Teruskan
Analisis Definisi mencapai menghitung untuk setiap titik program set definisi yang berpotensi dapat mencapai titik ini program.
1: jika b == 4 maka2: a = 5;3: lain4: a = 3;5: endif6:7: jika <4 maka8: ...
Definisi mencapai variabel "a" pada baris 7 adalah himpunan tugas a = 5 pada baris 2 dan a = 3 pada baris 4.[Sunting] Analisis Mundur
Analisis variabel tinggal menghitung untuk setiap titik program variabel yang mungkin berpotensi dibaca kemudian sebelum update menulis berikutnya. Hasilnya adalah biasanya digunakan oleh eliminasi kode mati untuk menghapus pernyataan yang menetapkan ke suatu variabel yang nilainya tidak digunakan sesudahnya.
Di-negara blok adalah himpunan variabel yang tinggal di ujung blok. Its luar negara adalah serangkaian variabel yang ada tinggal pada awal itu. Di-negara adalah gabungan dari out-negara dari blok penerus. Fungsi transfer dari sebuah pernyataan diterapkan dengan membuat variabel yang ditulis mati, kemudian membuat variabel yang dibaca hidup.
/ / Keluar: {}b1: a = 3;
b = 5;
d = 4;
jika a> b maka
/ / Dalam: {a, b, d}
/ / Keluar: {a, b}b2: c = a + b;
d = 2;
/ / Dalam: {b, d}
/ / Keluar: {b, d}b3: endif
c = 4;
kembali b * d + c;
/ / Dalam: {}
Out-negara b3 hanya berisi b dan d, karena c telah ditulis. Di negara-b1 adalah gabungan dari out-negara bagian b2 dan b3. Definisi c dalam b2 dapat dihapus, karena c adalah tidak hidup segera setelah pernyataan itu.
Memecahkan persamaan aliran data dimulai dengan menginisialisasi semua di-negara-negara dan keluar ke set kosong. Daftar kerja diinisialisasi dengan memasukkan titik keluar (B3) dalam daftar pekerjaan (khas untuk mengalir ke belakang). Dihitung nya keluar-negara berbeda dari yang sebelumnya, sehingga pendahulunya b1 dan b2 dimasukkan dan proses berlanjut. Kemajuan tersebut diringkas dalam tabel di bawah ini.pengolahan di negara-negara lama keluar baru keluar-negara daftar pekerjaanb3 {} {} {b, d} (b1, b2)b1 {b, d} {} {} (b2)b2 {b, d} {} {a, b} (b1)b1 {a, b, d} {} {} ()
Catatan b1 yang masuk dalam daftar sebelum b2, b1 pengolahan yang memaksa dua kali (b1 adalah kembali dimasukkan sebagai pendahulu dari b2). Memasukkan b1 b2 sebelumnya akan membiarkan selesai sebelumnya.
Menginisialisasi dengan himpunan kosong adalah inisialisasi optimis: semua variabel dimulai sebagai mati. Perhatikan bahwa keluar-negara tidak dapat menyusut dari satu iterasi ke depan, meskipun keluar-negara dapat lebih kecil yang di-negara. Hal ini dapat dilihat dari fakta bahwa setelah iterasi pertama keluar-satunya negara dapat berubah dengan perubahan negara dalam-. Karena di negara dimulai sebagai himpunan kosong, hanya dapat tumbuh di iterasi lebih lanjut.[Sunting] Pendekatan-pendekatan lain
Pada tahun 2002, Markus Mohnen dijelaskan metode baru data-flow analisis yang tidak memerlukan konstruksi eksplisit dari sebuah grafik aliran data, [2], bukan mengandalkan pada interpretasi abstrak program dan menjaga working set counter program. Pada setiap cabang kondisional, baik target ditambahkan ke working set. Masing-masing jalan diikuti untuk sebagai petunjuk sebanyak mungkin (sampai akhir program atau sampai telah dilingkarkan dengan tidak ada perubahan), dan kemudian dihapus dari set dan program counter berikutnya diambil.[Sunting] Bit masalah vektor
Contoh di atas adalah masalah di mana nilai data-aliran set, misalnya set definisi mencapai (Menggunakan sedikit untuk posisi definisi dalam program), atau set variabel hidup. Set ini dapat direpresentasikan secara efisien sebagai vektor bit, di mana setiap bit mewakili keanggotaan set satu elemen tertentu. Menggunakan representasi ini, fungsi bergabung dan transfer dapat diimplementasikan sebagai operasi bitwise logis. Operasi bergabung biasanya serikat buruh atau persimpangan, dilaksanakan oleh bitwise logis atau dan logis dan. Fungsi transfer untuk setiap blok dapat diuraikan dalam apa yang disebut gen dan membunuh set.
Sebagai contoh, dalam hidup-variabel analisis, operasi bergabung adalah serikat. Set membunuh adalah himpunan variabel yang ditulis dalam blok, sedangkan set gen adalah himpunan variabel yang dibaca tanpa tertulis pertama. Data-aliran persamaan menjadi
out_b = \ bigcup_ {s \ di succ_b} in_s
in_b = (out_b - kill_b) \ cangkir gen_b
Dalam operasi logis, ini berbunyi sebagai
keluar (b) = 0
untuk s di succ (b)
keluar (b) = keluar (b) atau (s)
dalam (b) = (keluar (b) dan tidak membunuh (b)) atau gen (b)
[Sunting] Sensitivitas
Analisis aliran data secara inheren aliran-sensitif. Analisis aliran data biasanya jalan-insensitive, meskipun mungkin untuk mendefinisikan data flow persamaan yang menghasilkan jalur-sensitif analisis.
Aliran-sensitif analisis memperhitungkan urutan pernyataan dalam program. Sebagai contoh, aliran-insensitive analisis alias pointer dapat menentukan "variabel x dan y dapat merujuk ke lokasi yang sama", sementara analisis aliran-sensitif dapat menentukan "setelah pernyataan 20, variabel x dan y dapat merujuk ke lokasi yang sama".
Sebuah jalur-sensitif analisis menghitung potongan informasi yang berbeda tergantung pada analisis predikat di instruksi cabang bersyarat. Sebagai contoh, jika cabang berisi kondisi x> 0, maka pada musim gugur-melalui jalan setapak, analisis akan berasumsi bahwa x <= 0 dan pada target cabang itu akan berasumsi bahwa memang x> 0 berlaku.
Sebuah konteks-sensitif analisis adalah analisis interprosedural yang mempertimbangkan konteks menelepon ketika menganalisis target dari pemanggilan fungsi. Secara khusus, menggunakan informasi konteks yang dapat melompat kembali ke situs panggilan asli, sedangkan tanpa informasi itu, analisis informasi harus disebarkan kembali ke semua situs panggilan mungkin, berpotensi kehilangan presisi.
Ini adalah proses pengumpulan informasi tentang cara variabel yang digunakan, didefinisikan dalam program ini. Analisis aliran data upaya untuk memperoleh informasi tertentu pada setiap titik dalam prosedur. Biasanya, itu sudah cukup untuk memperoleh informasi ini pada batas blok dasar, sejak dari bahwa adalah mudah untuk menghitung informasi pada poin di blok dasar. Dalam analisis arus maju, negara keluar dari blok adalah fungsi negara masuk blok. Fungsi ini adalah komposisi efek dari pernyataan di blok. Keadaan masuknya blok adalah fungsi dari negara-negara keluar dari pendahulunya. Ini menghasilkan satu set data-aliran persamaan:
Untuk setiap blok b:
outb = transb (inb)
in_b = join_ {p \ di pred_b} (out_p)
Dalam hal ini, transb adalah fungsi transfer blok b. Ia bekerja pada negara inb masuk, yang menghasilkan outb negara keluar. Operasi bergabung bergabung menggabungkan menyatakan keluar dari pendahulu p \ di pred_b b, menghasilkan negara masuknya b.
Setelah menyelesaikan set persamaan, negara masuk dan / atau keluar dari blok dapat digunakan untuk mendapatkan properti dari program pada batas blok. Fungsi transfer setiap pernyataan secara terpisah dapat diterapkan untuk mendapatkan informasi pada suatu titik di dalam blok dasar.
Setiap jenis tertentu dari data-aliran analisis telah mentransfer sendiri fungsi dan bergabung dengan operasi. Beberapa data-aliran masalah, analisis arus mundur. Ini mengikuti rencana yang sama, kecuali bahwa fungsi transfer diterapkan kepada negara keluar menghasilkan negara masuk, dan operasi bergabung bekerja pada masuknya negara penerus untuk menghasilkan negara keluar.
Titik masuk (aliran ke depan) memainkan peran penting: Karena tidak memiliki pendahulu, masuknya negara didefinisikan dengan baik pada awal analisis. Misalnya, himpunan variabel lokal dengan nilai-nilai diketahui kosong. Jika grafik aliran kontrol tidak mengandung siklus (tidak ada loop eksplisit atau implisit dalam prosedur) memecahkan persamaan secara langsung. Grafik aliran kontrol kemudian dapat topologi diurutkan, berjalan dalam urutan seperti ini, negara-negara entri dapat dihitung pada awal setiap blok, karena semua pendahulu dari blok yang telah diproses, sehingga mereka menyatakan keluar tersedia. Jika grafik aliran kontrol tidak mengandung siklus, sebuah algoritma yang lebih canggih diperlukan.[Sunting] Sebuah algoritma iteratif
Cara yang paling umum untuk memecahkan persamaan aliran data adalah dengan menggunakan algoritma iteratif. Ini dimulai dengan perkiraan negara di-blok masing-masing. Out-negara tersebut kemudian dihitung dengan menerapkan fungsi transfer pada di negara-negara. Dari ini, di-negara yang diperbarui dengan menerapkan operasi bergabung. Dua terakhir langkah ini diulang sampai kita mencapai fixpoint disebut: situasi di mana di negara-negara (dan keluar-negara bagian di konsekuensi) tidak berubah.
Sebuah algoritma dasar untuk memecahkan persamaan aliran data adalah round-robin algoritma iteratif:
untuk i ← 1 sampai N
menginisialisasi node i
sementara (set masih berubah)
untuk i ← 1 sampai N
recompute set pada node i
[Sunting] Konvergensi
Untuk digunakan, pendekatan iteratif harus benar-benar mencapai suatu fixpoint. Hal ini dapat dijamin oleh memaksakan kendala pada kombinasi dari domain nilai negara, fungsi transfer dan operasi join.
Nilai domain harus urutan parsial dengan ketinggian yang terbatas (yaitu, tidak ada rantai ascending terbatas x1 <x2 <...). Kombinasi dari fungsi transfer dan operasi harus bergabung monoton sehubungan dengan urutan parsial. Kemonotonan memastikan bahwa pada setiap iterasi nilai baik akan tetap sama atau akan tumbuh lebih besar, sementara tingginya terbatas memastikan bahwa hal itu tidak bisa tumbuh tanpa batas. Dengan demikian kita akhirnya akan mencapai situasi di mana T (x) = x untuk semua x, yang fixpoint tersebut.[Sunting] Pendekatan daftar pekerjaan
Sangat mudah untuk memperbaiki algoritma di atas dengan memperhatikan bahwa di negara-blok tidak akan berubah jika keluar-negara pendahulunya tidak berubah. Oleh karena itu, kami memperkenalkan sebuah daftar kerja: daftar blok yang masih harus diproses. Setiap kali keluar-negara perubahan blok, kita menambahkan penerus ke daftar kerja. Dalam setiap iterasi, blok dihapus dari daftar pekerjaan. Its keluar-negara dihitung. Jika out-negara berubah, penerus blok tersebut ditambahkan ke daftar kerja. Untuk efisiensi, blok tidak boleh dalam daftar bekerja lebih dari sekali.
Algoritma ini dimulai dengan menempatkan titik masuk dalam daftar pekerjaan. Ini berakhir ketika daftar pekerjaan kosong.[Sunting] Perintah penting
Efisiensi iteratif memecahkan persamaan aliran data dipengaruhi oleh urutan di mana node lokal dikunjungi. Selain itu, tergantung, apakah data-aliran persamaan yang digunakan untuk maju atau mundur aliran data analisis atas CFG tersebut. Intuitif, dalam masalah aliran ke depan, akan tercepat jika semua pendahulu dari blok telah diproses sebelum blok itu sendiri, sejak saat iterasi akan menggunakan informasi terbaru. Dengan tidak adanya loop adalah mungkin untuk memesan blok sedemikian rupa sehingga benar keluar-negara dihitung dengan memproses setiap blok hanya sekali.
Dalam berikut, pesanan beberapa iterasi untuk menyelesaikan persamaan aliran data yang dibahas (sebuah konsep yang berhubungan untuk memesan iterasi dari CFG adalah pohon traversal dari pohon).
Urutan acak - Ini pesanan iterasi tidak menyadari apakah data-aliran persamaan memecahkan masalah data aliran maju atau mundur. Oleh karena itu, kinerja yang relatif miskin dibandingkan dengan perintah iterasi khusus.
Postorder - Ini adalah perintah iterasi khas untuk mundur data masalah arus. Dalam iterasi postorder, node dikunjungi setelah semua node penggantinya telah dikunjungi. Biasanya, iterasi postorder diimplementasikan dengan strategi depth-first.
Sebaliknya postorder - Ini adalah perintah iterasi khas untuk meneruskan data-masalah arus. Dalam reverse-postorder iterasi, node dikunjungi sebelum semua node penggantinya telah dikunjungi, kecuali bila penggantinya adalah dicapai oleh ujung belakang. (Catatan bahwa ini tidak sama dengan preorder.)
[Sunting] Inisialisasi
Nilai awal di-negara adalah penting untuk mendapatkan hasil yang benar dan akurat. Jika hasilnya digunakan untuk optimasi compiler, mereka harus memberikan informasi yang konservatif, yaitu ketika menerapkan informasi, program tidak harus mengubah semantik. Iterasi dari algoritma fixpoint akan mengambil nilai-nilai dalam arah elemen maksimum. Menginisialisasi semua blok dengan elemen maksimum karena itu tidak berguna. Setidaknya satu blok dimulai di negara dengan nilai kurang maksimal. Rincian tergantung pada masalah data-aliran. Jika elemen minimal merupakan informasi benar-benar konservatif, hasilnya dapat digunakan dengan aman bahkan selama iterasi data aliran. Jika itu merupakan informasi yang paling akurat, fixpoint harus dicapai sebelum hasil dapat diterapkan.[Sunting] Contoh
Berikut ini adalah contoh dari sifat-sifat dari program komputer yang dapat dihitung dengan data-aliran analisis. Perhatikan bahwa sifat dihitung dengan analisis aliran data biasanya hanya perkiraan sifat nyata. Hal ini karena data-flow analisis beroperasi pada struktur sintaksis CFG tanpa simulasi aliran kontrol yang tepat dari program. Namun, untuk menjadi masih berguna dalam praktek, algoritma analisis data flow biasanya dirancang untuk menghitung masing-masing pendekatan bawah atas sifat program nyata.[Sunting] Analisis Teruskan
Analisis Definisi mencapai menghitung untuk setiap titik program set definisi yang berpotensi dapat mencapai titik ini program.
1: jika b == 4 maka2: a = 5;3: lain4: a = 3;5: endif6:7: jika <4 maka8: ...
Definisi mencapai variabel "a" pada baris 7 adalah himpunan tugas a = 5 pada baris 2 dan a = 3 pada baris 4.[Sunting] Analisis Mundur
Analisis variabel tinggal menghitung untuk setiap titik program variabel yang mungkin berpotensi dibaca kemudian sebelum update menulis berikutnya. Hasilnya adalah biasanya digunakan oleh eliminasi kode mati untuk menghapus pernyataan yang menetapkan ke suatu variabel yang nilainya tidak digunakan sesudahnya.
Di-negara blok adalah himpunan variabel yang tinggal di ujung blok. Its luar negara adalah serangkaian variabel yang ada tinggal pada awal itu. Di-negara adalah gabungan dari out-negara dari blok penerus. Fungsi transfer dari sebuah pernyataan diterapkan dengan membuat variabel yang ditulis mati, kemudian membuat variabel yang dibaca hidup.
/ / Keluar: {}b1: a = 3;
b = 5;
d = 4;
jika a> b maka
/ / Dalam: {a, b, d}
/ / Keluar: {a, b}b2: c = a + b;
d = 2;
/ / Dalam: {b, d}
/ / Keluar: {b, d}b3: endif
c = 4;
kembali b * d + c;
/ / Dalam: {}
Out-negara b3 hanya berisi b dan d, karena c telah ditulis. Di negara-b1 adalah gabungan dari out-negara bagian b2 dan b3. Definisi c dalam b2 dapat dihapus, karena c adalah tidak hidup segera setelah pernyataan itu.
Memecahkan persamaan aliran data dimulai dengan menginisialisasi semua di-negara-negara dan keluar ke set kosong. Daftar kerja diinisialisasi dengan memasukkan titik keluar (B3) dalam daftar pekerjaan (khas untuk mengalir ke belakang). Dihitung nya keluar-negara berbeda dari yang sebelumnya, sehingga pendahulunya b1 dan b2 dimasukkan dan proses berlanjut. Kemajuan tersebut diringkas dalam tabel di bawah ini.pengolahan di negara-negara lama keluar baru keluar-negara daftar pekerjaanb3 {} {} {b, d} (b1, b2)b1 {b, d} {} {} (b2)b2 {b, d} {} {a, b} (b1)b1 {a, b, d} {} {} ()
Catatan b1 yang masuk dalam daftar sebelum b2, b1 pengolahan yang memaksa dua kali (b1 adalah kembali dimasukkan sebagai pendahulu dari b2). Memasukkan b1 b2 sebelumnya akan membiarkan selesai sebelumnya.
Menginisialisasi dengan himpunan kosong adalah inisialisasi optimis: semua variabel dimulai sebagai mati. Perhatikan bahwa keluar-negara tidak dapat menyusut dari satu iterasi ke depan, meskipun keluar-negara dapat lebih kecil yang di-negara. Hal ini dapat dilihat dari fakta bahwa setelah iterasi pertama keluar-satunya negara dapat berubah dengan perubahan negara dalam-. Karena di negara dimulai sebagai himpunan kosong, hanya dapat tumbuh di iterasi lebih lanjut.[Sunting] Pendekatan-pendekatan lain
Pada tahun 2002, Markus Mohnen dijelaskan metode baru data-flow analisis yang tidak memerlukan konstruksi eksplisit dari sebuah grafik aliran data, [2], bukan mengandalkan pada interpretasi abstrak program dan menjaga working set counter program. Pada setiap cabang kondisional, baik target ditambahkan ke working set. Masing-masing jalan diikuti untuk sebagai petunjuk sebanyak mungkin (sampai akhir program atau sampai telah dilingkarkan dengan tidak ada perubahan), dan kemudian dihapus dari set dan program counter berikutnya diambil.[Sunting] Bit masalah vektor
Contoh di atas adalah masalah di mana nilai data-aliran set, misalnya set definisi mencapai (Menggunakan sedikit untuk posisi definisi dalam program), atau set variabel hidup. Set ini dapat direpresentasikan secara efisien sebagai vektor bit, di mana setiap bit mewakili keanggotaan set satu elemen tertentu. Menggunakan representasi ini, fungsi bergabung dan transfer dapat diimplementasikan sebagai operasi bitwise logis. Operasi bergabung biasanya serikat buruh atau persimpangan, dilaksanakan oleh bitwise logis atau dan logis dan. Fungsi transfer untuk setiap blok dapat diuraikan dalam apa yang disebut gen dan membunuh set.
Sebagai contoh, dalam hidup-variabel analisis, operasi bergabung adalah serikat. Set membunuh adalah himpunan variabel yang ditulis dalam blok, sedangkan set gen adalah himpunan variabel yang dibaca tanpa tertulis pertama. Data-aliran persamaan menjadi
out_b = \ bigcup_ {s \ di succ_b} in_s
in_b = (out_b - kill_b) \ cangkir gen_b
Dalam operasi logis, ini berbunyi sebagai
keluar (b) = 0
untuk s di succ (b)
keluar (b) = keluar (b) atau (s)
dalam (b) = (keluar (b) dan tidak membunuh (b)) atau gen (b)
[Sunting] Sensitivitas
Analisis aliran data secara inheren aliran-sensitif. Analisis aliran data biasanya jalan-insensitive, meskipun mungkin untuk mendefinisikan data flow persamaan yang menghasilkan jalur-sensitif analisis.
Aliran-sensitif analisis memperhitungkan urutan pernyataan dalam program. Sebagai contoh, aliran-insensitive analisis alias pointer dapat menentukan "variabel x dan y dapat merujuk ke lokasi yang sama", sementara analisis aliran-sensitif dapat menentukan "setelah pernyataan 20, variabel x dan y dapat merujuk ke lokasi yang sama".
Sebuah jalur-sensitif analisis menghitung potongan informasi yang berbeda tergantung pada analisis predikat di instruksi cabang bersyarat. Sebagai contoh, jika cabang berisi kondisi x> 0, maka pada musim gugur-melalui jalan setapak, analisis akan berasumsi bahwa x <= 0 dan pada target cabang itu akan berasumsi bahwa memang x> 0 berlaku.
Sebuah konteks-sensitif analisis adalah analisis interprosedural yang mempertimbangkan konteks menelepon ketika menganalisis target dari pemanggilan fungsi. Secara khusus, menggunakan informasi konteks yang dapat melompat kembali ke situs panggilan asli, sedangkan tanpa informasi itu, analisis informasi harus disebarkan kembali ke semua situs panggilan mungkin, berpotensi kehilangan presisi.
Sumber : Wikipedia
0 komentar:
Posting Komentar