This is an archive of the discontinued LLVM Phabricator instance.

[X86]: Adding a new priority function 'guided-src' for Scheduler DAG instruction scheduling.
Needs ReviewPublic

Authored by jbhateja on Jun 24 2017, 9:10 AM.

Details

Summary

Following analysis is in context to bug# 33362 related to instruction scheduling.

1/ PRE-RA scheduler DAG based Instruction Scheduling algorithm which scans instruction bottom up

by default picks instruction as per source order(default) from the available
instructions to be scheduled in next cycle.
Of course  instructions are available in the priority queue only after they
have satisfied precedence and resource constraints.

Thus LZCNT64rr <second_argument> which corresponds to  following IR
   %4 = tail call i64 @llvm.ctlz.i64(i64 %1, i1 false)    <-- SWAP

is scheduled later (remember algorithm works bottom-up so final schedule
    is reverse order of instructions which algo produces.)

2/ Peephole optimizer which kicks in later down the pipeline could fold the TEST

with CMPNE to produce CMPAE in first case (clz_i128) as LZCNT operating on first
argument was adjacent to TEST instruction and both are EFLAGS reg defining MIs.

3/ In second function(clz_i128_swap) due to swapping of llvm.ctlz LZCNT operating

on first argument of function is no longer adjacent to TEST due to reason
mentioned in Point 1/. Which is why flag folding could not happen.

Adding a priority function based on heuristic which takes into
consideration already scheduled instruction which share their operands with
the next instruction to be chosen from from the available queue
under option -pre-RA-sched=guided-src. Fall back priority selection is source order.

This case works, share your thoughts on this and what could be a better heuristic.

Event Timeline

jbhateja created this revision.Jun 24 2017, 9:10 AM
RKSimon edited reviewers, added: andreadb, filcab, MatzeB, RKSimon; removed: llvm-commits.Jun 24 2017, 9:15 AM
RKSimon edited subscribers, added: llvm-commits; removed: MatzeB.

ping @reviewers

RKSimon edited edge metadata.Jun 29 2017, 8:21 AM

I'll leave the scheduler part of the review to someone who understands it better!

include/llvm/CodeGen/SchedulerRegistry.h
64

Fix this comment for createGuidedSrcListDAGScheduler

lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp
2614

(style) Put Weight += 10; on a newline.

test/CodeGen/X86/guided_sched.ll
3

Drop the avx2/skx requirements - you should be able to just use -mattr=+lzcnt

jbhateja updated this revision to Diff 104890.Jun 30 2017, 10:14 AM

Review comments from RKSimon

jbhateja marked 3 inline comments as done.Jul 6 2017, 7:16 AM

@Reviewers , kindly drop in your comments if any.

Thanks

@Reviewers , kindly drop in your comments if any.

jbhateja retitled this revision from [X86]: Adding a priorty selection guided-src for pre-RA instruction scheduling. to [X86]: Adding a new priority function 'guided-src' for Scheduler DAG instruction scheduling..Jul 15 2017, 3:32 AM
jbhateja edited the summary of this revision. (Show Details)
filcab added inline comments.Jul 19 2017, 10:07 PM
lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp
58

This should have a space, otherwise when concatenating the strings we end up with backson.

jbhateja updated this revision to Diff 107480.Jul 20 2017, 4:24 AM

Change for better formatting.

Ping @ reviewers

Ping @ reviewers.

I'm not a scheduler expert so I don't think I can approve this. I have an additional concern - you've added a new scheduler just for one bug - will it ever get used?

I'm not a scheduler expert so I don't think I can approve this. I have an additional concern - you've added a new scheduler just for one bug - will it ever get used?

This is not a new sheduler , its a new priority selector, we have several priority selectors like source order based, bottom up register reduction, hybrid . These priority selector pick the next instruction to be scheduled in the next cycle out of available candidates.

This new priority selector adds another heuristic which is to pick the instruction out of ready to schdule list whose operands have already been scheduled.

It will extend the list of already existing priority selectors which user can select using -pre-RA-sched option.

Thanks

jbhateja updated this revision to Diff 114580.Sep 11 2017, 6:13 AM
MatzeB edited edge metadata.Sep 27 2017, 1:02 PM

Sorry about this review stalling. To give at least some feedback:

  • We generally want to phase out the SelectionDAG schedulers and only have them do a minimal amount of work. The actual scheduling should happen in the MachineScheduler. So ideally we would not add new features here. (That said I can see why you are doing it here: the MachineScheduler currently does not reorder flags producers/users)
  • I believe none of the currently active LLVM developers is really familiar with the SelectionDAG schedulers.

I will try to find time for an actual review soon (otherwise please keep pinging).

Sorry about this review stalling. To give at least some feedback:

  • We generally want to phase out the SelectionDAG schedulers and only have them do a minimal amount of work. The actual scheduling should happen in the MachineScheduler. So ideally we would not add new features here. (That said I can see why you are doing it here: the MachineScheduler currently does not reorder flags producers/users)
  • I believe none of the currently active LLVM developers is really familiar with the SelectionDAG schedulers.

I will try to find time for an actual review soon (otherwise please keep pinging).

Thanks Matze, I undertand your point here.

RKSimon resigned from this revision.Jan 13 2018, 7:03 AM