Kamis, 09 Juni 2011

TEKNIK KOMPILASI (TEKNIK OPTIMASI)

TEKNIK OPTIMASI

Dependensi optimasi. Tahapan optimasi kode bertujuan untuk menghasilkan kode program yang berukuran lebih kecil dan lebih cepat eksekusinya. Berdasarkan ketergantungannya pada mesin, optimasi di bagi  menjadi :
  1. Machine Dependent Optimizer. Kode dioptimasi sehingga lebih efisien pad mesin tertentu. Optimasi ini memerlukan informasi mengenai feature yang ada pada mesin tujuan dan mengambil keuntungan darinya untuk menghasilkan kode yang lebih pendek atau dieksekusi lebih cepat.
  2. Machine Independent Optimizer. Strategi optimasi yang bisa diaplikasikan tanpa tergantung pada mesin tujuan tempat kode yang dihasilkan akan dieksekusi nantinya. Mesin ini meliputi optimasi lokal dan optimasi global.
OPTIMASI LOKAL
Optimasi Lokal adalah optimasi yang dilakukan hanya pada suatu blok dari source code, cara-caranya sebagai berikut:
  1. Folding. Mengganti konstansta atau ekspresi yang bisa dievaluasi pada saat compile time dengan nilai komputasinya. Misalkan Instruksi ;
A:=2+3+B

bisa diganti menjadi

A:=5+B

  1. Redundant-Subexpression Elimination. Sebuah ekspresi yang sudah pernah dikomputasi, digunakan lagi hasilnya, ketimbang melakukan komputasi ulang. Misalkan terdapat urutan instruksi :
A:=B+C
X:=Y+B+C

kemunculan kedua dari B+C yang redundan bisa diatasi dengan memanfaatkan hasil komputasinya yang sudah ada pada instruksi sebelumnya. Perhatikan, hal ini bisa dilakukan dengan catatan belum ada perubahan pada variabel yang berkaitan.

  1. Optimisasi dalam sebuah iterasi.
a.     Loop Unrolling: Menggantikan suatu loop dengan menulis statement dalam loop beberapa kali. Hal ini didasari pemikiran, sebuah iterasi pada implementasi level rendah akan memerlukan operasi sebagai berikut.
      Inisialisasi/pemberian nilai awal pada variabel loop. Dilakukan sekali pada saat permulaan eksekusi loop.
      Pengujian, apakah variabel loop telah mencapai kondisi terminasi.
      Adjustment yaitu penambahan atau pengurangan nilai pada variabel loop dengan jumlah tertentu.
      Operasi yang terjadi pada tubuh perulangan (loop body).
Dalam setiap perulangan akan terjadi pengujian dan adjusment yang menambah waktu eksekusi. Contoh pada instruksi :

FOR I:=1 to 2 DO
A[I]:=0;

terdapat instruksi untuk inisialisasi I menjadi 1. serta operasi penambahan nilai/increment 1 dan pengecekan variabel I pada setiap perulangan. Sehingga untuk perulangan saja memerlukan lima instruksi, ditambah dengan instruksi assignment pada tubuh perulangan menjadi tujuh instruksi. Dapat dioptimasikan menjadi :

A[1]:=0;
A[2]:=0;

yang hanya memerlukan dua instruksi assignment saja. Untuk menentukan optimasi ini perlu dilihat perbandingan kasusnya dengan tanpa melakukan optimasi.
b.       Frequency Reduction: Pemindahan statement ke tempat yang lebih jarang dieksekusi. Contoh:

FOR I:=1 TO 10 DO
BEGIN
X:=5;
A:=A+I;
END;

kita ,melihat bawa tidak terjadi perubahan /manipulasi pada variabel X didalam iterasi, karena itu kita bisa mengeluarkan instruksi tersebut keluar iterasi, menjadi:

X:=5;
FOR I:=1 TO 10 DO
BEGIN
A:=A+I
END;
  1. Strength Reduction. Penggantian suatu operasi dengan jenis operasi lain yang lebih cepat dieksekusi. Misalkan pada beberapa komputer operasi perkalian memerlukan waktu lebih banyak untuk dieksekusi dari pada operasi penjumlahan, maka penghematan waktu bisa dilakukan dengan mengganti operasi perkalian tertentu dengan penjumlahan. Contoh lain, instruksi :
A:=A+1;
dapat digantikan dengan: INC(A);



OPTIMISASI GLOBAL

