1%% -*- erlang-indent-level: 2 -*- 2%% 3%% Licensed under the Apache License, Version 2.0 (the "License"); 4%% you may not use this file except in compliance with the License. 5%% You may obtain a copy of the License at 6%% 7%% http://www.apache.org/licenses/LICENSE-2.0 8%% 9%% Unless required by applicable law or agreed to in writing, software 10%% distributed under the License is distributed on an "AS IS" BASIS, 11%% WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12%% See the License for the specific language governing permissions and 13%% limitations under the License. 14%% 15%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 16%% @doc 17%% CONSTTAB - maps labels to constants. 18%% <p> 19%% <strong> Note:</strong> 'constant' is a misnomer throughout this code. 20%% </p> 21%% <p> 22%% There are two different types of constants that can be stored: 23%% <ul> 24%% <li>Erlang terms</li> 25%% <li>Blocks of binary data</li> 26%% </ul> 27%% </p> 28%% <p> 29%% Erlang terms are just what you would expect, you can store any 30%% Erlang term in the constant table. 31%% The term is assumed to be loaded to the place in memory denoted by the 32%% label returned by the insertion function. 33%% </p> 34%% <p> 35%% Blocks of binary data comes in some different shapes, you can 36%% either insert a block of integers (of byte, word (4 bytes), or 37%% word (8 bytes) size) or a list of references to code. 38%% These references will then be threated as word sized addresses 39%% and can be used for jumptables. 40%% The list of references can have an optional ordering, so that 41%% you can create a jumptable that will be sorted on the load-time 42%% representation of e.g. atoms. 43%% </p> 44%% @type ctdata() = #ctdata{}. See {@link mk_ctdata/4}. 45%% @type ct_type() = term | block | sorted_block | ref 46%% @type data() = term() | [term()] | [byte()] | internal(). 47%% This type is dependent on ct_type 48%% <ul> 49%% <li> If ct_type() = term -- data() = term() </li> 50%% <li> If ct_type() = block -- data() = [byte()] </li> 51%% <li> If ct_type() = sorted_block -- data() = [term()] </li> 52%% <li> If ct_type() = ref -- data() = internal() </li> 53%% </ul> 54%% @type ct_alignment(). 55%% Alignment is always a power of two equal to the number of bytes 56%% in the machine word. 57%% @end 58%% @type byte(). <code>B</code> is an integer between 0 and 255. 59%% @type hipe_consttab(). 60%% An abstract datatype for storing data. 61%% @end 62%% Internal note: 63%% A hipe_consttab is a tuple {Data, ReferedLabels, NextConstLabel} 64%% @type hipe_constlbl(). 65%% An abstract datatype for referring to data. 66%% @type element_type() = byte | word 67%% @type block() = [integer() | label_ref()] 68%% @type label_ref() = {label, Label::code_label()} 69%% @type code_label() = hipe_sparc:label_name() | hipe_x86:label_name() 70%% @end 71%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 72-module(hipe_consttab). 73 74-export([new/0, % new() -> ConstTab 75 insert_term/2, % insert_term(ConstTab, Term) -> {NewTab, Lbl} 76 %% insert_fun/2, % insert_term(ConstTab, Fun) -> {NewTab, Lbl} 77 %% insert_word/2, % insert_word(ConstTab, Value) -> {NewTab, Lbl} 78 insert_sorted_block/2, % insert_word(ConstTab, ValueList) -> 79 % {NewTab, Lbl} 80 insert_sorted_block/4, 81 insert_block/3, 82 insert_binary_const/3, 83 %% insert_global_word/2, 84 %% insert_global_block/4, 85 %% update_word/3, % update_word(ConstTab, Value) -> {NewTab, Lbl} 86 %% update_block/5, 87 %% update_global_word/3, 88 %% update_global_block/5, 89 lookup/2, % lookup(Key, ConstTab) -> [Term|Block] 90 labels/1, % labels(ConstTab) -> LabelList 91 referred_labels/1, % referred_labels(ConstTab) -> LabelList 92 update_referred_labels/2, 93 decompose/1, 94 size_of/1, 95 const_type/1, 96 const_align/1, 97 const_exported/1, 98 const_data/1, 99 const_size/1 100 %% block_size/1 % size of a block in bytes 101 ]). 102 103%%----------------------------------------------------------------------------- 104 105-include("hipe_consttab.hrl"). 106 107-type code_label() :: term(). % XXX: FIXME 108-type label_ref() :: {'label', code_label()}. 109-type block() :: [hipe_constlbl() | label_ref()]. 110 111-type element_type() :: 'byte' | 'word'. 112 113-type sort_order() :: term(). % XXX: FIXME 114 115%%----------------------------------------------------------------------------- 116 117%% @doc Create a new constant table. 118-spec new() -> hipe_consttab(). 119new() -> {tree_empty(), [], 0}. 120 121 122%% @spec insert_term(ConstTab::hipe_consttab(), Term::term()) -> {NewTab, Lbl} 123%% NewTab = hipe_consttab() 124%% Lbl = hipe_constlbl() 125%% @doc Inserts an erlang term into the const table if the term was not 126%% present before, otherwise do nothing. 127-spec insert_term(hipe_consttab(), term()) -> {hipe_consttab(),hipe_constlbl()}. 128insert_term(ConstTab, Term) -> 129 case lookup_const(ConstTab, term, word_size(), false, Term) of 130 {value, Label} -> 131 {ConstTab, Label}; 132 none -> 133 insert_const(ConstTab, term, word_size(), false, Term) 134 end. 135 136 137%% %% @spec insert_fun(ConstTab::hipe_consttab(), Term::term()) -> {NewTab, Lbl} 138%% %% NewTab = hipe_consttab() 139%% %% Lbl = hipe_constlbl() 140%% %% @doc Inserts a Fun into the const table. 141%% %% Don't ask me what this is for... 142%% -spec insert_fun(hipe_consttab(), term()) -> {hipe_consttab(), hipe_constlbl()}. 143%% insert_fun(ConstTab, Fun) -> 144%% insert_const(ConstTab, term, word_size(), false, Fun). 145 146 147%% @spec (ConstTab::hipe_consttab(), TermList::[term()]) -> {NewTab, Lbl} 148%% NewTab = hipe_consttab() 149%% Lbl = hipe_constlbl() 150%% @doc Inserts a list of terms into the const table. 151-spec insert_sorted_block(hipe_consttab(), [term()]) -> {hipe_consttab(), hipe_constlbl()}. 152insert_sorted_block(CTab, TermList) -> 153 insert_const(CTab, sorted_block, word_size(), false, TermList). 154 155%% %% @spec (ConstTab::hipe_consttab(), InitVal::integer()) -> {NewTab, Lbl} 156%% %% NewTab = hipe_consttab() 157%% %% Lbl = hipe_constlbl() 158%% %% @doc Inserts a word into the const table. 159%% %% Shorthand for inserting a word. 160%% insert_word(ConstTab, InitVal) -> 161%% insert_block(ConstTab, word, [InitVal]). 162 163%% %% @spec (ConstTab::hipe_consttab(), InitVal::integer()) -> {NewTab, Lbl} 164%% %% NewTab = hipe_consttab() 165%% %% Lbl = hipe_constlbl() 166%% %% @doc Inserts a word into the const table. 167%% %% This constant should be exported from the function... 168%% %% <strong>Note</strong> Global constants are 169%% %% not supported in current version of HiPE. 170%% insert_global_word(ConstTab, InitVal) -> 171%% insert_global_block(ConstTab, word_size(), word, [InitVal]). 172 173 174%% @spec (ConstTab::hipe_consttab(), 175%% ElementType::element_type(), 176%% InitList::block()) -> {hipe_consttab(), hipe_constlbl()} 177%% @doc Inserts a block into the const table. 178%% The block can consist of references to labels in the code. 179%% This is used for jump tables. These references should be tracked 180%% and the corresponding BBs should not be considered dead. 181-spec insert_block(hipe_consttab(), element_type(), block()) -> 182 {hipe_consttab(), hipe_constlbl()}. 183insert_block({ConstTab, RefToLabels, NextLabel}, ElementType, InitList) -> 184 ReferredLabels = get_labels(InitList, []), 185 NewRefTo = ReferredLabels ++ RefToLabels, 186 {NewTa, Id} = insert_const({ConstTab, NewRefTo, NextLabel}, 187 block, size_of(ElementType), false, 188 {ElementType,InitList}), 189 {insert_backrefs(NewTa, Id, ReferredLabels), Id}. 190 191%% @doc Inserts a binary constant literal into the const table. 192-spec insert_binary_const(hipe_consttab(), ct_alignment(), binary()) -> 193 {hipe_consttab(), hipe_constlbl()}. 194insert_binary_const(ConstTab, Alignment, Binary) 195 when (Alignment =:= 4 orelse Alignment =:= 8 orelse Alignment =:= 16 196 orelse Alignment =:= 32), is_binary(Binary), 197 size(Binary) rem Alignment =:= 0 -> 198 insert_const(ConstTab, block, Alignment, false, 199 {byte, binary_to_list(Binary)}). 200 201 202%% @spec (ConstTab::hipe_consttab(), ElementType::element_type(), 203%% InitList::block(), SortOrder) -> {hipe_consttab(), hipe_constlbl()} 204%% @doc Inserts a block into the const table. 205%% The block can consist of references to labels in the code. 206%% This is used for jump tables. These references should be tracked 207%% and the corresponding BBs should not be considered dead. 208%% At load-time the block will be sorted according to SortOrder. 209%% This is used to make jump tables on atom indices. 210-spec insert_sorted_block(hipe_consttab(), element_type(), block(), sort_order()) -> 211 {hipe_consttab(), hipe_constlbl()}. 212insert_sorted_block({ConstTab, RefToLabels, NextLabel}, 213 ElementType, InitList, SortOrder) -> 214 ReferredLabels = get_labels(InitList, []), 215 NewRefTo = ReferredLabels ++ RefToLabels, 216 {NewTa, Id} = insert_const({ConstTab, NewRefTo, NextLabel}, 217 block, word_size(), false, 218 {ElementType, InitList, SortOrder}), 219 {insert_backrefs(NewTa, Id, ReferredLabels), Id}. 220 221insert_backrefs(Tbl, From, ToLabels) -> 222 lists:foldl(fun(To, Tab) -> 223 insert_ref(Tab, From, To) 224 end, Tbl, ToLabels). 225 226insert_ref({Table, RefToLabels, NextLblNr}, From, To) -> 227 Ref = {To, ref}, 228 case tree_lookup(Ref, Table) of 229 none -> 230 {tree_insert(Ref, [From], Table), RefToLabels, NextLblNr}; 231 {value, RefList} -> 232 {tree_update(Ref, [From|RefList], Table), RefToLabels, NextLblNr} 233 end. 234 235find_refs(To, {Table,_,_}) -> 236 %% returns 'none' or {value, V} 237 tree_lookup({To, ref}, Table). 238 239delete_ref(To, {ConstTab, RefToLabels, NextLabel}) -> 240 {tree_delete({To, ref}, ConstTab), RefToLabels, NextLabel}. 241 242%% TODO: handle refs to labels. 243%% insert_global_block(ConstTab, Align, ElementType, InitList) -> 244%% ByteList = decompose(size_of(ElementType), InitList), 245%% insert_const(ConstTab, block, Align, true, {byte,ByteList}). 246 247get_labels([{label, L}|Rest], Acc) -> 248 get_labels(Rest, [L|Acc]); 249get_labels([I|Rest], Acc) when is_integer(I) -> 250 get_labels(Rest, Acc); 251get_labels([], Acc) -> 252 Acc. 253 254%% @spec size_of(element_type()) -> pos_integer() 255%% @doc Returns the size in bytes of an element_type. 256-spec size_of(element_type()) -> pos_integer(). 257size_of(byte) -> 1; 258size_of(word) -> word_size(). 259 260%% @spec decompose({element_type(), block()}) -> [byte()] 261%% @doc Turns a block into a list of bytes. 262%% <strong>Note:</strong> Be careful with the byte order here. 263-spec decompose({element_type(), block()}) -> [byte()]. 264decompose({ElementType, Data}) -> 265 decompose(size_of(ElementType), Data). 266 267decompose(_Bytes, []) -> 268 []; 269decompose(Bytes, [X|Xs]) -> 270 number_to_bytes(Bytes, X, decompose(Bytes, Xs)). 271 272number_to_bytes(0, X, Bytes) when is_integer(X) -> 273 Bytes; 274number_to_bytes(N, X, Bytes) -> 275 Byte = X band 255, 276 number_to_bytes(N-1, X bsr 8, [Byte|Bytes]). 277 278%% @spec block_size({element_type(), block()}) -> non_neg_integer() 279%% @doc Returns the size in bytes of a block. 280block_size({ElementType, Block}) -> 281 length(Block) * size_of(ElementType); 282block_size({ElementType, Block, _SortOrder}) -> 283 length(Block) * size_of(ElementType). 284 285 286%%-------------------- 287%% ctdata and friends 288%%-------------------- 289 290-type ct_type() :: 'block' | 'ref' | 'sorted_block' | 'term'. 291 292-record(ctdata, {type :: ct_type(), 293 alignment :: ct_alignment(), 294 exported :: boolean(), 295 data :: term()}). 296-type ctdata() :: #ctdata{}. 297 298-spec mk_ctdata(Type::ct_type(), Alignment::ct_alignment(), 299 Exported::boolean(), Data::term()) -> ctdata(). 300mk_ctdata(Type, Alignment, Exported, Data) -> 301 #ctdata{type = Type, alignment = Alignment, exported = Exported, data = Data}. 302 303-spec const_type(ctdata()) -> ct_type(). 304const_type(#ctdata{type = Type}) -> Type. 305 306-spec const_align(ctdata()) -> ct_alignment(). 307const_align(#ctdata{alignment = Alignment}) -> Alignment. 308 309-spec const_exported(ctdata()) -> boolean(). 310const_exported(#ctdata{exported = Exported}) -> Exported. 311 312-spec const_data(ctdata()) -> term(). 313const_data(#ctdata{data = Data}) -> Data. 314 315-spec update_const_data(ctdata(), {_,[_]} | {_,[_],_}) -> ctdata(). 316update_const_data(CTData, Data) -> 317 CTData#ctdata{data = Data}. 318 319%% @doc Returns the size in bytes. 320-spec const_size(ctdata()) -> non_neg_integer(). 321const_size(Constant) -> 322 case const_type(Constant) of 323 %% term: you can't and shouldn't ask for its size 324 block -> block_size(const_data(Constant)); 325 sorted_block -> length(const_data(Constant)) * word_size() 326 end. 327 328-spec word_size() -> ct_alignment(). 329word_size() -> 330 hipe_rtl_arch:word_size(). 331 332 333%%-------------------- 334%% Update a label 335%%-------------------- 336 337 338%% TODO: Remove RefsTOfrom overwitten labels... 339%% update_word(ConstTab, Label, InitVal) -> 340%% update_block(ConstTab, Label, word_size(), word, [InitVal]). 341%% 342%% update_global_word(ConstTab, Label, InitVal) -> 343%% update_global_block(ConstTab, Label, word_size(), word, [InitVal]). 344 345%% 346%% Update info for an existing label 347%% 348%% Returns NewTable 349%% 350%% 351%% update_block(ConstTab, Label, Align, ElementType, InitList) -> 352%% ByteList = decompose(size_of(ElementType), InitList), 353%% update_const(ConstTab, Label, block, Align, false, {ElementType,ByteList}). 354 355update_block_labels(ConstTab, DataLbl, OldLbl, NewLbl) -> 356 Const = lookup(DataLbl, ConstTab), 357 Old = {label, OldLbl}, 358 case const_data(Const) of 359 {Type, Data} -> 360 NewData = update_data(Data, Old, NewLbl), 361 update(ConstTab, DataLbl, update_const_data(Const, {Type,NewData})); 362 {Type, Data, Order} -> 363 NewData = update_data(Data, Old, NewLbl), 364 update(ConstTab, DataLbl, update_const_data(Const, {Type,NewData,Order})) 365 end. 366 367update_data(Data, Old, New) -> 368 [if Lbl =:= Old -> {label, New}; true -> Lbl end || Lbl <- Data]. 369 370%% update_global_block(ConstTab, Label, Align, ElementType, InitList) -> 371%% ByteList = decompose(size_of(ElementType), InitList), 372%% update_const(ConstTab, Label, block, Align, true, ByteList). 373 374%% 375%% Insert a constant in the table, returns {NewTable, Label}. 376%% 377 378insert_const({Table, RefToLabels, NextLblNr}, Type, Alignment, Exported, Data) -> 379 Const = mk_ctdata(Type, Alignment, Exported, Data), 380 {{tree_insert(NextLblNr, Const, Table), RefToLabels, NextLblNr+1}, 381 NextLblNr}. 382 383%% %% Update information for a label, returns NewTable. 384%% %% (Removes old info.) 385%% 386%% update_const({Table, RefToLabels, NextLblNr}, Label, Type, Alignment, Exported, Data) -> 387%% Const = mk_ctdata(Type, Alignment, Exported, Data), 388%% {tree_update(Label, Const, Table), RefToLabels, NextLblNr}. 389 390update({Table, RefToLabels, NextLblNr}, Label, NewConst) -> 391 {tree_update(Label, NewConst, Table), RefToLabels, NextLblNr}. 392 393%% @spec lookup(hipe_constlbl(), hipe_consttab()) -> ctdata() 394%% @doc Lookup a label. 395-spec lookup(hipe_constlbl(), hipe_consttab()) -> ctdata(). 396lookup(Lbl, {Table, _RefToLabels, _NextLblNr}) -> 397 tree_get(Lbl, Table). 398 399%% Find out if a constant term is present in the constant table. 400lookup_const({Table, _RefToLabels, _NextLblNr}, 401 Type, Alignment, Exported, Data) -> 402 Const = mk_ctdata(Type, Alignment, Exported, Data), 403 tree_lookup_key_for_value(Const, Table). 404 405%% @doc Return the labels bound in a table. 406-spec labels(hipe_consttab()) -> [hipe_constlbl() | {hipe_constlbl(), 'ref'}]. 407labels({Table, _RefToLabels, _NextLblNr}) -> 408 tree_keys(Table). 409 410%% @spec referred_labels(hipe_consttab()) -> [hipe_constlbl()] 411%% @doc Return the referred labels bound in a table. 412-spec referred_labels(hipe_consttab()) -> [hipe_constlbl()]. 413referred_labels({_Table, RefToLabels, _NextLblNr}) -> 414 RefToLabels. 415 416 417%% 418%% Change label names in constant blocks (jump_tables). 419%% 420-spec update_referred_labels(hipe_consttab(), 421 [{hipe_constlbl(), hipe_constlbl()}]) -> 422 hipe_consttab(). 423update_referred_labels(Table, LabelMap) -> 424 %% io:format("LabelMap: ~w\nTb:~w\n", [LabelMap, Table]), 425 {Tb, Refs, Next} = 426 lists:foldl( 427 fun({OldLbl, NewLbl}, Tbl) -> 428 case find_refs(OldLbl, Tbl) of 429 none -> 430 Tbl; 431 {value, DataLbls} -> 432 %% A label may be referred several times. 433 UniqueLbls = ordsets:from_list(DataLbls), 434 lists:foldl(fun(DataLbl, AccTbl) -> 435 insert_ref( 436 delete_ref(OldLbl, 437 update_block_labels(AccTbl, DataLbl, OldLbl, NewLbl)), 438 DataLbl, NewLbl) 439 end, 440 Tbl, 441 UniqueLbls) 442 end 443 end, 444 Table, 445 LabelMap), 446 NewRefs = [case lists:keyfind(Lbl, 1, LabelMap) of 447 {_, New} -> New; 448 false -> Lbl 449 end || Lbl <- Refs], 450 %% io:format("NewTb:~w\n", [{Tb, NewRefs, Next}]), 451 {Tb, NewRefs, Next}. 452 453 454%%----------------------------------------------------------------------------- 455%% primitives for constants 456%%----------------------------------------------------------------------------- 457 458%% Since using `gb_trees' is not safe because of term ordering, we use 459%% the `dict' module instead since it matches with =:= on the keys. 460 461tree_keys(T) -> 462 dict:fetch_keys(T). 463 464-spec tree_to_list(dict:dict()) -> [{_, _}]. 465tree_to_list(T) -> 466 dict:to_list(T). 467 468tree_get(Key, T) -> 469 dict:fetch(Key, T). 470 471tree_update(Key, Val, T) -> 472 dict:store(Key, Val, T). 473 474tree_insert(Key, Val, T) -> 475 dict:store(Key, Val, T). 476 477tree_delete(Key, T) -> 478 dict:erase(Key, T). 479 480tree_lookup(Key, T) -> 481 case dict:find(Key, T) of 482 {ok, Val} -> 483 {value, Val}; 484 error -> 485 none 486 end. 487 488-spec tree_empty() -> dict:dict(). 489tree_empty() -> 490 dict:new(). 491 492-spec tree_lookup_key_for_value(ctdata(), dict:dict()) -> 'none' | {'value', _}. 493tree_lookup_key_for_value(Val, T) -> 494 tree_lookup_key_for_value_1(tree_to_list(T), Val). 495 496-spec tree_lookup_key_for_value_1([{_,_}], ctdata()) -> 'none' | {'value', _}. 497tree_lookup_key_for_value_1([{Key, Val}|_], Val) -> 498 {value, Key}; 499tree_lookup_key_for_value_1([_|Left], Val) -> 500 tree_lookup_key_for_value_1(Left, Val); 501tree_lookup_key_for_value_1([], _Val) -> 502 none. 503