Re: [GOOGLE] Refactor AutoFDO

[Dehao Chen <dehao at google dot com>]

On Wed, Jul 31, 2013 at 10:14 AM, Xinliang David Li <davidxl@google.com> wrote:
> Another round of documentation  and naming (not for coding style, but
> for clearer semantics) related comments:
>
> David
>
>>
>> namespace autofdo {
>>
>> /* Represent a source location: (function_decl, lineno).  */
>> typedef std::pair<tree, unsigned> decl_lineno;
>> /* Represent an inline stack. vector[0] is the leaf node.  */
>> typedef std::vector<decl_lineno> inline_stack;
>
> leaf or root?

leaf

>
>> /* String array.  */
>> typedef std::vector<const char *> string_vector;
>
> Module name, function name strings or a generic string table??

done
>
>> /* Map from index in string_map to profile count.  */
>> typedef std::map<unsigned, gcov_type> target_map;
>
> What index? function index?  Is profile count function profile count
> or target call count?

done
>
> Should it renamed to icall_target_map to be clearer?

done
>
>> /* Represent profile count: (execution_count, value_profile_histogram.  */
>> typedef std::pair<gcov_type, target_map> count_info;
>>
>
> The executation count is for what entity?

done
>
>> struct string_compare
>> {
>>   bool operator() (const char *a, const char *b) const
>>     { return strcmp (a, b) < 0; }
>> };
>>
>> /* Store a string array, indexed by string position in the array.  */
>> class string_map {
>
> Is it better to rename it to function_name_map ? string_map is too general.

done
>
>
>>  public:
>>   static string_map *create ();
>>
>>   /* For a given string, returns its index.  */
>>   int get_index (const char *name) const;
>>   /* For a given decl, returns the index of the decl name.  */
>>   int get_index_by_decl (tree decl) const;
>>   /* For a given index, returns the string.  */
>>   const char *get_name (int index) const;
>>
>>  private:
>>   string_map () {}
>>   bool read ();
>>
>>   typedef std::map<const char *, unsigned, string_compare> string_index_map;
>>   string_vector vector_;
>>   string_index_map map_;
>> };
>>
>> /* Profile of a function copy:
>>      1. total_count of the copy.
>>      2. head_count of the copy (only valid when the copy is a top-level
>> symbol, i.e. it is the original copy instead of the inlined copy).
>>      3. map from source location (decl_lineno) to profile (count_info).
>
> Source location of the inlined callsite?

done
>
>>      4. map from callsite (64 bit integer, higher 32 bit is source location
>> (decl_lineno), lower 32 bit is callee function name index in
>> string_map) to callee symbol.  */
>> class symbol {
>
>
> May be rename it to " function_instance" ?

done
>
>> public:
>>   typedef std::vector<symbol *> symbol_stack;
>>
>>   /* Read the profile and create a symbol with head count as  HEAD_COUNT.
>>      Recursively read callsites to create nested symbols too. STACK is used
>>      to track the recursive creation process.  */
>>   static const symbol *read_symbol (symbol_stack *stack, gcov_type head_count);
>>
>>   /* Recursively deallocate all callsites (nested symbols).  */
>>   ~symbol ();
>>
>>   /* Accessors.  */
>>   unsigned name () const { return name_; }
>>   gcov_type total_count () const { return total_count_; }
>>   gcov_type head_count () const { return head_count_; }
>>
>>   /* Recursively traverse STACK starting from LEVEL to find the corresponding
>>      symbol.  */
>>   const symbol *get_symbol (const inline_stack &stack, unsigned level) const;
>>
>>   /* Return the profile info for LOC.  */
>>   bool get_count_info (location_t loc, count_info *info) const;
>>
>> private:
>>   symbol (unsigned name, gcov_type head_count)
>>       : name_(name), total_count_(0), head_count_(head_count) {}
>>   const symbol *get_symbol_by_decl (unsigned lineno, tree decl) const;
>>
>>   /* Map from callsite (64 bit integer, higher 32 bit is source location
>>      (decl_lineno), lower 32 bit is callee function name index in
>>      string_map) to callee symbol.  */
>>   typedef std::map<gcov_type, const symbol *> callsite_map;
>
> Why not making a pair and use it as the key?

done
>
>>   /* Map from source location (decl_lineno) to profile (count_info).  */
>>   typedef std::map<unsigned, count_info> position_count_map;
>>
>>   /* symbol name index in the string map.  */
>
>
> Index in string_vector or string_map?

done
>
>>   unsigned name_;
>>   /* The total sampled count.  */
>>   gcov_type total_count_;
>>   /* The total sampled count in the head bb.  */
>>   gcov_type head_count_;
>>   /* Map from callsite location to callee symbol.  */
>>   callsite_map callsites;
>>   /* Map from source location to count and instruction number.  */
>>   position_count_map pos_counts;
>> };
>>
>> /* Profile for all functions.  */
>> class symbol_map {
>
>
> symbol_map --> program_profiles or afdo_profile ?

done
>
>> public:
>>   static symbol_map *create ()
>>     {
>>       symbol_map *map = new symbol_map ();
>>       if (map->read ())
>> return map;
>>       delete map;
>>       return NULL;
>>     }
>>   ~symbol_map ();
>>   /* For a given DECL, returns the top-level symbol.  */
>>   const symbol *get_symbol_by_decl (tree decl) const;
>>   /* Find profile info for a given gimple STMT. If found, store the profile
>>      info in INFO, and return true; otherwise return false.  */
>>   bool get_count_info (gimple stmt, count_info *info) const;
>>   /* Find total count of the callee of EDGE.  */
>>   gcov_type get_callsite_total_count (struct cgraph_edge *edge) const;
>>
>> private:
>>   /* Map from symbol name index (in string_map) to symbol.  */
>>   typedef std::map<unsigned, const symbol *> Namesymbol_map;
>>
>>   symbol_map () {}
>>   bool read ();
>>   /* Return the symbol in the profile that correspond to the inline STACK.  */
>>   const symbol *get_symbol_by_inline_stack (const inline_stack &stack) const;
>>
>>   Namesymbol_map map_;
>> };
>>
>> /* Module profile.  */
>> class module_map {
>
> afdo_module_profile ?

done
>
>> public:
>>   static module_map *create ()
>>     {
>>       module_map *map = new module_map ();
>>       if (map->read ())
>> return map;
>>       delete map;
>>       return NULL;
>>     }
>>
>>   /* For a given module NAME, returns this module's gcov_m
>
> On Tue, Jul 30, 2013 at 4:48 PM, Dehao Chen <dehao@google.com> wrote:
>> Patch updated to fix the code style and documentation.
>>
>> Thanks,
>> Dehao
>>
>> On Tue, Jul 30, 2013 at 2:24 PM, Xinliang David Li <davidxl@google.com> wrote:
>>> I have some preliminary comments. Mostly just related to code style
>>> and missing documentation.
>>>
>>> David
>>>
>>>>
>>>> #define DEFAULT_AUTO_PROFILE_FILE "fbdata.afdo"
>>>>
>>>> struct SourceLocation
>>>
>>> Is using Upper case in struct names allowed?
>>>
>>>> {
>>>>   tree func_decl;
>>>>   unsigned lineno;
>>>> };
>>>>
>>>> typedef std::vector<const char *> StringVector;
>>>> typedef std::vector<SourceLocation> InlineStack;
>>>> typedef std::map<unsigned, gcov_type> TargetMap;
>>>>
>>>
>>> Add short description of each new types.
>>>
>>>> struct ProfileInfo
>>>> {
>>>>   gcov_type count;
>>>>   TargetMap target_map;
>>>> };
>>>>
>>>> struct StringCompare
>>>> {
>>>>   bool operator() (const char* a, const char* b) const
>>>
>>> '*' should bind to name.
>>>
>>>>     { return strcmp (a, b) < 0; }
>>>> };
>>>>
>>>
>>>> class StringMap {
>>>>  public:
>>>>   static StringMap *Create();
>>>>   int GetIndex (const char *name) const;
>>>>   int GetIndexByDecl (tree decl) const;
>>>>   const char *GetName (int index) const;
>>>>
>>>>  private:
>>>>   StringMap () {}
>>>>   bool Read ();
>>>>
>>>>   typedef std::map<const char *, unsigned, StringCompare> StringIndexMap;
>>>>   StringVector vector_;
>>>>   StringIndexMap map_;
>>>> };
>>>
>>> Add some documentation on the new type, indicating what is 'index'.
>>>
>>>>
>>>> class Symbol {
>>>
>>> The name 'Symbol' is too generic -- can cause conflicts in the future
>>> unless namespace is used. ALso missing documentation.
>>>
>>>>  public:
>>>>   typedef std::vector<Symbol *> SymbolStack;
>>>
>>> Fix indentation problems.
>>>
>>>
>>>>
>>>>   /* Read the profile and create a symbol with head count as  HEAD_COUNT.
>>>>      Recursively read callsites to create nested symbols too. STACK is used
>>>>      to track the recursive creation process.  */
>>>>   static const Symbol *ReadSymbol (SymbolStack *stack, gcov_type head_count);
>>>>
>>>>   /* Recursively deallocate all callsites (nested symbols).  */
>>>>   ~Symbol ();
>>>>
>>>>   /* Accessors.  */
>>>>   unsigned name () const { return name_; }
>>>>   gcov_type total_count () const { return total_count_; }
>>>>   gcov_type head_count () const { return head_count_; }
>>>>
>>>>   /* Recursively traverse STACK starting from LEVEL to find the corresponding
>>>>      symbol.  */
>>>>   const Symbol *GetSymbol (const InlineStack &stack, unsigned level) const;
>>>>
>>>>   /* Return the profile info for LOC.  */
>>>>   bool GetProfileInfo (location_t loc, ProfileInfo *info) const;
>>>>
>>>>  private:
>>>>   Symbol (unsigned name, gcov_type head_count)
>>>>       : name_(name), total_count_(0), head_count_(head_count) {}
>>>>   const Symbol *GetSymbolByDecl (unsigned lineno, tree decl) const;
>>>>
>>>>   typedef std::map<gcov_type, const Symbol *> CallsiteMap;
>>>
>>> Need documentation for this map.
>>>
>>>>   typedef std::map<unsigned, ProfileInfo> PositionCountMap;
>>>
>>> Need documentation.
>>>
>>>>
>>>>   /* Symbol name index in the string map.  */
>>>>   unsigned name_;
>>>>   /* The total sampled count.  */
>>>>   gcov_type total_count_;
>>>>   /* The total sampled count in the head bb.  */
>>>>   gcov_type head_count_;
>>>>   /* Map from callsite location to callee symbol.  */
>>>>   CallsiteMap callsites;
>>>>   /* Map from source location to count and instruction number.  */
>>>>   PositionCountMap pos_counts;
>>>> };
>>>>
>>>> class SymbolMap {
>>>
>>> Need documentation.
>>>
>>>>  public:
>>>>   static SymbolMap *Create ()
>>>>     {
>>>>       SymbolMap *map = new SymbolMap ();
>>>>       if (map->Read ())
>>>> return map;
>>>>       delete map;
>>>>       return NULL;
>>>>     }
>>>>   ~SymbolMap ();
>>>>   const Symbol *GetSymbolByDecl (tree decl) const;
>>>>   bool GetProfileInfo (gimple stmt, ProfileInfo *info) const;
>>>>   gcov_type GetCallsiteTotalCount (struct cgraph_edge *edge) const;
>>>
>>>  Missing documentation for the interfaces
>>>>
>>>>  private:
>>>
>>>>   typedef std::map<unsigned, const Symbol *> NameSymbolMap;
>>>
>>> map from what to symbol?
>>>
>>>>
>>>>   SymbolMap () {}
>>>>   bool Read ();
>>>>   const Symbol *GetSymbolByInlineStack (const InlineStack &stack) const;
>>>
>>>  Missing documentation for the interfaces
>>>
>>>
>>>>
>>>>   NameSymbolMap map_;
>>>> };
>>>>
>>>> class ModuleMap {
>>>
>>> Need documentation.
>>>
>>> On Tue, Jul 30, 2013 at 11:03 AM, Dehao Chen <dehao@google.com> wrote:
>>>> I just rebased the CL to head and updated the patch.
>>>>
>>>> Thanks,
>>>> Dehao
>>>>
>>>> On Tue, Jul 30, 2013 at 10:09 AM, Xinliang David Li <davidxl@google.com> wrote:
>>>>> I can not apply the patch cleanly in my v17 gcc client -- there is
>>>>> some problem in auto-profile.c.
>>>>>
>>>>> David
>>>>>
>>>>> On Mon, Jul 29, 2013 at 7:52 PM, Dehao Chen <dehao@google.com> wrote:
>>>>>> This patch refactors AutoFDO to use:
>>>>>>
>>>>>> 1. C++ to rewrite the whole thing.
>>>>>> 2. Use tree instead of hashtable to represent the profile.
>>>>>> 3. Make AutoFDO standalone: keep changes to other modules minimum.
>>>>>>
>>>>>> Bootstrapped and passed regression test and benchmark test.
>>>>>>
>>>>>> OK for google-4_8 branch?
>>>>>>
>>>>>> Thanks,
>>>>>> Dehao
>>>>>>
>>>>>> http://codereview.appspot.com/12079043

Attachment: patch.txt
Description: Text document