Optimisasi global biasanya dilakukan dengan analisis flow, yaitu suatu graf berarah yang menunjukkan jalur yang mungkin selama dieksekusi program. Kegunaannya adalah sebagai berikut:  
1.    Bagi pemrogram menginformasikan :
    a. Unreachable/dead code: kode yang tidak akan pernah dieksekusi. Misalnya terdapat urutan      
        instruksi:   
        
        X:=5;
        IF X:=0 THEN 
        A:=A+1 
       
        Instruksi A:=A+1 tidak akan pernah dieksekusi
    b. Unused parameter pada prosedur: parameter yang tidak akan pernah digunakan didalam prosedur
        Contohnya : 
        
        Procedure Jumlah (a,b,c:integer);
         var x: integer 
         begin 
            x:=a+b 
         end;
       
         kita lihat parameter c tidak pernah digunakan didalam prosedur, sehingga seharusnya tidak perlu     
         diikutrestakan. 
    c. Unused Variable: Variabel yang tidak pernah dipakai dalam program. Contohnya : 
        
        Program Pendek; 
        var a,b:integer; 
        begin 
            a:=5; 
        end; 
        
        variabel b tidak pernah digunakan dalam program sehingga bisa dihilangkan.
   d.   Variabel yang dipakai tanpa nilai awal. Contohnya: 
         
         Program awal;
         var a,b: integer; 
         begin 
            a:=5; 
            a:=a+b; 
         end;
         
         kita lihat variabel b digunakan tanpa memiliki nilai awal/belum di-assign.
2.  Bagi kompilator:
  •   Meningkatkan efisiensi eksekusi program.
  • Menghilangkan useless code/kode yang tidak terpakai.

Senin, 30 Mei 2011

TEKNIK KOMPILASI (CARA PENANGANAN KESALAHAN)


CARA PENANGANAN KESALAHAN

Kesalahan Program bisa merupakan :
  1. Kesalahan Leksikal : THEN ditulis TEN
  2. Kesalahan Sintaks : A:=X+(B*(C+D)       {jumlah kurungnya kurang}
  3. Kesalahan Semantik :
a. Tipe data yang salah.
                        Contoh :          Var Siswa : Integer
                                                Siswa := 'Yanuar'         {tipe string}
b. Variabel belum didefinisikan.
                        Contoh :          B := B + 1       {B belum didefinisikan}

Langkah-langkah Penanganan Kesalahan adalah sebagai berikut :
  1. Mendeteksi Kesalahan
  2. Melaporkan Kesalahan
  3. Tindak lanjut pemulihan/perbaikan
sebuah kompilator yang menemukan kesalahan akan melakukan pelaporan kesalahan, yang biasanya 
meliputi :
  1. Kode kesalahan
  2. Pesan kesalahan dalam bahasa natural
  3. Nama dan atribut identifier
  4. Tipe-tipe yang terkait bila type checking

Contoh : Error Massage: Error 162 Jumlah := unknown identifier
artinya :
  •  kode kesalahan = 162
  • pesan kesalahan = unknown identifier
  • nama identifier = Jumlah

Adanya pesan kesalahan tersebut akan memudahkan pemrogram dalam mencari dan mengoreksi sumber dari kesalahan.

REAKSI KOMPILATOR PADA KESALAHAN

Terdapat beberapa tingkatan reaksi yang dilakukan oleh kompilator saat menemukan kesalahan, yaitu :
  1. Reaksi-reaksi yang tidak dapat diterima (tidak melaporkan error);
a.   Kompilator crash: berhenti atau hang.
b.  Looping: kompilator masih berjalan tapi tidak pernah berakhir karena looping tak berhingga (indefinite/onbounded loop)
c.  Menghasilkan program objek yang salah: kompilator melanjutkan proses sampai selesai tapi program objek yang dihasilkan salah. Ini berbahaya bila tidak diketahui pemrogram, karena baru akan muncul saat program dieksekusi.
  1. Reaksi yang benar tapi kurang dapat diterima dan kurang bermanfaat. Kompilator menemukan kesalahan pertama, melaporkannya, lalu berhenti (halt). Ini bisa muncul bila pembuat kompilator menganggap jarang terjadi kemunculan error dalam program sehingga kemampuan kompilator untuk mendeteksi dan melaporkan kesalahan hanya satu untuk setiap kali kompilasi. Pemrogram akan membuang waktu untuk melakukan pengulangan kompilasi setiap kali terdapat sebuah error.
  2. Reaksi-reaksi yang dapat diterima:
a.  Reaksi yang sudah dapat dilakukan, yaitu kompilator melaporkan error, dan selanjutnya melakukan :
    Recovery/pemulihan, lalu melanjutkan mencari error lain bila masih ada.
    Repair/perbaikan kesalahan, lalu melanjutkan proses translasi dan menghasilkan program objek yang valid.
Kebanyakan kompilator dewasa ini sudah memiliki kemampuan recovery dan repair.
b.  Reaksi yang belum dapat dilakukan, yaitu kompilator mengkoreksi kesalahan, lalu menghasilkan program objek sesuai dengan yang diinginkan pemrogram. Disini komputernya sudah memiliki kecerdasan untuk mengetahui maksud pemrogram. Tingkatan respon ini belum dapat diimplementasikan pada kompilator yang ada dewasa ini.

ERROR RECOVERY

Pemulihan kesalahan bertujuan mengembalikan kondisi parser kekondisi stabil (supaya bisa melanjutkan proses parsing keposisi selanjutnya). Strategi untuk melakukan error recovery sebagai berikut:
  1. Mekanisme Ad Hoc. Recovery yang dilakukan tergantung dari pembuat kompilator sendiri/spesifik dan tidak terikat pada suatu aturan tertentu. Cara ini bisa disebut juga sebagai special purpose error recovery.
  2. Syntax directed recovery. Melakukan recovery berdasarkan syntax. Contoh :
            Begin
          A:=A+1
          B:=B+1;
          C:=C+1
     end;
kompilator akan mengenali sebagai (dalam notasi BNF):
            begin<statement>?<statement>;<statement>end;
'?' akan dikenali sebagai ';'
  1. Secondary Error Recovery berguna untuk melokalisir error, dengan cara sebagai berikut:
a.   Panic Mode. Maju terus dan mengabaikan teks sampai bertemu delimiter (';'). contoh,
                              IF A:=1
                              Kondisi := true;
Pada teks diatas tidak terdapat instuksi THEN, kompilator akan maju terus/skip sampai bertemu titik koma.
b.  Unit Deletion. Menghapus keseluruhan suatu unit sintaktik (misal: <blok>, <exp>, <statement> ). Efeknya mirip dengan panic mode tetapi unit deletion memelihara kebenaran sintaksis dari source program dan mempermudah untuk melakukan error repairing lebih lanjut.
  1. Context Sensitive Recovery. Berkaitan dengan semantik, misal bila terdapat variabel yang belum dideklarasikan (Undefined Variable) maka diasumsikan tipenya berdasarkan kemunculannya.        Contoh :
                              B:= 'nama'
sementara diawal program variabel B belum dideklarasikan, maka  berdasarkan kemunculannya diasumsikan variabel B bertipe string.

ERROR REPAIRING

Perbaikan kesalahan bertujuan memodifikasi source program dari kesalahan dan membuatnya valid sehingga memungkinkan kompilator untuk melakukan translasi program yang mana akan dialirkan ketahapan selanjutnya pada proses kompilasi. Mekanismenya sebagai berikut :
  1. Mekanisme Ad Hoc. Tergantung dari pembuat kompilator sendiri/spesifik.
  2. Syntax Directed Repar. Menyisipkan simbol terminal yang dianggap hilang atau membuang terminal penyebab kesalahan. Contoh :algoritma berikut kurang instruksi DO
                        WHILE A < 1
            I:=I+1;
Kompilator akan menyisipkan DO
contoh lain :
                        Procedure Increment;
          begin
            x:=x+1;
          end;
          end;
terdapat kelebihan simbol end, yang menyebabkan kesalahan maka kompilator akan membuangnya.

  1. Context Sensitive Repair. Perbaikan dilakukan pada kesalahan berikut.
a.  Tipe Identifier. Diatasi dengan membangkitkan identifier dummy, contoh:
                              Var A:string;
            begin
              A:=0;
            end;
kompilator akan memperbaiki kesalahan dengan membangkitkan identifier baru, misal B yang bertipe integer.
b.   Tipe  Konstanta diatasi dengan membangkitkan konstanta baru dengan tipe yang tepat.
  1. Spelling Repair. Memperbaiki kesalahan pengetikan pada identifier, misal:
                        WHILLE A=1 DO
identifier yang salah tersebut akan diperbaiki menjadi WHILE.